Блог пользователя dumbguy

C++ STL map vs unordered_map
Автор dumbguy, история, 7 лет назад, По-английски

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
.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

    → Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.

    → Ответить
»
7 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

Antihashmap test.

→ Ответить