-4

What is the difference between unordered_map and map of C++ STL. Please explain in terms of complexity and use.

I replace map with unordered_map and I got accepted while earlier i was getting Time limit Exceeded.

And where should we use map and where unordered map

Shivam Duggal
  • 317
  • 2
  • 10

1 Answers1

0

std::map has guaranteed O(log N) complexity for search, insertion and deletion. It uses a comparison operator, and iteration happens in the order defined by that comparison operator.

std::unordered_map only guarantees O(N) complexity for search, insertion and deletion, but you normally expect it to be O(M), where M is (more or less) the size of an individual key. Assuming keys are small relative to the number of items, it's basically O(1).

Jerry Coffin
  • 476,176
  • 80
  • 629
  • 1,111
  • If you consider size of key in std::unordered_map then you should also do that in std::map. The complexity is O(logN * M) where M is (more or less) the complexity for each comparison. – Kan Li Jun 15 '15 at 20:25
  • @icando: yes and no--at least in a typical case, with a map, you can stop a comparison at the first mismatch between two keys, whereas with an unordered map, your hash has to take the entire key into account every time. From a purist viewpoint, they're both O(M), but more practically, the difference can be quite substantial. – Jerry Coffin Jun 15 '15 at 20:27