insert vs emplace vs operator[] in c++ map
Solution 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.
Solution 2
Emplace: Takes advantage of the rvalue reference to use the actual objects that you have already created. This means that no copy or move constructor is called, good for LARGE objects! O(log(N)) time.
Insert: Has overloads for standard lvalue reference and rvalue reference, as well as iterators to lists of elements to insert, and "hints" as to the position an element belongs. The use of a "hint" iterator can bring the time insertion takes down to contant time, otherwise it is O(log(N)) time.
Operator[]: Checks to see if the object exists, and if it does, modifies the reference to this object, otherwise uses the provided key and value to call make_pair on the two objects, and then does the same work as the insert function. This is O(log(N)) time.
make_pair: Does little more than make a pair.
There was no "need" for adding emplace to the standard. In c++11 I believe the && type of reference was added. This removed the necessity for move semantics, and allowed optimization of some specific type of memory management. In particular, the rvalue reference. The overloaded insert(value_type &&) operator does not take advantage of the in_place semantics, and is therefore much less efficient. While it provides the capability of dealing with rvalue references, it ignores their key purpose, which is in place construction of objects.
Solution 3
The code below shows the "big picture idea" of how insert()
differs from emplace()
by tracking every constructor call and telling you info about them as they happen. The code is long but easy so here's a summary to get to the point faster. The summary and a quick look through the code should be enough understand it and its output.
Summary of code: main()
's code insert()
s and emplace()
s Foo
objects into an unordered_map<Foo,int>
with calls such as "umap.emplace(11, d);
" and "umap.insert({12, d})
". Every call is printed to cout
before it is executed. The Foo
class uses static int foo_counter
to keep track of the total number of Foo
objects that have been constructed (or moved, copied, etc.) thus far. Each Foo
object stores the (unique) value of foo_counter
at the time of its creation in its local variable val
, and the unique object with val
== 8
(for example) is called "foo8
" or "Foo
8". Every constructor/destructor call prints info about the call (e.g. calling Foo(11)
will output "Foo(int) with val: 11
"). Comparing this output to the code will make the difference between insert()
and emplace()
clear.
Code
#include <iostream>
#include <unordered_map>
#include <utility>
using namespace std;
//Foo simply outputs what constructor is called with what value.
struct Foo {
static int foo_counter; //Track how many Foo objects have been created.
int val; //This Foo object was the val-th Foo object to be created.
Foo() { val = foo_counter++;
cout << "Foo() with val: " << val << '\n';
}
Foo(int value) : val(value) { foo_counter++;
cout << "Foo(int) with val: " << val << '\n';
}
Foo(Foo& f2) { val = foo_counter++;
cout << "Foo(Foo &) with val: " << val
<< " \tcreated from: \t" << f2.val << '\n';
}
Foo(const Foo& f2) { val = foo_counter++;
cout << "Foo(const Foo &) with val: " << val
<< " \tcreated from: \t" << f2.val << '\n';
}
Foo(Foo&& f2) { val = foo_counter++;
cout << "Foo(Foo&&) moving: " << f2.val
<< " \tand changing it to:\t" << val << '\n';
}
~Foo() { cout << "~Foo() destroying: " << val << '\n'; }
Foo& operator=(const Foo& rhs) {
cout << "Foo& operator=(const Foo& rhs) with rhs.val: " << rhs.val
<< " \tcalled with lhs.val = \t" << val
<< " \tChanging lhs.val to: \t" << rhs.val << '\n';
val = rhs.val;
return *this;
}
bool operator==(const Foo &rhs) const { return val == rhs.val; }
bool operator<(const Foo &rhs) const { return val < rhs.val; }
};
int Foo::foo_counter = 0;
//Create a hash function for Foo in order to use Foo with unordered_map
template<> struct std::hash<Foo> {
size_t operator()(const Foo &f) const { return hash<int>{}(f.val); }
};
int main() {
unordered_map<Foo, int> umap;
int d; //Some int that will be umap's value. It is not important.
//Print the statement to be executed and then execute it.
cout << "\nFoo foo0, foo1, foo2, foo3;\n";
Foo foo0, foo1, foo2, foo3;
cout << "\numap.insert(pair<Foo, int>(foo0, d))\n";
umap.insert(pair<Foo, int>(foo0, d));
//Side note: equivalent to: umap.insert(make_pair(foo0, d));
cout << "\numap.insert(move(pair<Foo, int>(foo1, d)))\n";
umap.insert(move(pair<Foo, int>(foo1, d)));
//Side note: equiv. to: umap.insert(make_pair(foo1, d));
cout << "\npair<Foo, int> pair(foo2, d)\n";
pair<Foo, int> pair(foo2, d);
cout << "\numap.insert(pair)\n";
umap.insert(pair);
cout << "\numap.emplace(foo3, d)\n";
umap.emplace(foo3, d);
cout << "\numap.emplace(11, d)\n";
umap.emplace(11, d);
cout << "\numap.insert({12, d})\n";
umap.insert({12, d});
cout.flush();
}
Output
Foo foo0, foo1, foo2, foo3;
Foo() with val: 0
Foo() with val: 1
Foo() with val: 2
Foo() with val: 3
umap.insert(pair<Foo, int>(foo0, d))
Foo(Foo &) with val: 4 created from: 0
Foo(Foo&&) moving: 4 and changing it to: 5
~Foo() destroying: 4
umap.insert(move(pair<Foo, int>(foo1, d)))
Foo(Foo &) with val: 6 created from: 1
Foo(Foo&&) moving: 6 and changing it to: 7
~Foo() destroying: 6
pair<Foo, int> pair(foo2, d)
Foo(Foo &) with val: 8 created from: 2
umap.insert(pair)
Foo(const Foo &) with val: 9 created from: 8
umap.emplace(foo3, d)
Foo(Foo &) with val: 10 created from: 3
umap.emplace(11, d)
Foo(int) with val: 11
umap.insert({12, d})
Foo(int) with val: 12
Foo(const Foo &) with val: 13 created from: 12
~Foo() destroying: 12
~Foo() destroying: 8
~Foo() destroying: 3
~Foo() destroying: 2
~Foo() destroying: 1
~Foo() destroying: 0
~Foo() destroying: 13
~Foo() destroying: 11
~Foo() destroying: 5
~Foo() destroying: 10
~Foo() destroying: 7
~Foo() destroying: 9
The BIG picture
The main "big picture" difference between insert()
and emplace()
is:
Whereas using
insert()
almost† always requires the construction or pre-existence of someFoo
object inmain()
's scope (followed by a copy or move), if usingemplace()
then any call to aFoo
constructor is done entirely internally in theunordered_map
(i.e. inside the scope of theemplace()
method's definition). The argument(s) for the key that you pass toemplace()
are directly forwarded to aFoo
constructor call withinunordered_map::emplace()
's definition (optional additional details: where this newly constructed object is immediately incorporated into one ofunordered_map
's member variables so that no destructor is called when execution leavesemplace()
and no move or copy constructors are called).
† The reason for the "almost" in "almost always" above is because one overload of insert()
is actually equivalent to emplace()
. As described in this cppreference.com page, the overload template<class P> pair<iterator, bool> insert(P&& value)
(which is overload (2) of insert()
on that page) is equivalent to emplace(forward<P>(value))
. Since we're interested in differences, I'm going to ignore this overload and not mention this particular technicality again.
Stepping through the code
I will now go through the code and its output in detail.
- First, notice that an
unordered_map
always internally storesFoo
objects (and not, say,Foo *
s) as keys, which are all destroyed when theunordered_map
is destroyed. Here, theunordered_map
's internal keys were foos 13, 11, 5, 10, 7, and 9.
- So technically, our
unordered_map
actually storespair<const Foo, int>
objects, which in turn store theFoo
objects. But to understand the "big picture idea" of howemplace()
differs frominsert()
(see highlighted box above), it's okay to temporarily imagine thispair
object as being entirely passive. Once you understand this "big picture idea," it's important to then back up and understand how the use of this intermediarypair
object byunordered_map
introduces subtle, but important, technicalities.
-
insert()
ing each offoo0
,foo1
, andfoo2
required 2 calls to one ofFoo
's copy/move constructors and 2 calls toFoo
's destructor (as I now describe):-
insert()
ing each offoo0
andfoo1
created a temporary object (foo4
andfoo6
, respectively) whose destructor was then immediately called after the insertion completed. In addition, theunordered_map
's internalFoo
s (which arefoo
s 5 and 7) also had their destructors called when theunordered_map
was destroyed once execution reached the end ofmain()
. - To
insert()
foo2
, we instead first explicitly created a non-temporary pair object (calledpair
), which calledFoo
's copy constructor onfoo2
(creatingfoo8
as an internal member ofpair
). We theninsert()
ed this pair, which resulted inunordered_map
calling the copy constructor again (onfoo8
) to create its own internal copy (foo9
). As withfoo
s 0 and 1, the end result was two destructor calls for thisinsert()
ion with the only difference being thatfoo8
's destructor was called only when we reached the end ofmain()
rather than being called immediately afterinsert()
finished.
-
-
emplace()
ingfoo3
resulted in only 1 copy/move constructor call (creatingfoo10
internally in theunordered_map
) and only 1 call toFoo
's destructor. The reason why callingumap.emplace(foo3, d)
calledFoo
's non-const copy constructor is the following: Since we're usingemplace()
, the compiler knows thatfoo3
(a non-constFoo
object) is meant to be an argument to someFoo
constructor. In this case, the most fittingFoo
constructor is the non-const copy constructorFoo(Foo& f2)
. This is whyumap.emplace(foo3, d)
called a copy constructor whileumap.emplace(11, d)
did not. -
For
foo11
, we directly passed the integer 11 toemplace(11, d)
so thatunordered_map
would call theFoo(int)
constructor while execution is within itsemplace()
method. Unlike in (2) and (3), we didn't even need some pre-exitingfoo
object to do this. Importantly, notice that only 1 call to aFoo
constructor occurred (which createdfoo11
). -
We then directly passed the integer 12 to
insert({12, d})
. Unlike withemplace(11, d)
(which recall resulted in only 1 call to aFoo
constructor), this call toinsert({12, d})
resulted in two calls toFoo
's constructor (creatingfoo12
andfoo13
).
Epilogue
Where to go from here?
a. Play around with the above source code and study documentation for insert()
(e.g. here) and emplace()
(e.g. here) that's found online. If you're using an IDE such as eclipse or NetBeans then you can easily get your IDE to tell you which overload of insert()
or emplace()
is being called (in eclipse, just keep your mouse's cursor steady over the function call for a second). Here's some more code to try out:
cout << "\numap.insert({{" << Foo::foo_counter << ", d}})\n";
umap.insert({{Foo::foo_counter, d}});
//but umap.emplace({{Foo::foo_counter, d}}); results in a compile error!
cout << "\numap.insert(pair<const Foo, int>({" << Foo::foo_counter << ", d}))\n";
umap.insert(pair<const Foo, int>({Foo::foo_counter, d}));
//The above uses Foo(int) and then Foo(const Foo &), as expected. but the
// below call uses Foo(int) and the move constructor Foo(Foo&&).
//Do you see why?
cout << "\numap.insert(pair<Foo, int>({" << Foo::foo_counter << ", d}))\n";
umap.insert(pair<Foo, int>({Foo::foo_counter, d}));
//Not only that, but even more interesting is how the call below uses all
// three of Foo(int) and the Foo(Foo&&) move and Foo(const Foo &) copy
// constructors, despite the below call's only difference from the call above
// being the additional { }.
cout << "\numap.insert({pair<Foo, int>({" << Foo::foo_counter << ", d})})\n";
umap.insert({pair<Foo, int>({Foo::foo_counter, d})});
//Pay close attention to the subtle difference in the effects of the next
// two calls.
int cur_foo_counter = Foo::foo_counter;
cout << "\numap.insert({{cur_foo_counter, d}, {cur_foo_counter+1, d}}) where "
<< "cur_foo_counter = " << cur_foo_counter << "\n";
umap.insert({{cur_foo_counter, d}, {cur_foo_counter+1, d}});
cout << "\numap.insert({{Foo::foo_counter, d}, {Foo::foo_counter+1, d}}) where "
<< "Foo::foo_counter = " << Foo::foo_counter << "\n";
umap.insert({{Foo::foo_counter, d}, {Foo::foo_counter+1, d}});
//umap.insert(initializer_list<pair<Foo, int>>({{Foo::foo_counter, d}}));
//The call below works fine, but the commented out line above gives a
// compiler error. It's instructive to find out why. The two calls
// differ by a "const".
cout << "\numap.insert(initializer_list<pair<const Foo, int>>({{" << Foo::foo_counter << ", d}}))\n";
umap.insert(initializer_list<pair<const Foo, int>>({{Foo::foo_counter, d}}));
You'll soon see that which overload of the pair
constructor (see reference) ends up being used by unordered_map
can have an important effect on how many objects are copied, moved, created, and/or destroyed as well as when this all occurs.
b. See what happens when you use some other container class (e.g. set
or unordered_multiset
) instead of unordered_map
.
c. Now use a Goo
object (just a renamed copy of Foo
) instead of an int
as the range type in an unordered_map
(i.e. use unordered_map<Foo, Goo>
instead of unordered_map<Foo, int>
) and see how many and which Goo
constructors are called. (Spoiler: there is an effect but it isn't very dramatic.)
Solution 4
Apart from the optimisation opportunities and the simpler syntax, an important distinction between insertion and emplacement is that the latter allows explicit conversions. (This is across the entire standard library, not just for maps.)
Here's an example to demonstrate:
#include <vector>
struct foo
{
explicit foo(int);
};
int main()
{
std::vector<foo> v;
v.emplace(v.end(), 10); // Works
//v.insert(v.end(), 10); // Error, not explicit
v.insert(v.end(), foo(10)); // Also works
}
This is admittedly a very specific detail, but when you're dealing with chains of user-defined conversions, it's worth keeping this in mind.
Related videos on Youtube
German Capuano
I earned my PhD from Georgia Institute of Technology, one of the top engineering institutions in the world. I specialize in computational simulations and machine learning, and my work has been published in several top journals. My latest article was one of the most read articles of this year in CMAME, the #1 journal in computational mechanics.
Updated on July 08, 2022Comments
-
German Capuano almost 2 years
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[]
orinsert()
, plus variants like usingvalue_type
ormake_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:What is the advantage of each one of them over the others?
Was there any need for adding emplace to the standard? Is there anything that wasn't possible before without it?
-
Kerrek SB almost 11 yearsEmplacement semantics allow explicit conversions and direct initialization.
-
FrankHB over 5 yearsNow
operator[]
is based ontry_emplace
. It may be worth mentioninginsert_or_assign
as well. -
German Capuano over 5 years@FrankHB if you (or someone else) adds an up-to-date answer, I could change the accepted one.
-
dk123 over 10 yearsThis is hinted in the answer, but map[]=val will overwrite the previous value if one exists.
-
v.oddou almost 10 yearsa more interesting question in my sense, is that it serves little purpose. Because you save the pair copy, which is good because no pair copy means no
mapped_type
isntance copy. What we want, is emplace the construction of themapped_type
in the pair, and emplace the pair construction in the map. Therefore, thestd::pair::emplace
function, and its forwarding support inmap::emplace
are both missing. In its current form, you still have to give a constructed mapped_type to the pair constructor which will copy it, once. its better than twice, but still no good. -
v.oddou almost 10 yearsactually I amend that comment, in C++11 there is a template pair constructor that serves the exact same purpose than emplace in the case of 1 argument construction. and some weird piecewise construct, as they call it, using tuples to forward arguments, so we can still have perfect forwarding it seems.
-
Kaitain over 8 yearsImagine that foo required two ints in its ctor rather than one. Would you be able to use this call?
v.emplace(v.end(), 10, 10);
...or would you now need to use:v.emplace(v.end(), foo(10, 10) );
? -
Kaitain over 8 yearsI don't have access to a compiler right now, but I will assume that this means that both versions will work. Almost all examples you see for
emplace
make use of a class that takes a single parameter. IMO it would actually make the nature of emplace's variadic syntax a good deal more clear if multiple parameters were used in examples. -
Deqing over 7 yearsLooks like there is a performance bug of insert in unordered_map and map: link
-
David Rodríguez - dribeas over 7 years@Deqing: Nothing new, that's been known for ages in most implementations, but it is not a bug in the standard. Some implementations need to pay the cost, others are just not being smart enough about how to do it because it complicates the code sufficiently to do the right thing, and it does not really take all the cost away. A common solution for some cases is using
operator[]
if the Value's value-initialized is not a valid entry in the map (saymap<int, shared_ptr<T>>
in most cases an emptyshared_ptr
is not a valid value) -
underscore_d over 5 years"There was no "need" for adding emplace to the standard." This is patently false.
emplace()
is simply the only way to insert an element that cannot be copied or moved. (& yes, perhaps, to most efficiently insert one whose copy and move constructors cost a lot more than construction, if such a thing exists) It also seems you got the idea wrong: it's not about "[taking] advantage of the rvalue reference to use the actual objects that you have already created"; no object is created yet, & you forward themap
the arguments it needs to create it inside itself. You don't make the object. -
ShadowRanger almost 5 yearsMight be nice to update this with info on
insert_or_assign
andtry_emplace
(both from C++17), which help fill some gaps in functionality from the existing methods. -
BAdhi about 3 yearsI believe its worth mentioning, say if the
Foo(int)
is changed to something likeFoo(int, int)
where there are multiple arguments on constructor, then to achieve something similar toumap.emplace(11, d)
, we can usestd::piecewise_construct
andstd::forward_as_tuple
. So the statement would beumap.emplace(std::piecewise_construct, std::forward_as_tuple(11, 12), std::forward_as_tuple(d));
-
Admin over 2 yearsEmplace is not memory-optimized only for both large memory, it's why i downvoted.
-
Admin over 2 years@underscore_d Fixed in edit.
-
underscore_d over 2 years@Ben_LCDB Thanks for taking the time to try! But I don't agree with edits that substantially change the meaning of the post. If the author wants to fix their post, they can. I don't think it's other members' place to 'fix' it for them by changing the sentiment. Otherwise no one would ever have time to post good answers, as they'd be spending it 'fixing' all the bad ones...
-
Admin over 2 yearsIs it the change of order in the section that made you think it was substantially ? Nevermind !