Unordered_Map Lookup Time

Question

The built in maps and sets in C++ libraries (including unordered_map and multimap) requires that the find function (used to lookup a specific element) utilize an iterator for traversing the elements. The C++ reference site claims that looking up elements using these data structures takes on average constant time, much like a regular hash table. But wouldn't an iterator have to traverse the entire list, making this O(n) time on average, before finding the element?

Answer 1

You statement are no true:

• map, set, multimap and multiset are normally implemented as binary trees (ex: in VS are implemented as Red Black Trees), the find method in this case search the key using the property that in one node the left child is less than the node (according to the comparer) and the right child is greater than the node (according to the comparer). This give O(log n), as required by the standard.
• In the case of unordered_map and unordered_set are implemented as hash tables, normally implemented as a collection of buckets (ex: std::vector<Bucket>) and the bucket is implemented as a collection of elements of the unordered_map (ex: std::vector<elem> or std::list<elem>), assuming that hashing function is constant time (or excluding the time), the search in this collections is in average constant time O(1) (the hashing give the bucket where the element are placed, if there are few elem in the bucket search between then the target elem). The worst case is when all elements are in the same bucket in this case the search of the target element would need to iterate through all elements in the bucket until found or not (in O(n)). With good hashing function you could increase probability of split evenly enough the elem in the bucket (obtaining the expected constant time).

Note: the find function return a iterator that don't mean that use iterator to search the requested element.