alexashu's blog

map vs unordered_map
By alexashu, history, 4 years ago, In English

Yesterday , I gave contest round 702 div3 .

Problem F

Solution 1(https://codeforces.net/contest/1490/submission/107661957)

Solution 2(https://codeforces.net/contest/1490/submission/107661859)

In Solution1 I used unordered_map which gave me tle and than i used map in solution 2 it didn't.

Can anyone explain how does unordered_map gave tle and map won't?

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

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

Exactly same thing happened with me too, It was my myth that unordered_map is always faster than map . See this comment and blog u will understand. Comment Blog

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

In most of the cases unordered_map is faster, but not always. map is implemented using red black tree but unordered_map is implemented using list.Here is the catch what if all the values lies in a single list,then it will take O(n)instead of O(1) but map always take O(logn).For more detail you can refer documentation. :)

→ Reply