std::*map as fast as possible

The views presented here are solely based author’s personal opinion, research, observations and are in no way affiliated to any organization.

std::map offers an associative container that stores unique key-value pairs sorted by keys. It is implemented using red-black trees and offers O(log n) time complexity for insertion, deletion, and find. For data that need not have any particular ordering, std::unordered_map can provide O(1) amortized complexity for insertion, deletion, and find.

Map containers are widely used in code, but a few important details in map insertion are often overlooked which adds an unnecessary performance penalty.

Consider a typicalstd::unordered_map usage:

std::unordered_map<K, V> my_map;

Now to insert in this map, one may use insert function provided by std::unordered_map as:

my_map.insert(std::make_pair(key,
                            V(arg1, arg2)));

Here, many unnecessary temporary copies are being created. One of the least suspecting copies may be due to conversion of outer std::make_pair. insert function expects std::pair<const Key, Value>, so unless key object is const, there would be an additional implicit conversion (and hence the copy).

More experienced C++ developers will immediately suggest using emplace instead of insert, to leverage perfect forwarding. Using emplace , removes outer std::make_pair.

my_map.emplace(key, V(arg1, arg2));

Interestingly, if V does not have a copy (or move) constructor, the above line won't even compile. Contrast this with typical usage of std::vector.

std::vector<V> vals;
vals.emplace_back(arg1, arg2);

In a std::vector<V>, we are able to construct V in-place using emplace_back function call. So the question is, how to do it in a std::map?

Let’s look at the definition of map:

template<
    class Key,
    class T,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<std::pair<const Key, T> >
>
class map;

and the definition emplace call:

template< class... Args >
std::pair<iterator,bool> emplace( Args&&... args );

It’s clear that emplace just forwards the arguments. So we actually want to construct the Value in the map in-place. Recall that std::map stores items as std::pair. Looking at the constructor of std::pair, we find:

template< class... Args1, class... Args2 >
pair( std::piecewise_construct_t,
      std::tuple<Args1...> first_args,
      std::tuple<Args2...> second_args );

std::piecewise_construct_t is the trick to constructing the items of pair in-place. With this, we can do emplace in std::map, without creating any temporary copies as follows:

my_map.emplace(std::piecewise_construct_t,
               std::forward_as_tuple(key),
               std::forward_as_tuple(arg1, arg2));

std::forward_as_tuple will bind the template arguments to key and value types as necessary to construct them individually in-place.

Interesting read:

1. N4387 — Improving pair and tuple