Что такое контейнер deque в C++?

std::deque (double-ended queue) — это последовательный контейнер, который позволяет эффективно добавлять и удалять элементы как в начале, так и в конце. Он реализуется как последовательность блоков памяти, что обеспечивает быстрый доступ к любому элементу по индексу (почти как в std::vector), но без необходимости перемещать существующие элементы при вставке/удалении в начале.

Основные характеристики:

• Произвольный доступ: Элементы доступны по индексу со сложностью O(1).
• Вставка/удаление в конце: Осуществляется со сложностью O(1).
• Вставка/удаление в начале: Осуществляется со сложностью O(1).
• Вставка/удаление в середине: Осуществляется со сложностью O(n), где n — количество элементов между точкой вставки/удаления и ближайшим концом.
• Непрерывное хранение: Элементы хранятся в нескольких непрерывных блоках памяти, но не обязательно в одном большом блоке, как std::vector.
• Итераторы: Итераторы std::deque не гарантируют оставаться действительными после вставок/удалений, кроме как в конце (после push_back/pop_back) и начале (после push_front/pop_front), если вставляемый/удаляемый элемент не приводил к перераспределению всех блоков.

Используется, когда требуется частая вставка или удаление элементов с обоих концов, а также произвольный доступ.

Пример использования:

cpp

Сравнение с std::vector: