The complexity of iteration time through C ++ unordered_map

Question

I know that unordered_map in C ++ STL is implemented as a hash table consisting of buckets that correspond to hashed values. Time for inserts, deletions and search for elements is guaranteed that their depreciation will be constant. However, I do not quite understand how the iterator works on this data structure. When I increment the iterator, how does it know where the next position is? And what would be the difficulty in time when I repeated through unordered_map using an iterator? Is time used to find the next position of an iterator constant? I found some information about the internal structure of unordered_map in the book "C ++ Standard Library: Tutorial and Reference", but I could not find the answer to my questions. Hope someone can help!

Thank.

Answer 1

Hash tables are implemented using buckets containing linked lists. The iteration is simple:

• See if the current node has the next pointer. If so, move on to that.
• If the current node does not have the next pointer, go to the next bucket with node.
• If there is no such node, then you have iterated.

(Find the first node by finding the first bucket with node in it.)

Intuitively, since iterating over the entire hash table using the above O (n) algorithm, it would seem that each “next” operation is an amortized constant time.