How does std::map's emplace() avoid premature construction?

Question

I am confused about std::maps's implementation of emplace(). emplace() is a variadic template function with the following declaration:

template <class Args...>
iterator emplace( Args&&... args );

As far as I understand, emplace() completely avoids constructing its value_type, i.e., std::pair<const key_type,mapped_type>, and instead constructs the object in-place. I assume this means that the object is constructed only once, the moment that the new map node is created. The object is never copied or moved.

What I don't understand is how std::map finds the correct place to add the new entry before constructing the key-value pair. As far as I see, std::map needs access to the key but the key is contained within args and only accessible after construction of the key-value pair.

I must be misunderstanding some aspect of emplace(). Does std::map actually avoid construction of the key-value pair? If so, how does it avoid move/copy operations? Or is there another way to access the key in args?

Answer 1

emplace constructs the pair in-place forwarding the arguments to its constructor; it does not avoid element_type construction, it just avoids one copy of a useless temporary pair compared to insert. In this regard, it's just as for the other containers: emplace is like insert, but instead if receiving a ready-made element_type to copy or move inside the container, it receives the arguments to construct element_type in its target location.

To further clarify: if you call emplace(key, value) key and value are copied/moved anyhow when constructing the pair. It's just that, if you did insert(make_pair(key, value)), not only key and value would have beem copied/moved when creating the temporary pair argument, but the pair itself would have then needed to be moved in the map node.

I don't think that is what OP intends to ask for. The intended question to me seems to be how std::map can find the correct location to insert the new element if it can't construct the key prior to searching for the location, e.g. if the first argument to emplace is not the key type itself.

In that case for an std::map there's not much of a problem: first you can construct a node (which contains the pair and the various pointers to other nodes, and has its own allocation on the heap), and then you can put it in the right place in the RB tree (which boils down to just a couple of pointers assignment).

Answer 2

Well, IIRC, std::map and std::unrodered_map use tree-like structures, with a lot of small nodes pointing at each other. So once the pair is constructed - it doesn't have to be moved anywhere, the map simply needs to point at it from somewhere.