Александр Степанов Менг Ли РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL)

comp_programming

Александр

Степанов

stepanov@mti.sgi.com

Менг

Ли

lee@hlp.hp.com

РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL)

1999 ru

Алексей

Суханов

Андрей

Кутырин

honorato bonafe

Fiction Book Designer, FB Editor v2.0

02.09.2009 FBD-9F0713-1705-7D48-14A2-7EFB-4F34-F62F8A 1.0

1.0 chm-›fb2

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ РАДИОТЕХНИКИ, ЭЛЕКТРОНИКИ И АВТОМАТИКИ (ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ) Москва 1999

Александр Степанов Менг Ли РУКОВОДСТВО ПО СТАНДАРТНОЙ БИБЛИОТЕКЕ ШАБЛОНОВ (STL)

Введение

Стандартная Библиотека Шаблонов предоставляет набор хорошо сконструированных и согласованно работающих вместе обобщённых компонентов C++. Особая забота была проявлена для обеспечения того, чтобы все шаблонные алгоритмы работали не только со структурами данных в библиотеке, но также и с встроенными структурами данных C++. Например, все алгоритмы работают с обычными указателями. Ортогональный проект библиотеки позволяет программистам использовать библиотечные структуры данных со своими собственными алгоритмами, а библиотечные алгоритмы - со своими собственными структурами данных. Хорошо определённые семантические требования и требования сложности гарантируют, что компонент пользователя будет работать с библиотекой и что он будет работать эффективно. Эта гибкость обеспечивает широкую применимость библиотеки.

Другое важное соображение - эффективность. C++ успешен, потому что он объединяет выразительную мощность с эффективностью. Много усилий было потрачено, чтобы проверить, что каждый шаблонный компонент в библиотеке имеет обобщённую реализацию, которая имеет эффективность выполнения с разницей в пределах нескольких процентов от эффективности соответствующей программы ручной кодировки.

Третьим соображением в проекте была разработка библиотечной структуры, которая, будучи естественной и лёгкой для понимания, основана на прочной теоретической основе.

Структура библиотеки

Библиотека содержит пять основных видов компонентов:

- алгоритм (algorithm): определяет вычислительную процедуру.

- контейнер (container): управляет набором объектов в памяти.

- итератор (iterator): обеспечивает для алгоритма средство доступа к содержимому контейнера.

- функциональный объект (function object): инкапсулирует функцию в объекте для использования другими компонентами.

- адаптер (adaptor): адаптирует компонент для обеспечения различного интерфейса.

Такое разделение позволяет нам уменьшить количество компонентов. Например, вместо написания функции поиска элемента для каждого вида контейнера мы обеспечиваем единственную версию, которая работает с каждым из них, пока удовлетворяется основной набор требований.

Следующее описание разъясняет структуру библиотеки. Если программные компоненты сведены в таблицу как трёхмерный массив, где одно измерение представляет различные типы данных (например, int, double), второе измерение представляет различные контейнеры (например, вектор, связный список, файл), а третье измерение представляет различные алгоритмы с контейнерами (например, поиск, сортировка, перемещение по кругу), если i, j и k - размеры измерений, тогда должно быть разработано i* j *k различных версий кода. При использовании шаблонных функций, которые берут параметрами типы данных, нам нужно только j * k версий. Далее, если заставим наши алгоритмы работать с различными контейнерами, то нам нужно просто j+k версий. Это значительно упрощает разработку программ, а также позволяет очень гибким способом использовать компоненты в библиотеке вместе с определяемыми пользователем компонентами. Пользователь может легко определить специализированный контейнерный класс и использовать для него библиотечную функцию сортировки. Для сортировки пользователь может выбрать какую-то другую функцию сравнения либо через обычный указатель на сравнивающую функцию, либо через функциональный объект (объект, для которого определён operator()), который сравнивает. Если пользователю необходимо выполнить передвижение через контейнер в обратном направлении, то используется адаптер reverse_iterator.

Библиотека расширяет основные средства C++ последовательным способом, так что программисту на C/C++ легко начать пользоваться библиотекой. Например, библиотека содержит шаблонную функцию merge (слияние). Когда пользователю нужно два массива a и b объединить в с, то это может быть выполнено так:

int a[1000];

int b[2000];

int c[3000];

…

merge(a, a+1000, b, b+2000, c);

Когда пользователь хочет объединить вектор и список (оба - шаблонные классы в библиотеке) и поместить результат в заново распределённую неинициализированную память, то это может быть выполнено так:

vector‹Employee› a;

list‹Employee› b;

…

Employee* с = allocate(a.size() + b.size(), (Employee*)0);

merge(a.begin(), a.end(), b.begin(), b.end(), raw_storage_iterator‹Employee*, Employee›(c));

где begin() и end() - функции-члены контейнеров, которые возвращают правильные типы итераторов или указателе-подобных объектов, позволяющие merge выполнить задание, а raw_storage_iterator - адаптер, который позволяет алгоритмам помещать результаты непосредственно в неинициализированную память, вызывая соответствующий конструктор копирования.

Во многих случаях полезно перемещаться через потоки ввода-вывода таким же образом, как через обычные структуры данных. Например, если мы хотим объединить две структуры данных и затем сохранить их в файле, было бы хорошо избежать создания вспомогательной структуры данных для хранения результата, а поместить результат непосредственно в соответствующий файл. Библиотека обеспечивает и istream_iterator, и ostream_iterator шаблонные классы, чтобы многие из библиотечных алгоритмов могли работать с потоками ввода-вывода, которые представляют однородные блоки данных. Далее приводится программа, которая читает файл, состоящий из целых чисел, из стандартного ввода, удаляя все числа, делящиеся на параметр команды, и записывает результат в стандартный вывод:

main(int argc, char** argv) {

if (argc!= 2) throw("usage: remove_if_divides integer\n ");

remove_copy_if(istream_iterator‹int›(cin), istream_iterator‹int›(), ostream_iterator‹int›(cout, "\n"), not1(bind2nd(modulus‹int›(), atoi(argv[1]))));

}

Вся работа выполняется алгоритмом remove_copy_if, который читает целые числа одно за другим, пока итератор ввода не становится равным end-of-stream (конец-потока) итератору, который создаётся конструктором без параметров. (Вообще все алгоритмы работают способом "отсюда досюда", используя два итератора, которые показывают начало и конец ввода.) Потом remove_copy_if записывает целые числа, которые выдерживают проверку, в выходной поток через итератор вывода, который связан с cout. В качестве предиката remove_copy_if использует функциональный объект, созданный из функционального объекта modulus‹int›, который берёт i и j и возвращает i % j как бинарный предикат, и превращает в унарный предикат, используя bind2nd, чтобы связать второй параметр с параметром командной строки atoi(argv[1]). Потом отрицание этого унарного предиката получается с помощью адаптера функции not1.

Несколько более реалистичный пример - фильтрующая программа, которая берёт файл и беспорядочно перетасовывает его строки.

main(int argc, char**) {

if (argc!= 1) throw("usage: shuffle\n");

vector‹string› v;

copy(istream_iterator‹string›(cin), istream_iterator‹string›(), inserter(v, v.end()));

random_shuffle(v.begin(), v.end());

copy(v.begin(), v.end(), ostream_iterator‹string›(cout));

}

В этом примере copy перемещает строки из стандартного ввода в вектор, но так как вектор предварительно не размещён в памяти, используется итератор вставки, чтобы вставить в вектор строки одну за другой. (Эта методика позволяет всем функциям копирования работать в обычном режиме замены также, как в режиме вставки.) Потом random_shuffle перетасовывает вектор, а другой вызов copy копирует его в поток cout.

Требования

Для гарантии совместной работы различные компоненты библиотеки должны удовлетворять некоторым основным требованиям. Требования должны быть общими, насколько это возможно, так что вместо высказывания "класс X должен определить функцию-член operator++() ", мы говорим "для любого объекта x класса X определён ++x ". (Не определено, является ли оператор членом или глобальной функцией.) Требования установлены в терминах чётких выражений, которые определяют допустимые условия типов, удовлетворяющих требованиям. Для каждого набора требований имеется таблица, которая определяет начальный набор допустимых выражений и их семантику. Любой обобщённый алгоритм, который использует требования, должен быть написан в терминах допустимых выражений для своих формальных параметров.

Если требуется, чтобы была операция линейного времени сложности, это значит - не хуже, чем линейного времени, и операция постоянного времени удовлетворяет требованию.

В некоторых случаях мы представили семантические требования, использующие код C++. Такой код предназначен как спецификация эквивалентности одной конструкции другой, не обязательно как способ, которым конструкция должна быть реализована (хотя в некоторых случаях данный код, однозначно, является оптимальной реализацией).

Основные компоненты

Этот раздел содержит некоторые основные шаблонные функции и классы, которые используются в остальной части библиотеки.

Операторы (Operators)

Чтобы избежать избыточных определений operator!= из operator== и operator›, ‹=, ›= из operator‹, библиотека обеспечивает следующее:

template ‹class Tl, class T2›

inline bool operator!=(const T1& x, const T2& y) {

return !(x == y);

}

template ‹class Tl, class T2›

inline bool operator›(const T1& x, const T2& y) {

return y ‹ x;

}

template ‹class Tl, class T2›

inline bool operator‹=(const T1& x, const T2& y) {

return !(y ‹ x);

}

template ‹class Tl, class T2›

inline bool operator›=(const T1& x, const T2& y) {

return !(x ‹ y);

}

Пара (Pair)

Библиотека включает шаблоны для разнородных пар значений.

template ‹class T1, class T2›

struct pair {

T1 first;

T2 second;

pair() {}

pair(const T1& x, const T2& y): first(x), second(y) {}

};

template ‹class T1, class T2›

inline bool operator==(const pair‹Tl,T2›& x, const pair‹Tl,T2›& y) {

return x.first == y.first && x.second == y.second;

}

template ‹class T1, class T2›

inline bool operator‹(const pair‹Tl,T2›& x, const pair‹Tl,T2›& y) {

return x.first ‹ y.first || (!(y.first ‹ x.first) && x.second ‹ y.second);

}

Библиотека обеспечивает соответствующую шаблонную функцию make_pair, чтобы упростить конструкцию пар. Вместо выражения, например:

return pair‹int, double›(5, 3.1415926); // явные типы,

можно написать

return make_pair(5, 3.1415926); // типы выводятся.

template ‹class Tl, class T2›

inline pair‹Tl,T2› make_pair(const T1& x, const T2& y) {

return pair‹Tl,T2›(x, y);

}

Итераторы

Итераторы - это обобщение указателей, которые позволяют программисту работать с различными структурами данных (контейнерами) единообразным способом. Чтобы создать шаблонные алгоритмы, которые правильно и эффективно работают с различными типами структур данных, нам нужно формализовать не только интерфейсы, но также семантику и предположения сложности итераторов. Итераторы - это объекты, которые имеют operator*, возвращающий значение некоторого класса или встроенного типа T, называемого значимым типом (value type) итератора. Для каждого типа итератора X, для которого определено равенство, имеется соответствующий знаковый целочисленный тип, называемый типом расстояния (distanсe type) итератора.

Так как итераторы - обобщение указателей, их семантика - обобщение семантики указателей в C++. Это гарантирует, что каждая шаблонная функция, которая использует итераторы, работает с обычными указателями. Есть пять категорий итераторов в зависимости от операций, определённых для них: ввода (input iterators), вывода (output iterators), последовательные (forward iterators), двунаправленные (bidirectional iterators) и произвольного доступа (random access iterators.) Последовательные итераторы удовлетворяют всем требованиям итераторов ввода и вывода и могут использоваться всякий раз, когда определяется тот или другой вид. Двунаправленные итераторы удовлетворяют всем требованиям последовательных итераторов и могут использоваться всякий раз, когда определяется последовательный итератор. Итераторы произвольного доступа удовлетворяют всем требованиям двунаправленных итераторов и могут использоваться всякий раз, когда определяется двунаправленный итератор. Имеется дополнительный атрибут, который могли быть иметь последовательные, двунаправленные и произвольного доступа итераторы, то есть они могут быть модифицируемые (mutable) или постоянные (constant) в зависимости от того, ведёт ли себя результат operator* как ссылка или как ссылка на константу. Постоянные итераторы не удовлетворяют требованиям итераторов вывода.

Таблица 1. Отношения среди категорий итераторов

Произвольного доступа -› Двунаправленные -› Последовательные -->	- › Ввода
	- › Вывода

Точно также, как обычный указатель на массив гарантирует, что имеется значение указателя, указывающего за последний элемент массива, так и для любого типа итератора имеется значение итератора, который указывает за последний элемент соответствующего контейнера. Эти значения называются законечными (past-the-end) значениями. Значения итератора, для которых operator* определён, называются разыменовываемыми (dereferenceable). Библиотека никогда не допускает, что законечные значения являются разыменовываемыми. Итераторы могут также иметь исключительные (singular) значения, которые не связаны ни с каким контейнером. Например, после объявления неинициализированного указателя x (например, int* x;), всегда должно предполагаться, что x имеет исключительное значение указателя. Результаты большинства выражений не определены для исключительных значений. Единственное исключение - присваивание неисключительного значения итератору, который имеет исключительное значение. В этом случае исключительное значение перезаписывается таким же образом, как любое другое значение. Разыменовываемые и законечные значения всегда являются неисключительными.

Итератор j называется доступным (reachable) из итератора i, если и только если имеется конечная последовательность применений operator++ к i, которая делает i==j. Если i и j относятся к одному и тому же контейнеру, тогда или j доступен из i, или i доступен из j, или оба доступны (i==j).

Большинство алгоритмических шаблонов библиотеки, которые работают со структурами данных, имеют интерфейсы, которые используют диапазоны. Диапазон - это пара итераторов, которые указывают начало и конец вычисления. Интервал [i,i) - пустой диапазон; вообще, диапазон [i,j) относится к элементам в структуре данных, начиная с элемента, указываемого i, и до элемента, но не включая его, указываемого j. Диапазон [i,j) допустим, если и только если j доступен из i. Результат применения алгоритмов библиотеки к недопустимым диапазонам не определён.

Все категории итераторов требуют только те функции, которые осуществимы для данной категории со сложностью постоянного времени (амортизированные). Поэтому таблицы требований для итераторов не имеют столбца сложности.

В следующих разделах мы принимаем: a и b - значения X, n - значение типа расстояния Distance, u, tmp и m - идентификаторы, r и s - леводопустимые (lvalues) значения X, t - значение значимого типа T.

Итераторы ввода (Input iterators)

Класс или встроенный тип X удовлетворяет требованиям итератора ввода для значимого типа T, если справедливы следующие выражения:

Таблица 2. Требования итератора ввода

выражение	возвращаемый тип	семантика исполнения	утверждение/примечание состояние до/после
X(a)	-	-	X(a) - копия a. примечание: предполагается деструктор.
X u(a); X u = a;	-	-	после: u - копия a.
u = a	X&	-	после: u - копия a.
a == b	обратимый в bool	-	если a - копия b, тогда a == b возвращает true. == - это отношение эквивалентности в области действия ==.
a!= b	обратимый в bool	!(a == b)	-
*a	обратимый в T	-	до: a - разыменовываемое. если a - копия b, то a эквивалентно b.
++r	X&	-	до: r - разыменовываемое. после: r - разыменовываемое или r - законечное.
void r++	void	void ++r	-
*r++	Т	{X tmp = r; ++r; return tmp;}	-

ПРИМЕЧАНИЕ. Для итераторов ввода нет никаких требований на тип или значение r++ кроме требования, чтобы *r++ работал соответственным образом. В частности, r == s не подразумевает, что ++r == ++s. (Равенство не гарантирует свойство замены или ссылочной прозрачности.) Что касается ++r, то нет больше никаких требований на значения любых копий r за исключением того, что они могут быть безопасно уничтожены или присвоены. После выполнения ++r не требуется, чтобы были копии (предыдущего) r в области ==. Алгоритмы с итераторами ввода никогда не должны пытаться проходить через тот же самый итератор дважды. Они должны быть однопроходными (single pass) алгоритмами. Не требуется, чтобы значимый тип T был леводопустимым типом (lvalue type). Эти алгоритмы могут использоваться с входными потоками как источниками входных данных через класс istream_iterator.

Итераторы вывода (Output iterators)

Класс или встроенный тип X удовлетворяет требованиям итератора вывода, если справедливы следующие выражения:

Таблица 3. Требования итератора вывода

выражение	возвращаемый тип	семантика исполнения	утверждение/примечание состояние до/после
X(a)	-	-	a = t эквивалентно X(a) = t. примечание: предполагается деструктор.
X u(a); X u = a;	-	-	-
*a = t	результат не используется	-	-
++r	X&	-	-
r++	Х или Х&	-	-

ПРИМЕЧАНИЕ. Единственное допустимое использование operator* - на левой стороне выражения присваивания. Присваивание через то же самое значение итератора происходит только однажды. Алгоритмы с итераторами вывода никогда не должны пытаться проходить через тот же самый итератор дважды. Они должны быть однопроходными (single pass) алгоритмами. Равенство и неравенство не обязательно определены. Алгоритмы, которые берут итераторы вывода, могут использоваться с выходными потоками для помещения в них данных через класс ostream_iterator, также как с итераторами вставки и вставляющими указателями. В частности, следующие два условия должны соблюдаться: во-первых, через любое значение итератора должно выполняться присваивание до его увеличения (то есть, для итератора вывода i недопустима последовательность кода i++; i++;); во-вторых, любое значение итератора вывода может иметь только одну активную копию в любое данное время (например, недопустима последовательность кода i = j; *++i = a; *j = b;).

Последовательные итераторы (Forward iterators)

Класс или встроенный тип X удовлетворяет требованиям последовательного итератора, если справедливы следующие выражения:

Таблица 4. Требования последовательного итератора

выражение	возвращаемый тип	семантика исполнения	утверждение/примечание состояние до/после
X u;	-	-	примечание: u может иметь исключительное значение. примечание: предполагается деструктор.
X()	-	-	примечание: X() может быть исключительным.
X(a);	-	-	a == X(a)
X u(a); X u = a;	-	X u; u = a;	после: u == a.
a == b	обратимый в bool	-	== - это отношение эквивалентности.
a!= b	обратимый в bool	!(a == b)	-
r = a	X&	-	после: r == a.
*a	обратимый в T	-	до: a - разыменовываемое. a==b подразумевает a==b. Если X - модифицируемый, то *a = t - допустимо.
++r	X&	-	до: r - разыменовываемое. после: r - разыменовываемое или r - законечное. r == s и r - разыменовываемое подразумевает ++r==++s. &r==&++r.
r++	X	{X tmp = r; ++ r; return tmp;}	-

ПРИМЕЧАНИЕ. Тот факт, что r == s подразумевает ++r == ++s (что неверно для итераторов ввода и вывода) и что удалено ограничение на число присваиваний через итератор (которое применяется к итераторам вывода), позволяет использование многопроходных однонаправленных алгоритмов с последовательными итераторами.

Двунаправленные итераторы (Bidirectional iterators)

Класс или встроенный тип X удовлетворяет требованиям двунаправленного итератора, если к таблице, которая определяет последовательные итераторы, мы добавим следующие строки:

Таблица 5. Требования двунаправленного итератора (в дополнение к последовательному итератору)

выражение	возвращаемый тип	семантика исполнения	утверждение/примечание состояние до/после
--r	X&	-	до: существует s такое, что r==++s. после: s - разыменовываемое. --(++r)==r. --r==--s подразумевает r==s.&r==&--r.
r--	X	{X tmp = r; --r; return tmp;}	-

ПРИМЕЧАНИЕ. Двунаправленные итераторы позволяют алгоритмам перемещать итераторы назад так же, как вперёд.

Итераторы произвольного доступа (Random access iterators)

Класс или встроенный тип X удовлетворяет требованиям итераторов произвольного доступа, если к таблице, которая определяет двунаправленные итераторы, мы добавим следующие строки:

Таблица 6: Требования итератора произвольного доступа (в дополнение к двунаправленному итератору)

выражение	возвращаемый тип	семантика исполнения	утверждение/примечание состояние до/после
r += n	X&	{Distance m = n; if(m ›= 0) while(m--) ++r; else while(m++) --r; return r;}	-
a + n n + a	X	{X tmp = a; return tmp += n;}	a + n == n + a.
r -= n	X&	return r += -n;	-
a - n	X	{X tmp = a; return tmp -= n;}	-
b - a	Distance	-	до: существует значение n типа Distance такое, что a+n=b. b==a+(b-a).
a[n]	обратимый в T	*(a + n)	-
a ‹ b	обратимый в bool	b - a › 0	‹ - это отношение полного упорядочения
a › b	обратимый в bool	b ‹ a	› - это отношение полного упорядочения, противоположное ‹.
a ›= b	обратимый в bool	!(a ‹ b)	-
a ‹= b	обратимый в bool	!(a › b)	-

Теги итераторов (Iterator tags)

Чтобы осуществлять алгоритмы только в терминах итераторов, часто бывает необходимо вывести тип значения и тип расстояния из итератора. Для решения этой задачи требуется, чтобы для итератора i любой категории, отличной от итератора вывода, выражение value_type(i) возвращало (T*)(0), а выражение distance_type(i) возвращало (Distance*)(0). Для итераторов вывода эти выражения не требуются.

Примеры использования тегов итераторов

Для всех типов обычных указателей мы можем определить value_type и distance_type с помощью следующего:

template ‹class T›

inline T* value_type(const T*) {return (T*)(0);}

template ‹class T›

inline ptrdiff_t* distance_type(const T*) {return (ptrdiff_t*)(0);}

Тогда, если мы хотим осуществить обобщённую функцию reverse, мы пишем следующее:

template ‹class BidirectionalIterator›

inline void reverse(BidirectionalIterator first, BidirectionalIterator last) {

_reverse(first, last, value_type(first), distance_type(first));

}

где _reverse определена следующим образом:

template ‹class BidirectionalIterator, class T, class Distance›

