[CPP] Unordered Maps working slower than Ordered Maps

Revision en2, by bucky21, 2021-01-17 15:59:55

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.me/contest/1234/problem/B2

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

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

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

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

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

Solution using Ordered Maps: https://codeforces.me/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!

Tags cpp, maps, map vs unordered_map

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English bucky21 2021-01-17 15:59:55 10
en1 English bucky21 2021-01-17 15:58:50 1131 Initial revision (published)