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

Если вставка в std::unordered_map вызывает rehash, все ранее полученные итераторы этого контейнера становятся недействительными. При этом ссылки и указатели на уже существующие элементы сохраняют действительность, пока сами элементы не удалены.

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

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

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

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

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

Итератор обычно содержит не только ссылку на элемент, но и сведения о текущем положении внутри структуры контейнера. После rehash внутренняя организация корзин меняется, поэтому старое положение больше нельзя считать корректным.

Использование такого итератора после вставки приводит к неопределённому поведению. Особенно опасна ситуация, когда программа сохраняет итераторы, затем добавляет элементы, а после этого разыменовывает сохранённые итераторы или продолжает обход.

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

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

Во время этого перемещения итераторы инвалидируются, даже если объекты элементов физически не копируются. Для стандартных unordered-контейнеров ссылки и указатели на элементы при rehash не инвалидируются: узлы с элементами сохраняют адреса. Исключение — удаление соответствующего элемента.

Проверить или предотвратить неожиданный rehash можно с помощью операций reserve, rehash, а также настройкой max_load_factor. reserve задаёт минимальную ёмкость, достаточную для указанного числа элементов с учётом текущего максимального коэффициента загрузки, но не является гарантией, что будущие операции никогда не изменят структуру.

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    m.reserve(100);
    m.emplace(1, 10);

    int& reference = m.at(1);
    auto iterator = m.find(1);

    m.emplace(2, 20); // rehash здесь не обязан происходить

    std::cout << reference << '\
'; // ссылка остаётся корректной
    // iterator можно использовать только если вставка не вызвала rehash
}

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

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

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

Сервис строит индекс по идентификаторам объектов. Для каждого найденного объекта сохраняется итератор, затем индекс пополняется новыми объектами, после чего сохранённые итераторы используются для формирования ответа.

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

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

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

Инвалидируются ли ссылки на элементы при rehash?

Нет, сам по себе rehash ссылки и указатели на существующие элементы std::unordered_map не инвалидирует. Элементы обычно организованы как отдельные узлы, поэтому изменение массива корзин меняет связи с узлами, но не обязано менять адреса узлов. Ссылка всё равно становится недействительной, если соответствующий элемент удалить или уничтожить контейнер.

Гарантирует ли reserve отсутствие инвалидирования итераторов при последующих вставках?

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

Всегда ли вставка без rehash сохраняет все итераторы?

Для вставки в unordered-контейнеры отсутствие rehash означает, что итераторы на существующие элементы не инвалидируются. Однако итератор, относящийся к удалённому элементу, после erase недействителен независимо от rehash. Поэтому нужно отдельно учитывать операции вставки, перераспределения и удаления, а не считать контейнер неизменяемым только потому, что его размер вырос незначительно.