Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

When should I use a std::unordered_map instead of std::map?

Revision en1, by lucius_fox, 2023-12-05 09:31:28

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.

Tags help, maps, map vs unordered_map, hashing, query

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English lucius_fox 2023-12-05 09:31:28 1275 Initial revision (published)