Snow's blog

What is the complexity for map.clear and unordered_map.clear
By Snow, history, 3 years ago, In English

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

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Snow (previous revision, new revision, compare).

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I noticed the same thing on the same problem.

It seems that in competitive programming map is always a better choice than unordered_map. According to this discussion on stackoverflow, unordered_map.clear() might do quite a lot on all "buckets". Also map offers a stable O(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).

→ Reply