Как и в случае с вектором, тип элементов дека передается в первом параметре шаблона. Допускается любой тип, поддерживающий присваивание и копирование. Необязательный второй параметр шаблона определяет модель памяти, ло умолчанию используется модель allocator (см. главу 15)

Возможности деков

По споим возможностям деки во многом отличаются от векторов.

О Вставка и удаление выполняются быстро как в начале, так и в конце (для векторов эти операции выполняются быстро только в конце). Операции выполняются с амортизированным постоянным временем.

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

О Итераторы должны быть умными указателями особого типа. Обычные указатели не подходят из-за необходимости перехода между блоками.

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

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

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

Следующие особенности векторов характерны также и для деков.

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

О Итераторы являются итераторами произвольного доступа.

Подведем итог. Выбирайте дек, если выполняются следующие условия:

О вставка элементов выполняется с обоих концов (классический пример очереди);

О в программе не используются ссылки на элементы контейнера;

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

В системах, не поддерживающих значения по умолчанию для параметров шаблонов, второй параметр обычно отсутствует.

Интерфейс векторов и деков почти не отличается. Если в программе не используются специфические возможности вектора или дека, вы можете легко опробовать оба контейнера.

Операции над деками

в табл. 6.9-6,11 перечислены все операции, поддерживаемые деками.

Таблица 6.9. Конструкторы и деструктор деков Операция Описание

deque<Elem> с Создает пустой дек, не содержащий ни одного элемента

deque<Eiem> с1(с2) Создает копию другого дека того же типа (с копированием всех

элементов)

deque<Elem> с(п) Создает дек из п элементов, создаваемых конструктором по умолчанию

deque<Elenfi> c(n,elem) Создает дек, инициализируемый п копиями эпемента elem deque<Elem> c(beg,end) Создает дек, инициализируемый элементами интервала [beg,end) c.~deque<Elem>() Уничтожает все элементы и освобождает память

Таблица 6.10. Немодифицирующие операции над деками Операция Описание

c.size() Возвращает фактическое количество элементов

C.emptyO Проверяет, пуст ли контейнер (эквивалент size()==0, но иногда выполняется быстрее)

c.max size() Возвращает максимально возможное количество элементов

с1 == с2 Проверяет равенство с1 и с2

с1 != с2 Проверяет неравенство с1 и с2 (эквивалент !(с1==с2))

с1 < с2 Проверяет, что с1 меньше с2

с1 > с2 Проверяет, что с1 больше с2 (эквивалент с2<с1)

с1 <= с2 Проверяет, что с1 не больше с2 (эквивалент !(с2<с1))

с1 >= с2 Проверяет, что с1 не меньше с2 (эквивалент !(с1<с2))

c.at(idx) Возвращает элемент с индексом idx (при недопустимом значении индекса генерируется исключение out of range)

c[idx] Возвращает элемент с индексом idx (без интервальной проверки!)

C.frontO Возвращает первый элемент (без проверки его существования!)

с.ЬаскО Возвращает последний элемент (без проверки его существования!)

c.rbegin() Возвращает обратный итератор для первого элемента при переборе в обратном направлении

c.rendO Возвращает обратный итератор для позиции эа последним элементом

при переборе в обратном направлении

Таблица 6.11. Модифицирующие операции над деками

Операция

Описание

с1 = с2

c.assign(n,elem)

c.assign(beg,end)

cl,swap(c2)

swap(cl,c2)

c.insert(pos,elem)

c.insert(pos,n,elem)

с. i nsert( pos, beg,end)

c.push back(elem)

c.pop back()

c.push front(elem)

c.pop front()

c.erase(pos)

c.erase(beg,end)

c.resize(num)

c.resize(num,elem)

C.clearO

Присваивает cl все элементы c2 Присваивает п копий элемента elem Присваивает элементы интервала [beg,end) Меняет местами содержимое с1 и с2 То же, но в форме глобальной функции

Вставляет копию elem в позицию итератора pes и возвращает позицию нового элемента

Вставляет п копий elem в позицию итератора pes (и не возвращает значения)

Вставляет в позицию итератора pos копию всех элементов интервала [beg,end) (и не возвращает значения)

Присоединяет копию elem в конец дека

Удаляет последний элемент (не возвращая его)

Вставляет копию elem в начало дека

Удаляет первый элемент (не возвращая его)

Удаляет элемент в позиции итератора pes и возвращает позицию следующего элемента

Удаляет все элементы из интервала [beg,end) и возвращает позицию следующего элемента

Приводит контейнер к размеру num (если slze() при этом увеличивается, новые элементы создаются своим конструктором по умолчанию)

Приводит контейнер к размеру num (если size() при этом увеличивается, новые элементы создаются как копии elem)

Удаляет все элементы (контейнер остается пустым)

Операции деков отличаются от операций векторов только в следующих отношениях:

О деки не поддерживают функции, связанные с емкостью (capacityO и reserve());

О в деках определены прямые функции вставки и удаления первого элемента (push front() и рор Ьаск()).

Поскольку остальные операции остались без изменений, здесь они не рассматриваются. За описаниями обращайтесь на с. 159.

При работе с деками необходимо учитывать следующее.

О Функции обращения к элементам (кроме at()) не проверяют правильность индексов и итераторов.

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