title: Unordered_Map Lookup Time
body: <p>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? </p>