7

Unordered_map vs map, which one should I use when?

 2 years ago
source link: http://codeforces.com/blog/entry/104332
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Unordered_map vs map, which one should I use when?

Hey all, I know that this is a very common topic and you are probably quite turned off by it but i still don't quite understand it. Please take the time to read through this post. Thanks a lot!

During the contest yesterday, I was solving 3SUM — closure: https://codeforces.com/contest/1698/problem/C I figured out the logic to the question and started implementing it. I used unordered_map — passed the pretests — but then TLE'd on the main tests. This was my submission: https://codeforces.com/contest/1698/submission/162250574

But then, i made some changes to this code and got AC. This was my next submission: https://codeforces.com/contest/1698/submission/162252261

Notice the difference between these two pieces of code? Yes! I used a map instead of unordered_map. Now, I have read many threads and articles advising to use maps instead of unordered_maps in my life, for all sorts of reasons, like slow hash functions, frequent collisions which cause the use of buckets which slow the unordered_map down, etc. But in this case, the only thing I'm doing is inserting and using the unordered_map::count function. are these not examples of where the unordered_map's O(1) time complexity should beat the map's O(logN)? Unlike, for example, iterating through the map, in which case, using a map instead of unordered_map would be faster? I was specifically asking myself this question during the contest and because of the fact that this was the only thing I was doing, I chose to use unordered_map — which turned out to stab me in the back and lose me quite a bit of rating. Basically, my question is, during competitive programming, is there EVER a time in which I would want to use unordered_map instead of map?


About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK