Правила инвалидации итераторов в C++: когда итераторы становятся недействительными?

Что такое инвалидация итераторов и почему ваш код ломается?

Итератор — это объект, который "указывает" на элемент контейнера. Когда контейнер изменяется (добавление, удаление элементов), некоторые или все итераторы могут стать недействительными — они перестают указывать на валидные данные. Использование такого итератора приводит к неопределенному поведению (UB), что может вызвать краш, мусорные данные или незаметные ошибки.

В вашем коде проблема в строке orders.erase(it). После удаления элемента итератор it становится недействительным. Но вы тут же делаете ++it в заголовке цикла for, что является UB. Вот почему программа падает.

Правила инвалидации для основных контейнеров

Последовательные контейнеры (vector, deque, string)

• push_back/push_front: Если происходит реаллокация (превышение capacity), все итераторы и ссылки становятся недействительными. Если реаллокации нет — итераторы недействительны только для deque (при push_front).
• insert/emplace: Все итераторы после точки вставки становятся недействительными (из-за сдвига элементов).
• erase: Итераторы, указывающие на удаленный элемент и на все последующие элементы, становятся недействительными.
• reserve/resize: Если происходит реаллокация — все итераторы инвалидируются.

Связные списки (list, forward_list)

• insert/emplace: Итераторы остаются валидными (кроме вставленного элемента).
• erase: Недействителен только итератор на удаленный элемент.
• splice: Итераторы остаются валидными.

Ассоциативные контейнеры (set, map, unordered_set и т.д.)

• insert/emplace: Итераторы остаются валидными (для unordered — если нет рехеширования).
• erase: Недействителен только итератор на удаленный элемент.
• clear: Все итераторы становятся недействительными.

Как правильно удалять элементы во время итерации

Есть два основных подхода:

1. Использовать возвращаемое значение erase (для последовательных контейнеров)

Метод erase возвращает итератор на следующий после удаленного элемент. Используйте его:

std::vector<int> orders = {101, 102, 103, 104, 105};

for (auto it = orders.begin(); it != orders.end(); ) {
    if (*it == 103) {
        it = orders.erase(it);  // it теперь указывает на 104
    } else {
        ++it;
    }
}

2. Использовать std::remove_if + erase (идиома "erase-remove")

Это более эффективно для vector, так как минимизирует количество перемещений элементов:

#include <algorithm>

std::vector<int> orders = {101, 102, 103, 104, 105};

auto new_end = std::remove_if(orders.begin(), orders.end(),
                               [](int x) { return x == 103; });
orders.erase(new_end, orders.end());

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

• Всегда проверяйте документацию вашего контейнера перед модификацией во время итерации.
• Для vector и deque предпочитайте идиому "erase-remove".
• Для list и ассоциативных контейнеров безопасно использовать возвращаемое значение erase.
• Избегайте хранения итераторов между модификациями контейнера, если не уверены в правилах.
• В C++20 появился std::erase и std::erase_if для всех контейнеров — это самый простой способ:

std::erase_if(orders, [](int x) { return x == 103; });  // C++20

Запомните главное правило: никогда не используйте итератор после операции, которая может его инвалидировать. Всегда обновляйте итератор из результата модифицирующей операции.

void test_erase_during_iteration() {
    std::vector<int> v = {1, 2, 3};
    auto it = v.begin();
    v.erase(it);  // Ошибка! it теперь недействителен
    // assert(*it == 2);  // UB
}