bucky21's blog

[CPP] Unordered Maps working slower than Ordered Maps
By bucky21, history, 4 years ago, In English

Hi All

I have been implementing the solution to the following problem. I first tried using Unordered Maps but the solution gave a TLE, however, when I submitted the same code using Ordered Maps, it got Accepted.

Problem Link: https://codeforces.net/contest/1234/problem/B2

Solution using Unordered Maps: https://codeforces.net/contest/1234/submission/104445196

Solution using Ordered Maps: https://codeforces.net/contest/1234/submission/104445219

The same problem was observed in the following question as well:

Problem Link: https://codeforces.net/contest/808/problem/D

Solution using Unordered Maps: https://codeforces.net/contest/808/submission/101908196

Solution using Ordered Maps: https://codeforces.net/contest/808/submission/101848962

In most of the theory, I went through, regarding Maps in CPP, it states that ordered maps are mostly slower than unordered maps as the lookup in unordered maps is O(1).

Does anyone have any clue as to what might be the coding error leading to such a deviation. Any help will be appreciated!

Thanks in advance!

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

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

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

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

Lookup is not necessarily O(1) in unordered map. Read This

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

Why make such blog? If you want to use a DS, first read up on it. Search for articles on CF, other places as well. In this case, read neal's blog on unordered_map. https://codeforces.net/blog/entry/62393. Copy the implementation at the bottom slap it in there. Understand how to use it. Understand why unordered_map can be so slow. Understand how to use the custom hash.

→ Reply