Таблица 6,33. Характеристики контейнеров STL

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Int mainC)

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

set<string> coll(CistrediT iterator<string>Cc1n)).

Ci streaiTj terator<stri ng>C)));

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

copy (coll.beginC). coll.endO.

ostream iterator<string>(cout. \n ));