GreatRevan's blog

Is normal set faster than unordered_set??
By GreatRevan, history, 12 months ago, In English

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

  • Vote: I like it
  • -4
  • Vote: I do not like it

»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

It’s due to hash attacks. You can mitigate this by using a custom hasher.

→ Reply
»
12 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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 .

→ Reply
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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.

→ Reply