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 (двунаправленная очередь) — это контейнер индексированных последовательностей, который позволяет быстро вставлять и удалять элементы как в начале, так и в конце. Кроме того, вставка и удаление элементов в любом конце очереди никогда не делают указатели или ссылки на остальные элементы недействительными.

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

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

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

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

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

Шаблонные параметры

Недействительность итераторов

Примечания к недействительности

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

Типы членов

Члены функций

Вне-членные функции

Примечания

Пример

#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++.

См. также