Как происходит инвалидирование итераторов в контейнере unordered_map?

Инвалидация итераторов std::unordered_map происходит при изменении структуры хеш-таблицы или удалении элементов.

Основные случаи:

• Вставка: При вставке элемента может потребоваться перехеширование (реаллокация и перестройка таблицы), если коэффициент загрузки превышает max_load_factor(). В этом случае все итераторы, ссылки и указатели на элементы становятся недействительными. Если перехеширования не происходит, итераторы на существующие элементы остаются валидными, а итератор, указывающий на конец контейнера (end()), может стать недействительным.
• Удаление: Удаление одного элемента с помощью итератора (erase(pos)) инвалидирует только итератор pos и ссылки/указатели на удаленный элемент. Итераторы на другие элементы остаются валидными. Удаление диапазона элементов (erase(first, last)) инвалидирует все итераторы, ссылки и указатели в удаленном диапазоне. Использование clear() или удаление с помощью ключа (erase(key)) инвалидирует все итераторы, ссылки и указатели на удаленные элементы. Итераторы на другие элементы остаются валидными.
• Перехеширование (rehash): Явный вызов rehash() или автоматическое перехеширование из-за вставки инвалидирует все итераторы, ссылки и указатели.
• Резервирование (reserve): Аналогично перехешированию, явный вызов reserve() может вызвать реаллокацию и инвалидацию всех итераторов, ссылок и указателей.

Важно помнить, что в unordered_map порядок элементов не гарантируется, и при изменении контейнера расположение элементов может меняться независимо от инвалидации итераторов.

#include <unordered_map>
#include <iostream>

int main() {
    std::unordered_map<int, std::string> my_map;
    my_map[1] = "one";
    my_map[2] = "two";

    auto it = my_map.begin(); // Итератор на начало

    my_map[3] = "three"; // Вставка, может вызвать перехеширование и инвалидировать it

    // Вставка без перехеширования (например, если load_factor низкий)
    // it может остаться валидным, но его позиция может измениться логически

    // auto it_to_erase = my_map.find(1);
    // if (it_to_erase != my_map.end()) {
    //     my_map.erase(it_to_erase); // Инвалидирует it_to_erase
    //     // Другие итераторы остаются валидными
    // }

    // my_map.clear(); // Инвалидирует все итераторы

    return 0;
}