Руководство по стандартной библиотеке шаблонов STL

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

Библиотека содержит пять основных видов компонентов: - алгоритм (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 a; list b; ... Employee* с = allocate(a.size() + b.size(), (Employee*) 0); merge(a.begin(), a.end(), b.begin(), b.end(), raw_storage_iterator (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(cin), istream_iterator(), ostream_iterator(cout, "\n"), not1(bind2nd (modulus(), atoi(argv[1])))); } Вся работа выполняется алгоритмом remove_copy_if, который читает целые числа одно за другим, пока итератор ввода не становится равным end-of-stream (конец-потока) итератору, который создаётся конструктором без параметров. (Вообще все алгоритмы работают способом "отсюда досюда", используя два итератора, которые показывают начало и конец ввода.) Потом remove_copy_if записывает целые числа, которые выдерживают проверку, в выходной поток через итератор вывода, который связан с cout. В качестве предиката remove_copy_if использует функциональный объект, созданный из функционального объекта modulus, который берёт i и j и возвращает i % j как бинарный предикат, и превращает в унарный предикат, используя bind2nd, чтобы связать второй параметр с параметром командной строки atoi(argv[1]). Потом отрицание этого унарного предиката получается с помощью адаптера функции not1.

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

main(int argc, char**) { if(argc != 1) throw("usage: shuffle\n"); vector v; copy(istream_iterator(cin),istream_iterator(), inserter(v, v.end())); random_shuffle(v.begin(), v.end()); copy(v.begin(), v.end(), ostream_iterator(cout)); } В этом примере copy перемещает строки из стандартного ввода в вектор, но так как вектор предварительно не размещён в памяти, используется итератор вставки, чтобы вставить в вектор строки одну за другой. (Эта методика позволяет всем функциям копирования работать в обычном режиме замены также, как в режиме вставки.) Потом random_shuffle перетасовывает вектор, а другой вызов copy копирует его в поток cout.

Требования

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

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

Чтобы избежать избыточных определений operator!= из operator== и operator>, , >= из operator, библиотека обеспечивает следующее:
template inline bool operator!=(const T1& x, const T2& y) { return !(x == y); } template inline bool operator>(const T1& x, const T2& y) { return y < x; } template inline bool operator inline bool operator>=(const T1& x, const T2& y) { return !(x < y); }

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

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

Пара (Pair)

Библиотека включает шаблоны для разнородных пар значений. template struct pair { T1 first; T2 second; pair() {} pair(const T1& x, const T2& y) : first(x), second(y) {} }; template inline bool operator==(const pair& x, const pair& y) { return x.first == y.first && x.second == y.second; } template inline bool operator& x, const pair& y) { return x.first < y.first (!(y.first < x.first) && x.second < y.second); } Библиотека обеспечивает соответствующую шаблонную функцию make_pair, чтобы упростить конструкцию пар. Вместо выражения, например: return pair(5, 3.1415926); // явные типы, можно написать return make_pair(5, 3.1415926); // типы выводятся. template inline pair make_pair(const T1& x, const T2& y) { return pair(x, y);

