[PATCH] Implement C++17 node extraction and insertion (P0083R5)

[Jonathan Wakely]

On 21/09/16 14:48 +0100, Jonathan Wakely wrote:
>This implements container node extraction/insertion, and merging. The
>patch includes Debug Mode support and pretty printers for the node
>handles.
>
>Most of the changes are fairly straightforward, with two things worth
>pointing out.
>
>There's a FIXME in bits/hashtable.h due to an exception-safety issue.
>If the hash function or equality predicate throws then the node is
>destroyed and deallocated. It would be better to leave it unchanged in
>the node_handle argument.
>
>I didn't want to make all map and multimap specializations friends of
>each other (and similarly for all sets and multisets, and again for
>the unordered ones). That would make it too easy to accidentally
>access the internals of a map<T,U> from a map<V,W>. So I defined the
>_Rb_tree_merge_helper and _Hash_merge_helper class templates to
>mediate access, so that any access to a "foreign" container type must
>be done through that type, and only certain internals can be obtained.

I forgot to mention another thing worth calling out.

I spoke to Richi and Michael Matz at the Cauldron and they assured me
that the middle end won't do any optimizations that would cause the
"magic happens here" part to do the wrong thing. Specifically, the
node handle for maps does this to get a non-const pointer to the
key_type in the pair:

      auto& __key = const_cast<_Key&>(__ptr->_M_valptr()->first);
      _M_pkey = _S_pointer_to(__key);
      _M_pmapped = _S_pointer_to(__ptr->_M_valptr()->second);

Where _S_pointer_to() is:

      template<typename _Tp>
        using __pointer = __ptr_rebind<typename _AllocTraits::pointer, _Tp>;

      template<typename _Tp>
        __pointer<_Tp>
        _S_pointer_to(_Tp& __obj)
        { return pointer_traits<__pointer<_Tp>>::pointer_to(__obj); }

The potentially worrying part of this is the const_cast, but as we
know that the pair is inside a non-const node allocated on the heap,
it will never be in read-only memory or actually non-modifiable. Once
we have std::launder we could consider using that, i.e.

      _M_pkey = _S_pointer_to(std::launder(__key));