void _reverse(BidirectionalIterator first, BidirectionalIterator last, T*, Distance*) {

Distance n;

distance(first, last, n); // смотри раздел "Операции с итераторами"

--n;

while (n › 0) {

T tmp = *first;

*first++ = *--last;

*last = tmp;

n -= 2;

}

Если имеется дополнительный тип указателя _huge такой, что разность двух указателей _huge имеет тип long long, мы определяем:

template ‹class T›

inline T* value_type(const T _huge *) {return (T*) (0);}

template ‹class T›

inline long long* distance_type(const T _huge *) {

return (long long*)(0);

}

Часто желательно для шаблонной функции выяснить, какова наиболее специфичная категория её итераторного аргумента, так чтобы функция могла выбирать наиболее эффективный алгоритм во время компиляции. Чтобы облегчить это, библиотека вводит классы тегов категорий (category tag), которые используются как теги времени компиляции для выбора алгоритма. Это следущие теги: input_iterator_tag, output_iterator_tag, forward_iterator_tag, bidirectional_iterator_tag и random_access_iterator_tag. Каждый итератор i должен иметь выражение iterator_category(i), определённое для него, которое возвращает тег наиболее специфичной категории, который описывает его поведение. Например, мы определяем, что все типы указателей находятся в категории итераторов произвольного доступа:

template ‹class T›

inline random_access_iterator_tag iterator_category(const T*) {

return random_access_iterator_tag();

}

Определяемый пользователем итератор BinaryTreeIterator может быть включен в категорию двунаправленных итераторов следующим образом:

template ‹class T›

inline bidirectional_iterator_tag iterator_category(const BinaryTreeIterator‹T›&) {

return bidirectional_iterator_tag();

}

Если шаблонная функция evolve хорошо определена для двунаправленных итераторов, но может быть осуществлена более эффективно для итераторов произвольного доступа, тогда реализация выглядит так:

template ‹class BidirectionalIterator›

inline void evolve(BidirectionalIterator first, BidirectionalIterator last) {

evolve(first, last, iterator_category(first));

}

template ‹class BidirectionalIterator›

void evolve(BidirectionalIterator first, BidirectionalIterator last, bidirectional_iterator_tag) {

//… более универсальный, но менее эффективный алгоритм

}

template ‹class RandomAccessIterator›

void evolve(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag) {

//… более эффективный, но менее универсальный алгоритм

}

Примитивы, определённые в библиотеке

Чтобы упростить задачу определения iterator_category, value_type и distance_type для определяемых пользователем итераторов, библиотека обеспечивает следующие предопределённые классы и функции:

// iterator tags (теги итераторов)

struct input_iterator_tag {};

struct output_iterator_tag {};

struct forward_iterator_tag {};

struct bidirectional_iterator_tag {};

struct random_access_iterator_tag {};

// iterator bases (базовые классы итераторов)

template ‹class T, class Distance = ptrdiff_t› struct input_iterator {};

struct output_iterator {};

// output_iterator не шаблон, потому что у итераторов вывода

// не определены ни значимый тип, ни тип расстояния.

template ‹class T, class Distance = ptrdiff_t›

struct forward_iterator {};

template ‹class T, class Distance = ptrdiff_t›

struct bidirectional_iterator {};

template ‹class T, class Distance = ptrdiff_t›

struct random_access_iterator {};

// iterator_category (функции категорий итераторов)

template ‹class T, class Distance›

inline input_iterator_tag iterator_category(const input_iterator‹T, Distance›&) {

return input_iterator_tag();

}

inline output_iterator_tag iterator_category(const output_iterator&) {

return output_iterator_tag();

}

template ‹class T, class Distance›

inline forward_iterator_tag iterator_category(const forward_iterator‹T, Distance›&) {

return forward_iterator_tag();

}

template ‹class T, class Distance›

inline bidirectional_iterator_tag iterator_category(const bidirectional_iterator‹T, Distance›&) {

return bidirectional_iterator_tag();

}

template ‹class T, class Distance›

inline random_access_iterator_tag iterator_category(const random_access_iterator‹T, Distance›&) {

return random_access_iterator_tag();

}

template ‹class T›

inline random_access_iterator_tag iterator_category(const T*) {

return random_access_iterator_tag();

}

// value_type of iterator (функции значимого типа итераторов)

template ‹class T, class Distance›

inline T* value_type(const input_iterator‹T, Distance›&) {

return (T*) (0);

}

template ‹class T, class Distance›

inline T* value_type(const forward_iterator‹T, Distance›&) {

return (T*) (0);

}

template ‹class T, class Distance›

inline T* value_type(const bidirectional_iterator‹T, Distance›&) {

return (T*) (0);

}

template ‹class T, class Distance›

inline T* value_type(const random_access_iterator‹T, Distance›&) {

return (T*) (0);

}

template ‹class T›

inline T* value_type(const T*) {return (T*) (0);}

// distance_type of iterator (функции типа расстояния итераторов)

template ‹class T, class Distance›

inline Distance* distance_type(const input_iterator‹T, Distance›&) {

return (Distance*) (0);

}

template ‹class T, class Distance›

inline Distance* distance_type(const forward_iterator‹T, Distance›&) {

return (Distance*) (0);

}

template ‹class T, class Distance›

inline Distance* distance_type(const bidirectional_iterator‹T, Distance›&) {

return (Distance*) (0);

}

template ‹class T, class Distance›

inline Distance* distance_type(const random_access_iterator‹T, Distance›&) {

return (Distance*) (0);

}

template ‹class T›

inline ptrdiff_t* distance_type(const T*) {return (ptrdiff_t*) (0);}

Если пользователь хочет определить двунаправленный итератор для некоторой структуры данных, содержащей double, и такой, чтобы работал с большой (large) моделью памяти компьютера, то это может быть сделано таким определением:

class MyIterator: public bidirectional_iterator ‹double, long› {

// код, осуществляющий ++, и т.д.

};

Тогда нет необходимости определять iterator_category, value_type, и distance_type в MyIterator.

Операции с итераторами (Iterator operations)

Так как только итераторы произвольного доступа обеспечивают + и - операторы, библиотека предоставляет две шаблонные функции advance и distance. Эти функции используют + и - для итераторов произвольного доступа (и имеют, поэтому, сложность постоянного времени для них); для итераторов ввода, последовательных и двунаправленных итераторов функции используют ++, чтобы обеспечить реализацию со сложностью линейного времени. advance берет отрицательный параметр n только для итераторов произвольного доступа и двунаправленных итераторов. advance увеличивает (или уменьшает для отрицательного n) итераторную ссылку i на n. distance увеличивает n на число единиц, сколько требуется, чтобы дойти от first до last.

template ‹class InputIterator, class Distance›

inline void advance(InputIterator& i, Distance n);

template ‹class InputIterator, class Distance›

inline void distance(InputIterator first, InputIterator last, Distance& n);

distance должна быть функцией 3-х параметров, сохраняющей результат в ссылке вместо возвращения результата, потому что тип расстояния не может быть выведен из встроенных итераторных типов, таких как int*.

Функциональные объекты

Функциональные объекты - это объекты, для которых определён operator(). Они важны для эффективного использования библиотеки. В местах, где ожидается передача указателя на функцию алгоритмическому шаблону, интерфейс установлен на приём объекта с определённым operator(). Это не только заставляет алгоритмические шаблоны работать с указателями на функции, но также позволяет им работать с произвольными функциональными объектами. Использование функциональных объектов вместе с функциональными шаблонами увеличивает выразительную мощность библиотеки также, как делает результирующий код более эффективным. Например, если мы хотим поэлементно сложить два вектора a и b, содержащие double, и поместить результат в a, мы можем сделать зто так:

transform(a.begin(), a.end(), b.begin(), a.begin(), plus‹double›());

Если мы хотим отрицать каждый элемент a, мы можем сделать это так:

transform(a.begin(), a.end(), a.begin(), negate‹double›());

Соответствующие функции вставят сложение и отрицание.

Чтобы позволить адаптерам и другим компонентам манипулировать функциональными объектами, которые используют один или два параметра, требуется, чтобы они соответственно обеспечили определение типов (typedefs) argument_type и result_type для функциональных объектов, которые используют один параметр, и first_argument_type, second_argument_type и result_type для функциональных объектов, которые используют два параметра.

Базовые классы (Base)

Следующие классы предоставляются, чтобы упростить определение типов (typedefs) параметров и результата:

template ‹class Arg, class Result›

struct unary_function {

typedef Arg argument_type;

typedef Result result_type;

};

template ‹class Arg1, class Arg2, class Result›

struct binary_function {

typedef Arg1 first_argument_type;

typedef Arg2 second_argument_type;

typedef Result result_type;

};

Арифметические операции (Arithmetic operations)

Библиотека обеспечивает базовые классы функциональных объектов для всех арифметических операторов языка.

template ‹class T›

struct plus: binary_function‹T, T, T› {

Т operator()(const T& x, const T& y) const {return x + y;}

};

template ‹class T›

struct minus: binary_function‹T, T, T› {

Т operator()(const T& x, const T& y) const {return x - y;}

};

template ‹class T›

struct times: binary_function‹T, T, T› {

Т operator()(const T& x, const T& y) const (return x * y;}

};

template ‹class T›

struct divides: binary_function‹T, T, T› {

Т operator()(const T& x, const T& y) const {return x / y;}

};

template ‹class T›

struct modulus: binary_function‹T, T, T› {

Т operator()(const T& x, const T& y) const {return x % y;}

};

template ‹class T›

struct negate: unary_function‹T, T› {

Т operator()(const T& x) const {return -x;}

};

Сравнения (Comparisons)

Библиотека обеспечивает базовые классы функциональных объектов для всех операторов сравнения языка

template ‹class T›

struct equal_to: binary_function‹T, T, bool› {

bool operator()(const T& x, const T& y) const {return x == y;}

};

template ‹class T›

struct not_equal_to: binary_function‹T, T, bool› {

bool operator()(const T& x, const T& y) const {return x!= y;}

};

template ‹class T›

struct greater: binary_function‹T, T, bool› {

bool operator()(const T& x, const T& y) const {return x › y;}

};

template ‹class T›

struct less: binary_function‹T, T, bool› {

bool operator()(const T& x, const T& y) const {return x ‹ y;}

};

template ‹class T›

struct greater_equal: binary_function‹T, T, bool› {

bool operator()(const T& x, const T& y) const {return x ›= y;}

};

template ‹class T›

struct less_equal: binary_function‹T, T, bool› {

bool operator()(const T& x, const T& y) const {return x ‹= y;}

};

Логические операции (Logical operations)

template ‹class T›

struct logical_and: binary_function‹T, T, bool› {

bool operator()(const T& x, const T& y) const {return x&& y;}

};

template ‹class T›

struct logical_or: binary_function‹T, T, bool› {

bool operator()(const T& x, const T& y) const {return x || y;}

};

template ‹class T›

struct logical_not: unary_function‹T, bool› {

bool operator()(const T& x) const {return!x;}

};

Распределители

Одна из общих проблем в мобильности - это способность инкапсулировать информацию относительно модели памяти. Эта информация включает типы указателей, тип их разности, тип размера объектов в этой модели памяти, также как её примитивы выделения и освобождения памяти.

STL принимается за эту проблему, обеспечивая стандартный набор требований для распределителей (allocators), являющихся объектами, которые инкапсулируют эту информацию. Все контейнеры в STL параметризованы в терминах распределителей. Это значительно упрощает задачу взаимодействия с многочисленными моделями памяти.

Требования распределителей (Allocator requirements)

В следующей таблице мы предполагаем, что X - класс распределителей для объектов типа T, a - значение X, n имеет тип X::size_type, p имеет тип X::pointer, r имеет тип X::reference и s имеет тип X::const_reference.

Все операции c распределителями, как ожидается, сводятся к постоянному времени.

Таблица 7. Требования распределителей

выражение	возвращаемый тип	утверждение/примечание состояние до/после
X::value_type	Т	-
X::reference	леводопустимое значение T (lvalue of T)	-
X::const_reference	const lvalue of T	-
X::pointer	указатель на тип T	результатом operator* для значений X::pointer является reference.
X::const_pointer	указатель на тип const T	результат operator* для значений X::const_pointer ― const_reference; это - тот же самый тип указателя, как X::pointer, в частности, sizeof(X::const_pointer)==sizeof(X::pointer).
X:: size_type	беззнаковый целочисленный тип	тип, который может представлять размер самого большого объекта в модели памяти.
X::difference_type	знаковый целочисленный тип	тип, который может представлять разность между двумя любыми указателями в модели памяти.
X a;	-	примечание: предполагается деструктор.
a.address(r)	указатель	*(a.address(r))==r.
a.const_address(s)	const_pointer	*(a.address(s))==s.
a.allocate(n)	X::pointer	память распределяется для n объектов типа T, но объекты не создаются. allocate может вызывать соответствующее исключение.
a.deallocate(p)	результат не используется	все объекты в области, указываемой p, должны быть уничтожены до этого запроса.
construct(p, a)	void	после: *p==a.
destroy(p)	void	значение, указываемое p, уничтожается.
a.init_page_size()	X::size_type	возвращённое значение - оптимальное значение для начального размера буфера данного типа. Предполагается, что если k возвращено функцией init_page_size, t - время конструирования для T, и u - время, которое требуется для выполнения allocate(k), тогда k*t будет намного больше, чем u.
a.max_size()	X::size_type	наибольшее положительное значение X::difference_type

pointer относится к категории модифицируемых итераторов произвольного доступа, ссылающихся на T. const_pointer относится к категории постоянных итераторов произвольного доступа, ссылающихся на T. Имеется определённое преобразование из pointer в const_pointer.

Для любого шаблона распределителя Alloc имеется определение для типа void. У Alloc‹void› определены только конструктор, деструктор и Alloc‹void›::pointer. Преобразования определены из любого Alloc‹T›::pointer в Alloc‹void›::pointer и обратно, так что для любого p будет p == Alloc‹T›::pointer(Alloc‹void›::pointer(p)).

Распределитель по умолчанию (The default allocator)

template ‹class T›

class allocator {

public:

typedef T* pointer;

typedef const T* const_pointer;

typedef T& reference;

typedef const T& const_reference;

typedef T value_type;

typedef size_t size_type;

typedef ptrdiff_t difference_type;

allocator();

~allocator();

pointer address(reference x);

const_pointer const_address(const_reference x);

pointer allocate(size_type n);

void deallocate(pointer p);

size_type init_page_size();

size_type max_size();

};

class allocator‹void› {

public:

typedef void* pointer;

allocator();

~allocator();

};

Предполагается, что в дополнение к allocator поставщики библиотеки обеспечивают распределители для всех моделей памяти.

Контейнеры

Контейнеры - это объекты, которые содержат другие объекты. Они управляют размещением в памяти и свобождением этих объектов через конструкторы, деструкторы, операции вставки и удаления.

В следующей таблице мы полагаем, что X - контейнерный класс, содержащий объекты типа T, a и b - значения X, u - идентификатор, r - значение X&.

Таблица 8. Требования контейнеров

выражение	возвращаемый тип	семантика исполнения	утверждение/примечание состояние до/после	сложность
X::value_type	Т	-	-	время компиляции
X::reference	-	-	-	время компиляции
X::const_reference	-	-	-	время компиляции
X::pointer	тип указателя, указывающий на X::reference	-	указатель на T в модели памяти, используемой контейнером	время компиляции
X::iterator	тип итератора, указывающий на X::reference	-	итератор любой категории, кроме итератора вывода.	время компиляции
X::const_iterator	тип итератора, указывающий на X::const_reference	-	постоянный итератор любой категории, кроме итератора вывода.	время компиляции
X::difference_type	знаковый целочисленный тип	-	идентичен типу расстояния X::iterator и X::const_iterator	время компиляции
X::size_type	беззнаковый целочисленный тип	-	size_type может представлять любое неотрицательное значение difference_type	время компиляции
X u;	-	-	после: u.size()==0.	постоянная
X()	-	-	X().size()==0.	постоянная
X(a)	-	-	a==X(a).	линейная
X u(a); X u==a;	-	X u; u = a;	после: u==a.	линейная
(&a)-›~X()	результат не используется	-	после: a.size()==0. примечание: деструктор применяется к каждому элементу a, и вся память возвращается.	линейная
a.begin()	iterator; const_iterator для постоянного a	-	-	постоянная
a.end()	iterator; const_iterator для постоянного a	-	-	постоянная
a==b	обратимый в bool	a.size()==b.size() && equal(a.begin(), a.end(), b.begin())	== - это отношение эквивалентности. примечание: equal определяется в разделе алгоритмов.	линейная
a!= b	обратимый в bool	!(a==b)	-	линейная
r = a	X&	if(&r!=&a){ (&r)-›X::~X(); new(&r)X(a); return r;}	после: r==a.	линейнaя
a.size()	size_type	size_type n = 0; distance(a.begin(), a.end(), n); return n;	-	постоянная
a.max_size()	size_type	-	size() самого большого возможного контейнера.	постоянная
a.empty()	обратимый в bool	a.size()==0	-	постоянная
a ‹ b	обратимый в bool	lexicographical_compare(a.begin(), a.end(), b.begin(), b.end())	до: ‹ определён для значений T. ‹ - отношение полного упорядочения. lexicographical_compare определяется в разделе алгоритмов.	линейная
a › b	обратимый в bool	b ‹ a	-	линейнaя
a ‹= b	обратимый в bool	!(a › b)	-	линейная
a ›= b	обратимый в bool	!(a ‹ b)	-	линейная
a.swap(b)	void	swap(a, b)	-	постоянная

Функция-член size() возвращает число элементов в контейнере. Её семантика определяется правилами конструкторов, вставок и удалений.

begin() возвращает итератор, ссылающийся на первый элемент в контейнере. end() возвращает итератор, который является законечным.

Если тип итератора контейнера принадлежит к категории двунаправленных итераторов или итераторов произвольного доступа, то контейнер называется reversible (обратимым) и удовлетворяет следующим дополнительным требованиям:

Таблица 9. Требования обратимых контейнеров (в дополнение к контейнерам)

выражение	возвращаемый тип	семантика исполнения	сложность
X::reverse_iterator	-	reverse_iterator‹iterator, value_type, reference, difference_type› для итератора произвольного доступа. reverse_bidirectional_iterator‹iterator, value_type, reference, difference_type› для двунаправленного итератора	время компиляции
X::const_reverse_iterator	-	reverse_iterator‹const_iterator, value_type, const_reference, difference_type› для итератора произвольного доступа. reverse_bidirectional_iterator‹const_iterator, value_type, const_reference, difference_type› для двунаправленного итератора.	время компиляции
a.rbegin()	reverse_iterator; const_reverse_iterator для постоянного a	reverse_iterator(end())	постоянная
a.rend()	reverse_iterator; const_reverse_iterator для постоянного a	reverse_iterator(begin())	постоянная

Последовательности (Sequences)

Последовательность - это вид контейнера, который организует конечное множество объектов одного и того же типа в строгом линейном порядке. Библиотека обеспечивает три основных вида последовательных контейнеров: vector (вектор), list (список) и deque (двусторонняя очередь). Она также предоставляет контейнерные адаптеры, которые облегчают создание абстрактных типов данных, таких как стеки или очереди, из основных видов последовательностей (или из других видов последовательностей, которые пользователь может сам определить).

В следующих двух таблицах X - последовательный класс, a - значение X, i и j удовлетворяют требованиям итераторов ввода, [i, j) - допустимый диапазон, n - значение X::size_type, p - допустимый итератор для a, q - разыменовываемый итератор для a, [q1, q2) - допустимый диапазон в a, t - значение X::value_type.

Сложности выражений зависят от последовательностей.

Таблица 10. Требования последовательностей (в дополнение к контейнерам)

выражение	возвращаемый тип	утверждение/примечание состояние до/после
X(n, t) X a(n, t);	-	после: size()==n. создаёт последовательность с n копиями t.
X(i, j) X a(i, j);	-	после: size()==расстоянию между i и j. создаёт последовательность, равную диапазону [i, j).
a.insert(p, t)	iterator	вставляет копию t перед p. возвращаемое значение указывает на вставленную копию.
a.insert(p, n, t)	результат не используется	вставляет n копий t перед p.
a.insert(p, i, j)	результат не используется	вставляет копии элементов из диапазона [i, j) перед p.
a.erase(q)	результат не используется	удаляет элемент, указываемый q.
a.erase(ql, q2)	результат не используется	удаляет элементы в диапазоне [ql, q2).

vector (вектор), list (список) и deque (двусторонняя очередь) выдвигают программисту различные предложения сложности и должны использоваться соответственно. vectоr - тип последовательности, которая используется по умолчанию. list нужно использовать, когда имеются частые вставки и удаления из середины последовательности, deque - структура данных для выбора, когда большинство вставок и удалений происходит в начале или в конце последовательности.

Типы iterator и const_iterator для последовательностей должны быть, по крайней мере, из категории последовательных итераторов.

Таблица 11. Необязательные операции последовательностей

выражение	возвращаемый тип	семантика исполнения	контейнер
a.front()	reference; const_reference для постоянного a	*a.begin()	vector, list, deque
a.back()	reference; const_reference для постоянного a	*a.(--end())	vector, list, deque
a.push_front(t)	void	a.insert(a.begin(), t)	list, deque
a.push_back(t)	void	a.insert(a.end(), t)	vector, list, deque
a.pop_front()	void	a.erase(a.begin())	list, deque
a.pop_back()	void	a.erase(--a.end())	vector, list, deque
a[n]	reference; const_reference для постоянного a	*(a.begin() + n)	vector, deque

Все операции в расположенной выше таблице обеспечиваются только для контейнеров, для которых они занимают постоянное время.

Вектор (Vector)

vector - вид последовательности, которая поддерживает итераторы произвольного доступа. Кроме того, он поддерживает операции вставки и удаления в конце с постоянным (амортизированным) временем; вставка и удаление в середине занимают линейное время. Управление памятью обрабатывается автоматически, хотя для улучшения эффективности можно давать подсказки.

template ‹class T, template ‹class U› class Allocator = allocator›

class vector {

public:

// определения типов (typedefs):

typedef iterator;

typedef const_iterator;

typedef Allocator‹T›::pointer pointer;

typedef Allocator‹T›::reference reference;

typedef Allocator‹T›::const_reference const_reference;

typedef size_type;

typedef difference_type;

typedef T value_type;

typedef reverse_iterator;

typedef const_reverse_iterator;

// размещение/освобождение (allocation/deallocation):

vector();

vector(size_type n, const T& value = T());

vector(const vector‹T, Allocator›& x);

template ‹class InputIterator›

vector(InputIterator first, InputIterator last);

~vector();

vector‹T, Allocator›& operator=(const vector‹T, Allocator›& x);

void reserve(size_type n);

void swap(vector‹T, Allocator›& x);

// средства доступа (accessors):

iterator begin();

const_iterator begin() const;

iterator end();

const_iterator end() const;

reverse_iterator rbegin();

const_reverse_iterator rbegin();

reverse_iterator rend();

const_reverse_iterator rend();

size_type size() const;

size_type max_size() const;

size_type capacity() const;

bool empty() const;

reference operator[](size_type n);

const_reference operator[](size_type n) const;

reference front();

const_reference front() const;

reference back();

const_reference back() const;

// вставка/стирание (insert/irase):

void push_back(const T& x);

iterator insert(iterator position, const T& x = T());

void insert(iterator position, size_type n, const T& x);

template ‹class InputIterator›

void insert(iterator position, InputIterator first, InputIterator last);

void pop_back();

void erase(iterator position);

void erase(iterator first, iterator last);

};

template ‹class T, class Allocator›

bool operator==(const vector‹T, Allocator›& x, const vector‹T, Allocator›& y);

template ‹class T, class Allocator›

bool operator‹(const vector‹T, Allocator›& x, const vector‹T, Allocator›& y);

iterator - это итератор произвольного доступа, ссылающийся на T. Точный тип зависит от исполнения и определяется в Allocator.

const_iterator - это постоянный итератор произвольного доступа, ссылающийся на const T. Точный тип зависит от исполнения и определяется в Allocator. Гарантируется, что имеется конструктор для const_iterator из iterator.

size_type - беззнаковый целочисленный тип. Точный тип зависит от исполнения и определяется в Allocator.

difference_type - знаковый целочисленный тип. Точный тип зависит от исполнения и определяется в Allocator.

Конструктор template ‹class InputIterator› vector(InputIterator first, InputIterator last) делает только N вызовов конструктора копирования T (где N - расстояние между first и last) и никаких перераспределений, если итераторы first и last относятся к последовательной, двунаправленной или произвольного доступа категориям. Он делает, самое большее, 2N вызовов конструктора копирования T и logN перераспределений, если они - только итераторы ввода, так как невозможно определить расстояние между first и last и затем сделать копирование.

Функция-член capasity (ёмкость) возвращает размер распределённой памяти в векторе. Функция-член reserve - директива, которая сообщает vector (вектору) запланированноe изменение размера, так чтобы он мог соответственно управлять распределением памяти. Это не изменяет размер последовательности и занимает, самое большее, линейное время от размера последовательности. Перераспределение в этом случае происходит тогда и только тогда, когда текущая ёмкость меньше, чем параметр reserve. После reserve ёмкость (capasity) больше или равна параметру reserve, если происходит перераспределение; а иначе равна предыдущему значению capasity. Перераспределение делает недействительными все ссылки, указатели и итераторы, ссылающиеся на элементы в последовательности. Гарантируется, что нет никакого перераспределения во время вставок, которые происходят после того, как reserve выполняется, до времени, когда размер вектора достигает размера, указанного reserve.

insert (вставка) вызывает перераспределение, если новый размер больше, чем старая ёмкость. Если никакого перераспределения не происходит, все итераторы и ссылки перед точкой вставки остаются справедливыми. Вставка единственного элемента в вектор линейна относительно расстояния от точки вставки до конца вектора. Амортизированная сложность во время жизни вектора, вставляющего единственный элемент в свой конец, постоянна. Вставка множественных элементов в вектор с единственным вызовом вставляющей функции-члена линейна относительно суммы числа элементов плюс расстояние до конца вектора. Другими словами, намного быстрее вставить много элементов в середину вектора сразу, чем делать вставку по одному элементу. Шаблонная вставляющая функция-член предраспределяет достаточно памяти для вставки, если итераторы first и last относятся к последовательной, двунаправленной или произвольного доступа категориям. Иначе функция вставляет элементы один за другим и не должна использоваться для вставки в середину векторов.

erase (стирание) делает недействительными все итераторы и ссылки после пункта стирания. Деструктор T вызывается столько раз, каково число стёртых элементов, а оператор присваивания T вызывается столько раз, каково число элементов в векторе после стёртых элементов.

Чтобы оптимизировать распределение места, даётся определение для bool.

class vector‹bool, allocator› {

public:

// битовая ссылка (bit reference):

class reference {

public:

~reference();

operator bool() const;

reference& operator=(const bool x);

void flip(); // инвертирует бит (flips the bit)

};

// определения типов (typedefs):

typedef bool const_reference;

typedef iterator;

typedef const_iterator;

typedef size_t size_type;

typedef ptrdiff_t difference_type;

typedef bool value_type;

typedef reverse_iterator;

typedef const_reverse_iterator;

// размещение/освобождение (allocation/deallocation):

vector();

vector(size_type n, const bool& value = bool());

vector(const vector‹bool, allocator›& x);

template ‹class InputIterator›

vector(InputIterator first, InputIterator last);

~vector();

vector‹bool, allocator›& operator=(const vector‹bool, allocator›& x);

void reserve(size_type n);

void swap(vector‹bool, allocator›& x);

// средства доступа (accessors):

iterator begin();

const_iterator begin() const;

iterator end();

const_iterator end() const;

reverse_iterator rbegin();

const_reverse_iterator rbegin();

reverse_iterator rend();

const_reverse_iterator rend();

size_type size() const;

size_type max_size() const;

size_type capacity() const;

bool empty() const;

reference operator[](size_type n);

const_reference operator[](size_type n) const;

reference front();

const_reference front() const;

reference back();

const_reference back() const;

// вставка/стирание (insert/irase):

void push_back(const bool& x);

iterator insert(iterator position, const bool& x = bool());

void insert(iterator position, size_type n, const bool& x);

template ‹class InputIterator›

void insert(iterator position, InputIterator first, InputIterator last);

void pop_back();

void erase(iterator position);

void erase(iterator first, iterator last);

};

void swap(vector‹bool, allocator›::reference x, vector‹bool, allocator›::reference y);

bool operator==(const vector‹bool, allocator›& x, const vector‹bool, allocator›& y);

bool operator‹(const vector‹bool, allocator›& x, const vector‹bool, allocator›& y);

reference - класс, который имитирует поведение ссылок отдельного бита в vector‹bool›.

Ожидается, что каждое исполнение обеспечит определение vector‹bool› для всех поддерживаемых моделей памяти.

Сейчас невозможно шаблонизировать определение. То есть мы не можем написать:

template ‹template ‹class U› class Allocator = allocator›

class vector‹bool, Allocator› {/*… */};

Поэтому обеспечивается только vector‹bool, Allocator›.

Список (List)

list - вид последовательности, которая поддерживает двунаправленные итераторы и позволяет операции вставки и стирания с постоянным временем в любом месте последовательности, с управлением памятью, обрабатываемым автоматически. В отличие от векторов и двусторонних очередей, быстрый произвольный доступ к элементам списка не поддерживается, но многим алгоритмам, во всяком случае, только и нужен последовательный доступ.

template ‹class T, template ‹class U› class Allocator = allocator›

class list {

public:

// определения типов:

typedef iterator;

typedef const_iterator;

typedef Allocator‹T›::pointer pointer;

typedef Allocator‹T›::reference reference;

typedef Allocator‹T›::const_reference const_reference;

typedef size_type;

typedef difference_type;

typedef Т value_type;

typedef reverse_iterator;

typedef const_reverse_iterator;

// размещение/удаление:

list()

list(size_type n, const T& value = T());

template ‹class InputIterator›

list(InputIterator first, InputIterator last);

list(const list‹T, Allocator›& x);

~list();

list‹T, Allocator›& operator=(const list‹T,Allocator›& x);

void swap(list‹T, Allocator& x);

// средства доступа:

iterator begin();

const_iterator begin() const;

iterator end();

const_iterator end() const;

reverse_iterator rbegin();

const_reverse_iterator rbegin();

reverse_iterator rend();

const_reverse_iterator rend();

bool empty() const;

size_type size() const;

size_type max_size() const;

reference front();

const_reference front() const;

reference back();

const_reference back() const;

// вставка/стирание:

void push_front(const T& x);

void push_back(const T& x);

iterator insert(iterator position, const T& x = T());

void insert(iterator position, size_type n, const T& x);

template ‹class InputIterator›

void insert(iterator position, InputIterator first, InputIterator last);

void pop_front();

void pop_back();

void erase(iterator position);

void erase(iterator first, iterator last);

// специальные модифицирующие операции cо списком:

void splice(iterator position, list‹T, Allocator›& x);

void splice(iterator position, list‹T, Allocator›& x, iterator i);

void splice(iterator position, list‹T, Allocator›& x, iterator first, iterator last);

void remove(const T& value);

template ‹class Predicate›

void remove_if(Predicate pred);

void unique();

template ‹class BinaryPredicate›

void unique(BinaryPredicate binary_pred);

void merge(list‹T, Allocator›& x);

template ‹class Compare›

void merge(list‹T,Allocator›& x, Compare comp);

void reverse();

void sort();

template ‹class Compare› void sort(Compare comp);

};

template ‹class T, class Allocator›

bool operator==(const list‹T, Allocator›& x, const list‹T, Allocator›& y);

template ‹class T, class Allocator›

bool operator‹(const list‹T, Allocator›& x, const list‹T, Allocator›& y);

iterator - двунаправленный итератор, ссылающийся на T. Точный тип зависит от исполнения и определяется в Allocator.

const_iterator - постоянный двунаправленный итератор, ссылающийся на const T. Точный тип зависит от исполнения и определяется в Allocator. Гарантируется, что имеется конструктор для const_iterator из iterator.

size_type - беззнаковый целочисленный тип. Точный тип зависит от исполнения и определяется в Allocator.

difference_type - знаковый целочисленный тип. Точный тип зависит от исполнения и определяется в Allocator.

insert не влияет на действительность итераторов и ссылок. Вставка единственного элемента в список занимает постоянное время, и ровно один раз вызывается конструктор копирования T. Вставка множественных элементов в список зависит линейно от числа вставленных элементов, а число вызовов конструктора копирования T точно равно числу вставленных элементов.

erase делает недействительными только итераторы и ссылки для стёртых элементов. Стирание единственного элемента - операция постоянного времени с единственным вызовом деструктора T. Стирание диапазона в списке занимает линейное время от размера диапазона, а число вызовов деструктора типа T точно равно размеру диапазона.

Так как списки позволяют быструю вставку и стирание в середине списка, то некоторые операции определяются специально для них:

list обеспечивает три операции стыковки, которые разрушительно перемещают элементы из одного списка в другой:

void splice(iterator position, list‹T, Allocator›& x) вставляет содержимое x перед position, и x становится пустым. Требуется постоянное время. Результат не определён, если &x==this.

void splice(iterator position, list‹T, Allocator›& x, iterator i) вставляет элемент, указываемый i, из списка x перед position и удаляет элемент из x. Требуется постоянное время. i - допустимый разыменовываемый итератор списка x. Результат не изменяется, если position==i или position==++i.

void splice(iterator position, list‹T, Allocator›& x, iterator first, iterator last) вставляет элементы из диапазона [first, last) перед position и удаляет элементы из x. Требуется постоянное время, если &x==this; иначе требуется линейное время. [first, last) - допустимый диапазон в x. Результат не определён, если position - итератор в диапазоне [first, last).

remove стирает все элементы в списке, указанном итератором списка i, для которого выполняются следующие условия: *i==value, pred(*i)==true. remove устойчиво, то есть относительный порядок элементов, которые не удалены, тот же самый, как их относительный порядок в первоначальном списке. Соответствующий предикат применяется точно size() раз.

unique стирает все, кроме первого элемента, из каждой последовательной группы равных элементов в списке. Соответствующий бинарный предикат применяется точно size() - 1 раз.

merge сливает список аргумента со списком (предполагается, что оба сортированы). Слияние устойчиво, то есть для равных элементов в двух списках элементы списка всегда предшествуют элементам из списка аргумента. x пуст после слияния. Выполняется, самое большее, size() + x.size() - 1 сравнений.

reverse переставляет элементы в списке в обратном порядке. Операция линейного времени.

sort сортирует список согласно operator‹ или сравнивающему функциональному объекту. Она устойчива, то есть относительный порядок равных элементов сохраняется. Выполняется приблизительно NlogN сравнений, где N равно size().

Двусторонняя очередь (Deque)

deque - вид последовательности, которая, подобно вектору, поддерживает итераторы произвольного доступа. Кроме того она поддерживает операции вставки и стирания в начале или в конце за постоянное время; вставка и стирание в середине занимают линейное время. Как с векторами, управление памятью обрабатывается автоматически.

template ‹class T, template ‹class U› class Allocator = allocator›

class deque {

public:

// typedefs:

typedef iterator;

typedef const_iterator;

typedef Allocator‹T›::pointer pointer;

typedef Allocator‹T›::reference reference;

typedef Allocator‹T›::const_reference const_reference;

typedef size_type;

typedef difference_type;

typedef Т value_type;

typedef reverse_iterator;

typedef const_revcrse_iterator;

// размещение/удаление:

deque();

deque(size_type n, const T& value = T());

deque(const deque‹T, Allocator›& x);

template ‹class InputIterator›

deque(InputIterator first, InputIterator last);

~deque();

deque‹T, Allocator›& operator=(const deque‹T,Allocator›& x);

void swap(deque‹T, Allocator›& x);

// средства доступа:

iterator begin();

const_iterator begin() const;

iterator end();

const_iterator end() const;

reverse_iterator rbegin();

const_reverse_iterator rbegin();

reverse_iterator rend();

const_reverse_iterator rend();

size_type size() const;

size_type max_size() const;

bool empty() const;

reference operator[](size_type n);

const_reference operator[](size_type n) const;

reference front();

const_reference front() const;

reference back();

const_reference back() const;

// вставка/стирание:

void push_front(const T& x);

void push_back(const T& x);

iterator insert(iterator position, const T& x = T());

void insert(iterator position, size_type n, const T& x);

template

void insert(iterator position, InputIterator first, InputIterator last);

void pop_front();

void pop_back();

void erase(iterator position);

void erase(iterator first, iterator last);

};

template ‹class T, class Allocator›

bool operator==(const deque‹T, Allocator›& x, const deque‹T, Allocator›& y);

template ‹class T, class Allocator›

bool operator‹(const deque‹T, Allocator›& x, const deque‹T, Allocator›& y);

iterator - итератор произвольного доступа, ссылающийся на T. Точный тип зависит от исполнения и определяется в Allocator.

const_iterator - постоянный итератор произвольного доступа, ссылающийся на const T. Точный тип зависит от исполнения и определяется в Allocator. Гарантируется, что имеется конструктор для const_iterator из iterator.

size_type - беззнаковый целочисленный тип. Точный тип зависит от исполнения и определяется в Allocator.

difference_type - знаковый целочисленный тип. Точный зависит от исполнения и определяется в Allocator.

insert (вставка) в середину двусторонней очереди делает недействительными все итераторы и ссылки двусторонней очереди. insert и push (помещение) с обоих концов двусторонней очереди делают недействительными все итераторы двусторонней очереди, но не влияют на действительность всех ссылок на двустороннюю очередь. В худшем случае вставка единственного элемента в двустороннюю очередь занимает линейное время от минимума двух расстояний: от точки вставки - до начала и до конца двусторонней очереди. Вставка единственного элемента либо в начало, либо в конец двусторонней очереди всегда занимает постоянное время и вызывает единственный запрос конструктора копии T. То есть двусторонняя очередь особенно оптимизирована для помещения и извлечения элементов в начале и в конце.

erase (стирание) в середине двусторонней очереди делает недействительными все итераторы и ссылки двусторонней очереди. erase и pop (извлечение) с обоих концов двусторонней очереди делают недействительными только итераторы и ссылки на стёртый элемент. Число вызовов деструктора равно числу стёртых элементов, а число вызовов оператора присваивания равно минимуму из числа элементов перед стёртыми элементами и числа элементов после стёртых элементов.

Ассоциативные контейнеры (Associative containers)

Ассоциативные контейнеры обеспечивают быстрый поиск данных, основанных на ключах. Библиотека предоставляет четыре основных вида ассоциативных контейнеров: set (множество), multiset (множество с дубликатами), map (словарь) и multimap (словарь с дубликатами).

Все они берут в качестве параметров Key (ключ) и упорядочивающее отношение Compare, которое вызывает полное упорядочение по элементам Key. Кроме того, map и multimap ассоциируют произвольный тип T с Key. Объект типа Compare называется сравнивающим объектом (comparison object) контейнера.

В этом разделе, когда мы говорим о равенстве ключей, мы подразумеваем отношение эквивалентности, обусловленное сравнением и не (not) operator== для ключей. То есть считается, что два ключа k1 и k2 являются равными, если для сравнивающего объекта comp истинно comp(k1, k2)==false && comp(k2, k1)==false.

Ассоциативный контейнер поддерживает уникальные ключи (unique keys), если он может содержать, самое большее, один элемент для каждого значения ключа. Иначе он поддерживает равные ключи (equal keys). set и map поддерживают уникальные ключи. multiset и multimap поддерживают равные ключи.

Для set и multiset значимый тип - тот же самый, что и тип ключа. Для map и multimap он равен pair‹const Key, T›.

iterator ассоциативного контейнера относится к категории двунаправленного итератора. insert не влияет на действительность итераторов и ссылок контейнера, а erase делает недействительными только итераторы и ссылки на стёртые элементы.

В следующей таблице обозначается: X - класс ассоциативного контейнера, a - значение X, a_uniq - значение X, когда X поддерживает уникальные ключи, a a_eq - значение X, когда X поддерживает многократные ключи, i и j удовлетворяют требованиям итераторов ввода и указывают на элементы value_type, [i, j) - допустимый диапазон, p - допустимый итератор для a, q - разыменовываемый итератор для a, [q1, q2) - допустимый диапазон в a, t - значение X::value_type и k - значение X::key_type.

Таблица 12. Требования ассоциативных контейнеров (в дополнение к контейнерам)

выражение	возвращаемый тип	утверждение/примечание состояние до/после	сложность
X::key_type	Key	-	время компиляции
X::key_compare	Compare	по умолчанию less‹key_type›.	время компиляции
X::value_compare	тип бинарного предиката	то же, что key_compare для set и multiset; отношение упорядочения пар, вызванное первым компонентом (т.е. Key), для map и multimap.	время компиляции
X(c); X a(c);	-	создает пустой контейнер; использует с как объект сравнения.	постоянная
X(); X a;	-	создает пустой контейнер; использует Compare() как объект сравнения.	постоянная
X(i,j,c); X a(i,j,c);	-	cоздает пустой контейнер и вставляет в него элементы из диапазона [i, j); использует с как объект сравнения.	вообще NlogN (N - расстояние от i до j); линейная, если [i, j) отсортирован value_comp()
X(i,j); X a(i,j);	-	то же, что выше, но использует Compare() как объект сравнения.	то же, что выше
a.key_comp()	X::key_compare	возвращает объект сравнения, из которого а был создан.	постоянная
a.value_comp()	X::value_compare	возвращает объект value_compare, созданный из объекта сравнения.	постоянная
a_uniq.insert(t)	pair‹iterator, bool›	вставляет t, если и только если в контейнере нет элемента с ключом, равным ключу t. Компонент bool возвращенной пары показывает, происходит ли вставка, а компонент пары iterator указывает на элемент с ключом, равным ключу t.	логарифмическая
a_eq.insert(t)	iterator	вставляет t и возвращает итератор, указывающий на вновь вставленный элемент.	логарифмическая
a.insert(p, t)	iterator	вставляет t, если и только если в контейнерах с уникальными ключами нет элемента с ключом, равным ключу t; всегда вставляет t в контейнеры с дубликатами. всегда возвращает итератор, указывающий на элемент с ключом, равным ключу t. итератор p - подсказка, указывающая, где вставка должна начать поиск.	вообще логарифмическая, но сводится к постоянной, если t вставлен прямо перед p.
a.insert(i, j)	результат не используется	вставляет в контейнер элементы из диапазона [i, j);	вообще Nlog(size()+N) (N - расстояние от i до j); линейная, если [i, j) отсортирован согласно value_comp()
a.erase(k)	size_type	стирает все элементы в контейнере с ключом, равным k. возвращает число уничтоженных элементов.	log(size()) + count(k)
a.erase(q)	результат не используется	стирает элемент, указанный q.	сводится к постоянной
a.erase(ql, q2)	результат не используется	стирает все элементы в диапазоне [ql, q2).	log(size())+ N, где N - расстояние от ql до q2.
a.find(k)	iterator; const_iterator для константы a	возвращает итератор, указывающий на элемент с ключом, равным k, или a.end(), если такой элемент не найден.	логарифмическая
a.count(k)	size_type	возвращает число элементов с ключом, равным k.	log(size()) + count(k)
a.lower_bound(k)	iterator; const_iterator для константы a	возвращает итератор, указывающий на первый элемент с ключом не меньше, чем k.	логарифмическая
a.upper_bound(k)	iterator; const_iterator для константы a	возвращает итератор, указывающий на первый элемент с ключом больше, чем k.	логарифмическая
a.equal_range(k)	pair‹iterator, itеrator›; pair‹const_iterator, const_iterator› для константы a	эквивалент make_pair(lower_bound(k), upper_bound(k)).	логарифмическая

Основным свойством итераторов ассоциативных контейнеров является то, что они выполняют итерации через контейнеры в порядке неубывания ключей, где неубывание определено сравнением, которое использовалось для их создания. Для любых двух разыменованных итераторов i и j таких, что расстояние от i до j является положительным, value_comp (*j, *i)==false. Для ассоциативных контейнеров с уникальными ключами выдерживается более сильное условие value_comp(*i, *j)==true.

Множество (Set)

set - это ассоциативный контейнер, который поддерживает уникальные ключи (не содержит ключи с одинаковыми значениями) и обеспечивает быстрый поиск ключей.

template ‹class Key, class Compare = less‹Key›, template ‹class U› class Allocator = allocator›

class set {

public:

// typedefs:

typedef Key key_type;

typedef Key value_type;

typedef Allocator‹Key›::pointer pointer;

typedef Allocator‹Key›::reference reference;

typedef Allocator‹Key›::const_reference const_reference;

typedef Compare key_compare;

typedef Compare value_compare;

typedef iterator;

typedef iterator const_iterator;

typedef size_type;

typedef difference_type;

typedef reverse_iterator;

typedef const_reverse_iterator;

// allocation/deallocation:

set(const Compare& comp = Compare());

template ‹class InputIterator›

set(InputIterator first, InputIterator last, const Compare& comp = Compare());

set(const set‹Key, Compare, Allocator›& x);

~set();

set‹Key, Compare, Allocator›& operator=(const set‹Key, Compare, Allocator›& x);

void swap(set‹Key, Compare, Allocator›& x);

// accessors:

key_compare key_comp() const;

value_compare value_comp() const;

iterator begin() const;

iterator end() const;

reverse_iterator rbegin() const;

reverse_iterator rend() const;

bool empty() const;

size_type size() const;

size_type max_size() const;

// insert/erase

pair‹iterator, bool› insert(const value_type& x);

iterator insert(iterator position, const value_type& x);

template ‹class InputIterator›

void insert(InputIterator first, InputIterator last);

void erase(iterator position);

size_type erase(const key_type& x);

void erase(iterator first, iterator last);

// set operations:

iterator find(const key_type& x) const;

size_type count(const key_type& x) const;

iterator lower_bound(const key_type& x) const;

iterator upper_bound(const key_type& x) const;

pair‹iterator, iterator› equal_range(const key_type& x) const;

};

template ‹class Key, class Compare, class Allocator›

bool operator==(const set‹Key, Compare, Allocator›& x, const set‹Key, Compare, Allocator›& y);

template ‹class Key, class Compare, class Allocator›

bool operator‹(const set‹Key, Compare, Allocator›& x, const set‹Key, Compare, Allocator›& y);

iterator - постоянный двунаправленный итератор, указывающий на const value_type. Точный тип зависит от реализации и определяется в Allocator.

сonst_iterator - тот же самый тип, что и iterator.

size_type - целочисленный тип без знака. Точный тип зависит от реализации и определяется в Allocator.

difference_type - целочисленный тип со знаком. Точный тип зависит от реализации и определяется в Allocator.

Множество с дубликатами (Multiset)

multiset - это ассоциативный контейнер, который поддерживает равные ключи (возможно, содержит множественные копии того же самого значения ключа) и обеспечивает быстрый поиск ключей.

template ‹class Key, class Compare = less‹Key›, template ‹class U› class Allocator = allocator›

class multiset {

public:

// typedefs:

typedef Key key_type;

typedef Key value_type;

typedef Allocator‹Key›::pointer pointer;

typedef Aliocator‹Key›::reference reference;

typedef Allocator‹Key›::const_reference const_reference;

typedef Compare key_compare;

typedef Compare value_compare;

typedef iterator;

typedef iterator const_iterator;

typedef size_type;

typedef difference_type;

typedef reverse_iterator;

typedef const_reverse_iterator;

// allocation/deallocation:

multiset(const Compare& comp = Compare());

template ‹class InputIterator›

multiset(InputIterator first, InputIterator last, const Compare& comp = Compare());

multiset(const multiset‹Key, Compare, Allocator›& x);

~multiset();

multiset‹Key, Compare, Allocator›& operator=(const multiset‹Key, Compare, Allocator›& x);

void swap(multiset‹Key, Compare, Allocator›& x);

// accessors:

key_compare key_comp() const;

value_compare value_comp() const;

iterator begin() const;

iterator end() const;

reverse_iterator rbegin();

reverse_iterator rend();

bool empty() const;

size_type size() const;

size_type max_size() const;

// insert/erase:

iterator insert(const value_type& x);

iterator insert(iterator position, const value_type& x);

template ‹class InputIterator›

void insert(InputIterator first, InputIterator last);

void erase(iterator position);

size_type erase(const key_type& x);

void erase(iterator first, iterator last);

// multiset operations:

iterator find(const key_type& x) const;

size_type count(const key_type& x) const;

iterator lower_bound(const key_type& x) const;

iterator upper_bound(const key_type& x) const;

pair‹iterator, iterator› equal_range(const key_type& x) const;

};

template ‹class Key, class Compare, class Allocator›

bool operator==(const multiset‹Key, Compare, Allocator›& x, const multiset‹Key, Compare, Allocator›& y);

template ‹class Key, class Compare, class Allocator›

bool operator‹(const multiset‹Key, Compare, Allocator›& x, const multiset‹Key, Compare, Allocator›& y);

сonst_iterator - тот же самый тип, что и iterator.

size_type - целочисленный тип без знака. Точный тип зависит от реализации и определяется в Allocator.

difference_type - целочисленный тип со знаком. Точный тип зависит от реализации и определяется в Allocator.

Словарь (Map)

map - ассоциативный контейнер, который поддерживает уникальные ключи (не содержит ключи с одинаковыми значениями) и обеспечивает быстрый поиск значений другого типа T, связанных с ключами.

template ‹class Key, class T, class Compare = less‹Key›, template ‹class U› class Allocator = allocator›

class map {

public:

// typedefs:

typedef Key key_type;

typedef pair‹const Key, T› value_type;

typedef Compare key_compare;

class value_compare : public binary_function‹value_type, value_type, bool› {

friend class map;

protected:

Compare comp;

value_compare(Compare c): comp(c) {}

public:

bool operator()(const value_type& x, const value_type& y) {

return comp(x.first, y.first);

}

};

typedef iterator;

typedef const_iterator;

typedef Allocator‹value_type›::pointer pointer;

typedef Allocator‹value_type›::reference reference;

typedef Allocator‹value_type›::const_reference const_reference;

typedef size_type;

typedef difference_type;

typedef reverse_iterator;

typedef const_reverse_iterator;

// allocation/deallocation:

map(const Compare& comp = Compare());

template ‹class InputIterator›

map(InputIterator first, InputIterator last, const Compare& comp = Compare());

map(const map‹Key, T, Compare, Allocator›& x);

~map();

map‹Key, T, Compare, Allocator›& operator=(const map‹Key, T, Compare, Allocator›& x);

void swap(map‹Key, T, Compare, Allocator›& x);

// accessors:

key_compare key_comp() const;

value_compare value_comp() const;

iterator begin();

const_iterator begin() const;

iterator end();

const_iterator end() const;

reverse_iterator rbegin();

const_reverse_iterator rbegin();

reverse_iterator rend();

const_reverse_iterator rend();

bool empty() const;

size_type size() const;

size_type max_size() const;

Allocator‹T›::reference operator[](const key_type& x);

// insert/erase:

pair‹iterator, bool› insert(const value_type& x);

iterator insert(iterator position, const value_type& x);

template ‹class InputIterator›

void insert(InputIterator first, InputIterator last);

void erase(iterator position);

size_type erase(const key_type& x);

void erase(iterator first, iterator last);

// map operations:

iterator find(const key_type& x);

const_iterator find(const key_type& x) const;

size_type count(const key_type& x) const;

iterator lower_bound(const key_type& x);

const_iterator lower_bound(const key_type& x) const;

iterator upper_bound(const key_type& x);

const_iterator upper_bound(const key_type& x) const;

pair‹iterator, iterator› equal_range(const key_type& x);

pair‹const_iterator, const_iterator› equal_range(const key_type& x)const;

};

template ‹class Key, class T, class Compare, class Allocator›

bool operator==(const map‹Key, T, Compare, Allocator›& x, const map‹Key, T, Compare, Allocator›& y);

template ‹class Key, class T, class Compare, class Allocator›

bool operator‹(const map‹Key, T, Compare, Allocator›& x, const map‹Key, T, Compare, Allocator›& y);

iterator - двунаправленный итератор, указывающий на value_type. Точный тип зависит от реализации и определяется в Allocator.

const_iterator - постоянный двунаправленный итератор, указывающий на const value_type. Точный тип зависит от реализации и определяется в Allocator. Гарантируется, что имеется конструктор для const_iterator из iterator.

size_type - целочисленный тип без знака. Точный тип зависит от реализации и определяется в Allocator.

difference_type - целочисленный тип со знаком. Точный тип зависит от реализации и определяется в Allocator.

В дополнение к стандартному набору методов ассоциативных контейнеров, map обеспечивает операцию Allocator::reference operator[](const key_type&). Для словаря m и ключа k запись m[k] семантически эквивалентна (*((m.insert(make_pair(k, T()))).first)).second.

Словарь с дубликатами (Multimар)

multimар - ассоциативный контейнер, который поддерживает равные ключи (возможно, содержит множественные копии того же самого значения ключа) и обеспечивает быстрый поиск значений другого типа T, связанных с ключами.

template ‹class Key, class T, class Compare = less‹Key›, template ‹class U› class Allocator = allocator›

class multimap {

public:

// typedefs:

typedef Key key_type;

typedef pair‹const Key, T› value_type;

typedef Compare key_compare;

class value_compare : public binary_function‹value_type, value_type, bool› {

friend class multimap;

protected:

Compare comp;

value_compare(Compare c): comp(c) {}

public:

bool operator()(const value_type& x, const value_type& y) {

return comp(x.first, y.first);

}

};

typedef iterator;

typedef const_iterator;

typedef Allocator‹value_type›::pointer pointer;

typedef Allocator‹value_type›::reference reference;

typedef Allocator‹value_type›::const_reference const_reference;

typedef size_type;

typedef difference_type;

typedef reverse_iterator;

typedef const_reverse_iterator;

// allocation/deallocation:

multimap(const Compare& comp = Compare());

template ‹class InputIterator›

multimap(InputIterator first, InputIterator last, const Compare& comp = Compare());

multimap(const multimap‹Key, T, Compare, Allocator›& x);

~multimap();

multimap‹Key, T, Compare, Allocator›& operator=(const multimap‹Key, T, Compare, Allocator›& x);

void swap(multimap‹Key, T, Compare, Allocator›& x);

// accessors:

key_compare key_comp() const;

value_compare value_comp() const;

iterator begin();

const_iterator begin() const;

iterator end();

const_iterator end() const;

reverse_iterator rbegin();

const_reverse_iterator rbegin();

reverse_iterator rend()

const_reverse_iterator rend();

bool empty() const;

size_type size() const;

size_type max_size() const;

// insert/erase:

iterator insert(const value_type& x);

iterator insert(iterator position, const value_type& x);

template ‹class InputIterator›

void insert(InputIterator first, InputIterator last);

void erase(iterator position);

size_type erase(const key_type& x);

void erase(iterator first, iterator last);

// multimap operations:

iterator find(const key_type& x);

const_iterator find(const key_type& x) const;

size_type count(const key_type& x) const;

iterator lower_bound(const key_type& x);

const_iterator lower_bound(const key_type& x) const;

iterator upper_bound(const key_type& x);

const_iterator upper_bound(const key_type& x) const;

pair‹iterator, iterator› equal_range(const key_type& x);

pair‹const_iterator, const_iterator› equal_range(const key_type& x) const;

};

template ‹class Key, class T, class Compare, class Allocator›

bool operator==(const multimap‹Key, T, Compare, Allocator›& x, const multimap‹Key, T, Compare, Allocator›& y);

template ‹class Key, class T, class Compare, class Allocator›

bool operator‹(const multimap‹Key, T, Compare, Allocator›& x, const multimap‹Key, T, Compare, Allocator›& y);

const_iterator - постоянный двунаправленный итератор, указывающий на value_type. Точный тип зависит от реализации и определяется в Allocator. Гарантируется, что имеется конструктор для const_iterator из iterator.

size_type - целочисленный тип без знака. Точный тип зависит от реализации и определяется в Allocator.

difference_type - целочисленный тип со знаком. Точный тип зависит от реализации и определяется в Allocator.

ИТЕРАТОРЫ ПОТОКОВ

Чтобы шаблоны алгоритмов могли работать непосредственно с потоками ввода-вывода, предусмотрены соответствующие шаблонные классы, подобные итераторам. Например,

partial_sum_copy(istream_iterator‹double›(cin), istream_iterator‹double›(), ostream_iterator‹double›(cout, "\n"));

читает файл, содержащий числа с плавающей запятой, из cin и печатает частичные суммы в cout.

Итератор входного потока (Istream Iterator)

istream_iterator‹T› читает (используя operator››) последовательные элементы из входного потока, для которого он был создан. После своего создания итератор каждый раз при использовании ++ читает и сохраняет значение T. Если достигнут конец потока (operator void* () в потоке возвращает false), итератор становится равным значению end-of-stream (конец-потока). Конструктор без параметров istream_iterator() всегда создаёт итераторный объект конца потокового ввода, являющийся единственым законным итератором, который следует использовать для конечного условия. Результат operator* для конца потока не определён, а для любого другого значения итератора возвращается const T&.

Невозможно записывать что-либо с использованием входных итераторов. Основная особенность входных итераторов - тот факт, что операторы ++ не сохраняют равенства, то есть i==j не гарантирует вообще, что ++i==++j. Каждый раз, когда ++ используется, читается новое значение. Практическое следствие этого факта - то, что входные итераторы могут использоваться только для однопроходных алгоритмов, что действительно имеет здравый смысл, так как многопроходным алгоритмам всегда более соответствует использование структур данных в оперативной памяти.

Два итератора конец-потока всегда равны. Итератор конец-потока не равен не-конец-потока итератору. Два не-конец-потока итератора равны, когда они созданы из того же самого потока.

template ‹class T, class Distance = ptrdiff_t›

class istream_iterator: public input_iterator‹T, Distance› {

friend bool operator==(const istream_iterator‹T, Distance›& x, const istream_iterator‹T, Distance›& y);

public:

istream_iterator();

istream_iterator(istream& s);

istream_iterator(const istream_iterator‹T, Distance›& x);

~istream_iterator();

const T& operator*() const;

istream_iterator‹T, Distance›& operator++();

istream_iterator‹T, Distance› operator++(int);

};

template ‹class T, class Distance›

bool operator==(const istream_iterator‹T, Distance›& x, const istream_iterator‹T, Distance›& y);

Итератор выходного потока (Ostream Iterator)

istream_iterator‹T› записывает (используя operator‹‹) последовательные элементы в выходной поток, из которого он был создан. Если он был создан с параметром конструктора char*, эта строка, называемая строкой разделителя (delimiter string), записывается в поток после того, как записывается каждое T. Невозможно с помощью выходного итератора получить значение. Его единственное использование - выходной итератор в ситуациях, подобных нижеследующему:

while (first != last) *result++ = *first++;

ostream_iterator определён как:

template ‹class T›

class ostream_iterator: public output_iterator {

public:

ostream_iterator(ostream& s);

ostream_iterator(ostream& s, const char* delimiter);

ostream_iterator(const ostream_iterator‹T›& x);

~ostream_iterator();

ostream_iterator‹T›& operator=(const T& value);

ostream_iterator‹T›& operator*();

ostream_iterator‹T›& operator++();

ostream_iterator‹T›& operator++(int);

};

АЛГОРИТМЫ

Все алгоритмы отделены от деталей реализации структур данных и используют в качестве параметров типы итераторов. Поэтому они могут работать с определяемыми пользователем структурами данных, когда эти структуры данных имеют типы итераторов, удовлетворяющие предположениям в алгоритмах.

Для некоторых алгоритмов предусмотрены и оперативные и копирующие версии. Решение, включать ли копирующую версию, было обычно основано на рассмотрении сложности. Когда стоимость выполнения операции доминирует над стоимостью копии, копирующая версия не включена. Например, sort_copy не включена, так как стоимость сортировки намного значительнее, и пользователи могли бы также делать copy перед sort. Когда такая версия предусмотрена для какого-то алгоритма algorithm, он называется algorithm _copy . Алгоритмы, которые берут предикаты, оканчиваются суффиксом _if (который следует за суффиксом _copy).

Класс Predicate используется всякий раз, когда алгоритм ожидает функциональный объект, при применении которого к результату разыменования соответствующего итератора возвращается значение, обратимое в bool. Другими словами, если алгоритм берёт Predicate pred как свой параметр и first как свой параметр итератора, он должен работать правильно в конструкции if (pred(*first)) {…}. Предполагается, что функциональный объект pred не применяет какую-либо непостоянную функцию для разыменованного итератора.

Класс BinaryPredicate используется всякий раз, когда алгоритм ожидает функциональный объект, который при его применении к результату разыменования двух соответствующих итераторов или к разыменованию итератора и типа T, когда T - часть сигнатуры, возвращает значение, обратимое в bool. Другими словами, если алгоритм берёт BinaryPredicate binary_pred как свой параметр и first1 и first2 как свои параметры итераторов, он должен работать правильно в конструкции if (binary_pred(*first, *first2)) {…}. BinaryPredicate всегда берёт тип первого итератора как свой первый параметр, то есть в тех случаях, когда T value - часть сигнатуры, он должен работать правильно в контексте if (binary_pred (*first, value)) {…}. Ожидается, что binary_pred не будет применять какую-либо непостоянную функцию для разыменованных итераторов.

В описании алгоритмов операторы + и - используются для некоторых категорий итераторов, для которых они не должны быть определены. В этих случаях семантика a+n такая же, как семантика {X tmp = a; advance(tmp, n); return tmp;}, а семантика a-b такая же, как семантика {Distance n; distance(a, b, n); return n;}.

Не меняющие последовательность операции (Non-mutating sequence operations)

Операции с каждым элементом (For each)

template <class InputIterator, class Function>

Function for_each(InputIterator first, InputIterator last, Function f);

for_each применяет f к результату разыменования каждого итератора в диапазоне [first, last) и возвращает f. Принято, что f не применяет какую-то непостоянную функцию к разыменованному итератору. f применяется точно last-first раз. Если f возвращает результат, результат игнорируется.

Найти (Find)

template ‹class InputIterator, class T›

InputIterator find(InputIterator first, InputIterator last, const T& value);

template ‹class InputIterator, class Predicate›

InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);