Двунаправленные итераторы (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	обратимый в bool	!(a > b)	.

Итераторы ввода (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;).

Итераторы

Итераторы - это обобщение указателей, которые позволяют программисту работать с различными структурами данных (контейнерами) единообразным способом. Чтобы создать шаблонные алгоритмы, которые правильно и эффективно работают с различными типами структур данных, нам нужно формализовать не только интерфейсы, но также семантику и предположения сложности итераторов. Итераторы - это объекты, которые имеют 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.

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

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

Последовательные итераторы (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 (что неверно для итераторов ввода и вывода) и что удалено ограничение на число присваиваний через итератор (которое применяется к итераторам вывода), позволяет использование многопроходных однонаправленных алгоритмов с последовательными итераторами.

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

Для всех типов обычных указателей мы можем определить value_type и distance_type с помощью следующего:
template inline T* value_type(const T*) { return (T*) (0); } template inline ptrdiff_t* distance_type(const T*) { return (ptrdiff_t*) (0); } Тогда, если мы хотим осуществить обобщённую функцию reverse, мы пишем следующее: template inline void reverse(BidirectionalIterator first, BidirectionalIterator last) { _reverse(first, last, value_type(first), distance_type(first)); } где _reverse определена следующим образом: template 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 inline T* value_type(const T _huge *) { return (T*) (0); } template 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 inline random_access_iterator_tag iterator_category(const T*) { return random_access_iterator_tag(); } Определяемый пользователем итератор BinaryTreeIterator может быть включен в категорию двунаправленных итераторов следующим образом: template inline bidirectional_iterator_tag iterator_category( const BinaryTreeIterator&) { return bidirectional_iterator_tag(); } Если шаблонная функция evolve хорошо определена для двунаправленных итераторов, но может быть осуществлена более эффективно для итераторов произвольного доступа, тогда реализация выглядит так:
template inline void evolve(BidirectionalIterator first, BidirectionalIterator last) { evolve(first, last, iterator_category(first)); } template void evolve(BidirectionalIterator first, BidirectionalIterator last, bidirectional_iterator_tag) { // ... более универсальный, но менее эффективный алгоритм } template 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 struct input_iterator {}; struct output_iterator {}; // output_iterator не шаблон, потому что у итераторов вывода // не определены ни значимый тип, ни тип расстояния. template struct forward_iterator {}; template struct bidirectional_iterator {}; template struct random_access_iterator {}; // iterator_category (функции категорий итераторов) template inline input_iterator_tag iterator_category(const input_iterator&) { return input_iterator_tag(); } inline output_iterator_tag iterator_category(const output_iterator&) { return output_iterator_tag(); } template inline forward_iterator_tag iterator_category(const forward_iterator&) { return forward_iterator_tag(); } template inline bidirectional_iterator_tag iterator_category(const bidirectional_iterator&) { return bidirectional_iterator_tag(); ) template inline random_access_iterator_tag iterator_category(const random_access_iterator&) { return random_access_iterator_tag(); } template inline random_access_iterator_tag iterator_category(const T*) { return random_access_iterator_tag(); } // value_type of iterator (функции значимого типа итераторов) template inline T* value_type(const input_iterator&) ( return (T*) (0); } template inline T* value_type(const forward_iterator&) { return (T*) (0); } template inline T* value_type(const bidirectional_iterator&) { return (T*) (0); } template inline T* value_type(const random_access_iterator&) { return (T*) (0); } template inline T* value_type(const T*) { return (T*) (0); } // distance_type of iterator (функции типа расстояния итераторов) template inline Distance* distance_type(const input_iterator&) { return (Distance*) (0); } template inline Distance* distance_type(const forward_iterator&) { return (Distance*) (0); } template inline Distance* distance_type(const bidirectional_iterator&) { return (Distance*) (0); } template inline Distance* distance_type(const random_access_iterator&) { return (Distance*) (0); } template inline ptrdiff_t* distance_type(const T*) { return (ptrdiff_t*) (0); } Если пользователь хочет определить двунаправленный итератор для некоторой структуры данных, содержащей double, и такой, чтобы работал с большой (large) моделью памяти компьютера, то это может быть сделано таким определением:
class MyIterator : public bidirectional_iterator { // код, осуществляющий ++, и т.д. }; Тогда нет необходимости определять iterator_category, value_type, и distance_type в MyIterator.

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

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

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

Библиотека обеспечивает базовые классы функциональных объектов для всех арифметических операторов языка.
template struct plus : binary_function { Т operator()(const T& x, const T& y) const { return x + y; } }; template struct minus : binary_function { Т operator()(const T& x, const T& y) const { return x - y; } }; template struct times : binary_function { Т operator()(const T& x, const T& y) const ( return x * y; } }; template struct divides : binary_function { Т operator()(const T& x, const T& y) const { return x / y; } }; template struct modulus : binary_function { Т operator()(const T& x, const T& y) const { return x % y; } }; template struct negate : unary_function { Т operator()(const T& x) const { return -x; } };

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

Следующие классы предоставляются, чтобы упростить определение типов (typedefs) параметров и результата:
template struct unary_function { typedef Arg argument_type; typedef Result result_type; }: template struct binary_function { typedef Arg1 first_argument_type; typedef Arg2 second_argument_type; typedef Result result_type; };

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

Функциональные объекты - это объекты, для которых определён operator(). Они важны для эффективного использования библиотеки. В местах, где ожидается передача указателя на функцию алгоритмическому шаблону, интерфейс установлен на приём объекта с определённым operator(). Это не только заставляет алгоритмические шаблоны работать с указателями на функции, но также позволяет им работать с произвольными функциональными объектами. Использование функциональных объектов вместе с функциональными шаблонами увеличивает выразительную мощность библиотеки также, как делает результирующий код более эффективным. Например, если мы хотим поэлементно сложить два вектора a и b, содержащие double, и поместить результат в a, мы можем сделать зто так:
transform(a.begin(), a.end(), b.begin(), a.begin(), plus()); Если мы хотим отрицать каждый элемент a, мы можем сделать это так:
transform(a.begin(), a.end(), a.begin(), negate()); Соответствующие функции вставят сложение и отрицание. Чтобы позволить адаптерам и другим компонентам манипулировать функциональными объектами, которые используют один или два параметра, требуется, чтобы они соответственно обеспечили определение типов (typedefs) argument_type и result_type для функциональных объектов, которые используют один параметр, и first_argument_type, second_argument_type и result_type для функциональных объектов, которые используют два параметра.

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

template struct logical_and : binary_function { bool operator()(const T& x, const T& y) const { return x && y; } };
template struct logical_or : binary_function { bool operator()(const T& x, const T& y) const { return x y; } };
template struct logical_not : unary_function { bool operator()(const T& x) const { return !x; } };

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

Библиотека обеспечивает базовые классы функциональных объектов для всех операторов сравнения языка
template struct equal_to : binary_function { bool operator()(const T& x, const T& y) const { return x == y; } }; template struct not_equal_to : binary_function { bool operator()(const T& x, const T& y) const { return x != y; } }; template struct greater : binary_function { bool operator()(const T& x, const T& y) const { return x > y; } }; template struct less : binary_function { bool operator()(const T& x, const T& y) const { return x < y; } }; template struct greater_equal : binary_function { bool operator()(const T& x, const T& y) const { return x >= y; } }; template struct less_equal : binary_function { bool operator()(const T& x, const T& y) const { return x

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

template 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 { public: typedef void* pointer; allocator(); ~allocator(); }; Предполагается, что в дополнение к allocator поставщики библиотеки обеспечивают распределители для всех моделей памяти.

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

Одна из общих проблем в мобильности - это способность инкапсулировать информацию относительно модели памяти. Эта информация включает типы указателей, тип их разности, тип размера объектов в этой модели памяти, также как её примитивы выделения и освобождения памяти.
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 определены только конструктор, деструктор и Alloc::pointer. Преобразования определены из любого Alloc::pointer в Alloc::pointer и обратно, так что для любого p будет p == Alloc::pointer(Alloc::pointer(p)).

Ассоциативные контейнеры (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.
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.	время компиляции
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	вставляет 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; pairator, const_iterator> для константы a	эквивалент make_pair(lower_boud(k), upper_bound (k)).	логарифмическая

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

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

deque - вид последовательности, которая, подобно вектору, поддерживает итераторы произвольного доступа. Кроме того она поддерживает операции вставки и стирания в начале или в конце за постоянное время; вставка и стирание в середине занимают линейное время. Как с векторами, управление памятью обрабатывается автоматически.
template class Allocator = allocator> class deque { public: // typedefs: typedef iterator; typedef const_iterator; typedef Allocator::pointer pointer; typedef Allocator ::reference reference; typedef Allocator::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& x); template deque(InputIterator first, InputIterator last); ~deque(); deque& operator=(const deque& x); void swap(deque& 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 bool operator==(const deque& x, const deque& y); template bool operator& x, const deque& 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 (извлечение) с обоих концов двусторонней очереди делают недействительными только итераторы и ссылки на стёртый элемент. Число вызовов деструктора равно числу стёртых элементов, а число вызовов оператора присваивания равно минимуму из числа элементов перед стёртыми элементами и числа элементов после стёртых элементов.

Контейнеры

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

выражение	возвращаемый тип	семантика исполнения	утверждение/примечание состояние до/после	сложность
X::value_type	Т	.	.	время компиляции
X::reference	.	.	.	время компиляции
X::const_refe rence	.	.	.	время компиляции
X::pointer	тип указателя, указывающий на X::reference	.	указатель на T в модели памяти, используемой контейнером	время компиляции
X::iterator	тип итратора, указывающий на X::reference	.	итератор любой категории, кроме итератора вывода.	время компиляции
X::const_iter ator	тип итератора, указывающий на 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())	== - это отношение эквивалентности. примечание: eqial определяется в разделе алгоритмов.	линейная
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	обратимый в 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 для итератора произвольного доступа. reverse_bidirectional_iteratoriterator, value_type, reference, difference_type> для двунаправленного итератора	время компиляции
X::const_r everse_ite rator	.	reverse_iterator для итератора произвольного доступа. reverse_bidirectional_iteratorconst_iterator, value_type, const_reference, difference_type> для двунаправленного итератора.	время компиляции
a.rbegin()	reverse_iterator; const_reverse_iter ator для постоянного a	reverse_iterator(end())	постоянная
a.rend()	reverse_iterator; const_reverse_iter ator для постоянного a	reverse_iterator(begin())	постоянная

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

multiset - это ассоциативный контейнер, который поддерживает равные ключи (возможно, содержит множественные копии того же самого значения ключа) и обеспечивает быстрый поиск ключей.
template , template class Allocator = allocator> class multiset { public: // typedefs: typedef Key key_type; typedef Key value_type; typedef Allocator::pointer pointer; typedef Aliocator::reference reference; typedef Allocator::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 multiset(InputIterator first, InputIterator last, const Compare& comp == Compare()); multiset(const multiset& x); ~multiset(); multiset& operator=(const multiset& x); void swap(multiset& x); // accessors: key_compare key_comp() const; value_compare value_comp() const; iterator begin() const; iterator end() const; reverse_iterator rbegin(); revferse_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 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 equal_range(const key_type& x) const; }; template bool operator==(const multiset& x, const multiset& y); template bool operator<(const multiset& x, const multiset& y); iterator - постоянный двунаправленный итератор, указывающий на const value_type. Точный тип зависит от реализации и определяется в Allocator.
сonst_iterator - тот же самый тип, что и iterator.
size_type - целочисленный тип без знака. Точный тип зависит от реализации и определяется в Allocator.
difference_type - целочисленный тип со знаком. Точный тип зависит от реализации и определяется в Allocator.

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

set - это ассоциативный контейнер, который поддерживает уникальные ключи (не содержит ключи с одинаковыми значениями) и обеспечивает быстрый поиск ключей.
template , template class Allocator = allocator> class set { public: // typedefs: typedef Key key_type; typedef Key value_type; typedef Allocator::pointer pointer; typedef Allocator::reference reference; typedef Allocator::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 set(InputIterator first, InputIterator last, const Compare& comp = Compare()); set(const set& x); ~set(); set& operator=(const set& x); void swap(set& 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 insert(const value_type& x); iterator insert(iterator position, const value_type& x); template 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 equal_range(const key_type& x) const; }; template bool operator==(const set& x, const set& y); template bool operator<(const set& x, const set& y); iterator - постоянный двунаправленный итератор, указывающий на const value_type. Точный тип зависит от реализации и определяется в Allocator.
сonst_iterator - тот же самый тип, что и iterator.
size_type - целочисленный тип без знака. Точный тип зависит от реализации и определяется в Allocator.
difference_type - целочисленный тип со знаком. Точный тип зависит от реализации и определяется в Allocator.

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

Последовательность - это вид контейнера, который организует конечное множество объектов одного и того же типа в строгом линейном порядке. Библиотека обеспечивает три основных вида последовательных контейнеров: vector (вектор), list (список) и deque (двусторонняя очередь). Она также предоставляет контейнерные адаптеры, которые облегчают создание абстрактных типов данных, таких как стеки или очереди, из основных видов последовательностей (или из других видов последовательностей, которые пользователь может сам определить).
В следующих двух таблицах X - последовательный класс, a - значение X, i и j удовлетворяют требованиям итераторов ввода, [i, j) - допустимый диапазон, n - значение X::size_type, p - допустимый итератор для a, q - разыменовываемый итератор для a, [ql, 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

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

Словарь (Map)

map - ассоциативный контейнер, который поддерживает уникальные ключи (не содержит ключи с одинаковыми значениями) и обеспечивает быстрый поиск значений другого типа T, связанных с ключами.
template , template class Allocator = allocator> class map { public: // typedefs: typedef Key key_type; typedef pair value_type; typedef Compare key_compare; class value_compare : public binary_function { 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::pointer pointer; typedef Allocator::reference reference; typedef Allocator::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 map(InputIterator first, InputIterator last, const Compare& comp = Compare()); map(const map& x); ~map(); map& operator=(const map& x); void swap(map& 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::reference operator[](const key_type& x); // insert/erase: pair insert(const value_type& x); iterator insert(iterator position, const value_type& x); template 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 equal_range(const key_type& x); pair equal_range(const key_type& x)const; }; template bool operator==(const map& x, const map& y); template bool operator<(const mapr& x, const map& 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 , template class Allocator = allocator> class multimap { public: // typedefs: typedef Key key_type; typedef pair value_type; typedef Compare key_compare; class value_compare : public binary_function { 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::pointer pointer; typedef Allocator::reference reference; typedef Allocator::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 multimap(InputIterator first, InputIterator last, const Compare& comp = Compare()); multimap(const multimap& x); ~multimap(); multimap& operator=(const multimap& x); void swap(multimap& 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 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 equal_range(const key_type& x); pair equal_range(const key_type& x) const; }; template bool operator==(const multimap& x, const multimap& y); template bool operator<(const multimap& x, const multimap& y); iterator - двунаправленный итератор, указывающий на value_type. Точный тип зависит от реализации и определяется в Allocator.
const_iterator - постоянный двунаправленный итератор, указывающий на value_type. Точный тип зависит от реализации и определяется в Allocator. Гарантируется, что имеется конструктор для const_iterator из iterator.
size_type - целочисленный тип без знака. Точный тип зависит от реализации и определяется в Allocator.
difference_type - целочисленный тип со знаком. Точный тип зависит от реализации и определяется в Allocator.

Список (List)

list - вид последовательности, которая поддерживает двунаправленные итераторы и позволяет операции вставки и стирания с постоянным временем в любом месте последовательности, с управлением памятью, обрабатываемым автоматически. В отличие от векторов и двусторонних очередей, быстрый произвольный доступ к элементам списка не поддерживается, но многим алгоритмам, во всяком случае, только и нужен последовательный доступ.
template class Allocator = allocator> class list { public: // определения типов: typedef iterator; typedef const_iterator; typedef Allocator::pointer pointer; typedef Allocator::reference reference; typedef Allocator::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 list(InputIterator first, InputIterator last); list(const list& x) ; ~list(); list& operator=(const list& x); void swap(list 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& x); void splice(iterator position, list& x, iterator i); void splice(iterator position, list& x, iterator first, iterator last); void remove(const T& value); template void remove_if(Predicate pred); void unique(); template void unique(BinaryPredicate binary_pred); void merge(list& x); template void merge(list& x, Compare comp); void reverse(); void sort(); template void sort(Compare comp); }; template bool operator==(const list& x, const list& y); template bool operator& x, const list& 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& x) вставляет содержимое x перед position, и x становится пустым. Требуется постоянное время. Результат не определён, если &x == this.

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

void splice(iterator position, list& 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().

Вектор (Vector)

vector - вид последовательности, которая поддерживает итераторы произвольного доступа. Кроме того, он поддерживает операции вставки и удаления в конце с постоянным (амортизированным) временем; вставка и удаление в середине занимают линейное время. Управление памятью обрабатывается автоматически, хотя для улучшения эффективности можно давать подсказки.
template class vector { public: // определения типов (typedefs): typedef iterator; typedef const_iterator; typedef Allocator::pointer pointer; typedef Allocator::reference reference; typedef Allocator::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& x); template vector(InputIterator first, InputIterator last); ~vector(); vector& operator=(const vector& x); void reserve(size_type n); void swap(vector& 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 void insert(iterator position, InputIterator first, InputIterator last); void pop_back(); void erase(iterator position); void erase(iterator first, iterator last); }; template bool operator==(const vector& x, const vector& y); template bool operator& x, const vector& y); iterator - это итератор произвольного доступа, ссылающийся на T.
Точный тип зависит от исполнения и определяется в Allocator.

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

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

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

Конструктор template 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 { 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& x); template vector(InputIterator first, InputIterator last); ~vector(); vector& operator=(const vector& x); void reserve(size_type n); void swap(vector& 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 void insert(iterator position, InputIterator first, InputIterator last); void pop_back(); void erase(iterator position); void erase(iterator first, iterator last); }; void swap(vector::reference x, vector::reference y); bool operator==(const vector& x, const vector& y); bool operator& x, const vector& y); reference - класс, который имитирует поведение ссылок отдельного бита в vector.

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

Сейчас невозможно шаблонизировать определение. То есть мы не можем написать: template class Allocator == allocator> class vector { /* ... */ }; Поэтому обеспечивается только vector.

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

istream_iterator читает (используя operator>>) последовательные элементы из входного потока, для которого он был создан. После своего создания итератор каждый раз при использовании ++ читает и сохраняет значение T. Если достигнут конец потока (operator void* () в потоке возвращает false), итератор становится равным значению end-of-stream (конец-потока). Конструктор без параметров istream_iterator() всегда создаёт итераторный объект конца потокового ввода, являющийся единственым законным итератором, который следует использовать для конечного условия. Результат operator* для конца потока не определён, а для любого другого значения итератора возвращается const T&.
Невозможно записывать что-либо с использованием входных итераторов. Основная особенность входных итераторов - тот факт, что операторы ++ не сохраняют равенства, то есть i == j не гарантирует вообще, что ++ i == ++ j. Каждый раз, когда ++ используется, читается новое значение. Практическое следствие этого факта - то, что входные итераторы могут использоваться только для однопроходных алгоритмов, что действительно имеет здравый смысл, так как многопроходным алгоритмам всегда более соответствует использование структур данных в оперативной памяти.
Два итератора конец-потока всегда равны. Итератор конец-потока не равен не-конец-потока итератору. Два не-конец-потока итератора равны, когда они созданы из того же самого потока.
template class istream_iterator : public input_iterator { friend bool operator==(const istream_iterator& x, const istream_iterator& y); public: istream_iterator(); istream_iterator(istream& s); istream_iterator(const istream_iterator& x); ~istream_iterator(); const T& operator*() const; istream_iterator& operator++(); istream_iterator operator++(int); }; template bool operator==(const istream_iterator& x, const istream_iterator& y);

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

istream_iterator записывает (используя operator) последовательные элементы в выходной поток, из которого он был создан. Если он был создан с параметром конструктора char*, эта строка, называемая строкой разделителя (delimiter string), записывается в поток после того, как записывается каждое T. Невозможно с помощью выходного итератора получить значение. Его единственное использование - выходной итератор в ситуациях, подобных нижеследующему:
while (first != last) *result++ = *first++; ostream_iterator определён как:
template class ostream_iterator : public output_iterator { public: ostream_iterator(ostream& s); ostream_iterator(ostream& s, const char* delimiter); ostream_iterator(const ostream_iterator& x); ~ostream_iterator(); ostream_iterator& operator=(const T& value); ostream_iterator& operator*(); ostream_iterator& operator++(); ostream_iterator& operator++(int); };

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

Чтобы шаблоны алгоритмов могли работать непосредственно с потоками ввода-вывода, предусмотрены соответствующие шаблонные классы, подобные итераторам. Например,
partial_sum_copy(istream_iterator(cin), istream_iterator(), ostream_iterator(cout, "\n")); читает файл, содержащий числа с плавающей запятой, из cin и печатает частичные суммы в cout.

АЛГОРИТМЫ

Все алгоритмы отделены от деталей реализации структур данных и используют в качестве параметров типы итераторов. Поэтому они могут работать с определяемыми пользователем структурами данных, когда эти структуры данных имеют типы итераторов, удовлетворяющие предположениям в алгоритмах.
Для некоторых алгоритмов предусмотрены и оперативные и копирующие версии. Решение, включать ли копирующую версию, было обычно основано на рассмотрении сложности. Когда стоимость выполнения операции доминирует над стоимостью копии, копирующая версия не включена. Например, 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;}.

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

template OutputIterator partial_sum(InputIterator first, InputIterator last, OutputIterator result); template 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.

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

Все алгоритмы в этом разделе - версии двоичного поиска. Они работают с итераторами не произвольного доступа, уменьшая число сравнений, которое будет логарифмическим для всех типов итераторов. Они особенно подходят для итераторов произвольного доступа, так как эти алгоритмы делают логарифмическое число шагов в структуре данных. Для итераторов не произвольного доступа они выполняют линейное число шагов.
template ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value); template 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 ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value); template 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 ForwardIterator equal_range(ForwardIterator first, ForwardIterator last, const T& value); template 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 ForwardIterator binary_search(ForwardIterator first, ForwardIterator last, const T& value); template 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 сравнений.

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

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

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

template OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result); copy копирует элементы. Для каждого неотрицательного целого числа n < (last - first) выполняется присваивание *( result + n) = *( first + n). Точно делается last - first присваиваний. Результат copy не определён, если result находится в диапазоне [first, last).
template 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 выполняется присваивание *(result - n) = *(last - n). copy_backward возвращает result - (last - first). Точно делается last - first присваиваний. Результат copy_backward не определён, если result находится в диапазоне [first, last).

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

template bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); template 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)) сравнений.

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

template const T& min(const T& a, const T& b); template const T& min(const T& a, const T& b, Compare comp); template const T& max(const T& a, const T& b); template const T& max(const T& a, const T& b, Compare comp); min возвращает меньшее, а max большее. min и max возвращают первый параметр, когда их параметры равны.
template ForwardIterator max_element(ForwardIterator first, ForwardIterator last); template 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 ForwardIterator min_element(ForwardIterator first, ForwardIterator last); template 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) соответствующих сравнений.

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

template void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last); template 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. Операция линейна в среднем.

Найти (Find)

template InputIterator find(InputIterator first, InputIterator last, const T& value); template 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 ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last); template 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) раз.

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

template T accumulate(InputIterator first, InputIterator last, T init); template 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 не вызывает побочных эффектов.

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

template OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template 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 void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last); template void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp); inplace_merge объединяет два сортированных последовательных диапазона [first, middle) и [middle, last), помещая результат объединения в диапазон [first, last). Объединение устойчиво, то есть для равных элементов в двух диапазонах элементы из первого диапазона всегда предшествуют элементам из второго. Когда доступно достаточно дополнительной памяти, выполняется максимально (last - first) - 1 сравнений. Если никакая дополнительная память не доступна, может использоваться алгоритм со сложностью O(NlogN).

