Двусторонняя очередь (deque, double-ended queue) — это контейнерная структура данных, которая позволяет эффективно добавлять и удалять элементы как с начала, так и с конца.
Её основные характеристики:
push_front, pop_front, push_back, pop_back выполняются в среднем за время O(1).std::vector, элементы std::deque не обязательно хранятся в едином непрерывном блоке памяти. Он обычно реализован как последовательность блоков фиксированного размера.Сравнение с std::vector и std::list:
| Характеристика | std::vector | std::deque | std::list |
|---|---|---|---|
| Доступ по индексу | O(1) | O(1) | O(n) |
| Вставка/удаление в начале | O(n) | O(1) | O(1) |
| Вставка/удаление в конце | Амортизированно O(1) | O(1) | O(1) |
| Вставка/удаление в середине | O(n) | O(n) (в среднем) | O(1) (по итератору) |
| Занимаемая память | Непрерывный блок, возможен оверхед | Несколько блоков, возможен оверхед | Каждый элемент с указателями |
cppИспользуется, когда требуется частая вставка или удаление элементов с обоих концов очереди и при этом нужен эффективный доступ по индексу.