4

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.

John
  • 2,963
  • 11
  • 33
  • Why would you want to replace an unordered map with a map, if the order does not matter? – ChrisMM Jan 06 '22 at 02:37
  • Well, (a) fewer data structures to learn, (b) stable results in unit tests, (c) shorter to type... – Jiří Baum Jan 06 '22 at 02:47
  • 1
    @JiříBaum "stable results in unit tests".Could you please explain that in more detail for me? – John Jan 06 '22 at 02:56
  • If a function uses `unordered_map` to (for example) return a list of items, that list will be in arbitrary order, so the unit tests will have to check for it more carefully than if the same function used `map`, which would return the list in a fixed order – Jiří Baum Jan 06 '22 at 06:01
  • None of those three reasons are really big, just minor things that might tempt one to just pick one and always use it – Jiří Baum Jan 06 '22 at 06:03
  • 1
    @JiříBaum "If a function uses unordered_map to (for example) return a list of items, **that list will be in arbitrary**". I am a little confused indeed. ***Since the hash function is fixed***, I think **the list should be in unique oder** except the hash function has some relation with time.Could you please explain that in layman's term? – John Jan 06 '22 at 06:20
  • 1
    Ah, you're right; I'm used to hash maps with random salt (to help defend against DoS attacks). Sorry about that! Unsalted hash maps will indeed be arbitrary but fixed, so won't be a problem for unit tests. – Jiří Baum Jan 06 '22 at 06:30

3 Answers3

10

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.

user17732522
  • 53,019
  • 2
  • 56
  • 105
5

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.

eerorika
  • 232,697
  • 12
  • 197
  • 326
2

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.

MM92x
  • 548
  • 1
  • 4
  • 25
  • 1
    As per the aforementioned link, which says that the element ordering for `map` is `strict weak`. I think it's wrong. The element ordering for `map` is `strict` other than `strict weak`.How do you think about it? – John Jan 06 '22 at 02:49
  • "for a single element operation, I recommend std::unordered_map."What's "single element operation"? Could you please explain that in more detail for me? – John Jan 06 '22 at 02:51
  • About "single element access" I suggest yout to read the comments on `ypnos` answer here: https://stackoverflow.com/questions/13799593/how-to-choose-between-map-and-unordered-map/13799886#13799886 (comments do examples of timing critical applications for which, in some cases, `std::map` can be preferred. The discussion shall answer to your second question as well, and it is very interesting! – MM92x Jan 06 '22 at 02:59
  • Your question on the `strict weak` concept is very interesting. By doing some researches, I noticed that `std::map` must comply with `Compare` concept which requires `strict weak` ordering. Source: https://en.cppreference.com/w/cpp/named_req/Compare – MM92x Jan 06 '22 at 03:11
  • I see, thank you for your detailed explanation. My understanding of such matter is at a different level with your help. – John Jan 06 '22 at 06:12
  • Thanks to you too, I did learn too :) – MM92x Jan 06 '22 at 06:45