Обменять (Swap)

template void swap(T& a, T& b); swap обменивает значения, хранимые в двух местах.
template void iter_swap(ForwardIterator1 a, ForwardIterator2 b); iter_swap обменивает значения, указанные двумя итераторами a и b.
tempate 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)) перекрываются.

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

Этот раздел определяет все основные операции над множеством для сортированных структур. Они даже работают с множествами с дубликатами, содержащими множественные копии равных элементов. Семантика операций над множеством обобщена на множества с дубликатами стандартным способом, определяя объединение, содержащее максимальное число местонахождений каждого элемента, пересечение, содержащее минимум, и так далее. template bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); template 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 OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template 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 OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template 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 OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); set_difference создаёт сортированную разность элементов из двух диапазонов. Он возвращает конец созданного диапазона. Выполняется максимально ((last1 - first1) + (last2 - first2)) * 2 - 1 сравнений. Результат set_difference не определён, если возникающий в результате диапазон перекрывается с любым из первоначальных диапазонов.

template OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result); template 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 void push_heap(RandomAccessIterator first, RandomAccessIterator last); template void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); push_heap полагает, что диапазон [first, last - 1) является соответствующей пирамидой, и надлежащим образом помещает значение с позиции last - 1 в результирующую пирамиду [first, last). Выполняется максимально log(last - first) сравнений.
template void pop_heap(RandomAccessIterator first, RandomAccessIterator last); template void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); pop_heap полагает, что диапазон [first, last) является соответствующей пирамидой, затем обменивает значения в позициях first и last - 1 и превращает [first, last - 1) в пирамиду. Выполняется максимально 2 * log(last - first) сравнений.
template void make_heap(RandomAccessIterator first, RandomAccessIterator last); template void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); make_heap создает пирамиду из диапазона [first, last). Выполняется максимально 3 * (last - first) сравнений.
template void sort_heap(RandomAccessIterator first, RandomAccessIterator last); template void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); sort_heap сортирует элементы в пирамиде [first, last). Выполняется максимально NlogN сравнений, где N равно last - first. sort_heap не устойчив.

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

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