find возвращает первый итератор i в диапазоне [first, last), для которого соблюдаются следующие соответствующие условия: *i==value, pred(*i)==true. Если такой итератор не найден, возвращается last. Соответствующий предикат применяется точно find(first, last, value) - first раз.

Найти рядом (Аdjacent find)

template ‹class ForwardIterator›

ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last);

template ‹class ForwardIterator, class BinaryPredicate›

ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred);

adjacent_find возвращает первый итератор i такой, что i и i+1 находятся в диапазоне [first, last) и для которого соблюдаются следующие соответствующие условия: *i==*(i+1), binary_pred(*i, *(i+1))==true. Если такой итератор i не найден, возвращается last. Соответствующий предикат применяется, самое большее, max((last - first) - 1, 0) раз.

Подсчет (Count)

template ‹class InputIterator, class T, class Size›

void count(InputIterator first, InputIterator last, const T& value, Size& n);

template ‹class InputIterator, class Predicate, class Size›

void count_if(InputIterator first, InputIterator last, Predicate pred, Size& n);

count добавляет к n число итераторов i в диапазоне [first, last), для которых соблюдаются следующие соответствующие условия: *i==value, pred(*i)==true. Соответствующий предикат применяется точно last-first раз.

count должен сохранять результат в параметре ссылки вместо того, чтобы возвращать его, потому что тип размера не может быть выведен из встроенных типов итераторов, как, например, int*.

Отличие (Mismatch)

template ‹class InputIterator1, class InputIterator2›

pair‹InputIterator1, InputIterator2› mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);

template ‹class InputIterator1, class InputIterator2, class BinaryPredicate›

pair‹InputIterator1, InputIterator2› mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate binary_pred);

mismatch возвращает пару итераторов i и j таких, что j==first2 + (i - first1) и i является первым итератором в диапазоне [first1, last1), для которого следующие соответствующие условия выполнены: !(*i==*(first2 + (i - first1))), binary_pred (*i, *(first2 + (i - first1)))==false. Если такой итератор i не найден, пара last1 и first2 + (last1 - first1) возвращается. Соответствующий предикат применяется, самое большее, last1 - first1 раз.

Сравнение на равенство (Equal)

template ‹class InputIterator1, class InputIterator2›

bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);

template ‹class InputIterator1, class InputIterator2, class BinaryPredicate›

bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate binary_pred);

equal возвращает true, если для каждого итератора i в диапазоне [first1, last1) выполнены следующие соответствующие условия: *i==*(first2 + (i-first1)), binary_pred(*i, *(first2 + (i - first1)))==true. Иначе equal возвращает false. Соответствующий предикат применяется, самое большее, last1 - first1 раз.

Поиск подпоследовательности (Search)

template ‹class ForwardIterator1, class ForwardIterator2›

ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);

template ‹class ForwardIterator1, class ForwardIterator2, class BinaryPredicate›

ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate binary_pred);

search находит подпоследовательность равных значений в последовательности. search возвращает первый итератор i в диапазоне [first1, last1 - (last2 - first2)) такой, что для любого неотрицательного целого числа n, меньшего чем last2 - first2, выполнены следующие соответствующие условия: *(i+n)==*(first2+n), binary_pred(*(i+n), *(first2+n))==true. Если такой итератор не найден, возвращается last1. Соответствующий предикат применяется, самое большее, (last1 - first1) * (last2 - first2) раз. Квадратичное поведение, однако, является крайне маловероятным.

Меняющие последовательность операции (Mutating sequence operations)

Копировать (Copy)

template ‹class InputIterator, class OutputIterator›

OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result);

copy копирует элементы. Для каждого неотрицательного целого числа n ‹ (last - first) выполняется присваивание *(result + n) = *(first + n). Точно делается last - first присваиваний. Результат copy не определён, если result находится в диапазоне [first, last).

template ‹class BidirectionalIterator1, class BidirectionalIterator2›

BidirectionalIterator2 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 result);

copy_backward копирует элементы в диапазоне [first, last) в диапазон [result - (last - first), result), начиная от last-1 и продолжая до first. Его нужно использовать вместо copy, когда last находится в диапазоне [result - (last-first), result). Для каждого положительного целого числа n ‹= (last - first) выполняется присваивание *(result-n) = *(last-n). copy_backward возвращает result - (last-first). Точно делается last - first присваиваний. Результат copy_backward не определён, если result находится в диапазоне [first, last).

Обменять (Swap)

template ‹class T›

void swap(T& a, T& b);

swap обменивает значения, хранимые в двух местах.

template ‹class ForwardIterator1, class ForwardIterator2›

void iter_swap(ForwardIterator1 a, ForwardIterator2 b);

iter_swap обменивает значения, указанные двумя итераторами a и b.

tempate ‹class ForwardIterator1, class ForwardIterator2›

ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);

Для каждого неотрицательного целого числа n ‹ (last1 - first1) выполняется перестановка: swap(*(first1 + n), *(first2 + n)). swap_ranges возвращает first2 + (last1 - first1). Выполняется точно last1 - first1 перестановок. Результат swap_ranges не определён, если два диапазона [first1, last1) и [first2, first2 + (last1 - first1)) перекрываются.

Преобразовать (Transform)

template ‹class InputIterator, class OutputIterator, class UnaryOperation›

OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op);

template ‹class InputIterator1, class InputIterator2, class OutputIterator, class Binary0peration›

OutputIterator transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryOperation binary_op);

transform присваивает посредством каждого итератора i в диапазоне [result, result+(last1-first1)) новое соответствующее значение, равное op(*(first1+(i-result)) или binary_op(*(first1+(i-result), *(first2+(i-result))). transform возвращает result+(last1-first1). Применяются op или binary_op точно last1 - first1 раз. Ожидается, что op и binary_op не имеют каких-либо побочных эффектов. result может быть равен first в случае унарного преобразования или first1 либо first2 в случае бинарного.

Заменить (Replace)

template ‹class ForwardIterator, class T›

void replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);

template ‹class ForwardIterator, class Predicate, class T›

void replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value);

replace заменяет элементы, указанные итератором i в диапазоне [first, last), значением new_value, когда выполняются следующие соответствующие условия: *i==old_value, pred(*i)==true. Соответствующий предикат применяется точно last - first раз.

template ‹class InputIterator, class OutputIterator, class T›

OutputIterator replace_copy(InputIterator first, InputIterator last, OutputIterator result, const T& old_value, const T& new_value);

template ‹class Iterator, class OutputIterator, class Predicate, class T›

OutputIterator replace_copy_if(Iterator first, Iterator last, OutputIterator result, Predicate pred, const T& new_value);

replace_copy присваивает каждому итератору i в диапазоне [result, result+(last-first)) значение new_value или *(first+(i-result)) в зависимости от выполнения следующих соответствующих условий: *(first+(i-result))==old_value, pred(*(first+(i-result)))==true. replace_copy возвращает result+(last-first). Соответствующий предикат применяется точно last - first раз.

Заполнить (Fill)

template ‹class ForwardIterator, class T›

void fill(ForwardIterator first, ForwardIterator last, const T& value);

template ‹class OutputIterator, class Size, class T›

OutputIterator fill_n(Output Iterator first, Size n, const T& value);

fill присваивает значения через все итераторы в диапазоне [first, last) или [first, first+n). fill_n возвращает first+n. Точно делается last - first (или n) присваиваний.

Породить (Generate)

template ‹class ForwardIterator, class Generator›

void generate(ForwardIterator first, ForwardIterator last, Generator gen);

template ‹class OutputIterator, class Size, class Generator›

OutputIterator generate_n(OutputIterator first, Size n, Generator gen);

generate вызывает функциональный объект gen и присваивает возвращаемое gen значение через все итераторы в диапазоне [first, last) или [first, first + n). gen не берёт никакие параметры. generate_n возвращает first + n. Точно выполняется last - first (или n) вызовов gen и присваиваний.

Удалить (Remove)

template ‹class ForwardIterator, class T›

ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T& value);

template ‹class ForwardIterator, class Predicate›

ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);

remove устраняет все элементы, указываемые итератором i в диапазоне [first, last), для которых выполнены следующие соответствующие условия: *i==value, pred(*i)==true. remove возвращает конец возникающего в результате своей работы диапазона. remove устойчив, то есть относительный порядок элементов, которые не удалены, такой же, как их относительный порядок в первоначальном диапазоне. Соответствующий предикат применяется точно last -first раз.

template ‹class InputIterator, class OutputIterator, class T›

OutputIterator remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value);

template ‹class InputIterator, class OutputIterator, class Predicate›

OutputIterator remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);

remove_copy копирует все элементы, указываемые итератором i в диапазоне [first, last), для которых не выполнены следующие соответствующие условия: *i==value, pred(*i)==true. remove_copy возвращает конец возникающего в результате своей работы диапазона. remove_copy устойчив, то есть относительный порядок элементов в результирующем диапазоне такой же, как их относительный порядок в первоначальном диапазоне. Соответствующий предикат применяется точно last-first раз.

Убрать повторы (Unique)

template ‹class ForwardIterator›

ForwardIterator unique(ForwardIterator first, ForwardIterator last);

template ‹class ForwardIterator, class BinaryPredicate›

ForwardIterator unique(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred);

unique устраняет все, кроме первого, элементы из каждой последовательной группы равных элементов, указываемые итератором i в диапазоне [first, last), для которых выполнены следующие соответствующие условия: *i==*(i-1) или binary_pred(*i, *(i-1))==true. unique возвращает конец возникающего в результате диапазона. Соответствующий предикат применяется точно (last-first)-1 раз.

template ‹class InputIterator, class OutputIterator›

OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result);

template ‹class InputIterator, class OutputIterator, class BinaryPredicate›

OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate binary_pred);

unique_copy копирует только первый элемент из каждой последовательной группы равных элементов, указываемых итератором i в диапазоне [first, last), для которых выполнены следующие соответствующие условия: *i==*(i-1) или binary_pied(*i, *(i-1))==true. unique_copy возвращает конец возникающего в результате диапазона. Соответствующий предикат применяется точно (last-first)-1 раз.

Расположить в обратном порядке (Reverse)

template ‹class BidirectionalIterator›

void reverse(BidirectionalIterator first, BidirectionalIterator last);

Для каждого неотрицательного целого числа i‹=(last-first)/2 функция reverse применяет перестановку ко всем парам итераторов first+i, (last-i)-1. Выполняется точно (last-first)/2 перестановок.

template ‹class BidirectionalIterator, class OutputIterator›

OutputIterator reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);

reverse_copy копирует диапазон [first, last) в диапазон [result, result+(last-first)) такой, что для любого неотрицательного целого числа i ‹ (last-first) происходит следующее присваивание: *(result+(last-first)-i) = *(first+i). reverse_copy возвращает result+(last-first). Делается точно last-first присваиваний. Результат reverse_copy не определён, если [first, last) и [result, result +(last-first)) перекрываются.

Переместить по кругу (Rotate)

template ‹class ForwardIterator›

void rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);

Для каждого неотрицательного целого числа i ‹ (last-first) функция rotate помещает элемент из позиции first+i в позицию first+(i+(last-middle))%(last-first). [first, middle) и [middle, last) - допустимые диапазоны. Максимально выполняется last-first перестановок.

template ‹class ForwardIterator, class OutputIterator›

OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);

rotate_copy копирует диапазон [first, last) в диапазон [result, result+(last-first)) такой, что для каждого неотрицательного целого числа i ‹ (last-first) происходит следующее присваивание: *(result+(i+(last-middle))%(last-first)) = *(first+i). rotate_copy возвращает result+(last-first). Делается точно last-first присваиваний. Результат rotate_copy не определён, если [first, last) и [result, result+(last-first)) перекрываются.

Перетасовать (Random shuffle)

template ‹class RandomAccessIterator›

void random_shuffle(RandomAccessIterator first, RandomAccessIterator last);

template ‹class RandomAccessIterator, class RandomNumberGenerator›

void random_shuffie(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& rand);

random_shuffle переставляет элементы в диапазоне [first, last) с равномерным распределением. Выполняется точно last-first перестановок. random_shuffle может брать в качестве параметра особый генерирующий случайное число функциональный объект rand такой, что rand берёт положительный параметр n типа расстояния RandomAccessIterator и возвращает случайно выбранное значение между 0 и n-1.

Разделить (Partitions)

template ‹class BidirectionalIterator, class Predicate›

BidirectionalIterator partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred);

partition помещает все элементы в диапазоне [first, last), которые удовлетворяют pred, перед всеми элементами, которые не удовлетворяют. Возвращается итератор i такой, что для любого итератора j в диапазоне [first, i) будет pred(*j)==true, а для любого итератора k в диапазоне [i, last) будет pred(*k)==false. Делается максимально (last-first)/2 перестановок. Предикат применяется точно last-first раз.

template ‹class BidirectionalIterator, class Predicate›

BidirectionalIterator stable_partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred);

stable_partition помещает все элементы в диапазоне [first, last), которые удовлетворяют pred, перед всеми элементами, которые не удовлетворяют. Возвращается итератор i такой, что для любого итератора j в диапазоне [first, i) будет pred(*j)==true, а для любого итератора k в диапазоне [i, last) будет pred(*k)==false. Относительный порядок элементов в обеих группах сохраняется. Делается максимально (last-first)*log(last-first) перестановок, но только линейное число перестановок, если имеется достаточная дополнительная память. Предикат применяется точно last-first раз.

Операции сортировки и отношения (Sorting and related operations)

Все операции в этом разделе имеют две версии: одна берёт в качестве параметра функциональный объект типа Compare, а другая использует operator‹.

Compare - функциональный объект, который возвращает значение, обратимое в bool. Compare comp используется полностью для алгоритмов, принимающих отношение упорядочения. comp удовлетворяет стандартным аксиомам для полного упорядочения и не применяет никакую непостоянную функцию к разыменованному итератору. Для всех алгоритмов, которые берут Compare, имеется версия, которая использует operator‹ взамен. То есть comp(*i, *j)==true по умолчанию для *i‹*j==true.

Последовательность сортируется относительно компаратора comp, если для любого итератора i, указывающего на элемент в последовательности, и любого неотрицательного целого числе n такого, что i + n является допустимым итератором, указывающим на элемент той же самой последовательности, comp(*(i+n), *i)==false.

В описаниях функций, которые имеют дело с упорядочивающими отношениями, мы часто используем представление равенства, чтобы описать такие понятия, как устойчивость. Равенство, к которому мы обращаемся, не обязательно operator==, а отношение равенства стимулируется полным упорядочением. То есть два элементa a и b считаются равными, если и только если !(a ‹ b)&&!(b ‹ a).

Сортировка (Sort)

template ‹class RandomAccessIterator›

void sort(RandomAccessIterator first, RandomAccessIterator last);

template ‹class RandomAccessIterator, class Compare›

void sort(RandomAccessIterator first, RandomAccessIterator last, Compare соmр);

sort сортирует элементы в диапазоне [first, last). Делается приблизительно NIogN (где N равняется last-first) сравнений в среднем. Если режим наихудшего случая важен, должны использоваться stable_sort или partial_sort.

template ‹class RandomAccessIterator›

void stable_sort(RandomAccessIterator first, RandomAccessIterator last);

template ‹class RandomAccessIterator, class Compare›

void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

stable_sort сортирует элементы в диапазоне [first, last). Он устойчив, то есть относительный порядок равных элементов сохраняется. Делается максимум N(logN)² (где N равняется last-first) сравнений; если доступна достаточная дополнительная память, тогда это - NlogN.

template ‹class RandomAccessIterator›

void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);

template ‹class RandomAccessIterator, class Compare›

void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);

partial_sort помещает первые middle - first сортированных элементов из диапазона [first, last) в диапазон [first, middle). Остальная часть элементов в диапазоне [middle, last) помещена в неопределённом порядке. Берётся приблизительно (last-first)*log(middle-first) сравнений.

template ‹class InputIterator, class RandomAccessIterator›

RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last);

template ‹class InputIterator, class RandomAccessIterator, class Compare›

RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);

partial_sort_copy помещает первые min(last-first, result_last-result_first) сортированных элементов в диапазон [result_first, result_first+min(last-first, result_last-result_first)). Возвращается или result_last, или result_first+(last-first), какой меньше. Берётся приблизительно (last-first)*log(min(last-first, result_last-result_first)) сравнений.

N-й элемент (Nth element)

template ‹class RandomAccessIterator›

void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);

template ‹class RandomAccessIterator, class Compare›

void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);

После операции nth_element элемент в позиции, указанной nth, является элементом, который был бы в той позиции, если бы сортировался целый диапазон. Также для любого итератора i в диапазоне [first, nth) и любого итератора j в диапазоне [nth, last) считается, что !(*i › *j) или comp(*i, *j)==false. Операция линейна в среднем.

Двоичный поиск (Binary search)

Все алгоритмы в этом разделе - версии двоичного поиска. Они работают с итераторами не произвольного доступа, уменьшая число сравнений, которое будет логарифмическим для всех типов итераторов. Они особенно подходят для итераторов произвольного доступа, так как эти алгоритмы делают логарифмическое число шагов в структуре данных. Для итераторов не произвольного доступа они выполняют линейное число шагов.

template ‹class ForwardIterator, class T›

ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value);

template ‹class ForwardIterator, class T, class Compare›

ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

lower_bound находит первую позицию, в которую value может быть вставлено без нарушения упорядочения. lower_bound возвращает самый дальний итератор i в диапазоне [first, last) такой, что для любого итератора j в диапазоне [first, i) выполняются следующие соответствующие условия: *j‹value или comp(*j, value)==true. Делается максимум log(last-first)+1 сравнений.

template ‹class ForwardIterator, class T›

ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value);

template ‹class ForwardIterator, class T, class Compare›

ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

upper_bound находит самую дальнюю позицию, в которую value может быть вставлено без нарушения упорядочения. upper_bound возвращает самый дальний итератор i в диапазоне [first, last) такой, что для любого итератора j в диапазоне [first, i) выполняются следующие соответствующие условия: !(value‹*j) или comp(value, *j)==false. Делается максимум log(last-first)+1 сравнений.

template ‹class ForwardIterator, class T›

ForwardIterator equal_range(ForwardIterator first, ForwardIterator last, const T& value);

template ‹class ForwardIterator, class T, class Compare›

ForwardIterator equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

equal_range находит самый большой поддиапазон [i, j) такой, что значение может быть вставлено по любому итератору k в нём. k удовлетворяет соответствующим условиям: !(*k ‹ value)&&!(value ‹ *k) или comp(*k, value)==false&& comp(value, *k)==false. Делается максимум 2*log(last-first)+1 сравнений.

template ‹class ForwardIterator, class T›

ForwardIterator binary_search(ForwardIterator first, ForwardIterator last, const T& value);

template ‹class ForwardIterator, class T, class Compare›

ForwardIterator binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

binary_search возвращает истину, если в диапазоне [first, last) имеется итератор i, который удовлетворяет соответствующим условиям: !(*i ‹ value)&&!(value ‹ *i) или comp(*i, value)==false&&comp(value, *i)==false. Делается максимум log(last-first)+2 сравнений.

Объединение (Merge)

template ‹class InputIterator1, class Input Iterator2, class OutputIterator›

OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

template ‹class InputIterator1, class InputIterator2, class OutputIterator, class Compare›

OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

merge объединяет два сортированных диапазона [first1, last1) и [first2, last2) в диапазон [result, result+(last1-first1)+(last2-first2)). Объединение устойчиво, то есть для равных элементов в двух диапазонах элементы из первого диапазона всегда предшествуют элементам из второго. merge возвращает result+(last1-first1)+(last2-first2). Выполняется максимально (last1-first1)+(last2-first2)-1 сравнений. Результат merge не определён, если возникающий в результате диапазон перекрывается с любым из первоначальных диапазонов.

template ‹class BidirectionalIterator›

void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);

template ‹class BidirectionalIterator, class Compare›

void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);

inplace_merge объединяет два сортированных последовательных диапазона [first, middle) и [middle, last), помещая результат объединения в диапазон [first, last). Объединение устойчиво, то есть для равных элементов в двух диапазонах элементы из первого диапазона всегда предшествуют элементам из второго. Когда доступно достаточно дополнительной памяти, выполняется максимально (last-first)-1 сравнений. Если никакая дополнительная память не доступна, может использоваться алгоритм со сложностью O(NlogN).

Операции над множеством для сортированных структур (Set operations on sorted structures)

Этот раздел определяет все основные операции над множеством для сортированных структур. Они даже работают с множествами с дубликатами, содержащими множественные копии равных элементов. Семантика операций над множеством обобщена на множества с дубликатами стандартным способом, определяя объединение, содержащее максимальное число местонахождений каждого элемента, пересечение, содержащее минимум, и так далее.

template ‹class InputIterator1, class InputIterator2›

bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);

template ‹class InputIterator1, class InputIterator2, class Compare›

bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);

includes возвращает true, если каждый элемент в диапазоне [first2, last2) содержится в диапазоне [first1, last1). Иначе возвращается false. Выполняется максимально ((last1-first1)+(last2-first2))*2-1 сравнений.

template ‹class InputIterator1, class InputIterator2, class OutputIterator›

OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

template ‹class InputIterator1, class InputIterator2, class OutputIterator, class Compare›

OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

set_union создаёт сортированное объединение элементов из двух диапазонов. Он возвращает конец созданного диапазона. set_union устойчив, то есть, если элемент присутствует в обоих диапазонах, он копируется из первого диапазона. Выполняется максимально ((last1-first1)+(last2-first2))*2-1 сравнений. Результат set_union не определён, если возникающий в результате диапазон перекрывается с любым из первоначальных диапазонов.

template ‹class InputIterator1, class InputIterator2, class OutputIterator›

OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

template ‹class InputIterator1, class InputIterator2, class OutputIterator, class Compare›

OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

set_intersection создаёт сортированное пересечение элементов из двух диапазонов. Он возвращает конец созданного диапазона. Гарантируется, что set_intersection устойчив, то есть, если элемент присутствует в обоих диапазонах, он копируется из первого диапазона. Выполняется максимально ((last1-first1)+(last2-first2))*2-1 сравнений. Результат set_union не определён, если возникающий в результате диапазон перекрывается с любым из первоначальных диапазонов.

template ‹class InputIterator1, class InputIterator2, class OutputIterator›

OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

template ‹class InputIterator1, class InputIterator2, class OutputIterator, class Compare›

OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

set_difference создаёт сортированную разность элементов из двух диапазонов. Он возвращает конец созданного диапазона. Выполняется максимально ((last1-first1)+(last2-first2))*2- сравнений. Результат set_difference не определён, если возникающий в результате диапазон перекрывается с любым из первоначальных диапазонов.

template ‹class InputIterator1, class InputIterator2, class OutputIterator›

OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);

template ‹class InputIterator1, class InputIterator2, class OutputIterator, class Compare›

OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);

set_symmetric_difference создаёт сортированную симметричную разность элементов из двух диапазонов. Он возвращает конец созданного диапазона. Выполняется максимально ((last1-first1)+(last2-first2))*2-1 сравнений. Результат set_symmetric_difference не определён, если возникающий в результате диапазон перекрывается с любым из первоначальных диапазонов.

Операции над пирамидами (Heap operations)

Пирамида - специфическая организация элементов в диапазоне между двумя итераторами произвольного доступа [a, b). Два её ключевые свойства: (1) *a - самый большой элемент в диапазоне, (2) *a может быть удалён с помощью pop_heap или новый элемент добавлен с помощью push_heap за O(logN) время. Эти свойства делают пирамиды полезными для приоритетных очередей. make_heap преобразовывает диапазон в пирамиду, a sort_heap превращает пирамиду в сортированную последовательность.

template ‹class RandomAccessIterator›

void push_heap(RandomAccessIterator first, RandomAccessIterator last);

template ‹class RandomAccessIterator, class Compare›

void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

push_heap полагает, что диапазон [first, last-1) является соответствующей пирамидой, и надлежащим образом помещает значение с позиции last-1 в результирующую пирамиду [first, last). Выполняется максимально log(last-first) сравнений.

template ‹class RandomAccessIterator›

void pop_heap(RandomAccessIterator first, RandomAccessIterator last);

template ‹class RandomAccessIterator, class Compare›

void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

pop_heap полагает, что диапазон [first, last) является соответствующей пирамидой, затем обменивает значения в позициях first и last-1 и превращает [first, last-1) в пирамиду. Выполняется максимально 2*log(last-first) сравнений.

template ‹class RandomAccessIterator›

void make_heap(RandomAccessIterator first, RandomAccessIterator last);

template ‹class RandomAccessIterator, class Compare›

void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

make_heap создает пирамиду из диапазона [first, last). Выполняется максимально 3*(last-first) сравнений.

template ‹class RandomAccessIterator›

void sort_heap(RandomAccessIterator first, RandomAccessIterator last);

template ‹class RandomAccessIterator, class Compare›

void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

sort_heap сортирует элементы в пирамиде [first, last). Выполняется максимально NlogN сравнений, где N равно last-first. sort_heap не устойчив.

Минимум и максимум (Minimum and maximum)

template ‹class T›

const T& min(const T& a, const T& b);

template ‹class T, class Compare›

const T& min(const T& a, const T& b, Compare comp);

template ‹class T›

const T& max(const T& a, const T& b);

template ‹class T, class Compare›

const T& max(const T& a, const T& b, Compare comp);

min возвращает меньшее, а max большее. min и max возвращают первый параметр, когда их параметры равны.

template ‹class ForwardIterator›

ForwardIterator max_element(ForwardIterator first, ForwardIterator last);

template ‹class ForwardIterator, class Compare›

ForwardIterator max_element(ForwardIterator first, ForwardIterator last, Compare comp);

max_element возвращает первый такой итератор i в диапазоне [first, last), что для любого итератора j в диапазоне [first, last) выполняются следующие соответствующие условия: !(*i‹*j) или comp(*i, *j)==false. Выполняется точно max((last-first)-1, 0) соответствующих сравнений.

template ‹class ForwardIterator›

ForwardIterator min_element(ForwardIterator first, ForwardIterator last);

template ‹class ForwardIterator, class Compare›

ForwardIterator min_element(ForwardIterator first, ForwardIterator last, Compare comp);

min_element возвращает первый такой итератор i в диапазоне [first, last), что для любого итератора j в диапазоне [first, last) выполняются следующие соответствующие условия: !(*j‹*i) или comp(*j, *i)==false. Выполняется точно max((last-first)-1, 0) соответствующих сравнений.

Лексикографическое сравнение (Lexicographical comparison)

template ‹class InputIterator1, class InputIterator2›

bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);

template ‹class InputIterator1, class InputIterator2, class Compare›

bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);

lexicographical_compare возвращает true, если последовательность элементов, определённых диапазоном [first1, last1), лексикографически меньше, чем последовательность элементов, определённых диапазоном [first2, last2). Иначе он возвращает ложь. Выполняется максимально 2*min((last1-first1), (last2-first2)) сравнений.

Генераторы перестановок (Permutation generators)

template ‹class BidirectionalIterator›

bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);

template ‹class BidirectionalIterator, class Compare›

bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);

next_permutation берёт последовательность, определённую диапазоном [first, last), и трансформирует её в следующую перестановку. Следующая перестановка находится, полагая, что множество всех перестановок лексикографически сортировано относительно operator‹ или comp. Если такая перестановка существует, возвращается true. Иначе он трансформирует последовательность в самую маленькую перестановку, то есть сортированную по возрастанию, и возвращает false. Максимально выполняется (last-first)/2 перестановок.

template ‹class BidirectionalIterator›

bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last);

template ‹class BidirectionalIterator, class Compare›

bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);

prev_permutation берёт последовательность, определённую диапазоном [first, last), и трансформирует её в предыдущую перестановку. Предыдущая перестановка находится, полагая, что множество всех перестановок лексикографически сортировано относительно operator‹ или comp. Если такая перестановка существует, возвращается true. Иначе он трансформирует последовательность в самую большую перестановку, то есть сортированную по убыванию, и возвращает false. Максимально выполняется (last - first)/2 перестановок.

Обобщённые численные операции (Generalized numeric operations)

Накопление (Accumulate)

template ‹class InputIterator, class T›

T accumulate(InputIterator first, InputIterator last, T init);

template ‹class InputIterator, class T, class BinaryOperation›

T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation binary_op);

accumulate подобен оператору APL reduction и функции Common Lisp reduce, но он избегает трудности определения результата уменьшения для пустой последовательности, всегда требуя начальное значение. Накопление выполняется инициализацией сумматора acc начальным значением init и последующим изменением его acc = acc+*i или acc = binary_op(acc, *i) для каждого итератора i в диапазоне [first, last) по порядку. Предполагается, что binary_op не вызывает побочных эффектов.

Скалярное произведение (Inner product)

template ‹class InputIterator1, class InputIterator2, class T›

T inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init);

template ‹class InputIterator1, class InputIterator2, class T, class BinaryOperation1, class BinaryOperation2›

T inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init, BinaryOperation1 binary_op1, BinaryOperation2 binary_op2);

inner_product вычисляет свой результат, инициализируя сумматор acc начальным значением init и затем изменяя его acc = acc+(*i1)*(*i2) или acc = binary_op1(acc, binary_op2(*i1, *i2)) для каждого итератора i1 в диапазоне [first, last) и итератора i2 в диапазоне [first2, first2+(last-first)) по порядку. Предполагается, что binary_op1 и binary_op2 не вызывают побочных эффектов.

Частичная сумма (Partial sum)

template ‹class InputIterator, class OutputIterator›

OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result);

template ‹class InputIterator, class OutputIterator, class BinaryOperation›

OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op);

partial_sum присваивает каждому итератору i в диапазоне [result, result+(last-first)) значение, соответственно равное ((…(*first+*(first+1))+…)+*(first+(i-result))) или binary_op(binary_op(…, binary_op(*first, *(first+1)),…), *(first+(i-result))). Функция partial_sum возвращает result+(last-first). Выполняется binary_op точно (last-first)-1 раз. Ожидается, что binary_op не имеет каких-либо побочных эффектов. result может быть равен first.

Смежная разность (Adjacent difference)

template ‹class InputIterator, class OutputIterator›

OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result);

template ‹class InputIterator, class OutputIterator, class BinaryOperation›

OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result, BinaryOperation binary_op);

adjacent_difference присваивает каждому элементу, указываемому итератором i в диапазоне [result+1, result+(last-first)) значение, соответственно равное *(first+(i-result))-*(first+(i-result)-1) или binary_op(*(first+(i-result)), *(first+(i-result)-1)). Элемент, указываемый result, получает значение *first. Функция adjacent_difference возвращает result+(last-first). Применяется binary_op точно (last-first)-1 раз. Ожидается, что binary_op не имеет каких-либо побочных эффектов. result может быть равен first.

АДАПТЕРЫ

Адаптеры - шаблонные классы, которые обеспечивают отображения интерфейса. Например, insert_iterator обеспечивает контейнер интерфейсом итератора вывода.

Адаптеры контейнеров (Container adaptors)

Часто бывает полезно обеспечить ограниченные интерфейсы контейнеров. Библиотека предоставляет stack, queue и priority_queue через адаптеры, которые могут работать с различными типами последовательностей.

Стек (Stack)

Любая последовательность, поддерживающая операции back, push_back и pop_back, может использоваться для модификации stack. В частности, могут использоваться vector, list и deque.

template ‹class Container›

class stack {

friend bool operator==(const stack‹Container›& х, const stack‹Container›& y);

friend bool operator‹(const stack‹Container›& х, const stack‹Container›& y);

public:

typedef Container::value_type value_type;

typedef Container::size_type size_type;

protected:

Container c;

public:

bool empty() const {return c.empty();}

size_type size() const {return c.size();}

value_type& top() {return c.back();}

const value_type& top() const {return c.back();}

void push(const value_type& х) {с.push_back(х);}

void pop() {c.pop_back();}

};

template ‹class Container›

bool operator==(const stack ‹Container›& х, const stack‹Container›& y) {return х.с == у.с;}

template ‹class Container›

bool operator‹(const stack‹Container›& х, const stack‹Container›& y) {return х.с ‹ у.с;}

Например, stack‹vector‹int› › - целочисленный стек, сделанный из vector, а stack‹deque‹char› › - символьный стек, сделанный из deque.

Очередь (Queue)

Любая последовательность, поддерживающая операции front, push_back и pop_front, может использоваться для модификации queue. В частности, могут использоваться list и deque.

template ‹class Container›

class queue {

friend bool operator==(const queue‹Container›& х, const queue‹Container›& y);

friend bool operator‹(const queue‹Container›& х, const queue‹Container›& y);

public:

typedef Container::value_type value_type;

typedef Container::size_type size_type;

protected:

Container c;

public:

bool empty() const {return c.empty();}

size_type size() const {return c.size();}

value_type& front() {return c.front();}

const value_type& front() const {return c.front();}

value_type& back() {return c.back();}

const value_type& back() const {return c.back();}

void push(const value_type& х) {с.push_back(х);}

void pop() {с.pop_front();}

};

template ‹class Container›

bool operator==(const queue‹Container›& х, const queue‹Container›& y) {return х.с == у.с;}

template ‹class Container›

bool operator‹(const queue‹Container›& х, const queue‹Container›& y) {return х.с ‹ у.с;}

Очередь с приоритетами (Priority queue)

Любая последовательность, с итератором произвольного доступа и поддерживающая операции front, push_back и pop_front, может использоваться для модификации priority_queue. В частности, могут использоваться vector и deque.

template ‹class Container, class Compare = less‹Container::value_type› ›

class priority_queue {

public:

typedef Container::value_type value_type;

typedef Container::size_type size_type;

protected:

Container c;

Compare comp;

public:

priority_queue(const Compare& х = Compare()): c(), comp(х) {}

template ‹class InputIterator›

priority_queue(InputIterator first, InputIterator last,

const Compare& х = Compare()): c(first, last), comp(x) {make_heap(c.begin(), с.end(), comp);}

bool empty() const {return c.empty();}

size_type size() const {return c.size();}

const value_type& top() const {return c.front();}

void push(const value_type& х) {

c.push_back(х);

push_heap(c.begin(), c.end(), comp);

}

void pop() {

pop_heap(c.begin(), c.end(), comp);

с.рор_bасk();

}

}; // Никакое равенство не обеспечивается

Адаптеры итераторов (Iterator adaptors)

Обратные итераторы (Reverse iterators)

Двунаправленные итераторы и итераторы произвольного доступа имеют соответствующие адаптеры обратных итераторов, которые выполняют итерации через структуру данных в противоположном направлении.Они имеют те же самые сигнатуры, как и соответствующие итераторы. Фундаментальное соотношение между обратным итератором и его соответствующим итератором i установлено тождеством &*(reverse_iterator(i))==&*(i - 1). Это отображение продиктовано тем, что, в то время как после конца массива всегда есть указатель, может не быть допустимого указателя перед началом массива.

template ‹class BidirectionalIterator, class T, class Reference = T&, class Distance = ptrdiff_t›

class reverse_bidirectionaiIterator : public bidirectional_iterator‹T, Distance› {

typedef reverse_bidirectional_iterator‹BidirectionalIterator, T, Reference, Distance› self;

friend bool operator==(const self& х, const self& y);

protected:

BidirectionalIterator current;

public:

reverse_bidirectional_iterator() {}

reverse_bidirectional_iterator(BidirectionalIterator х) : current(х) {}

BidirectionalIterator base() {return current;}

Reference operator*() const {

BidirectionalIterator tmp = current;

return *--tmp;

}

self& operator++() {

--current;

return *this;

}

self operator++(int) {

self tmp = *this;

--current;

return tmp;

}

self& operator--() {

++current;

return *this;

}

self operator--(int) {

self tmp = *this;

++current;

return tmp;

}

};

template ‹class BidirectionalIterator, class T, class Reference, class Distance›

inline bool operator==(const reverse_bidirectional_iterator‹BidirectionalIterator, T, Reference, Distance›& x, const reverse_bidirectional_iterator‹BidirectionalIterator,

T, Reference, Distance›& y) {

return x.current==y.current;

}

template ‹class RandomAccessIterator, class T, class Reference = T&, class Distance = ptrdiff_t›

class reverse_iterator: public random_access_iterator‹T, Distance› {

typedef reverse_iterator‹RandomAccessIterator, T, Reference, Distance› self;

friend bool operator==(const self& x, const self& y);

friend bool operator‹(const self& x, const self& y);

friend Distance operator-(const self& x, const self& y);

friend self operator+(Distance n, const self& x);

protected:

RandomAccessIterator current;

public:

reverse_iterator() {}

reverse_iterator(RandomAccessIterator x): current (x) {}

RandomAccessIterator base() {return current;}

Reference operator*() const {

RandomAccessIterator tmp = current;

return *--tmp;

}

self& operator++() {

--current;

return *this;

}

self operator++(int) {

self tmp = *this;

--current;

return tmp;

}

self& operator--() {

++current;

return *this;

}

self operator--(int) {

self tmp = *this;

++current;

return tmp;

}

self operator+(Distance n) const {

return self(current - n);

}

self& operator+=(Distance n) {

current -= n;

return *this;

}

self operator-(Distance n) const {

return self(current + n);

}

self operator-=(Distance n) {

current += n;

return *this;

}

Reference operator[](Distance n) {return *(*this + n);}

};

