Above is a piece of code that attempts to implement the emplace family routines. One can insert something like
const value_type& (value_type&&) val or variadic arguments
Args&&... args, both of which then can be handled by the
Of course, this simple implementation is flawed as it requires an extra move operation. In order to obtain the key from
Args&&... args, we need to somehow get the value itself which can be a value (set) or a pair of <key, val> values (map). This is done by using the compile-time template bool constant/parameter
IsMap. If we must construct the actual object within the method
insert_at_leaf, then, well, an extra move operation is inevitable.
The solution to the question is we construct the node in-place, thus the name
empalce ;) We first construct the node in the heap using the variadic arguments
node_ptr z = new_node(/*parent=*/nullptr, std::forward<Args>(args)...); , then
get_key from the node by reference. And what is left is we walk through the tree and find the right position to insert the node and reset the parent link. Tada🎉, there you are. This makes even more sense if we look at the C++ specification where
node_handle were introduced in C++17. Their presence makes implementing
emplace more easily and naturally.
But the C++ folks are soooo ambitious and if the original one has so many combined benefits (simplicity, flexibility, versatility, etc.) and actually works pretty well (given the overhead of an extra move operation is negligible), we can just keep the way it is :)
Ref: A C++17 compliant AVL map container.