kshitij_coder's blog

Why does map work better than unordered_map?
By kshitij_coder, history, 4 years ago, In English

I was trying to solve the question B2 — Social Network (hard version). Question Link: https://mirror.codeforces.com/contest/1234/problem/B2

I first tried to code the solution using queue and unordered_map. But that gave me TLE. But when I used a map in place of unordered_map, the solution got accepted. Unordered_map does not keep the keys in a sorted format. Then why did an implementation using maps work better? Please guide me on this.

Thanks in advance!!

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

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

This is one of the most linked blogs to the issue.

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

Unordered map works in constant time(O(1)) on "Average" but has a worst-case complexity of O(n). Map always works in O(logn) time. I hope this explains you why got TLE in this. Tip: Always use map if the constraints allow!

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

Blowing up unordered_map, and how to stop getting hacked on it

Spoiler
→ Reply