Контейнеры STL. Рекомендации по выбору контейнера

   
На этом шаге мы приведем некоторые рекомендации по выбору контейнера.

   
Стандартная библиотека C++ содержит разные типы контейнеров, обладающие разными возможностями. Возникает вопрос:
когда использовать тот или иной тип контейнера? В таблице 1 приводятся некоторые рекомендации. Однако эти общие утверждения не
всегда согласуются с реальностью. Например, при малом количестве элементов фактор сложности можно не учитывать, потому что
обработка малого количества элементов с линейной сложностью происходит быстрее, чем обработка большого количества элементов
с логарифмической сложностью.

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

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

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

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

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

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

   
На следующем шаге мы закончим рассмотрение этого вопроса.



Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий