zarif_2002's blog

unordered map vs map
By zarif_2002, history, 6 years ago, In English

https://mirror.codeforces.com/contest/808/problem/D

unordered_map took me to tle but map took me to ac.

unordered_map submission https://mirror.codeforces.com/contest/808/submission/48371065

map submission https://mirror.codeforces.com/contest/808/submission/48371396

but we know generally unordered_map works in O(1) time where map works in O(log n) time. so, why this occurs. please.

  • Vote: I like it
  • -6
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://mirror.codeforces.com/blog/entry/62393

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    Generally, if one already know the hash function(like the one in unordered_map) you use in your code, then one could make mean data to blow it up(if your hash function is not safe enough), while map(RBTree) is stable.

    → Reply