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.
The most important difference between a regular
std::map
andstd::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)$$$ forinsert
, lookup (map[key]
), anderase
while unordered maps, implemented as hash tables, take (amortised) $$$O(1)$$$ to do the above operations.However, regular
std::map
(andstd::set
, for that matter) provide the methodslower_bound
andupper_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 anunordered_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.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).