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

Контейнер (container) содержит коллекцию объектов определенного типа. Последовательные контейнеры (sequential container) позволяют контролировать порядок, в котором хранятся элементы и предоставляется доступ к ним. Этот порядок не зависит от значений элементов, он соответствует позиции, в которую помещаются элементы контейнера. В отличие от них, ассоциативные контейнеры (упорядоченные и неупорядоченные) хранят свои элементы на основании значения ключа, как будет описано в главе 11.

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

Эта глава основана на материале разделов 3.2–3.4. Здесь подразумевается, что читатель знаком с их материалом.

Все последовательные контейнеры, перечисленные в табл. 9.1, предоставляют быстрый последовательный доступ к своим элементам. Однако эти контейнеры обладают разной производительностью и возможностями, включая следующие:

• цена добавления и удаления элементов из контейнера;

• цена непоследовательного доступа к элементам контейнера.

Таблица 9.1. Типы последовательных контейнеров

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

Например, контейнеры stringи vectorсодержат свои элементы в соседних областях памяти. Поскольку элементы расположены последовательно, их адрес по индексу вычисляется очень быстро. Но добавление или удаление элемента в середину такого контейнера занимает много времени: для обеспечения последовательности все элементы после удаления или вставки придется переместить. Кроме того, добавление элемента может иногда потребовать резервирования дополнительного места для хранения. В этом случае каждый элемент следует переместить в новое место.

Контейнеры 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.

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