I'm just in a funny mood. Don't take this post too seriously.
These are all of the problems I've solved using unordered_map. This should be a complete list. For context, I've solved maybe around 4000 problems in total?
- 1120C - Compress String
- Logistics from Estonian Open 2016
I think neither solution is intended. The moral of the story: this class (and unordered_set) are very rarely if ever necessary in competitive programming. Yes, in theory they can do in $$$O(1)$$$ what map does in $$$O(\log n)$$$. In practice, they have a pretty large constant and are maybe only marginally faster than map. And that's not to mention all the times you can get hacked on it.
most people gravitate towards them essentially because they have been "sold" this idea of having constant lookup time which is neither guarantee-able nor safe from poor performance. funnily enough, the logarithmic retrieval complexity that they despise so much isn't even a bottleneck in most cases, is much safer compared to getting unnecessary time limit exceeded verdicts because you didn't write a custom hash lol. but hey, to each their own.
Moreover, in cases where it is a bottleneck,
unordered_mapusually doesn't help. This list would be 10 or so problems longer if I included problems where I tried that.I remember atleast 2 problems where i tried umap and then replaced by a vector with binary search (granted this cant be done for all problems)
The vector and binary search variant was 2 — 3x faster atleast (maybe more, i have forgotten)
also, there's one more issue (a gcc implementation issue to be precise) with unordered_map which i personally didn't know about until recently. it can be found here
This one here is one of the problems where using map leads to a time limit exceeded in tc 6 But unordered_map with a custom hash works
287988574
I don't see why either of them is necessary. Of course this list would be much longer if I replaced all arrays in my submissions with
unordered_maps.But the conventional wisdom is: when in doubt, just use a hashmap.
I've only ever heard this in the context of interview prep, not cp lol
Is gp hash table safe every time we want O(1)?
the general rule is that whenever you see "every time", the answer is probably no. moreover, you might want to refer to this to dig more about pbds (the "a better hash function" section might be helpful).
I think you meant: Yes, in theory they can do in O(n) what map does in O(logn).
Awesome :)
When I read the title (and your handle), I was expecting to see nothing but empty list in this post
I am surprised. I completely agree that it is not common to see unordered map being helpful but I am sure I had much more than 2 such occasions. "Create one large unordered map and reserve it with a big number at the beginning of the solution" is a relatively common idea that I'd say I use around once a year.
It is absolutely possible to write a completely safe O(1) hash table, see https://en.wikipedia.org/wiki/Universal_hashing and with also rehashes that detect if too many collisions are present. It is mathematically sound assuming source of randomness is proper, and even not it is almost impossible to make a hack case that simultaneously break two hashes. The issue is it will degrade into the time advantage against map/set even more. Therefore, for all practical purposes unordered_map should be regarded as O(log n) practically.
Worth mentioning that there are many cases radix sort (which sorts equal value together) may be sufficient.