Удаление элемента из начала (begin()) контейнера std::vector в C++ имеет линейную сложность O(n), где n — количество элементов в векторе. Это поведение связано с особенностями внутренней реализации std::vector как динамического массива.

🔧 Как устроен std::vector

• std::vector представляет собой непрерывный блок памяти, аналогичный обычному массиву (T*).

• Он хранит элементы последовательно, без пропусков.

• Элементы добавляются в конец с амортизированной сложностью O(1).

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

📉 Удаление с начала: что происходит

Рассмотрим код:

std::vector<int> v = {1, 2, 3, 4, 5};
v.erase(v.begin()); // удаляем первый элемент

Под капотом:

1. Первый элемент v[0] удаляется.

2. Все остальные элементы [v[1], v[2], ..., v[n-1]] сдвигаются влево на одну позицию.

3. Последний элемент фактически теряется (т.к. размер вектора уменьшается).

Количество операций перемещения:

• Примерно n - 1 вызовов копирования/перемещения объектов.

📦 Сложность операции

⚠️ Почему не O(1)?

Потому что vector не поддерживает "дырки" в памяти: все элементы должны быть в смежных ячейках. Поэтому при удалении с начала, всё «сдвигается».

В отличие от deque, list или forward_list, которые предназначены для эффективной вставки/удаления в начале/середине.

💡 Последствия

1. Если часто требуется удаление с начала — vector не подходит.

2. Альтернативы:

   • std::deque — быстрая вставка/удаление в начале и в конце.

   • std::list — двусвязный список, эффективный для произвольных удалений, но не кэш-френдли.

   • std::queue (на базе deque по умолчанию).

📊 Пример

std::vector<int> v;
for (int i = 0; i < 10000; ++i)
v.push_back(i);
// Удаление с начала
while (!v.empty())
v.erase(v.begin()); // O(n) на каждую итерацию → общая O(n²)

Этот код очень медленный на больших объёмах, потому что каждый erase(v.begin()) требует копирования n - 1 элементов.

🧠 Способы избежать дорогостоящего erase(v.begin())

1. Поменять контейнер:

std::deque<int> d;
d.push_back(1);
d.pop_front(); // O(1)

1. Использовать "логический индекс начала" (сдвиг окна):

std::vector<int> v = {1,2,3,4,5};
size_t start = 0; // логическое начало
// Вместо erase — просто увеличиваем логическое начало
start++;
// Элемент v\[start\] — фактический первый элемент

Но в этом случае вы должны сами следить за памятью, возможно проводить сжатие/очистку позднее.

🧪 Анализ производительности (асимптотика)

Если n — количество элементов:

• Одна операция erase(v.begin()) — O(n).

• Повторить её n раз — O(n²).

• Поэтому для очередей (FIFO) std::vector нежелателен.

🧾 Резюме поведения erase

v.erase(v.begin()); // O(n)
v.erase(v.end() - 1); // O(1)
v.erase(v.begin() + i); // O(n - i)

Чем ближе элемент к концу вектора, тем быстрее операция.

💬 Альтернативные контейнеры и их поведение

Таким образом, std::vector отлично подходит для сценариев, где данные обрабатываются в конце (например, стек), но неэффективен для очередей и других структур, требующих частого удаления в начале.