Операции сортировки и отношения (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).

Отличие (Mismatch)

template pair mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2); template pair 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 раз.

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

template 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 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 void random_shuffle(RandomAccessIterator first, RandomAccessIterator last); template void random_shuffie(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& rand); random_shuffle переставляет элементы в диапазоне [first, last) с равномерным распределением. Выполняется точно last - first перестановок. random_shuffle может брать в качестве параметра особый генерирующий случайное число функциональный объект rand такой, что rand берёт положительный параметр n типа расстояния RandomAccessIterator и возвращает случайно выбранное значение между 0 и n-1.

Подсчет (Count)

template void count(InputIterator first, InputIterator last, const T& value, Size& n); template 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*.

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

template ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template 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) раз. Квадратичное поведение, однако, является крайне маловероятным.

Породить (Generate)

template void generate(ForwardIterator first, ForwardIterator last, Generator gen); template 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 и присваиваний.

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

template OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op); template 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 в случае бинарного.

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

template void reverse(BidirectionalIterator first, BidirectionalIterator last); Для каждого неотрицательного целого числа i функция reverse применяет перестановку ко всем парам итераторов first + i, (last - i) - 1. Выполняется точно (last - first)/2 перестановок.
template 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)) перекрываются.

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

template 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 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 раз.

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

template T inner_product(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, T init); template 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 не вызывают побочных эффектов.

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

template OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result); template 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.

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

template void sort(RandomAccessIterator first, RandomAccessIterator last); template void sort(RandomAccessIterator first, RandomAccessIterator last, Compare соmр); sort сортирует элементы в диапазоне [first, last). Делается приблизительно NIogN (где N равняется last - first) сравнений в среднем. Если режим наихудшего случая важен, должны использоваться stable_sort или partial_sort.
template void stable_sort(RandomAccessIterator first, RandomAccessIterator last); template void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp); stable_sort сортирует элементы в диапазоне [first, last). Он устойчив, то есть относительный порядок равных элементов сохраняется. Делается максимум N(logN)2 (гдеN равняется last - first) сравнений; если доступна достаточная дополнительная память, тогда зто - NlogN.
template void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last); template 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 RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last); template 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)) сравнений.

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

template bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2); template 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 раз.

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

template ForwardIterator unique(ForwardIterator first, ForwardIterator last); template 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 OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result); template 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 раз.

Удалить (Remove)

template ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T& value); template ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, Predicate pred); remove устраняет все элементы, указываемые итератором i в диапазоне [first, last), для которых выполнены следующие соответствующие условия: *i == value, pred (*i) == true. remove возвращает конец возникающего в результате своей работы диапазона. remove устойчив, то есть относительный порядок элементов, которые не удалены, такой же, как их относительный порядок в первоначальном диапазоне. Соответствующий предикат применяется точно last -first раз.
template OutputIterator remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value); template 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 раз.

Заменить (Replace)

template void replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value); template 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 OutputIterator replace_copy(InputIterator first, InputIterator last, OutputIterator result, const T& old_value, const T& new_value); template 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 void fill(ForwardIterator first, ForwardIterator last, const T& value); template OutputIterator fill_n(Output Iterator first, Size n, const T& value); fill присваивает значения через все итераторы в диапазоне [first, last) или [first, first + n). fill_n возвращает first + n. Точно делается last - first (или n) присваиваний.

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

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

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

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

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

Чтобы позволить указателям на (унарные и бинарные) функции работать с функциональными адаптерами, библиотека обеспечивает следующее:
template class pointer_to_unary_function : public unary_function { 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 pointer_to_unary_function ptr_fun(Result (*x)(Arg)) { return pointer_to_unary_function(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 pointer_to_binary_function ptr_fun(Result (*x)(Arg1, Arg2)) { return pointer_to_binary_function(x); } Например, replace_if(v.begin(), v.end(), not1(bind2nd(ptr_fun(strcmp), "C")), "C++") заменяет все "С" на "C++" в последовательности v.
Системы трансляции, которые имеют множественный указатель на типы функций, должны обеспечить дополнительные шаблоны функций ptr_fun.

АДАПТЕРЫ

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

Итераторы вставки (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 back_insert_iterator : public output_iterator { protected: Container& container; public: back_insert_iterator(Container& x) : container(x) {} back_insert_iterator & operator=(const Container::value_type& value) { container.push_back(value); return *this; } back_insert_iterator& operator*() { return *this; } back_insert_iterator& operator++() { return *this; } back_insert_iterator& operator++(int) { return *this; } }; template back_insert_iterator back_inserter(Container& x) { return back_insert_iterator(x); } template class front_insert_iterator : public output_iterator { protected: Container& container; public: front_insert_iterator(Container& x) : container (x) {} front_insert_iterator& operator=(const Container::value_type& value) { container.push_front(value); return *this; } front_insert_iterator& operator*() { return *this; } front_insert_iterator& operator++() { return *this; } front_insert_iterator& operator++(int) { return *this;} }; template front_insert_iterator front_inserter(Container& x) { return front_insert_iterator(х); } template 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& operator=(const Container::value_type& value) { iter = container.insert(iter, value); ++iter; return *this; } insert_iterator& operator*() { return *this; } insert_iterator& operator++() { return *this; } insert_iterator& operator++(int) { return *this; } }; template insert_iterator&tl;Container> inserter(Container& x, Iterator i) { return insert_iterator(x, Container::iterator(i)); }

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

Двунаправленные итераторы и итераторы произвольного доступа имеют соответствующие адаптеры обратных итераторов, которые выполняют итерации через структуру данных в противоположном направлении.Они имеют те же самые сигнатуры, как и соответствующие итераторы. Фундаментальное соотношение между обратным итератором и его соответствующим итератором i установлено тождеством &*(reverse_iterator(i)) == &*(i - 1). Это отображение продиктовано тем, что, в то время как после конца массива всегда есть указатель, может не быть допустимого указателя перед началом массива.
template class reverse_bidirectionaiIterator : public bidirectional_iterator { typedef reverse_bidirectional_iterator 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 inline bool operator==( const reverse_bidirectional_iterator& x, const reverse_bidirectional_iterator& y){ return x.current == y.current; } template class reverse_iterator : public random_access_iterator{ typedef reverse_iterator 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 inline bool operator==( const reverse_iterator& x, const reverse_iterator& y) { return x.current == y.current; } template inline bool operator<( const reverse_iterator& x, const reverse_iterator& y) { return y.current < x.current; } template inline Distance operator-( const reverse_iterator& х, const reverse_iterator& y) { return y.current - x.current; } template inline reverse_iterator operator+( Distance n, const reverse_iterator& x) { return reverse_iterator (x.current - n); }

Очередь (Queue)

Любая последовательность, поддерживающая операции front, push_back и pop_front, может использоваться для модификации queue. В частности, могут использоваться list и deque.
template class queue { friend bool operator==(const queue& х, const queue& y); friend bool operator<(const queue& х, const queue& 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 bool operator==(const queue& х, const queue& y) { return х.с == у.с;} template bool operator<(const queue& х, const queue<Container>& y) { return х.с < у.с; }

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

Любая последовательность, с итератором произвольного доступа и поддерживающая операции front, push_back и pop_front, может использоваться для модификации priority_queue. В частности, могут использоваться vector и deque.
template > 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 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(); } }; // Никакое равенство не обеспечивается

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

Отрицатели not1 и not2 берут унарный и бинарный предикаты соответственно и возвращают их дополнения.
template class unary_negate : public unary_function { protected: Predicate pred; public: unary_negate(const Predicate& x) : pred(x) {} bool operator()(const argument_type& x) const { return !pred(x); } }; template unary_negate not1(const Predicate& pred) { return unary_negate(pred); } template class binary_negate : public binary_function { 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 binary_negate not2(const Predicate& pred) { return binary_negate(pred); }

Привязки (Binders)

Привязки bind1st и bind2nd берут функциональный объект f двух параметров и значение x и возвращают функциональный объект одного параметра, созданный из f с первым или вторым параметром соответственно, связанным с х.
template 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 binder1st<0peration> bind1st(const Operation& op, const T& x) { return binder1st<0peration>(op, Operation::first_argument_type(x)); } template 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 binder2nd bind2nd(const Operation& op, const T& x) { return binder2nd<0peration>(op, Operation::second_argument_type(x)); } Например, find_if(v.begin(), v.end(), bind2nd(greater(), 5)) находит первое целое число в векторе v большее, чем 5; find_if(v.begin(), v.end(), bind1st(greater(), 5)) находит первое целое число в v меньшее, чем 5.

Стек (Stack)

Любая последовательность, поддерживающая операции back, push_back и pop_back, может использоваться для модификации stack. В частности, могут использоваться vector, list и deque.
template class stack { friend bool operator==(const stack& х, const stack& y); friend bool operator<(const stack& х, const stack& 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 bool operator==(const stack & х, const stack& y) { return х.с == у.с;} template bool operator<(const stack& х, const stack& y) { return х.с < у.с; } Например, stack > - целочисленный стек, сделанный из vector, а stack > - символьный стек, сделанный из deque.

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

Чтобы получать типичный указатель на неинициализированный буфер памяти данного размера, определена следующая функция:
template inline T* allocate(ptrdiff_t n, Т*); // n >= 0 Размер (в байтах) распределённого буфера - не меньше n*sizeof(T).
Для каждой модели памяти имеется соответствующий шаблон функции allocate, определённый с типом первого параметра, являющимся типом расстояния указателей в модели памяти.
Например, если система трансляции поддерживает _huge указатели с типом расстояния long long, обеспечивается следующая шаблонная функция:
template inline T _huge* allocate(long long n, T _huge *); Также обеспечиваются следующие функции:
template inline void deallocate(T* buffer); template inline void construct(T1* p, const T2& value) { new (p) T1(value);} template inline void destroy(T* pointer) { pointer->~T();} deallocate освобождает буфер, выделенный allocate. Для каждой модели памяти имеются соответствующие шаблоны функций deallocate, construct и destroy, определённые с типом первого параметра, являющимся типом указателя в модели памяти.
template pair get_temporary_buffer(ptrdiff_t n, T*); template void return_temporary_buffer(T* p); get_temporary_buffer ищет наибольший буфер, не больше чем n*sizeof(T), и возвращает пару, состоящую из адреса и размера (в единицах sizeof(T)) буфера. return_temporary_buffer возвращает буфер, выделенный get_temporary_buffer.

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

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

int main

#include #include

int main () { vector 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; }



#include #include

int mult ( int initial_, int element_) { return initial_ * element_; }

int main () { vector 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; }

int main

#include #include

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; }



#include #include

int main () { vector v (10); for (int i = 0; i < v.size (); i++) v[i] = i * i; vector result (v.size ()); adjacent_difference (v.begin (), v.end (), result.begin ()); ostream_iterator iter (cout, " "); copy (v.begin (), v.end (), iter); cout << endl; copy (result.begin (), result.end (), iter); cout << endl; return 0; }



#include #include

int mult ( int a_, int b_) { return a_ * b_; }

int main () { vector v (10); for (int i = 0; i < v.size (); i++) v[i] = i + 1; vector rslt (v.size ()); adjacent_difference (v.begin (), v.end (), rslt.begin (), mult); ostream_iterator iter (cout, " "); copy (v.begin (), v.end (), iter); cout << endl; copy (rslt.begin (), rslt.end (), iter); cout << endl; return 0; }

Found adjacent pair of:

#include #include

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; }



#include #include

int main () { typedef vector 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; }



#include #include #include

typedef vector 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; }

Advance

#include #include
int main () { typedef vector 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; }

int main

#include #include

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; }



#include #include

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; }



#include #include

int main () { vector i; i.push_back (1); i.push_back (4); i.push_back (2); i.push_back (8); i.push_back (2); 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; }



#include #include

int main () { vector years; years.push_back (1962); years.push_back (1992); years.push_back (2001); years.push_back (1999); sort (years.begin (), years.end ()); vector:: iterator i; for (i = years.begin (); i != years.end (); i++) cout << *i << endl; return 0; }



#include #include

int main () { list 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::iterator i; for (i = years.begin (); i != years.end (); i++) cout << *i << endl; return 0; }

int main

#include #include

int main () { { cout << "vectors:" << endl; os_my_allocator alloc; vector v3 (alloc); v3.push_back (42); vector v4 (alloc); v4.push_back (42); }

{ cout << "bit_vectors:" << endl; os_my_allocator alloc; bit_vector v1 (alloc); v1.push_back (1); }

{ cout << "deques:" << endl; os_my_allocator alloc; deque d (alloc); d.push_back (42); }

{ cout << "lists:" << endl; os_my_allocator > alloc; list l (alloc); l.push_back (42); }

{ cout << "sets:" << endl; os_my_allocator > alloc; set > s (alloc); s.insert (42); }

{ cout << "maps" << endl; os_my_allocator > > alloc; map > m (alloc); m[4] = 2.0; }

return 0; }

is odd and positive"

#include #include

struct odd : public unary_function { odd () {} bool operator () (int n_) const { return (n_ % 2) == 1; } };

struct positive : public unary_function { positive () {} bool operator () (int n_) const { return n_ >= 0; } };

int array [6] = { -2, -1, 0, 1, 2, 3 };

int main () { binary_compose, odd, positive> b (logical_and (), odd (), positive ()); int* p = find_if (array, array + 6, b); if (p != array + 6) cout << *p << " is odd and positive" << endl;

return 0; }



#include #include

struct odd : public unary_function { odd () {} bool operator () (int n_) const { return (n_ % 2) == 1; } };

struct positive : public unary_function { 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 (), odd (), positive ())); if (p != array + 6) cout << *p << " is odd and positive" << endl; return 0; }

int array

#include #include

int array [3] = { 1, 2, 3 };

int main () { int* p = remove_if (array, array + 3, binder1st > (less (), 2)); for (int* i = array; i != p; i++) cout << *i << endl; return 0; }



#include #include

int array [3] = { 1, 2, 3 };

int main () { int* p = remove_if (array, array + 3, bind1st(less (), 2)); for (int* i = array; i != p; i++) cout << *i << endl; return 0; }

int array

#include #include

int array [3] = { 1, 2, 3 };

int main () { replace_if (array, array + 3, binder2nd > (greater (), 2), 4); for (int i = 0; i < 3; i++) cout << array[i] << endl; return 0; }



#include #include

int array [3] = { 1, 2, 3 };

int main () { replace_if (array, array + 3, bind2nd (greater (), 2), 4); for (int i = 0; i < 3; i++) cout << array[i] << endl; return 0; }

iterator i; for

#include #include

char* array [] = { "laurie", "jennifer", "leisa" };

int main () { vector names; copy (array, array + 3, back_insert_iterator > (names)); vector:: iterator i; for (i = names.begin (); i != names.end (); i++) cout << *i << endl; return 0; }



#include #include

char* array [] = { "laurie", "jennifer", "leisa" };

int main () { vector names; copy (array, array + 3, back_inserter (names)); vector:: iterator i; for (i = names.begin (); i != names.end (); i++) cout << *i << endl; return 0; }

did not find 42"

#include #include

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; }



