Какая асимптотическая сложность удаления в vector?

Какая асимптотическая сложность удаления в vector?

Краткий ответ

Удаление элемента из std::vector имеет сложность O(n) в худшем случае, где n — количество элементов в vector.

Почему именно O(n)?

std::vector — это динамический массив. Его элементы хранятся в памяти последовательно. Когда вы удаляете элемент, все элементы после него нужно сдвинуть на позицию влево, чтобы заполнить "дыру".

std::vector<int> vec = {10, 20, 30, 40, 50};
//                       0   1   2   3   4

// Удаление элемента на позиции 1 (значение 20)
vec.erase(vec.begin() + 1);

// Процесс:
// Было:    [10, 20, 30, 40, 50]
// Шаг 1:   Удаляем 20
// Шаг 2:   Сдвигаем 30 на позицию 1
// Шаг 3:   Сдвигаем 40 на позицию 2
// Шаг 4:   Сдвигаем 50 на позицию 3
// Итог:    [10, 30, 40, 50]

Количество операций сдвига: n - i - 1, где i — позиция удаляемого элемента и n — размер вектора.

Анализ разных случаев

Удаление с конца (last element):

vec.pop_back();  // или vec.erase(vec.end() - 1);
// Сложность: O(1) — никаких сдвигов не требуется

Удаление с начала (first element):

vec.erase(vec.begin());
// Нужно сдвинуть все n-1 элементов
// Сложность: O(n)

Удаление с середины:

vec.erase(vec.begin() + i);
// Нужно сдвинуть n - i - 1 элементов
// Сложность: O(n) в худшем случае

Практический пример

#include <iostream>
#include <vector>
#include <chrono>

int main() {
    const int n = 1000000;
    std::vector<int> vec(n);
    for (int i = 0; i < n; ++i) {
        vec[i] = i;
    }
    
    // Удаление с конца
    auto start = std::chrono::high_resolution_clock::now();
    vec.pop_back();
    auto end = std::chrono::high_resolution_clock::now();
    std::cout << "Pop back: " 
              << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count()
              << " мкс\n";  // ~0.001 мкс
    
    // Удаление с начала
    start = std::chrono::high_resolution_clock::now();
    vec.erase(vec.begin());
    end = std::chrono::high_resolution_clock::now();
    std::cout << "Erase at begin: "
              << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count()
              << " мкс\n";  // ~1000-2000 мкс (зависит от CPU)
    
    return 0;
}

Вывод: Удаление с начала в 1000+ раз медленнее, чем с конца!

Удаление нескольких элементов

Неправильно (O(n²)):

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

// Удалить все четные числа
for (int i = 0; i < vec.size(); ++i) {
    if (vec[i] % 2 == 0) {
        vec.erase(vec.begin() + i);  // O(n) для каждого элемента!
        --i;  // Компенсируем сдвиг
    }
}
// Итоговая сложность: O(n²)

Правильно (O(n)) — использовать erase-remove idiom:

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

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

Как это работает:

1. std::remove_if() переместит все элементы, которые нужно оставить, в начало
2. Вернет итератор на новый конец
3. erase() удалит элементы от этого итератора до конца

Проблема с вектором — почему он медленный для удаления

Вектор vs Список (std::list):

// Vector
std::vector<int> vec = {1, 2, 3, 4, 5};
vec.erase(vec.begin() + 1);  // O(n) — нужно сдвигать элементы

// List
std::list<int> lst = {1, 2, 3, 4, 5};
auto it = lst.begin();
++it;  // Указатель на 2
lst.erase(it);  // O(1) — просто переconectить связи в списке

Когда использовать каждый контейнер:

• std::vector: частый доступ по индексу, редкие удаления (или удаления с конца)
• std::list: частые удаления и вставки в середину
• std::deque: удаления с обоих концов, быстрый доступ

Практический совет

Если нужно удалить много элементов из вектора:

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

// Вариант 1: создать новый вектор (O(n))
for (int x : original) {
    if (x % 2 != 0) {
        filtered.push_back(x);
    }
}

// Вариант 2: erase-remove idiom (O(n))
original.erase(
    std::remove_if(original.begin(), original.end(),
                   [](int x) { return x % 2 == 0; }),
    original.end()
);

Оба варианта имеют O(n), но создание нового вектора часто быстрее в практике благодаря лучшей локальности памяти.

Итоговая таблица сложностей

Заключение

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