I thought unordered_set was faster because it doesn't need to deal with sorting.
I got accepted for problem C on a recent Div.3 contest, but it returned as TLE on test 17 after contest finished and I lost 52 points. You know what's funny? When you replace unordered_set with normal set, it gives accepted (sorting ability of normal set doesn't help you for this problem)
Code with unordered_set (TLE on test 17): https://mirror.codeforces.com/contest/2106/submission/317003071
Same code with normal set (Accepted): https://mirror.codeforces.com/contest/2106/submission/317364054
It’s due to hash attacks. You can mitigate this by using a custom hasher.
This problem happens so often that I just asked ChatGPT to sum it up, take a look at this chat:
https://chatgpt.com/share/680d1664-4814-8011-9b58-aaa807bea445
I guess I should just use set to prevent those hashing problems, even though unordered_set is meant to be faster
I recommend using gp hash table with the splitmix64 hash, it functions the same as unordered_set but it is faster in edge cases because of it's O(logn) time complexity compared to the unordered_set O(n)
Can you drop an example code please?
https://mirror.codeforces.com/contest/2097/submission/317465961
But some unordered_set functions aren't avialble so just normal unordered_set<int, SplitMix64> st; would also be fine with ~ same speed
But what is the point of using unordered_set with $$$O(log(n))$$$ time complexity, why not just using normal set?
Thank you so much! I don't think I'm on this level rn but yeah, it helps
Yes'nt. In theory, unordered set's operations are much faster than set(1 vs logn). Butt, due to collision, sometimes unordered_set operation can take up to O(n). Check this blog
In some cases if hashing is bad(hash collisions) , then the time complexity of later one increases . It happens in worst cases only , overall unordered_set is better than set .
unordered_set meant to be faster than normal set in normal cases, but in worst case all elements goes into the same bucket due to hash collisions which leads to O(n) per operation.
Avoid using unordered_set or unordered_map as much as you can for not getting TLE.