In practice, when `std::unordered_map` must be used instead of `std::map`?

Question

In practice, is there any circumstance which std::unordered_map must be used instead of std::map?

I know the differences between them, say internal implementation,time complexity for searching element and so on.

But I really can't find a circumstance where std::unordered_map could not be replaced by std::map indeed.

Answer 1

Yes, for example if the key type does not have a sensible strict weak ordering but does have sensible equality and is hashable.

A strict weak order is required for the key type on the ordered associative containers std::set and std::map.

Answer 2

I know the difference between them, say internal implementation,time complexity for searching element

In that case, you should know that that the average asymptotic element lookup time complexity of unordered map is constant, while the complexity of ordered map is logarithmic. This means that there is some size of container at which point the lookup will be faster when using unordered map.

But I really can't find a circumstance where std::unordered_map could not be replaced by std::map indeed.

If the container is large enough, and if you cannot afford the cost of ordered map lookup, then you cannot choose to replace the faster unordered map lookup.

Another case where ordered map cannot be used is where there doesn't exist a cheap function to compare relative order of the key.