Есть ли особенности итераторов в зависимости от контейнера в C++

Что проверяют

Знаете ли вы категории итераторов и, главное, правила их инвалидации для каждого контейнера. Следом почти всегда дают код с удалением элементов в цикле и спрашивают, где тут неопределённое поведение.

Как отвечать

Особенности есть, и их две группы: какая у контейнера категория итератора и когда итераторы становятся недействительными.

По категориям:

• contiguous (C++20) и random access: vector, array, string дают непрерывную память и it + n за O(1); deque тоже random access, но память у него не сплошная;
• bidirectional: list, set, map и multi-версии, умеют ++ и --, но не прыжок на n;
• forward: forward_list и неупорядоченные unordered_set, unordered_map, только вперёд.

От категории зависят алгоритмы. std::sort требует random access, поэтому у list есть свой list::sort(). std::advance и std::distance на списке идут за O(n). В set ищите методом s.lower_bound(x): свободная std::lower_bound на двунаправленных итераторах сделает O(log n) сравнений, но O(n) шагов. Ключ через итератор ассоциативного контейнера менять нельзя: у map элемент имеет тип pair<const Key, T>.

Инвалидация:

• vector: вставка с превышением capacity инвалидирует всё, без него только итераторы после точки вставки; erase инвалидирует всё начиная с удалённого;
• deque: вставка в середину ломает всё, вставка в начало или конец ломает итераторы, но не ссылки на элементы;
• list, set, map: вставка ничего не ломает, удаление инвалидирует только удалённый элемент;
• unordered-контейнеры: рехеширование инвалидирует итераторы, но не ссылки и указатели.

Где спотыкаются

Удаляют в цикле через v.erase(it), а потом делают ++it. Правильно it = v.erase(it), а с C++20 проще std::erase_if(v, pred).

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

Говорят, что доступ через итератор map стоит O(log n). Разыменование O(1), инкремент амортизированно O(1), логарифм стоит поиск, а не обход.