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

1️⃣ Как кратко ответить

При удалении элемента из вектора в C++ все элементы, следующие за удаляемым, сдвигаются на одну позицию влево. Это может вызвать перераспределение памяти, если вектор уменьшает свой размер. Операция удаления имеет линейную сложность O(n), так как требует перемещения элементов.

2️⃣ Подробное объяснение темы

Вектор в C++ — это динамический массив, который может изменять свой размер. Он предоставляет удобные методы для добавления и удаления элементов. Однако, удаление элемента из вектора требует понимания того, как это влияет на внутреннюю структуру и производительность.

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

1. Сдвиг элементов: Все элементы, которые находятся после удаляемого, сдвигаются на одну позицию влево. Это необходимо для того, чтобы заполнить "пустое" место, оставшееся после удаления элемента. Например, если у вас есть вектор [1, 2, 3, 4, 5] и вы удаляете элемент 3, то вектор станет [1, 2, 4, 5].

2. Изменение размера: Вектор уменьшает свой размер на единицу. Однако, это не обязательно означает, что память будет освобождена. Вектор может сохранить выделенную память для будущих добавлений элементов, чтобы избежать частого перераспределения памяти.

3. Перераспределение памяти: Хотя удаление элемента само по себе не вызывает перераспределение памяти, вектор может перераспределить память, если его размер значительно уменьшился и он решает освободить неиспользуемую память. Это зависит от реализации и политики управления памятью вектора.

4. Сложность операции: Удаление элемента из вектора имеет линейную сложность O(n), где n — количество элементов, следующих за удаляемым. Это связано с необходимостью сдвига всех этих элементов.

Рассмотрим пример кода, чтобы понять, как это работает:

#include <iostream>
#include <vector>
​
int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
​
    // Удаляем элемент с индексом 2 (значение 3)
    numbers.erase(numbers.begin() + 2);
​
    // Выводим элементы вектора после удаления
    for (int number : numbers) {
        std::cout << number << " ";
    }
​
    return 0;
}

• #include <iostream> и #include <vector>: Подключаем заголовочные файлы для работы с потоками ввода-вывода и векторами.
• std::vector<int> numbers = {1, 2, 3, 4, 5};: Создаем вектор numbers и инициализируем его значениями от 1 до 5.
• numbers.erase(numbers.begin() + 2);: Удаляем элемент с индексом 2 (значение 3). Метод erase принимает итератор на элемент, который нужно удалить. numbers.begin() + 2 указывает на третий элемент вектора.
• for (int number : numbers): Используем цикл for для перебора всех элементов вектора после удаления.
• std::cout << number << " ";: Выводим каждый элемент вектора на экран, чтобы увидеть результат удаления.

Этот пример демонстрирует, как удаление элемента из вектора приводит к сдвигу оставшихся элементов и уменьшению размера вектора.