std::deque

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';
}

13 7 5 16 8 25

[править] Отчёты о дефектах

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

[править] Смотрите также