Remove Then Erase

Проблема: производительность erase.

Идиома remove-erase позволяет эффективно удалить элементы из контейнера (std::vector, std::deque, std::string) по заданному условию. Она состоит из двух шагов:

• std::remove сдвигает нужные элементы в конец
• метод контейнера .erase() удаляет их из памяти

Суть идиомы - избежать квадратичной сложности при поэлементном удалении в цикле.

Неправильно:

#include <vector>

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

    for (auto it = v.begin(); it != v.end(); ) {
        if (*it == 2)
            it = v.erase(it); // O(n) сдвиг на каждой итерации
        else
            ++it;
    }
}

Каждый вызов erase вызывает перемещение всех элементов, следующих за удаляемым. При частых удалениях (например, каждом втором элементе) суммарная сложность становится O(n²). На больших векторах это катастрофа для производительности.

Правильно:

#include <vector>
#include <algorithm>

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

    // Один проход — O(n), один вызов erase — O(n)
    v.erase(std::remove(v.begin(), v.end(), 2), v.end());
}

std::remove делает один линейный проход, сдвигая сохраняемые элементы на освободившиеся места без многократных перемещений хвоста. Затем один вызов erase подчищает «мусор» в конце. Итоговая сложность - O(n). На миллионе элементов разница между O(n) и O(n²) - это разница между мгновенным выполнением и зависанием.

Не нужно использовать идиому в std::list и std::forward_list - у них есть оптимизированный метод remove() (и remove_if()), который делает всё сам за O(n) без лишних копирований:

std::list<int> lst = {1, 2, 3, 2, 4};
lst.remove(2); // Встроенный метод — быстро и без идиомы

Использовать std::remove на списке — плохая идея: он будет переставлять элементы, а не перелинковывать узлы, теряя главное преимущество списка.