Johann Gerell Johann Gerell - 6 months ago 42
C++ Question

Choosing between std::map and std::unordered_map

Now that

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


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.