Рассмотрим последовательные контейнеры более подробно.

Контейнер deque –дек ( double-ended queue – двусторонняя очередь ). Создается как динамический массив, в который можно включать элементы и из которого можно брать элементы с двух концов.

Контейнер list – организует хранение объектов в виде двусвязного списка и располагается в памяти произвольным образом. Каждый элемент списка содержит три поля: значение элемента, указатель на предшествующий и указатель на последующий элементы списка, что позволяет перемещаться по списку вперед и назад. Вставка и удаление работают эффективно для любой позиции элемента в списке (изменяются только указатели). Например, добавление каждого нового элемента приводит к тому, что меняют свои значения указатели (на предыдущий и следующий элементы списка) для тех элементов, между которыми вставляется новый элемент. В новом элементе таким указателям присваиваются значения адресов соседних элементов. Список использует только тот объем памяти, который нужен для имеющегося количества элементов. Накладными расходами являются два указателя в каждом элементе и необходимость использования указателя для получения значения элемента. С другой стороны, список не поддерживает произвольного доступа к своим элементам: например, для выборки n-го элемента нужно последовательно выбрать предыдущие n-1 элементов.

Контейнер vector – «безопасный», автоматически расширяющийся массив, обеспечивающий произвольный доступ к находящимся в нем элементам. Представляет собой область памяти, где элементы хранятся друг за другом, является аналогом обычного массива, за исключением того, что автоматически выделяет и освобождает память по мере необходимости. Для этого типа произвольный доступ (возможность извлечь, например, элемент 5, затем 15, затем 7 и т.д.) можно реализовать очень эффективно, поскольку каждый из них находится на некотором фиксированном расстоянии от начала. Однако вставка элемента в любую позицию, кроме конца вектора, неэффективна. Для этого потребуется сдвинуть все последующие элементы путем копирования их значений. По этой же причине неэффективным является удаление любого элемента, кроме последнего. Особенно это сказывается на больших векторах.

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

Контейнер двустронняя очередь (deque) во многом аналогичен вектору, элементы хранятся в непрерывной области памяти. Но в отличие от вектора для двустронней очереди операции вставки и удаления самого первого элемента (как и последнего) работают быстрее; это достигается двухуровневым представлением контейнера, при котором один уровень представляет собой реальное размещение элементов, а второй уровень адресует первый и последний из них.

Адаптер (специализированный контейнер) queue – очередь реализуется как динамический массив, элементы в который можно включать только в конец, а извлекать только из начала.

Адаптер stack – стек реализуется как динамический массив, включение и извлечение элементов которого можно осуществлять только с одного конца.

 

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

Вот некоторые критерии для выбора вида последовательного контейнера:

вектор предпочтительнее, если:

· требуется произвольный доступ к элементам;

· небольшой размер набора данных;

· используются объекты простого класса элементов данных (при этом выполняется побитовое копирование, а не вызов конструктора копирования);

· количество элементов известно заранее;

· не нужно вставлять и удалять элементы в начало контейнера;

· хранить в векторе не объекты сложного класса, а указатели на них.

список предпочтительнее, если:

· необходимо иметь возможность вставлять и удалять элементы в середину;

· эффективность вектора становится слишком низкой.

 

Если нужна возможность и произвольного доступа, и произвольного добавления/удаления элементов, приходится выбирать: тратить время на поиск элемента или на его перемещение в случае вставки/удаления. В общем случае необходимо исходить из того, какую основную задачу решает приложение: поиск или добавление элементов? Если ни один из стандартных контейнеров не удовлетворяет, может быть, стоит разработать свою собственную, более сложную, структуру данных.

 

Практически в любом контейнерном классе определены поля следующих типов:

поле	содержание
value_type	тип элемента контейнера
size_type	тип индексов, счетчиков элементов и т.д.
iterator	итератор
const_iterator	константный итератор
reverse_iterator	обратный итератор
const_reverse_iterator	константный обратный итератор
reference	ссылка на элемент
const_reference	константная ссылка на элемент
key_type	тип ключа (для ассоциативных контейнеров)
key_compare	тип функции-критерия сравнения (для ассоциативных контейнеров)