Просмотр кода страницы cpp/container/deque

У вас нет прав на выполнение действия «редактирование этой страницы» по следующей причине:
Запрошенное действие могут выполнять участники одной из следующих групп: Участники, Администраторы.
Вы можете просмотреть и скопировать исходный код этой страницы.
{{cpp/title|deque}}
{{cpp/container/deque/navbar}}
{{dcl begin}}
{{dcl header|deque}}
{{dcl | num=1 |1=
template<
    class T,
    class Allocator = std::allocator<T>
> class deque;
}} 
{{dcl | num=2 |since=c++17|1=
namespace pmr {
    template <class T>
    using deque = std::deque<T, std::pmr::polymorphic_allocator<T>>;
}
}}
{{dcl end}}

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

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

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

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

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


{{tt|std::deque}} соответствует требованиям {{named req|Container}}, {{named req|AllocatorAwareContainer}}, {{named req|SequenceContainer}} и {{named req|ReversibleContainer}}.

===Параметры шаблона===
{{par begin}}
{{par inc | cpp/container/param list T | deque}}
{{par inc | cpp/container/param list Allocator | deque}}
{{par end}}

===Недействительность итератора===
{{todo|В этом разделе всё еще есть несколько неточностей, для получения более подробной информации обратитесь к страницам отдельных функций-элементов.}}

{| class="dsctable" style="font-size:0.9em"
! Операции
! Недействителен
|-
| Все операции только для чтения
| Ниодин
|-
| {{lc|swap}}, {{lc|std::swap}}
| Конечный итератор может быть признан недействительным<br>(определяется реализацией)
|-
| {{lc|shrink_to_fit}}, {{lc|clear}}, {{lc|insert}}, {{lc|emplace}}, {{lc|push_front}},<br> {{lc|push_back}}, {{lc|emplace_front}}, {{lc|emplace_back}}
| Все
|-
| {{lc|erase}}
| Если удаление в начале только удалённые элементы<br>
При удалении в конце только удалённые элементы и итератор за последним элементом<br>
Иначе все итераторы недействительны.<br><br>
{{rev inl|until=c++11|Не указано, когда конечный итератор становится недействительным.}}<br><br>
{{rev inl|since=c++11|Конечный итератор также становится недействительным, если только удалённые элементы не находятся в начале контейнера, а последний элемент не удалён.}}
|-
| {{lc|resize}}
| Если новый размер меньше старого - только на удалённые элементы и <br> конечный итератор<br>Если новый размер больше старого - все итераторы недействительны <br>В противном случае ни один итератор не станет недействительным.
|-
| {{lc|pop_front}}, {{lc|pop_back}}
| Удаление элемента.<br>
Конечный итератор<br>
{{rev inl|until=c++11|может быть признан недействительным (определяется реализацией)}}<br>
{{rev inl|since=c++11|также признан недействительным}}
|}

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

===Типы элементы===
{{dsc begin}}
{{dsc hitem | Тип элемент | Определение}}
{{dsc inc | cpp/container/dsc value_type | deque}}
{{dsc inc | cpp/container/dsc allocator_type | deque}}
{{dsc inc | cpp/container/dsc size_type | deque}}
{{dsc inc | cpp/container/dsc difference_type | deque}}
{{dsc inc | cpp/container/dsc reference | deque}}
{{dsc inc | cpp/container/dsc const_reference | deque}}
{{dsc inc | cpp/container/dsc pointer | deque}}
{{dsc inc | cpp/container/dsc const_pointer | deque}}
{{dsc inc | cpp/container/dsc iterator | deque}}
{{dsc inc | cpp/container/dsc const_iterator | deque}}
{{dsc inc | cpp/container/dsc reverse_iterator | deque}}
{{dsc inc | cpp/container/dsc const_reverse_iterator | deque}}
{{dsc end}}

