Что происходит, когда мы удаляем элемент вектора?

Удаление элементов из вектора в C++

Общее понимание процесса

Когда вы удаляете элемент из вектора с помощью метода erase(), происходят следующие операции:

1. Вызывается деструктор удаляемого элемента
2. Все последующие элементы сдвигаются влево на одну позицию
3. Размер вектора уменьшается на 1
4. Ёмкость остаётся той же (выделенная память не освобождается)

Детальное объяснение с примерами

Удаление одного элемента

#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {10, 20, 30, 40, 50};
    
    std::cout << "До удаления: ";
    for (int x : v) std::cout << x << " ";  // 10 20 30 40 50
    std::cout << std::endl;
    
    // Удаляем элемент по индексу 2 (значение 30)
    v.erase(v.begin() + 2);
    
    std::cout << "После удаления: ";
    for (int x : v) std::cout << x << " ";  // 10 20 40 50
    std::cout << std::endl;
    
    std::cout << "Размер: " << v.size() << std::endl;     // 4
    std::cout << "Ёмкость: " << v.capacity() << std::endl; // 5 (не изменилась!)
    
    return 0;
}

Влияние на итераторы

Основной побочный эффект — итераторы, указывающие на удаляемый элемент и после него, инвалидируются:

std::vector<int> v = {1, 2, 3, 4, 5};

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

// Теперь it невалидный итератор — его нельзя использовать!
// std::cout << *it;  // UNDEFINED BEHAVIOR

// erase() возвращает итератор на следующий элемент
auto next = v.erase(it);  // Безопасно использовать next

Удаление диапазона элементов

std::vector<int> v = {10, 20, 30, 40, 50, 60, 70};

// Удаляем элементы с индекса 2 по 4 включительно (30, 40, 50)
auto new_end = v.erase(v.begin() + 2, v.begin() + 5);

// После удаления: 10 20 60 70
// new_end указывает на 60 (первый элемент после удаленного диапазона)

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

Временная сложность: O(n), где n — количество элементов после удаляемого элемента, которые нужно сдвинуть.

std::vector<int> v(1000);

// O(1) — удаление последнего элемента
v.erase(v.end() - 1);

// O(n) — удаление первого элемента (нужно сдвинуть 999 элементов)
v.erase(v.begin());

// O(n/2) в среднем — удаление из середины
v.erase(v.begin() + 500);

Особенности с пользовательскими типами

Для объектов с нетривиальными деструкторами или конструкторами копирования весь процесс становится более дорогостоящим:

struct Person {
    std::string name;  // Требует копирования
    int age;
    
    Person(const std::string& n, int a) : name(n), age(a) {
        std::cout << "Создание: " << name << std::endl;
    }
    
    ~Person() {
        std::cout << "Удаление: " << name << std::endl;
    }
    
    Person(const Person& other) = default;
    Person& operator=(const Person& other) = default;
};

int main() {
    std::vector<Person> people;
    people.emplace_back("Alice", 30);
    people.emplace_back("Bob", 25);
    people.emplace_back("Charlie", 35);
    
    std::cout << "Удаляем Bob..." << std::endl;
    people.erase(people.begin() + 1);
    // Вывод:
    // Удаление: Bob
    // Удаление: Charlie
    // Создание: Charlie
    // После сдвига Charlie перемещается на позицию Bob
    
    return 0;
}

Оптимизация: shrink_to_fit()

Если вы удалили много элементов, можно освободить лишнюю память:

std::vector<int> v(10000);
v.erase(v.begin(), v.begin() + 9000);  // Удалили 9000 элементов

std::cout << "Размер: " << v.size() << std::endl;      // 1000
std::cout << "Ёмкость: " << v.capacity() << std::endl;  // 10000

// Освобождаем лишнюю память
v.shrink_to_fit();  // или v.shrink_to_fit()

std::cout << "Новая ёмкость: " << v.capacity() << std::endl;  // ~1000

Удаление с условием: erase-remove idiom

Для удаления нескольких элементов по условию используется erase-remove idiom (C++98/03):

#include <algorithm>

std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

// Удалить все чётные числа
auto it = std::remove_if(v.begin(), v.end(), [](int x) {
    return x % 2 == 0;
});
v.erase(it, v.end());
// Результат: 1 3 5 7 9

C++20: std::erase и std::erase_if

В современном C++ появились удобные функции:

#include <vector>

std::vector<int> v = {1, 2, 3, 4, 5, 6};

// Удалить все элементы со значением 3
std::erase(v, 3);

// Удалить все элементы, удовлетворяющие условию
std::erase_if(v, [](int x) { return x > 4; });

Ключевые моменты

• Деструктор вызывается для удаляемого элемента
• Все последующие элементы сдвигаются влево (O(n) операция)
• Итераторы на удаленный элемент и после него инвалидируются
• Ёмкость не уменьшается — используйте shrink_to_fit() если нужно
• Удаление с конца (O(1)) значительно быстрее, чем с начала (O(n))
• Для массового удаления используйте erase-remove idiom или std::erase_if