Time complexity of iterating through a C++ unordered_map [duplicate]

Question

I know that the unordered_map in C++ STL is implemented as hashtable consisting of buckets that correspond to hashed values. The time for insertions, deletions and element search is guaranteed to be amortized constant. However I don't quite understand how the iterator works on this data structure. When I increment the iterator, how does it know where is the next position? And what would the time complexity be when I iterated through a unordered_map using an iterator? Is the time used to find the next position of the iterator constant ? I found some information on the internal structure of unordered_map in the book The C++ Standard Library: A tutorial and Reference but I couldn't find the answer to my questions. Hope someone can help!

Thanks.

Answer 1

Hash tables are implemented using buckets that contain linked lists. So iterating is easy:

1. See if the current node has a next pointer. If so, go to that.
2. If the current node has no next pointer, go to the next bucket that has a node.
3. If there is no such node, then you're done iterating.

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

Intuitively, since iterating through the whole hash table using the above algorithm is O(n), it would appear that each "next" operation is amortised constant time.