Присоединение элементов от а до z for (char с=а: c<=z: ++с) { coll .push back(c):

/* Вывод содержимого списка

* - пока в списке остаются элементы.

* - вывести и удалить первый элемент. */

while (! coll .emptyO) {

cout « coll-frontC) « ; coll.pop frontC);

cout « endl:

Как обычно, заголовочный файл <list> используется для определения коллекции типа list, содержащей символьные элементы:

list <char> coll;

Функция emptyO возвращает логический признак отсутствия элементов в контейнере. Цикл выполняется до тех пор, пока функция возврашает false(), то есть пока контейнер содержит элементы:

while С! coll .emptyO) { }

В теле цикла функция front() возвращает первый элемент: cout « coll .frontо « :

Функция pop front() удаляет первый элемент из контейнера; соП .pop frontO;

Учтите, что функция pop front() не возвращает удаляемый элемент, поэтому эти две команды не удается заменить одной командой.

Результат выполнения программы зависит от кодировки. В кодировке ASCII он выглядит так:

abcdefghijklmnop rstuvwxyz

Конечно, процедура «вывода» содержимого цикла, которая выводит и удаляет первый элемент, выглядит несколько странно - обычно в цикле перебираются все элементы. Тем не менее списки не поддерживают произвольный доступ к элементам, поэтому оператор [] будет работать недостаточно эффективно. Существует другой способ перебора и вывода элементов, основанный на приме-

В других кодировках результат может содержать символы, не являющиеся буквами, и даже быть пустым (если т» в этой кодировке ие больше «а*»-).

нении итераторов. Пример будет приведен после знакомства с итераторами (а если вам не терпится, обратитесь к с. 97).

Строки

Строки также могут использоваться в качестве контейнеров STL. Под строками подразумеваются объекты строковых классов С++ (basic string<>, string и wstring), представленные в главе И. В целом строки аналогичны векторам, но их элементы всегда относятся к символьному тину. Дополнительная информация представлена на с. 480,

Обычные массивы

Другая разновидность контейнеров является не классом, а одним из типов базового языка С и С++: речь идет об обычных массивах со статическим или динамическим размером. Обычные массивы не относятся к контейнерам STL, поскольку они не поддерживают функции типа size() или emptyO, однако архитектура STL позволяет вызывать для них алгоритмы. Это особенно удобно при обработке статических массивов в списках инициализации.

Принципы работы с массивами хорошо известны, нова лишь возможность использования массивов с алгоритмами. Данная тема рассматривается на с. 223.

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

Ассоциативные контейнеры

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

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

Ниже перечислены стандартные ассоциативные контейнеры, определенные в STL. Для обращения к их элементам применяются итераторы, поэтому примеры откладываются до с. 96, на которой речь пойдет об итераторах.

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

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

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

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

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

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

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

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

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

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

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

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