#include #include #include

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; }

int array

#include #include

int array [4] = { 4, 9, 7, 1 };

int main () { sort (array, array + 4, binary_negate > (greater ())); for (int i = 0; i < 4; i++) cout << array[i] << endl; return 0; }



#include #include

int array [4] = { 4, 9, 7, 1 };

int main () { sort (array, array + 4, not2 (greater ())); for (int i = 0; i < 4; i++) cout << array[i] << endl; return 0; }

int main

#include #include

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; }

A string to be

#include #include #include

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; }



#include #include

int main () { vector v (10); for (int i = 0; i < v.size (); i++) v[i] = i; ostream_iterator iter (cout, " "); copy (v.begin (), v.end (), iter); cout << endl; return 0; }



#include #include

int main () { vector v1 (10); for (int i = 0; i < v1.size (); i++) v1[i] = i; vector v2 (10); copy (v1.begin (), v1.end (), v2.begin ()); ostream_iterator iter (cout, " "); copy (v2.begin (), v2.end (), iter); cout << endl; return 0; }



#include #include

int main () { typedef vector IVec; vector v1 (10); for (int loc = 0; loc < v1.size (); loc++) v1[loc] = loc; vector v2; insert_iterator i (v2, v2.begin ()); copy (v1.begin (), v1.end (), i); ostream_iterator outIter (cout, " "); copy (v2.begin (), v2.end (), outIter); cout << endl; return 0; }

Copyb

#include #include
int main () { vector v1 (10); for (int i = 0; i < v1.size (); i++) v1[i] = i; vector v2(v1.size ()); copy_backward (v1.begin (), v1.end (), v2.end ()); ostream_iterator iter (cout, " "); copy (v2.begin (), v2.end (), iter); cout << endl; return 0; }

int main

#include #include

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; }

int main

#include #include

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; }



#include #include

int main () { vector 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; }



#include #include

int odd (int a_) { return a_ % 2; }

int main () { vector 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; }



#include #include

int main () { deque 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; }

Divides

#include #include
int input [3] = { 2, 3, 4 };
int main () { int result = accumulate (input, input + 3, 48, divides ()); cout << "result = " << result << endl; return 0; }

can be inserted from

#include #include

int numbers[10] = { 0, 0, 1, 1, 2, 2, 2, 2, 3, 3 };

int main () { pair 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; }



#include #include

int main () { typedef vector IntVec; IntVec v (10); for (int i = 0; i < v.size (); i++) v[i] = i / 3; ostream_iterator iter (cout, " "); cout << "Within the collection:\n\t"; copy (v.begin (), v.end (), iter); pair 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; }



#include #include #include

char chars[] = "aabbccddggghhklllmqqqqssyyzz";

int main () { const unsigned count = sizeof (chars) - 1; ostream_iterator iter (cout); cout << "Within the collection:\n\t"; copy (chars, chars + count, iter); pair range; range = equal_range (chars, chars + count, 'q', less()); cout << "\ nq can be inserted from before index " << (range.first - chars) << " to before index " << (range.second - chars) << endl; return 0; }

numbers1 is equal to numbers2"

#include #include

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; }



#include #include

int main () { vector v1 (10); for (int i = 0; i < v1.size (); i++) v1[i] = i; vector 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; }



#include #include

bool values_squared ( int a_, int b_) { return (a_ * a_ == b_); }

int main () { vector v1 (10); vector 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; }

Equalto

#include #include
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 ()); for (int i = 0; i < 4; i++) cout << output[i] << endl; return 0; }

Compile this code without defining

#include

// Compile this code without defining the symbol OS_USE_EXCEPTIONS.

int main () { vector v; v.pop_back (); // Generates an empty object error. return 0; }



#include

// Compile this code with the symbol OS_USE_EXCEPTIONS defined.

int main () { vector v; try { v.pop_back (); // Generates an exception. } catch (const char* str) { cout << "Caught exception " << str << endl; } return 0; }



#include

// 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 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; }

int main

#include #include

int main () { vector v (10); fill (v.begin (), v.end (), 42); for (int i = 0; i < 10; i++) cout << v[i] << ' '; cout << endl; return 0; }

Found 25 at offset

#include #include

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; }



#include #include

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; }

bool odd

#include #include

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; }



