std::deque

 

C++

Поддержка компилятором

Автономные и размещённые реализации

Язык

Стандартная библиотека

Заголовки стандартной библиотеки

Требования к именованию

Макросы тестирования функциональности (C++20)

Поддержка языка

Библиотека концептов (C++20)

Библиотека метапрограммирования (C++11)

Библиотека диагностики

Библиотека общих утилит

Библиотека строк

Библиотека контейнеров

Библиотека итераторов

Библиотека диапазонов (C++20)

Библиотека алгоритмов

Библиотека численных данных

Библиотека ввода/вывода

Библиотека локализаций

Регулярные выражения (C++11)

Атомарные операции (C++11)

Библиотека поддержки конкуренции (C++11)

Библиотека файловой системы (C++17)

Технические спецификации

Указатель символов

Внешние библиотеки

 

Библиотека контейнеров

Последовательные

array (C++11)

vector

deque

forward_list (C++11)

list

Ассоциативные

set

multiset

map

multimap

Неупорядоченные ассоциативные

unordered_set (C++11)

unordered_multiset (C++11)

unordered_map (C++11)

unordered_multimap (C++11)

Адаптеры

stack

queue

priority_queue

Представления

span (C++20)

mdspan (C++23)

Аннулирование итератора

Таблица функций-элементов

Таблица функций, не являющихся элементами

 

std::deque

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

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

deque::deque

deque::~deque

deque::operator=

deque::assign

deque::get_allocator

Доступ к элементам

deque::at

deque::operator[]

deque::front

deque::back

Итераторы

deque::begindeque::cbegin (C++11)

deque::enddeque::cend (C++11)

deque::rbegindeque::crbegin (C++11)

deque::renddeque::crend (C++11)

Ёмкость

deque::empty

deque::size

deque::max_size

deque::shrink_to_fit

Модификаторы

deque::clear

deque::insert

deque::emplace

deque::erase

deque::push_front

deque::emplace_front

deque::pop_front

deque::push_back

deque::emplace_back

deque::pop_back

deque::resize

deque::swap

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

std::swap

eraseerase_if (C++20)(C++20)

operator==operator!=operator<operator>operator<=operator>=operator<=> (до C++20)(до C++20)(до C++20)(до C++20)(до C++20)(C++20)

Принципы вывода (C++17)

 

Определено в заголовочном файле <deque>
template<     class T,     class Allocator = std::allocator<T> > class deque;	(1)
namespace pmr {     template <class T>     using deque = std::deque<T, std::pmr::polymorphic_allocator<T>>; }	(2)	(начиная с C++17)

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.

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

T	—	Тип элементов. T должен соответствовать требованиям CopyAssignable и CopyConstructible. (до C++11) Требования, предъявляемые к элементам, зависят от фактических операций, выполняемых с контейнером. Как правило, требуется, чтобы тип элемента был полным типом и отвечал требованиям Erasable, но многие функции-элементы предъявляют более строгие требования. (начиная с C++11)
Allocator	—	Аллокатор, который используется для получения/освобождения памяти и создания/уничтожения элементов в этой памяти. Тип должен соответствовать требованиям Allocator. Поведение не определено (до C++20)Программа не корректна (начиная с C++20), если Allocator::value_type не совпадает с T.

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

Операции	Недействителен
Все операции только для чтения	Ниодин
swap, std::swap	Конечный итератор может быть признан недействительным (определяется реализацией)
shrink_to_fit, clear, insert, emplace, push_front, push_back, emplace_front, emplace_back	Все
erase	Если удаление в начале, тогда только на удалённые элементы Если удаление в конце, тогда только на удалённые элементы и конечный итератор В противном случае все итераторы недействительны (включая конечный итератор).
resize	Если новый размер меньше старого: только на удалённые элементы и конечный итератор Если новый размер больше старого: все итераторы недействительны В противном случае ни один итератор не станет недействительным.
pop_front	Только на удалённый элемент
pop_back	На удалённый элемент и конечный итератор

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

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

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

Тип элемент	Определение
value_type	T
allocator_type	Allocator
size_type	Беззнаковый целочисленный тип (обычно std::size_t)
difference_type	Знаковый целочисленный тип (обычно std::ptrdiff_t)
reference	value_type&
const_reference	const value_type&
pointer	Allocator::pointer (до C++11) std::allocator_traits<Allocator>::pointer (начиная с C++11)
const_pointer	Allocator::const_pointer (до C++11) std::allocator_traits<Allocator>::const_pointer (начиная с C++11)
iterator	LegacyRandomAccessIterator в value_type
const_iterator	LegacyRandomAccessIterator в const value_type
reverse_iterator	std::reverse_iterator<iterator>
const_reverse_iterator	std::reverse_iterator<const_iterator>

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

(конструктор)	создаёт deque (public функция-элемент)
(деструктор)	уничтожает deque (public функция-элемент)
operator=	присваивает значения контейнеру (public функция-элемент)
assign	присваивает значения контейнеру (public функция-элемент)
get_allocator	возвращает связанный аллокатор (public функция-элемент)
Доступ к элементам
at	предоставляет доступ к указанному элементу с проверкой границ (public функция-элемент)
operator[]	предоставляет доступ к указанному элементу (public функция-элемент)
front	предоставляет доступ к первому элементу (public функция-элемент)
back	предоставляет доступ к последнему элементу (public функция-элемент)
Итераторы
begin cbegin (C++11)	возвращает итератор на начало (public функция-элемент)
end cend (C++11)	возвращает итератор на конец (public функция-элемент)
rbegin crbegin (C++11)	возвращает обратный итератор на начало (public функция-элемент)
rend crend (C++11)	возвращает обратный итератор на конец (public функция-элемент)
Ёмкость
empty	проверяет, пуст ли контейнер (public функция-элемент)
size	возвращает количество элементов (public функция-элемент)
max_size	возвращает максимально возможное количество элементов (public функция-элемент)
shrink_to_fit (C++11)	уменьшает использование памяти за счёт освобождения неиспользуемой памяти (public функция-элемент)
Модификаторы
clear	очищает содержимое (public функция-элемент)
insert	вставляет элементы (public функция-элемент)
emplace (C++11)	создаёт элемент на месте (public функция-элемент)
erase	удаляет элементы (public функция-элемент)
push_back	добавляет элемент в конец (public функция-элемент)
emplace_back (C++11)	создаёт элементы на месте в конце (public функция-элемент)
pop_back	удаляет последний элемент (public функция-элемент)
push_front	вставляет элементы в начало списка (public функция-элемент)
emplace_front (C++11)	конструирует элементы на месте в начале списка (public функция-элемент)
pop_front	удаляет первый элемент (public функция-элемент)
resize	изменяет количество хранимых элементов (public функция-элемент)
swap	меняет местами содержимое (public функция-элемент)

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

operator== operator!= operator< operator<= operator> operator>= operator<=> (убрано в C++20) (убрано в C++20) (убрано в C++20) (убрано в C++20) (убрано в C++20) (C++20)	лексикографически сравнивает значения в deque (шаблон функции)
std::swap(std::deque)	специализация алгоритма std::swap (шаблон функции)
erase(std::deque) erase_if(std::deque) (C++20)	удаляет все элементы, удовлетворяющие определённым критериям (шаблон функции)

Пример

Запустить этот код

#include <iostream>
#include <deque>
 
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 << ' ';
    }
}

Вывод:

13 7 5 16 8 25

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

queue	адаптирует контейнер для предоставления очереди (структура данных FIFO) (шаблон класса)