I have been solving Stone Age Problem and something caught my attention, what is the real complexity for map.clear and unordered_map.clear
The same code using map.clear passes but unorder_map.clear however cppreference says both are linear, so what is the real complexity.
UPD1: I have proved that isn't related with collision because I haven tested initiating a new one instead of cleaning and it passes. AC
I think its not because of clear() method but since unordered_maps are made using hash maps there might be some cases which maximizes collision that's why you got TLE
Not sure it is related with collision, I have tested using the custom_hash as suggested on this blog and doesn't work neither.
PD, the keys are between [1, N] N <= 2e5 which doesn't looks to fall into collision easily.
IIRC, unordered works in 0(number of elements+ number of buckets) in the implementation I checked.so if you have a lot of buckets (due to reserving or the fact that you had a lot of elements at some point) itll take long
what is buckets?
Auto comment: topic has been updated by Snow (previous revision, new revision, compare).
I noticed the same thing on the same problem.
It seems that in competitive programming
mapis always a better choice thanunordered_map. According to this discussion on stackoverflow,unordered_map.clear()might do quite a lot on all "buckets". Alsomapoffers a stableO(log N)complexity so you never need to worry about hash collisions (as you proved this problem is not related to collisions but other problems might be).Or you can always do
m = unordered_map<int, int>();(but you still cannot get rid of collisions).I think custom_hash of Neal makes every solution unhackable unless you are using clear() function non-carefully,I faced similar problem; here is the fact behind this : Unordered_Map is unhackable if clear() is used technically Snow