burakcetin's blog

Why std::map accessing is slower then count?
By burakcetin, 9 years ago, In English

525E - Anya and Cubes

On this problem before accessing an element in a map checking if the element is contained or not makes program faster. It doesnt make sense to me. Isnt both log(n) comp? Or is there an exception on accessing elements which are not in container?

TLE: 10498148

AC: 10498342

I only changed that part between these.

Also can someone tell how to use unordered map or give a code using it? Or any type of hashmap implementation i can use in c++.

UPD: It looks like when you use [] operator you create a node so tree size grows each time. Thanks for help everybody.

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

»
9 years ago, # |
  Vote: I like it +9 Vote: I do not like it

It happens because operator[] actually inserts element into map if it was not found. Therefore, your map grows during execution. You can clearly see this by looking at memory consumption.

Reasoning is very simple: otherwise you won't be able to write code like a[x] = b;. operator[] is unable to determine what you're gonna do with the result — just check or write something. So, it always returns reference to an element and, therefore, this element has to be created.

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

Operator [] inserts (key,0) into the map if the key wasn't there, so the size of the map grows and subsequent requests will take more time.

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

If you use m.find(val), then it only looks up whether val is contained in the existing tree. If you use m[val], then it first creates a new tree node, initializes it with a default value and then returns it to you. So naturally m[val] is more expensive both in time and space.

→ Reply