std:: deque

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

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

Хранилище дека автоматически расширяется и сжимается по мере необходимости. Расширение дека обходится дешевле, чем расширение std::vector , поскольку оно не связано с копированием существующих элементов в новое место памяти. С другой стороны, дека обычно имеют высокую минимальную стоимость памяти; дек, содержащий всего один элемент, должен выделить полный внутренний массив (например, в 8 раз больше размера объекта в 64-битной libstdc++; в 16 раз больше размера объекта или 4096 байт, в зависимости от того, что больше, в 64-битной libc++).

Сложность (эффективность) стандартных операций с деками следующая:

• Произвольный доступ - константный O(1) .
• Вставка или удаление элементов в конце или начале - константная O(1) .
• Вставка или удаление элементов - линейная O(n) .

std::deque удовлетворяет требованиям Container , AllocatorAwareContainer , SequenceContainer и ReversibleContainer .

#include <deque>
#include <iostream>
int main()
{
    // Создаем deque содержащий целые числа
    std::deque<int> d = {7, 5, 16, 8};
    // Добавляем целое число в начало и конец deque
    d.push_front(13);
    d.push_back(25);
    // Итерируем и выводим значения deque
    for (int n : d)
        std::cout << n << ' ';
    std::cout << '\n';
}

13 7 5 16 8 25