Choosing between std::map and std::unordered_map

c++ c++11 hash map unordered-map
Johann Gerell picture Johann Gerell · Oct 11, 2010 · Viewed 89.3k times · Source

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

Arun picture Arun · Oct 11, 2010

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.

Related questions

What is the default hash function used in C++ std::unordered_map?

I am using unordered_map<string, int> and unordered_map<int, int> What hash function is used in each case and what is chance of collision in each case? I will be inserting unique string and …

Read More
How to specialize std::hash<Key>::operator() for user-defined type in unordered containers?

To support user-defined key types in std::unordered_set<Key> and std::unordered_map<Key, Value> one has to provide operator==(Key, Key) and a hash functor: struct X { int id; /* ... */ }; bool operator==(X a, X …

Read More
Compile time string hashing

I have read in few different places that using C++11's new string literals it might be possible to compute a string's hash at compile time. However, no one seems to be ready to come out and say that it …

Read More