Краткий ответ

Выберите std::deque: он обеспечивает постоянное время доступа по индексу и постоянную сложность вставки в начало. У std::vector доступ по индексу также выполняется за O(1), но вставка в начало обычно требует сдвига всех существующих элементов и занимает O(n).

Исторический контекст

Последовательные контейнеры решают разные задачи, поэтому один контейнер не может одновременно оптимально поддерживать все виды операций. std::vector ориентирован на непрерывное хранение и эффективный последовательный доступ, а std::deque — на работу с обоими концами последовательности.

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

Постановка проблемы

При вставке элемента в начало vector должен освободить первую позицию и сдвинуть вправо все существующие элементы. Это требует линейного количества перемещений, а при нехватке capacity может дополнительно потребоваться перераспределение всего буфера.

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

Подробное решение

У обоих контейнеров обращение по индексу имеет сложность O(1). У vector адрес вычисляется относительно начала единого непрерывного массива, а у deque сначала определяется нужный блок, затем позиция внутри блока; число таких действий не зависит от размера контейнера.

Ключевое различие — вставка в начало. Для vector она имеет сложность O(n) из-за сдвига элементов. Для deque вставка в начало и конец имеет постоянную сложность согласно требованиям стандартной библиотеки.

#include <deque>

int main() {
    std::deque<int> values{10, 20, 30};
    values.push_front(5);
    values.push_back(40);
    int element = values[2];
}

Однако deque не хранит элементы непрерывно. Поэтому его нельзя использовать там, где требуется указатель на непрерывный массив элементов, например для передачи данных в интерфейс, принимающий массив. Vector обычно лучше использует кэш процессора при последовательном обходе и имеет более простой внутренний layout.

Вставка в середину deque не становится постоянной: элементы всё равно приходится перемещать, поэтому такая операция имеет линейную сложность. Если нужны только операции на концах без индексирования, возможны другие структуры, но для одновременного индексирования и работы с началом deque является естественным выбором.

Ситуация из практики

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

List устранил бы сдвиги на концах, но потерял бы быстрый доступ по индексу и обычно имел бы худшую локальность данных. Vector с ручным кольцевым буфером мог бы быть эффективнее, но потребовал бы дополнительной логики для управления индексами, переполнением и порядком элементов.

В этой ситуации выбранный deque поддерживает операции на обоих концах и индексирование непосредственно из стандартной библиотеки. Это уменьшает сложность реализации при приемлемом компромиссе по непрерывности хранения и локальности доступа.

Что кандидаты часто упускают

Гарантирует ли std::deque непрерывное хранение элементов?

Нет. В отличие от std::vector, элементы deque могут находиться в нескольких блоках памяти. Последовательный обход поддерживается итераторами контейнера, но преобразовывать диапазон элементов deque в один непрерывный массив нельзя.
Всегда ли std::deque быстрее std::vector, если вставка выполняется в начало?

Нет. Deque имеет подходящую асимптотику для этой операции, но фактическая скорость зависит от размера элементов, реализации библиотеки, распределения памяти и характера доступа. Если вставки в начало редки, а основной сценарий — последовательный обход или работа с непрерывным буфером, vector может оказаться быстрее несмотря на потенциально более дорогую вставку.
Что произойдёт со сложностью при вставке в середину std::deque?

Она будет линейной: часть элементов придётся переместить, чтобы освободить позицию. Deque оптимизирует операции на концах, но не превращает произвольную вставку в постоянную. Если приложение часто изменяет середину последовательности, нужно отдельно оценить подходящий контейнер и стоимость перемещений элементов.