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

О Мультиотображенггя - то же, что и отображения, но с возможностью дублирования ключей. Это означает, что мультиотображение может содержать несколько элементов с одинаковыми ключами. Мультиотображение также может использоваться в качестве словаря - см. пример на с. 215.

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

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

Контейнерные адаптеры

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

О Стеки - контейнеры, элементы которых обрабатываются по принципу LIFO (последним прибыл, первым обслужен).

О Очереди - контейнеры, элементы которых обрабатываются по принципу FIFO (первым прибыл, первым обслужен). Иначе говоря, очередь представляет собой обычный буфер.

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

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

Итераторы

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

О * - получение элемента в текущей позиции итератора. Если элемент состоит из отдельных членов, для обращения к ним непосредственно через итератор используется оператор

О ++ - перемещение итератора к следующему элементу. Многие итераторы также поддерживают перемещение в обратном направлении, для чего используется оператор ~,

О == и != - проверка совпадений позиций, представленных двумя итераторами. О = - присваивание итератора (позиции элемента, на которую он ссылается).

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

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

О begin() - возвращает итератор, установленный в начало последовательности элементов контейнера. Началом считается позиция первого элемента (если on есть).

О end() - возвращает итератор, установленный в конец последовательности элементов контейнера. Концом считается позиция за последним элементом.

Итак, функции beginO и end() определяют полуоткрытый интервал, который содержит первый элемент, но выходит за пределы последнего элемента (рис. 5.3). Полуоткрытый интервал обладает двумя достоинствами:

О появляется простое условие завершения перебора в контейнере: цикл продолжается до тех пор, пока не будет достигнута позиция end();

О предотвращается специальная обработка пустых интервалов, поскольку в пустом интервале begin() совпадает с end().

На некоторых старых платформах итераторы еще не поддерживают оператор ->.

beginO

end О

Рис. 5.3. Функции beginQ и endQ

Следующий пример демонстрирует применение итераторов. В нем выводятся значения всех элементов списка (усовершенствованная версия примера со списками, приведенного на с. 92).

stl/list2,cpp include <1ostreafn> include <l1st> using namespace std:

int mainC)

list<char> coll:

Список с символьными элементами

Присоединение элементов от а до z

for (char с=а: c<=z: -н-с) ( coll,push backCc):

/* Вывод содержимого списка * - перебор всех элементов. */

list<char>::const iterator pos: for epos = coll ,begin(): pos -coll.endO: ++pos) { cout *pos :

cout endl:

После того как список создан и заполнен символами от а до z , все элементы выводятся в цикле for:

list<char>::const 1terator pos; for epos = coll.beginC): pos != coll.endC): ++pos) { cout *pos ;

Итератор pos объявляется непосредственно перед началом цикла. В объявлении выбирается тип итератора для обращения к элементам контейнерного класса без возможности модификации:

list<char>::const iterator pos: