How to choose between map and unordered_map?
c++, data-structures, dictionary, stl, unordered-map
Solution
In practice, if memory is no issue, `unordered_map` is always faster if you want single element access.
The worst case is theoretical and bound to a single hash accounting for all of the elements. This is not of practical relevance. The `unordered_map` gets slower as soon as you have at least log N elements belonging to the same hash. This is also not of practical relevance. In some special scenarios you could use a specific hashing algorithm that ensures a more uniform distribution. For ordinary strings that don't share a specific pattern, the generic hash functions coming with `unordered_map` are just as good.
If you want to traverse the map (using iterators) in a sorted fashion, you cannot use `unordered_map`. On the contrary, `map` not only allows that, but also can provide you with the next element in a map based on an approximation of the key (see `lower_bound` and `upper_bound` methods).
Problem
Suppose I wanted to map data with a string as the key. What container should I have chosen, `map` or `unordered_map`? `unordered_map` takes up more memory so let's suppose memory isn't an issue, and the concern is speed. `unordered_map` should generally give average complexity of O(1) with the worst case of O(n). In what cases would it get to O(n)? When does a `map` get more time efficient than `unordered_map`? Does it happen when n is small? Assuming I would use STL `unordered_map` with the default haser Vs. map. string is the key. If I'm going to iterate over the elements rather than access an individual element each time, should I prefer `map`?