map vs unordered_map for few elements

Question

I am trying to choose between map and unordered_map for the following use case:

The key of the map is a pointer. The most common use case is that there will be a single element in the map. In general, the max number of elements in the map less than 10. The map is accessed very often and speed is the most important factor. Changes to the map are infrequent.

While measuring the speed is obviously the correct approach here, this code will be used on several platforms so I'm trying to create a general rule of thumb for choosing between a map and unordered_map based on number of elements. I've seen some posts here that hint that std::map may be faster for a small number elements, but no definition of "small" was given.

Is there a rule of thumb for when to choose between a map and unordered_map based on number of elements? Is another data structure (such as linear search through a vector) even better?

Answer 1

Under the premise that you always need to measure in order to figure out what's more appropriate in terms of performance, if all these things are true:

1. Changes to the map are not frequent;
2. The map contains a maximum of 10 elements;
3. Lookups will be frequent;
4. You care a lot about performance;

Then I would say you would be better off putting your elements in an std::vector and performing a plain iteration over all your elements to find the one you're looking for.

An std::vector will allocate its elements in a contiguous region of memory, so cache locality is likely to grant you a greater performance - the time required to fetch a cache line from main memory after a cache miss is at least one order of magnitude higher than the time required to access the CPU cache.

Quite interestingly, it seems like Boost's flat_map is ideal for your use case (courtesy of Praetorian):

flat_map is similar to std::map but it's implemented like an ordered vector. (from the online documentation)

So if using Boost is an option for you, you may want to try this one.

Answer 2

I believe for your case of 10 elements or less and usually only one a linear search of an unsorted vector will work best. However, depending on the hash algorithm used the unordered_map may be faster instead.

It should be easy enough for you to benchmark.