Mediumdequevector
Чем std::deque отличается от std::vector?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
std::vector — contiguous array, рост через reallocation. std::deque — double-ended queue из chunks фиксированного размера с внешним массивом указателей.
std::vector<int> v;
v.push_back(1); // O(1) amortized
v.insert(v.begin(), 0); // O(n)
std::deque<int> d;
d.push_back(1); // O(1)
d.push_front(0); // O(1) — главное преимущество
// ссылки на элементы не инвалидируются при push на концы- минусы deque: не contiguous (хуже cache locality, нельзя
T*в C-API), больше overhead, random access с двумя indirection; std::stack/std::queueпо умолчанию на deque.
Большинство случаев — vector; deque — для queue-задач с front/back операциями.
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.