Что такое контейнер 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), если вставляемый/удаляемый элемент не приводил к перераспределению всех блоков.

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

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

#include <deque>
#include <iostream>

int main() {
    std::deque<int> dq;

    dq.push_back(10); // Добавить в конец
    dq.push_front(5);  // Добавить в начало
    dq.push_back(15); // Добавить в конец

    // Содержимое: 5, 10, 15

    std::cout << "Element at index 1: " << dq[1] << std::endl; // Доступ по индексу

    dq.pop_front(); // Удалить из начала
    dq.pop_back();  // Удалить из конца

    // Содержимое: 10

    std::cout << "Remaining element: " << dq.front() << std::endl; // Доступ к первому элементу

    return 0;
}

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