5.4. Контейнеры. Алгоритмы. Итераторы

В стандартной библиотеке помимо «pair» и «string» присутствуют и другие классы, называемые контейнерами. Они предназначены для хранения определенных структур данных, при этом тип самих данных может быть любым. Наличие таких классов обусловлено неэффективностью применения встроенных средств.

Контейнеры делятся на последовательные, адаптивные и ассоциативные. В последовательных контейнерах элементы расположены в ряд и связаны меж собой позицией. К таким контейнерам относятся:

• Вектор – «vector» (динамически изменяемый массив).

• Список – «list» (связанный список).

• Очередь с двусторонним доступом – «deque» (вставка и выборка как с конца очереди, так и с начала).

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

• Очередь – «queue» (работает по принципу FIFO: первый вошел – первый вышел).

• Стек – «stack» (работает по принципу LIFO: последний вошел – первый вышел).

• Приоритетная очередь – «priority_queue» (элементы достигают выхода в соответствии со своими приоритетами).

В ассоциативные контейнерах элементы не располагаются последовательно, а хранятся в виде дерева. Доступ к ним осуществляется посредством ключей, модифицируемых самими контейнерами автоматически. К таким контейнерам относятся:

• Отображение – «map» (состоит из пар ключа и ассоциированного с ним значения).

• Мультиотображение – «multimap» (отображение с поддержкой одинаковых элементов).

• Множество – «set» (вырожденное отображение, в котором ключам не соответствуют никакие значения).

• Мультимножество – «multiset» (множество с поддержкой одинаковых элементов).

Каждый контейнер имеет свои встроенные методы.

Таблица 5.2. Указатели на элементы.

Название	Описание
begin()	Указывает на первый элемент
end()	Указывает на последний элемент
rbegin()	Указывает на первый элемент в обратном направлении
rend()	Указывает на последний элемент в обратном направлении

Таблица 5.3. Доступ к элементам.

Название	Описание
front()	Первый элемент
back()	Последний элемент
at()	Элемент с заданным индексом, с проверкой (не для списка)
[]	Элемент с заданным индексом, без проверки (не для списка)

Таблица 5.4. Операции со стеком и очередями.

Название	Описание
push_back()	Добавление в конец
pop_back()	Извлечение из конца
push_front()	Добавление в начало (только для списков и двусторонних очередей)
pop_front()	Извлечение из начала (только для списков и двусторонних очередей)

Таблица 5.5. Операции со списками.

Название	Описание
insert(a, c)	Вставка элемента a перед элементом в позиции c
insert(a, b, c)	Вставка b элементов a перед элементом в позиции c
erase(a)	Удаление элемента в позиции a
clear()	Очистка вектора

Таблица 5.6. Ассоциативные операции.

Название	Описание
[]	Элемент с заданным ключом (для контейнеров с уникальным ключом)
find()	Элемент с заданным ключом
lower_bound()	Поиск первого элемента с указанным ключом
upper_bound()	Поиск первого элемента с ключом, больше указанного
equal_range()	Поиск lower_bound() и upper_bound()
key_comp()	Копирование элемента с указанным ключом
value_comp()	Копирование элемента с указанным значением

Таблица 5.7. Другие операции.

Название	Описание
size()	Количество элементов
empty()	Проверка на пустоту
max_size()	Максимальный размер контейнера
resize()	Установка новой размерности
capacity()	Размер выделенной для вектора памяти
reserve()	Выделение для вектора памяти
swap()	Обмен векторов элементами
!=, ==, >, <, >=, <=, =	Операторы сравнения и оператор присвоения
=	Копирующее присваивание
assign(a, b)	Присвоение вектору a элементов b

Эффективная работа с разнообразными структурами данных происходит не только посредством простых встроенных в соответствующие классы методов, но и посредством обобщенных «algorithm» и численных «numeric» алгоритмов. Алгоритмы представляют из себя функции, выполняющие определенные действия над элементами контейнера. Они являются независимыми в том смысле, что могут применяться не только к определенным стандартным контейнерам, но и к разработанным пользователем.

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

Следует заметить, что итераторы механизм связывания со стандартными алгоритмами посредством итераторов применимо не только к контейнерам, но и к таким классам как «string».