13

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.

eaglesky
  • 730
  • 2
  • 13
  • 28
  • This post (http://stackoverflow.com/questions/19610457/c-stdunordered-map-complexity?rq=1) says any standard container must provide O(1) iterators. (I suggest removing this question unless it's actually different than the linked one). – Sam Aug 08 '14 at 02:36
  • Pulled this from one of the comments, "Section 24.4.4 of the C++ Standard," gives requirements for the ++ operator on forward iterators. Good question. I enjoyed this trip. :) – Sam Aug 08 '14 at 02:37
  • @sam If it's a "good" question, then there's no reason to remove it! Flag as duplicate, if applicable. – C. K. Young Aug 08 '14 at 02:38

1 Answers1

16

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.

C. K. Young
  • 219,335
  • 46
  • 382
  • 435
  • 9
    It isn't exactly O(n), rather it is O(N+n), where N is the number of buckets. This is because each bucket needs to be visited at least once even if it had no elements. These are typically a constant factor away from each other, which is why this is fine. – EyasSH Oct 31 '14 at 16:04