Что такое Deque в C++? — пример ответа на собеседовании C/C++ Разработчик

Что такое Deque в C++?

«Что такое Deque в C++?» — вопрос из категории STL, который задают на 30% собеседований C/C++ Разработчик. Ниже — развёрнутый ответ с разбором ключевых моментов.

Тип вопроса: STL Вероятность: 30% Категория: C/C++ Разработчик

Ответ

std::deque (double-ended queue, дек) — это контейнер стандартной библиотеки C++, который обеспечивает эффективную вставку и удаление элементов как в начало, так и в конец за амортизированное O(1).

Ключевые особенности и отличия от std::vector:

Особенность	`std::deque`	`std::vector`
Вставка в начало	O(1) (амортизир.)	O(n) (сдвиг всех элементов)
Расположение в памяти	Не гарантирует непрерывность (блочная структура)	Гарантирует непрерывность
Инвалидация указателей/итераторов	При модификации инвалидируются все итераторы, указатели/ссылки на элементы — нет (кроме удалённого элемента)	При любом изменении ёмкости инвалидируются все итераторы, указатели и ссылки

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

#include <deque>
#include <iostream>
#include <algorithm> // for std::copy

int main() {
    std::deque<int> dq = {2, 3, 4};

    // Эффективная вставка с двух сторон
    dq.push_front(1); // dq: [1, 2, 3, 4]
    dq.push_back(5);  // dq: [1, 2, 3, 4, 5]

    // Прямой доступ по индексу за O(1)
    std::cout << "Element at index 2: " << dq[2] << 'n'; // Выведет: 3

    // Итерация
    for (const auto& elem : dq) {
        std::cout << elem << ' ';
    }
    // Выведет: 1 2 3 4 5

    // Типичный use-case: реализация очереди с возможностью "заглянуть" в начало и конец
    // или скользящего окна (sliding window).
    return 0;
}

Внутренняя реализация: Обычно реализуется как массив указателей на фиксированные блоки памяти. Это компромисс, дающий быстрые операции с концами, но делающий произвольный доступ и итерацию чуть медленнее, чем у вектора, из-за дополниного уровня косвенности.

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