#include #include

bool div_3 (int a_) { return a_ % 3 ? 0 : 1; }

int main () { typedef vector 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; }

iterator i; for

#include #include

char* array [] = { "laurie", "jennifer", "leisa" };

int main () { deque names; copy (array, array + 3, front_insert_iterator > (names)); deque:: iterator i; for (i = names.begin (); i != names.end (); i++) cout << *i << endl; return 0; }



#include #include

char* array [] = { "laurie", "jennifer", "leisa" };

int main () { deque names; copy (array, array + 3, front_inserter (names)); deque:: iterator i; for (i = names.begin (); i != names.end (); i++) cout << *i << endl; return 0; }

void print

#include #include

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; }



#include #include

void print_sqr (int a_) { cout << a_ * a_ << " "; }

int main () { vector 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; }

Number greater than

#include #include

bool bigger (int i_) { return i_ > 3; }

int main () { vectorv; 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; }



#include #include

bool bigger_than ( int x_, int y_) { return x_ > y_; }

int main () { vectorv; v.push_back (4); v.push_back (1); v.push_back (5); sort (v.begin (), v.end (), bigger_than); vector::iterator i; for (i = v.begin (); i != v.end (); i++) cout << *i << endl; return 0; }



#include #include

int main () { vectorv; v.push_back (4); v.push_back (1); v.push_back (5); sort (v.begin (), v.end (), greater ()); vector:: iterator i; for (i = v.begin (); i != v.end (); i++) cout << *i << endl; return 0; }

Руководство по стандартной библиотеке шаблонов STL

#include #include #include
int main () { int numbers[10]; generate (numbers, numbers + 10, rand); for (int i = 0; i < 10; i++) cout << numbers[i] << ' '; cout << endl; return 0; }

#include #include #include
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 v1 (10); Fibonacci generator; generate (v1.begin (), v1.end (), generator); ostream_iterator iter (cout, " "); copy (v1.begin (), v1.end (), iter); cout << endl; return 0; }

Руководство по стандартной библиотеке шаблонов STL

#include #include #include
int main () { vector v1 (10); generate_n (v1.begin (), v1.size (), rand); for (int i = 0; i < 10; i++) cout << v1[i] << ' '; cout << endl; return 0; }



#include #include #include
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 v1 (10); Fibonacci generator; generate_n (v1.begin (), v1.size (), generator); ostream_iterator iter (cout, " "); copy (v1.begin (), v1.end (), iter); cout << endl; return 0; }

Руководство по стандартной библиотеке шаблонов STL

#include #include
int array [4] = { 3, 1, 4, 2 };
int main () { sort (array, array + 4, greater_equal ()); for (int i = 0; i < 4; i++) cout << array[i] << endl; return 0; }

Руководство по стандартной библиотеке шаблонов STL

#include #include
int array [4] = { 3, 1, 4, 2 };
int main () { sort (array, array + 4, greater ()); for (int i = 0; i < 4; i++) cout << array[i] << endl; return 0; }

numbers1 does not include numbers3"

#include #include

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; }



#include #include

int main () { vector v1(10); vector 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; }



#include #include #include

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 v1(nameSize); for (int i = 0; i < v1.size (); i++) { v1[i] = names[i]; } vector 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; }

int main

#include #include

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; }



#include #include

int main () { vector v1(10); for (int i = 0; i < v1.size (); i++) v1[i] = (v1.size () - i - 1) % 5; ostream_iterator iter (cout, " "); copy (v1.begin (), v1.end (), iter); cout << endl; inplace_merge (v1.begin (), v1.begin () + 5, v1.end (), greater()); copy (v1.begin (), v1.end (), iter); cout << endl; return 0; }

int result; result

#include #include #include

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; }



#include #include #include

int main () { vector v1 (3); vector v2 (v1.size ()); for (int i = 0; i < v1.size (); i++) { v1[i] = i + 1; v2[i] = v1.size () - i; } ostream_iterator 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; }



#include #include #include

int add ( int a_, int b_) { return a_ + b_; }

int mult (int a_, int b_) { return a_ * b_; }

int main () { vector v1 (3); vector v2 (v1.size ()); for (int i = 0; i < v1.size (); i++) { v1[i] = i + 1; v2[i] = v1.size () - i; } ostream_iterator 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; }

iterator j; for

#include #include

char* array1 [] = { "laurie", "jennifer", "leisa" }; char* array2 [] = { "amanda", "saskia", "carrie" };

int main () { deque names (array1, array1 + 3); deque::iterator i = names.begin () + 2; copy (array2, array2 + 3, insert_iterator > (names, i)); deque:: iterator j; for (j = names.begin (); j != names.end (); j++) cout << *j << endl; return 0; }



#include #include

char* array1 [] = { "laurie", "jennifer", "leisa" }; char* array2 [] = { "amanda", "saskia", "carrie" };

int main () { deque names (array1, array1 + 3); deque::iterator i = names.begin () + 2; copy (array2, array2 + 3, inserter (names, i)); deque:: iterator j; for (j = names.begin (); j != names.end (); j++) cout << *j << endl; return 0; }

int main

#include #include

int main () { int numbers[10]; iota (numbers, numbers + 10, 42); for (int i = 0; i < 10; i++) cout << numbers[i] << ' '; cout << endl; return 0; }

Null terminate buffer. cout

#include #include

int main () { char buffer [100]; int i = 0; cin.unsetf (ios::skipws); // Disable white-space skipping. cout << "Please enter a string: "; istream_iterator s (cin); while (*s != '\n') buffer[i++] = *s++; buffer[i] = '\0'; // Null terminate buffer. cout << "read " << buffer << endl; return 0; }



#include #include #include

typedef vector Line;

void printLine (const Line* line_) { vector::const_iterator i; for (i = line_->begin (); i != line_->end (); i++) cout << *i; cout << endl; }

int main () { Line buffer; vector lines; ifstream s ("data.txt"); s.unsetf (ios::skipws); // Disable white-space skipping. istream_iterator it1 (s); // Position at start of file. istream_iterator 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 ()); cout << "Read " << lines.size () << " lines" << endl; vector::iterator j; for (j = lines.begin (); j != lines.end (); j++) printLine (*j); release (lines.begin (), lines.end ()); // Release memory. return 0; }

Vector of character strings.

#include #include

int main () { vector v; // Vector of character strings. v.push_back ((char*) "zippy"); // First element. v.push_back ((char*) "motorboy"); // Second element. vector::iterator i = v.begin (); // Position at end. for (i = v.begin (); i != v.end (); i++) cout << *i << endl; // Display item. return 0; }



#include #include

void print (const vector& v_) { vector::const_iterator i; for (i = v_.begin (); i != v_.end (); i++) cout << *i << endl; }

int main () { vector v; // Vector of character strings. v.push_back ((char*) "zippy"); v.push_back ((char*) "motorboy"); print (v); return 0; }



#include #include

int main () { vector v; // Vector of character strings. v.push_back ((char*) "zippy"); // First element. v.push_back ((char*) "motorboy"); // Second element. vector::reverse_iterator i; for (i = v.rbegin (); i != v.rend (); i++) cout << *i << endl; // Display item. return 0; }



#include #include

int main () { vector v; // Empty vector of integers. v.push_back (1); v.push_back (2); v.push_back (3); // Position immediately after last item. vector::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; }

int main

#include #include

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; }



#include #include

int main () { vector v1 (6); iota (v1.begin (), v1.end (), 0); iter_swap (v1.begin (), v1.begin () + 3); ostream_iterator iter (cout, " "); copy (v1.begin (), v1.end (), iter); cout << endl; return 0; }

Less

#include #include
int array [4] = { 3, 1, 4, 2 };
int main () { sort (array, array + 4, less ()); for (int i = 0; i < 4; i++) cout << array[i] << endl; return 0; }

Lesseq

#include #include
int array [4] = { 3, 1, 4, 2 };
int main () { sort (array, array + 4, less_equal ()); for (int i = 0; i < 4; i++) cout << array[i] << endl; return 0; }

const unsigned size

#include #include

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; }



#include #include

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()); if (before) cout << n1 << " is after " << n2 << endl; else cout << n2 << " is after " << n1 << endl; return 0; }

int array1

#include #include

int array1 [] = { 9, 16, 36 }; int array2 [] = { 1, 4 };

int main () { list l1 (array1, array1 + 3); list l2 (array2, array2 + 2); list::iterator i1 = l1.begin (); l1.splice (i1, l2); list::iterator i2 = l1.begin (); while (i2 != l1.end ()) cout << *i2++ << endl; return 0; }



#include #include

int array1 [] = { 1, 16 }; int array2 [] = { 4, 9 };

int main () { list l1 (array1, array1 + 2); list l2 (array2, array2 + 2); list::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; }



#include #include

char array [] = { 'x', 'l', 'x', 't', 's', 's' };

int main () { list str (array, array + 6); list:: 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; }



#include #include

int array1 [] = { 1, 3, 6, 7 }; int array2 [] = { 2, 4 };

int main () { list l1 (array1, array1 + 4); list l2 (array2, array2 + 2); l1.merge (l2); for (list::iterator i = l1.begin (); i != l1.end (); i++) cout << *i; cout << endl; return 0; }

Logicand

#include #include
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 ()); for (int i = 0; i < 4; i++) cout << output[i] << endl; return 0; }

Logicnot

#include #include
bool input [7] = { 1, 0, 0, 1, 1, 1, 1 };
int main () { int n = 0; count_if (input, input + 7, logical_not (), n); cout << "count = " << n << endl; return 0; }

Logicor

#include #include
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 ()); for (int i = 0; i < 4; i++) cout << output[i] << endl; return 0; }

n3 can be inserted at

#include #include

int main () { vector 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; }



#include #include #include

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; }

Store mappings between roman numerals

#include #include

int main () { typedef map > 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 p; p = m.insert (pair ('c', 100)); if (p.second) cout << "First insertion successful" << endl; p = m.insert (pair ('c', 100)); if (p.second) cout << "Second insertion successful" << endl; else cout << "Existing pair " << (*(p.first)).first << " -> " << (*(p.first)).second << endl; return 0; }

int main

#include #include

int main () { cout << max (42, 100) << endl; return 0; }



#include #include #include

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; }

int main

#include #include

int numbers[6] = { 4, 10, 56, 11, -42, 19 };

int main () { cout << *max_element (numbers, numbers + 6) << endl; return 0; }



#include #include #include

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; }

int main

#include #include

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; }



#include #include

int main () { vector v1 (5); vector v2 (v1.size ()); iota (v1.begin (), v1.end (), 0); iota (v2.begin (), v2.end (), 3); vector result (v1.size () + v2.size ()); merge (v1.begin (), v1.end (), v2.begin (), v2.end (), result.begin ()); ostream_iterator 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; }



#include #include

int main () { vector v1 (5); vector v2 (v1.size ()); for (int i = 0; i < v1.size (); i++) { v1[i] = 10 - i; v2[i] = 7 - i; } vector result (v1.size () + v2.size ()); merge (v1.begin (), v1.end (), v2.begin (), v2.end (), result.begin (), greater() ); ostream_iterator 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; }

int main

#include #include

int main () { cout << min (42, 100) << endl; return 0; }



#include #include #include

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; }

int main

#include #include

int numbers[6] = { -10, 15, -100, 36, -242, 42 };

int main () { cout << *min_element (numbers, numbers + 6) << endl; return 0; }



#include #include #include

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; }

Minus

#include #include
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 ()); for (int i = 0; i < 4; i++) cout << output[i] << endl; return 0; }

n1 and n2 are the

#include #include

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 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; }



#include #include

int main () { typedef vector IntVec; IntVec v1 (10); IntVec v2 (v1.size ()); iota (v1.begin (), v1.end (), 0); iota (v2.begin (), v2.end (), 0); pair 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; }



#include #include #include

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 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; }

int main

#include #include

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; }



#include #include

int numbers[6] = { 5, 10, 4, 13, 11, 19 };

int main () { make_heap (numbers, numbers + 6, greater ()); for (int i = 6; i >= 1; i--) { cout << numbers[0] << endl; pop_heap (numbers, numbers + i, greater ()); } return 0; }

Loop until end is reached.

#include #include

int main () { typedef multimap > mmap; mmap m; cout << "count ('X') = " << m.count ('X') << endl; m.insert (pair ('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; }



#include #include

typedef multimap > mmap;

typedef pair 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; }

Modulus

#include #include
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 ()); for (int i = 0; i < 4; i++) cout << output[i] << endl; return 0; }

mset s; cout

#include #include

int main () { typedef multiset > 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 >::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; }



#include #include

char* names [] = { "dave", "alf", "chas", "bob", "ed", "chas" };

int main () { typedef multiset mset; mset s; s.insert (names, names + 6); for (mset::iterator i = s.begin (); i != s.end (); i++) cout << *i << endl; return 0; }



#include #include

int array [] = { 3, 6, 1, 2, 3, 2, 6, 7, 9 };

int main () { multiset > s (array, array + 9); multiset >::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; }



#include #include

int array [] = { 3, 6, 1, 2, 3, 2, 6, 7, 9 };

int main () { typedef multiset > mset; mset s (array, array + 9); pair p = s.equal_range (3); cout << "lower bound = " << *(p.first) << endl; cout << "upper bound = " << *(p.second) << endl; return 0; }



#include #include

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 fn_type; typedef multiset 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; }

Negate

#include #include
int input [3] = { 1, 2, 3 };
int main () { int output[3]; transform (input, input + 3, output, negate ()); for (int i = 0; i < 3; i++) cout << output[i] << endl; return 0; }

Nequal

#include #include
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 ()); for (int i = 0; i < 4; i++) cout << output[i] << endl; return 0; }

int main

#include #include

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; }



#include #include

int main () { vector v1 (3); iota (v1.begin (), v1.end (), 0); ostream_iterator 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; }

int main

#include #include

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; }



#include #include #include

int main () { vector v1 (10); for (int i = 0; i < v1.size (); i++) v1[i] = rand () % 10; ostream_iterator 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; }



#include #include #include

int main () { vector v1 (10); for (int i = 0; i < v1.size (); i++) v1[i] = rand () % 10; ostream_iterator iter (cout, " "); copy (v1.begin (), v1.end (), iter); cout << endl; nth_element (v1.begin (), v1.begin () + v1.size () / 2, v1.end (), greater()); copy (v1.begin (), v1.end (), iter); cout << endl; return 0; }

Ostmit

#include #include
int array [] = { 1, 5, 2, 4 };
int main () { char* string = "hello"; ostream_iterator it1 (cout); copy (string, string + 5, it1); cout << endl; ostream_iterator it2 (cout); copy (array, array + 4, it2); cout << endl; return 0; }

int main

#include #include

int main () { pair p = make_pair (1, 10); cout << "p.first = " << p.first << ", p.second = " << p.second << endl; return 0; }



#include #include

int main () { pair p = make_pair (1, 10); cout << "p.first = " << p.first << ", p.second = " << p.second << endl; return 0; }



#include #include

int main () { pair p = make_pair (1, 10); cout << "p.first = " << p.first << endl; cout << "p.second = " << p.second << endl; return 0; }

int main

#include #include

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; }



#include #include #include

int main () { vector v1 (10); for (int i = 0; i < v1.size (); i++) v1[i] = rand () % 10; ostream_iterator 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; }



#include #include #include

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 v1 (nameSize); for (int i = 0; i < v1.size (); i++) v1[i] = names[i]; ostream_iterator 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; }

int main

#include #include

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; }



#include #include #include

int main () { vector v1 (10); for (int i = 0; i < v1.size (); i++) v1[i] = rand () % 10; vector result (5); ostream_iterator 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; }



#include #include #include

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 v1 (nameSize); for (int i = 0; i < v1.size (); i++) v1[i] = names[i]; ostream_iterator iter (cout, " "); copy (v1.begin (), v1.end (), iter); cout << endl; vector 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; }

int main

#include #include

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; }

int main

#include #include

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; }



#include #include

int main () { vector v1 (10); iota (v1.begin (), v1.end (), 0); vector v2 (v1.size()); partial_sum (v1.begin (), v1.end (), v2.begin ()); ostream_iterator iter (cout, " "); copy (v1.begin (), v1.end (), iter); cout << endl; copy (v2.begin (), v2.end (), iter); cout << endl; return 0; }



#include #include

int main () { vector v1 (5); iota (v1.begin (), v1.end (), 1); vector v2 (v1.size()); partial_sum (v1.begin (), v1.end (), v2.begin (), times()); ostream_iterator iter (cout, " "); copy (v1.begin (), v1.end (), iter); cout << endl; copy (v2.begin (), v2.end (), iter); cout << endl; return 0; }

int main

#include #include

int main () { vector 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 iter (cout, " "); copy (v.begin (), v.end (), iter); cout << endl;

return 0; }



#include #include

int main () { vector v;

v.push_back (1); v.push_back (20); v.push_back (4); make_heap (v.begin (), v.end (), greater ());

v.push_back (7); push_heap (v.begin (), v.end (), greater ());

sort_heap (v.begin (), v.end (), greater ()); ostream_iterator iter (cout, " "); copy (v.begin (), v.end (), iter); cout << endl;

return 0; }

Plus

#include #include
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 (), times ()); cout << "total = " << total << endl; return 0; }

int main

#include #include

int main () { priority_queue, less > q; q.push (42); q.push (101); q.push (69); while (!q.empty ()) { cout << q.top () << endl; q.pop (); } return 0; }



#include #include

int main () { priority_queue, 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; }

int main

#include #include

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; }



#include #include

int main () { vector v1 (3); iota (v1.begin (), v1.end (), 0); ostream_iterator 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; }



#include #include

int main () { vector v1 (3); iota (v1.begin (), v1.end (), 0); ostream_iterator iter (cout, " "); copy (v1.begin (), v1.end (), iter); cout << endl; for (int i = 0; i < 9; i++) { prev_permutation (v1.begin (), v1.end (), greater()); copy (v1.begin (), v1.end (), iter); cout << endl; } return 0; }

int less_10

#include #include

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; }



#include #include #include

int main () { vector v1 (10); for (int i = 0; i < v1.size (); i++) v1[i] = rand () % 20; ostream_iterator iter (cout, " "); copy (v1.begin (), v1.end (), iter); cout << endl; partition (v1.begin (), v1.end (), bind2nd(less(), 11)); copy (v1.begin (), v1.end (), iter); cout << endl; return 0; }

int x_, int y_)

#include #include

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 (sum)); for (int i = 0; i < 4; i++) cout << output[i] << endl; return 0; }



#include #include

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; }

bool even

#include #include

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 (even)); if (p != array + 3) cout << *p << " is even" << endl; return 0; }



#include #include

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; }

int main

#include #include

int main () { queue > q; q.push (42); q.push (101); q.push (69); while (!q.empty ()) { cout << q.front () << endl; q.pop (); } return 0; }

Rawiter

