🔥 Почему v.erase(remove(...)) быстрее цикла с erase()?

Разница может быть существенной на больших векторах. Дело в количестве сдвигов памяти.

🍬 Наивный подход:

for (auto it = v.begin(); it != v.end(); ) {
    if (*it == target)
        it = v.erase(it); // каждый раз сдвиг O(n)
    else
        ++it;
}

Если удаляешь k элементов из вектора размера n, получаешь O(k×n) операций копирования. При k≈n/2 это O(n²).

⚡️ Erase-remove idiom:

v.erase(std::remove(v.begin(), v.end(), target), v.end());

remove() делает O(n) перемещений, erase() делает один сдвиг хвоста O(n). Итого O(n) вместо O(n²).

❗️Вывод: Это не микрооптимизация, а правильный алгоритм. При удалении из середины вектора — всегда используй erase-remove.

📍Навигация: Вакансии • Задачи • Собесы

Библиотека C/C++ разработчика

#под_капотом