Стенли Липпман - Язык программирования C++. Пятое издание

Контейнеры listи forward_listразработаны так, чтобы быстро добавлять и удалять элементы в любой позиции контейнера. Однако эти типы не поддерживают произвольный доступ к элементам: обратиться к элементу можно, только перебрав контейнер. Кроме того, дополнительные затраты памяти этих контейнеров зачастую являются существенными по сравнению с контейнерами vector, dequeи array.

Контейнер deque— это более сложная структура данных. Как и контейнеры string, vectorи deque, они обеспечивают быстрый произвольный доступ. Как и у контейнеров stringи vector, добавление или удаление элементов в середину контейнера deque — потенциально дорогая операция. Однако добавление и удаление элементов в оба конца контейнера dequeявляются быстрой операцией, сопоставимой с таковыми у контейнеров list и forward_list.

Типы forward_listи arrayбыли добавлены согласно новому стандарту. Класс array— более безопасная и легкая в употреблении альтернатива встроенным массивам. Как и встроенные массивы, объект библиотечного класса arrayимеет фиксированный размер. В результате он не поддерживает операции по добавлению и удалению элементов или изменению размеров контейнера. Класс forward_listпредназначен для замены наилучших самодельных односвязных списков. Следовательно, у него нет функции size(), поскольку сохранение или вычисление его размера повлекло бы дополнительные затраты по сравнению с самодельным списком. Для других контейнеров функция size()гарантированно будет выполняться быстро с постоянной скоростью.

По причинам, изложенным в разделе 13.6, новые библиотечные контейнеры работают существенно быстрее, чем в предыдущих версиях. Библиотечные контейнеры почти наверняка работают так же (если не лучше), чем даже наиболее тщательно разработанные альтернативы. Современные программы С++ должны использовать библиотечные контейнеры, а не множество примитивных структур, подобных массивам.

Как правило, если нет серьезных оснований предпочесть другой контейнер, лучше использовать контейнер vector.

Ниже приведено несколько эмпирических правил по выбору используемого контейнера.

• Если нет причин использовать другой контейнер, используйте вектор.

• Если имеется много небольших элементов и дополнительных затрат, не используйте контейнер listили forward_list.

• Если нужен произвольный доступ к элементам, используйте контейнер vectorили deque.

• Если необходима вставка или удаление элементов в середину, используйте контейнер listили forward_list.

• Если необходима вставка или удаление элементов в начало или в конец, но не в середину, используйте контейнер deque.

• Если вставка элементов в середину контейнера нужна только во время чтения ввода, а впоследствии нужен произвольный доступ к элементам, то:

• сначала решите, необходимо ли фактически добавлять элементы в середину контейнера. Зачастую проще добавлять элементы в vector, а затем использовать библиотечную функцию sort()(рассматриваемую в разделе 10.2.3) для переупорядочивания контейнера по завершении ввода;

• если вставка в середину необходима, рассмотрите возможность использования контейнера listна фазе ввода, а по его завершении — копирования списка в вектор.

Но что если нужен и произвольный доступ, и вставка (удаление) элементов в середину контейнера? Решение будет зависеть от отношения цены доступа к элементам в контейнере listи forward_listцены вставки (удаления) элементов в контейнер vectorили deque. Как правило, выбор типа контейнера определит преобладающая операция приложения (произвольный доступ или вставка и удаление). В таких случаях, вероятно, потребуется проверка производительности приложения с использованием контейнеров обоих типов.

Если вы не уверены, какой контейнер использовать, напишите свой код так, чтобы он использовал только те операции, которые совпадают у вектора и списка: используйте итераторы, а не индексы, и избегайте произвольного доступа к элементам. Так будет удобней заменить вектор на список при необходимости.