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.

CodePudding user response：

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.

CodePudding user response：

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.

CodePudding user response：

My opinion is that you should change question in:

when std::map must be used instead of std::unordered_map?

Indeed, insertion, deletion, search of std::unordered_map are less complex than std::map. The table of this question resumes the complexity for each operation.

So, using std::map is recommended in two cases at least:

1. When you need ordering
2. std::unordered_map are hash-based. When you have too many collisions and you can't find a suitable hash function, you may go for a std::map.

However, in normal conditions, for a single element operation, I recommend std::unordered_map.