Контейнеры

В STL контейнер – это параметризованный класс, представляемый шаблоном классов. Объект такого параметризованного класса пригоден для включения других объектов, поэтому один и тот же вид контейнера можно использовать для хранения данных различных типов (встроенных, либо пользовательских). Элементами контейнеров могут быть и контейнеры.

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

Использование контейнеров позволяет повысить надежность программ, их переносимость и универсальность, уменьшить сроки разработки. В то же время эти преимущества отражаются на быстродействии программы (оно снижается). Для эффективного использования контейнеров требуется вдумчивое освоение библиотеки STL.

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

Контейнеры могут быть фиксированного или переменного размера.

Способ доступа к элементам контейнера:

• прямой – доступ по индексу элемента;

• последовательный – последовательное перемещение от элемента к элементу;

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

Тип контейнера – это способ доступа к его элементам (но не тип его элементов):

Для представления различных структур данных (коллекций) в STL определены контейнеры двух видов:

• Последовательные контейнеры, представляющие собой упорядоченные коллекции, в которых каждый элемент занимает позицию, не зависящую от значения элемента. Позиция может зависеть от того, какой была коллекция в момент помещения в нее элемента и/или от явного указания места для размещаемого элемента. Последовательные контейнеры обеспечивают хранение конечного количества однотипных величин в виде непрерывной неупорядоченной последовательности. К ним относятся двусторонние очереди (deque), списки (list), векторы (vector), а также так называемые адаптеры, то есть варианты контейнеров – стеки (stack), очереди (queue) и очереди с приоритетами (priority_queue).

• Ассоциативные контейнеры, представляющие собой отсортированные по умолчанию коллекции однотипных элементов, в которых позиция элемента зависит от его значения. Ассоциативные контейнеры автоматически упорядочивают включаемые в них элементы по некоторому критерию. Критерий реализуется в виде функции, которая сравнивает либо значения элементов, либо специальные ключи, заданные для этих значений (элементов). Ассоциативные контейнеры реализуются в виде бинарных деревьев, где у каждого узла-элемента есть два узла–потомка (правый и левый). Все производные узлы слева имеют меньшие значения, а все производные справа – большие. К ассоциативным контейнерам относят: словари (map), словари с повторяющимися элементами (multimap), множества (set), множества с повторяющимися элементами (multiset), битовые множества (bitset).

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

Контейнер 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	тип функции-критерия сравнения (для ассоциативных контейнеров)