template ‹class RandomAccessIterator, class T, class Reference, class Distance›

inline bool operator==(const reverse_iterator‹RandomAccessIterator, T, Reference, Distance›& x, const reverse_iterator‹RandomAccessIterator, T, Reference, Distance›& y) {

return x.current == y.current;

}

template ‹class RandomAccessIterator, class T, class Reference, class Distance›

inline bool operator‹(const reverse_iterator‹RandomAccessIterator, T, Reference, Distance›& x, const reverse_iterator‹RandomAccessIterator, T, Reference, Distance›& y) {

return y.current ‹ x.current;

}

template ‹class RandomAccessIterator, class T, class Reference, class Distance›

inline Distance operator-(const reverse_iterator‹RandomAccessIterator, T, Reference, Distance›& х, const reverse_iterator‹RandomAccessIterator, T, Reference, Distance›& y) {

return y.current - x.current;

}

template ‹class RandomAccessIterator, class T, class Reference, class Distance›

inline reverse_iterator‹RandomAccessIterator, T, Reference, Distance› operator+(Distance n, const reverse_iterator‹RandomAccessIterator, T, Reference, Distance›& x) {

return reverse_iterator‹RandomAccessIterator, T, Reference, Distance›(x.current - n);

}

Итераторы вставки (Insert iterators)

Чтобы было возможно иметь дело с вставкой таким же образом, как с записью в массив, в библиотеке обеспечивается специальный вид адаптеров итераторов, называемых итераторами вставки (insert iterators). С обычными классами итераторов

while (first!= last) *result++ = *first++;

вызывает копирование диапазона [first, last) в диапазон, начинающийся с result. Тот же самый код с result, являющимся итератором вставки, вставит соответствующие элементы в контейнер. Такой механизм позволяет всем алгоритмам копирования в библиотеке работать в режиме вставки (insert mode) вместо обычного режима наложения записей.

Итератор вставки создаётся из контейнера и, возможно, одного из его итераторов, указывающих, где вставка происходит, если это ни в начале, ни в конце контейнера. Итераторы вставки удовлетворяют требованиям итераторов вывода. operator* возвращает непосредственно сам итератор вставки. Присваивание operator=(const T& х) определено для итераторов вставки, чтобы разрешить запись в них, оно вставляет х прямо перед позицией, куда итератор вставки указывает. Другими словами, итератор вставки подобен курсору, указывающему в контейнер, где происходит вставка. back_insert_iterator вставляет элементы в конце контейнера, front_insert_iterator вставляет элементы в начале контейнера, а insert_iterator вставляет элементы, куда итератор указывает в контейнере. back_inserter, front_inserter и inserter - три функции, создающие итераторы вставки из контейнера.

template ‹class Container›

class back_insert_iterator: public output_iterator {

protected:

Container& container;

public:

back_insert_iterator(Container& x): container(x) {}

back_insert_iterator ‹Container›& operator=(const Container::value_type& value) {

container.push_back(value);

return *this;

}

back_insert_iterator‹Container›& operator*() {return *this;}

back_insert_iterator‹Container›& operator++() {return *this;}

back_insert_iterator‹Container›& operator++(int) {return *this;}

};

template ‹class Container›

back_insert_iterator‹Container› back_inserter(Container& x) {

return back_insert_iterator‹Container›(x);

}

template ‹class Container›

class front_insert_iterator: public output_iterator {

protected:

Container& container;

public:

front_insert_iterator(Container& x): container (x) {}

front_insert_iterator‹Container›& operator=(const Container::value_type& value) {

container.push_front(value);

return *this;

}

front_insert_iterator‹Container›& operator*() {return *this;}

front_insert_iterator‹Container›& operator++() {return *this;}

front_insert_iterator‹Container›& operator++(int) {return *this;}

};

template ‹class Container›

front_insert_iterator‹Container› front_inserter(Container& x) {

return front_insert_iterator‹Container›(х);

}

template ‹class Container›

class insert_iterator: public output_iterator {

protected:

Container& container;

Container::iterator iter;

public:

insert_iterator(Container& x, Container::iterator i) : container (x), iter(i) {}

insert_iterator‹Container›& operator=(const Container::value_type& value) {

iter = container.insert(iter, value);

++iter;

return *this;

}

insert_iterator‹Container›& operator*() {return *this;}

insert_iterator‹Container›& operator++() {return *this;}

insert_iterator‹Container›& operator++(int) {return *this;}

};

template ‹class Container, class Iterator›

insert_iterator<Container› inserter(Container& x, Iterator i) {

return insert_iterator‹Container›(x, Container::iterator(i));

}

Адаптеры функций (Function adaptors)

Функциональные адаптеры работают только с классами функциональных объектов с определёнными типами параметров и типом результата.

Отрицатели (Negators)

Отрицатели not1 и not2 берут унарный и бинарный предикаты соответственно и возвращают их дополнения.

template ‹class Predicate›

class unary_negate: public unary_function‹Predicate::argument_type, bool› {

protected:

Predicate pred;

public:

unary_negate(const Predicate& x): pred(x) {}

bool operator()(const argument_type& x) const {return !pred(x);}

};

template ‹class Predicate›

unary_negate‹Predicate› not1(const Predicate& pred) {

return unary_negate‹Predicate›(pred);

}

template ‹class Predicate›

class binary_negate: public binary_function‹Predicate::first_argument_type, Predicate::second_argument_type, bool› {

protected:

Predicate pred;

public:

binary_negate(const Predicate& x): pred(x) {}

bool operator()(const first_argument_type& x, const second_argument_type& y) const {

return !pred(x, y);

}

};

template ‹class Predicate›

binary_negate‹Predicate› not2(const Predicate& pred) {

return binary_negate‹Predicate›(pred);

}

Привязки (Binders)

Привязки bind1st и bind2nd берут функциональный объект f двух параметров и значение x и возвращают функциональный объект одного параметра, созданный из f с первым или вторым параметром соответственно, связанным с х.

template ‹class Predicate›

class binder1st: public unary_function {

protected:

Operation op;

Operation::first_argument_type value;

public:

binder1st(const Operation& x, const Operation::first_argument_type& y) : op(x), value(y) {}

result_type operator()(const argument_type& x) const {

return op(value, x);

}

};

template ‹class Operation, class T›

binder1st‹Operation› bind1st(const Operation& op, const T& x) {

return binder1st‹Operation›(op, Operation::first_argument_type(x));

}

template ‹class Operation›

class binder2nd: public unary_function‹0peration::first_argument_type, Operation::result_type› {

protected:

Operation op;

Operation::second_argument_type value;

public:

binder2nd(const Operation& x, const Operation::second_argument_type& y) : op(x), value(y) {}

result_type operator()(const argument_type& x) const {

return op(x, value);

}

};

template ‹class Operation, class T›

binder2nd‹Operation› bind2nd(const Operation& op, const T& x) {

return binder2nd‹0peration›(op, Operation::second_argument_type(x));

}

Например, find_if(v.begin(), v.end(), bind2nd(greater‹int›(), 5)) находит первое целое число в векторе v большее, чем 5; find_if(v.begin(), v.end(), bind1st(greater‹int›(), 5)) находит первое целое число в v меньшее, чем 5.

Адаптеры указателей на функции (Adaptors for pointers to functions)

Чтобы позволить указателям на (унарные и бинарные) функции работать с функциональными адаптерами, библиотека обеспечивает следующее:

template ‹class Arg, class Result›

class pointer_to_unary_function: public unary_function‹Arg, Result› {

protected:

Result (*ptr)(Arg);

public:

pointer_to_unary_function() {}

pointer_to_unary_function(Result (*x)(Arg)): ptr(x) {}

Result operator()(Arg x) const {return ptr(x);}

};

template ‹class Arg, class Result›

pointer_to_unary_function‹Arg, Result› ptr_fun(Result (*x)(Arg)) {

return pointer_to_unary_function‹Arg, Result›(x);

}

template

class pointer_to_binary_function: public binary_function {

protected:

Result (*ptr)(Arg1, Arg2);

public:

pointer_to_binary_function() {}

pointer_to_binary_function(Result (*x)(Arg1, Arg2)): ptr(х) {}

Result operator()(Arg1 x, Arg2 y) const {return ptr(x, y);}

};

template ‹class Arg1, class Arg2, class Result›

pointer_to_binary_function‹Arg1, Arg2, Result› ptr_fun(Result (*x)(Arg1, Arg2)) {

return pointer_to_binary_function‹Argl, Arg2, Result›(x);

}

Например, replace_if(v.begin(), v.end(), not1(bind2nd(ptr_fun(strcmp), "C")), "C++") заменяет все "С" на "C++" в последовательности v.

Системы трансляции, которые имеют множественный указатель на типы функций, должны обеспечить дополнительные шаблоны функций ptr_fun.

Примитивы управления памятью (Memory Handling Primitives)

Чтобы получать типичный указатель на неинициализированный буфер памяти данного размера, определена следующая функция:

template ‹class T›

inline T* allocate(ptrdiff_t n, Т*); // n ›= 0

Размер (в байтах) распределённого буфера - не меньше n*sizeof(T).

Для каждой модели памяти имеется соответствующий шаблон функции allocate, определённый с типом первого параметра, являющимся типом расстояния указателей в модели памяти.

Например, если система трансляции поддерживает _huge указатели с типом расстояния long long, обеспечивается следующая шаблонная функция:

template ‹class T›

inline T _huge* allocate(long long n, T _huge *);

Также обеспечиваются следующие функции:

template ‹class T›

inline void deallocate(T* buffer);

template ‹class T1, class T2›

inline void construct(T1* p, const T2& value) {new (p) T1(value);}

template ‹class T›

inline void destroy(T* pointer) {pointer-›~T();}

deallocate освобождает буфер, выделенный allocate. Для каждой модели памяти имеются соответствующие шаблоны функций deallocate, construct и destroy, определённые с типом первого параметра, являющимся типом указателя в модели памяти.

template ‹class T›

pair‹T*, ptrdiff_t› get_temporary_buffer(ptrdiff_t n, T*);

template ‹class T›

void return_temporary_buffer(T* p);

get_temporary_buffer ищет наибольший буфер, не больше чем n*sizeof(T), и возвращает пару, состоящую из адреса и размера (в единицах sizeof(T)) буфера. return_temporary_buffer возвращает буфер, выделенный get_temporary_buffer.

ПРИМЕРЫ ПРОГРАММ С ШАБЛОНАМИ

Эти примеры демонстрируют использование нового продукта STL ‹ToolKit› от компании ObjectSpace. STL ‹ToolKit› - это самый простой способ использования STL, который работает на большинстве комбинаций платформ/компиляторов, включая cfront, Borland, Visual C++, Set C++, ObjectCenter и последние компиляторы от Sun&HP.

accum1.cpp

#include ‹ospace/stl.h›

#include ‹iostream.h›

int main() {

vector‹int› v(5);

for (int i = 0; i ‹ v.size(); i++) v[i] = i + 1;

int sum = accumulate(v.begin(), v.end(), 0);

cout ‹‹ "sum = " ‹‹ sum ‹‹ endl;

return 0;

}

accum2.cpp

#include ‹stl.h›

#include ‹iostream.h›

int mult(int initial_, int element_) {

return initial_ * element_;

}

int main() {

vector‹int› v(5);

for (int i = 0; i ‹ v.size(); i++) v[i] = i + 1;

int prod = accumulate(v.begin(), v.end(), 1, mult);

cout ‹‹ "prod = " ‹‹ prod ‹‹ endl;

return 0;

}

search2.cpp

#include ‹stl.h›

#include ‹iostream.h›

#include ‹string.h›

bool str_equal(const char* a_, const char* b_) {

return ::strcmp(a_, b_) == 0 ? 1:0;

}

char* grades[] = {"A", "B", "C", "D", "F"};

char* letters[] = {"Q", "E", "D"};

int main() {

const unsigned gradeCount = sizeof(grades) / sizeof(grades[0]);

const unsigned letterCount = sizeof(letters) / sizeof(letters[0]);

ostream_iterator ‹char*› iter(cout, " ");

cout ‹‹ "grades: ";

copy(grades, grades + gradeCount, iter);

cout ‹‹ "\nletters:";

copy(letters, letters + letterCount, iter);

cout ‹‹ endl;

char** location = search(grades, grades + gradeCount, letters, letters + letterCount, str_equal);

if (location == grades + gradeCount) cout ‹‹ "letters not found in grades" ‹‹ endl;

else cout ‹‹ "letters found in grades at offset: " ‹‹ location - grades ‹‹ endl;

copy(grades + 1, grades + 1 + letterCount, letters);

cout ‹‹ "grades: ";

copy(grades, grades + gradeCount, iter);

cout ‹‹ "\nletters:";

copy(letters, letters + letterCount, iter);

cout ‹‹ endl;

location = search(grades, grades + gradeCount, letters, letters + letterCount, str_equal);

if (location == grades + gradeCount) cout ‹‹ "letters not found in grades" ‹‹ endl;

else cout ‹‹ "letters found in grades at offset: " ‹‹ location - grades ‹‹ endl;

return 0;

}

incl2.cpp

#include ‹stl.h›

#include ‹iostream.h›

#include ‹string.h›

bool compare_strings(const char* s1_, const char* s2_) {

return ::strcmp(s1_, s2_) ‹ 0 ? 1: 0;

}

char* names[] = {"Todd", "Mike", "Graham", "Jack", "Brett"};

int main() {

const unsigned nameSize = sizeof(names)/sizeof(names[0]);

vector‹char*› v1(nameSize);

for (int i = 0; i ‹ v1.size(); i++) {

v1[i] = names[i];

}

vector‹char*› v2(2);

v2[0] = "foo";

v2[1] = "bar";

sort(v1.begin(), v1.end(), compare_strings);

sort(v2.begin(), v2.end(), compare_strings);

bool inc = includes(v1.begin(), v1.end(), v2.begin(), v2.end(), compare_strings);

if (inc) cout ‹‹ "v1 includes v2" ‹‹ endl;

else cout ‹‹ "v1 does not include v2" ‹‹ endl;

v2[0] = "Brett";

v2[1] = "Todd";

inc = includes(v1.begin(), v1.end(), v2.begin(), v2.end(), compare_strings);

if (inc) cout ‹‹ "v1 includes v2" ‹‹ endl;

else cout ‹‹ "v1 does not include v2" ‹‹ endl;

return 0;

}

search1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

typedef vector‹int› IntVec;

IntVec v1(10);

iota(v1.begin(), v1.end(), 0);

IntVec v2(3);

iota(v2.begin(), v2.end(), 50);

ostream_iterator‹int› iter(cout, " ");

cout ‹‹ "v1: ";

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

cout ‹‹ "v2: ";

copy(v2.begin(), v2.end(), iter);

cout ‹‹ endl;

IntVec::iterator location;

location = search(v1.begin(), v1.end(), v2.begin(), v2.end());

if (location == v1.end()) cout ‹‹ "v2 not contained in v1" ‹‹ endl;

else cout ‹‹ "Found v2 in v1 at offset: " ‹‹ location - v1.begin() ‹‹ endl;

iota(v2.begin(), v2.end(), 4);

cout ‹‹ "v1: ";

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

cout ‹‹ "v2: ";

copy(v2.begin(), v2.end(), iter);

cout ‹‹ endl;

location = search(v1.begin(), v1.end(), v2.begin(), v2.end());

if (location == v1.end()) cout ‹‹ "v2 not contained in v1" ‹‹ endl;

else cout ‹‹ "Found v2 in v1 at offset: " ‹‹ location - v1.begin() ‹‹ endl;

return 0;

}

istmit2.cpp

#include ‹iostream.h›

#include ‹fstream.h›

#include ‹stl.h›

typedef vector‹char› Line;

void printLine(const Line* line_) {

vector‹char›::const_iterator i;

for (i = line_-›begin(); i!= line_-›end(); i++) cout ‹‹ *i;

cout ‹‹ endl;

}

int main() {

Line buffer;

vector‹Line*› lines;

ifstream s("data.txt");

s.unsetf(ios::skipws); // Disable white-space skipping.

istream_iterator‹char, ptrdiff_t› it1(s); // Position at start of file.

istream_iterator‹char, ptrdiff_t› it2; // Serves as "past-the-end" marker.

copy(it1, it2, back_inserter(buffer));

Line::iterator i = buffer.begin();

Line::iterator p;

while (i != buffer.end()) {

p = find(i, buffer.end(), '\n');

lines.push_back(new Line(i, p));

i = ++p;

}

sort(lines.begin(), lines.end(), less_p‹Line*›());

cout ‹‹ "Read " ‹‹ lines.size() ‹‹ " lines" ‹‹ endl;

vector‹Line*›::iterator j;

for(j = lines.begin(); j!= lines.end(); j++) printLine(*j);

release(lines.begin(), lines.end()); // Release memory.

return 0;

}

alloc1.cpp

#include ‹stl.h›

#include ‹ospace/stl/examples/myaloc.h›

int main() {

{

cout ‹‹ "vectors:" ‹‹ endl;

os_my_allocator‹int› alloc;

vector‹int› v3(alloc);

v3.push_back(42);

vector‹int› v4(alloc);

v4.push_back(42);

}

{

cout ‹‹ "bit_vectors:" ‹‹ endl;

os_my_allocator‹unsigned int› alloc;

bit_vector v1(alloc);

v1.push_back(1);

}

{

cout ‹‹ "deques:" ‹‹ endl;

os_my_allocator‹int› alloc;

deque‹int› d(alloc);

d.push_back(42);

}

{

cout ‹‹ "lists:" ‹‹ endl;

os_my_allocator‹os_list_node‹int› › alloc;

list‹int› l(alloc);

l.push_back(42);

}

{

cout ‹‹ "sets:" ‹‹ endl;

os_my_allocator‹os_value_node‹int› › alloc;

set‹int, less‹int› › s(alloc);

s.insert(42);

}

{

cout ‹‹ "maps" ‹‹ endl;

os_my_allocator‹os_value_node‹os_pair‹const int, float› › › alloc;

map‹int, float, less‹int› › m(alloc);

m[4] = 2.0;

}

return 0;

}

release2.cpp

#include ‹stl.h›

#include ‹iostream.h›

class X {

public:

X(int i_): i (i_) {}

~X() {cout ‹‹ "Delete X(" ‹‹ i ‹‹ ")" ‹‹ endl;}

int i;

};

ostream& operator ‹‹ (ostream& stream_, const X& x_) {

return stream_ ‹‹ "X(" ‹‹ x_.i ‹‹ ")";

}

int main() {

vector‹X*› v;

v.push_back(new X(2));

v.push_back(new X(1));

v.push_back(new X(4));

vector‹X*›::iterator i;

cout ‹‹ "Initial contents:" ‹‹ endl;

for (i = v.begin(); i!= v.end(); i++) cout ‹‹ " " ‹‹ *(*i) ‹‹ endl;

release(v.begin()); // Delete the first heap-based object.

v.erase(v.begin()); // Erase the first element.

cout ‹‹ "Remaining contents:" ‹‹ endl;

for (i = v.begin(); i != v.end(); i++) cout ‹‹ " " ‹‹ *(*i) ‹‹ endl;

release(v.begin(), v.end()); // Delete remaining heap-based objects.

v.erase(v.begin(), v.end()); // Erase remaining elements.

return 0;

}

map1.cpp

#include ‹iostream.h›

#include ‹stl.h›

int main() {

typedef map‹char, int, less‹char› › maptype;

maptype m;

// Store mappings between roman numerals and decimals.

m['l'] = 50;

m['x'] = 20; // Deliberate mistake.

m['v'] = 5;

m['i'] = 1;

cout ‹‹ "m['x'] = " ‹‹ m['x'] ‹‹ endl;

m['x'] = 10; // Correct mistake.

cout ‹‹ "m['x'] = " ‹‹ m['x'] ‹‹ endl;

cout ‹‹ "m['z'] = " ‹‹ m['z'] ‹‹ endl; // Note default value is added.

cout ‹‹ "m.count('z') = " ‹‹ m.count('z') ‹‹ endl;

pair‹maptype::iterator, bool› p;

p = m.insert(pair‹const char, int›('c', 100));

if (p.second) cout ‹‹ "First insertion successful" ‹‹ endl;

p = m.insert(pair‹const char, int› ('c', 100));

if (p.second) cout ‹‹ "Second insertion successful" ‹‹ endl;

else cout ‹‹ "Existing pair " ‹‹ (*(p.first)).first ‹‹ " -› " ‹‹ (*(p.first)).second ‹‹ endl;

return 0;

}

mismtch2.cpp

#include ‹stl.h›

#include ‹iostream.h›

#include ‹string.h›

bool str_equal(const char* a_, const char* b_) {

return ::strcmp(a_, b_) == 0 ? 1: 0;

}

const unsigned size = 5;

char* n1[size] = {"Brett", "Graham", "Jack", "Mike", "Todd"};

int main() {

char* n2[size];

copy(n1, n1 + 5, n2);

pair‹char**, char**› result;

result = mismatch(n1, n1+ size, n2, str_equal);

if (result.first == n1 + size && result.second == n2 + size)

cout ‹‹ "n1 and n2 are the same" ‹‹ endl;

else cout ‹‹ "mismatch at index: " ‹‹ (result.first - n1) ‹‹ endl;

n2[2] = "QED";

result = mismatch(n1, n1 + size, n2, str_equal);

if (result.first == n2 + size && result.second == n2 + size)

cout ‹‹ "n1 and n2 are the same" ‹‹ endl;

else cout ‹‹ "mismatch at index: " ‹‹ (result.first - n1) ‹‹ endl;

return 0;

}

mismtch1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

typedef vector‹int› IntVec;

IntVec v1(10);

IntVec v2(v1.size());

iota(v1.begin(), v1.end(), 0);

iota(v2.begin(), v2.end(), 0);

pair ‹IntVec::iterator, IntVec::iterator› result;

result = mismatch(v1.begin(), v1.end(), v2.begin());

if (result.first = v1.end() && result.second == v2.end())

cout ‹‹ "v1 and v2 are the same" ‹‹ endl;

else cout ‹‹ "mismatch at index: " ‹‹ (result.first - v1.begin()) ‹‹ endl;

v2[v2.size()/2] = 42;

result = mismatch(v1.begin(), v1.end(), v2.begin());

if (result.first == v1.end() && result.second == v2.end())

cout ‹‹ "v1 and v2 are the same" ‹‹ endl;

else cout ‹‹ "mismatch at index: " ‹‹ (result.first - v1.begin()) ‹‹ endl;

return 0;

}

mmap2.cpp

#include ‹iostream.h›

#include ‹stl.h›

typedef multimap‹int, char, less‹int› › mmap;

typedef pair‹const int, char› pair_type;

pair_type p1(3, 'c');

pair_type p2(6, 'f');

pair_type p3(1, 'a');

pair_type p4(2, 'b');

pair_type p5(3, 'x');

pair_type p6(6, 'f');

pair_type array[] = { p1, p2, p3, p4, p5, p6 };

int main() {

mmap m(array, array + 7);

mmap::iterator i;

// Return location of first element that is not less than 3

i = m.lower_bound(3);

cout ‹‹ "lower bound:" ‹‹ endl;

cout ‹‹ (*i).first ‹‹ " -› " ‹‹ (*i).second ‹‹ endl;

// Return location of first element that is greater than 3

i = m.upper_bound(3);

cout ‹‹ "upper bound:" ‹‹ endl;

cout ‹‹ (*i).first ‹‹ " -› " ‹‹ (*i).second ‹‹ endl;

return 0;

}

adjfind2.cpp

#include ‹stl.h›

#include ‹iostream.h›

#include ‹string.h›

typedef vector‹char*› CStrVector;

int equal_length(const char* v1_, const char* v2_) {

return ::strlen(v1_) == ::strlen(v2_);

}

char* names[] = {"Brett", "Graham", "Jack", "Mike", "Todd"};

int main() {

const int nameCount = sizeof(names)/sizeof(names[0]);

CStrVector v(nameCount);

for (int i = 0; i ‹ nameCount; i++) v[i] = names[i];

CStrVector::iterator location;

location = adjacent_find(v.begin(), v.end(), equal_length);

if (location!= v.end())

cout ‹‹ "Found two adjacent strings of equal length: " ‹‹ *location

‹‹ " -and- " ‹‹ *(location + 1) ‹‹ endl;

else cout ‹‹ "Didn't find two adjacent strings of equal length.";

return 0;

}

list3.cpp

#include ‹iostream.h›

#include ‹stl.h›

char array[] = {'x', 'l', 'x', 't', 's', 's'};

int main() {

list‹char› str(array, array + 6);

list‹char›::iterator i;

cout ‹‹ "original: ";

for (i = str.begin(); i != str.end(); i++) cout ‹‹ *i;

cout ‹‹ endl;

cout ‹‹ "reversed: ";

str.reverse();

for (i = str.begin(); i != str.end(); i++) cout ‹‹ *i;

cout ‹‹ endl;

cout ‹‹ "removed: ";

str.remove('x');

for (i = str.begin(); i != str.end(); i++) cout ‹‹ *i;

cout ‹‹ endl;

cout ‹‹ "uniqued: ";

str.unique();

for (i = str.begin(); i != str.end(); i++) cout ‹‹ *i;

cout ‹‹ endl;

cout ‹‹ "sorted: ";

str.sort();

for (i = str.begin(); i != str.end(); i++) cout ‹‹ *i;

cout ‹‹ endl;

return 0;

}

parsrtc2.cpp

#include ‹stl.h›

#include ‹iostream.h›

#include ‹string.h›

bool str_compare(const char* a_, const char* b_) {

return ::strcmp(a_, b_) ‹ 0 ? 1: 0;

}

char* names[] = {"aa", "ff", "dd", "ee", "cc", "bb"};

int main() {

const unsigned nameSize = sizeof(names) / sizeof(names[0]);

vector‹char*› v1(nameSize);

for (int i = 0; i ‹ v1.size(); i++) v1[i] = names[i];

ostream_iterator‹char*› iter(cout, " ");

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

vector‹char*› result(5);

partial_sort_copy(v1.begin(), v1.end(), result.begin(), result.end(), str_compare);

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

return 0;

}

vec6.cpp

#include ‹iostream.h›

#include ‹stl.h›

int array[] = {1, 4, 9, 16, 25, 36};

int main() {

vector‹int› v(array, array + 6);

for (int i = 0; i ‹ v.size(); i++) cout ‹‹ "v[" ‹‹ i ‹‹ "] = " ‹‹ v[i] ‹‹ endl;

cout ‹‹ endl;

v.erase(v.begin()); // Erase first element.

for (i = 0; i ‹ v.size(); i++) cout ‹‹ "v[" ‹‹ i ‹‹ "] = " ‹‹ v[i] ‹‹ endl;

cout ‹‹ endl;

v.erase(v.end() - 1); // Erase last element.

for (i = 0; i ‹ v.size(); i++) cout ‹‹ "v[" ‹‹ i ‹‹ "] = " ‹‹ v[i] ‹‹ endl;

cout ‹‹ endl;

v.erase(v.begin() + 1, v.end() - 1); // Erase all but first and last.

for (i = 0; i ‹ v.size(); i++)

cout ‹‹ "v[" ‹‹ i ‹‹ "] = " ‹‹ v[i] ‹‹ endl;

cout ‹‹ endl;

v.erase(); // Erase all.

return 0;

}

inrprod2.cpp

#include ‹stl.h›

#include ‹iostream.h›

#include ‹string.h›

int add(int a_, int b_) {

return a_ + b_;

}

int mult(int a_, int b_) {

return a_ * b_;

}

int main() {

vector‹int› v1(3);

vector‹int› v2(v1.size());

for (int i = 0; i ‹ v1.size(); i++) {

v1[i] = i + 1;

v2[i] = v1.size() - i;

}

ostream_iterator‹int› iter(cout, " ");

cout ‹‹ "Inner product(product of sums):\n\t";

copy(v1.begin(), v1.end(), iter);

cout ‹‹ "\n\t";

copy(v2.begin(), v2.end(), iter);

int result = inner_product(v1.begin(), v1.end(), v2.begin(), 1, mult, add);

cout ‹‹ "\nis: " ‹‹ result ‹‹ endl;

return 0;

}

mmap1.cpp

#include ‹iostream.h›

#include ‹stl.h›

int main() {

typedef multimap‹char, int, less‹char› › mmap;

mmap m;

cout ‹‹ "count('X') = " ‹‹ m.count('X') ‹‹ endl;

m.insert(pair‹const char, int›('X', 10)); // Standard way.

cout ‹‹ "count('X') = " ‹‹ m.count('X') ‹‹ endl;

m.insert('X', 20); // Non-standard, but very convenient!

cout ‹‹ "count('X') = " ‹‹ m.count('X') ‹‹ endl;

m.insert('Y', 32);

mmap::iterator i = m.find('X'); // Find first match.

while (i != m.end()) { // Loop until end is reached.

cout ‹‹ (*i).first ‹‹ " -› " ‹‹ (*i).second ‹‹ endl;

i++;

}

int count = m.erase('X');

cout ‹‹ "Erased " ‹‹ count ‹‹ " items" ‹‹ endl;

return 0;

}

adjfind0.cpp

#include ‹stl.h›

#include ‹iostream.h›

int numbers1[5] = {1, 2, 4, 8, 16};

int numbers2[5] = {5, 3, 2, 1, 1};

int main() {

int* location = adjacent_find(numbers1, numbers1 + 5);

if (location != numbers1 + 5)

cout ‹‹ "Found adjacent pair of: " ‹‹ *location ‹‹ " at offset " ‹‹ (location - numbers1) ‹‹ endl;

else cout ‹‹ "No adjacent pairs" ‹‹ endl;

location = adjacent_find(numbers2, numbers2 + 5);

if (location != numbers2 + 5)

cout ‹‹ "Found adjacent pair of: " ‹‹ *location ‹‹ " at offset " ‹‹ (location - numbers2) ‹‹ endl;

else cout ‹‹ "No adjacent pairs" ‹‹ endl;

return 0;

}

parsrt2.cpp

#include ‹stl.h›

#include ‹iostream.h›

#include ‹string.h›

