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).
to be more serious, I never really understood when people described hash table insert as O(1). Like big-O is worst case whereas hash table insert is average/expected to be constant
Actually big-O is just a notation to describe the grow rate of functions, and that's it. There is no restriction say big-O should only describe function of complexity in worst case and it's nothing weird to use it to describe function of complexity in average case, and you can plug any function you want into it.
wiki
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.
funny
+this
(
unordered_set, though)I needed to use in this problem 1439B - Graph Subset Problem and it still the only one for me. Upd: unordered_set
I can't say I found this too funny, but you are one of the chillest high-rated people here so I have given you an updoot.