i_anku's blog

Which is faster in cpp unordered_map or map
By i_anku, history, 2 years ago, In English

map is faster in cpp than unordered_map?

So today I was up solving Codeforces Round #790 (Div. 4) i got stuck in problem F bc i was using unordered_map and repetedly getting tle at 19th and 20th testcase i gave up and tried to look into solution i found out they were using map i tried it and it gets accepted instantaneously, then i wonder which map is faster, tried to look into some online resources but found oppsosite of it every online resource was say unordered_map is faster than map here is my submissions with map unordered_map someone plz help me in this i am really confused, i might get downvote for this but i just want to know the reason thank u

  • Vote: I like it
  • +14
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

read this

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

average case time complexity : unordered_map O(1) < map O(logn)

worst case time complexity : unordered_map O(n) > map O(logn)

unordered_map suffers with collision issue if test cases are made that way. please read their internal implementation for more details.

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

unordered_map is usually faster in general and takes O(1) time for most its commands, though, on some special calls it takes O(n) time, and it's possible to generate test cases so that unordered_map takes O(n) time everytime you use it, which testers mostly put in their tests. Check out this blog for deeper understanding and on how to bypass those testcases. https://mirror.codeforces.com/blog/entry/62393

→ Reply