bool str_compare(const char* a_, const char* b_) {

return ::strcmp(a_, b_) ‹ 0 ? 1: 0;

}

char* names[] = {"aa", "ff", "dd", "ee", "cc", "bb"};

int main() {

const unsigned nameSize = sizeof(names) / sizeof(names[0]);

vector‹char*› v1(nameSize);

for (int i = 0; i ‹ v1.size(); i++) v1[i] = names[i];

ostream_iterator‹char*› iter(cout, " ");

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

partial_sort(v1.begin(), v1.begin() + nameSize/2, v1.end(), str_compare);

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

return 0;

}

mset5.cpp

#include ‹iostream.h›

#include ‹stl.h›

bool less_than(int a_, int b_) {

return a_ ‹ b_;

}

bool greater_than(int a_, int b_) {

return a_ › b_;

}

int array[] = {3, 6, 1, 9};

int main() {

typedef pointer_to_binary_function‹int, int, bool› fn_type;

typedef multiset‹int, fn_type› mset;

fn_type f(less_than);

mset s1(array, array + 4, f);

mset::const_iterator i = s1.begin();

cout ‹‹ "Using less_than: " ‹‹ endl;

while (i != s1.end()) cout ‹‹ *i++ ‹‹ endl;

fn_type g(greater_than);

mset s2(array, array + 4, g);

i = s2.begin();

cout ‹‹ "Using greater_than: " ‹‹ endl;

while (i != s2.end()) cout ‹‹ *i++ ‹‹ endl;

return 0;

}

mset1.cpp

#include ‹iostream.h›

#include ‹stl.h›

int main() {

typedef multiset‹int, less‹int› › mset;

mset s;

cout ‹‹ "count(42) = " ‹‹ s.count(42) ‹‹ endl;

s.insert(42);

cout ‹‹ "count(42) = " ‹‹ s.count(42) ‹‹ endl;

s.insert(42);

cout ‹‹ "count(42) = " ‹‹ s.count(42) ‹‹ endl;

set‹int, less‹int› ›::iterator i = s.find(40);

if (i == s.end()) cout ‹‹ "40 Not found" ‹‹ endl;

else cout ‹‹ "Found " ‹‹ *i ‹‹ endl;

i = s.find(42);

if (i == s.end()) cout ‹‹ "Not found" ‹‹ endl;

else cout ‹‹ "Found " ‹‹ *i ‹‹ endl;

int count = s.erase(42);

cout ‹‹ "Erased " ‹‹ count ‹‹ " instances" ‹‹ endl;

return 0;

}

vec2.cpp

#include ‹iostream.h›

#include ‹stl.h›

void print(vector‹double›& vector_) {

for (int i = 0; i ‹ vector_.size(); i++)

cout ‹‹ vector_[i] ‹‹ " ";

cout ‹‹ endl;

}

int main() {

vector‹double› v1; // Empty vector of doubles.

v1.push_back(32.1);

v1.push_back(40.5);

vector‹double› v2; // Another empty vector of doubles.

v2.push_back(3.56);

cout ‹‹ "v1 = ";

print(v1);

cout ‹‹ "v2 = ";

print(v2);

v1.swap(v2); // Swap the vector's contents.

cout ‹‹ "v1 = ";

print(v1);

cout ‹‹ "v2 = ";

print(v2);

v2 = v1; // Assign one vector to another.

cout ‹‹ "v2 = ";

print(v2);

return 0;

}

uniqcpy2.cpp

#include ‹stl.h›

#include ‹iostream.h›

#include ‹string.h›

bool str_equal(const char* a_, const char* b_) {

return ::strcmp(a_, b_) - 0 ? 1: 0;

}

char* labels[] = {"Q","Q","W","W","E","E","R","T","T","Y","Y"};

int main() {

const unsigned count = sizeof(labels) / sizeof(labels[0]);

ostream_iterator ‹char*› iter(cout);

copy(labels, labels + count, iter);

cout ‹‹ endl;

char* uCopy[count];

fill(uCopy, uCopy + count, ");

unique_copy(labels, labels + count, uCopy, str_equal);

copy(labels, labels + count, iter);

cout ‹‹ endl;

copy(uCopy, uCopy + count, iter);

cout ‹‹ endl;

return 0;

}

mismtch0.cpp

#include ‹stl.h›

#include ‹iostream.h›

int n1[5] = {1, 2, 3, 4, 5};

int n2[5] = {1, 2, 3, 4, 5};

int n3[5] = {1, 2, 3, 2, 1};

int main() {

pair ‹int*, int*› result;

result = mismatch(n1, n1 + 5, n2);

if (result.first == (n1 + 5) && result.second == (n2 + 5))

cout ‹‹ "n1 and n2 are the same" ‹‹ endl;

else cout ‹‹ "Mismatch at offset: " ‹‹ (result.first - n1) ‹‹ endl;

result = mismatch(n1, n1 + 5, n3);

if (result.first == (n1 + 5) && result.second == (n3 + 5))

cout ‹‹ "n1 and n3 are the same" ‹‹ endl;

else cout ‹‹ "Mismatch at offset: " ‹‹ (result.first - n1) ‹‹ endl;

return 0;

}

rndshuf2.cpp

#include ‹stl.h›

#include ‹stdlib.h›

#include ‹iostream.h›

class MyRandomGenerator {

public:

nsigned long operator()(unsigned long n_);

};

unsigned long MyRandomGenerator::operator()(unsigned long n_) {

return rand() % n_;

}

int main() {

vector‹int› v1(10);

iota(v1.begin(), v1.end(), 0);

ostream_iterator ‹int› iter(cout, " ");

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

MyRandomGenerator r;

for (int i = 0; i ‹ 3; i++) {

random_shuffle(v1.begin(), v1.end(), r);

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

}

return 0;

}

merge2.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

vector‹int› v1(5);

vector‹int› v2(v1.size());

for (int i = 0; i ‹ v1.size(); i++) {

v1[i] = 10 - i;

v2[i] = 7 - i;

}

vector‹int› result(v1.size() + v2.size());

merge(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin(), greater‹int›());

ostream_iterator ‹int› iter(cout, " ");

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

copy(v2.begin(), v2.end(), iter);

cout ‹‹ endl;

copy(result.begin(), result.end(), iter);

cout ‹‹ endl;

return 0;

}

adjfind1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

typedef vector‹int› IntVector;

IntVector v(10);

for (int i = 0; i ‹ v.size(); i++) v[i] = i;

IntVector::iterator location;

location = adjacent_find(v.begin(), v.end());

if (location != v.end()) cout ‹‹ "Found adjacent pair of: " ‹‹ *location ‹‹ endl;

else cout ‹‹ "No adjacent pairs" ‹‹ endl;

v[6] = 7;

location = adjacent_find(v.begin(), v.end());

if (location!= v.end()) cout ‹‹ "Found adjacent pair of: " ‹‹ *location ‹‹ endl;

else cout ‹‹ "No adjacent pairs" ‹‹ endl;

return 0;

}

vec7.cpp

#include ‹iostream.h›

#include ‹stl.h›

int array1[] = {1, 4, 25};

int array2[] = {9, 16};

int main() {

vector‹int› v(array1, array1 + 3);

v.insert(v.begin(), 0); // Insert before first element.

v.insert(v.end(), 36); // Insert after last element.

for (int i = 0; i ‹ v.size(); i++) cout ‹‹ "v[" ‹‹ i ‹‹ "] = " ‹‹ v[i] ‹‹ endl;

cout ‹‹ endl;

// Insert contents of array2 before fourth element.

v.insert(v.begin() + 3, array2, array2 + 2);

for (i = 0; i ‹ v.size(); i++)

cout ‹‹ "v[" ‹‹ i ‹‹ "] = " ‹‹ v[i] ‹‹ endl;

cout ‹‹ endl;

return 0;

}

bcompos1.cpp

#include ‹iostream.h›

#include ‹stl.h›

struct odd: public unary_function‹int, bool› {

odd() {}

bool operator() (int n_) const {return (n_ % 2) - 1;}

};

struct positive: public unary_function‹int, bool› {

positive() {}

bool operator() (int n_) const {return n_ ›= 0;}

};

int array[6] = {-2, -1, 0, 1, 2, 3};

int main() {

binary_compose‹logical_and‹bool›, odd, positive› b(logical_and‹bool›(), odd(), positive());

int* p = find_if(array, array + 6, b);

if (p != array + 6) cout ‹‹ *p ‹‹ " is odd and positive" ‹‹ endl;

return 0;

}

setsymd2.cpp

#include ‹stl.h›

#include ‹iostream.h›

#include ‹string.h›

char* word1 = "ABCDEFGHIJKLMNO";

char* word2 = "LMNOPQRSTUVWXYZ";

int main() {

ostream_iterator‹char› iter(cout, " ");

cout ‹‹ "word1: ";

copy(word1, word1 + ::strlen(word1), iter);

cout ‹‹ "\nword2: ";

copy(word2, word2 + ::strlen(word2), iter);

cout ‹‹ endl;

set_symmetric_difference(word1, word1 + ::strlen(word1), word2, word2 + ::strlen(word2), iter, less‹char›());

cout ‹‹ endl;

return 0;

}

search0.cpp

#include ‹stl.h›

#include ‹iostream.h›

int v1[6] = {1, 1, 2, 3, 5, 8};

int v2[6] = {0, 1, 2, 3, 4, 5};

int v3[2] = {3, 4};

int main() {

int* location;

location = search(v1, v1 + 6, v3, v3 + 2);

if (location == v1 + 6) cout ‹‹ "v3 not contained in v1" ‹‹ endl;

else cout ‹‹ "Found v3 in v1 at offset: " ‹‹ location - v1 ‹‹ endl;

location = search(v2, v2 + 6, v3, v3 + 2);

if (location == v2 + 6) cout ‹‹ "v3 not contained in v2" ‹‹ endl;

else cout ‹‹ "Found v3 in v2 at offset: " ‹‹ location - v2 ‹‹ endl;

return 0;

}

eqlrnge1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

typedef vector‹int› IntVec;

IntVec v(10);

for (int i = 0; i ‹ v.size(); i++) v[i] = i / 3; ostream_iterator‹int› iter(cout, " ");

cout ‹‹ "Within the collection:\n\t";

copy(v.begin(), v.end(), iter);

pair‹IntVec::iterator, IntVec::iterator› range;

range = equal_range(v.begin(), v.end(), 2);

cout ‹‹ "\n2 can be inserted from before index " ‹‹ (range.first - v.begin())

‹‹ " to before index " ‹‹ (range.second - v.begin()) ‹‹ endl;

return 0;

}

rotcopy1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

vector‹int› v1(10);

iota(v1.begin(), v1.end(), 0);

ostream_iterator ‹int› iter(cout, " ");

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

vector‹int› v2(v1.size());

for (int i = 0; i ‹ v1.size(); i++) {

rotate_copy(v1.begin(), v1.begin() + i, v1.end(), v2.begin());

ostream_iterator‹int› iter(cout, " ");

copy(v2.begin(), v2.end(), iter);

cout ‹‹ endl;

}

cout ‹‹ endl;

return 0;

}

eqlrnge2.cpp

#include ‹stl.h›

#include ‹iostream.h›

#include ‹string.h›

char chars[] = "aabbccddggghhklllmqqqqssyyzz";

int main() {

const unsigned count = sizeof(chars) - 1;

ostream_iterator‹char› iter(cout);

cout ‹‹ "Within the collection:\n\t";

copy(chars, chars + count, iter);

pair‹char*, char*› range;

range = equal_range(chars, chars + count, 'q', less‹char›());

cout ‹‹ "\nq can be inserted from before index " ‹‹ (range.first - chars) ‹‹ " to before index "

‹‹ (range.second - chars) ‹‹ endl;

return 0;

}

release1.cpp

#include ‹stl.h›

#include ‹iostream.h›

class X {

public:

X(int i_): i(i_) {}

~X() {cout ‹‹ "Delete X(" ‹‹ i ‹‹ ")" ‹‹ endl;}

int i;

};

ostream& operator ‹‹ (ostream& stream_, const X& x_) {

return stream_ ‹‹ "X(" ‹‹ x_.i ‹‹ ")";

}

int main() {

vector‹X*› v;

v.push_back(new X(2));

v.push_back(new X(1));

v.push_back(new X(4));

vector‹X*›::iterator i;

for (i = v.begin(); i!= v.end(); i++) cout ‹‹ *(*i) ‹‹ endl;

release(v.begin(), v.end()); // Delete heap-based objects.

return 0;

}

incl1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

vector‹int› v1(10);

vector‹int› v2(3);

for (int i = 0; i ‹ v1.size(); i++) {

v1[i] = i;

}

if (includes(v1.begin(), v1.end(), v2.begin(), v2.end())) cout ‹‹ "v1 includes v2" ‹‹ endl;

else cout ‹‹ "v1 does not include v2" ‹‹ endl;

for (i = 0; i ‹ v2.size(); i++) v2[i] = i + 3;

if (includes(v1.begin(), v1.end(), v2.begin(), v2.end())) cout ‹‹ "v1 includes v2" ‹‹ endl;

else cout ‹‹ "v1 does not include v2" ‹‹ endl;

return 0;

}

setintr2.cpp

#include ‹stl.h›

#include ‹iostream.h›

#include ‹string.h›

char* word1 = "ABCDEFGHIJKLMNO";

char* word2 = "LMNOPQRSTUVWXYZ";

int main() {

ostream_iterator ‹char› iter(cout, " ");

cout ‹‹ "word1: ";

copy(word1, word1 + ::strlen(word1), iter);

cout ‹‹ "\nword2: ";

copy(word2, word2 + ::strlen(word2), iter);

cout ‹‹ endl;

set_intersection(word1, word1 + ::strlen(word1), word2, word2 + ::strlen(word2), iter, less‹char›());

cout ‹‹ endl;

return 0;

}

inrprod1.cpp

#include ‹stl.h›

#include ‹iostream.h›

#include ‹string.h›

int main() {

vector‹int› v1(3);

vector‹int› v2(v1.size());

for (int i = 0; i ‹ v1.size(); i++) {

v1[i] = i + 1;

v2[i] = v1.size() - i;

}

ostream_iterator‹int› iter(cout, " ");

cout ‹‹ "Inner product(sum of products) of:\n\t";

copy(v1.begin(), v1.end(), iter);

cout ‹‹ "\n\t";

copy(v2.begin(), v2.end(), iter);

int result = inner_product(v1.begin(), v1.end(), v2.begin(), 0);

cout ‹‹ "\nis: " ‹‹ result ‹‹ endl;

return 0;

}

merge1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

vector‹int› v1(5);

vector‹int› v2(v1.size());

iota(v1.begin(), v1.end(), 0);

iota(v2.begin(), v2.end(), 3);

vector‹int› result(v1.size() + v2.size());

merge(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());

ostream_iterator‹int› iter(cout, " ");

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

copy(v2.begin(), v2.end(), iter);

cout ‹‹ endl;

copy(result.begin(), result.end(), iter);

cout ‹‹ endl;

return 0;

}

bcompos2.cpp

#include ‹iostream.h›

#include ‹stl.h›

struct odd: public unary_function‹int, bool› {

odd() {}

bool operator() (int n_) const {return (n_ % 2) - 1;}

};

struct positive: public unary_function‹int, bool› {

positive() {}

bool operator() (int n_) const {return n_ ›= 0;}

};

int array[6] = {-2, -1, 0, 1, 2, 3};

int main() {

int* p = find_if(array, array + 6, compose2(logical_and‹bool›(), odd(), positive()));

if (p != array + 6) cout ‹‹ *p ‹‹ " is odd and positive" ‹‹ endl;

return 0;

}

error3.cpp

#include ‹stl.h›

// Compile this code without defining OS_USE_EXCEPTIONS.

void my_handler(int code_, const char* str_) {

cout ‹‹ "Caught " ‹‹ str_ ‹‹ "[code " ‹‹ code_ ‹‹ "]" ‹‹ endl;

}

int main() {

os_handler_function_t old_h = os_set_error_handler(my_handler);

vector‹int› v;

v.pop_back(); // Generates an empty object error.

cout ‹‹ "returned from pop_back()" ‹‹ endl;

os_set_error_handler(old_h);

v.pop_back(); // Generates an empty object error.

cout ‹‹ "successful termination" ‹‹ endl;

return 0;

}

incl0.cpp

#include ‹stl.h›

#include ‹iostream.h›

int numbers1[5] = {1, 2, 3, 4, 5};

int numbers2[5] = {1, 2, 4, 8, 16};

int numbers3[2] = {4, 8};

int main() {

if (includes(numbers1, numbers1 + 5, numbers3, numbers3 + 2))

cout ‹‹ "numbers1 includes numbers3" ‹‹ endl;

else cout ‹‹ "numbers1 does not include numbers3" ‹‹ endl;

if (includes(numbers2, numbers2 + 5, numbers3, numbers3 + 2))

cout ‹‹ "numbers2 includes numbers3" ‹‹ endl;

else cout ‹‹ "numbers2 does not include numbers3" ‹‹ endl;

return 0;

}

setdiff2.cpp

#include ‹stl.h›

#include ‹iostream.h›

#include ‹string.h›

char* word1 = "ABCDEFGHIJKLMNO";

char* word2 = "LMNOPQRSTUVWXYZ";

int main() {

ostream_iterator‹char› iter(cout, " ");

cout ‹‹ "word1: ";

copy(word1, word1 + ::strlen(word1), iter);

cout ‹‹ "\nword2: ";

copy(word2, word2 + ::strlen(word2), iter);

cout ‹‹ endl;

set_difference(word1, word1 + ::strlen(word1), word2, word2 + ::strlen(word2), iter, less‹char›());

cout ‹‹ endl;

return 0;

}

setunon2.cpp

#include ‹stl.h›

#include ‹iostream.h›

#include ‹string.h›

char* word1 = "ABCDEFGHIJKLMNO";

char* word2 = "LMNOPQRSTUVWXYZ";

int main() {

ostream_iterator‹char› iter(cout, " ");

cout ‹‹ "word1: ";

copy(word1, word1 + ::strlen(word1), iter);

cout ‹‹ "\nword2: ";

copy(word2, word2 + ::strlen(word2), iter);

cout ‹‹ endl;

set_union(word1, word1 + ::strlen(word1), word2, word2 + ::strlen(word2), iter, less‹char›());

cout ‹‹ endl;

return 0;

}

unique2.cpp

#include ‹stl.h›

#include ‹iostream.h›

#include ‹string.h›

bool str_equal(const char* a_, const char* b_) {

return ::strcmp(a_, b_) == 0 ? 1: 0;

}

char* labels[] = {"Q","Q","W","W","E","E","R","T","T","Y","Y"};

int main() {

const unsigned count = sizeof(labels) / sizeof(labels[0]);

ostream_iterator‹char*› iter(cout);

copy(labels, labels + count, iter);

cout ‹‹ endl;

unique(labels, labels + count, str_equal);

copy(labels, labels + count, iter);

cout ‹‹ endl;

return 0;

}

parsrtc1.cpp

#include ‹stl.h›

#include ‹stdlib.h›

#include ‹iostream.h›

int main() {

vector‹int› v1(10);

for (int i = 0; i ‹ v1.size(); i++) v1[i] = rand() % 10;

vector‹int› result(5);

ostream_iterator‹int› iter(cout, " ");

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

partial_sort_copy(v1.begin(), v1.end(), result.begin(), result.end());

copy(result.begin(), result.end(), iter);

cout ‹‹ endl;

return 0;

}

equal1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

vector‹int› v1(10);

for (int i = 0; i ‹ v1.size(); i++) v1[i] = i;

vector‹int› v2(10);

if (equal(v1.begin(), v1.end(), v2.begin())) cout ‹‹ "v1 is equal to v2" ‹‹ endl;

else cout ‹‹ "v1 is not equal to v2" ‹‹ endl;

copy(v1.begin(), v1.end(), v2.begin());

if (equal(v1.begin(), v1.end(), v2.begin())) cout ‹‹ "v1 is equal to v2" ‹‹ endl;

else cout ‹‹ "v1 is not equal to v2" ‹‹ endl;

return 0;

}

equal0.cpp

#include ‹stl.h›

#include ‹iostream.h›

int numbers1[5] = {1, 2, 3, 4, 5};

int numbers2[5] = {1, 2, 4, 8, 16};

int numbers3[2] = {1, 2};

int main() {

if (equal(numbers1, numbers1 + 5, numbers2))

cout ‹‹ "numbers1 is equal to numbers2" ‹‹ endl;

else cout ‹‹ "numbers1 is not equal to numbers2" ‹‹ endl;

if (equal(numbers3, numbers3 + 2, numbers1))

cout ‹‹ "numbers3 is equal to numbers1" ‹‹ endl;

else cout ‹‹ "numbers3 is not equal to numbers1" ‹‹ endl;

return 0;

}

genern2.cpp

#include ‹stl.h›

#include ‹iostream.h›

#include ‹stdlib.h›

class Fibonacci {

public:

Fibonacci(): v1(0), v2(1) {}

int operator() ();

private:

int v1;

int v2;

};

int Fibonacci::operator() () {

int r = v1 + v2;

v1 = v2;

v2 = r;

return v1;

}

int main() {

vector‹int› v1(10);

Fibonacci generator;

generate_n(v1.begin(), v1.size(), generator);

ostream_iterator‹int› iter(cout, " ");

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

return 0;

}

gener2.cpp

#include ‹stl.h›

#include ‹iostream.h›

#include ‹stdlib.h›

class Fibonacci {

public:

Fibonacci(): v1(0), v2(1) {}

int operator() ();

private:

int v1;

int v2;

};

int Fibonacci::operator() () {

int r = v1 + v2;

v1 = v2;

v2 = r;

return v1;

}

int main() {

vector‹int› v1(10);

Fibonacci generator;

generate(v1.begin(), v1.end(), generator);

ostream_iterator‹int› iter(cout, " ");

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

return 0;

}

repcpif1.cpp

#include ‹stl.h›

#include ‹iostream.h›

bool odd(int a_) {

return a_ % 2;

}

int main() {

vector‹int› v1(10);

for (int i = 0; i ‹ v1.size(); i++) v1[i] = i % 5;

ostream_iterator‹int› iter(cout, " ");

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

vector‹int› v2(v1.size());

replace_copy_if(v1.begin(), v1.end(), v2.begin(), odd, 42);

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

copy(v2.begin(), v2.end(), iter);

cout ‹‹ endl;

return 0;

}

setsymd.cpp

#include ‹stl.h›

#include ‹iostream.h›

int v1[3] = {13, 18, 23};

int v2[4] = {10, 13, 17, 23};

int result[4] = {0, 0, 0, 0};

int main() {

set_symmetric_difference(v1, v1 + 3, v2, v2 + 4, result);

for (int i = 0; i ‹ 4; i++) cout ‹‹ result[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

deque1.cpp

#include ‹iostream.h›

#include ‹stl.h›

int main() {

deque‹int› d;

d.push_back(4); // Add after end.

d.push_back(9);

d.push_back(16);

d.push_front(1); // Insert at beginning.

for (int i = 0; i ‹ d.size(); i++) cout ‹‹ "d[" ‹‹ i ‹‹ "] = " ‹‹ d[i] ‹‹ endl;

cout ‹‹ endl;

d.pop_front(); // Erase first element.

d[2] = 25; // Replace last element.

for (i = 0; i ‹ d.size(); i++)

cout ‹‹ "d[" ‹‹ i ‹‹ "] = " ‹‹ d[i] ‹‹ endl;

return 0;

}

findif1.cpp

#include ‹stl.h›

#include ‹iostream.h›

bool div_3(int a_) {

return a_ % 3 ? 0 : 1;

}

int main() {

typedef vector‹int› IntVec;

IntVec v(10);

for (int i = 0; i ‹ v.size(); i++) v[i] = (i + 1) * (i + 1);

IntVec::iterator iter;

iter = find_if(v.begin(), v.end(), div_3);

if (iter!= v.end())

cout ‹‹ "Value " ‹‹ *iter ‹‹ " at offset " ‹‹ (iter - v.begin()) ‹‹ " is divisible by 3" ‹‹ endl;

return 0;

}

ucompos1.cpp

#include ‹iostream.h›

#include ‹math.h›

#include ‹stl.h›

struct square_root: public unary_function‹double, double› {

square_root() {}

double operator() (double x_) const {return sqrt(x_);}

};

int input[3] = {-1, -4, -16};

int main() {

int output[3];

transform(input, input + 3, output, unary_compose‹square_root, negate‹int› ›(square_root(), negate‹int›()));

for (int i = 0; i ‹ 3; i++) cout ‹‹ output[i] ‹‹ endl;

return 0;

}

rawiter.cpp

#include ‹iostream.h›

#include ‹stl.h›

class X {

public:

X(int i_ = 0): i (i_) {}

operator int() const {return i;}

private:

int i;

};

int main() {

os_heap_allocator‹X› a;

// Allocate (but do not construct) storage for 5 elements.

os_heap_allocator‹X›::pointer p = a.allocate(5);

raw_storage_iterator‹X*, X› r(p);

for (int i = 0; i ‹ 5; i++) *r++ = X(i);

for (i = 0; i ‹ 5; i++) cout ‹‹ *p++ ‹‹ endl;

return 0;

}

set2.cpp

#include ‹iostream.h›

#include ‹stl.h›

int main() {

set‹int, less‹int› › s;

pair‹set‹int, less‹int› ›::const_iterator, bool› p;

p = s.insert(42);

if (p.second) cout ‹‹ "Inserted new element " ‹‹ *(p.first) ‹‹ endl;

else cout ‹‹ "Existing element = " ‹‹ *(p.first) ‹‹ endl;

p = s.insert(42);

if (p.second) cout ‹‹ "Inserted new element " ‹‹ *(p.first) ‹‹ endl;

else cout ‹‹ "Existing element = " ‹‹ *(p.first) ‹‹ endl;

return 0;

}

mset3.cpp

#include ‹iostream.h›

#include ‹stl.h›

int array[] = {3, 6, 1, 2, 3, 2, 6, 7, 9};

int main() {

multiset‹int, less‹int› › s(array, array + 9);

multiset‹int, less‹int› ›::iterator i;

// Return location of first element that is not less than 3

i = s.lower_bound(3);

cout ‹‹ "lower bound = " ‹‹ *i ‹‹ endl;

// Return location of first element that is greater than 3

i = s.upper_bound(3);

cout ‹‹ "upper bound = " ‹‹ *i ‹‹ endl;

return 0;

}

binsrch2.cpp

#include ‹stl.h›

#include ‹iostream.h›

#include ‹string.h›

bool str_compare(const char* a_, const char* b_) {

return ::strcmp(a_, b_) ‹ 0 ? 1 : 0;

}

char* labels[] = {"aa", "dd", "ff", "jj", "ss", "zz"};

int main() {

const unsigned count = sizeof(labels) / sizeof(labels[0]);

if (binary_search(labels, labels + count, "ff", str_compare)) cout ‹‹ "ff is in labels." ‹‹ endl;

else cout ‹‹ "ff is not in labels." ‹‹ endl;

return 0;

}

nthelem2.cpp

#include ‹stl.h›

#include ‹stdlib.h›

#include ‹iostream.h›

int main() {

vector‹int› v1(10);

for (int i = 0; i ‹ v1.size(); i++) v1[i] = rand() % 10;

ostream_iterator‹int› iter(cout, " ");

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

nth_element(v1.begin(), v1.begin() + v1.size() / 2, v1.end(), greater‹int›());

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

return 0;

}

setintr1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

vector‹int› v1(10);

iota(v1.begin(), v1.end(), 0);

vector‹int› v2(10);

iota(v2.begin(), v2.end(), 7);

ostream_iterator ‹int› iter(cout, " ");

cout ‹‹ "v1: ";

copy(v1.begin(), v1.end(), iter);

cout ‹‹ "\nv2: ";

copy(v2.begin(), v2.end(), iter);

cout ‹‹ endl;

set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), iter);

cout ‹‹ endl;

return 0;

}

setdiff1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

vector‹int› v1(10);

iota(v1.begin(), v1.end(), 0);

vector‹int› v2(10);

iota(v2.begin(), v2.end(), 7);

ostream_iterator ‹int› iter(cout, " ");

cout ‹‹ "v1: ";

copy(v1.begin(), v1.end(), iter);

cout ‹‹ "\nv2: ";

copy(v2.begin(), v2.end(), iter);

cout ‹‹ endl;

set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), iter);

cout ‹‹ endl;

return 0;

}

adjdiff2.cpp

#include ‹stl.h›

#include ‹iostream.h›

int mult(int a_, int b_) {

return a_ * b_;

}

int main() {

vector‹int› v(10);

for (int i = 0; i ‹ v.size(); i++) v[i] = i + 1;

vector‹int› rslt(v.size());

adjacent_difference(v.begin(), v.end(), rslt.begin(), mult);

ostream_iterator‹int› iter(cout, " ");

copy(v.begin(), v.end(), iter);

cout ‹‹ endl;

copy(rslt.begin(), rslt.end(), iter);

cout ‹‹ endl;

return 0;

}

rotate1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

vector‹int› v1(10);

iota(v1.begin(), v1.end(), 0);

ostream_iterator‹int› iter(cout, " ");

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

for (int i = 0; i ‹ v1.size(); i++) {

rotate(v1.begin(), v1.begin() + i, v1.end());

ostream_iterator ‹int› iter(cout, " ");

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

}

cout ‹‹ endl;

return 0;

}

setunon1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

vector‹int› v1(10);

iota(v1.begin(), v1.end(), 0);

vector‹int› v2(10);

iota(v2.begin(), v2.end(), 7);

ostream_iterator‹int› iter(cout, " ");

cout ‹‹ "v1: ";

copy(v1.begin(), v1.end(), iter);

cout ‹‹ "\nv2: ";

copy(v2.begin(), v2.end(), iter);

cout ‹‹ endl;

set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), iter);

cout ‹‹ endl;

return 0;

}

insert1.cpp

#include ‹iostream.h›

#include ‹stl.h›

char* array1[] = {"laurie", "jennifer", "leisa"};

char* array2[] = {"amanda", "saskia", "carrie"};

int main() {

deque‹char*› names(array1, array1 + 3);

deque‹char*›::iterator i = names.begin() + 2;

copy(array2, array2 + 3, insert_iterator‹deque ‹char*› ›(names, i));

deque‹char*›::iterator j;

for (j = names.begin(); j!= names.end(); j++) cout ‹‹ *j ‹‹ endl;

return 0;

}

