Здравствуйте! На прошлом занятии мы узнали, как работают итераторы в контейнере map, то есть в двоичных деревьях поиска. Сейчас мы поговорим о том, как работают итераторы в unordered_map, то есть в хеш-таблицах. Посмотрим, например, хеш-таблицы. И для начала установим итератор на begin. Он указывает на первый элемент списка в первой непустой корзине. Инкремент итератора, то есть вызов оператора ++, происходит очень просто, это просто итерирование по односвязному списку. Если при очередном инкременте мы дошли до конца цепочки, то потом мы переходим далее, в следующую непустую корзину. И в том, и в другом случае инкремент будет стоить очень дешево. Нам надо лишь перейти по указателям на следующий элемент, либо перейти в следующую корзину. Согласитесь, это намного проще, чем вычисления на деревьях, и казалось бы с декрементом все должно быть аналогично, но нет, оказывается, мы вообще не можем вызывать оператор -- для таких итераторов. Это подчеркивается на схемах тем, что стрелки на рисунках направлены в одну сторону, то есть итераторы в хеш-таблицах ещё менее мощны, чем в двоичных деревьях поиска. Для них есть специальное название: последовательное, либо по простому forward iterator. Кажется, что мы уже закончили разбираться с итераторами в хеш-таблицах, они же заметно проще, чем итераторы в деревьях, но не совсем, есть важный нюанс: помните, мы затрагивали важное свойство хеш-таблиц, что их цепочки должны быть короткими. Для поддержания этого свойства иногда может случаться рехеширование - перекладывание существующих элементов по другим корзинкам, чтобы не держать их переполненными. Как именно это происходит - вопрос отдельный, но схематично пример изображён вот здесь. Теперь давайте задумаемся, что же будет с порядком элементов хеш-таблицы после рехеширования. Вообще, судя по названию unordered_map, элементы и так не были упорядоченны, а мы ещё и разложим их по корзинам по-новому. А что же будет с итераторами после рехеширования? Можно ли ими продолжать пользоваться? И для ответа на этот вопрос обратимся к документации. Давайте откроем cppreference и посмотрим, что нам говорит стандарт. Действительно, при вставке элементов в хеш-таблицу может случиться рехеширование, и в этом случае все итераторы инвалидируются. В наших предыдущих курсах мы уже разбирали, что такое инвалидация. Это значит, что итераторы перестают указывать туда, куда должны, и их использование может привести либо к падению программы, либо к неверному результату, либо к неопределенному поведению. Заметим, что итераторы в контейнере map, то есть в двоичном дереве поиска, более устойчивы и живучи в этом смысле. Даже когда при вставке нового элемента в дерево происходит перебалансировка и какой-то элемент, на который указывал итератор, смещается - проблемы нет, он просто поменяет связи с соседями, но с ним можно продолжать работать далее. Давайте ещё раз сравним инвалидацию итераторов в различных контейнерах. Использовать имеющиеся итераторы после вставки в хеш-таблицу - плохая идея, потому что они могут инвалидироваться, а вот удалять можно не опасаясь. Конечно, если удалить элемент по итератору, то он тоже инвалидируется - тут уж ничего не поделаешь. Итак, сегодня мы поговорили о том, как устроены итераторы в unordered_map и unordered_set, разобрали, что итераторы последовательные, то есть их можно двигать только вперёд на один шаг. Каждый инкремент стоит константу. Также обсудили, что при вставке элементов может произойти рехеширование, и тогда нельзя продолжать пользоваться имеющимися итераторами.