===Функции-элементы===
{{dsc begin}}
{{dsc inc | cpp/container/dsc constructor | deque}}
{{dsc inc | cpp/container/dsc destructor | deque}}
{{dsc inc | cpp/container/dsc operator{{=}} | deque}}
{{dsc inc | cpp/container/dsc assign | deque}}
{{dsc inc | cpp/container/dsc assign_range | deque}}
{{dsc inc | cpp/container/dsc get_allocator | deque}}

{{dsc h2 | Доступ к элементам}}
{{dsc inc | cpp/container/dsc at | deque}}
{{dsc inc | cpp/container/dsc operator_at | deque}}
{{dsc inc | cpp/container/dsc front | deque}}
{{dsc inc | cpp/container/dsc back | deque}}

{{dsc h2 | Итераторы}}
{{dsc inc | cpp/container/dsc begin | deque}}
{{dsc inc | cpp/container/dsc end | deque}}
{{dsc inc | cpp/container/dsc rbegin | deque}}
{{dsc inc | cpp/container/dsc rend | deque}}

{{dsc h2 | Ёмкость}}
{{dsc inc | cpp/container/dsc empty | deque}}
{{dsc inc | cpp/container/dsc size | deque}}
{{dsc inc | cpp/container/dsc max_size | deque}}
{{dsc inc | cpp/container/dsc shrink_to_fit | deque}}

{{dsc h2 | Модификаторы}}
{{dsc inc | cpp/container/dsc clear | deque}}
{{dsc inc | cpp/container/dsc insert | deque}}
{{dsc inc | cpp/container/dsc insert_range | deque}}
{{dsc inc | cpp/container/dsc emplace | deque}}
{{dsc inc | cpp/container/dsc erase | deque}}
{{dsc inc | cpp/container/dsc push_back | deque}}
{{dsc inc | cpp/container/dsc emplace_back | deque}}
{{dsc inc | cpp/container/dsc append_range | deque}}
{{dsc inc | cpp/container/dsc pop_back | deque}}
{{dsc inc | cpp/container/dsc push_front | deque}}
{{dsc inc | cpp/container/dsc emplace_front | deque}}
{{dsc inc | cpp/container/dsc prepend_range | deque}}
{{dsc inc | cpp/container/dsc pop_front | deque}}
{{dsc inc | cpp/container/dsc resize | deque}}
{{dsc inc | cpp/container/dsc swap | deque}}
{{dsc end}}

===Функции, не являющиеся элементами===
{{dsc begin}}
{{dsc inc | cpp/container/dsc operator_cmp | deque}}
{{dsc inc | cpp/container/dsc swap2 | deque}}
{{dsc inc | cpp/container/dsc erase seq | deque}}
{{dsc end}}

{{rrev|noborder=true|since=c++17|{{=}}{{=}}{{=}}{{rl|deduction guides|Принципы вывода}}{{=}}{{=}}{{=}}}}

===Примечание===
{{ftm begin|std=1|comment=1}}
{{ftm|__cpp_lib_containers_ranges|value=202202L|std=C++23|Создание и вставка диапазонов для контейнеров}}
{{ftm end}}

===Пример===

{{example
 |
 | code=
#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';
}
 | output=
13 7 5 16 8 25
}}

===Отчёты о дефектах===
{{dr list begin}}
{{dr list item|wg=lwg|dr=230|std=C++98|before={{tt|T}} не обязательно должен быть {{named req|CopyConstructible}} (элемент<br>типа {{tt|T}} может быть не создан)|after={{tt|T}} также должен быть {{named req|CopyConstructible}}}}
{{dr list end}}

===Смотрите также===
{{dsc begin}}
{{dsc inc | cpp/container/dsc queue}}
{{dsc end}}

{{langlinks|de|en|es|fr|it|ja|pl|pt|zh}}
Шаблоны, используемые на этой странице:
Возврат к странице cpp/container/deque.
cppreference.com

Поиск

Пространства имён

Варианты

Просмотры

Действия

Просмотр кода страницы cpp/container/deque

Навигация

Инструменты
