Choosing between std::map and std::unordered_map

Question

Now that std has a real hash map in unordered_map, why (or when) would I still want to use the good old map over unordered_map on systems where it actually exists? Are there any obvious situations that I cannot immediately see?

Answer 1

As already mentioned, map allows to iterate over the elements in a sorted way, but unordered_map does not. This is very important in many situations, for example displaying a collection (e.g. address book). This also manifests in other indirect ways like: (1) Start iterating from the iterator returned by find(), or (2) existence of member functions like lower_bound().

Also, I think there is some difference in the worst case search complexity.

• For map, it is O( lg N )

• For unordered_map, it is O( N ) [This may happen when the hash function is not good leading to too many hash collisions.]

The same is applicable for worst case deletion complexity.

Answer 2

In addition to the answers above you should also note that just because unordered_map is constant speed (O(1)) doesn't mean that it's faster than map (of order log(N)). The constant may be bigger than log(N) especially since N is limited by 2³² (or 2⁶⁴).

So in addition to the other answers (map maintains order and hash functions may be difficult) it may be that map is more performant.

For example in a program I ran for a blog post I saw that for VS10 std::unordered_map was slower than std::map (although boost::unordered_map was faster than both).

Note 3rd through 5th bars.

Answer 3

_{Partly based on Chandler Carruth's CppCon 2014 talk.}

std::map is (considered by many to be) not useful for performance-oriented work:

• If you want O(1)-amortized access, use a proper hash-map (which will probably use open addressing).
• If you want O(1)-amortized access but can't be bothered to get a decent implementation of anything at least use std::unorderded_map rather than std::map.
• If you want sorted sequential access into your map (which you typically don't), use something based on a vector.

Also, std::map is a balanced tree; and you have to traverse it, or re-balance it, incredibly often. These are cache-killer and cache-apocalypse operations respectively... so just say NO to std::map.

You might be interested in this SO question on efficient hash map implementations.

(PS - std::unordered_map is cache-unfriendly because it uses linked lists as buckets.)

Answer 4

I think it's obvious that you'd use the std::map you need to iterate across items in the map in sorted order.

You might also use it when you'd prefer to write a comparison operator (which is intuitive) instead of a hash function (which is generally very unintuitive).

Answer 5

Say you have very large keys, perhaps large strings. To create a hash value for a large string you need to go through the whole string from beginning to end. It will take at least linear time to the length of the key. However, when you only search a binary tree using the > operator of the key each string comparison can return when the first mismatch is found. This is typically very early for large strings.

This reasoning can be applied to the find function of std::unordered_map and std::map. If the nature of the key is such that it takes longer to produce a hash (in the case of std::unordered_map) than it takes to find the location of an element using binary search (in the case of std::map), it should be faster to lookup a key in the std::map. It's quite easy to think of scenarios where this would be the case, but they would be quite rare in practice i believe.