Какова сложность удаления элемента из начала вектора (std::vector)?

Удаление элемента из начала std::vector с помощью vector.erase(vector.begin()) имеет линейную временную сложность O(n).

Причина: std::vector хранит элементы в непрерывном блоке памяти. При удалении первого элемента все последующие элементы (n-1 штук) необходимо сдвинуть на одну позицию влево для сохранения непрерывности.

std::vector<int> v = {10, 20, 30, 40, 50};
// Удаляем первый элемент (10)
v.erase(v.begin()); // O(n) операций: сдвиг 20, 30, 40, 50
// v теперь содержит {20, 30, 40, 50}

Альтернативы для частых операций удаления из начала:

• std::deque: Удаление с начала (pop_front) имеет амортизированную сложность O(1), так как это двусторонняя очередь.
• std::list: Удаление с начала (pop_front) — O(1), но это связано с накладными расходами на хранение указателей и плохой локальностью данных.