Найдите причину некорректности цикла удаления из std::unordered map: пример с кодом

#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> m{{1, "a"}, {2, "b"}, {3, "c"}};
    for (auto it = m.begin(); it != m.end(); ++it) {
        if (it->first % 2 == 1)
            m.erase(it);
    }
}

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

После m.erase(it) итератор it становится недействительным, но в заголовке цикла выполняется ++it. Это обращение к недействительному итератору приводит к неопределённому поведению.

Безопасный вариант — присвоить итератор, возвращённый erase: it = m.erase(it), а увеличивать его вручную только при сохранении элемента.

Исторический контекст

Ассоциативные контейнеры поддерживают обход элементов, но удаление текущего элемента разрушает объект, на который указывает его итератор. Поэтому интерфейс erase с позицией был спроектирован так, чтобы возвращать итератор на следующий элемент.

Такой подход решает типичную задачу фильтрации контейнера за один проход: программе не нужно заранее искать следующий элемент или вычислять его через уже недействительный итератор.

Постановка проблемы

В цикле текущий итератор используется дважды: сначала передаётся в erase, затем автоматически увеличивается выражением ++it. После удаления он больше не обозначает элемент контейнера, поэтому второе использование нарушает требования к итераторам.

Результат не обязан проявиться сразу. Программа может внешне работать, пропустить элементы или завершиться аварийно — стандарт C++ не определяет такое поведение.

Подробное решение

Используйте возвращаемое значение erase как новый текущий итератор:

#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> m{{1, "a"}, {2, "b"}, {3, "c"}};
    for (auto it = m.begin(); it != m.end();) {
        if (it->first % 2 == 1)
            it = m.erase(it);
        else
            ++it;
    }
}

Если элемент удалён, erase(it) возвращает итератор на следующий элемент либо end(). Если элемент оставлен, его итератор всё ещё действителен, поэтому его можно увеличить обычным ++it.

Для std::unordered_map удаление элемента инвалидирует итератор на удалённый элемент, но не остальные итераторы. Однако операции, способные вызвать rehash, например вставка или reserve, могут инвалидировать все итераторы. Их нельзя бездумно смешивать с таким обходом.

Вызов m.erase(it->first) в этом цикле не является заменой: он удаляет элемент по ключу, но не возвращает следующий итератор. После такого вызова текущий it также нельзя увеличивать.

Сложность удаления одного элемента из std::unordered_map в среднем постоянная, но в худшем случае линейная из-за возможной работы с цепочкой элементов в одном бакете. Полный проход с удалением имеет среднюю сложность O(n).

Ситуация из практики

В обработчике кэша нужно удалить все записи, срок действия которых истёк, не создавая дополнительный список ключей. Рассматривались два варианта.

Первый вариант — сначала скопировать подходящие ключи в std::vector, а затем удалить их по ключу. Он прост для чтения, но требует дополнительной памяти O(k) и второго прохода по данным; кроме того, поиск по ключу выполняется отдельно для каждой записи.

Второй вариант — пройти контейнер и использовать it = cache.erase(it) для удалённых элементов. Он не требует дополнительного массива и выполняет фильтрацию за один проход, поэтому был выбран. Важно не добавлять новые элементы в тот же unordered_map во время обхода: возможный rehash сделает сохранённые итераторы недействительными.

Что кандидаты часто упускают

1. Можно ли написать m.erase(it++); в таком цикле?

   Да, это может быть корректным способом передать старое значение итератора в erase, предварительно сохранив результат постинкремента. Но такой код менее очевиден: порядок вычисления означает, что it сначала получает следующий итератор, а удаляется прежняя позиция. На собеседовании и в production-коде обычно предпочтительнее явный вариант it = m.erase(it).

2. Почему нельзя получить следующий элемент через std::next(it) после удаления?

   std::next(it) должен читать исходный итератор и перемещаться от него. После erase(it) исходный итератор недействителен, поэтому сам факт вызова std::next уже нарушает требования к программе. Следующий итератор нужно получить до удаления либо, что надёжнее, использовать результат erase.

3. Всегда ли вставка в std::unordered_map ломает такой цикл?

   Нет, но она может это сделать. Если вставка вызывает rehash, все итераторы контейнера становятся недействительными; если rehash не происходит, стандарт не требует инвалидировать все итераторы из-за обычной вставки. Надёжный код не должен полагаться на отсутствие rehash: при необходимости заранее вызвать reserve недостаточно для любых будущих изменений, поэтому структурные модификации лучше выполнять отдельно от обхода.