жит три стандартных класса последовательных контейнеров: vector (вектор), deque (дек) и list (список).

О Ассоциативные контейнеры представляют собой отсортированные коллекции, в которых позиция элемента зависит от его значения по определенному критерию сортировки. После занесения шести элементов в коллекцию порядок их следования будет определяться только их значениями. Последовательность вставки значения не имеет. STL содержит три стандартных класса ассоциативных контейнеров: set (множество), multiset (мультимножество), тар (отображение) и multimap (мультиотображение).

Ассоциативный контейнер можно рассматривать как особую разновидность последовательного контейнера, поскольку сортированные коллекции упорядочиваются в соответствии с критерием сортировки. Такой подход вполне естествен для тех, кто работал с другими библиотеками классов коллекций (такими, как в Smalltalk или NIHCU), в которых сортированные коллекции были производными от упорядоченных коллекций. Однако не следует забывать, что типы коллекций STL полностью независимы друг от друга. Они имеют разные реализации и не являются производными друг от друга.

Автоматическая сортировка элементов в ассоциативных контейнерах не означает, что эти контейнеры специально предназначены для сортировки элементов. С таким же успехом можно отсортировать элементы последовательного контейнера. Основным достоинством автоматической сортировки является более высокая эффективность поиска. В частности, программист всегда может воспользоваться двоичным поиском, для которого характерна логарифмическая, а не линейная сложность. Это означает, что для поиска в коллекции из 1000 элементов в среднем понадобится всего 10 сравнений вместо 500 (см. с. 37). Таким образом, автоматическая сортировка является только (полезным) побочным эффектом реализации ассоциативного контейнера, спроектированного с расчетом на повышение эффективности.

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

Последовательные контейнеры

В STL поддерживаются следующие разновидности последовательных контейнеров: О векторы; О деки; О списки.

Библиотека NIHCL (National Institute of Healths Class Library) была одной нз первых библиотек классов, написанных на С++.

Кроме того, строки и обычные массивы тоже можно рассматривать как особые разновидности последовательных контейнеров.

Векторы

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

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

stl/vectorl.cpp #include <iostreani> #1nclude <vector> using namespace std;

int mainO (

vector<int> co1l; Вектор с целыми эленентани

Присоединение элементов со значениями от 1 до 6 for (int 1-1; i<*6: ++1) { coll.push backC1):

Вывод элементов, разделенных пробелами for (int 1-=0: 1<со11 .sl2e(); ++i) { cout coll[1] ;

cout endl;

Следующая директива включает заголовочный файл для работы с векторами;

#1nclude <vector>

Показанное ниже объявление создает вектор с элементами типа int: vector<int> coll:

Вектор не инициализируется, поэтому конструктор по умолчанию создает пустую коллекцию.

Функция push back() присоединяет элемент к контейнеру:

со]1.push back(1);

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

Эта функция присутствует во всех последовательных контейнерах. Функция size() возвращает количество элементов в контейнере:

for (1nt i-0; 1<со11.SizeO: ++i) { }

Эта функция поддерживается всеми контейнерными классами. Оператор индексирования [] возвращает один элемент вектора:

cout со11[1] :

В данном примере элементы записываются в стандартный выходной поток данных, поэтому результаты работы программы выглядят так:

12 3 4 5 6

Деки

Термин дек (deque) происходит от сокращения фразы double-ended queues (двусторонняя очередь). Дек представляет собой динамический массив, реализованный таким образом, что может расти в обоих направлениях. Таким образом, операции вставки элементов в конец и в начало коллекции выполняются очень быстро, а вставка в середину занимает больше времени, потому что требует перемещения элементов.

В следующем примере мы объявляем дек для вещественных чисел, вставляем в начало контейнера элементы от 1.1 до 6.6, а затем выводим значения элементов дека.

stl/dequel.cpp #include <iostream> #include <deque> using namespace std:

int mainO

deque<float> coll: Дек с вещественными элементами

Вставка в начало элементов со значениями от 1.1 до 6.6 for (int i=l; i<=6: ++i) {

coll.push front(i*l.l); Вставка в начало дека

Вывод элементов, разделенных пробелами for (int i=0: i<col 1.size(); ++i) { cout coll[i] :

cout endl:

Следующая директива включает заголовочный файл для работы с векторами: #include <deque>