Mediumконтейнеры
Чем deque полезен и когда его применять?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
std::deque (double-ended queue) — O(1) вставка/удаление с обоих концов и O(1) доступ по индексу. Реализован как набор «чанков» фиксированного размера.
std::deque<int> d;
d.push_back(1); // O(1)
d.push_front(0); // O(1) — главное преимущество перед vector
d[0]; // O(1) доступ по индексу
d.pop_front(); // O(1)- Главное преимущество перед vector —
push_frontбез перемещения элементов; - Применение: очереди, sliding window, history (recent items с обоих концов);
- Минусы: память не полностью непрерывна (хуже cache locality), любая модификация инвалидирует все итераторы (но указатели/ссылки на элементы живы);
- Если push_front не нужен — vector эффективнее.
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.