Показанное ниже объявление создает пустую коллекцию вещественных чисел: deque<float> соП;

Функция push front() предназначена для вставки элементов;

coll.push front(1*l.1);

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

6.6 5.5 4.4 3.3 2.2 1.1

Элементы также могут вставляться в конец дека функцией push back(). Функция push front() не поддерживается векторами, поскольку в этом типе контейнера она будет выполняться слишком долго (при вставке элемента в начало вектора придется переместить все существующие элементы). Обычно контейнеры STL содержат только функции, обеспечивающие хорошую эффективность (то есть выполняемые с постоянной или логарифмической сложностью). Это сделано для того, чтобы предотвратить случайные вызовы неэффективных функций.

Списки

Класс list реализуется в виде двусвязного списка элементов. Это означает, что каждый элемент списка занимает отдельный блок памяти и содержит ссылки на предыдущий и следующий элементы. Списки не поддерживают произвольный доступ к элементам. Например, чтобы обратиться к десятому элементу, необходимо сначала перебрать первые девять элементов по цепочке ссылок. Тем не менее переход к следующему или предыдущему элементу выполняется с постоянным временем, поэтому обобщенная операщ-ш доступа к произвольному элементу имеет линейную сложность (среднее расстояние перехода пропорционально количеству элементов). Это гораздо хуже, чем амортизированное постоянное время доступа, обеспечиваемое векторами и деками.

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

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

stl/llstl.cpp #1nclude <iostreani> #include <list> using namespace std;

int mainO {

I1st<char> coll; Список с символьными зленентами

Присоединение элементов от а до 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, на которой речь пойдет об итераторах.

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

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