#include #include
class X { public: X (int i_ = 0) : i (i_) {} operator int () const { return i; }
private: int i; };
int main () { os_heap_allocator a; // Allocate (but do not construct) storage for 5 elements. os_heap_allocator::pointer p = a.allocate (5); raw_storage_iterator r (p); for (int i = 0; i < 5; i++) *r++ = X (i); for (i = 0; i < 5; i++) cout << *p++ << endl; return 0; }

based objects. return 0;

#include #include

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 v; v.push_back (new X (2)); v.push_back (new X (1)); v.push_back (new X (4)); vector::iterator i; for (i = v.begin (); i != v.end (); i++) cout << *(*i) << endl; release (v.begin (), v.end ()); // Delete heap- based objects. return 0; }



#include #include

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 v; v.push_back (new X (2)); v.push_back (new X (1)); v.push_back (new X (4)); vector::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; }

int main

#include #include

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; }

bool odd

#include #include

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; }

bool odd

#include #include

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; }

int main

#include #include

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; }

bool odd

#include #include

bool odd (int a_) { return a_ % 2; }

int main () { vector v1 (10); for (int i = 0; i < v1.size (); i++) v1[i] = i % 5; ostream_iterator iter (cout, " "); copy (v1.begin (), v1.end (), iter); cout << endl; vector 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; }

int main

#include #include

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; }



#include #include

int main () { vector v1 (10); for (int i = 0; i < v1.size (); i++) v1[i] = i % 5; ostream_iterator 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; }

int main

#include #include

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; }

bool odd

#include #include

bool odd (int a_) { return a_ % 2; }

int main () { vector 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; }

int array

#include #include

int array [] = { 1, 5, 2, 3 };

int main () { list v (array, array + 4); reverse_bidirectional_iterator::iterator, int, list::reference, list::difference_type> r (v.end ()); while (r != v.begin ()) cout << *r++ << endl; return 0; }



#include #include

int array [] = { 1, 5, 2, 3 };

int main () { list v (array, array + 4); list:: reverse_iterator r; for (r = v.rbegin (); r != v.rend (); r++) cout << *r << endl; return 0; }

int main

#include #include

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; }

int main

#include #include

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; }

int array

#include #include

int array [] = { 1, 5, 2, 3 };

int main () { vector v (array, array + 4); stl_reverse_iterator::iterator, int, vector::reference, vector::difference_type> r (v.end ()); while (r != v.begin ()) cout << *r++ << endl; return 0; }



#include #include

int array [] = { 1, 5, 2, 3 };

int main () { vector v (array, array + 4); vector:: reverse_iterator r; for (r = v.rbegin (); r != v.rend (); r++) cout << *r << endl; return 0; }

int main

#include #include

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; }



#include #include

int main () { vector v1(10); iota (v1.begin (), v1.end (), 0); ostream_iterator 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; }



#include #include #include

class MyRandomGenerator { public: unsigned long operator () (unsigned long n_); };

unsigned long MyRandomGenerator::operator () (unsigned long n_) { return rand () % n_; }

int main () { vector v1(10); iota (v1.begin (), v1.end (), 0); ostream_iterator 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; }

int main

#include #include

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; }



#include #include

int main () { vector v1 (10); iota (v1.begin (), v1.end (), 0); ostream_iterator 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 iter (cout, " "); copy (v1.begin (), v1.end (), iter); cout << endl; } cout << endl; return 0; }

int main

#include #include

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; }



#include #include

int main () { vector v1 (10); iota (v1.begin (), v1.end (), 0); ostream_iterator iter (cout, " "); copy (v1.begin (), v1.end (), iter); cout << endl; vector v2 (v1.size ()); for (int i = 0; i < v1.size (); i++) { rotate_copy (v1.begin (), v1.begin () + i, v1.end (), v2.begin ()); ostream_iterator iter (cout, " "); copy (v2.begin (), v2.end (), iter); cout << endl; } cout << endl; return 0; }

v3 not contained in v1"

#include #include

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; }



#include #include

int main () { typedef vector IntVec; IntVec v1 (10); iota (v1.begin (), v1.end (), 0); IntVec v2 (3); iota (v2.begin (), v2.end (), 50); ostream_iterator 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; }



#include #include #include

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 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; }

int main

#include #include

int main () { set > 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; }



#include #include

int main () { set > s; pair >::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; }

int main

#include #include

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; }



#include #include

int main () { vector v1 (10); iota (v1.begin (), v1.end (), 0); vector v2 (10); iota (v2.begin(), v2.end (), 7); ostream_iterator 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; }



#include #include #include

char* word1 = "ABCDEFGHIJKLMNO"; char* word2 = "LMNOPQRSTUVWXYZ";

int main () { ostream_iterator 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()); cout << endl; return 0; }

int main

#include #include

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; }



#include #include

int main () { vector v1 (10); iota (v1.begin (), v1.end (), 0); vector v2 (10); iota (v2.begin(), v2.end (), 7); ostream_iterator 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; }



#include #include #include

char* word1 = "ABCDEFGHIJKLMNO"; char* word2 = "LMNOPQRSTUVWXYZ";

int main () { ostream_iterator 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()); cout << endl; return 0; }

int main

#include #include

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; }



#include #include #include

char* word1 = "ABCDEFGHIJKLMNO"; char* word2 = "LMNOPQRSTUVWXYZ";

int main () { ostream_iterator 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()); cout << endl; return 0; }

int main

#include #include

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; }



#include #include

int main () { vector v1 (10); iota (v1.begin (), v1.end (), 0); vector v2 (10); iota (v2.begin(), v2.end (), 7); ostream_iterator 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; }



#include #include #include

char* word1 = "ABCDEFGHIJKLMNO"; char* word2 = "LMNOPQRSTUVWXYZ";

int main () { ostream_iterator 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()); cout << endl; return 0; }

int main

#include #include

int array[] = { 1, 50, -10, 11, 42, 19 };

int main () { int count = sizeof (array) / sizeof (array[0]); ostream_iterator iter (cout, " "); cout << "before: "; copy (array, array + count, iter); cout << "\nafter: "; sort (array, array + count, greater()); copy (array, array + count, iter); cout << endl; return 0; }

int main

#include #include

int main () { stack > s; s.push (42); s.push (101); s.push (69); while (!s.empty ()) { cout << s.top () << endl; s.pop (); } return 0; }



#include #include

int main () { stack > s; s.push (42); s.push (101); s.push (69); while (!s.empty ()) { cout << s.top () << endl; s.pop (); } return 0; }

bool less_10

#include #include

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; }



#include #include #include

int main () { vector v1 (10); for (int i = 0; i < v1.size (); i++) v1[i] = rand () % 20; ostream_iterator iter (cout, " "); copy (v1.begin (), v1.end (), iter); cout << endl; stable_partition (v1.begin (), v1.end (), bind2nd(less(), 11)); copy (v1.begin (), v1.end (), iter); cout << endl; return 0; }

int main

#include #include

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; }



#include #include #include

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; }

int main

#include #include

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; }

int main

#include #include #include

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; }

Times

#include #include
int input [4] = { 1, 5, 7, 2 };
int main () { int total = accumulate (input, input + 4, 1, times ()); cout << "total = " << total << endl; return 0; }

int negate_int

#include #include

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; }



#include #include #include

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 iter (cout); transform (n, n + count, trans, iter, map_char); cout << endl; return 0; }

double x_) const

#include #include #include

struct square_root : public unary_function { 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 ())); for (int i = 0; i < 3; i++) cout << output[i] << endl; return 0; }



#include #include #include

struct square_root : public unary_function { 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 ())); for (int i = 0; i < 3; i++) cout << output[i] << endl; return 0; }

int n_) const

#include #include

struct odd : public unary_function { 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 ())); if (p != array + 3) cout << *p << endl; return 0; }



#include #include

struct odd : public unary_function { 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; }

int main

#include #include

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; }



#include #include #include

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 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; }

int main

#include #include

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; }



#include #include #include

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 iter (cout); copy (labels, labels + count, iter); cout << endl; unique (labels, labels + count, str_equal); copy (labels, labels + count, iter); cout << endl; return 0; }

n3 can be inserted at

#include #include

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; }



#include #include #include

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; }

Empty vector of integers. cout

#include #include

int main () { vector 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; }



#include #include

void print (vector& vector_) { for (int i = 0; i < vector_.size (); i++) cout << vector_[i] << " "; cout << endl; }

int main () { vector v1; // Empty vector of doubles. v1.push_back (32.1); v1.push_back (40.5); vector 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; }



#include #include

int main () { vector v1; // Empty vector of characters. v1.push_back ('h'); v1.push_back ('i'); cout << "v1 = " << v1[0] << v1[1] << endl; vector 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; }



#include #include

int main () { vector 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; }



#include #include

int array [] = { 1, 4, 9, 16 };

int main () { vector v (array, array + 4); for (int i = 0; i < v.size (); i++) cout << "v[" << i << "] = " << v[i] << endl; return 0; }



#include #include

int array [] = { 1, 4, 9, 16, 25, 36 };

int main () { vector 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; }



#include #include

int array1 [] = { 1, 4, 25 }; int array2 [] = { 9, 16 };

int main () { vector 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; }



#include #include

int main () { vector 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; }




    Биржевая торговля: Механические торговые системы - Создание - Программирование

• Механические торговые системы (МТС)
  
• Технический анализ и МТС
  
• Разработка механических торговых систем
  
• Механические торговые системы
  
• GNU механические торговые системы
  
  
• Тестирование механических торговых систем
  
• MetaStock - механические торговые системы
  
• Omega Trade Station - механические торговые системы
  
  
• МТС - обзор языков программирования
  
• Си для механических торговых систем
  
• C# для механических торговых систем
  
• C++ для механических торговых систем
  
• Borland C++ для механических торговых систем
  
  
• C++ Builder для механических торговых систем
  
• Visual C++ для механических торговых систем
  

---

---