ucompos2.cpp

#include ‹iostream.h›

#include ‹math.h›

#include ‹stl.h›

struct square_root: public unary_function‹double, double› {

square_root() {}

double operator() (double x_) const {return sqrt(x_);}

};

int input[3] = {-1, -4, -16};

int main() {

int output[3];

transform(input, input + 3, output, compose1(square_root(), negate‹int›()));

for (int i = 0; i ‹ 3; i++) cout ‹‹ output[i] ‹‹ endl;

return 0;

}

parsrt1.cpp

#include ‹stl.h›

#include ‹stdlib.h›

#include ‹iostream.h›

int main() {

vector‹int› v1(10);

for (int i = 0; i ‹ v1.size(); i++)

v1[i] = rand() % 10;

ostream_iterator‹int› iter(cout, " ");

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

partial_sort(v1.begin(), v1.begin() + v1.size() / 2, v1.end());

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

return 0;

}

equal2.cpp

#include ‹stl.h›

#include ‹iostream.h›

bool values_squared(int a_, int b_) {

return (a_ * a_ == b_);

}

int main() {

vector‹int› v1(10);

vector‹int› v2(10);

for (int i = 0; i ‹ v1.size(); i++) {

v1[i] = i;

v2[i] = i * i;

}

if (equal(v1.begin(), v1.end(), v2.begin(), values_squared))

cout ‹‹ "v2[i] == v1[i] * v1[i]" ‹‹ endl;

else cout ‹‹ "v2[i] != v1[i] * v1[i]" ‹‹ endl;

return 0;

}

inplmrg2.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

vector‹int› v1(10);

for (int i = 0; i ‹ v1.size(); i++) v1[i] = (v1.size() - i - 1) % 5;

ostream_iterator‹int› iter(cout, " ");

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

inplace_merge(v1.begin(), v1.begin() + 5, v1.end(), greater‹int›());

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

return 0;

}

nthelem1.cpp

#include ‹stl.h›

#include ‹stdlib.h›

#include ‹iostream.h›

int main() {

vector‹int› v1(10);

for (int i = 0; i ‹ v1.size(); i++) v1[i] = rand() % 10;

ostream_iterator‹int› iter(cout, " ");

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

nth_element(v1.begin(), v1.begin() + v1.size() / 2, v1.end());

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

return 0;

}

vec4.cpp

#include ‹iostream.h›

#include ‹stl.h›

int main() {

vector‹int› v(4);

v[0] = 1;

v[1] = 4;

v[2] = 9;

v[3] = 16;

cout ‹‹ "front = " ‹‹ v.front() ‹‹ endl;

cout ‹‹ "back = " ‹‹ v.back() ‹‹ ", size = " ‹‹ v.size() ‹‹ endl;

v.push_back(25);

cout ‹‹ "back = " ‹‹ v.back() ‹‹ ", size = " ‹‹ v.size() ‹‹ endl;

v.pop_back();

cout ‹‹ "back = " ‹‹ v.back() ‹‹ ", size = " ‹‹ v.size() ‹‹ endl;

return 0;

}

lwrbnd2.cpp

#include ‹stl.h›

#include ‹iostream.h›

#include ‹string.h›

bool char_str_less(const char* a_, const char* b_) {

return ::strcmp(a_, b_) ‹ 0 ? 1 : 0;

}

char* str[] = {"a", "a", "b", "b", "q", "w", "z"};

int main() {

const unsigned strCt = sizeof(str)/sizeof(str[0]);

cout ‹‹ "d can be inserted at index: "

‹‹ (lower_bound(str, str + strCt, "d", char_str_less) - str) ‹‹ endl;

return 0;

}

pheap2.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

vector‹int› v;

v.push_back(1);

v.push_back(20);

v.push_back(4);

make_heap(v.begin(), v.end(), greater‹int›());

v.push_back(7);

push_heap(v.begin(), v.end(), greater‹int›());

sort_heap(v.begin(), v.end(), greater‹int›());

ostream_iterator‹int› iter(cout, " ");

copy(v.begin(), v.end(), iter);

cout ‹‹ endl;

return 0;

}

insert2.cpp

#include ‹iostream.h›

#include ‹stl.h›

char* array1[] = {"laurie", "jennifer", "leisa"};

char* array2[] = {"amanda", "saskia", "carrie"};

int main() {

deque‹char*› names(array1, array1 + 3);

deque‹char*›::iterator i = names.begin() + 2;

copy(array2, array2 + 3, inserter(names, i));

deque‹char*›::iterator j;

for (j = names.begin(); j!= names.end(); j++) cout ‹‹ *j ‹‹ endl;

return 0;

}

uprbnd2.cpp

#include ‹stl.h›

#include ‹iostream.h›

#include ‹string.h›

bool char_str_less(const char* a_, const char* b_) {

return ::strcmp(a_, b_) ‹ 0 ? 1 : 0;

}

char* str[] = {"a", "a", "b", "b", "q", "w", "z"};

int main() {

const unsigned strCt = sizeof(str)/sizeof(str[0]);

cout ‹‹ "d can be inserted at index: "

‹‹ upper_bound(str, str + strCt, "d", char_str_less) - str ‹‹ endl;

return 0;

}

vec3.cpp

#include ‹iostream.h›

#include ‹stl.h›

int main() {

vector‹char› v1; // Empty vector of characters.

v1.push_back('h');

v1.push_back('i');

cout ‹‹ "v1 = " ‹‹ v1[0] ‹‹ v1[1] ‹‹ endl;

vector‹char› v2(v1);

v2[1] = 'o'; // Replace second character.

cout ‹‹ "v2 = " ‹‹ v2[0] ‹‹ v2[1] ‹‹ endl;

cout ‹‹ "(v1 == v2) = " ‹‹ (v1 == v2) ‹‹ endl;

cout ‹‹ "(v1 ‹ v2) = " ‹‹ (v1 ‹ v2) ‹‹ endl;

return 0;

}

iter4.cpp

#include ‹iostream.h›

#include ‹stl.h›

int main() {

vector‹int› v; // Empty vector of integers.

v.push_back(1);

v.push_back(2);

v.push_back(3);

// Position immediately after last item.

vector‹int›::iterator i = v.end();

// Move back one and then access.

cout ‹‹ "last element is " ‹‹ *--i ‹‹ endl;

i -= 2; // Jump back two items.

cout ‹‹ "first element is " ‹‹ *i ‹‹ endl;

return 0;

}

setdiff0.cpp

#include ‹stl.h›

#include ‹iostream.h›

int v1[3] = {13, 18, 23};

int v2[4] = {10, 13, 17, 23};

int result[4] = {0, 0, 0, 0};

int main() {

set_difference(v1, v1 + 3, v2, v2 + 4, result);

for (int i = 0; i ‹ 4; i++) cout ‹‹ result[i] ‹‹ ' ';

cout ‹‹ endl;

set_difference(v2, v2 + 4, v1, v1 + 2, result);

for (i = 0; i ‹ 4; i++) cout ‹‹ result[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

lexcmp2.cpp

#include ‹stl.h›

#include ‹iostream.h›

const unsigned size = 6;

char n1[size] = "shoe";

char n2[size] = "shine";

int main() {

bool before = lexicographical_compare(n1, n1 + size, n2, n2 + size, greater‹char›());

if (before) cout ‹‹ n1 ‹‹ " is after " ‹‹ n2 ‹‹ endl;

else cout ‹‹ n2 ‹‹ " is after " ‹‹ n1 ‹‹ endl;

return 0;

}

adjdiff1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

vector‹int› v(10);

for (int i = 0; i ‹ v.size(); i++) v[i] = i * i;

vector‹int› result(v.size());

adjacent_difference(v.begin(), v.end(), result.begin());

ostream_iterator‹int› iter(cout, " ");

copy(v.begin(), v.end(), iter);

cout ‹‹ endl;

copy(result.begin(), result.end(), iter);

cout ‹‹ endl;

return 0;

}

stblptn1.cpp

#include ‹stl.h›

#include ‹stdlib.h›

#include ‹iostream.h›

int main() {

vector‹int› v1(10);

for (int i = 0; i ‹ v1.size(); i++) v1[i] = rand() % 20;

ostream_iterator‹int› iter(cout, " ");

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

stable_partition(v1.begin(), v1.end(), bind2nd(less‹int›(), 11));

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

return 0;

}

ptition1.cpp

#include ‹stl.h›

#include ‹stdlib.h›

#include ‹iostream.h›

int main() {

vector‹int› v1(10);

for (int i = 0; i ‹ v1.size(); i++) v1[i] = rand() % 20;

ostream_iterator ‹int› iter(cout, " ");

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

partition(v1.begin(), v1.end(), bind2nd(less‹int›(), 11));

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

return 0;

}

vec1.cpp

#include ‹iostream.h›

#include ‹stl.h›

int main() {

vector‹int› v1; // Empty vector of integers.

cout ‹‹ "empty = " ‹‹ v1.empty() ‹‹ endl;

cout ‹‹ "size = " ‹‹ v1.size() ‹‹ endl;

cout ‹‹ "max_size = " ‹‹ v1.max_size() ‹‹ endl;

v1.push_back(42); // Add an integer to the vector.

cout ‹‹ "size = " ‹‹ v1.size() ‹‹ endl;

cout ‹‹ "v1[0] = " ‹‹ v1[0] ‹‹ endl;

return 0;

}

sort2.cpp

#include ‹stl.h›

#include ‹iostream.h›

int array[] = {1, 50, -10, 11, 42, 19};

int main() {

int count = sizeof(array) / sizeof(array[0]);

ostream_iterator ‹int› iter(cout, " ");

cout ‹‹ "before: ";

copy(array, array + count, iter);

cout ‹‹ "\nafter: ";

sort(array, array + count, greater‹int›());

copy(array, array + count, iter);

cout ‹‹ endl;

return 0;

}

copy4.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

typedef vector‹int› IVec;

vector‹int› v1(10);

for (int loc = 0; loc ‹ v1.size(); loc++) v1[loc] = loc;

vector‹int› v2;

insert_iterator‹IVec› i (v2, v2.begin());

copy(v1.begin(), v1.end(), i);

ostream_iterator‹int› outiter(cout, " ");

copy(v2.begin(), v2.end(), outIter);

cout ‹‹ endl;

return 0;

}

prevprm2.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

vector‹int› v1(3);

iota(v1.begin(), v1.end(), 0);

ostream_iterator‹int› iter(cout, " ");

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

for (int i = 0; i ‹ 9; i++) {

prev_permutation(v1.begin(), v1.end(), greater‹int›());

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

}

return 0;

}

trnsfrm2.cpp

#include ‹stl.h›

#include ‹iostream.h›

#include ‹string.h›

char map_char(char a_, int b_) {

return char(a_ + b_);

}

int trans[] = {-4, 4, -6, -6, -10, 0, 10, -6, 6, 0, -1, -77};

char n[] = "Larry Mullen";

int main() {

const unsigned count = ::strlen(n);

ostream_iterator ‹char› iter(cout);

transform(n, n + count, trans, iter, map_char);

cout ‹‹ endl;

return 0;

}

iter1.cpp

#include ‹iostream.h›

#include ‹stl.h›

int main() {

vector‹const char*› v; // Vector of character strings.

v.push_back((char*) "zippy"); // First element.

v.push_back((char*) "motorboy"); // Second element.

vector‹const char*›::iterator i = v.begin(); // Position at end.

for (i = v.begin(); i != v.end(); i++) cout ‹‹ *i ‹‹ endl; // Display item.

return 0;

}

maxelem2.cpp

#include ‹stl.h›

#include ‹iostream.h›

#include ‹string.h›

bool str_compare(const char* a_, const char* b_) {

return ::strcmp(a_, b_) ‹ 0 ? 1 : 0;

}

char* names[] = {"Brett", "Graham", "Jack", "Mike", "Todd"};

int main() {

const unsigned namesCt = sizeof(names)/sizeof(names[0]);

cout ‹‹ *max_element(names, names + namesCt, str_compare) ‹‹ endl;

return 0;

}

minelem2.cpp

#include ‹stl.h›

#include ‹iostream.h›

#include ‹string.h›

bool str_compare(const char* a_, const char* b_) {

return ::strcmp(a_, b_) ‹ 0 ? 1 : 0;

}

char* names[] = {"Brett", "Graham", "Jack", "Mike", "Todd"};

int main() {

const unsigned namesCt = sizeof(names)/sizeof(names[0]);

cout ‹‹ *min_element(names, names + namesCt, str_compare) ‹‹ endl;

return 0;

}

partsum2.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

vector‹int› v1(5);

iota(v1.begin(), v1.end(), 1);

vector‹int› v2(v1.size());

partial_sum(v1.begin(), v1.end(), v2.begin(), times‹int›());

ostream_iterator‹int› iter(cout, " ");

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

copy(v2.begin(), v2.end(), iter);

cout ‹‹ endl;

return 0;

}

istmit1.cpp

#include ‹iostream.h›

#include ‹stl.h›

int main() {

char buffer[100];

int i = 0;

cin.unsetf(ios::skipws); // Disable white-space skipping.

cout ‹‹ "Please enter a string: ";

istream_iterator‹char, ptrdiff_t› s(cin);

while (*s!= '\n') buffer[i++] = *s++;

buffer[i] = '\0'; // Null terminate buffer.

cout ‹‹ "read " ‹‹ buffer ‹‹ endl;

return 0;

}

findif0.cpp

#include ‹stl.h›

#include ‹iostream.h›

bool odd(int a_) {

return a_ % 2;

}

int numbers[6] = {2, 4, 8, 15, 32, 64};

int main() {

int* location = find_if(numbers, numbers + 6, odd);

if (location != numbers + 6)

cout ‹‹ "Value " ‹‹ *location ‹‹ " at offset " ‹‹ (location - numbers) ‹‹ " is odd" ‹‹ endl;

return 0;

}

pheap1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

vector‹int› v;

v.push_back(1);

v.push_back(20);

v.push_back(4);

make_heap(v.begin(), v.end());

v.push_back(7);

push_heap(v.begin(), v.end());

sort_heap(v.begin(), v.end());

ostream_iterator‹int› iter(cout, " ");

copy(v.begin(), v.end(), iter);

cout ‹‹ endl;

return 0;

}

stblsrt2.cpp

#include ‹stl.h›

#include ‹iostream.h›

#include ‹string.h›

bool string_less(const char* a_, const char* b_) {

return ::strcmp(a_, b_) ‹ 0 ? 1 : 0;

}

char* letters[6] = {"bb", "aa", "ll", "dd", "qq", "cc"};

int main() {

stable_sort(letters, letters + 6, string_less);

for (int i = 0; i ‹ 6; i++) cout ‹‹ letters[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

nextprm1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

vector‹int› v1(3);

iota(v1.begin(), v1.end(), 0);

ostream_iterator‹int› iter(cout, " ");

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

for (int i = 0; i ‹ 9; i++) {

next_permutation(v1.begin(), v1.end());

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

}

return 0;

}

prevprm1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

vector‹int› v1(3);

iota(v1.begin(), v1.end(), 0);

ostream_iterator‹int› iter(cout, " ");

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

for (int i = 0; i ‹ 9; i++) {

prev_permutation(v1.begin(), v1.end());

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

}

return 0;

}

rndshuf1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

vector‹int› v1(10);

iota(v1.begin(), v1.end(), 0);

ostream_iterator‹int› iter(cout, " ");

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

for (int i = 0; i ‹ 3; i++) {

random_shuffle(v1.begin(), v1.end());

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

}

return 0;

}

ptrbinf1.cpp

#include ‹iostream.h›

#include ‹stl.h›

int sum(int x_, int y_) {

return x_ + y_;

}

int input1[4] = {7, 2, 3, 5};

int input2[4] = {1, 5, 5, 8};

int main() {

int output[4];

transform(input1, input1 + 4, input2, output, pointer_to_binary_function‹int, int, int›(sum));

for (int i = 0; i ‹ 4; i++) cout ‹‹ output[i] ‹‹ endl;

return 0;

}

iter2.cpp

#include ‹iostream.h›

#include ‹stl.h›

void print (const vector‹const char*›& v_) {

vector‹const char*›::const_iterator i;

for (i = v_.begin(); i != v_.end(); i++) cout ‹‹ *i ‹‹ endl;

}

int main() {

vector‹const char*› v; // Vector of character strings.

v.push_back((char*) "zippy");

v.push_back((char*) "motorboy");

print (v);

return 0;

}

partsum1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

vector‹int› v1(10);

iota(v1.begin(), v1.end(), 0);

vector‹int› v2(v1.size());

partial_sum(v1.begin(), v1.end(), v2.begin());

ostream_iterator ‹int› iter(cout, " ");

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

copy(v2.begin(), v2.end(), iter);

cout ‹‹ endl;

return 0;

}

replif1.cpp

#include ‹stl.h›

#include ‹iostream.h›

bool odd(int a_) {

return a_ % 2;

}

int main() {

vector‹int› v1(10);

for (int i = 0; i ‹ v1.size(); i++) {

v1[i] = i % 5;

cout ‹‹ v1[i] ‹‹ ' ';

}

cout ‹‹ endl;

replace_if(v1.begin(), v1.end(), odd, 42);

for (i = 0; i ‹ v1.size(); i++) cout ‹‹ v1[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

mset4.cpp

#include ‹iostream.h›

#include ‹stl.h›

int array[] = {3, 6, 1, 2, 3, 2, 6, 7, 9};

int main() {

typedef multiset‹int, less‹int› › mset;

mset s(array, array + 9);

pair‹mset::const_iterator, mset::const_iterator› p = s.equal_range(3);

cout ‹‹ "lower bound = " ‹‹ *(p.first) ‹‹ endl;

cout ‹‹ "upper bound = " ‹‹ *(p.second) ‹‹ endl;

return 0;

}

iter3.cpp

#include ‹iostream.h›

#include ‹stl.h›

int main() {

vector‹const char*› v; // Vector of character strings.

v.push_back((char*) "zippy"); // First element.

v.push_back((char*) "motorboy"); // Second element.

vector‹const char*›::reverse_iterator i;

for (i = v.rbegin(); i!= v.rend(); i++) cout ‹‹ *i ‹‹ endl; // Display item.

return 0;

}

list2.cpp

#include ‹iostream.h›

#include ‹stl.h›

int array1[] = {1, 16};

int array2[] = {4, 9};

int main() {

list‹int› l1(array1, array1 + 2);

list‹int› l2(array2, array2 + 2);

list‹int›::iterator i = l1.begin();

i++;

l1.splice(i, l2, l2.begin(), l2.end());

i = l1.begin();

while (i != l1.end()) cout ‹‹ *i++ ‹‹ endl;

return 0;

}

set1.cpp

#include ‹iostream.h›

#include ‹stl.h›

int main() {

set‹int, less‹int› › s;

cout ‹‹ "count(42) = " ‹‹ s.count(42) ‹‹ endl;

s.insert(42);

cout ‹‹ "count(42) = " ‹‹ s.count(42) ‹‹ endl;

s.insert(42);

cout ‹‹ "count(42) = " ‹‹ s.count(42) ‹‹ endl;

int count = s.erase(42);

cout ‹‹ count ‹‹ " elements erased" ‹‹ endl;

return 0;

}

list1.cpp

#include ‹iostream.h›

#include ‹stl.h›

int array1[] = {9, 16, 36};

int array2[] = {1, 4};

int main() {

list‹int› l1(array1, array1 + 3);

list‹int› l2(array2, array2 + 2);

list‹int›::iterator i1 = l1.begin();

l1.splice(i1, l2);

list‹int›::iterator i2 = l1.begin();

while (i2!= l1.end()) cout ‹‹ *i2++ ‹‹ endl;

return 0;

}

alg5.cpp

#include ‹iostream.h›

#include ‹stl.h›

int main() {

list‹int› years;

years.push_back(1962);

years.push_back(1992);

years.push_back(2001);

years.push_back(1999);

sort(years.begin(), years.end()); // Causes linker error.

list‹int›::iterator i;

for (i = years.begin(); i != years.end(); i++) cout ‹‹ *i ‹‹ endl;

return 0;

}

eqlrnge0.cpp

#include ‹stl.h›

#include ‹iostream.h›

int numbers[10] = {0, 0, 1, 1, 2, 2, 2, 2, 3, 3};

int main() {

pair ‹int*, int*› range;

range = equal_range(numbers, numbers + 10, 2);

cout ‹‹ "2 can be inserted from before index " ‹‹ (range.first - numbers)

‹‹ " to before index " ‹‹ (range.second - numbers) ‹‹ endl;

return 0;

}

advance.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

typedef vector‹int› IntVector;

IntVector v(10);

for (int i = 0; i ‹ v.size(); i++) v[i] = i;

IntVector::iterator location = v.begin();

cout ‹‹ "At Beginning: " ‹‹ *location ‹‹ endl;

advance(location, 5);

cout ‹‹ "At Beginning + 5: " ‹‹ *location ‹‹ endl;

return 0;

}

replace1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

vector‹int› v1(10);

for (int i = 0; i ‹ v1.size(); i++) v1[i] = i % 5;

ostream_iterator‹int› iter(cout, " ");

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

replace(v1.begin(), v1.end(), 2, 42);

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

return 0;

}

alg3.cpp

#include ‹iostream.h›

#include ‹stl.h›

int main() {

vector‹int› i;

i.push_back(1);

i.push_back(4);

i.push_back(2);

i.push_back(8);

i.push_back(2);

int n = 0; // Must be initialized, as count increments n.

count(i.begin(), i.end(), 2, n);

cout ‹‹ "Count of 2s = " ‹‹ n ‹‹ endl;

return 0;

}

func2.cpp

#include ‹iostream.h›

#include ‹stl.h›

bool bigger_than(int x_, int y_) {

return x_ › y_;

}

int main() {

vector‹int›v;

v.push_back(4);

v.push_back(1);

v.push_back(5);

sort(v.begin(), v.end(), bigger_than);

vector‹int›::iterator i;

for (i = v.begin(); i != v.end(); i++) cout ‹‹ *i ‹‹ endl;

return 0;

}

unegate1.cpp

#include ‹iostream.h›

#include ‹stl.h›

struct odd: public unary_function‹int, bool› {

odd() {}

bool operator() (int n_) const {return (n_ % 2) - 1;}

};

int array[3] = {1, 2, 3};

int main() {

int* p = find_if(array, array + 3, unary_negate‹odd›(odd()));

if (p != array + 3)

cout ‹‹ *p ‹‹ endl;

return 0;

}

alg4.cpp

#include ‹iostream.h›

#include ‹stl.h›

int main() {

vector‹int› years;

years.push_back(1962);

years.push_back(1992);

years.push_back(2001);

years.push_back(1999);

sort(years.begin(), years.end());

vector‹int›::iterator i;

for (i = years.begin(); i!= years.end(); i++)

cout ‹‹ *i ‹‹ endl;

return 0;

}

countif1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int odd(int a_) {

return a_ % 2;

}

int main() {

vector‹int› numbers(100);

for (int i = 0; i ‹ 100; i++) numbers[i] = i % 3;

int elements = 0;

count_if(numbers.begin(), numbers.end(), odd, elements);

cout ‹‹ "Found " ‹‹ elements ‹‹ " odd elements." ‹‹ endl;

return 0;

}

lwrbnd1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

vector‹int› v1(20);

for (int i = 0; i ‹ v1.size(); i++) {

v1[i] = i/4;

cout ‹‹ v1[i] ‹‹ ' ';

}

int* location = lower_bound(v1.begin(), v1.end(), 3);

cout ‹‹ "\n3 can be inserted at index: " ‹‹ (location - v1.begin()) ‹‹ endl;

return 0;

}

lexcmp1.cpp

#include ‹stl.h›

#include ‹iostream.h›

const unsigned size = 6;

char n1[size] = "shoe";

char n2[size] = "shine";

int main() {

bool before = lexicographical_compare(n1, n1 + size, n2, n2 + size);

if (before) cout ‹‹ n1 ‹‹ " is before " ‹‹ n2 ‹‹ endl;

else cout ‹‹ n2 ‹‹ " is before " ‹‹ n1 ‹‹ endl;

return 0;

}

copyb.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

vector‹int› v1(10);

for (int i = 0; i ‹ v1.size(); i++) v1[i] = i;

vector‹int› v2(v1.size());

copy_backward(v1.begin(), v1.end(), v2.end());

ostream_iterator‹int› iter(cout, " ");

copy(v2.begin(), v2.end(), iter);

cout ‹‹ endl;

return 0;

}

ptrbinf2.cpp

#include ‹iostream.h›

#include ‹stl.h›

int sum(int x_, int y_) {

return x_ + y_;

}

int input1[4] = {7, 2, 3, 5};

int input2[4] = {1, 5, 5, 8};

int main() {

int output[4];

transform(input1, input1 + 4, input2, output, ptr_fun(sum));

for (int i = 0; i ‹ 4; i++) cout ‹‹ output[i] ‹‹ endl;

return 0;

}

copyb0.cpp

#include ‹stl.h›

#include ‹iostream.h›

int numbers[5] = {1, 2, 3, 4, 5};

