zeref_dragoneel's blog

Difference in answers in unordered_map and map
By zeref_dragoneel, history, 11 years ago, In English

http://mirror.codeforces.com/contest/512/problem/B

solution id : 12300691 and 12300696 http://mirror.codeforces.com/submissions/arbit

unordered_map is giving wrong answers while map gives the correct answer.

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

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

Looks like you use fact, that in map all pairs are sorted. It's true for normal map(because it's based on BST), but wrong for unordered_map(because it's based on hash table and keys are sorted not by value, but by hashs)

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

std::map and std::unordered_map have different iterator invalidation rules. Basically, any std::unordered_map iterator can be invalidated after any insertion or deletion because of rehashing, and you can't control it. On other hand, std::map iterator is guaranteed to be valid until you erase it explicitly. That's why you got 2 different results.

→ Reply