Каждый класс контейнера, реализованный в STL, описывает набор типов, связанных с контейнером. При написании собственных контейнеров следует придерживаться этой же практики. Вот список наиболее важных типов:

• value_type — тип элемента

• size_type — тип для хранения числа элементов (обычно size_t)

• iterator — итератор для элементов контейнера

• key_type — тип ключа (в ассоциативном контейнере)

Помимо типов можно выделить набор функций, которые реализует почти каждый контейнер в STL. Они не требуются для взаимодействия с алгоритмами, но их реализация улучшает взаимозаменяемость контейнеров в прграмме. Если, к примеру, какой-то контейнер реализует набор характерных для списка функций, то его можно будет вставить в программу вместо списка, изменив в ней всего одну строчку. Список основных функций приведён в таблице.

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

Каждый алгоритм использует итераторы определённого типа. Например, алгоритм простого поиска (find) просматривает элементы подряд, пока нужный не будет найден. Для такой процедуры вполне достаточно итератора ввода. С другой стороны, алгоритм более быстрого двоичного поиска (binary_search) должен иметь возможность переходить к любому элементу последовательности, и поэтому требует итератора с произвольным доступом. Вполне естественно, что вместо менее функционального итератора можно передать алгоритму более функциональный, но не наоборот.

Все стандартные алгоритмы описаны в файле algorithm, в пространстве имён std.

Помимо уже рассмотренных элементов в STL есть ряд второстепенных понятий, с которыми следует познакомиться.

Аллокатор (allocator) – это объект, отвечающий за распределение памяти для элементов контейнера. С каждым стандартным контейнером связывается аллокатор (его тип передаётся как один из параметров шаблона). Если какому-то алгоритму требуется распределять память для элементов, он обязан делать это через аллокатор. В этом случае можно быть уверенным, что распределённые объекты будут уничтожены правильно.

В состав STL входит стандартный класс allocator (описан в файле xmemory). Именно его по умолчанию используют все контейнеры, реализованные в STL. Однако никто не мешает вам реализовать собственный. Необходимость в этом возникает очень редко, но иногда это можно сделать из соображений эффективности или в отладочных целях.

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

Что такое CmpFn? Естественнее всего предположить, что это указатель на функцию. Однако вызов функции по указателю – операция довольно долгая. В нашем примере вызов займёт больше времени, чем выполнение всех остальных инструкций в функции max. Проблема в том, что при таком подходе к передаче функции её не удаётся объявить как встроенную (inline).

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

Таким образом, объекты-функции используются в целях оптимизации

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

Предикаты широко используются в STL. Унарные предикаты используются для задания подмножества элементов контейнера, удовлетворяющих некоторому условию. Например, функция count_if считает количество элементов последовательности, для которых заданный унарный предикат возвращает true. Бинарные предикаты чаще всего используются для сравнения двух элементов.

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