Search code examples
c++stlunordered-mapstdmap

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

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.

Solution

  • 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.