std::deque

template<
    class T,
    class Allocator = std::allocator<T>
> class deque;

namespace pmr {
    template< class T >
    using deque = std::deque<T, std::pmr::polymorphic_allocator<T>>;
}

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

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

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

Сложность (эффективность) распространённых операций над deque:

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

std::deque соответствует требованиям Контейнера, Контейнера с учётом аллокатора, Контейнера последовательности и Обратимого контейнера.

Параметры шаблона

Инвалидация итераторов

Примечания об инвалидации

• При вставке с любого конца deque ссылки не становятся недействительными при выполнении insert и emplace.
• push_front, push_back, emplace_front и emplace_back не делают недействительными никакие ссылки на элементы deque.
• При удалении с любого конца deque ссылки на неудалённые элементы не становятся недействительными при выполнении erase, pop_front и pop_back.
• Вызов resize с меньшим размером не делает недействительными ссылки на неудалённые элементы.
• Вызов resize с большим размером не делает недействительными ссылки на элементы deque.

Типы-члены

Функции-члены

Функции, не являющиеся членами

Примечания

Пример

#include <deque>
#include <iostream>

int main()
{
    // Create a deque containing integers
    std::deque<int> d = {7, 5, 16, 8};
    
    // Add an integer to the beginning and end of the deque
    d.push_front(13);
    d.push_back(25);
    
    // Iterate and print values of deque
    for (int n : d)
        std::cout << n << ' ';
    std::cout << '\n';
}

13 7 5 16 8 25

Отчёты об ошибках

Следующие отчёты об ошибках, изменяющие поведение, были применены задним числом к ранее опубликованным стандартам C++.

См. также