8.3. Классы-контейнеры

В STL определены два типа контейнеров – последовательности и ассоциативные контейнеры.

Встроенные массивы, строки string, векторы valarray (векторы, оптимизированные для численных расчетов) и битовые поля bitset содержат элементы и, следовательно, могут считаться контейнерами. Однако эти типы не являются полностью разработанными стандартными контейнерами. Если бы они являлись таковыми, это помешало бы их основному назначению.

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

bitset множество битов <bitset>

deque двусторонняя очередь <deque>

list линейный список <list>

map ассоциативный список для хранения пар ключ/значение, где с каждым ключом связано одно значение <map>

multimap с каждым ключом связано два или более значений <map>

multiset множество, в котором каждый элемент не обязательно уникален <set>

priority_queue очередь с приоритетом <queue>

queue очередь <queue>

set множество <set>

stack стек <stack>

vector динамический массив <vector>

Ключевая идея для стандартных контейнеров заключается в том, что, когда это представляется разумным, они должны быть логически взаимозаменяемыми. Пользователь может выбирать между ними, основываясь на соображениях эффективности и потребности в специализированных операциях. Например, если часто требуется поиск по ключу, можно воспользоваться map (ассоциативным массивом). С другой стороны, если преобладают операции, характерные для списков, можно воспользоваться контейнером list. Если добавление и удаление элементов часто производится в концы контейнера, следует подумать об использовании очереди queue, очереди с двумя концами deque, стека stack. По умолчанию пользователь должен использовать vector; он реализован, чтобы хорошо работать для самого широкого диапазона задач. Кроме того, пользователь может разработать дополнительные контейнеры, вписывающиеся в рамки стандартных контейнеров.

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

Поскольку имена типов элементов, входящих в объявление класса-шаблона, могут быть самыми разными, в классах-контейнерах с помощью ключевого слова typedef объявляются некоторые согласованные версии этих типов. Эта операция позволяет конкретизировать имена типов. Ниже перечислены имена этих типов.

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

reference тип ссылки на элемент контейнера.

const_reference тип константной ссылки на элемент контейнера

iterator тип итератора

const_iterator тип константного итератора

reverse_iterator тип обратного итератора

const_reverse_iterator тип константного обратного итератора

value_type тип хранящегося в контейнере значения.

allocator_type тип распределителя памяти.

key_type тип ключа в ассоциативных контейнерах

mapped_type тип отображенного значения в ассоциативных контейнерах

key_compare тип функции, которая сравнивает два ключа.

value_compare тип функции, которая сравнивает два значения

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

iterator begin() указывает на первый элемент

iterator end() указывает на элемент, следующий за последним

reverse_iterator begin() указывает на первый элемент в обратной последовательности

reverse_iterator rend() указывает на элемент, следующий за последним в обратной последовательности

Следующие компонентные функции контейнеров используют итераторы в качестве возвращаемого ссылки

reference front() ссылка на первый элемент

reference back() ссылка на последний элемент

reference operator[]() доступ по индексу без проверки

reference at() доступ по индексу с проверкой

Следующие компонентные функции контейнеров включают элементы в контейнер

insert() включает элемент (последовательность элементов) в контейнер

push_back() добавление х в конец

push_front() добавление нового первого элемента (только для списков и очередей с двумя концами)

Следующие компонентные функции контейнров удаляют элелементы из контейнера

pop_back() удаление последнего элемента

pop_front() удаление первого элемента (только для списков и очередей с двумя концами)

erase() удаление заданной последовательности элементов

clear() удаление всех элементов контейнера

Операция доступа к элементу контейнера по индексу

reference operator[](size_type pos);

Операции для ассоциативных контейнеров:

T& operator[](const key_type& k)

доступ к элементу с ключом k