Ответ
Удаление элемента из начала 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), но это связано с накладными расходами на хранение указателей и плохой локальностью данных.
Ответ 18+ 🔞
Давай разберём эту тему, а то тут, бля, такой подвох, что сам от себя охуеешь. Представь, что у тебя есть очередь за колбасой, и первый мужик взял свою палку и ушёл. Что происходит? Правильно, ёпта, все остальные делают шаг вперёд. Так вот твой std::vector — это и есть та самая очередь, только в памяти компьютера.
Когда ты пишешь vector.erase(vector.begin()), ты по сути говоришь: "Эй, чувак, убери-ка этот первый элемент". А компилятор в ответ: "Да похуй, щас, всех остальных подвину". И начинается движуха: каждый следующий элемент копируется или перемещается на место предыдущего. Если у тебя там овердохуища элементов, то это, бля, будет долго — сложность-то O(n). Это как если бы в той очереди стояло тысяча человек, и каждому пришлось бы шагать.
std::vector<int> v = {10, 20, 30, 40, 50};
// Удаляем первый элемент (10)
v.erase(v.begin()); // И тут начинается: 20 сдвигается, 30 сдвигается, 40, 50... пиздец, волнение ебать!
// v теперь содержит {20, 30, 40, 50}Представь, что ты делаешь это в цикле. Это же, ядрёна вошь, будет не удаление, а натуральная пытка для процессора. Каждый раз сдвигать почти весь вектор — это пиздопроебибна идея.
Так что же делать, если надо часто удалять с начала?
std::deque— вот твой спаситель. У него удаление с начала (pop_front) — это амортизированная O(1). Он как хитрая жопа, устроен по-другому, не одним куском, а чанками. Удалил первый элемент из чанка — и всё, остальные даже не шелохнулись. Красота.std::list— ну, тут тоже O(1), потому что это просто список, перекинул указатели — и делов. Но есть нюанс, чувак: локальность данных у него хуй с горы. Элементы разбросаны по памяти как попало, поэтому итерироваться по нему медленнее, кэш процессора не работает. Так что выбирай с умом.
Короче, вывод простой: если тебе надо постоянно ковыряться в начале коллекции, vector — не твой вариант. Бери deque и живи спокойно. А то будешь как тот Гамлет, только вместо "быть или не быть" будешь думать "почему всё так долго, ёпта".
