When do I use node_type with std::map::insert?

Question

I'm accustomed to the existing interface of std::map.
Inserting elements returns a bool describing successful insertion,
as well the iterator as to where the inserted element would be.

template< class P >
std::pair<iterator,bool> insert( P&& value ); //(since C++11)

C++17 adds what looks to be a similar call, but with different type names:

insert_return_type insert(node_type&& nh);   //(since C++17)

I tried looking up what a node_type is, but it is primarily unspecified:

template</*unspecified*/>
class /*unspecified*/

Why was this function added in C++17, and when would I use it over the older call?

Answer 1

You can obtain a node from a std::map using its extract() function. Then you can put that node into another map (or into the same map after changing its key).

node_type extract(const_iterator position); (1)   (since C++17)
node_type extract(const key_type& x);       (2)   (since C++17)

1) Unlinks the node that contains the element pointed to by position and returns a node handle that owns it
2) If the container has an element with key equivalent to x, unlinks the node that contains that element from the container and returns a node handle that owns it. Otherwise, returns an empty node handle.

In either case, no elements are copied or moved, only the internal pointers of the container nodes are repointed (rebalancing may occur, as with erase()) Extracting a node invalidates the iterators to the extracted element. Pointers and references to the extracted element remain valid, but cannot be used while element is owned by a node handle: they become usable if the element is inserted into a container.

Example:

map<int, string> m{{1,”mango”}, {2,”papaya”}, {3,”guava”}};
auto nh = m.extract(2);
nh.key() = 4;
m.insert(move(nh));
// m == {{1,”mango”}, {3,”guava”}, {4,”papaya”}}

Answer 2

It's not just std::map, similar functions have been added to all associative and unordered associative containers. They are explained in the standard in [container.node]/1

A node handle is an object that accepts ownership of a single element from an associative container (23.2.4) or an unordered associative container (23.2.5). It may be used to transfer that ownership to another container with compatible nodes. Containers with compatible nodes have the same node handle type. ...

The table following the section above shows the containers with compatible nodes.

What the node handle interface allows you to do is transfer elements (nodes) from one container to another (compatible) container without having to copy/move the elements. Instead, the individual internal nodes maintained by the container are transferred as a whole.

This becomes necessary when dealing with a container that contains a non-copyable, non-moveable type.