Временная сложность перебора C++ unordered_map

Question

Я знаю, что unordered_map в C++ STL реализован как хеш-таблица, состоящая из блоков, которые соответствуют хеш-значениям. Время для вставок, удалений и поиска элементов гарантируется как постоянная амортизация. Однако я не совсем понимаю, как итератор работает с этой структурой данных. Когда я увеличиваю итератор, как он узнает, где находится следующая позиция? И какова будет сложность времени, когда я перебираю карту unordered_map с помощью итератора? Время используется, чтобы найти следующую позицию константы итератора? Я нашел некоторую информацию о внутренней структуре unordered_map в книге "Стандартная библиотека C++: учебное пособие и справочник", но не смог найти ответ на свои вопросы. Надеюсь, кто-то может помочь!

Благодарю.

Answer 1

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

1. Посмотрите, есть ли у текущего узла следующий указатель. Если так, иди к этому.
2. Если текущий узел не имеет следующего указателя, перейдите к следующему сегменту, в котором есть узел.
3. Если такого узла нет, значит, вы сделали итерацию.

(Найдите первый узел, найдя первое ведро с узлом в нем.)

Интуитивно понятно, что, поскольку итерация всей хеш-таблицы с использованием вышеуказанного алгоритма равна O(n), может показаться, что каждая "следующая" операция амортизируется с постоянным временем.