Confusion about the different efficiency between emplacement and insertion for containers not allowing duplicates

Question

In Item 41 from Effective Modern C++, the following is one of the situations that give a chance for emplacement functions to be more performant than the insertion conterparts:

The container is unlikely to reject the new value as a duplicate

the reason being that, given the arguments to the constructor of the oject whose insertion in the container is attempted, the emplace function will have to construct that object to asses whether it is already present in the container, in which case the construction has been a waste, followed by the unavoidable waste of the desctruction too.

I have already some doubts here. If I was to use the insertion function to avoid this scenario, then I would be constructing the object myself (probably a temporary, passing to its construtor the arguments that I'd pass to the emplacement function), and passing it to the insertion function, and then that temporary, if an equal value was in the container already, would got destroyed.

So I don't see a difference.

Furthermore, the author adds that

Such nodes are created for emplacement functions more often than for insertion functions.

Why in the world should which function I use to insert an object in a container influece if that object is already in the container?

Answer 1

I am not sure if and how this applies to the unordered containers. But a std::set is normally internally represented by a binary tree (often a red-black tree). You can assume that the nodes look somewhat like this:

struct Node {
    Node* parent, left_child, right_child;
    value_type value;
}

Now let's see what happens when emplacing and inserting:

• emplace(args...): Now, we need a value_type-object to be able to do the comparison. But we will not create a temporary that we will later move (std::set does not require value_type to be either moveable or copyable!). We will directly create a Node a on the heap and construct value inplace from args. After that we check if value is already in the set. If so, we delete a and are done. Otherwise we adjust the Node* of a to take it into the set.

• insert(val): Here, we already have an object (that may be a temporary). So we find out if it is already in the set. If so, nothing happens and we are done. If it is not in the set, we now allocate a Node and copy/move val into that Node and set the Node* to take it into the set.

Now let's analyze the different szenarios.

• emplace(args...): It does not matter if the value_type object constructed from args... is already in the map. We will always allocate one Node and use the value_type(args...) constructor once. No moves, no copies. If the object is already present, we will delete a Node thereby calling the destructor of value_type.
• insert(val): If val is already present, we make no constructions at all in insert. If not, we allocate one Node and copy/move val into it. If you construct val from args... while passing it to insert (i.e. call insert(value_type(args...))), then we of course have another value_type(args...) and also a call to the destructor of this temporary.

So, emplace will always have an allocation of Node, regardless of the value being present or not. insert(value_type(args...)) will no have that if the value was present, but it will have an extra move, if the value was not present.

So if your container will likely reject the object, you will have needless heap allocations for the Node. This can be more costly than the extra move from insert. Also, you will see that it is never reasonable to emplace an already existing object, since that will only add Node-allocations¹ if it fails and has no bonus.

---

1: One could have another overload of emplace(value_type) to not do that. I am not sure if the standard libraries do that.