На этом шаге мы приведем некоторые рекомендации по выбору контейнера.
Стандартная библиотека C++ содержит разные типы контейнеров, обладающие разными возможностями. Возникает вопрос: когда использовать тот или иной тип контейнера? В таблице 1 приводятся некоторые рекомендации. Однако эти общие утверждения не всегда согласуются с реальностью. Например, при малом количестве элементов фактор сложности можно не учитывать, потому что обработка малого количества элементов с линейной сложностью происходит быстрее, чем обработка большого количества элементов с логарифмической сложностью.
В дополнение к таблице далее приводится еще несколько полезных практических рекомендаций.
- По умолчанию выбирайте вектор. Этот контейнер имеет простейшую внутреннюю структуру и поддерживает
произвольный доступ. Этим обусловлена гибкость и универсальность доступа, а обработка данных часто выполняется достаточно быстро.
- Если вы собираетесь часто вставлять и/или удалять элементы в начале и в конце последовательности, выбирайте дек.
Кроме того, дек больше подходит в ситуациях, когда при удалении элементов обязательно должна освобождаться внутренняя память
контейнера. Элементы вектора обычно хранятся в одном блоке памяти, поэтому дек может содержать больше элементов за счет
использования нескольких блоков памяти.
- Если вы собираетесь часто вставлять, удалять и перемещать элементы в середине контейнера, возможно, вам стоит остановить
выбор на списке. Списки поддерживают специальные функции для перемещения элементов между контейнерами с постоянным временем.
Но учтите, что списки не обеспечивают произвольного доступа, поэтому обращение к элементам внутри списка выполняется
относительно медленно (если известно только начало списка).
Как и во всех узловых контейнерах, итераторы списков остаются действительными до тех пор, пока элементы, на которые они ссылаются, остаются в контейнере. В векторах все итераторы, указатели и ссылки становятся недействительными при превышении емкости, а некоторые - при вставке и удалении элементов. Итераторы, указатели и ссылки в деках становятся недействительными при изменении размера контейнера.
- Если вам нужен контейнер с высоким уровнем безопасности исключений, когда любая операция либо завершается успешно, либо
не вносит изменений, выбирайте список, но воздержитесь от выполнения присваивания и вызона функции sort(), а
если исключения могут произойти при сравнении элементов - от вызова функций merge(), remove(), remove_if() и unique().
Можно также выбрать ассоциативные контейнеры (но без многоэлементной вставки, а если исключения могут произойти при
копировании/присваивании критерия сравнения - без вызова функции swap()). Общие сведения об обработке исключений в
STL приведены на 121 шаге.
- Если вам требуется часто искать элементы по определенному критерию, воспользуйтесь множеством или мультимножеством с
сортировкой элементов по этому критерию. Помните, что при сортировке 1000 элементов логарифмическая сложность
работает на порядок быстрее линейной. В таких ситуациях наглядно проявляются преимущества бинарных деревьев. Скорость
поиска по хэш-таблице обычно в 5-10 раз превышает скорость поиска по бинарному дереву. Подумайте об использовании
хэш-контейнера, даже несмотря на то, что хэш-таблицы не стандартизированы. Однако содержимое хэш-контейнеров не сортируется,
и если вам необходима определенная упорядоченность элементов, этот тип контейнера вам не подойдет. А раз хэш-таблицы не входят
в стандартную библиотеку C++, вам понадобятся их исходные тексты для обеспечения переносимости программы.
- Для работы с парами "ключ/значение" используется отображеиие или мультиотображение (или их хэшированные версии, если они доступны).
- Если вам нужен ассоциативный массив, используйте отображение.
- Если вам нужен словарь, используйте мультиотображение.
Если нужно сортировать объекты по двум разным критериям, возникают проблемы. Допустим, вы хотите хранить объекты в порядке, указанном пользователем, но при этом предоставить средства поиска по другому критерию; как и при работе с базами данных, операции по двум и более критериям должны выполняться достаточно быстро. Вероятно, в такой ситуации стоит воспользоваться двумя множествами или отображениями, совместно использующими общие объекты с разными критериями сортировки. С другой стороны, хранение объектов в двух коллекциях - особая тема, которая рассматривается на предыдущем шаге.
Автоматическая сортировка ассоциативных контейнеров вовсе не означает, что эти контейнеры работают более эффективно там, где сортировка необходима. Дело в том, что ассоциативный контейнер проводит сортировку при каждой вставке нового элемента. Часто более эффективным оказывается другое решение - использование последовательного контейнера и сортировка всех элементов после вставки одним или несколькими алгоритмами сортировки.
На следующем шаге мы закончим рассмотрение этого вопроса.
