В дополнение к таблице далее приводится еще несколько полезных практических реко\гендан;ий.

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

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

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

Как и во всех узловых контейнерах, итераторы списков остаются действительными до тех пор, пока элементы, на которые они ссылаются, остаются в контейнере. В векторах все итераторы, указатели и ссылки становятся недействительными при превышении емкости, а некоторые - при вставке и удалении элементов. Итераторы, указатели и ссылки в деках становятся недействительными при изменении размера контейнера.

О Если вам нужен контейнер с высоким уровнем безопасности исключений, когда любая операция либо завершается успешно, либо не вносит изменений, выбирайте список, но воздержитесь от выполнения присваивания и вызова функции sort(), а если исключения могут произойти при сравнении элементов - от вы.зова функций merge(), remove(), remove if() н unique() (см. с. 180). Можно также выбрать ассоциативные контейнеры (но без многоэлементной вставки, а если исключения могут произойти при копировании/присваи-вании критерия сравнения - без вызова функции swap()). Общие сведения об обработке исключений в STL приведены па с. 148. На с. 254 перечислены все контейнерные операции, предоставляющие особые гарантии в отношении исключений.

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

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

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

О Для работы с парами «ключ/значение» используется отображение или мультиотображение (нли их хэшированные версии, если они доступны).

О Если вам нужен ассоциативный массив, используйте отображение.

О Если вам нужен словарь, используйте мультиотображение.

Если нужно сортировать объекты по двум разным критериям, возникают проблемы. Допустим, вы хотите хранить объекты в порядке, указанном пользователем, но при этом предоставить средства поиска по другому критерию; как и при работе с базами данных, операции по двум и более критериям должны выполняться достаточно быстро. Вероятно, в такой ситуации стоит воспользоваться двумя множествами или отображениями, совместно использующими общие объекты с разнылн1 критериями сортировки. С другой стороны, хранение объектов в двух коллекциях - особая тема, которая рассматривается на с. 226.

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

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

Решение с использованием множества:

cont/sortset.cpp #1nclude <1ostream> linclude <str1ng> linclude <algorithin> linclude <set> using namespace std;

Int mainC)

Создание строкового множества * - инициализация словами, прочитанными из стандартного ввода */

set<string> coll (CistrediTi 1terator<string>Cc1n)).

Ci streamjterator<stri ng>C)));

Вывод всех элементов

copy Ccol 1 .beginC). coll.endO.

ostream iterator<str1ng>(cout. "\n"));

Решение с использованием вектора:

II cont/sortvec.cpp finclude <1ostream> finclude <string> finclude <algor1thm> finclude <vector> using namespace std:

Int mainC) {

/* Создание строкового вектора

* - инициализация словами, прочитанными из стандартного ввода */

vector<string> col 1((istream 1terator<string>(cin)).

f1stream 1terator<str1ng>C)));

Сортировка элементов

sort (coll.beginO, coll.endO):

Вывод всех злементов с подавлением дубликатов unique copy (coll.beginO. coll.endO,

ostream iterator<str1ng>(cout. "\n")):

Когда автор запустил обе программы в своей системе для тестового набора из 150 ООО строк, векторная версия работала примерно иа 10 % быстрее. Включение вызова reserveO ускорило ее еще на 5 %. Если разрешить наличие дубликатов (использование типа multiset вместо set и вызов сору() вместо unique copy()), ситуация кардинально меняется: векторная версия работает еще на 40 % быстрее! Такие показатели нельзя считать типичными, однако они доказывают, что во многих случаях стоит опробовать разные варианты обработки элементов.

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

Гипы и функции контейнеров

В настоящем разделе подробно описаны различные контейнеры STL и все поддерживаемые ими операции. Типы и операции сгруппированы по функциональности. Для каждых типа и операции приводятся сигнатура, краткое описание н типы контейнеров, в которых они поддерживаются. Под обозначением контейнер понимается тип контейнера (вектор, дек, список, лшожество, мультимножество, отображение, мультиотображение или строка).