11

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
  • 690
  • 2
  • 12
  • 27
  • 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. – Chris Jester-Young Aug 08 '14 at 02:38
  • @sam Thanks for your link! – eaglesky Aug 08 '14 at 08:06

1 Answers1

14

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.

Chris Jester-Young
  • 213,251
  • 44
  • 377
  • 423
  • 1
    This is the answer I am looking for. Thank you! – eaglesky Aug 08 '14 at 08:06
  • 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