lucius_fox's blog

When should I use a std::unordered_map instead of std::map?
By lucius_fox, history, 12 months ago, In English

I was trying to solve E.Collapsing Strings from the recent educational round. I used polynomial hashing to count the occurrences of each suffix of each string in the given list and store it in a map, then iterate over the prefixes of all the strings and then subtract 2*length_of_the_prefix*(the_count_of_this_prefix_in_the_map) from the initial count(assuming total length of every pairwise combination is added to the final count) to get the final answer.

For the purpose of keeping count of the frequencies of the hash I was using a map, which gave TLE. However after replacing map with unordered_map it was accepted.

This caused me think about which situations I should use an unordered_map instead of a regular map (ordered map). Is an unordered_map always inherently faster than a map? in which cases should I use it? I'm asking here because I couldn't get a satisfactory answer after searching the web. Please help.

P.S also if you could, please suggest how I could better implement my algorithm for the above problem if possible.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The most important difference between a regular std::map and std::unordered_map is that the former has its keys ordered while the latter does not. The former keeps its keys ordered even after updates (insertions and deletions) and therefore has a slower performance and time complexity: ordered maps, typically implemented using red–black trees, take $$$O(\log n)$$$ for insert, lookup (map[key]), and erase while unordered maps, implemented as hash tables, take (amortised) $$$O(1)$$$ to do the above operations.

However, regular std::map (and std::set, for that matter) provide the methods lower_bound and upper_bound, which return the least key not less/greater than the parameter respectively. These operations take $$$O(\log n)$$$ time and can be especially useful in binary search-type problems. To do the above operations with an unordered_map, one would need to traverse the entire map, resulting in $$$O(n)$$$ complexity.

As for the use cases of these containers, I would suggest using unordered_map most of the time, when the order of the key is unimportant. Use the ordered versions only when you want fast binary search together with the ability to insert/erase elements.

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

You can refer to this blog link. Use unordered_map and custom_hash. This may be faster than map and hard to hack (I am not sure because I do not know cpp well).

→ Reply