dumbguy's blog

C++ STL map vs unordered_map
By dumbguy, history, 7 years ago, In English

Hello guys,
Since a long time i was under the impression that STL unordered_map is faster due to its non ordering than STL map.
But in a problem when i submitted the solution using unordered_map i got TLE but with map i got AC.
Can anyone please provide an insight into this because i am not able to understand why this happened for this particular solution.

For reference, this is the solution using unordered_map : 33578534 and this one using map : 33578782.
This is the actual problem 776C - Molly's Chemicals
.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
7 years ago, # |
  Vote: I like it -13 Vote: I do not like it

This can be explained by a single fact that Unordered_map is implemented using a hash table. In which a hash key is generated for the input and it is stored at the key location. Whereas in case of Ordered Map or map it is stored in a tree.

So whenever same values are stored in an unordered_map then there will be a link list at the key. And it will take O(n) time to access a link list. Whereas in ordered_map it will always take O(log n) time.

So, it is advisable to use unordered_map in case of unique elements only.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Correct me if i am wrong but in this problem, the value of the corresponding key is being updated(adding) and not appending so i guess there is nothing like linked list in this case.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I thought by definition map and unordered map only store unique elements and you have to use multimap and unordered multimap to deal with non-unique elements.

    → Reply
»
7 years ago, # |
  Vote: I like it +30 Vote: I do not like it

Antihashmap test.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I didn't get you dalex ... Can you please elaborate?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Hashmap works in O(n) per query in worst case. This test is the worst case.

      → Reply