Map vs unordered_map performance

I heard an opinion recently that by default we should be using unordered_map instead of map. It improves speed at the expense of the memory, but generally we don't care much about memory nowadays, unless we're storing a really huge number of elements. But, if we're not storing a large number of elements, doesn't the constant matter more? Where's the balance?

I measured the performance of std::map and std::unordered_map to see how much the constant matters. Of course this will depend on your particular implementation of standard library. When measuring the results below I was using libstdc++6 8.2.1 and g++ 8.2.1.

I filled the maps with std::strings for keys and values. Lengths of keys were between 15 and 20 characters, lengths of values were about 10 characters longer. I then tested two things: how long does it take to lookup a value that doesn't exist in the map, and then how long does it take to add a new value and then remove it. 


// lookup
selectedmap["Nonexistent"];

// insert + delete
selectedmap["NonexistentKey"] = "Nonexistent";
selectedmap.erase("NonexistentKey");

I was surprised to learn that std::unordered_map already becomes faster than std::map when they have just 4 stored elements! The y-axis is milliseconds, x-axis is size of maps:

std::map vs std::unordered_map

When I did similar experiment on Windows with Visual Studio 2017 and C++14 turned on, I got about 10 elements. When sizes of maps are this small, the element will be found fast enough even if std::map is faster. I guess std::unordered_map really should be the default. There is little to pay attention to but the memory limitation, which is not likely to be a problem, and how heavy the hash function is.


Previous: Notes from porting to std::string_view
Next: Concepts today