insert vs emplace vs operator[] in c++ map

Question

I'm using maps for the first time and I realized that there are many ways to insert an element. You can use emplace(), operator[] or insert(), plus variants like using value_type or make_pair. While there is a lot of information about all of them and questions about particular cases, I still can't understand the big picture. So, my two questions are:

1. What is the advantage of each one of them over the others?

2. Was there any need for adding emplace to the standard? Is there anything that wasn't possible before without it?

Answer 1

In the particular case of a map the old options were only two: operator[] and insert (different flavors of insert). So I will start explaining those.

The operator[] is a find-or-add operator. It will try to find an element with the given key inside the map, and if it exists it will return a reference to the stored value. If it does not, it will create a new element inserted in place with default initialization and return a reference to it.

The insert function (in the single element flavor) takes a value_type (std::pair<const Key,Value>), it uses the key (first member) and tries to insert it. Because std::map does not allow for duplicates if there is an existing element it will not insert anything.

The first difference between the two is that operator[] needs to be able to construct a default initialized value, and it is thus unusable for value types that cannot be default initialized. The second difference between the two is what happens when there is already an element with the given key. The insert function will not modify the state of the map, but instead return an iterator to the element (and a false indicating that it was not inserted).

// assume m is std::map<int,int> already has an element with key 5 and value 0
m[5] = 10;                      // postcondition: m[5] == 10
m.insert(std::make_pair(5,15)); // m[5] is still 10

In the case of insert the argument is an object of value_type, which can be created in different ways. You can directly construct it with the appropriate type or pass any object from which the value_type can be constructed, which is where std::make_pair comes into play, as it allows for simple creation of std::pair objects, although it is probably not what you want...

The net effect of the following calls is similar:

K t; V u;
std::map<K,V> m;           // std::map<K,V>::value_type is std::pair<const K,V>

m.insert( std::pair<const K,V>(t,u) );      // 1
m.insert( std::map<K,V>::value_type(t,u) ); // 2
m.insert( std::make_pair(t,u) );            // 3

But the are not really the same... [1] and [2] are actually equivalent. In both cases the code creates a temporary object of the same type (std::pair<const K,V>) and passes it to the insert function. The insert function will create the appropriate node in the binary search tree and then copy the value_type part from the argument to the node. The advantage of using value_type is that, well, value_type always matches value_type, you cannot mistype the type of the std::pair arguments!

The difference is in [3]. The function std::make_pair is a template function that will create a std::pair. The signature is:

template <typename T, typename U>
std::pair<T,U> make_pair(T const & t, U const & u );

I have intentionally not provided the template arguments to std::make_pair, as that is the common usage. And the implication is that the template arguments are deduced from the call, in this case to be T==K,U==V, so the call to std::make_pair will return a std::pair<K,V> (note the missing const). The signature requires value_type that is close but not the same as the returned value from the call to std::make_pair. Because it is close enough it will create a temporary of the correct type and copy initialize it. That will in turn be copied to the node, creating a total of two copies.

This can be fixed by providing the template arguments:

m.insert( std::make_pair<const K,V>(t,u) );  // 4

But that is still error prone in the same way that explicitly typing the type in case [1].

Up to this point, we have different ways of calling insert that require the creation of the value_type externally and the copy of that object into the container. Alternatively you can use operator[] if the type is default constructible and assignable (intentionally focusing only in m[k]=v), and it requires the default initialization of one object and the copy of the value into that object.

In C++11, with variadic templates and perfect forwarding there is a new way of adding elements into a container by means of emplacing (creating in place). The emplace functions in the different containers do basically the same thing: instead of getting a source from which to copy into the container, the function takes the parameters that will be forwarded to the constructor of the object stored in the container.

m.emplace(t,u);               // 5

In [5], the std::pair<const K, V> is not created and passed to emplace, but rather references to the t and u object are passed to emplace that forwards them to the constructor of the value_type subobject inside the data structure. In this case no copies of the std::pair<const K,V> are done at all, which is the advantage of emplace over the C++03 alternatives. As in the case of insert it will not override the value in the map.

---

An interesting question that I had not thought about is how emplace can actually be implemented for a map, and that is not a simple problem in the general case.