Какая сложность удаления элемента из std::vector?

Какая сложность удаления элемента из std::vector?

Это классический вопрос на собеседованиях, так как ответ раскрывает понимание того, как устроены контейнеры STL и как нужно выбирать структуры данных.

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

O(n) в худшем случае, где n - количество элементов ПОСЛЕ удаляемого элемента.

Почему? Потому что vector хранит элементы последовательно в памяти, и при удалении нужно сдвинуть все элементы после удаляемого.

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

Структура vector

vector<int> v = {10, 20, 30, 40, 50};

В памяти:
[10] [20] [30] [40] [50]
  ^   ^    ^    ^    ^
index 0   1    2    3    4

Удаление элемента с индексом 2 (значение 30)

До удаления:
[10] [20] [30] [40] [50]

После удаления:
[10] [20] [40] [50] [???]
            ^    ^
        Сдвинуты

Векторный сдвигает элементы 40 и 50 на одну позицию влево. Это требует O(n-2) = O(n) копий в худшем случае.

Анализ сложности для разных позиций

std::vector<int> v = {10, 20, 30, 40, 50};  // 5 элементов

// Удаление с конца O(1)
v.erase(v.end() - 1);  // Удалить 50
// Операций: 0 сдвигов

// Удаление из середины O(n/2) = O(n)
v.erase(v.begin() + 2);  // Удалить 30
// Операций: 2 сдвига (40 и 50)

// Удаление с начала O(n)
v.erase(v.begin());  // Удалить 10
// Операций: 4 сдвига (20, 30, 40, 50)

Реальная реализация

Внутри vector, erase() реализован примерно так:

template<typename T>
iterator vector<T>::erase(const_iterator position) {
    // position указывает на элемент для удаления
    // end() - указатель на конец вектора
    
    // Копируем все элементы ПОСЛЕ удаляемого на позицию удаляемого
    iterator it = begin() + std::distance(begin(), position);
    
    // std::move сдвигает элементы
    std::move(it + 1, end(), it);
    
    // Уменьшаем размер
    _size--;
    
    return it;
}

// Фактически:
vector: [10, 20, 30, 40, 50]
//                ^   ^   ^
// move(it+1, end(), it) сдвигает [40, 50] на позицию 30
vector: [10, 20, 40, 50, ???]

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

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

// ПЛОХО: O(n^2)
for (int i = 0; i < 5; ++i) {
    v.erase(v.begin());  // O(n) операция повторяется n раз
}
// Всего операций: n + (n-1) + (n-2) + ... = O(n^2)

// ХОРОШО: O(n)
v.erase(v.begin(), v.begin() + 5);  // O(n) за одну операцию
// Все элементы сдвигаются один раз

// ЕЩЕ ЛУЧШЕ: Erase-remove idiom O(n)
v.erase(
    std::remove_if(v.begin(), v.end(), 
        [](int x) { return x < 6; }  // удалить < 6
    ),
    v.end()
);

Erase-Remove Idiom

Для удаления нескольких элементов по условию:

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

// Удалить все четные числа
v.erase(
    std::remove_if(v.begin(), v.end(),
        [](int x) { return x % 2 == 0;}
    ),
    v.end()
);

// Результат: {1, 3, 5, 7, 9}

Почему это лучше?

Шаг 1: remove_if переносит "плохие" элементы в конец O(n)
vector после remove_if: [1, 3, 5, 7, 9, ???, ???, ???, ???, ???]
                                        ^
                    Возвращает new_end

Шаг 2: erase удаляет хвост O(k), где k - кол-во удаленных

Итого: O(n + k) = O(n)

Сравнение с другими контейнерами

// std::vector<T>
// Удаление в начале: O(n)
// Удаление в конце: O(1)
// Удаление в середине: O(n)
// Memory: плотно упакована

v.erase(v.begin());  // Дорого!

// std::deque<T>
// Удаление в начале: O(1)
// Удаление в конце: O(1)
// Удаление в середине: O(n)
// Memory: чанки памяти

dq.erase(dq.begin());  // Дешево!

// std::list<T>
// Удаление в начале: O(1)
// Удаление в конце: O(1)
// Удаление в середине: O(1) если есть итератор
// Memory: разреженная (много overhead)

list.erase(iter);  // Дешево!

// std::set<T>
// Удаление: O(log n)
// Плюс: автоматически отсортирован

set.erase(value);  // O(log n)

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

Пример 1: Фильтрация вектора

// Удалить элементы больше 5
vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

// Способ 1: ПЛОХО - O(n^2)
for (auto it = v.begin(); it != v.end(); ) {
    if (*it > 5) {
        it = v.erase(it);  // O(n) операция
    } else {
        ++it;
    }
}

// Способ 2: ХОРОШО - O(n)
v.erase(
    std::remove_if(v.begin(), v.end(),
        [](int x) { return x > 5; }
    ),
    v.end()
);

Пример 2: Удаление дубликатов

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

// Сначала отсортировать
std::sort(v.begin(), v.end());

// Потом unique + erase - O(n)
v.erase(
    std::unique(v.begin(), v.end()),
    v.end()
);

// Результат: {1, 2, 3, 4}

Пример 3: Оптимизированное удаление

class OptimizedRemoval {
public:
    static void removeByIndex(vector<int>& v, int index) {
        // Поменять с последним и удалить
        std::swap(v[index], v.back());
        v.pop_back();  // O(1)
        // Результат: элементы переставляются, но O(1) операция
    }
};

vector<int> v = {10, 20, 30, 40, 50};
OptimizedRemoval::removeByIndex(v, 2);  // Удалить 30
// Результат: {10, 20, 50, 40} (порядок нарушен, но O(1))

Оптимизация: swap and pop

Если порядок элементов не важен:

// ПЛОХО: O(n)
vector<int> v = {1, 2, 3, 4, 5};
v.erase(v.begin() + 2);  // O(3)

// ХОРОШО: O(1)
vector<int> v = {1, 2, 3, 4, 5};
std::swap(v[2], v.back());
v.pop_back();
// Результат: {1, 2, 5, 4}

Ключевые выводы

1. Удаление из vector: O(n) в худшем случае
2. Удаление из конца: O(1) - используйте pop_back()
3. Удаление нескольких элементов: используйте erase-remove idiom O(n)
4. Если нужно часто удалять из начала: используйте deque или list
5. Если порядок не важен: используйте swap and pop для O(1)
6. Для фильтрации: используйте remove_if + erase

Выбор контейнера зависит от паттерна использования - нет универсального лучшего решения!