std::deque — cppreference.com

<tbody> </tbody>

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

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

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

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

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

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

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

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

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

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

Типы элементы

Функции-элементы

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

Примечание

Пример

#include <deque>
#include <iostream>

int main()
{
    // Создаём двухстороннюю очередь, содержащую целые числа
    std::deque<int> d = {7, 5, 16, 8};

    // Добавляем целое число в начало и конец двухсторонней очереди
    d.push_front(13);
    d.push_back(25);

    // Итерируем и распечатываем значения двухсторонней очереди
    for(int n : d)
        std::cout << n << ' ';
    std::cout << '\n';
}

Отчёты о дефектах

Следующие изменения поведения были применены с обратной силой к ранее опубликованным стандартам C++:

Смотрите также