int main() {

int result[5];

copy_backward(numbers, numbers + 5, result + 5);

for (int i = 0; i ‹ 5; i++) cout ‹‹ numbers[i] ‹‹ ' ';

cout ‹‹ endl;

for (i = 0; i ‹ 5; i++) cout ‹‹ result[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

binsert1.cpp

#include ‹iostream.h›

#include ‹stl.h›

char* array[] = {"laurie", "jennifer", "leisa"};

int main() {

vector‹char*› names;

copy(array, array + 3, back_insert_iterator‹vector‹char*› ›(names));

vector‹char*›::iterator i;

for (i = names.begin(); i!= names.end(); i++) cout ‹‹ *i ‹‹ endl;

return 0;

}

unegate2.cpp

#include ‹iostream.h›

#include ‹stl.h›

struct odd: public unary_function‹int, bool› {

odd() {}

bool operator() (int n_) const {return (n_ % 2) - 1;}

};

int array[3] = {1, 2, 3};

int main() {

int* p = find_if(array, array + 3, not1 (odd()));

if (p != array + 3) cout ‹‹ *p ‹‹ endl;

return 0;

}

revcopy1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int numbers[6] = {0, 1, 2, 3, 4, 5};

int main() {

int result[6];

reverse_copy(numbers, numbers + 6, result);

for (int i = 0; i ‹ 6; i++) cout ‹‹ numbers[i] ‹‹ ' ';

cout ‹‹ endl;

for (i = 0; i ‹ 6; i++) cout ‹‹ result[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

finsert1.cpp

#include ‹iostream.h›

#include ‹stl.h›

char* array[] = {"laurie", "jennifer", "leisa"};

int main() {

deque‹char*› names;

copy(array, array + 3, front_insert_iterator‹deque ‹char*› ›(names));

deque‹char*›::iterator i;

for (i = names.begin(); i!= names.end(); i++) cout ‹‹ *i ‹‹ endl;

return 0;

}

remcpif1.cpp

#include ‹stl.h›

#include ‹iostream.h›

bool odd(int a_) {

return a_ % 2;

}

int numbers[6] = {1, 2, 3, 1, 2, 3};

int result[6] = {0, 0, 0, 0, 0, 0};

int main() {

remove_copy_if(numbers, numbers + 6, result, odd);

for (int i = 0; i ‹ 6; i++) cout ‹‹ result[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

inplmrg1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int numbers[6] = {1, 10, 42, 3, 16, 32};

int main() {

for (int i = 0; i ‹ 6; i++) cout ‹‹ numbers[i] ‹‹ ' ';

cout ‹‹ endl;

inplace_merge(numbers, numbers + 3, numbers + 6);

for (i = 0; i ‹ 6; i++) cout ‹‹ numbers[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

list4.cpp

#include ‹iostream.h›

#include ‹stl.h›

int array1[] = {1, 3, 6, 7};

int array2[] = {2, 4};

int main() {

list‹int› l1(array1, array1 + 4);

list‹int› l2(array2, array2 + 2);

l1.merge(l2);

for (list‹int›::iterator i = l1.begin(); i != l1.end(); i++) cout ‹‹ *i;

cout ‹‹ endl;

return 0;

}

revbit1.cpp

#include ‹iostream.h›

#include ‹stl.h›

int array[] = {1, 5, 2, 3};

int main() {

list‹int› v(array, array + 4);

reverse_bidirectional_iterator‹list‹int›::iterator, int, list‹int›::reference, list‹int›::difference_type› r(v.end());

while (r != v.begin())

cout ‹‹ *r++ ‹‹ endl;

return 0;

}

copy3.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

vector‹int› v1(10);

for (int i = 0; i ‹ v1.size(); i++) v1[i] = i;

vector‹int› v2(10);

copy(v1.begin(), v1.end(), v2.begin());

ostream_iterator‹int› iter(cout, " ");

copy(v2.begin(), v2.end(), iter);

cout ‹‹ endl;

return 0;

}

merge0.cpp

#include ‹stl.h›

#include ‹iostream.h›

int numbers1[5] = {1, 6, 13, 25, 101};

int numbers2[5] = {-5, 26, 36, 46, 99};

int main() {

int result[10];

merge(numbers1, numbers1 + 5, numbers2, numbers2 + 5, result);

for (int i = 0; i ‹ 10; i++) cout ‹‹ result[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

reviter1.cpp

#include ‹iostream.h›

#include ‹stl.h›

int array[] = {1, 5, 2, 3};

int main() {

vector‹int› v(array, array + 4);

stl_reverse_iterator‹vector‹int›::iterator, int, vector‹int›::reference, vector‹int›::difference_type› r (v.end());

while (r!= v.begin()) cout ‹‹ *r++ ‹‹ endl;

return 0;

}

find1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int years[] = {1942, 1952, 1962, 1972, 1982, 1992};

int main() {

const unsigned yearCount = sizeof(years) / sizeof(years[0]);

int* location = find(years, years + yearCount, 1972);

cout ‹‹ "Found 1972 at offset " ‹‹ (location - years) ‹‹ endl;

return 0;

}

trnsfrm1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int negate_int(int a_) {

return -a_;

}

int numbers[6] = {-5, -1, 0, 1, 6, 11};

int main() {

int result[6];

transform(numbers, numbers + 6, result, negate_int);

for (int i = 0; i ‹ 6; i++) cout ‹‹ result[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

binsert2.cpp

#include ‹iostream.h›

#include ‹stl.h›

char* array[] = {"laurie", "jennifer", "leisa"};

int main() {

vector‹char*› names;

copy(array, array + 3, back_inserter(names));

vector‹char*›::iterator i;

for (i = names.begin(); i!= names.end(); i++) cout ‹‹ *i ‹‹ endl;

return 0;

}

finsert2.cpp

#include ‹iostream.h›

#include ‹stl.h›

char* array[] = {"laurie", "jennifer", "leisa"};

int main() {

deque‹char*› names;

copy(array, array + 3, front_inserter(names));

deque‹char*›::iterator i;

for (i = names.begin(); i!= names.end(); i++) cout ‹‹ *i ‹‹ endl;

return 0;

}

mset2.cpp

#include ‹iostream.h›

#include ‹stl.h›

char* names[] = {"dave", "alf", "chas", "bob", "ed", "chas"};

int main() {

typedef multiset‹char*, less_s› mset;

mset s;

s.insert(names, names + 6);

for (mset::iterator i = s.begin(); i!= s.end(); i++) cout ‹‹ *i ‹‹ endl;

return 0;

}

ostmit.cpp

#include ‹iostream.h›

#include ‹stl.h›

int array[] = {1, 5, 2, 4};

int main() {

char* string = "hello";

ostream_iterator‹char› it1(cout);

copy(string, string + 5, it1);

cout ‹‹ endl;

ostream_iterator‹int› it2(cout);

copy(array, array + 4, it2);

cout ‹‹ endl;

return 0;

}

ptrunf1.cpp

#include ‹iostream.h›

#include ‹stl.h›

bool even(int n_) {

return (n_ % 2) == 0;

}

int array[3] = {1, 2, 3};

int main() {

int* p = find_if(array, array + 3, pointer_to_unary_function‹int, bool›(even));

if (p != array + 3) cout ‹‹ *p ‹‹ " is even" ‹‹ endl;

return 0;

}

func1.cpp

#include ‹iostream.h›

#include ‹stl.h›

bool bigger(int i_) {

return i_ › 3;

}

int main() {

vector‹int› v;

v.push_back(4);

v.push_back(1);

v.push_back(5);

int n = 0;

count_if(v.begin(), v.end(), bigger, n);

cout ‹‹ "Number greater than 3 = " ‹‹ n ‹‹ endl;

return 0;

}

stblptn0.cpp

#include ‹stl.h›

#include ‹iostream.h›

bool less_10(int a_) {

return a_ ‹ 10 ? 1 : 0;

}

int numbers[6] = {10, 5, 11, 20, 6, -2};

int main() {

stable_partition(numbers, numbers + 6, less_10);

for (int i = 0; i ‹ 6; i++) cout ‹‹ numbers[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

setunon0.cpp

#include ‹stl.h›

#include ‹iostream.h›

int v1[3] = {13, 18, 23};

int v2[4] = {10, 13, 17, 23};

int result[7] = {0, 0, 0, 0, 0, 0, 0};

int main() {

set_union(v1, v1 + 3, v2, v2 + 4, result);

for (int i = 0; i ‹ 7; i++) cout ‹‹ result[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

mkheap1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int numbers[6] = {5, 10, 4, 13, 11, 19};

int main() {

make_heap(numbers, numbers + 6, greater‹int›());

for (int i = 6; i ›= 1; i--) {

cout ‹‹ numbers[0] ‹‹ endl;

pop_heap(numbers, numbers + i, greater‹int›());

}

return 0;

}

setintr0.cpp

#include ‹stl.h›

#include ‹iostream.h›

int v1[3] = {13, 18, 23};

int v2[4] = {10, 13, 17, 23};

int result[4] = {0, 0, 0, 0};

int main() {

set_intersection(v1, v1 + 3, v2, v2 + 4, result);

for (int i = 0; i ‹ 4; i++) cout ‹‹ result[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

logicand.cpp

#include ‹iostream.h›

#include ‹stl.h›

bool input1[4] = {1, 1, 0, 1};

bool input2[4] = {0, 1, 0, 0};

int main() {

int output[4];

transform(input1, input1 + 4, input2, output, logical_and‹bool›());

for (int i = 0; i ‹ 4; i++) cout ‹‹ output[i] ‹‹ endl;

return 0;

}

logicor.cpp

#include ‹iostream.h›

#include ‹stl.h›

bool input1[4] = {1, 1, 0, 1};

bool input2[4] = {0, 1, 0, 0};

int main() {

int output[4];

transform(input1, input1 + 4, input2, output, logical_or‹bool›());

for (int i = 0; i ‹ 4; i++) cout ‹‹ output[i] ‹‹ endl;

return 0;

}

nequal.cpp

#include ‹iostream.h›

#include ‹stl.h›

int input1[4] = {1, 7, 2, 2};

int input2[4] = {1, 6, 2, 3};

int main() {

int output[4];

transform(input1, input1 + 4, input2, output, not_equal_to‹int›());

for (int i = 0; i ‹ 4; i++) cout ‹‹ output[i] ‹‹ endl;

return 0;

}

ptition0.cpp

#include ‹stl.h›

#include ‹iostream.h›

int less_10(int a_) {

return a_ ‹ 10 ? 1 : 0;

}

int numbers[6] = {6, 12, 3, 10, 1, 20};

int main() {

partition(numbers, numbers + 6, less_10);

for (int i = 0; i ‹ 6; i++) cout ‹‹ numbers[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

inrprod0.cpp

#include ‹stl.h›

#include ‹iostream.h›

#include ‹string.h›

int vector1[5] = {1, 2, 3, 4, 5};

int vector2[5] = {1, 2, 3, 4, 5};

int main() {

int result;

result = inner_product(vector1, vector1 + 5, vector2, 0);

cout ‹‹ "Inner product = " ‹‹ result ‹‹ endl;

return 0;

}

func3.cpp

#include ‹iostream.h›

#include ‹stl.h›

int main() {

vector‹int›v;

v.push_back(4);

v.push_back(1);

v.push_back(5);

sort(v.begin(), v.end(), greater‹int›());

vector‹int›::iterator i;

for (i = v.begin(); i != v.end(); i++) cout ‹‹ *i ‹‹ endl;

return 0;

}

modulus.cpp

#include ‹iostream.h›

#include ‹stl.h›

int input1[4] = {6, 8, 10, 2};

int input2[4] = {4, 2, 11, 3};

int main() {

int output[4];

transform(input1, input1 + 4, input2, output, modulus‹int›());

for (int i = 0; i ‹ 4; i++) cout ‹‹ output[i] ‹‹ endl;

return 0;

}

uprbnd1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

int array[20];

for (int i = 0; i ‹ 20; i++) {

array[i] = i/4;

cout ‹‹ array[i] ‹‹ ' ';

}

cout ‹‹ "\n3 can be inserted at index: "

‹‹ upper_bound(array, array + 20, 3) - array ‹‹ endl;

return 0;

}

equalto.cpp

#include ‹iostream.h›

#include ‹stl.h›

int input1[4] = {1, 7, 2, 2};

int input2[4] = {1, 6, 2, 3};

int main() {

int output[4];

transform(input1, input1 + 4, input2, output, equal_to‹int›());

for (int i = 0; i ‹ 4; i++) cout ‹‹ output[i] ‹‹ endl;

return 0;

}

count1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

vector‹int› numbers(100);

for (int i = 0; i ‹ 100; i++) numbers[i] = i % 3;

int elements = 0;

count(numbers.begin(), numbers.end(), 2, elements);

cout ‹‹ "Found " ‹‹ elements ‹‹ " 2's." ‹‹ endl;

return 0;

}

uniqcpy1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int numbers[8] = {0, 1, 1, 2, 2, 2, 3, 4};

int result[8] = {0, 0, 0, 0, 0, 0, 0, 0};

int main() {

unique_copy(numbers, numbers + 8, result);

for (int i = 0; i ‹ 8; i++) cout ‹‹ result[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

minus.cpp

#include ‹iostream.h›

#include ‹stl.h›

int input1[4] = {1, 5, 7, 8};

int input2[4] = {1, 4, 8, 3};

int main() {

int output[4];

transform(input1, input1 + 4, input2, output, minus‹int›());

for (int i = 0; i ‹ 4; i++) cout ‹‹ output[i] ‹‹ endl;

return 0;

}

replcpy1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int numbers[6] = {0, 1, 2, 0, 1, 2};

int result[6] = {0, 0, 0, 0, 0, 0};

int main() {

replace_copy(numbers, numbers + 6, result, 2, 42);

for (int i = 0; i ‹ 6; i++) cout ‹‹ result[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

swprnge1.cpp

#include ‹stl.h›

#include ‹iostream.h›

#include ‹string.h›

int main() {

char* word1 = "World";

char* word2 = "Hello";

cout ‹‹ word1 ‹‹ " " ‹‹ word2 ‹‹ endl;

swap_ranges(word1, word1 + ::strlen(word1), word2);

cout ‹‹ word1 ‹‹ " " ‹‹ word2 ‹‹ endl;

return 0;

}

vec8.cpp

#include ‹iostream.h›

#include ‹stl.h›

int main() {

vector‹int› v;

cout ‹‹ "capacity = " ‹‹ v.capacity() ‹‹ endl;

v.push_back(42);

cout ‹‹ "capacity = " ‹‹ v.capacity() ‹‹ endl;

v.reserve (5000);

cout ‹‹ "capacity = " ‹‹ v.capacity() ‹‹ endl;

return 0;

}

plus.cpp

#include ‹iostream.h›

#include ‹stl.h›

int input1[4] = {1, 6, 11, 8};

int input2[4] = {1, 5, 2, 3};

int main() {

int total = inner_product(input1, input1 + 4, input2, 0, plus‹int›(), times‹int›());

cout ‹‹ "total = " ‹‹ total ‹‹ endl;

return 0;

}

remcopy1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int numbers[6] = {1, 2, 3, 1, 2, 3};

int result[6] = {0, 0, 0, 0, 0, 0};

int main() {

remove_copy(numbers, numbers + 6, result, 2);

for (int i = 0; i ‹ 6; i++) cout ‹‹ result[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

error2.cpp

#include ‹stl.h›

// Compile this code with the symbol OS_USE_EXCEPTIONS defined.

int main() {

vector‹int› v;

try {

v.pop_back(); // Generates an exception.

} catch (const char* str) {

cout ‹‹ "Caught exception " ‹‹ str ‹‹ endl;

}

return 0;

}

iterswp1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

vector‹int› v1(6);

iota(v1.begin(), v1.end(), 0);

iter_swap(v1.begin(), v1.begin() + 3);

ostream_iterator‹int› iter(cout, " ");

copy(v1.begin(), v1.end(), iter);

cout ‹‹ endl;

return 0;

}

remif1.cpp

#include ‹stl.h›

#include ‹iostream.h›

bool odd(int a_) {

return a_ % 2;

}

int numbers[6] = {0, 0, 1, 1, 2, 2};

int main() {

remove_if(numbers, numbers + 6, odd);

for (int i = 0; i ‹ 6; i++)

cout ‹‹ numbers[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

foreach1.cpp

#include ‹stl.h›

#include ‹iostream.h›

void print_sqr(int a_) {

cout ‹‹ a_ * a_ ‹‹ " ";

}

int main() {

vector‹int› v1(10);

for (int i = 0; i ‹ v1.size(); i++) v1[i] = i;

for_each(v1.begin(), v1.end(), print_sqr);

cout ‹‹ endl;

return 0;

}

parsrtc0.cpp

#include ‹stl.h›

#include ‹iostream.h›

int numbers[6] = {5, 2, 4, 3, 1, 6};

int main() {

int result[3];

partial_sort_copy(numbers, numbers + 6, result, result + 3);

for (int i = 0; i ‹ 3; i++) cout ‹‹ result[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

pqueue2.cpp

#include ‹iostream.h›

#include ‹stl.h›

int main() {

priority_queue‹deque‹char*›, greater_s› q;

q.push((char*) "cat");

q.push((char*) "dog");

q.push((char*) "ape");

while (!q.empty()) {

cout ‹‹ q.top() ‹‹ endl;

q.pop();

}

return 0;

}

binsrch1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

int vector[100];

for (int i = 0; i ‹ 100; i++) vector[i] = i;

if (binary_search(vector, vector + 100, 42)) cout ‹‹ "found 42" ‹‹ endl;

else cout ‹‹ "did not find 42" ‹‹ endl;

return 0;

}

ptrunf2.cpp

#include ‹iostream.h›

#include ‹stl.h›

bool even(int n_) {

return (n_ % 2) == 0;

}

int array[3] = {1, 2, 3};

int main() {

int* p = find_if(array, array + 3, ptr_fun(even));

if (p != array + 3) cout ‹‹ *p ‹‹ " is even" ‹‹ endl;

return 0;

}

rotcopy0.cpp

#include ‹stl.h›

#include ‹iostream.h›

int numbers[6] = {0, 1, 2, 3, 4, 5};

int main() {

int result[6];

rotate_copy(numbers, numbers + 3, numbers + 6, result);

for (int i = 0; i ‹ 6; i++) cout ‹‹ result[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

mkheap0.cpp

#include ‹stl.h›

#include ‹iostream.h›

int numbers[6] = {5, 10, 4, 13, 11, 19};

int main() {

make_heap(numbers, numbers + 6);

for (int i = 6; i ›= 1; i--) {

cout ‹‹ numbers[0] ‹‹ endl;

pop_heap(numbers, numbers + i);

}

return 0;

}

copy1.cpp

#include ‹stl.h›

#include ‹iostream.h›

#include ‹string.h›

char string[23] = "A string to be copied.";

int main() {

char result[23];

copy(string, string + 23, result);

cout ‹‹ " Src: " ‹‹ string ‹‹ "\nDest: " ‹‹ result ‹‹ endl;

return 0;

}

find0.cpp

#include ‹stl.h›

#include ‹iostream.h›

int numbers[10] = {0, 1, 4, 9, 16, 25, 36, 49, 64};

int main() {

int* location;

location = find(numbers, numbers + 10, 25);

cout ‹‹ "Found 25 at offset " ‹‹ (location - numbers) ‹‹ endl;

return 0;

}

partsum0.cpp

#include ‹stl.h›

#include ‹iostream.h›

int numbers[6] = {1, 2, 3, 4, 5, 6};

int main() {

int result[6];

partial_sum(numbers, numbers + 6, result);

for (int i = 0; i ‹ 6; i ++) cout ‹‹ result[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

bvec1.cpp

#include ‹iostream.h›

#include ‹stl.h›

int main() {

bit_vector b(3);

for (int i = 0; i ‹ b.size(); i++) cout ‹‹ b[i];

cout ‹‹ endl;

b[0] = b[2] = 1;

for (i = 0; i ‹ b.size(); i++) cout ‹‹ b[i];

cout ‹‹ endl;

return 0;

}

bind2nd1.cpp

#include ‹iostream.h›

#include ‹stl.h›

int array[3] = {1, 2, 3};

int main() {

replace_if(array, array + 3, binder2nd‹greater‹int› ›(greater‹int›(), 2), 4);

for (int i = 0; i ‹ 3; i++) cout ‹‹ array[i] ‹‹ endl;

return 0;

}

bind1st1.cpp

#include ‹iostream.h›

#include ‹stl.h›

int array[3] = {1, 2, 3};

int main() {

int* p = remove_if(array, array + 3, binder1st‹less‹int› ›(less‹int›(), 2));

for (int* i = array; i != p; i++) cout ‹‹ *i ‹‹ endl;

return 0;

}

reviter2.cpp

#include ‹iostream.h›

#include ‹stl.h›

int array[] = {1, 5, 2, 3};

int main() {

vector‹int› v(array, array + 4);

vector‹int›::reverse_iterator r;

for (r = v.rbegin(); r != v.rend(); r++) cout ‹‹ *r ‹‹ endl;

return 0;

}

copy2.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

vector‹int› v(10);

for (int i = 0; i ‹ v.size(); i++) v[i] = i;

ostream_iterator‹int› iter(cout, " ");

copy(v.begin(), v.end(), iter);

cout ‹‹ endl;

return 0;

}

max2.cpp

#include ‹stl.h›

#include ‹iostream.h›

#include ‹string.h›

bool str_compare(const char* a_, const char* b_) {

return ::strcmp(a_, b_) ‹ 0 ? 1 : 0;

}

int main() {

cout ‹‹ max("shoe", "shine", str_compare) ‹‹ endl;

return 0;

}

min2.cpp

#include ‹stl.h›

#include ‹iostream.h›

#include ‹string.h›

bool str_compare(const char* a_, const char* b_) {

return ::strcmp(a_, b_) ‹ 0 ? 1 : 0;

}

int main() {

cout ‹‹ min("shoe", "shine", str_compare) ‹‹ endl;

return 0;

}

parsrt0.cpp

#include ‹stl.h›

#include ‹iostream.h›

int numbers[6] = {5, 2, 4, 3, 1, 6};

int main() {

partial_sort(numbers, numbers + 3, numbers + 6);

for (int i = 0; i ‹ 6; i++) cout ‹‹ numbers[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

partsrt0.cpp

#include ‹stl.h›

#include ‹iostream.h›

int numbers[6] = {5, 2, 4, 3, 1, 6};

int main() {

partial_sort(numbers, numbers + 3, numbers + 6);

for (int i = 0; i ‹ 6; i++) cout ‹‹ numbers[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

bnegate1.cpp

#include ‹iostream.h›

#include ‹stl.h›

int array[4] = {4, 9, 7, 1};

int main() {

sort(array, array + 4, binary_negate‹greater‹int› ›(greater‹int›()));

for (int i = 0; i ‹ 4; i++) cout ‹‹ array[i] ‹‹ endl;

return 0;

}

nthelem0.cpp

#include ‹stl.h›

#include ‹iostream.h›

int numbers[6] = {5, 2, 4, 1, 0, 3};

int main() {

nth_element(numbers, numbers + 3, numbers + 6);

for (int i = 0; i ‹ 6; i++) cout ‹‹ numbers[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

revbit2.cpp

#include ‹iostream.h›

#include ‹stl.h›

int array[] = {1, 5, 2, 3};

int main() {

list‹int› v(array, array + 4);

list‹int›::reverse_iterator r;

for (r = v.rbegin(); r != v.rend(); r++) cout ‹‹ *r ‹‹ endl;

return 0;

}

count0.cpp

#include ‹stl.h›

#include ‹iostream.h›

int numbers[10] = {1, 2, 4, 1, 2, 4, 1, 2, 4, 1};

int main() {

int result = 0;

count(numbers, numbers + 10, 1, result);

cout ‹‹ "Found " ‹‹ result ‹‹ " 1's." ‹‹ endl;

return 0;

}

negate.cpp

#include ‹iostream.h›

#include ‹stl.h›

int input[3] = {1, 2, 3};

int main() {

int output[3];

transform(input, input + 3, output, negate‹int›());

for (int i = 0; i ‹ 3; i++) cout ‹‹ output[i] ‹‹ endl;

return 0;

}

pqueue1.cpp

#include ‹iostream.h›

#include ‹stl.h›

int main() {

priority_queue‹deque‹int›, less‹int› › q;

q.push(42);

q.push(101);

q.push(69);

while (!q.empty()) {

cout ‹‹ q.top() ‹‹ endl;

q.pop();

}

return 0;

}

genern1.cpp

#include ‹stl.h›

#include ‹iostream.h›

#include ‹stdlib.h›

int main() {

vector‹int› v1(10);

generate_n(v1.begin(), v1.size(), rand);

for (int i = 0; i ‹ 10; i++) cout ‹‹ v1[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

rotate0.cpp

#include ‹stl.h›

#include ‹iostream.h›

int numbers[6] = {0, 1, 2, 3, 4, 5};

int main() {

rotate(numbers, numbers + 3, numbers + 6);

for (int i = 0; i ‹ 6; i++) cout ‹‹ numbers[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

foreach0.cpp

#include ‹stl.h›

#include ‹iostream.h›

void print(int a_) {

cout ‹‹ a_ ‹‹ ' ';

}

int numbers[10] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55};

int main() {

for_each(numbers, numbers + 10, print);

cout ‹‹ endl;

return 0;

}

alg2.cpp

#include ‹iostream.h›

#include ‹stl.h›

int i[] = {1, 4, 2, 8, 2, 2};

int main() {

int n = 0; // Must be initialized, as count increments n.

count(i, i + 6, 2, n);

cout ‹‹ "Count of 2s = " ‹‹ n ‹‹ endl;

return 0;

}

gener1.cpp

#include ‹stl.h›

#include ‹iostream.h›

#include ‹stdlib.h›

int main() {

int numbers[10];

generate(numbers, numbers + 10, rand);

for (int i = 0; i ‹ 10; i++) cout ‹‹ numbers[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

replace0.cpp

#include ‹stl.h›

#include ‹iostream.h›

int numbers[6] = {0, 1, 2, 0, 1, 2};

int main() {

replace(numbers, numbers + 6, 2, 42);

for (int i = 0; i ‹ 6; i++) cout ‹‹ numbers[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

rndshuf0.cpp

#include ‹stl.h›

#include ‹iostream.h›

int numbers[6] = {1, 2, 3, 4, 5, 6};

int main() {

random_shuffle(numbers, numbers + 6);

for (int i = 0; i ‹ 6; i++) cout ‹‹ numbers[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

bind1st2.cpp

#include ‹iostream.h›

#include ‹stl.h›

int array[3] = {1, 2, 3};

int main() {

int* p = remove_if(array, array + 3, bind1st(less‹int›(), 2));

for (int* i = array; i != p; i++) cout ‹‹ *i ‹‹ endl;

return 0;

}

unique1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int numbers[8] = {0, 1, 1, 2, 2, 2, 3, 4};

int main() {

unique(numbers, numbers + 8);

for (int i = 0; i ‹ 8; i ++) cout ‹‹ numbers[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

bind2nd2.cpp

#include ‹iostream.h›

#include ‹stl.h›

int array[3] = {1, 2, 3};

int main() {

replace_if(array, array + 3, bind2nd(greater‹int (), 2), 4);

for (int i = 0; i ‹ 3; i++) cout ‹‹ array[i] ‹‹ endl;

return 0;

}

vec5.cpp

#include ‹iostream.h›

#include ‹stl.h›

int array[] = {1, 4, 9, 16};

int main() {

vector‹int› v(array, array + 4);

for (int i = 0; i ‹ v.size(); i++) cout ‹‹ "v[" ‹‹ i ‹‹ "] = " ‹‹ v[i] ‹‹ endl;

return 0;

}

iterswp0.cpp

#include ‹stl.h›

#include ‹iostream.h›

int numbers[6] = {0, 1, 2, 3, 4, 5};

int main() {

iter_swap(numbers, numbers + 3);

for (int i = 0; i ‹ 6; i++) cout ‹‹ numbers[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

remove1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int numbers[6] = {1, 2, 3, 1, 2, 3};

int main() {

remove(numbers, numbers + 6, 1);

for (int i = 0; i ‹ 6; i++) cout ‹‹ numbers[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

stblsrt1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int array[6] = {1, 50, -10, 11, 42, 19};

int main() {

stable_sort(array, array + 6);

for (int i = 0; i ‹ 6; i++) cout ‹‹ array[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

reverse1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int numbers[6] = {0, 1, 2, 3, 4, 5};

int main() {

reverse(numbers, numbers + 6);

for (int i = 0; i ‹ 6; i++) cout ‹‹ numbers[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

logicnot.cpp

#include ‹iostream.h›

#include ‹stl.h›

bool input[7] = {1, 0, 0, 1, 1, 1, 1};

int main() {

int n = 0;

count_if(input, input + 7, logical_not‹bool›(), n);

cout ‹‹ "count = " ‹‹ n ‹‹ endl;

return 0;

}

bnegate2.cpp

#include ‹iostream.h›

#include ‹stl.h›

int array[4] = {4, 9, 7, 1};

int main() {

sort(array, array + 4, not2(greater‹int›()));

for (int i = 0; i ‹ 4; i++) cout ‹‹ array[i] ‹‹ endl;

return 0;

}

queue1.cpp

#include ‹iostream.h›

#include ‹stl.h›

int main() {

queue‹list‹int› › q;

q.push(42);

q.push(101);

q.push(69);

while (!q.empty()) {

cout ‹‹ q.front() ‹‹ endl;

q.pop();

}

return 0;

}

stack1.cpp

#include ‹iostream.h›

#include ‹stl.h›

int main() {

stack‹deque‹int› › s;

s.push(42);

s.push(101);

s.push(69);

while (!s.empty()) {

cout ‹‹ s.top() ‹‹ endl;

s.pop();

}

return 0;

}

greateq.cpp

#include ‹iostream.h›

#include ‹stl.h›

int array[4] = {3, 1, 4, 2};

int main() {

sort(array, array + 4, greater_equal‹int›());

for (int i = 0; i ‹ 4; i++) cout ‹‹ array[i] ‹‹ endl;

return 0;

}

stack2.cpp

#include ‹iostream.h›

#include ‹stl.h›

int main() {

stack‹list‹int› › s;

s.push(42);

s.push(101);

s.push(69);

while (!s.empty()) {

cout ‹‹ s.top() ‹‹ endl;

s.pop();

}

return 0;

}

lesseq.cpp

#include ‹iostream.h›

#include ‹stl.h›

int array[4] = {3, 1, 4, 2};

int main() {

sort(array, array + 4, less_equal‹int›());

for (int i = 0; i ‹ 4; i++) cout ‹‹ array[i] ‹‹ endl;

return 0;

}

divides.cpp

#include ‹iostream.h›

#include ‹stl.h›

int input[3] = {2, 3, 4};

int main() {

int result = accumulate(input, input + 3, 48, divides‹int›());

cout ‹‹ "result = " ‹‹ result ‹‹ endl;

return 0;

}

greater.cpp

#include ‹iostream.h›

#include ‹stl.h›

int array[4] = {3, 1, 4, 2};

int main() {

sort(array, array + 4, greater‹int›());

for (int i = 0; i ‹ 4; i++) cout ‹‹ array[i] ‹‹ endl;

return 0;

}

swap1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

int a = 42;

int b = 19;

cout ‹‹ "a = " ‹‹ a ‹‹ " b = " ‹‹ b ‹‹ endl;

swap(a, b);

cout ‹‹ "a = " ‹‹ a ‹‹ " b = " ‹‹ b ‹‹ endl;

return 0;

}

times.cpp

#include ‹iostream.h›

#include ‹stl.h›

int input[4] = {1, 5, 7, 2};

int main() {

int total = accumulate(input, input + 4, 1, times‹int›());

cout ‹‹ "total = " ‹‹ total ‹‹ endl;

return 0;

}

less.cpp

#include ‹iostream.h›

#include ‹stl.h›

int array[4] = {3, 1, 4, 2};

int main() {

sort(array, array + 4, less‹int› ());

for (int i = 0; i ‹ 4; i++) cout ‹‹ array[i] ‹‹ endl;

return 0;

}

alg1.cpp

#include ‹iostream.h›

#include ‹stl.h›

int main() {

int i = min(4, 7);

cout ‹‹ "min(4, 7) = " ‹‹ i ‹‹ endl;

char c = maX('a', 'z');

cout ‹‹ "maX('a', 'z') = " ‹‹ c ‹‹ endl;

return 0;

}

filln1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

vector‹int› v(10);

fill_n(v.begin(), v.size(), 42);

for (int i = 0; i ‹ 10; i++) cout ‹‹ v[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

iota1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

int numbers[10];

iota(numbers, numbers + 10, 42);

for (int i = 0; i ‹ 10; i++) cout ‹‹ numbers[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

nextprm0.cpp

#include ‹stl.h›

#include ‹iostream.h›

int v1[3] = {0, 1, 2};

int main() {

next_permutation(v1, v1 + 3);

for (int i = 0; i ‹ 3; i++) cout ‹‹ v1[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

prevprm0.cpp

#include ‹stl.h›

#include ‹iostream.h›

int v1[3] = {0, 1, 2};

int main() {

prev_permutation(v1, v1 + 3);

for (int i = 0; i ‹ 3; i++) cout ‹‹ v1[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

fill1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

vector‹int› v(10);

fill(v.begin(), v.end(), 42);

for (int i = 0; i ‹ 10; i++) cout ‹‹ v[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}

pair2.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

pair‹int, int› p = make_pair(1, 10);

cout ‹‹ "p.first = " ‹‹ p.first ‹‹ endl;

cout ‹‹ "p.second = " ‹‹ p.second ‹‹ endl;

return 0;

}

error1.cpp

#include ‹stl.h›

// Compile this code without defining the symbol OS_USE_EXCEPTIONS.

int main() {

vector‹int› v;

v.pop_back(); // Generates an empty object error.

return 0;

}

pair0.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

pair‹int, int› p = make_pair(1, 10);

cout ‹‹ "p.first = " ‹‹ p.first ‹‹ ", p.second = " ‹‹ p.second ‹‹ endl;

return 0;

}

pair1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

pair‹int, int› p = make_pair(1, 10);

cout ‹‹ "p.first = " ‹‹ p.first ‹‹ ", p.second = " ‹‹ p.second ‹‹ endl;

return 0;

}

minelem1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int numbers[6] = {-10, 15, -100, 36, -242, 42};

int main() {

cout ‹‹ *min_element(numbers, numbers + 6) ‹‹ endl;

return 0;

}

maxelem1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int numbers[6] = {4, 10, 56, 11, -42, 19};

int main() {

cout ‹‹ *max_element(numbers, numbers + 6) ‹‹ endl;

return 0;

}

max1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

cout ‹‹ max(42, 100) ‹‹ endl;

return 0;

}

min1.cpp

#include ‹stl.h›

#include ‹iostream.h›

int main() {

cout ‹‹ min(42, 100) ‹‹ endl;

return 0;

}

adjdiff0.cpp

#include ‹stl.h›

#include ‹iostream.h›

int numbers[5] = {1, 2, 4, 8, 16};

int main() {

int difference[5];

adjacent_difference(numbers, numbers + 5, difference);

for (int i = 0; i ‹ 5; i++) cout ‹‹ numbers[i] ‹‹ ' ';

cout ‹‹ endl;

for (i = 0; i ‹ 5; i++) cout ‹‹ difference[i] ‹‹ ' ';

cout ‹‹ endl;

return 0;

}