Удаление элемента из вектора по индексу: анатомия std::vector::erase

Как стереть элемент из std::vector по индексу: заглядываем под капот

Привет, коллега! Если ты когда-нибудь писал на C++ и работал с динамическими массивами, то наверняка сталкивался с вопросом: "How do I erase an element from std::vector<> by index?" — это один из самых популярных запросов на Stack Overflow, и не зря. На первый взгляд, задача кажется тривиальной: вызвал erase — и готово. Но что на самом деле происходит в памяти? Почему удаление из середины вектора стоит дорого? И как не наступить на грабли с итераторами?

В этой статье мы не просто покажем, как написать v.erase(v.begin() + index). Мы разберёмся, как эта операция работает под капотом, какие структуры данных задействованы и как выбрать оптимальный способ удаления. Погнали!

1. std::vector: что это за зверь?

Прежде чем удалять, давай вспомним, как устроен std::vector. Это динамический массив, который хранит элементы в непрерывной области памяти. У него есть три ключевых указателя (или итератора):

• begin — начало выделенной памяти;
• end — конец занятой памяти (за последним элементом);
• capacity — конец выделенной памяти (граница, до которой можно расти без перераспределения).

Визуально это выглядит так:

[0] [1] [2] [3] [4] ... [capacity-1]
 ^                        ^
 begin                   end

Когда ты удаляешь элемент из середины, вектор не просто "выкидывает" его — он физически сдвигает все последующие элементы влево. Это и есть главная "боль" операции erase.

2. Удаление по индексу: базовый синтаксис

Самый простой способ удалить элемент по индексу — использовать метод erase с итератором:

#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {10, 20, 30, 40, 50};
    int index = 2; // хотим удалить третий элемент (30)

    // Проверяем, что индекс в пределах
    if (index < v.size()) {
        v.erase(v.begin() + index);
    }

    for (int x : v) std::cout << x << " ";
    // Вывод: 10 20 40 50
    return 0;
}

Всё просто, правда? Но что если нужно удалить несколько элементов подряд? Для этого есть перегрузка erase(first, last):

v.erase(v.begin() + 1, v.begin() + 3); // удалит элементы с индексами 1 и 2

3. А что под капотом? Детальный разбор

Теперь самое интересное. Когда ты вызываешь v.erase(iterator), внутри происходит следующее:

1. Проверка итератора (в debug-режиме) — убеждаемся, что он валиден и указывает на элемент вектора.
2. Сдвиг элементов — все элементы, находящиеся после удаляемого, копируются (или перемещаются, если тип поддерживает move semantics) на одну позицию влево.
3. Уменьшение размера — внутренний счётчик size уменьшается на 1.
4. Деструктор — для "хвостового" элемента (который теперь дублируется) вызывается деструктор (если тип не тривиальный).

Давай посмотрим на упрощённую реализацию (псевдокод):

template<typename T>
typename std::vector<T>::iterator
vector<T>::erase(iterator pos) {
    // 1. Сдвигаем все элементы после pos на одну позицию влево
    for (auto it = pos; it != end() - 1; ++it) {
        *it = std::move(*(it + 1));
    }
    // 2. Уменьшаем размер
    --size;
    // 3. Вызываем деструктор для последнего элемента
    allocator.destroy(end()); // end() теперь указывает на бывший последний элемент
    return pos; // возвращаем итератор на элемент, следующий за удалённым
}

Обрати внимание на std::move — современный C++ старается избежать лишних копирований. Если тип поддерживает перемещение, будет использован move assignment. Если нет — обычное копирование.

4. Почему erase — это O(n)?

Из предыдущего раздела ясно: чтобы удалить элемент по индексу i, нужно сдвинуть n - i - 1 элементов. В худшем случае (удаление первого элемента) — сдвигаются все n-1 элементов. Отсюда и линейная сложность — O(n).

Для сравнения:

• pop_back() — O(1). Просто уменьшаем size, никаких сдвигов.
• erase в конце — O(1). Почти как pop_back, но с возвратом итератора.
• erase в начале или середине — O(n).

Это важно помнить при проектировании высоконагруженных систем. Если тебе нужно часто удалять элементы из середины, возможно, std::vector — не лучший выбор. Присмотрись к std::list (двусвязный список) или std::deque (двусторонняя очередь).

5. Типичные ошибки и как их избежать

5.1. Инвалидация итераторов

Самая частая проблема — после вызова erase все итераторы, указывающие на элементы после удалённого, становятся недействительными. Пример:

std::vector<int> v = {1, 2, 3, 4, 5};
auto it = v.begin() + 2; // указывает на 3
v.erase(v.begin());      // удаляем первый элемент
// it теперь указывает на неопределённое место!
std::cout << *it; // ОПАСНО: неопределённое поведение

Правильный подход — обновлять итератор, используя возвращаемое значение erase:

auto it = v.begin() + 2;
it = v.erase(v.begin()); // it теперь указывает на новый первый элемент (2)

5.2. Удаление в цикле

Если нужно удалить несколько элементов по условию, не делай так:

// НЕПРАВИЛЬНО: после erase итератор инвалидируется
for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it % 2 == 0) {
        v.erase(it); // it теперь недействителен!
    }
}

Правильный вариант — использовать erase-remove idiom или обновлять итератор:

// Вариант 1: erase-remove idiom (рекомендуется)
v.erase(std::remove_if(v.begin(), v.end(),
                       [](int