Контейнер deque

Деком (англ. deque, от double-ended queue) называется структура данных, которая позволяет добавлять элементы и в конец, и в начало, а также удалять элементы из конца и из начала. Все эти операции реализованы за O(1), то есть выполняются быстро.

В STL есть специальный контейнер deque, который реализует подобную функциональность. Для его использования необходимо подключить заголовочный файл deque:

#include<deque>

Объявляется дек, например, целых чисел так:

deque <int> D;

Дек поддерживает следущие методы:

Название метода Описание
size() Возвращает размер дека
empty() Возвращает true, если дек пуста, или false, если непуст
clear() Очищает дек
front() Возвращает значение первого элемента в деке
back() Возвращает значение последнего элемента в деке
pop_front() Удаляет первый элемент из дека, не возвращает значение
pop_back() Удаляет последний элемент из дека, не возвращает значение
push_front(elem) Добавляет новый элемент elem в начало дека
push_back(elem) Добавляет новый элемент elem в конец дека

У дека есть много общего с векторами. Например, к элементам дека можно обращаться по индексу, при помощи [i] или метода at(i). Эти обращения выполняются быстро - реализация дека насколько хитра, что можно быстро добавлять элементы в начало и в конец, а также быстро обращаться к элементу по его номеру. У дека, как и у вектора, есть методы erase, insert и resize, но они работают за линейное время.

Также с объектами класса deque допустимы операции =, ==, !=, <, >, <=, >=.

Подробней о контейнере deque можно прочитать в документации.