[libcxx][c++17] P0083R5: Splicing Maps and Sets

[erik.pilkington]

Summary

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0083r3.pdf

This patch adds support for p0083, splicing maps and sets. This feature allows users to extract a container node from a unordered or associative container, then insert it into another container without having to copy the node. The container_type::node_type member is a smart pointer that holds an extracted node. This proposal also includes a merge member function that can extract and insert nodes from a source container without losing nodes if an exception is thrown (from, i.e., a comparator).

This implementation for this is pretty straightforward, most of the operations necessary to write this API are already part of __tree and __hash_table. In __hash_table, I split up the functions __node_insert_unqiue and __node_insert_multi into 2 parts in order to implement merge. The first part, __node_insert_{multi,unique}_prepare checks to see if a node already is present in the container (as needed), and rehashes the container. This function can forward exceptions, but doesn't mutate the node it's preparing to insert. the __node_insert_{multi,unique}_perform is noexcept, but mutates the pointers in the node to actually insert it into the container. This allows merge to call a _prepare function on a node while it is in the source container, without invalidating anything or losing nodes if an exception is thrown. Another quirk is the __generic_container_node_destructor templated struct, this is forward-declared (and used, in a dependent context) in <__node_handle> and specialized in <__tree> and <__hash_table>. This allows <__node_handle> to call into __hash_node_destructor and __tree_node_destructor without including those headers.

As far as testing goes, I added some tests and ran them with msan, ubsan, and asan. I also ran the libstdc++ tests for this with the same sanitizers on linux and macos.

I'm still pretty new to libc++, so take this patch with a grain of salt!
Thanks for taking a look,
Erik

[rsmith]

How do you deal with the fact that node handles for map-like types need to be able to mutate a const member of a pair in-place? Are you assuming/hoping the compiler won't do bad things to the program as a result, or is there some reason why it would be unlikely to do so / disallowed from doing so? If you're just casting pair<const K, V> to / from pair<K, V> (and I think that's what's happening), there is a very real risk that struct-path-sensitive TBAA will decide that pair<const K, V>::first and pair<K, V>::first cannot alias (and likewise for ::second) and then miscompile code using libc++'s node pointers.

One way we could deal with this is by adding an attribute to the compiler to indicate "the const is a lie", that we can apply to std::pair::first, with the semantics being that a top-level const is ignored when determining the "real" type of the member (and so mutating the member after a const_cast has defined behavior). This would apply to all std::pairs, not just the node_handle case, but in practice we don't optimize on the basis of a member being declared const *anyway*, so this isn't such a big deal right now.

Another possibility would be a compiler intrinsic to change the type of the pair, in-place, from a std::pair<const K, V> to a std::pair<K, V>, without changing anything about the members -- except that the first member changes type.

Yet another possibility would be to only ever access the key field through a type annotated with __attribute__((may_alias)), and then launder the node pointer when we're ready to insert it back into the container (to "pick up" the new value of the const member). That's formally breaking the rules (a launder isn't enough, because we didn't actually create a new object, and in any case we still mutated the value of a const subobject), but it'll probably work fine across compilers that support the attribute.

libcxx/include/__node_handle

148

using __base::__base; would be a much more reasonable way to write an inheriting constructor declaration here.

[erik.pilkington]

Use the simpler inherited constructor spelling @rsmith suggested.

[erik.pilkington]

One way we could deal with this is by adding an attribute to the compiler to indicate "the const is a lie", that we can apply to std::pair::first, with the semantics being that a top-level const is ignored when determining the "real" type of the member (and so mutating the member after a const_cast has defined behavior). This would apply to all std::pairs, not just the node_handle case, but in practice we don't optimize on the basis of a member being declared const *anyway*, so this isn't such a big deal right now.

I'm a fan of this idea, this would also have the bonus of fixing some pre-existing type-punning between pair<const K, V> and pair<K, V> (see __hash_value_type and __value_type in <unordered_map> and <map>).

Another possibility would be a compiler intrinsic to change the type of the pair, in-place, from a std::pair<const K, V> to a std::pair<K, V>, without changing anything about the members -- except that the first member changes type.

How could this work? It would still be possible for TBAA to assume that void m(std::pair<const K, V>*, std::pair<K, V>*);'s parameters don't alias when optimizing m, regardless of how we form the non-const pair, right?

Yet another possibility would be to only ever access the key field through a type annotated with __attribute__((may_alias)), and then launder the node pointer when we're ready to insert it back into the container (to "pick up" the new value of the const member). That's formally breaking the rules (a launder isn't enough, because we didn't actually create a new object, and in any case we still mutated the value of a const subobject), but it'll probably work fine across compilers that support the attribute.

I think we could fall back to this in cases where the attribute from idea (1) isn't available. There, we could mark std::pair as may_alias and still fix __hash_value_type and __value_type. This would pessimize std::pair, but only for "older" compilers.

So unless I've gotten this all wrong, I'll write a patch to support that new attribute and come back to this patch if/when that lands. Sound good?

Thanks for the feedback!
Erik

[mclow.lists]

One way we could deal with this is by adding an attribute to the compiler to indicate "the const is a lie", that we can apply to std::pair::first, with the semantics being that a top-level const is ignored when determining the "real" type of the member (and so mutating the member after a const_cast has defined behavior). This would apply to all std::pairs, not just the node_handle case, but in practice we don't optimize on the basis of a member being declared const *anyway*, so this isn't such a big deal right now.

I'm a fan of this idea, this would also have the bonus of fixing some pre-existing type-punning between pair<const K, V> and pair<K, V> (see hash_value_type and value_type in <unordered_map> and <map>).

This was supposed to be taken care of by [class.mem]/21 (common initial sequence), but that foundered on "standard-layout".

[rsmith]

In D46845#1099732, @mclow.lists wrote:

One way we could deal with this is by adding an attribute to the compiler to indicate "the const is a lie", that we can apply to std::pair::first, with the semantics being that a top-level const is ignored when determining the "real" type of the member (and so mutating the member after a const_cast has defined behavior). This would apply to all std::pairs, not just the node_handle case, but in practice we don't optimize on the basis of a member being declared const *anyway*, so this isn't such a big deal right now.

I'm a fan of this idea, this would also have the bonus of fixing some pre-existing type-punning between pair<const K, V> and pair<K, V> (see hash_value_type and value_type in <unordered_map> and <map>).

This was supposed to be taken care of by [class.mem]/21 (common initial sequence), but that foundered on "standard-layout".

Also, the common initial sequence rule only allows loads through the wrong type, not stores, and in any case does not alter the rule that modifying a const object results in UB.

[erik.pilkington]

In D46845#1098634, @rsmith wrote:

One way we could deal with this is by adding an attribute to the compiler to indicate "the const is a lie", that we can apply to std::pair::first, with the semantics being that a top-level const is ignored when determining the "real" type of the member (and so mutating the member after a const_cast has defined behavior). This would apply to all std::pairs, not just the node_handle case, but in practice we don't optimize on the basis of a member being declared const *anyway*, so this isn't such a big deal right now.

Would you mind elaborating on this? If we don't optimize on a member being const, then what should this attribute actually do? The only thing I can think of is making a field with type const T with the attribute claim it's a T to TBAA, but that would be a no-op because loads and stores through those types are compatible anyways.

In D46845#1098634, @rsmith wrote:

Yet another possibility would be to only ever access the key field through a type annotated with __attribute__((may_alias)), and then launder the node pointer when we're ready to insert it back into the container (to "pick up" the new value of the const member). That's formally breaking the rules (a launder isn't enough, because we didn't actually create a new object, and in any case we still mutated the value of a const subobject), but it'll probably work fine across compilers that support the attribute.

What about instead of type-punning between pair<const K, V> and pair<K, V> (with may_alias) we just did a const_cast in key, and launder the pair when finished? Because loads and stores to const K and K are already assumed to alias each other, we should be able to omit the may_alias attribute (right?). Would that be enough to placate the compiler? If it is, then I think we should just do this and avoid adding another attribute to clang. I'll upload a patch with this to show what I mean.

Thanks!
Erik

[erik.pilkington]

make __map_node_handle use a const_cast on the key instead of type-punning between pair<const K, V> and pair<K, V>. Add calls to std::launder in key() and before inserting a node handle.

[erik.pilkington]

Add _LIBCPP_ASSERT calls to all the entry points, friendly ping!

[rsmith]

In D46845#1105638, @erik.pilkington wrote:

make __map_node_handle use a const_cast on the key instead of type-punning between pair<const K, V> and pair<K, V>. Add calls to std::launder in key() and before inserting a node handle.

Can you do this as a separate change, prior to adding node_handle? I would in particular expect this to result in the removal of the union __value_type from <map>.

[erik.pilkington]

Update this patch to depend on https://reviews.llvm.org/D47607, which fixes __value_type in map and unordered_map. Thanks!

[EricWF]

libcxx/include/__hash_table

2261

If I'm not mistaken, __node_handle_extract_unique and __node_handle_extract_multi have the exact same implementation. This is intentional, no? If so can't we just use one implementation?

libcxx/include/__node_handle

2

This header needs to be added to the module.modulemap.

83

I'm not sure we should by trying to move a pointer. It's misleading, and we shouldn't expect it to act any differently.

119

Missing _LIBCPP_NODISCARD_AFTER_CXX17

libcxx/test/std/containers/associative/set/merge.pass.cpp

21

Please include test_macros.h directly.

[erik.pilkington]

Address @EricWF's comments.

libcxx/include/__hash_table

2261

Yep, good point. The new patch just has __node_handle_extract.

[erik.pilkington]

Ping!

[erik.pilkington]

Ping! If it'd make this easier to review, I'd be happy to split this up a bit.

[erik.pilkington]

Split this up. I'm moving the merge stuff to a follow-up, that makes this diff a lot easier to read.

[erik.pilkington]

Ping!

[EricWF]

I'm working on this! I'll be taking what is hopefully a final pass at the tests today.

[ldionne]

Generally looks pretty good, but I have a couple questions/suggestions.

libcxx/include/__hash_table

2226

When a function is declared with a visibility macro (_LIBCPP_INLINE_VISIBILITY in this case), I think it is customary in libc++ to repeat the visibility macro on the definition as well. If that's correct, apply here and to other similar functions below, and also in __tree.

2273

Just a quick Q: am I mistaken or remove() is not part of the unordered_map API? We're not naming it __remove() just because we already have other functions called remove(), so any macro redefining remove would already break things -- is that the idea?

libcxx/include/__node_handle

34

Clever way of reducing header dependencies. I like it.

37

I'd like to suggest a different approach for implementing the node handles for sets and maps. I believe this would simplify things slightly:

template <class _NodeType, class _Alloc, template <class...> class _MapOrSetSpecifics>
class __basic_node_handle 
    : public _MapOrSetSpecifics<_NodeType, __basic_node_handle<_NodeType, _Alloc, _MapOrSetSpecifics>>
{
    // same as right now
};

Then, you can get the two different node handles by simply providing the methods in the base class:

template <class _NodeType, class _Derived>
struct __map_node_handle_specifics {
    using key_type = typename _NodeType::__node_value_type::key_type;
    using mapped_type = typename _NodeType::__node_value_type::mapped_type;

    _LIBCPP_INLINE_VISIBILITY
    key_type& key() const
    {
        return static_cast<_Derived const*>(this)->__ptr_->__value_.__ref().first;
    }

    _LIBCPP_INLINE_VISIBILITY
    mapped_type& mapped() const
    {
        return static_cast<_Derived const*>(this)->__ptr_->__value_.__ref().second;
    }
};

template <class _NodeType, class _Derived>
struct __set_node_handle_specifics {
    using value_type = typename _NodeType::__node_value_type;

    _LIBCPP_INLINE_VISIBILITY
    value_type& value() const
    {
        return static_cast<_Derived const*>(this)->__ptr_->__value_;
    }
};

template <class _NodeType, class _Alloc>
using __map_node_handle = __basic_node_handle<_NodeType, _Alloc, __map_node_handle_specifics>;

template <class _NodeType, class _Alloc>
using __set_node_handle = __basic_node_handle<_NodeType, _Alloc, __set_node_handle_specifics>;

This is a classic application of the CRTP. I believe it would reduce the amount of boilerplate currently required for special member functions. It's possible that you thought of this and realized it didn't work for a reason I'm missing right now, too, but the idea seems to work on the surface: https://wandbox.org/permlink/nMaKEg43PVJpA0ld.

You don't have to do this, but please consider it if you think it would simplify the code.

libcxx/include/map

863

I believe this function should be marked with _LIBCPP_INLINE_VISIBILITY -- even though in practice the compiler will probably always inline it.

Also, you don't seem to be using that function at all in the diff -- is that right?

So please either mark with _LIBCPP_INLINE_VISIBILITY and use it, or remove it altogether. This comment applies to all 8 containers to which similar methods were added.

libcxx/include/set

399

Is this forward declaration necessary?

libcxx/include/unordered_set

569

Why don't you use

return __table.template __node_handle_insert_unique<node_type>(__hint, _VSTD::move(__nh));

instead? It seems like this way, if __node_handle_insert_unique(const_iterator, node_type) eventually starts taking advantage of the iterator hint, you'd get the improvement here for free.

1090

For the other containers, the two insert methods come before the two extract methods. This is very nitpicky, but you should consider keeping the same order here too for consistency.

libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/insert_extract.pass.cpp

15

Please be more specific about which functions you're testing. I find it useful to look at those comments to quickly see what exact signatures are being tested when I'm looking for tests that exercice some specific piece of code.

Actually, perhaps you should extract those tests into multiple files:
unord.map/unord.map.modifiers/insert.node_handle.pass.cpp => test overload of insert on node_type
unord.map/unord.map.modifiers/insert.hint_node_handle.pass.cpp => test overload of insert with a hint and a node_type
unord.map/unord.map.modifiers/extract.node_handle.pass.cpp => test overload of extract on node_type
unord.map/unord.map.modifiers/extract.iterator.pass.cpp => test overload of extract on iterator
unord.map/insert_return_type.pass.cpp => test insert_return_type
unord.map/node_type.pass.cpp => test node handle operations

I believe this would be more consistent with the way things are currently organized for other functions. This comment applies to all containers touched by this review.

24

Consider using using XXX = YYY consistently.

34

You don't need spaces between consecutive >'s since those tests are not supported in C++03. Feel free to keep them or remove them, I'm just pointing it out.

100–102

Why is this test useful?

[ldionne]

I forgot to mention it in my initial review, but it also seems like you forgot to update all the synopsis in the comments at the beginning of headers.

[erik.pilkington]

Address @ldionne's comments.

libcxx/include/__hash_table

2226

I can't say I know libc++'s policy here either, but it couldn't hurt, so I added the attributes to the new patch. Maybe @EricWF or @mclow.lists could weigh in here?

2273

Yep, I think that was the thinking. IMO it would be nice to just call it __remove to avoid any confusion.

libcxx/include/__node_handle

37

Oh, neat! That's a great idea, I didn't even consider CRTP here for some reason. Makes this simpler though. I added this to the new patch.

libcxx/include/map

863

Oh, sorry! This was used in the implementation of merge, which I moved to a follow-up. I'll sink it down there and add the visibility attribute.

libcxx/include/set

399

No, nice catch! This was also supposed to be a part of the follow-up, I'll move it there.

libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/insert_extract.pass.cpp

15

Okay, the new patch divides up the tests for each container into 4 files: extract_iterator.pass.cpp, extract_key.pass.cpp, insert_node_type.pass.cpp, and insert_node_type_hint.pass.cpp. I decided to move the insert_return_type and node_type testing to container.node/node_handle.pass.cpp because they don't really depend on any specific container, and it matches how the standard defines these.

24

done!

34

Sure, sorry! clang-format adds these in because it isn't smart enough to know when we're in a C++11 context.

100–102

I guess it isn't really, it was more of a sanity check.

[ldionne]

libcxx/include/map

43

You are missing // since C++17 comments here and elsewhere.

[erik.pilkington]

Add // C++17 to the header comments.

[ldionne]

LGTM -- great! Just make sure the commit message does not pretend the change includes merge.

This may be obvious, but my LGTM alone should probably not be enough to submit.

[erik.pilkington]

Ping!

[erik.pilkington]

Ping!

[mclow.lists]

One more thing -
When you add a new header file, you need to update include/module.modulemap, test/libcxx/double_include.sh.cpp, and include/CMakeLists.txt.
Take a look at D49338 for an example.

[erik.pilkington]

Address @mclow.lists's comment. Thanks!

[erik.pilkington]

In D46845#1183435, @mclow.lists wrote:

One more thing -
When you add a new header file, you need to update include/module.modulemap, test/libcxx/double_include.sh.cpp, and include/CMakeLists.txt.
Take a look at D49338 for an example.

Are you sure we have to update test/libcxx/double_include.sh.cpp? Looks like that file only has public headers, but this patch only adds __node_handle, which is internal. The new patch adds this header to include/CMakeLists.txt though (__node_handle already appeared in module.modulemap)

[mclow.lists]

In D46845#1183462, @erik.pilkington wrote:

In D46845#1183435, @mclow.lists wrote:

One more thing -
When you add a new header file, you need to update include/module.modulemap, test/libcxx/double_include.sh.cpp, and include/CMakeLists.txt.
Take a look at D49338 for an example.

Are you sure we have to update test/libcxx/double_include.sh.cpp? Looks like that file only has public headers, but this patch only adds __node_handle, which is internal. The new patch adds this header to include/CMakeLists.txt though (__node_handle already appeared in module.modulemap)

D'oh! You're right. I didn't see that you had a patch for module.modulemap.
Sorry for the noise.

Go ahead and commit (and thanks for doing this!)

libcxx/include/__hash_table

             __alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__value_));
         if (__p)
             __alloc_traits::deallocate(__na_, __p, 1);
     }
 
     template <class> friend class __hash_map_node_destructor;
 };
 
+#if _LIBCPP_STD_VER > 14
+template <class _NodeType, class _Alloc>
+struct __generic_container_node_destructor;
+
+template <class _Tp, class _VoidPtr, class _Alloc>
+struct __generic_container_node_destructor<__hash_node<_Tp, _VoidPtr>, _Alloc>
+    : __hash_node_destructor<_Alloc>
+{
+    using __hash_node_destructor<_Alloc>::__hash_node_destructor;
+};
+#endif
 
 #ifndef _LIBCPP_CXX03_LANG
 template <class _Key, class _Hash, class _Equal, class _Alloc>
 struct __diagnose_hash_table_helper {
   static constexpr bool __trigger_diagnostics()
     _LIBCPP_DIAGNOSE_WARNING(__check_hash_requirements<_Key, _Hash>::value
                          && !__invokable<_Hash const&, _Key const&>::value,
       "the specified hash functor does not provide a const call operator")

     size_type max_size() const _NOEXCEPT
     {
         return std::min<size_type>(
             __node_traits::max_size(__node_alloc()),
             numeric_limits<difference_type >::max()
         );
     }
 
+private:
+    __next_pointer __node_insert_multi_prepare(size_t __cp_hash,
+                                               value_type& __cp_val);
+    void __node_insert_multi_perform(__node_pointer __cp,
+                                     __next_pointer __pn) _NOEXCEPT;
+
+    __next_pointer __node_insert_unique_prepare(size_t __nd_hash,
+                                                value_type& __nd_val);
+    void __node_insert_unique_perform(__node_pointer __ptr) _NOEXCEPT;
+
+public:
     pair<iterator, bool> __node_insert_unique(__node_pointer __nd);
     iterator             __node_insert_multi(__node_pointer __nd);
     iterator             __node_insert_multi(const_iterator __p,
                                              __node_pointer __nd);
 
 #ifndef _LIBCPP_CXX03_LANG
     template <class _Key, class ..._Args>
     _LIBCPP_INLINE_VISIBILITY

     iterator __insert_multi(const_iterator __p, const __container_value_type& __x);
 #endif
 
     _LIBCPP_INLINE_VISIBILITY
     pair<iterator, bool> __insert_unique(const __container_value_type& __x) {
         return __emplace_unique_key_args(_NodeTypes::__get_key(__x), __x);
     }
 
+#if _LIBCPP_STD_VER > 14
+    template <class _NodeHandle, class _InsertReturnType>
+    _LIBCPP_INLINE_VISIBILITY
+    _InsertReturnType __node_handle_insert_unique(_NodeHandle&& __nh);
+    template <class _NodeHandle>
+    _LIBCPP_INLINE_VISIBILITY
+    iterator __node_handle_insert_unique(const_iterator __hint,
+                                         _NodeHandle&& __nh);
+    template <class _NodeHandle>
+    _LIBCPP_INLINE_VISIBILITY
+    _NodeHandle __node_handle_extract_unique(key_type const& __key);
+    template <class _NodeHandle>
+    _NodeHandle __node_handle_extract_unique(const_iterator __it);
+    template <class _Table>
+    _LIBCPP_INLINE_VISIBILITY
+    void __node_handle_merge_unique(_Table& __source);
+
+    template <class _NodeHandle>
+    _LIBCPP_INLINE_VISIBILITY
+    iterator __node_handle_insert_multi(_NodeHandle&& __nh);
+    template <class _NodeHandle>
+    _LIBCPP_INLINE_VISIBILITY
+    iterator __node_handle_insert_multi(const_iterator __hint, _NodeHandle&& __nh);
+    template <class _NodeHandle>
+    _LIBCPP_INLINE_VISIBILITY
+    _NodeHandle __node_handle_extract_multi(key_type const&);
+    template <class _NodeHandle>
+    _LIBCPP_INLINE_VISIBILITY
+    _NodeHandle __node_handle_extract_multi(const_iterator __it);
+    template <class _Table>
+    _LIBCPP_INLINE_VISIBILITY
+    void __node_handle_merge_multi(_Table& __source);
+#endif
+
     void clear() _NOEXCEPT;
     void rehash(size_type __n);
     _LIBCPP_INLINE_VISIBILITY void reserve(size_type __n)
         {rehash(static_cast<size_type>(ceil(__n / max_load_factor())));}
 
     _LIBCPP_INLINE_VISIBILITY
     size_type bucket_count() const _NOEXCEPT
     {

         size_type __bc = bucket_count();
         for (size_type __i = 0; __i < __bc; ++__i)
             __bucket_list_[__i] = nullptr;
         size() = 0;
     }
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
-pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd)
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_prepare(
+    size_t __hash, value_type& __value)
 {
-    __nd->__hash_ = hash_function()(__nd->__value_);
     size_type __bc = bucket_count();
-    bool __inserted = false;
-    __next_pointer __ndptr;
-    size_t __chash;
+
     if (__bc != 0)
     {
-        __chash = __constrain_hash(__nd->__hash_, __bc);
-        __ndptr = __bucket_list_[__chash];
+        size_t __chash = __constrain_hash(__hash, __bc);
+        __next_pointer __ndptr = __bucket_list_[__chash];
         if (__ndptr != nullptr)
         {
             for (__ndptr = __ndptr->__next_; __ndptr != nullptr &&
-                                             __constrain_hash(__ndptr->__hash(), __bc) == __chash;
-                                                     __ndptr = __ndptr->__next_)
             {
-                if (key_eq()(__ndptr->__upcast()->__value_, __nd->__value_))
-                    goto __done;
+                if (key_eq()(__ndptr->__upcast()->__value_, __value))
+                    return __ndptr;
             }
         }
     }
+    if (size()+1 > __bc * max_load_factor() || __bc == 0)
     {
-        if (size()+1 > __bc * max_load_factor() || __bc == 0)
-        {
-            rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
-                           size_type(ceil(float(size() + 1) / max_load_factor()))));
-            __bc = bucket_count();
-            __chash = __constrain_hash(__nd->__hash_, __bc);
-        }
-        // insert_after __bucket_list_[__chash], or __first_node if bucket is null
-        __next_pointer __pn = __bucket_list_[__chash];
-        if (__pn == nullptr)
-        {
-            __pn =__p1_.first().__ptr();
-            __nd->__next_ = __pn->__next_;
-            __pn->__next_ = __nd->__ptr();
-            // fix up __bucket_list_
-            __bucket_list_[__chash] = __pn;
-            if (__nd->__next_ != nullptr)
-                __bucket_list_[__constrain_hash(__nd->__next_->__hash(), __bc)] = __nd->__ptr();
-        }
-        else
-        {
-            __nd->__next_ = __pn->__next_;
-            __pn->__next_ = __nd->__ptr();
-        }
+        rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
+                                     size_type(ceil(float(size() + 1) / max_load_factor()))));
+    }
+    return nullptr;
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+void
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique_perform(
+    __node_pointer __nd) _NOEXCEPT
+    size_type __bc = bucket_count();
+    size_t __chash = __constrain_hash(__nd->__hash(), __bc);
+    // insert_after __bucket_list_[__chash], or __first_node if bucket is null
+    __next_pointer __pn = __bucket_list_[__chash];
+    if (__pn == nullptr)
+    {
+        __pn =__p1_.first().__ptr();
+        __nd->__next_ = __pn->__next_;
+        __pn->__next_ = __nd->__ptr();
+        // fix up __bucket_list_
+        __bucket_list_[__chash] = __pn;
+        if (__nd->__next_ != nullptr)
+            __bucket_list_[__constrain_hash(__nd->__next_->__hash(), __bc)] = __nd->__ptr();
+    }
+    else
+    {
+        __nd->__next_ = __pn->__next_;
+        __pn->__next_ = __nd->__ptr();
+    }
+    ++size();
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd)
+{
+    __nd->__hash_ = hash_function()(__nd->__value_);
+    __next_pointer __ndptr =
+        __node_insert_unique_prepare(__nd->__hash(), __nd->__value_);
+    bool __inserted = false;
+    if (__ndptr == nullptr)
+    {
+        __node_insert_unique_perform(__nd);
         __ndptr = __nd->__ptr();
-        // increment size
-        ++size();
         __inserted = true;
     }
-__done:
 #if _LIBCPP_DEBUG_LEVEL >= 2
     return pair<iterator, bool>(iterator(__ndptr, this), __inserted);
 #else
     return pair<iterator, bool>(iterator(__ndptr), __inserted);
 #endif
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
-typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
-__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp)
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::__next_pointer
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_prepare(
+    size_t __cp_hash, value_type& __cp_val)
 {
-    __cp->__hash_ = hash_function()(__cp->__value_);
     size_type __bc = bucket_count();
     if (size()+1 > __bc * max_load_factor() || __bc == 0)
     {
         rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
                                      size_type(ceil(float(size() + 1) / max_load_factor()))));
         __bc = bucket_count();
     }
-    size_t __chash = __constrain_hash(__cp->__hash_, __bc);
+    size_t __chash = __constrain_hash(__cp_hash, __bc);
     __next_pointer __pn = __bucket_list_[__chash];
-    if (__pn == nullptr)
-    {
-        __pn =__p1_.first().__ptr();
-        __cp->__next_ = __pn->__next_;
-        __pn->__next_ = __cp->__ptr();
-        // fix up __bucket_list_
-        __bucket_list_[__chash] = __pn;
-        if (__cp->__next_ != nullptr)
-            __bucket_list_[__constrain_hash(__cp->__next_->__hash(), __bc)]
-                = __cp->__ptr();
-    }
-    else
+    if (__pn != nullptr)
     {
         for (bool __found = false; __pn->__next_ != nullptr &&
-                                   __constrain_hash(__pn->__next_->__hash(), __bc) == __chash;
-                                                           __pn = __pn->__next_)
         {
             //      __found    key_eq()     action
             //      false       false       loop
             //      true        true        loop
             //      false       true        set __found to true
             //      true        false       break
-            if (__found != (__pn->__next_->__hash() == __cp->__hash_ &&
-                            key_eq()(__pn->__next_->__upcast()->__value_, __cp->__value_)))
+            if (__found != (__pn->__next_->__hash() == __cp_hash &&
+                            key_eq()(__pn->__next_->__upcast()->__value_, __cp_val)))
             {
                 if (!__found)
                     __found = true;
                 else
                     break;
             }
         }
+    }
+    return __pn;
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+void
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi_perform(
+    __node_pointer __cp, __next_pointer __pn) _NOEXCEPT
+{
+    size_type __bc = bucket_count();
+    size_t __chash = __constrain_hash(__cp->__hash_, __bc);
+    if (__pn == nullptr)
+    {
+        __pn =__p1_.first().__ptr();
+        __cp->__next_ = __pn->__next_;
+        __pn->__next_ = __cp->__ptr();
+        // fix up __bucket_list_
+        __bucket_list_[__chash] = __pn;
+        if (__cp->__next_ != nullptr)
+            __bucket_list_[__constrain_hash(__cp->__next_->__hash(), __bc)]
+                = __cp->__ptr();
+    }
+    else
+    {
         __cp->__next_ = __pn->__next_;
         __pn->__next_ = __cp->__ptr();
         if (__cp->__next_ != nullptr)
         {
             size_t __nhash = __constrain_hash(__cp->__next_->__hash(), __bc);
             if (__nhash != __chash)
                 __bucket_list_[__nhash] = __cp->__ptr();
         }
     }
     ++size();
+}
+
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __cp)
+{
+    __cp->__hash_ = hash_function()(__cp->__value_);
+    __next_pointer __pn = __node_insert_multi_prepare(__cp->__hash(), __cp->__value_);
+    __node_insert_multi_perform(__cp, __pn);
+
 #if _LIBCPP_DEBUG_LEVEL >= 2
     return iterator(__cp->__ptr(), this);
 #else
     return iterator(__cp->__ptr());
 #endif
 }
 
 template <class _Tp, class _Hash, class _Equal, class _Alloc>

 #if _LIBCPP_DEBUG_LEVEL >= 2
     _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
         "unordered container::insert(const_iterator, lvalue) called with an iterator not"
         " referring to this unordered container");
 #endif
     __node_holder __h = __construct_node(__x);
     iterator __r = __node_insert_multi(__p, __h.get());
     __h.release();
     return __r;
 }
 
 #endif  // _LIBCPP_CXX03_LANG
 
+#if _LIBCPP_STD_VER > 14
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _NodeHandle, class _InsertReturnType>
+_InsertReturnType
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique(
+    _NodeHandle&& __nh)
+{
+    if (__nh.empty())
+        return _InsertReturnType{end(), false, _NodeHandle()};
+    pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_);
+    if (__result.second)
+        __nh.__release();
+    return _InsertReturnType{__result.first, __result.second, _VSTD::move(__nh)};
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _NodeHandle>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_unique(
+    const_iterator, _NodeHandle&& __nh)
+{
+    if (__nh.empty())
+        return end();
+    pair<iterator, bool> __result = __node_insert_unique(__nh.__ptr_);
+    if (__result.second)
+        __nh.__release();
+    return __result.first;
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _NodeHandle>
+_NodeHandle
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract_unique(
+    key_type const& __key)
+{
+    iterator __i = find(__key);
+    if (__i == end())
+        return _NodeHandle();
+    return __node_handle_extract_unique<_NodeHandle>(__i);
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _NodeHandle>
+_NodeHandle
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract_unique(
+    const_iterator __p)
+{
+    allocator_type __alloc(__node_alloc());
+    return _NodeHandle(remove(__p).release(), __alloc);
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Table>
+void
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_unique(
+    _Table& __source)
+{
+    static_assert(is_same<__node, typename _Table::__node>::value, "");
+
+    for (typename _Table::iterator __it = __source.begin();
+         __it != __source.end();)
+    {
+        __node_pointer __src_ptr = __it.__node_->__upcast();
+        size_t __hash = hash_function()(__src_ptr->__value_);
+        __next_pointer __ndptr =
+            __node_insert_unique_prepare(__hash, __src_ptr->__value_);
+        if (__ndptr == nullptr)
+        {
+            (void)__source.remove(__it++).release();
+            __src_ptr->__hash_ = __hash;
+            __node_insert_unique_perform(__src_ptr);
+        }
+        else
+            ++__it;
+    }
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _NodeHandle>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi(
+    _NodeHandle&& __nh)
+{
+    if (__nh.empty())
+        return end();
+    iterator __result = __node_insert_multi(__nh.__ptr_);
+    __nh.__release();
+    return __result;
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _NodeHandle>
+typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi(
+    const_iterator __hint, _NodeHandle&& __nh)
+{
+    if (__nh.empty())
+        return end();
+
+    iterator __result = __node_insert_multi(__hint, __nh.__ptr_);
+    __nh.__release();
+    return __result;
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _NodeHandle>
+_NodeHandle
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract_multi(
+    key_type const& __key)
+{
+    iterator __it = find(__key);
+    if (__it == end())
+        return _NodeHandle();
+    return __node_handle_extract_multi<_NodeHandle>(__it);
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _NodeHandle>
+_NodeHandle
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract_multi(const_iterator __it)
+{
+    allocator_type __alloc(__node_alloc());
+    return _NodeHandle(remove(__it).release(), __alloc);
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+template <class _Table>
+void
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_merge_multi(
+    _Table& __source)
+{
+    static_assert(is_same<typename _Table::__node, __node>::value, "");
+
+    for (typename _Table::iterator __it = __source.begin();
+         __it != __source.end();)
+    {
+        __node_pointer __src_ptr = __it.__node_->__upcast();
+        size_t __src_hash = hash_function()(__src_ptr->__value_);
+        __next_pointer __pn =
+            __node_insert_multi_prepare(__src_hash, __src_ptr->__value_);
+        (void)__source.remove(__it++).release();
+        __src_ptr->__hash_ = __src_hash;
+        __node_insert_multi_perform(__src_ptr, __pn);
+    }
+}
+#endif  // _LIBCPP_STD_VER > 14
+
 template <class _Tp, class _Hash, class _Equal, class _Alloc>
 void
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::rehash(size_type __n)
 {
     if (__n == 1)
         __n = 2;
     else if (__n & (__n - 1))
         __n = __next_prime(__n);

libcxx/include/__node_handle

+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___NODE_HANDLE
+#define _LIBCPP___NODE_HANDLE
+
+#include <__config>
+#include <memory>
+#include <optional>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+#if _LIBCPP_STD_VER > 14
+
+#define __cpp_lib_node_extract 201606L
+
+// Specialized in __tree & __hash_table for their _NodeType.
+template <class _NodeType, class _Alloc>
+struct __generic_container_node_destructor;
+
+template <class _NodeType, class _Alloc>
+class __node_handle_base
+{
+    typedef allocator_traits<_Alloc> __alloc_traits;
+    typedef typename __rebind_pointer<typename __alloc_traits::void_pointer,
+                                      _NodeType>::type
+        __node_pointer_type;
+
+public:
+    typedef _Alloc allocator_type;
+    typedef typename _NodeType::__node_value_type value_type;
+
+    __node_pointer_type __ptr_ = nullptr;
+    optional<allocator_type> __alloc_;
+
+    _LIBCPP_INLINE_VISIBILITY
+    void __release()
+    {
+        __ptr_ = nullptr;
+        __alloc_ = _VSTD::nullopt;
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    void __destroy_node_pointer()
+    {
+        if (__ptr_ != nullptr)
+        {
+            typedef typename __allocator_traits_rebind<
+                allocator_type, _NodeType>::type __node_alloc_type;
+            __node_alloc_type __alloc(*__alloc_);
+            __generic_container_node_destructor<_NodeType, __node_alloc_type>(
+                __alloc, true)(__ptr_);
+            __ptr_ = nullptr;
+        }
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    __node_handle_base() = default;
+
+    _LIBCPP_INLINE_VISIBILITY
+    __node_handle_base(__node_pointer_type __ptr, allocator_type const& __alloc)
+            : __ptr_(__ptr), __alloc_(__alloc)
+    {
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    __node_handle_base(__node_handle_base&& __other) noexcept
+            : __ptr_(_VSTD::move(__other.__ptr_)),
+              __alloc_(_VSTD::move(__other.__alloc_))
+    {
+        __other.__ptr_ = nullptr;
+        __other.__alloc_ = _VSTD::nullopt;
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    __node_handle_base& operator=(__node_handle_base&& __other)
+    {
+        _LIBCPP_ASSERT(__alloc_ == _VSTD::nullopt ||
+                       __alloc_traits::propagate_on_container_move_assignment::value ||
+                       __alloc_ == __other.__alloc_,
+                       "");
+
+        __destroy_node_pointer();
+        __ptr_ = __other.__ptr_;
+
+        if (__alloc_traits::propagate_on_container_move_assignment::value ||
+            __alloc_ == _VSTD::nullopt)
+            __alloc_ = _VSTD::move(__other.__alloc_);
+
+        __other.__ptr_ = nullptr;
+        __other.__alloc_ = _VSTD::nullopt;
+
+        return *this;
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    allocator_type get_allocator() const { return *__alloc_; }
+
+    _LIBCPP_INLINE_VISIBILITY
+    explicit operator bool() const { return __ptr_ != nullptr; }
+
+    _LIBCPP_INLINE_VISIBILITY
+    bool empty() const { return __ptr_ == nullptr; }
+
+    _LIBCPP_INLINE_VISIBILITY
+    void swap(__node_handle_base& __other) noexcept(
+        __alloc_traits::propagate_on_container_swap::value ||
+        __alloc_traits::is_always_equal::value)
+    {
+        using _VSTD::swap;
+        swap(__ptr_, __other.__ptr_);
+        if (__alloc_traits::propagate_on_container_swap::value ||
+            __alloc_ == _VSTD::nullopt || __other.__alloc_ == _VSTD::nullopt)
+            swap(__alloc_, __other.__alloc_);
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    ~__node_handle_base()
+    {
+        __destroy_node_pointer();
+    }
+};
+
+template <class _NodeType, class _Alloc>
+class _LIBCPP_TEMPLATE_VIS __set_node_handle
+    : public __node_handle_base<_NodeType, _Alloc>
+{
+    template <class _Tp, class _Compare, class _Allocator>
+        friend class __tree;
+    template <class _Tp, class _Hash, class _Equal, class _Allocator>
+        friend class __hash_table;
+
+    typedef __node_handle_base<_NodeType, _Alloc> __base;
+    using __base::__node_handle_base;
+
+public:
+    typedef typename _NodeType::__node_value_type value_type;
+
+    _LIBCPP_INLINE_VISIBILITY
+    __set_node_handle() = default;
+
+    _LIBCPP_INLINE_VISIBILITY
+    __set_node_handle(__set_node_handle&& __other) noexcept = default;
+
+    _LIBCPP_INLINE_VISIBILITY
+    __set_node_handle& operator=(__set_node_handle&& __other) = default;
+
+    _LIBCPP_INLINE_VISIBILITY
+    value_type& value() const
+    {
+        return this->__ptr_->__value_;
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    friend void swap(__set_node_handle& __a, __set_node_handle& __b)
+        noexcept(noexcept(__a.swap(__b))) { __a.swap(__b); }
+
+    _LIBCPP_INLINE_VISIBILITY ~__set_node_handle() = default;
+};
+
+template <class _NodeType, class _Alloc>
+class _LIBCPP_TEMPLATE_VIS __map_node_handle
+    : public __node_handle_base<_NodeType, _Alloc>
+{
+    template <class _Tp, class _Compare, class _Allocator>
+        friend class __tree;
+    template <class _Tp, class _Hash, class _Equal, class _Allocator>
+        friend class __hash_table;
+
+    typedef __node_handle_base<_NodeType, _Alloc> __base;
+    using __base::__node_handle_base;
+
+public:
+    typedef typename _NodeType::__node_value_type::key_type key_type;
+    typedef typename _NodeType::__node_value_type::mapped_type mapped_type;
+
+    _LIBCPP_INLINE_VISIBILITY
+    __map_node_handle() = default;
+
+    _LIBCPP_INLINE_VISIBILITY
+    __map_node_handle(__map_node_handle&& __other) noexcept = default;
+
+    _LIBCPP_INLINE_VISIBILITY
+    __map_node_handle& operator=(__map_node_handle&& __other) = default;
+
+    _LIBCPP_INLINE_VISIBILITY
+    key_type& key() const
+    {
+        return this->__ptr_->__value_.__nc.first;
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    mapped_type& mapped() const
+    {
+        return this->__ptr_->__value_.__nc.second;
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    friend void swap(__map_node_handle& __a, __map_node_handle& __b)
+        noexcept(noexcept(__a.swap(__b))) { __a.swap(__b); }
+
+    _LIBCPP_INLINE_VISIBILITY ~__map_node_handle() = default;
+};
+
+template <class _Iterator, class _NodeType>
+struct __insert_return_type
+{
+    _Iterator position;
+    bool inserted;
+    _NodeType node;
+};
+
+#endif // _LIBCPP_STD_VER > 14
+
+_LIBCPP_END_NAMESPACE_STD
+_LIBCPP_POP_MACROS
+
+#endif

libcxx/include/__tree

             __alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__value_));
         if (__p)
             __alloc_traits::deallocate(__na_, __p, 1);
     }
 
     template <class> friend class __map_node_destructor;
 };
 
+#if _LIBCPP_STD_VER > 14
+template <class _NodeType, class _Alloc>
+struct __generic_container_node_destructor;
+template <class _Tp, class _VoidPtr, class _Alloc>
+struct __generic_container_node_destructor<__tree_node<_Tp, _VoidPtr>, _Alloc>
+    : __tree_node_destructor<_Alloc>
+{
+    using __tree_node_destructor<_Alloc>::__tree_node_destructor;
+};
+#endif
 
 template <class _Tp, class _NodePtr, class _DiffType>
 class _LIBCPP_TEMPLATE_VIS __tree_iterator
 {
     typedef __tree_node_types<_NodePtr>                     _NodeTypes;
     typedef _NodePtr                                        __node_pointer;
     typedef typename _NodeTypes::__node_base_pointer        __node_base_pointer;
     typedef typename _NodeTypes::__end_node_pointer         __end_node_pointer;

 
     pair<iterator, bool> __node_insert_unique(__node_pointer __nd);
     iterator             __node_insert_unique(const_iterator __p,
                                               __node_pointer __nd);
 
     iterator __node_insert_multi(__node_pointer __nd);
     iterator __node_insert_multi(const_iterator __p, __node_pointer __nd);
 
+
+    _LIBCPP_INLINE_VISIBILITY iterator __remove_node_pointer(__node_pointer);
+
+#if _LIBCPP_STD_VER > 14
+    template <class _NodeHandle, class _InsertReturnType>
+    _LIBCPP_INLINE_VISIBILITY
+    _InsertReturnType __node_handle_insert_unique(_NodeHandle&&);
+    template <class _NodeHandle>
+    _LIBCPP_INLINE_VISIBILITY
+    iterator __node_handle_insert_unique(const_iterator, _NodeHandle&&);
+    template <class _NodeHandle>
+    _LIBCPP_INLINE_VISIBILITY
+    _NodeHandle __node_handle_extract_unique(key_type const&);
+    template <class _NodeHandle>
+    _LIBCPP_INLINE_VISIBILITY
+    _NodeHandle __node_handle_extract_unique(const_iterator);
+    template <class _Tree>
+    _LIBCPP_INLINE_VISIBILITY
+    void __node_handle_merge_unique(_Tree& __source);
+
+    template <class _NodeHandle>
+    _LIBCPP_INLINE_VISIBILITY
+    iterator __node_handle_insert_multi(_NodeHandle&&);
+    template <class _NodeHandle>
+    _LIBCPP_INLINE_VISIBILITY
+    iterator __node_handle_insert_multi(const_iterator, _NodeHandle&&);
+    template <class _NodeHandle>
+    _LIBCPP_INLINE_VISIBILITY
+    _NodeHandle __node_handle_extract_multi(key_type const&);
+    template <class _NodeHandle>
+    _NodeHandle __node_handle_extract_multi(const_iterator);
+    template <class _Tree>
+    _LIBCPP_INLINE_VISIBILITY
+    void __node_handle_merge_multi(_Tree& __source);
+#endif
+
     iterator erase(const_iterator __p);
     iterator erase(const_iterator __f, const_iterator __l);
     template <class _Key>
         size_type __erase_unique(const _Key& __k);
     template <class _Key>
         size_type __erase_multi(const _Key& __k);
 
     void __insert_node_at(__parent_pointer     __parent,

     __parent_pointer __parent;
     __node_base_pointer& __child = __find_leaf(__p, __parent, _NodeTypes::__get_key(__nd->__value_));
     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd));
     return iterator(__nd);
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 typename __tree<_Tp, _Compare, _Allocator>::iterator
-__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p)
+__tree<_Tp, _Compare, _Allocator>::__remove_node_pointer(__node_pointer __ptr)
 {
-    __node_pointer __np = __p.__get_np();
-    iterator __r(__p.__ptr_);
+    iterator __r(__ptr);
     ++__r;
-    if (__begin_node() == __p.__ptr_)
+    if (__begin_node() == __ptr)
         __begin_node() = __r.__ptr_;
     --size();
-    __node_allocator& __na = __node_alloc();
     __tree_remove(__end_node()->__left_,
-                  static_cast<__node_base_pointer>(__np));
+                  static_cast<__node_base_pointer>(__ptr));
+    return __r;
+}
+
+#if _LIBCPP_STD_VER > 14
+template <class _Tp, class _Compare, class _Allocator>
+template <class _NodeHandle, class _InsertReturnType>
+_InsertReturnType
+__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_unique(
+    _NodeHandle&& __nh)
+{
+    if (__nh.empty())
+        return _InsertReturnType{end(), false, _NodeHandle()};
+
+    __parent_pointer __parent;
+    __node_base_pointer& __child = __find_equal(__parent,
+                                                __nh.__ptr_->__value_);
+    if (__child != nullptr)
+        return _InsertReturnType{
+            iterator(static_cast<__node_pointer>(__child)),
+            false, _VSTD::move(__nh)};
+
+    __node_pointer __ptr = __nh.__ptr_;
+    __insert_node_at(__parent, __child,
+                     static_cast<__node_base_pointer>(__ptr));
+    __nh.__release();
+    return _InsertReturnType{iterator(__ptr), true, _NodeHandle()};
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+template <class _NodeHandle>
+typename __tree<_Tp, _Compare, _Allocator>::iterator
+__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_unique(
+    const_iterator __hint, _NodeHandle&& __nh)
+{
+    if (__nh.empty())
+        return end();
+
+    __parent_pointer __parent;
+    __node_base_pointer __dummy;
+    __node_base_pointer& __child = __find_equal(__hint, __parent, __dummy,
+                                                __nh.__ptr_->__value_);
+    __node_pointer __r = static_cast<__node_pointer>(__child);
+    if (__child == nullptr)
+    {
+        __insert_node_at(__parent, __child,
+                         static_cast<__node_base_pointer>(__nh.__ptr_));
+        __r = __nh.__ptr_;
+        __nh.__release();
+    }
+    return iterator(__r);
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+template <class _NodeHandle>
+_NodeHandle
+__tree<_Tp, _Compare, _Allocator>::__node_handle_extract_unique(key_type const& __key)
+{
+    iterator __it = find(__key);
+    if (__it == end())
+        return _NodeHandle();
+    return __node_handle_extract_unique<_NodeHandle>(__it);
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+template <class _NodeHandle>
+_NodeHandle
+__tree<_Tp, _Compare, _Allocator>::__node_handle_extract_unique(const_iterator __p)
+{
+    __node_pointer __np = __p.__get_np();
+    __remove_node_pointer(__np);
+    __np->__left_ = nullptr;
+    __np->__right_ = nullptr;
+    return _NodeHandle(__np, __alloc());
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+template <class _Tree>
+void
+__tree<_Tp, _Compare, _Allocator>::__node_handle_merge_unique(_Tree& __source)
+{
+    static_assert(is_same<typename _Tree::__node_pointer, __node_pointer>::value, "");
+
+    for (typename _Tree::iterator __i = __source.begin();
+         __i != __source.end();)
+    {
+        __node_pointer __src_ptr = __i.__get_np();
+
+        __parent_pointer __parent;
+        __node_base_pointer& __child = __find_equal(
+            __parent, _NodeTypes::__get_key(__src_ptr->__value_));
+
+        ++__i;
+
+        if (__child != nullptr)
+            continue;
+
+        __source.__remove_node_pointer(__src_ptr);
+        __src_ptr->__left_ = nullptr;
+        __src_ptr->__right_ = nullptr;
+        __insert_node_at(__parent, __child,
+                         static_cast<__node_base_pointer>(__src_ptr));
+    }
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+template <class _NodeHandle>
+typename __tree<_Tp, _Compare, _Allocator>::iterator
+__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi(_NodeHandle&& __nh)
+{
+    if (__nh.empty())
+        return end();
+
+    __parent_pointer __parent;
+    __node_base_pointer& __child = __find_leaf_high(
+        __parent, _NodeTypes::__get_key(__nh.__ptr_->__value_));
+    __node_pointer __ptr = __nh.__ptr_;
+    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr));
+    __nh.__release();
+    return iterator(__ptr);
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+template <class _NodeHandle>
+typename __tree<_Tp, _Compare, _Allocator>::iterator
+__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi(
+    const_iterator __hint, _NodeHandle&& __nh)
+{
+    if (__nh.empty())
+        return end();
+
+    __parent_pointer __parent;
+    __node_pointer __ptr = __nh.__ptr_;
+    __node_base_pointer& __child = __find_leaf(__hint, __parent,
+                                               _NodeTypes::__get_key(__ptr->__value_));
+    __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr));
+    __nh.__release();
+    return iterator(__ptr);
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+template <class _NodeHandle>
+_NodeHandle
+__tree<_Tp, _Compare, _Allocator>::__node_handle_extract_multi(key_type const& __key)
+{
+    iterator __i = find(__key);
+    if (__i == end())
+        return _NodeHandle();
+    return __node_handle_extract_multi<_NodeHandle>(__i);
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+template <class _NodeHandle>
+_NodeHandle
+__tree<_Tp, _Compare, _Allocator>::__node_handle_extract_multi(const_iterator __p)
+{
+    __node_pointer __np = __p.__get_np();
+    __remove_node_pointer(__np);
+    return _NodeHandle(__np, __alloc());
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+template <class _Tree>
+void
+__tree<_Tp, _Compare, _Allocator>::__node_handle_merge_multi(_Tree& __source)
+{
+    static_assert(is_same<typename _Tree::__node_pointer, __node_pointer>::value, "");
+
+    for (typename _Tree::iterator __i = __source.begin();
+         __i != __source.end();)
+    {
+        __node_pointer __src_ptr = __i.__get_np();
+
+        __parent_pointer __parent;
+        __node_base_pointer& __child = __find_leaf_high(
+            __parent, _NodeTypes::__get_key(__src_ptr->__value_));
+
+        ++__i;
+
+        __source.__remove_node_pointer(__src_ptr);
+        __insert_node_at(__parent, __child,
+                         static_cast<__node_base_pointer>(__src_ptr));
+    }
+}
+
+#endif  // _LIBCPP_STD_VER > 14
+
+template <class _Tp, class _Compare, class _Allocator>
+typename __tree<_Tp, _Compare, _Allocator>::iterator
+__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p)
+{
+    __node_pointer __np = __p.__get_np();
+    iterator __r = __remove_node_pointer(__np);
+    __node_allocator& __na = __node_alloc();
     __node_traits::destroy(__na, _NodeTypes::__get_ptr(
         const_cast<__node_value_type&>(*__p)));
     __node_traits::deallocate(__na, __np, 1);
     return __r;
 }
 
 template <class _Tp, class _Compare, class _Allocator>
 typename __tree<_Tp, _Compare, _Allocator>::iterator

libcxx/include/map

public:
     typedef typename allocator_type::const_pointer   const_pointer;
     typedef typename allocator_type::size_type       size_type;
     typedef typename allocator_type::difference_type difference_type;
 
     typedef implementation-defined                   iterator;
     typedef implementation-defined                   const_iterator;
     typedef std::reverse_iterator<iterator>          reverse_iterator;
     typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;
 
     class value_compare
         : public binary_function<value_type, value_type, bool>
     {
         friend class map;
     protected:
         key_compare comp;
 
         value_compare(key_compare c);
swap(multimap<Key, T, Compare, Allocator>& x,
     noexcept(noexcept(x.swap(y)));
 
 }  // std
 
 */
 
 #include <__config>
 #include <__tree>
+#include <__node_handle>
 #include <iterator>
 #include <memory>
 #include <utility>
 #include <functional>
 #include <initializer_list>
 #include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
public:
     typedef typename __alloc_traits::const_pointer         const_pointer;
     typedef typename __alloc_traits::size_type             size_type;
     typedef typename __alloc_traits::difference_type       difference_type;
     typedef __map_iterator<typename __base::iterator>             iterator;
     typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
     typedef _VSTD::reverse_iterator<iterator>               reverse_iterator;
     typedef _VSTD::reverse_iterator<const_iterator>         const_reverse_iterator;
 
+#if _LIBCPP_STD_VER > 14
+    typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
+    typedef __insert_return_type<iterator, node_type> insert_return_type;
+#endif
+
+    __base& __get_tree() { return __tree_; }
+
     _LIBCPP_INLINE_VISIBILITY
     map()
         _NOEXCEPT_(
             is_nothrow_default_constructible<allocator_type>::value &&
             is_nothrow_default_constructible<key_compare>::value &&
             is_nothrow_copy_constructible<key_compare>::value)
         : __tree_(__vc(key_compare())) {}
 
#endif // _LIBCPP_STD_VER > 14
     size_type erase(const key_type& __k)
         {return __tree_.__erase_unique(__k);}
     _LIBCPP_INLINE_VISIBILITY
     iterator  erase(const_iterator __f, const_iterator __l)
         {return __tree_.erase(__f.__i_, __l.__i_);}
     _LIBCPP_INLINE_VISIBILITY
     void clear() _NOEXCEPT {__tree_.clear();}
 
+#if _LIBCPP_STD_VER > 14
+    _LIBCPP_INLINE_VISIBILITY
+    insert_return_type insert(node_type&& __nh)
+    {
+        return __tree_.template __node_handle_insert_unique<
+            node_type, insert_return_type>(_VSTD::move(__nh));
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    iterator insert(const_iterator __hint, node_type&& __nh)
+    {
+        return __tree_.template __node_handle_insert_unique<node_type>(
+            __hint.__i_, _VSTD::move(__nh));
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    node_type extract(key_type const& __key)
+    {
+        return __tree_.template __node_handle_extract_unique<node_type>(__key);
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    node_type extract(const_iterator __it)
+    {
+        return __tree_.template __node_handle_extract_unique<node_type>(__it.__i_);
+    }
+    template <class _C2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(map<key_type, mapped_type, _C2, allocator_type>& __source)
+    {
+        __tree_.__node_handle_merge_unique(__source.__get_tree());
+    }
+    template <class _C2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(map<key_type, mapped_type, _C2, allocator_type>&& __source)
+    {
+        __tree_.__node_handle_merge_unique(__source.__get_tree());
+    }
+    template <class _C2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(multimap<key_type, mapped_type, _C2, allocator_type>& __source)
+    {
+        __tree_.__node_handle_merge_unique(__source.__get_tree());
+    }
+    template <class _C2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(multimap<key_type, mapped_type, _C2, allocator_type>&& __source)
+    {
+        __tree_.__node_handle_merge_unique(__source.__get_tree());
+    }
+#endif
+
     _LIBCPP_INLINE_VISIBILITY
     void swap(map& __m)
         _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
         {__tree_.swap(__m.__tree_);}
 
     _LIBCPP_INLINE_VISIBILITY
     iterator find(const key_type& __k)             {return __tree_.find(__k);}
     _LIBCPP_INLINE_VISIBILITY
public:
     typedef typename __alloc_traits::const_pointer         const_pointer;
     typedef typename __alloc_traits::size_type             size_type;
     typedef typename __alloc_traits::difference_type       difference_type;
     typedef __map_iterator<typename __base::iterator>      iterator;
     typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
     typedef _VSTD::reverse_iterator<iterator>               reverse_iterator;
     typedef _VSTD::reverse_iterator<const_iterator>         const_reverse_iterator;
 
+#if _LIBCPP_STD_VER > 14
+    typedef __map_node_handle<typename __base::__node, allocator_type> node_type;
+#endif
+
+    __base& __get_tree() { return __tree_; }
+
     _LIBCPP_INLINE_VISIBILITY
     multimap()
         _NOEXCEPT_(
             is_nothrow_default_constructible<allocator_type>::value &&
             is_nothrow_default_constructible<key_compare>::value &&
             is_nothrow_copy_constructible<key_compare>::value)
         : __tree_(__vc(key_compare())) {}
 
#endif  // _LIBCPP_CXX03_LANG
     iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
     _LIBCPP_INLINE_VISIBILITY
     iterator erase(iterator __p)       {return __tree_.erase(__p.__i_);}
     _LIBCPP_INLINE_VISIBILITY
     size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
     _LIBCPP_INLINE_VISIBILITY
     iterator  erase(const_iterator __f, const_iterator __l)
         {return __tree_.erase(__f.__i_, __l.__i_);}
+
+#if _LIBCPP_STD_VER > 14
+    _LIBCPP_INLINE_VISIBILITY
+    iterator insert(node_type&& __nh)
+    {
+        return __tree_.template __node_handle_insert_multi<node_type>(
+            _VSTD::move(__nh));
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    iterator insert(const_iterator __hint, node_type&& __nh)
+    {
+        return __tree_.template __node_handle_insert_multi<node_type>(
+            __hint.__i_, _VSTD::move(__nh));
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    node_type extract(key_type const& __key)
+    {
+        return __tree_.template __node_handle_extract_multi<node_type>(__key);
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    node_type extract(const_iterator __it)
+    {
+        return __tree_.template __node_handle_extract_multi<node_type>(
+            __it.__i_);
+    }
+    template <class _C2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(multimap<key_type, mapped_type, _C2, allocator_type>& __source)
+    {
+        return __tree_.__node_handle_merge_multi(__source.__get_tree());
+    }
+    template <class _C2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(multimap<key_type, mapped_type, _C2, allocator_type>&& __source)
+    {
+        return __tree_.__node_handle_merge_multi(__source.__get_tree());
+    }
+    template <class _C2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(map<key_type, mapped_type, _C2, allocator_type>& __source)
+    {
+        return __tree_.__node_handle_merge_multi(__source.__get_tree());
+    }
+    template <class _C2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(map<key_type, mapped_type, _C2, allocator_type>&& __source)
+    {
+        return __tree_.__node_handle_merge_multi(__source.__get_tree());
+    }
+#endif
+
     _LIBCPP_INLINE_VISIBILITY
     void clear() {__tree_.clear();}
 
     _LIBCPP_INLINE_VISIBILITY
     void swap(multimap& __m)
         _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
         {__tree_.swap(__m.__tree_);}
 

libcxx/include/set

swap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y)
     noexcept(noexcept(x.swap(y)));
 
 }  // std
 
 */
 
 #include <__config>
 #include <__tree>
+#include <__node_handle>
 #include <functional>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
+template <class _Key, class _Compare, class _Allocator>
+class multiset;
+
 template <class _Key, class _Compare = less<_Key>,
           class _Allocator = allocator<_Key> >
 class _LIBCPP_TEMPLATE_VIS set
 {
 public:
     // types:
     typedef _Key                                     key_type;
     typedef key_type                                 value_type;
public:
     typedef typename __base::const_pointer         const_pointer;
     typedef typename __base::size_type             size_type;
     typedef typename __base::difference_type       difference_type;
     typedef typename __base::const_iterator        iterator;
     typedef typename __base::const_iterator        const_iterator;
     typedef _VSTD::reverse_iterator<iterator>       reverse_iterator;
     typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
 
+#if _LIBCPP_STD_VER > 14
+    typedef __set_node_handle<typename __base::__node, allocator_type> node_type;
+    typedef __insert_return_type<iterator, node_type> insert_return_type;
+#endif
+
+    __base& __get_tree() { return __tree_; }
+
     _LIBCPP_INLINE_VISIBILITY
     set()
         _NOEXCEPT_(
             is_nothrow_default_constructible<allocator_type>::value &&
             is_nothrow_default_constructible<key_compare>::value &&
             is_nothrow_copy_constructible<key_compare>::value)
         : __tree_(value_compare()) {}
 
#endif  // _LIBCPP_CXX03_LANG
     size_type erase(const key_type& __k)
         {return __tree_.__erase_unique(__k);}
     _LIBCPP_INLINE_VISIBILITY
     iterator  erase(const_iterator __f, const_iterator __l)
         {return __tree_.erase(__f, __l);}
     _LIBCPP_INLINE_VISIBILITY
     void clear() _NOEXCEPT {__tree_.clear();}
 
+#if _LIBCPP_STD_VER > 14
+    _LIBCPP_INLINE_VISIBILITY
+    insert_return_type insert(node_type&& __nh)
+    {
+        return __tree_.template __node_handle_insert_unique<
+            node_type, insert_return_type>(_VSTD::move(__nh));
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    iterator insert(const_iterator __hint, node_type&& __nh)
+    {
+        return __tree_.template __node_handle_insert_unique<node_type>(
+            __hint, _VSTD::move(__nh));
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    node_type extract(key_type const& __key)
+    {
+        return __tree_.template __node_handle_extract_unique<node_type>(__key);
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    node_type extract(const_iterator __it)
+    {
+        return __tree_.template __node_handle_extract_unique<node_type>(__it);
+    }
+    template <class _C2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(set<key_type, _C2, allocator_type>& __source)
+    {
+        __tree_.__node_handle_merge_unique(__source.__get_tree());
+    }
+    template <class _C2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(set<key_type, _C2, allocator_type>&& __source)
+    {
+        __tree_.__node_handle_merge_unique(__source.__get_tree());
+    }
+    template <class _C2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(multiset<key_type, _C2, allocator_type>& __source)
+    {
+        __tree_.__node_handle_merge_unique(__source.__get_tree());
+    }
+    template <class _C2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(multiset<key_type, _C2, allocator_type>&& __source)
+    {
+        __tree_.__node_handle_merge_unique(__source.__get_tree());
+    }
+#endif
+
     _LIBCPP_INLINE_VISIBILITY
     void swap(set& __s) _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
         {__tree_.swap(__s.__tree_);}
 
     _LIBCPP_INLINE_VISIBILITY
     allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
     _LIBCPP_INLINE_VISIBILITY
     key_compare    key_comp()      const {return __tree_.value_comp();}
public:
     typedef typename __base::const_pointer         const_pointer;
     typedef typename __base::size_type             size_type;
     typedef typename __base::difference_type       difference_type;
     typedef typename __base::const_iterator        iterator;
     typedef typename __base::const_iterator        const_iterator;
     typedef _VSTD::reverse_iterator<iterator>       reverse_iterator;
     typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
 
+#if _LIBCPP_STD_VER > 14
+    typedef __set_node_handle<typename __base::__node, allocator_type> node_type;
+#endif
+
+    __base& __get_tree() { return __tree_; }
+
     // construct/copy/destroy:
     _LIBCPP_INLINE_VISIBILITY
     multiset()
         _NOEXCEPT_(
             is_nothrow_default_constructible<allocator_type>::value &&
             is_nothrow_default_constructible<key_compare>::value &&
             is_nothrow_copy_constructible<key_compare>::value)
         : __tree_(value_compare()) {}
#endif  // _LIBCPP_CXX03_LANG
     _LIBCPP_INLINE_VISIBILITY
     size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
     _LIBCPP_INLINE_VISIBILITY
     iterator  erase(const_iterator __f, const_iterator __l)
         {return __tree_.erase(__f, __l);}
     _LIBCPP_INLINE_VISIBILITY
     void clear() _NOEXCEPT {__tree_.clear();}
 
+#if _LIBCPP_STD_VER > 14
+    _LIBCPP_INLINE_VISIBILITY
+    iterator insert(node_type&& __nh)
+    {
+        return __tree_.template __node_handle_insert_multi<node_type>(
+            _VSTD::move(__nh));
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    iterator insert(const_iterator __hint, node_type&& __nh)
+    {
+        return __tree_.template __node_handle_insert_multi<node_type>(
+            __hint, _VSTD::move(__nh));
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    node_type extract(key_type const& __key)
+    {
+        return __tree_.template __node_handle_extract_multi<node_type>(__key);
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    node_type extract(const_iterator __it)
+    {
+        return __tree_.template __node_handle_extract_multi<node_type>(__it);
+    }
+    template <class _C2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(multiset<key_type, _C2, allocator_type>& __source)
+    {
+        __tree_.__node_handle_merge_multi(__source.__get_tree());
+    }
+    template <class _C2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(multiset<key_type, _C2, allocator_type>&& __source)
+    {
+        __tree_.__node_handle_merge_multi(__source.__get_tree());
+    }
+    template <class _C2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(set<key_type, _C2, allocator_type>& __source)
+    {
+        __tree_.__node_handle_merge_multi(__source.__get_tree());
+    }
+    template <class _C2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(set<key_type, _C2, allocator_type>&& __source)
+    {
+        __tree_.__node_handle_merge_multi(__source.__get_tree());
+    }
+#endif
+
     _LIBCPP_INLINE_VISIBILITY
     void swap(multiset& __s)
         _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
         {__tree_.swap(__s.__tree_);}
 
     _LIBCPP_INLINE_VISIBILITY
     allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
     _LIBCPP_INLINE_VISIBILITY

libcxx/include/unordered_map

operator!=(const unordered_multimap<Key, T, Hash, Pred, Alloc>& x,
                const unordered_multimap<Key, T, Hash, Pred, Alloc>& y);
 
 }  // std
 
 */
 
 #include <__config>
 #include <__hash_table>
+#include <__node_handle>
 #include <functional>
 #include <stdexcept>
 #include <tuple>
 
 #include <__debug>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
+template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
+class unordered_multimap;
+
 template <class _Key, class _Cp, class _Hash, bool _IsEmpty>
 class __unordered_map_hasher
     : private _Hash
 {
 public:
     _LIBCPP_INLINE_VISIBILITY
     __unordered_map_hasher()
         _NOEXCEPT_(is_nothrow_default_constructible<_Hash>::value)
public:
     typedef typename __table::size_type              size_type;
     typedef typename __table::difference_type        difference_type;
 
     typedef __hash_map_iterator<typename __table::iterator>       iterator;
     typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
     typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
     typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
 
+#if _LIBCPP_STD_VER > 14
+    typedef __map_node_handle<__node, allocator_type> node_type;
+    typedef __insert_return_type<iterator, node_type> insert_return_type;
+#endif
+
+    __table& __get_table() { return __table_; }
+
     _LIBCPP_INLINE_VISIBILITY
     unordered_map()
         _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
         {
 #if _LIBCPP_DEBUG_LEVEL >= 2
             __get_db()->__insert_c(this);
 #endif
         }
#endif // _LIBCPP_STD_VER > 14
     _LIBCPP_INLINE_VISIBILITY
     iterator erase(iterator __p)       {return __table_.erase(__p.__i_);}
     _LIBCPP_INLINE_VISIBILITY
     size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
     _LIBCPP_INLINE_VISIBILITY
     iterator erase(const_iterator __first, const_iterator __last)
         {return __table_.erase(__first.__i_, __last.__i_);}
     _LIBCPP_INLINE_VISIBILITY
         void clear() _NOEXCEPT {__table_.clear();}
 
+#if _LIBCPP_STD_VER > 14
+    _LIBCPP_INLINE_VISIBILITY
+    insert_return_type insert(node_type&& __nh)
+    {
+        return __table_.template __node_handle_insert_unique<
+            node_type, insert_return_type>(_VSTD::move(__nh));
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    iterator insert(const_iterator __hint, node_type&& __nh)
+    {
+        return __table_.template __node_handle_insert_unique<node_type>(
+            __hint.__i_, _VSTD::move(__nh));
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    node_type extract(key_type const& __key)
+    {
+        return __table_.template __node_handle_extract_unique<node_type>(__key);
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    node_type extract(const_iterator __it)
+    {
+        return __table_.template __node_handle_extract_unique<node_type>(
+            __it.__i_);
+    }
+
+    template <class _H2, class _P2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& __src)
+    {
+        return __table_.__node_handle_merge_unique(__src.__get_table());
+    }
+    template <class _H2, class _P2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& __src)
+    {
+        return __table_.__node_handle_merge_unique(__src.__get_table());
+    }
+    template <class _H2, class _P2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& __src)
+    {
+        return __table_.__node_handle_merge_unique(__src.__get_table());
+    }
+    template <class _H2, class _P2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& __src)
+    {
+        return __table_.__node_handle_merge_unique(__src.__get_table());
+    }
+#endif
+
     _LIBCPP_INLINE_VISIBILITY
     void swap(unordered_map& __u)
         _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
         { __table_.swap(__u.__table_);}
 
     _LIBCPP_INLINE_VISIBILITY
     hasher hash_function() const
         {return __table_.hash_function().hash_function();}
public:
     typedef typename __table::size_type              size_type;
     typedef typename __table::difference_type        difference_type;
 
     typedef __hash_map_iterator<typename __table::iterator>       iterator;
     typedef __hash_map_const_iterator<typename __table::const_iterator> const_iterator;
     typedef __hash_map_iterator<typename __table::local_iterator> local_iterator;
     typedef __hash_map_const_iterator<typename __table::const_local_iterator> const_local_iterator;
 
+#if _LIBCPP_STD_VER > 14
+    typedef __map_node_handle<__node, allocator_type> node_type;
+#endif
+
+    __table& __get_table() { return __table_; }
+
     _LIBCPP_INLINE_VISIBILITY
     unordered_multimap()
         _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
         {
 #if _LIBCPP_DEBUG_LEVEL >= 2
             __get_db()->__insert_c(this);
 #endif
         }
#endif  // _LIBCPP_CXX03_LANG
     _LIBCPP_INLINE_VISIBILITY
     size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
     _LIBCPP_INLINE_VISIBILITY
     iterator erase(const_iterator __first, const_iterator __last)
         {return __table_.erase(__first.__i_, __last.__i_);}
     _LIBCPP_INLINE_VISIBILITY
     void clear() _NOEXCEPT {__table_.clear();}
 
+#if _LIBCPP_STD_VER > 14
+    _LIBCPP_INLINE_VISIBILITY
+    iterator insert(node_type&& __nh)
+    {
+        return __table_.template __node_handle_insert_multi<node_type>(
+            _VSTD::move(__nh));
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    iterator insert(const_iterator __hint, node_type&& __nh)
+    {
+        return __table_.template __node_handle_insert_multi<node_type>(
+            __hint.__i_, _VSTD::move(__nh));
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    node_type extract(key_type const& __key)
+    {
+        return __table_.template __node_handle_extract_multi<node_type>(__key);
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    node_type extract(const_iterator __it)
+    {
+        return __table_.template __node_handle_extract_multi<node_type>(
+            __it.__i_);
+    }
+
+    template <class _H2, class _P2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& __src)
+    {
+        return __table_.__node_handle_merge_multi(__src.__get_table());
+    }
+    template <class _H2, class _P2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& __src)
+    {
+        return __table_.__node_handle_merge_multi(__src.__get_table());
+    }
+    template <class _H2, class _P2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& __src)
+    {
+        return __table_.__node_handle_merge_multi(__src.__get_table());
+    }
+    template <class _H2, class _P2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& __src)
+    {
+        return __table_.__node_handle_merge_multi(__src.__get_table());
+    }
+#endif
+
     _LIBCPP_INLINE_VISIBILITY
     void swap(unordered_multimap& __u)
         _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
         {__table_.swap(__u.__table_);}
 
     _LIBCPP_INLINE_VISIBILITY
     hasher hash_function() const
         {return __table_.hash_function().hash_function();}

libcxx/include/unordered_set

template <class Value, class Hash, class Pred, class Alloc>
     operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
                const unordered_multiset<Value, Hash, Pred, Alloc>& y);
 }  // std
 
 */
 
 #include <__config>
 #include <__hash_table>
+#include <__node_handle>
 #include <functional>
 
 #include <__debug>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
+template <class _Value, class _Hash, class _Pred, class _Alloc>
+class unordered_multiset;
+
 template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
           class _Alloc = allocator<_Value> >
 class _LIBCPP_TEMPLATE_VIS unordered_set
 {
 public:
     // types
     typedef _Value                                                     key_type;
     typedef key_type                                                   value_type;
public:
     typedef typename __table::size_type       size_type;
     typedef typename __table::difference_type difference_type;
 
     typedef typename __table::const_iterator       iterator;
     typedef typename __table::const_iterator       const_iterator;
     typedef typename __table::const_local_iterator local_iterator;
     typedef typename __table::const_local_iterator const_local_iterator;
 
+#if _LIBCPP_STD_VER > 14
+    typedef __set_node_handle<typename __table::__node, allocator_type> node_type;
+    typedef __insert_return_type<iterator, node_type> insert_return_type;
+#endif
+
+    __table& __get_table() { return __table_; }
+
     _LIBCPP_INLINE_VISIBILITY
     unordered_set()
         _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
         {
 #if _LIBCPP_DEBUG_LEVEL >= 2
             __get_db()->__insert_c(this);
 #endif
         }
#endif
     _LIBCPP_INLINE_VISIBILITY
     size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
     _LIBCPP_INLINE_VISIBILITY
     iterator erase(const_iterator __first, const_iterator __last)
         {return __table_.erase(__first, __last);}
     _LIBCPP_INLINE_VISIBILITY
     void clear() _NOEXCEPT {__table_.clear();}
 
+#if _LIBCPP_STD_VER > 14
+    _LIBCPP_INLINE_VISIBILITY
+    insert_return_type insert(node_type&& __nh)
+    {
+        return __table_.template __node_handle_insert_unique<
+            node_type, insert_return_type>(_VSTD::move(__nh));
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    iterator insert(const_iterator, node_type&& __nh)
+    {
+        return insert(_VSTD::move(__nh)).position;
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    node_type extract(key_type const& __key)
+    {
+        return __table_.template __node_handle_extract_unique<node_type>(__key);
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    node_type extract(const_iterator __it)
+    {
+        return __table_.template __node_handle_extract_unique<node_type>(__it);
+    }
+
+    template<class _H2, class _P2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source)
+    {
+        __table_.__node_handle_merge_unique(__source.__get_table());
+    }
+    template<class _H2, class _P2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source)
+    {
+        __table_.__node_handle_merge_unique(__source.__get_table());
+    }
+    template<class _H2, class _P2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source)
+    {
+        __table_.__node_handle_merge_unique(__source.__get_table());
+    }
+    template<class _H2, class _P2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source)
+    {
+        __table_.__node_handle_merge_unique(__source.__get_table());
+    }
+#endif
+
     _LIBCPP_INLINE_VISIBILITY
     void swap(unordered_set& __u)
         _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
         {__table_.swap(__u.__table_);}
 
     _LIBCPP_INLINE_VISIBILITY
     hasher hash_function() const {return __table_.hash_function();}
     _LIBCPP_INLINE_VISIBILITY
public:
     typedef typename __table::size_type       size_type;
     typedef typename __table::difference_type difference_type;
 
     typedef typename __table::const_iterator       iterator;
     typedef typename __table::const_iterator       const_iterator;
     typedef typename __table::const_local_iterator local_iterator;
     typedef typename __table::const_local_iterator const_local_iterator;
 
+#if _LIBCPP_STD_VER > 14
+    typedef __set_node_handle<typename __table::__node, allocator_type> node_type;
+#endif
+
+    __table& __get_table() { return __table_; }
+
     _LIBCPP_INLINE_VISIBILITY
     unordered_multiset()
         _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
         {
 #if _LIBCPP_DEBUG_LEVEL >= 2
             __get_db()->__insert_c(this);
 #endif
         }
#endif  // _LIBCPP_CXX03_LANG
     _LIBCPP_INLINE_VISIBILITY
     iterator insert(const_iterator __p, const value_type& __x)
         {return __table_.__insert_multi(__p, __x);}
 
     template <class _InputIterator>
         _LIBCPP_INLINE_VISIBILITY
         void insert(_InputIterator __first, _InputIterator __last);
 
+#if _LIBCPP_STD_VER > 14
+    _LIBCPP_INLINE_VISIBILITY
+    node_type extract(const_iterator __position)
+    {
+        return __table_.template __node_handle_extract_multi<node_type>(
+            __position);
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    node_type extract(key_type const& __key)
+    {
+        return __table_.template __node_handle_extract_multi<node_type>(__key);
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    iterator insert(node_type&& __nh)
+    {
+        return __table_.template __node_handle_insert_multi<node_type>(
+            _VSTD::move(__nh));
+    }
+    _LIBCPP_INLINE_VISIBILITY
+    iterator insert(const_iterator __hint, node_type&& __nh)
+    {
+        return __table_.template __node_handle_insert_multi<node_type>(
+            __hint, _VSTD::move(__nh));
+    }
+
+    template <class _H2, class _P2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>& __source)
+    {
+        return __table_.__node_handle_merge_multi(__source.__get_table());
+    }
+    template <class _H2, class _P2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(unordered_multiset<key_type, _H2, _P2, allocator_type>&& __source)
+    {
+        return __table_.__node_handle_merge_multi(__source.__get_table());
+    }
+    template <class _H2, class _P2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source)
+    {
+        return __table_.__node_handle_merge_multi(__source.__get_table());
+    }
+    template <class _H2, class _P2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(unordered_set<key_type, _H2, _P2, allocator_type>&& __source)
+    {
+        return __table_.__node_handle_merge_multi(__source.__get_table());
+    }
+#endif
+
     _LIBCPP_INLINE_VISIBILITY
     iterator erase(const_iterator __p) {return __table_.erase(__p);}
     _LIBCPP_INLINE_VISIBILITY
     size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
     _LIBCPP_INLINE_VISIBILITY
     iterator erase(const_iterator __first, const_iterator __last)
         {return __table_.erase(__first, __last);}
     _LIBCPP_INLINE_VISIBILITY

libcxx/test/std/containers/associative/map/map.modifiers/insert_extract.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <map>
+
+// class map
+
+#include <map>
+#include <type_traits>
+#include "min_allocator.h"
+#include "Counter.h"
+
+namespace test_irt
+{
+typedef std::map<int, int> int_map_type;
+using intIRT = int_map_type::insert_return_type;
+static_assert(std::is_move_constructible<intIRT>::value &&
+              std::is_move_assignable<intIRT>::value &&
+              std::is_default_constructible<intIRT>::value &&
+              std::is_destructible<intIRT>::value, "");
+
+typedef std::map<Counter<int>, Counter<int>, std::less<Counter<int>>,
+                 min_allocator<std::pair<const Counter<int>, Counter<int>>>> map_type;
+using minIRT = map_type::insert_return_type;
+
+static_assert(std::is_move_constructible<minIRT>::value &&
+              std::is_move_assignable<minIRT>::value &&
+              std::is_default_constructible<minIRT>::value &&
+              std::is_destructible<minIRT>::value, "");
+
+static void doit()
+{
+    {
+        intIRT a, b;
+        std::swap(a, b);
+
+        minIRT c, d;
+        std::swap(c, d);
+    }
+
+    {
+        map_type mp = {{0, 0}};
+        map_type::node_type nh = mp.extract(mp.begin());
+        map_type::insert_return_type irt = mp.insert(std::move(nh));
+        assert(irt.inserted);
+        assert(irt.position == mp.begin());
+        assert(irt.node.empty());
+    }
+
+    {
+        map_type mp = {{0, 0}};
+        map_type::node_type nh = mp.extract(mp.begin());
+        mp.insert({0, 0});
+        map_type::insert_return_type irt = mp.insert(std::move(nh));
+        assert(!irt.inserted);
+        assert(irt.position == mp.begin());
+        assert(!irt.node.empty());
+    }
+
+    {
+        map_type mp;
+        map_type::node_type nh;
+        map_type::insert_return_type irt = mp.insert(std::move(nh));
+        assert(!irt.inserted);
+        assert(irt.position == mp.end());
+        assert(irt.node.empty());
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_extract
+{
+using the_map = std::map<int, int>;
+
+static void doit()
+{
+    the_map s;
+    s.insert({1, 0});
+    s.insert({2, 0});
+    s.insert({3, 0});
+    assert(s.size() == 3);
+
+    the_map::node_type handle = s.extract(2);
+    assert(s.size() == 2);
+    the_map::iterator i = s.begin();
+    assert((*i).first == 1);
+    ++i;
+    assert((*i).first == 3);
+    ++i;
+    assert(i == s.end());
+}
+}
+
+namespace test_count_dtors
+{
+typedef std::map<Counter<int>, Counter<int>> map_type;
+
+static void doit()
+{
+    {
+        map_type dtc;
+        for (int i = 0; i != 10; ++i)
+            dtc.emplace(i, i + 10);
+
+        assert(Counter_base::gConstructed == 20);
+        assert(dtc.size() == 10);
+
+        map_type::node_type nh3 = dtc.extract(Counter<int>(3));
+        map_type::node_type nh0 = dtc.extract(Counter<int>(0));
+        map_type::node_type nh9 = dtc.extract(Counter<int>(9));
+
+        assert(static_cast<bool>(nh3) && static_cast<bool>(nh0) &&
+               static_cast<bool>(nh9));
+
+        assert(dtc.size() == 7);
+
+        dtc.insert(std::move(nh3));
+        assert(dtc.size() == 8);
+
+        assert(Counter_base::gConstructed == 20);
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_min_alloc
+{
+typedef std::map<int, int, std::less<int>, min_allocator<std::pair<const int, int>>> map_type;
+
+static void doit()
+{
+    map_type mp;
+    mp.insert({10, 10});
+    map_type::node_type nt = mp.extract(10);
+    assert(!nt.empty());
+    assert(mp.empty());
+    mp.insert(std::move(nt));
+    assert(mp.size() == 1);
+}
+}
+
+namespace test_handle_operations
+{
+typedef std::map<int, Counter<int>, std::less<Counter<int>>, min_allocator<std::pair<const int, Counter<int>>>> map_type;
+
+static void doit()
+{
+    map_type::node_type nh;
+    assert(!static_cast<bool>(nh));
+
+    {
+        map_type mp = {{1, 6}, {2, 7}, {3, 8}, {4, 9}, {5, 10}};
+        assert(Counter_base::gConstructed == 5);
+        while (!mp.empty())
+        {
+            nh = mp.extract(mp.begin());
+        }
+        assert(mp.size() == 0);
+        assert(Counter_base::gConstructed == 1);
+        assert(static_cast<bool>(nh));
+    }
+
+    {
+        map_type other;
+        other.insert(std::move(nh));
+        assert(!static_cast<bool>(nh));
+    }
+
+    assert(Counter_base::gConstructed == 0);
+
+    {
+        map_type::node_type a, b;
+        std::swap(a, b);
+        map_type s = {{24, 101}, {42, 100}};
+        assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+        a = s.extract(s.begin());
+        a.swap(b);
+        assert(!static_cast<bool>(a) && static_cast<bool>(b));
+        s.insert(std::move(b));
+        assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+        a = s.extract(s.begin());
+        b = s.extract(s.begin());
+        assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+        assert(b.mapped() == 100 && b.key() == 42);
+        assert(a.mapped() == 101 && a.key() == 24);
+
+        swap(a, b);
+        assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+        assert(a.mapped() == 100 && a.key() == 42);
+        assert(b.mapped() == 101 && b.key() == 24);
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+int main()
+{
+    test_irt::doit();
+    test_extract::doit();
+    test_count_dtors::doit();
+    test_min_alloc::doit();
+    test_handle_operations::doit();
+}

libcxx/test/std/containers/associative/map/map.modifiers/merge.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <map>
+
+// class map
+
+// template <class C2>
+//   void merge(map<key_type, C2, allocator_type>& source);
+
+#include <map>
+#include "Counter.h"
+
+template <class Map>
+bool map_equal(const Map& map, Map other)
+{
+    return map == other;
+}
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+struct throw_comparator
+{
+    bool& should_throw_;
+
+    throw_comparator(bool& should_throw) : should_throw_(should_throw) {}
+
+    template <class T>
+    bool operator()(const T& lhs, const T& rhs) const
+    {
+        if (should_throw_)
+            throw 0;
+        return lhs < rhs;
+    }
+};
+#endif
+
+int main()
+{
+    {
+        std::map<int, int> src{{1, 0}, {3, 0}, {5, 0}};
+        std::map<int, int> dst{{2, 0}, {4, 0}, {5, 0}};
+        dst.merge(src);
+        assert(map_equal(src, {{5,0}}));
+        assert(map_equal(dst, {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}}));
+    }
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+    {
+        bool do_throw = false;
+        typedef std::map<Counter<int>, int, throw_comparator> map_type;
+        map_type src({{1, 0}, {3, 0}, {5, 0}}, throw_comparator(do_throw));
+        map_type dst({{2, 0}, {4, 0}, {5, 0}}, throw_comparator(do_throw));
+
+        assert(Counter_base::gConstructed == 6);
+
+        do_throw = true;
+        try
+        {
+            dst.merge(src);
+        }
+        catch (int)
+        {
+            do_throw = false;
+        }
+        assert(!do_throw);
+        assert(map_equal(src, map_type({{1, 0}, {3, 0}, {5, 0}}, throw_comparator(do_throw))));
+        assert(map_equal(dst, map_type({{2, 0}, {4, 0}, {5, 0}}, throw_comparator(do_throw))));
+    }
+#endif
+    assert(Counter_base::gConstructed == 0);
+    struct comparator
+    {
+        comparator() = default;
+
+        bool operator()(const Counter<int>& lhs, const Counter<int>& rhs) const
+        {
+            return lhs < rhs;
+        }
+    };
+    {
+        typedef std::map<Counter<int>, int, std::less<Counter<int>>> first_map_type;
+        typedef std::map<Counter<int>, int, comparator> second_map_type;
+        typedef std::multimap<Counter<int>, int, comparator> third_map_type;
+
+        first_map_type first{{1, 0}, {2, 0}, {3, 0}};
+        second_map_type second{{2, 0}, {3, 0}, {4, 0}};
+        third_map_type third{{1, 0}, {3, 0}};
+
+        assert(Counter_base::gConstructed == 8);
+
+        first.merge(second);
+        first.merge(std::move(second));
+        first.merge(third);
+        first.merge(std::move(third));
+
+        assert(map_equal(first, {{1, 0}, {2, 0}, {3, 0}, {4, 0}}));
+        assert(map_equal(second, {{2, 0}, {3, 0}}));
+        assert(map_equal(third, {{1, 0}, {3, 0}}));
+
+        assert(Counter_base::gConstructed == 8);
+    }
+    assert(Counter_base::gConstructed == 0);
+    {
+        std::map<int, int> first;
+        {
+            std::map<int, int> second;
+            first.merge(second);
+            first.merge(std::move(second));
+        }
+        {
+            std::multimap<int, int> second;
+            first.merge(second);
+            first.merge(std::move(second));
+        }
+    }
+}

libcxx/test/std/containers/associative/multimap/multimap.modifiers/insert_extract.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <map>
+
+// class multimap
+
+#include <map>
+#include <type_traits>
+#include "min_allocator.h"
+#include "Counter.h"
+
+namespace test_extract
+{
+using the_map = std::multimap<int, int>;
+
+static void doit()
+{
+    the_map s;
+    s.insert({1, 0});
+    s.insert({2, 0});
+    s.insert({3, 0});
+    assert(s.size() == 3);
+
+    the_map::node_type handle = s.extract(2);
+    assert(s.size() == 2);
+    the_map::iterator i = s.begin();
+    assert((*i).first == 1);
+    ++i;
+    assert((*i).first == 3);
+    ++i;
+    assert(i == s.end());
+}
+}
+
+namespace test_count_dtors
+{
+typedef std::multimap<Counter<int>, Counter<int>> map_type;
+
+static void doit()
+{
+    {
+        map_type dtc;
+        for (int i = 0; i != 10; ++i)
+            dtc.emplace(i, i + 10);
+
+        assert(Counter_base::gConstructed == 20);
+        assert(dtc.size() == 10);
+
+        map_type::node_type nh3 = dtc.extract(Counter<int>(3));
+        map_type::node_type nh0 = dtc.extract(Counter<int>(0));
+        map_type::node_type nh9 = dtc.extract(Counter<int>(9));
+
+        assert(static_cast<bool>(nh3) && static_cast<bool>(nh0) &&
+               static_cast<bool>(nh9));
+
+        assert(dtc.size() == 7);
+
+        dtc.insert(std::move(nh3));
+        assert(dtc.size() == 8);
+
+        assert(Counter_base::gConstructed == 20);
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_min_alloc
+{
+typedef std::multimap<int, int, std::less<int>, min_allocator<std::pair<const int, int>>> map_type;
+
+static void doit()
+{
+    map_type mp;
+    mp.insert({10, 10});
+    map_type::node_type nt = mp.extract(10);
+    assert(!nt.empty());
+    assert(mp.empty());
+    mp.insert(std::move(nt));
+    assert(mp.size() == 1);
+}
+}
+
+namespace test_handle_operations
+{
+typedef std::multimap<int, Counter<int>, std::less<Counter<int>>, min_allocator<std::pair<const int, Counter<int>>>> map_type;
+
+static void doit()
+{
+    map_type::node_type nh;
+    assert(!static_cast<bool>(nh));
+
+    {
+        map_type mp = {{1, 6}, {2, 7}, {3, 8}, {4, 9}, {5, 10}};
+        assert(Counter_base::gConstructed == 5);
+        while (!mp.empty())
+        {
+            nh = mp.extract(mp.begin());
+        }
+        assert(mp.size() == 0);
+        assert(Counter_base::gConstructed == 1);
+        assert(static_cast<bool>(nh));
+    }
+
+    {
+        map_type other;
+        other.insert(std::move(nh));
+        assert(!static_cast<bool>(nh));
+    }
+
+    assert(Counter_base::gConstructed == 0);
+
+    {
+        map_type::node_type a, b;
+        std::swap(a, b);
+        map_type s = {{24, 101}, {42, 100}};
+        assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+        a = s.extract(s.begin());
+        a.swap(b);
+        assert(!static_cast<bool>(a) && static_cast<bool>(b));
+        s.insert(std::move(b));
+        assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+        a = s.extract(s.begin());
+        b = s.extract(s.begin());
+        assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+        assert(b.mapped() == 100 && b.key() == 42);
+        assert(a.mapped() == 101 && a.key() == 24);
+
+        swap(a, b);
+        assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+        assert(a.mapped() == 100 && a.key() == 42);
+        assert(b.mapped() == 101 && b.key() == 24);
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+int main()
+{
+    test_extract::doit();
+    test_count_dtors::doit();
+    test_min_alloc::doit();
+    test_handle_operations::doit();
+}

libcxx/test/std/containers/associative/multimap/multimap.modifiers/merge.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <map>
+
+// class multimap
+
+// template <class C2>
+//   void merge(multimap<key_type, C2, allocator_type>& source);
+
+#include <map>
+#include "Counter.h"
+
+template <class Map>
+bool map_equal(const Map& map, Map other)
+{
+    return map == other;
+}
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+struct throw_comparator
+{
+    bool& should_throw_;
+
+    throw_comparator(bool& should_throw) : should_throw_(should_throw) {}
+
+    template <class T>
+    bool operator()(const T& lhs, const T& rhs) const
+    {
+        if (should_throw_)
+            throw 0;
+        return lhs < rhs;
+    }
+};
+#endif
+
+int main()
+{
+    {
+        std::multimap<int, int> src{{1, 0}, {3, 0}, {5, 0}};
+        std::multimap<int, int> dst{{2, 0}, {4, 0}, {5, 0}};
+        dst.merge(src);
+        assert(map_equal(src, {}));
+        assert(map_equal(dst, {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}, {5, 0}}));
+    }
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+    {
+        bool do_throw = false;
+        typedef std::multimap<Counter<int>, int, throw_comparator> map_type;
+        map_type src({{1, 0}, {3, 0}, {5, 0}}, throw_comparator(do_throw));
+        map_type dst({{2, 0}, {4, 0}, {5, 0}}, throw_comparator(do_throw));
+
+        assert(Counter_base::gConstructed == 6);
+
+        do_throw = true;
+        try
+        {
+            dst.merge(src);
+        }
+        catch (int)
+        {
+            do_throw = false;
+        }
+        assert(!do_throw);
+        assert(map_equal(src, map_type({{1, 0}, {3, 0}, {5, 0}}, throw_comparator(do_throw))));
+        assert(map_equal(dst, map_type({{2, 0}, {4, 0}, {5, 0}}, throw_comparator(do_throw))));
+    }
+#endif
+    assert(Counter_base::gConstructed == 0);
+    struct comparator
+    {
+        comparator() = default;
+
+        bool operator()(const Counter<int>& lhs, const Counter<int>& rhs) const
+        {
+            return lhs < rhs;
+        }
+    };
+    {
+        typedef std::multimap<Counter<int>, int, std::less<Counter<int>>> first_map_type;
+        typedef std::multimap<Counter<int>, int, comparator> second_map_type;
+        typedef std::map<Counter<int>, int, comparator> third_map_type;
+
+        first_map_type first{{1, 0}, {2, 0}, {3, 0}};
+        second_map_type second{{2, 0}, {3, 0}, {4, 0}};
+        third_map_type third{{1, 0}, {3, 0}};
+
+        assert(Counter_base::gConstructed == 8);
+
+        first.merge(second);
+        first.merge(std::move(second));
+        first.merge(third);
+        first.merge(std::move(third));
+
+        assert(map_equal(first, {{1, 0}, {1, 0}, {2, 0}, {2, 0}, {3, 0}, {3, 0}, {3, 0}, {4, 0}}));
+        assert(map_equal(second, {}));
+        assert(map_equal(third, {}));
+
+        assert(Counter_base::gConstructed == 8);
+    }
+    assert(Counter_base::gConstructed == 0);
+    {
+        std::multimap<int, int> first;
+        {
+            std::multimap<int, int> second;
+            first.merge(second);
+            first.merge(std::move(second));
+        }
+        {
+            std::multimap<int, int> second;
+            first.merge(second);
+            first.merge(std::move(second));
+        }
+    }
+}

libcxx/test/std/containers/associative/multiset/insert_extract.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <set>
+
+// class multiset
+
+#include <set>
+#include <type_traits>
+#include "min_allocator.h"
+#include "Counter.h"
+
+namespace test_extract
+{
+using the_set = std::multiset<int>;
+
+static void doit()
+{
+    the_set s;
+    s.insert(1);
+    s.insert(2);
+    s.insert(3);
+    assert(s.size() == 3);
+
+    the_set::node_type handle = s.extract(2);
+    assert(s.size() == 2);
+    the_set::iterator i = s.begin();
+    assert(*i == 1);
+    ++i;
+    assert(*i == 3);
+    ++i;
+    assert(i == s.end());
+}
+}
+
+namespace test_count_dtors
+{
+typedef std::multiset<Counter<int>> set_type;
+
+static void doit()
+{
+    {
+        set_type dtc;
+        for (int i = 0; i != 10; ++i)
+            dtc.emplace(i);
+
+        assert(Counter_base::gConstructed == 10);
+        assert(dtc.size() == 10);
+
+        set_type::node_type nh3 = dtc.extract(Counter<int>(3));
+        set_type::node_type nh0 = dtc.extract(Counter<int>(0));
+        set_type::node_type nh9 = dtc.extract(Counter<int>(9));
+
+        assert(Counter_base::gConstructed == 10);
+        assert(dtc.size() == 7);
+
+        dtc.insert(std::move(nh3));
+        assert(dtc.size() == 8);
+        assert(Counter_base::gConstructed == 10);
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_min_alloc
+{
+typedef std::multiset<int, std::less<int>, min_allocator<int>> set_type;
+
+static void doit()
+{
+    set_type st;
+    st.insert(10);
+    set_type::node_type nt = st.extract(10);
+    assert(!nt.empty());
+    assert(st.empty());
+    st.insert(std::move(nt));
+    assert(st.size() == 1);
+}
+}
+
+namespace test_handle_operations
+{
+typedef std::multiset<Counter<int>, std::less<Counter<int>>, min_allocator<Counter<int>>> set_type;
+
+static void doit()
+{
+    set_type::node_type nh;
+    assert(!static_cast<bool>(nh));
+
+    {
+        set_type st = {1, 2, 3, 4, 5};
+        assert(Counter_base::gConstructed == 5);
+        while (!st.empty())
+        {
+            nh = st.extract(st.begin());
+        }
+        assert(st.size() == 0);
+        assert(Counter_base::gConstructed == 1);
+        assert(static_cast<bool>(nh));
+    }
+
+    {
+        set_type other;
+        other.insert(std::move(nh));
+        assert(!static_cast<bool>(nh));
+    }
+
+    assert(Counter_base::gConstructed == 0);
+
+    {
+        set_type::node_type a, b;
+        std::swap(a, b);
+        set_type s = {42, 24};
+        assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+        a = s.extract(s.begin());
+        a.swap(b);
+        assert(!static_cast<bool>(a) && static_cast<bool>(b));
+        s.insert(std::move(b));
+        assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+        a = s.extract(s.begin());
+        b = s.extract(s.begin());
+        assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+        Counter<int>* aval = &a.value();
+        Counter<int>* bval = &b.value();
+        assert(aval->get() == 24);
+        assert(bval->get() == 42);
+
+        swap(a, b);
+        assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+        aval = &a.value();
+        bval = &b.value();
+        assert(aval->get() == 42);
+        assert(bval->get() == 24);
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_multi
+{
+typedef std::multiset<int> set_type;
+static void doit()
+{
+    {
+        set_type s = {1, 2, 2};
+        assert(s.count(2) == 2);
+        set_type::node_type nh = s.extract(2);
+        assert(s.count(1) == 1);
+        assert(s.count(2) == 1);
+        assert(s.size() == 2);
+        s.insert(std::move(nh));
+        assert(s.size() == 3);
+        assert(nh.empty());
+    }
+
+    {
+        set_type s = {0};
+        set_type::node_type nt = s.extract(s.begin());
+        assert(nt.value() == 0);
+        assert(s.size() == 0);
+        s.insert(std::move(nt));
+    }
+
+    {
+        set_type s = {1, 2};
+        set_type::node_type nh = s.extract(1);
+        s.insert(s.begin(), std::move(nh));
+        assert(nh.empty());
+        assert(s.size() == 2);
+    }
+
+    {
+        set_type s;
+        set_type::node_type nh;
+        set_type::iterator i = s.insert(std::move(nh));
+        assert(i == s.end());
+    }
+}
+}
+
+int main()
+{
+    test_extract::doit();
+    test_count_dtors::doit();
+    test_min_alloc::doit();
+    test_handle_operations::doit();
+    test_multi::doit();
+}

libcxx/test/std/containers/associative/multiset/merge.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <set>
+
+// class multiset
+
+// template <class C2>
+//   void merge(multiset<Key, C2, Allocator>& source);
+//
+// template <class C2>
+//   void merge(multiset<Key, C2, Allocator>&& source);
+//
+// template <class C2>
+//   void merge(set<Key, C2, Allocator>& source);
+//
+// template <class C2>
+//   void merge(set<Key, C2, Allocator>&& source);
+
+#include <set>
+#include "Counter.h"
+
+template <class Set>
+bool set_equal(const Set& set, Set other)
+{
+    return set == other;
+}
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+struct throw_comparator
+{
+    bool& should_throw_;
+
+    throw_comparator(bool& should_throw) : should_throw_(should_throw) {}
+
+    template <class T>
+    bool operator()(const T& lhs, const T& rhs) const
+    {
+        if (should_throw_)
+            throw 0;
+        return lhs < rhs;
+    }
+};
+#endif
+
+int main()
+{
+    {
+        std::multiset<int> src{1, 3, 5};
+        std::multiset<int> dst{2, 4, 5};
+        dst.merge(src);
+        assert(set_equal(src, {}));
+        assert(set_equal(dst, {1, 2, 3, 4, 5, 5}));
+    }
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+    {
+        bool do_throw = false;
+        typedef std::multiset<Counter<int>, throw_comparator> set_type;
+        set_type src({1, 3, 5}, throw_comparator(do_throw));
+        set_type dst({2, 4, 5}, throw_comparator(do_throw));
+
+        assert(Counter_base::gConstructed == 6);
+
+        do_throw = true;
+        try
+        {
+            dst.merge(src);
+        }
+        catch (int)
+        {
+            do_throw = false;
+        }
+        assert(!do_throw);
+        assert(set_equal(src, set_type({1, 3, 5}, throw_comparator(do_throw))));
+        assert(set_equal(dst, set_type({2, 4, 5}, throw_comparator(do_throw))));
+    }
+#endif
+    assert(Counter_base::gConstructed == 0);
+    struct comparator
+    {
+        comparator() = default;
+
+        bool operator()(const Counter<int>& lhs, const Counter<int>& rhs) const
+        {
+            return lhs < rhs;
+        }
+    };
+    {
+        typedef std::multiset<Counter<int>, std::less<Counter<int>>> first_set_type;
+        typedef std::multiset<Counter<int>, comparator> second_set_type;
+        typedef std::set<Counter<int>, comparator> third_set_type;
+
+        first_set_type first{1, 2, 3};
+        second_set_type second{2, 3, 4};
+        third_set_type third{1, 3};
+
+        assert(Counter_base::gConstructed == 8);
+
+        first.merge(second);
+        first.merge(std::move(second));
+        first.merge(third);
+        first.merge(std::move(third));
+
+        assert(set_equal(first, {1, 1, 2, 2, 3, 3, 3, 4}));
+        assert(set_equal(second, {}));
+        assert(set_equal(third, {}));
+
+        assert(Counter_base::gConstructed == 8);
+    }
+    assert(Counter_base::gConstructed == 0);
+    {
+        std::multiset<int> first;
+        {
+            std::multiset<int> second;
+            first.merge(second);
+            first.merge(std::move(second));
+        }
+        {
+            std::set<int> second;
+            first.merge(second);
+            first.merge(std::move(second));
+        }
+    }
+}

libcxx/test/std/containers/associative/set/insert_extract.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <set>
+
+// class set
+
+#include <set>
+#include <type_traits>
+#include "min_allocator.h"
+#include "Counter.h"
+
+namespace test_irt
+{
+typedef std::set<int> int_set_type;
+using intIRT = int_set_type::insert_return_type;
+static_assert(std::is_move_constructible<intIRT>::value &&
+              std::is_move_assignable<intIRT>::value &&
+              std::is_default_constructible<intIRT>::value &&
+              std::is_destructible<intIRT>::value, "");
+
+typedef std::set<Counter<int>, std::less<Counter<int>>,
+                 min_allocator<Counter<int>>> set_type;
+using minIRT = set_type::insert_return_type;
+
+static_assert(std::is_move_constructible<minIRT>::value &&
+              std::is_move_assignable<minIRT>::value &&
+              std::is_default_constructible<minIRT>::value &&
+              std::is_destructible<minIRT>::value, "");
+
+static void doit()
+{
+    {
+        intIRT a, b;
+        std::swap(a, b);
+
+        minIRT c, d;
+        std::swap(c, d);
+    }
+
+    {
+        set_type st = {0};
+        set_type::node_type nh = st.extract(st.begin());
+        set_type::insert_return_type irt = st.insert(std::move(nh));
+        assert(irt.inserted);
+        assert(irt.position == st.begin());
+        assert(irt.node.empty());
+    }
+
+    {
+        set_type st = {0};
+        set_type::node_type nh = st.extract(st.begin());
+        st.insert(0);
+        set_type::insert_return_type irt = st.insert(std::move(nh));
+        assert(!irt.inserted);
+        assert(irt.position == st.begin());
+        assert(!irt.node.empty());
+    }
+
+    {
+        set_type st;
+        set_type::node_type nh;
+        set_type::insert_return_type irt = st.insert(std::move(nh));
+        assert(!irt.inserted);
+        assert(irt.position == st.end());
+        assert(irt.node.empty());
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_extract
+{
+using the_set = std::set<int>;
+
+static void doit()
+{
+    the_set s;
+    s.insert(1);
+    s.insert(2);
+    s.insert(3);
+    assert(s.size() == 3);
+
+    the_set::node_type handle = s.extract(2);
+    assert(s.size() == 2);
+    the_set::iterator i = s.begin();
+    assert(*i == 1);
+    ++i;
+    assert(*i == 3);
+    ++i;
+    assert(i == s.end());
+}
+}
+
+namespace test_count_dtors
+{
+typedef std::set<Counter<int>> set_type;
+
+static void doit()
+{
+    {
+        set_type dtc;
+        for (int i = 0; i != 10; ++i)
+            dtc.emplace(i);
+
+        assert(Counter_base::gConstructed == 10);
+        assert(dtc.size() == 10);
+
+        set_type::node_type nh3 = dtc.extract(Counter<int>(3));
+        set_type::node_type nh0 = dtc.extract(Counter<int>(0));
+        set_type::node_type nh9 = dtc.extract(Counter<int>(9));
+
+        assert(Counter_base::gConstructed == 10);
+        assert(dtc.size() == 7);
+
+        dtc.insert(std::move(nh3));
+        assert(dtc.size() == 8);
+        assert(Counter_base::gConstructed == 10);
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_min_alloc
+{
+typedef std::set<int, std::less<int>, min_allocator<int>> set_type;
+
+static void doit()
+{
+    set_type st;
+    st.insert(10);
+    set_type::node_type nt = st.extract(10);
+    assert(!nt.empty());
+    assert(st.empty());
+    st.insert(std::move(nt));
+    assert(st.size() == 1);
+}
+}
+
+namespace test_handle_operations
+{
+typedef std::set<Counter<int>, std::less<Counter<int>>, min_allocator<Counter<int>>> set_type;
+
+static void doit()
+{
+    set_type::node_type nh;
+    assert(!static_cast<bool>(nh));
+
+    {
+        set_type st = {1, 2, 3, 4, 5};
+        assert(Counter_base::gConstructed == 5);
+        while (!st.empty())
+        {
+            nh = st.extract(st.begin());
+        }
+        assert(st.size() == 0);
+        assert(Counter_base::gConstructed == 1);
+        assert(static_cast<bool>(nh));
+    }
+
+    {
+        set_type other;
+        other.insert(std::move(nh));
+        assert(!static_cast<bool>(nh));
+    }
+
+    assert(Counter_base::gConstructed == 0);
+
+    {
+        set_type::node_type a, b;
+        std::swap(a, b);
+        set_type s = {42, 24};
+        assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+        a = s.extract(s.begin());
+        a.swap(b);
+        assert(!static_cast<bool>(a) && static_cast<bool>(b));
+        s.insert(std::move(b));
+        assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+        a = s.extract(s.begin());
+        b = s.extract(s.begin());
+        assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+        Counter<int>* aval = &a.value();
+        Counter<int>* bval = &b.value();
+        assert(aval->get() == 24);
+        assert(bval->get() == 42);
+
+        swap(a, b);
+        assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+        aval = &a.value();
+        bval = &b.value();
+        assert(aval->get() == 42);
+        assert(bval->get() == 24);
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+int main()
+{
+    test_irt::doit();
+    test_extract::doit();
+    test_count_dtors::doit();
+    test_min_alloc::doit();
+    test_handle_operations::doit();
+}

libcxx/test/std/containers/associative/set/merge.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <set>
+
+// class set
+
+// template <class C2>
+//   void merge(set<key_type, C2, allocator_type>& source);
+
+#include <set>
+#include "Counter.h"
+
+template <class Set>
+bool set_equal(const Set& set, Set other)
+{
+    return set == other;
+}
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+struct throw_comparator
+{
+    bool& should_throw_;
+
+    throw_comparator(bool& should_throw) : should_throw_(should_throw) {}
+
+    template <class T>
+    bool operator()(const T& lhs, const T& rhs) const
+    {
+        if (should_throw_)
+            throw 0;
+        return lhs < rhs;
+    }
+};
+#endif
+
+int main()
+{
+    {
+        std::set<int> src{1, 3, 5};
+        std::set<int> dst{2, 4, 5};
+        dst.merge(src);
+        assert(set_equal(src, {5}));
+        assert(set_equal(dst, {1, 2, 3, 4, 5}));
+    }
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+    {
+        bool do_throw = false;
+        typedef std::set<Counter<int>, throw_comparator> set_type;
+        set_type src({1, 3, 5}, throw_comparator(do_throw));
+        set_type dst({2, 4, 5}, throw_comparator(do_throw));
+
+        assert(Counter_base::gConstructed == 6);
+
+        do_throw = true;
+        try
+        {
+            dst.merge(src);
+        }
+        catch (int)
+        {
+            do_throw = false;
+        }
+        assert(!do_throw);
+        assert(set_equal(src, set_type({1, 3, 5}, throw_comparator(do_throw))));
+        assert(set_equal(dst, set_type({2, 4, 5}, throw_comparator(do_throw))));
+    }
+#endif
+    assert(Counter_base::gConstructed == 0);
+    struct comparator
+    {
+        comparator() = default;
+
+        bool operator()(const Counter<int>& lhs, const Counter<int>& rhs) const
+        {
+            return lhs < rhs;
+        }
+    };
+    {
+        typedef std::set<Counter<int>, std::less<Counter<int>>> first_set_type;
+        typedef std::set<Counter<int>, comparator> second_set_type;
+        typedef std::multiset<Counter<int>, comparator> third_set_type;
+
+        first_set_type first{1, 2, 3};
+        second_set_type second{2, 3, 4};
+        third_set_type third{1, 3};
+
+        assert(Counter_base::gConstructed == 8);
+
+        first.merge(second);
+        first.merge(std::move(second));
+        first.merge(third);
+        first.merge(std::move(third));
+
+        assert(set_equal(first, {1, 2, 3, 4}));
+        assert(set_equal(second, {2, 3}));
+        assert(set_equal(third, {1, 3}));
+
+        assert(Counter_base::gConstructed == 8);
+    }
+    assert(Counter_base::gConstructed == 0);
+    {
+        std::set<int> first;
+        {
+            std::set<int> second;
+            first.merge(second);
+            first.merge(std::move(second));
+        }
+        {
+            std::multiset<int> second;
+            first.merge(second);
+            first.merge(std::move(second));
+        }
+    }
+}

libcxx/test/std/containers/container.node/node_handle.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+#include <unordered_set>
+#include <unordered_map>
+#include <set>
+#include <map>
+#include "min_allocator.h"
+
+using namespace std;
+
+// [container.node.overview] Table 83.
+template <class K, class T, class C1, class C2, class H1, class H2, class E1, class E2, class A_set, class A_map>
+struct node_compatibility_table
+{
+    static constexpr bool value =
+        is_same_v<typename map<K, T, C1, A_map>::node_type,               typename map<K, T, C2, A_map>::node_type> &&
+        is_same_v<typename map<K, T, C1, A_map>::node_type,               typename multimap<K, T, C2, A_map>::node_type> &&
+        is_same_v<typename set<K, C1, A_set>::node_type,                  typename set<K, C2, A_set>::node_type> &&
+        is_same_v<typename set<K, C1, A_set>::node_type,                  typename multiset<K, C2, A_set>::node_type> &&
+        is_same_v<typename unordered_map<K, T, H1, E1, A_map>::node_type, typename unordered_map<K, T, H2, E2, A_map>::node_type> &&
+        is_same_v<typename unordered_map<K, T, H1, E1, A_map>::node_type, typename unordered_multimap<K, T, H2, E2, A_map>::node_type> &&
+        is_same_v<typename unordered_set<K, H1, E1, A_set>::node_type,    typename unordered_set<K, H2, E2, A_set>::node_type> &&
+        is_same_v<typename unordered_set<K, H1, E1, A_set>::node_type,    typename unordered_multiset<K, H2, E2, A_set>::node_type>;
+};
+
+template <class T> struct my_hash
+{
+    typedef T argument_type;
+    typedef size_t result_type;
+    my_hash() = default;
+    size_t operator()(const T&) const {return 0;}
+};
+
+template <class T> struct my_compare
+{
+    my_compare() = default;
+    bool operator()(const T&, const T&) const {return true;}
+};
+
+template <class T> struct my_equal
+{
+    my_equal() = default;
+    bool operator()(const T&, const T&) const {return true;}
+};
+
+struct Static
+{
+    Static() = default;
+    Static(const Static&) = delete;
+    Static(Static&&) = delete;
+    Static& operator=(const Static&) = delete;
+    Static& operator=(Static&&) = delete;
+};
+
+namespace std
+{
+template <> struct hash<Static>
+{
+    typedef Static argument_type;
+    typedef size_t result_type;
+    hash() = default;
+    size_t operator()(const Static&) const;
+};
+}
+
+static_assert(node_compatibility_table<
+                  int, int, std::less<int>, std::less<int>, std::hash<int>,
+                  std::hash<int>, std::equal_to<int>, std::equal_to<int>,
+                  std::allocator<int>,
+                  std::allocator<std::pair<const int, int> > >::value,
+              "");
+
+static_assert(
+    node_compatibility_table<int, int, std::less<int>, my_compare<int>,
+                             std::hash<int>, my_hash<int>, std::equal_to<int>,
+                             my_equal<int>, allocator<int>,
+                             allocator<std::pair<const int, int> > >::value,
+    "");
+
+static_assert(node_compatibility_table<
+                  Static, int, my_compare<Static>, std::less<Static>,
+                  my_hash<Static>, std::hash<Static>, my_equal<Static>,
+                  std::equal_to<Static>, min_allocator<Static>,
+                  min_allocator<std::pair<const Static, int> > >::value,
+              "");
+
+int main()
+{
+    return 0;
+}

libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/insert_extract.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_map>
+
+// class unordered_map
+
+#include <unordered_map>
+#include <type_traits>
+#include "min_allocator.h"
+#include "Counter.h"
+
+namespace test_irt
+{
+typedef std::unordered_map<int, int> int_map_type;
+using intIRT = int_map_type::insert_return_type;
+static_assert(std::is_move_constructible<intIRT>::value &&
+              std::is_move_assignable<intIRT>::value &&
+              std::is_default_constructible<intIRT>::value &&
+              std::is_destructible<intIRT>::value, "");
+
+typedef std::unordered_map<
+    Counter<int>, Counter<int>, std::hash<Counter<int> >,
+    std::equal_to<Counter<int> >,
+    min_allocator<std::pair<const Counter<int>, Counter<int> > > >
+    map_type;
+using minIRT = map_type::insert_return_type;
+
+static_assert(std::is_move_constructible<minIRT>::value &&
+              std::is_move_assignable<minIRT>::value &&
+              std::is_default_constructible<minIRT>::value &&
+              std::is_destructible<minIRT>::value, "");
+
+static void doit()
+{
+    {
+        intIRT a, b;
+        std::swap(a, b);
+
+        minIRT c, d;
+        std::swap(c, d);
+    }
+
+    {
+        map_type mp = {{0, 0}};
+        map_type::node_type nh = mp.extract(mp.begin());
+        map_type::insert_return_type irt = mp.insert(std::move(nh));
+        assert(irt.inserted);
+        assert(irt.position == mp.begin());
+        assert(irt.node.empty());
+    }
+
+    {
+        map_type mp = {{0, 0}};
+        map_type::node_type nh = mp.extract(mp.begin());
+        mp.insert({0, 0});
+        map_type::insert_return_type irt = mp.insert(std::move(nh));
+        assert(!irt.inserted);
+        assert(irt.position == mp.begin());
+        assert(!irt.node.empty());
+    }
+
+    {
+        map_type mp;
+        map_type::node_type nh;
+        map_type::insert_return_type irt = mp.insert(std::move(nh));
+        assert(!irt.inserted);
+        assert(irt.position == mp.end());
+        assert(irt.node.empty());
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_extract
+{
+using the_map = std::unordered_map<int, int>;
+
+static void doit()
+{
+    the_map s;
+    s.insert({1, 0});
+    s.insert({2, 0});
+    s.insert({3, 0});
+    assert(s.size() == 3);
+
+    the_map::node_type handle = s.extract(2);
+    assert(s.size() == 2);
+    assert(s.count(1) == 1 && s.count(3) == 1);
+    the_map::iterator i = s.begin();
+    std::advance(i, 2);
+    assert(i == s.end());
+}
+}
+
+namespace test_count_dtors
+{
+typedef std::unordered_map<Counter<int>, Counter<int>> map_type;
+
+static void doit()
+{
+    {
+        map_type dtc;
+        for (int i = 0; i != 10; ++i)
+            dtc.emplace(i, i + 10);
+
+        assert(Counter_base::gConstructed == 20);
+        assert(dtc.size() == 10);
+
+        map_type::node_type nh3 = dtc.extract(Counter<int>(3));
+        map_type::node_type nh0 = dtc.extract(Counter<int>(0));
+        map_type::node_type nh9 = dtc.extract(Counter<int>(9));
+
+        assert(static_cast<bool>(nh3) && static_cast<bool>(nh0) &&
+               static_cast<bool>(nh9));
+
+        assert(dtc.size() == 7);
+
+        dtc.insert(std::move(nh3));
+        assert(dtc.size() == 8);
+
+        assert(Counter_base::gConstructed == 20);
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_min_alloc
+{
+typedef std::unordered_map<int, int, std::hash<int>, std::equal_to<int>, min_allocator<std::pair<const int, int>>> map_type;
+
+static void doit()
+{
+    map_type mp;
+    mp.insert({10, 10});
+    map_type::node_type nt = mp.extract(10);
+    assert(!nt.empty());
+    assert(mp.empty());
+    mp.insert(std::move(nt));
+    assert(mp.size() == 1);
+}
+}
+
+namespace test_handle_operations
+{
+typedef std::unordered_map<int, Counter<int>, std::hash<Counter<int>>, std::equal_to<Counter<int>>, min_allocator<std::pair<const int, Counter<int>>>> map_type;
+
+static void doit()
+{
+    map_type::node_type nh;
+    assert(!static_cast<bool>(nh));
+
+    {
+        map_type mp = {{1, 6}, {2, 7}, {3, 8}, {4, 9}, {5, 10}};
+        assert(Counter_base::gConstructed == 5);
+        while (!mp.empty())
+        {
+            nh = mp.extract(mp.begin());
+        }
+        assert(mp.size() == 0);
+        assert(Counter_base::gConstructed == 1);
+        assert(static_cast<bool>(nh));
+    }
+
+    {
+        map_type other;
+        other.insert(std::move(nh));
+        assert(!static_cast<bool>(nh));
+    }
+
+    assert(Counter_base::gConstructed == 0);
+
+    {
+        map_type::node_type a, b;
+        std::swap(a, b);
+        map_type s = {{24, 101}, {42, 100}};
+        assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+        a = s.extract(s.begin());
+        a.swap(b);
+        assert(!static_cast<bool>(a) && static_cast<bool>(b));
+        s.insert(std::move(b));
+        assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+        a = s.extract(24);
+        b = s.extract(42);
+        assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+        assert(b.mapped() == 100 && b.key() == 42);
+        assert(a.mapped() == 101 && a.key() == 24);
+
+        swap(a, b);
+        assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+        assert(a.mapped() == 100 && a.key() == 42);
+        assert(b.mapped() == 101 && b.key() == 24);
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+int main()
+{
+    test_irt::doit();
+    test_extract::doit();
+    test_count_dtors::doit();
+    test_min_alloc::doit();
+    test_handle_operations::doit();
+}

libcxx/test/std/containers/unord/unord.map/unord.map.modifiers/merge.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_map>
+
+// class unordered_map
+
+// template <class C2>
+//   void merge(unordered_map<key_type, C2, allocator_type>& source);
+
+#include <unordered_map>
+#include "Counter.h"
+
+template <class Map>
+bool map_equal(const Map& map, Map other)
+{
+    return map == other;
+}
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+template <class T>
+struct throw_hasher
+{
+    bool& should_throw_;
+
+    throw_hasher(bool& should_throw) : should_throw_(should_throw) {}
+
+    typedef size_t result_type;
+    typedef T argument_type;
+
+    size_t operator()(const T& p) const
+    {
+        if (should_throw_)
+            throw 0;
+        return std::hash<T>()(p);
+    }
+};
+#endif
+
+int main()
+{
+    {
+        std::unordered_map<int, int> src{{1, 0}, {3, 0}, {5, 0}};
+        std::unordered_map<int, int> dst{{2, 0}, {4, 0}, {5, 0}};
+        dst.merge(src);
+        assert(map_equal(src, {{5,0}}));
+        assert(map_equal(dst, {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}}));
+    }
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+    {
+        bool do_throw = false;
+        typedef std::unordered_map<Counter<int>, int, throw_hasher<Counter<int>>> map_type;
+        map_type src({{1, 0}, {3, 0}, {5, 0}}, 0, throw_hasher<Counter<int>>(do_throw));
+        map_type dst({{2, 0}, {4, 0}, {5, 0}}, 0, throw_hasher<Counter<int>>(do_throw));
+
+        assert(Counter_base::gConstructed == 6);
+
+        do_throw = true;
+        try
+        {
+            dst.merge(src);
+        }
+        catch (int)
+        {
+            do_throw = false;
+        }
+        assert(!do_throw);
+        assert(map_equal(src, map_type({{1, 0}, {3, 0}, {5, 0}}, 0, throw_hasher<Counter<int>>(do_throw))));
+        assert(map_equal(dst, map_type({{2, 0}, {4, 0}, {5, 0}}, 0, throw_hasher<Counter<int>>(do_throw))));
+    }
+#endif
+    assert(Counter_base::gConstructed == 0);
+    struct equal
+    {
+        equal() = default;
+
+        bool operator()(const Counter<int>& lhs, const Counter<int>& rhs) const
+        {
+            return lhs == rhs;
+        }
+    };
+    struct hasher
+    {
+        hasher() = default;
+        typedef Counter<int> argument_type;
+        typedef size_t result_type;
+        size_t operator()(const Counter<int>& p) const
+        {
+            return std::hash<Counter<int>>()(p);
+        }
+    };
+    {
+        typedef std::unordered_map<Counter<int>, int, std::hash<Counter<int>>, std::equal_to<Counter<int>>> first_map_type;
+        typedef std::unordered_map<Counter<int>, int, hasher, equal> second_map_type;
+        typedef std::unordered_multimap<Counter<int>, int, hasher, equal> third_map_type;
+
+        first_map_type first{{1, 0}, {2, 0}, {3, 0}};
+        second_map_type second{{2, 0}, {3, 0}, {4, 0}};
+        third_map_type third{{1, 0}, {3, 0}};
+
+        assert(Counter_base::gConstructed == 8);
+
+        first.merge(second);
+        first.merge(std::move(second));
+        first.merge(third);
+        first.merge(std::move(third));
+
+        assert(map_equal(first, {{1, 0}, {2, 0}, {3, 0}, {4, 0}}));
+        assert(map_equal(second, {{2, 0}, {3, 0}}));
+        assert(map_equal(third, {{1, 0}, {3, 0}}));
+
+        assert(Counter_base::gConstructed == 8);
+    }
+    assert(Counter_base::gConstructed == 0);
+    {
+        std::unordered_map<int, int> first;
+        {
+            std::unordered_map<int, int> second;
+            first.merge(second);
+            first.merge(std::move(second));
+        }
+        {
+            std::unordered_multimap<int, int> second;
+            first.merge(second);
+            first.merge(std::move(second));
+        }
+    }
+}

libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/insert_extract.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_map>
+
+// class unordered_multimap
+
+#include <unordered_map>
+#include <type_traits>
+#include "min_allocator.h"
+#include "Counter.h"
+
+namespace test_extract
+{
+using the_map = std::unordered_multimap<int, int>;
+
+static void doit()
+{
+    the_map s;
+    s.insert({1, 0});
+    s.insert({2, 0});
+    s.insert({3, 0});
+    assert(s.size() == 3);
+
+    the_map::node_type handle = s.extract(2);
+    assert(s.size() == 2);
+    assert(s.count(1) == 1 && s.count(3) == 1);
+    the_map::iterator i = s.begin();
+    std::advance(i, 2);
+    assert(i == s.end());
+}
+}
+
+namespace test_count_dtors
+{
+typedef std::unordered_multimap<Counter<int>, Counter<int>> map_type;
+
+static void doit()
+{
+    {
+        map_type dtc;
+        for (int i = 0; i != 10; ++i)
+            dtc.emplace(i, i + 10);
+
+        assert(Counter_base::gConstructed == 20);
+        assert(dtc.size() == 10);
+
+        map_type::node_type nh3 = dtc.extract(Counter<int>(3));
+        map_type::node_type nh0 = dtc.extract(Counter<int>(0));
+        map_type::node_type nh9 = dtc.extract(Counter<int>(9));
+
+        assert(static_cast<bool>(nh3) && static_cast<bool>(nh0) &&
+               static_cast<bool>(nh9));
+
+        assert(dtc.size() == 7);
+
+        dtc.insert(std::move(nh3));
+        assert(dtc.size() == 8);
+
+        assert(Counter_base::gConstructed == 20);
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_min_alloc
+{
+typedef std::unordered_multimap<int, int, std::hash<int>, std::equal_to<int>, min_allocator<std::pair<const int, int>>> map_type;
+
+static void doit()
+{
+    map_type mp;
+    mp.insert({10, 10});
+    map_type::node_type nt = mp.extract(10);
+    assert(!nt.empty());
+    assert(mp.empty());
+    mp.insert(std::move(nt));
+    assert(mp.size() == 1);
+}
+}
+
+namespace test_handle_operations
+{
+typedef std::unordered_multimap<int, Counter<int>, std::hash<Counter<int>>, std::equal_to<Counter<int>>, min_allocator<std::pair<const int, Counter<int>>>> map_type;
+
+static void doit()
+{
+    map_type::node_type nh;
+    assert(!static_cast<bool>(nh));
+
+    {
+        map_type mp = {{1, 6}, {2, 7}, {3, 8}, {4, 9}, {5, 10}};
+        assert(Counter_base::gConstructed == 5);
+        while (!mp.empty())
+        {
+            nh = mp.extract(mp.begin());
+        }
+        assert(mp.size() == 0);
+        assert(Counter_base::gConstructed == 1);
+        assert(static_cast<bool>(nh));
+    }
+
+    {
+        map_type other;
+        other.insert(std::move(nh));
+        assert(!static_cast<bool>(nh));
+    }
+
+    assert(Counter_base::gConstructed == 0);
+
+    {
+        map_type::node_type a, b;
+        std::swap(a, b);
+        map_type s = {{24, 101}, {42, 100}};
+        assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+        a = s.extract(s.begin());
+        a.swap(b);
+        assert(!static_cast<bool>(a) && static_cast<bool>(b));
+        s.insert(std::move(b));
+        assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+        a = s.extract(24);
+        b = s.extract(42);
+        assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+        assert(b.mapped() == 100 && b.key() == 42);
+        assert(a.mapped() == 101 && a.key() == 24);
+
+        swap(a, b);
+        assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+        assert(a.mapped() == 100 && a.key() == 42);
+        assert(b.mapped() == 101 && b.key() == 24);
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+int main()
+{
+    test_extract::doit();
+    test_count_dtors::doit();
+    test_min_alloc::doit();
+    test_handle_operations::doit();
+}

libcxx/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/merge.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_map>
+
+// class unordered_multimap
+
+// template <class C2>
+//   void merge(unordered_multimap<key_type, C2, allocator_type>& source);
+
+#include <unordered_map>
+#include "Counter.h"
+
+template <class Map>
+bool map_equal(const Map& map, Map other)
+{
+    return map == other;
+}
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+template <class T>
+struct throw_hasher
+{
+    bool& should_throw_;
+
+    throw_hasher(bool& should_throw) : should_throw_(should_throw) {}
+
+    typedef size_t result_type;
+    typedef T argument_type;
+
+    size_t operator()(const T& p) const
+    {
+        if (should_throw_)
+            throw 0;
+        return std::hash<T>()(p);
+    }
+};
+#endif
+
+int main()
+{
+    {
+        std::unordered_multimap<int, int> src{{1, 0}, {3, 0}, {5, 0}};
+        std::unordered_multimap<int, int> dst{{2, 0}, {4, 0}, {5, 0}};
+        dst.merge(src);
+        assert(map_equal(src, {}));
+        assert(map_equal(dst, {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {5, 0}, {5, 0}}));
+    }
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+    {
+        bool do_throw = false;
+        typedef std::unordered_multimap<Counter<int>, int, throw_hasher<Counter<int>>> map_type;
+        map_type src({{1, 0}, {3, 0}, {5, 0}}, 0, throw_hasher<Counter<int>>(do_throw));
+        map_type dst({{2, 0}, {4, 0}, {5, 0}}, 0, throw_hasher<Counter<int>>(do_throw));
+
+        assert(Counter_base::gConstructed == 6);
+
+        do_throw = true;
+        try
+        {
+            dst.merge(src);
+        }
+        catch (int)
+        {
+            do_throw = false;
+        }
+        assert(!do_throw);
+        assert(map_equal(src, map_type({{1, 0}, {3, 0}, {5, 0}}, 0, throw_hasher<Counter<int>>(do_throw))));
+        assert(map_equal(dst, map_type({{2, 0}, {4, 0}, {5, 0}}, 0, throw_hasher<Counter<int>>(do_throw))));
+    }
+#endif
+    assert(Counter_base::gConstructed == 0);
+    struct equal
+    {
+        equal() = default;
+
+        bool operator()(const Counter<int>& lhs, const Counter<int>& rhs) const
+        {
+            return lhs == rhs;
+        }
+    };
+    struct hasher
+    {
+        hasher() = default;
+        typedef Counter<int> argument_type;
+        typedef size_t result_type;
+        size_t operator()(const Counter<int>& p) const
+        {
+            return std::hash<Counter<int>>()(p);
+        }
+    };
+    {
+        typedef std::unordered_multimap<Counter<int>, int, std::hash<Counter<int>>, std::equal_to<Counter<int>>> first_map_type;
+        typedef std::unordered_multimap<Counter<int>, int, hasher, equal> second_map_type;
+        typedef std::unordered_map<Counter<int>, int, hasher, equal> third_map_type;
+
+        first_map_type first{{1, 0}, {2, 0}, {3, 0}};
+        second_map_type second{{2, 0}, {3, 0}, {4, 0}};
+        third_map_type third{{1, 0}, {3, 0}};
+
+        assert(Counter_base::gConstructed == 8);
+
+        first.merge(second);
+        first.merge(std::move(second));
+        first.merge(third);
+        first.merge(std::move(third));
+
+        assert(map_equal(first, {{1, 0}, {2, 0}, {3, 0}, {4, 0}, {2, 0}, {3, 0}, {1, 0}, {3, 0}}));
+        assert(map_equal(second, {}));
+        assert(map_equal(third, {}));
+
+        assert(Counter_base::gConstructed == 8);
+    }
+    assert(Counter_base::gConstructed == 0);
+    {
+        std::unordered_multimap<int, int> first;
+        {
+            std::unordered_multimap<int, int> second;
+            first.merge(second);
+            first.merge(std::move(second));
+        }
+        {
+            std::unordered_map<int, int> second;
+            first.merge(second);
+            first.merge(std::move(second));
+        }
+    }
+}

libcxx/test/std/containers/unord/unord.multiset/insert_extract.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_set>
+
+// class unordered_multiset
+
+#include <unordered_set>
+#include <type_traits>
+#include <iterator>
+#include "min_allocator.h"
+#include "Counter.h"
+
+namespace test_extract
+{
+using the_set = std::unordered_multiset<int>;
+
+static void doit()
+{
+    the_set s;
+    s.insert(1);
+    s.insert(2);
+    s.insert(3);
+    assert(s.size() == 3);
+
+    the_set::node_type handle = s.extract(2);
+    assert(s.size() == 2);
+    assert(s.count(1) == 1 && s.count(3) == 1);
+    the_set::iterator i = s.begin();
+    std::advance(i, 2);
+    assert(i == s.end());
+}
+}
+
+namespace test_count_dtors
+{
+typedef std::unordered_multiset<Counter<int>> set_type;
+
+static void doit()
+{
+    {
+        set_type dtc;
+        for (int i = 0; i != 10; ++i)
+            dtc.emplace(i);
+
+        assert(Counter_base::gConstructed == 10);
+        assert(dtc.size() == 10);
+
+        set_type::node_type nh3 = dtc.extract(Counter<int>(3));
+        set_type::node_type nh0 = dtc.extract(Counter<int>(0));
+        set_type::node_type nh9 = dtc.extract(Counter<int>(9));
+
+        assert(Counter_base::gConstructed == 10);
+        assert(dtc.size() == 7);
+
+        dtc.insert(std::move(nh3));
+        assert(dtc.size() == 8);
+
+        assert(Counter_base::gConstructed == 10);
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_min_alloc
+{
+typedef std::unordered_multiset<int, std::hash<int>, std::equal_to<int>, min_allocator<int>> set_type;
+
+static void doit()
+{
+    set_type st;
+    st.insert(10);
+    set_type::node_type nt = st.extract(10);
+    assert(!nt.empty());
+    assert(st.empty());
+    st.insert(std::move(nt));
+    assert(st.size() == 1);
+}
+}
+
+namespace test_handle_operations
+{
+typedef std::unordered_multiset<Counter<int>, std::hash<Counter<int>>, std::equal_to<Counter<int>>, min_allocator<Counter<int>>> set_type;
+
+static void doit()
+{
+    set_type::node_type nh;
+    assert(!static_cast<bool>(nh));
+
+    {
+        set_type st = {1, 2, 3, 4, 5};
+        assert(Counter_base::gConstructed == 5);
+        while (!st.empty())
+        {
+            nh = st.extract(st.begin());
+        }
+        assert(st.size() == 0);
+        assert(Counter_base::gConstructed == 1);
+        assert(static_cast<bool>(nh));
+    }
+
+    {
+        set_type other;
+        other.insert(std::move(nh));
+        assert(other.size() == 1);
+        assert(!static_cast<bool>(nh));
+    }
+
+    assert(Counter_base::gConstructed == 0);
+
+    {
+        set_type::node_type a, b;
+        std::swap(a, b);
+        set_type s = {42, 24};
+        assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+        a = s.extract(s.begin());
+        a.swap(b);
+        assert(!static_cast<bool>(a) && static_cast<bool>(b));
+        s.insert(std::move(b));
+        assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+        a = s.extract(s.begin());
+        b = s.extract(s.begin());
+        assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+        Counter<int>* aval = &a.value();
+        Counter<int>* bval = &b.value();
+        assert(aval->get() == 24);
+        assert(bval->get() == 42);
+
+        swap(a, b);
+        assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+        aval = &a.value();
+        bval = &b.value();
+        assert(aval->get() == 42);
+        assert(bval->get() == 24);
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+int main()
+{
+    test_extract::doit();
+    test_count_dtors::doit();
+    test_min_alloc::doit();
+    test_handle_operations::doit();
+}

libcxx/test/std/containers/unord/unord.multiset/merge.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_set>
+
+// class unordered_multiset
+
+// template <class C2>
+//   void merge(unordered_multiset<key_type, C2, allocator_type>& source);
+
+#include <unordered_set>
+#include "Counter.h"
+
+template <class Set>
+bool set_equal(const Set& set, Set other)
+{
+    return set == other;
+}
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+template <class T>
+struct throw_hasher
+{
+    bool& should_throw_;
+
+    throw_hasher(bool& should_throw) : should_throw_(should_throw) {}
+
+    typedef size_t result_type;
+    typedef T argument_type;
+
+    size_t operator()(const T& p) const
+    {
+        if (should_throw_)
+            throw 0;
+        return std::hash<T>()(p);
+    }
+};
+#endif
+
+int main()
+{
+    {
+        std::unordered_multiset<int> src{1, 3, 5};
+        std::unordered_multiset<int> dst{2, 4, 5};
+        dst.merge(src);
+        assert(set_equal(src, {}));
+        assert(set_equal(dst, {1, 2, 3, 4, 5, 5}));
+    }
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+    {
+        bool do_throw = false;
+        typedef std::unordered_multiset<Counter<int>, throw_hasher<Counter<int>>> set_type;
+        set_type src({1, 3, 5}, 0, throw_hasher<Counter<int>>(do_throw));
+        set_type dst({2, 4, 5}, 0, throw_hasher<Counter<int>>(do_throw));
+
+        assert(Counter_base::gConstructed == 6);
+
+        do_throw = true;
+        try
+        {
+            dst.merge(src);
+        }
+        catch (int)
+        {
+            do_throw = false;
+        }
+        assert(!do_throw);
+        assert(set_equal(src, set_type({1, 3, 5}, 0, throw_hasher<Counter<int>>(do_throw))));
+        assert(set_equal(dst, set_type({2, 4, 5}, 0, throw_hasher<Counter<int>>(do_throw))));
+    }
+#endif
+    assert(Counter_base::gConstructed == 0);
+    struct equal
+    {
+        equal() = default;
+
+        bool operator()(const Counter<int>& lhs, const Counter<int>& rhs) const
+        {
+            return lhs == rhs;
+        }
+    };
+    struct hasher
+    {
+        hasher() = default;
+        typedef Counter<int> argument_type;
+        typedef size_t result_type;
+        size_t operator()(const Counter<int>& p) const { return std::hash<Counter<int>>()(p); }
+    };
+    {
+        typedef std::unordered_multiset<Counter<int>, std::hash<Counter<int>>, std::equal_to<Counter<int>>> first_set_type;
+        typedef std::unordered_multiset<Counter<int>, hasher, equal> second_set_type;
+        typedef std::unordered_set<Counter<int>, hasher, equal> third_set_type;
+
+        first_set_type first{1, 2, 3};
+        second_set_type second{2, 3, 4};
+        third_set_type third{1, 3};
+
+        assert(Counter_base::gConstructed == 8);
+
+        first.merge(second);
+        first.merge(std::move(second));
+        first.merge(third);
+        first.merge(std::move(third));
+
+        assert(set_equal(first, {1, 2, 3, 4, 2, 3, 1, 3}));
+        assert(set_equal(second, {}));
+        assert(set_equal(third, {}));
+
+        assert(Counter_base::gConstructed == 8);
+    }
+    assert(Counter_base::gConstructed == 0);
+    {
+        std::unordered_multiset<int> first;
+        {
+            std::unordered_multiset<int> second;
+            first.merge(second);
+            first.merge(std::move(second));
+        }
+        {
+            std::unordered_set<int> second;
+            first.merge(second);
+            first.merge(std::move(second));
+        }
+    }
+}

libcxx/test/std/containers/unord/unord.set/insert_extract.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_set>
+
+// class unordered_set
+
+#include <unordered_set>
+#include <type_traits>
+#include <iterator>
+#include "min_allocator.h"
+#include "Counter.h"
+
+namespace test_irt
+{
+typedef std::unordered_set<int> int_set_type;
+using intIRT = int_set_type::insert_return_type;
+static_assert(std::is_move_constructible<intIRT>::value &&
+              std::is_move_assignable<intIRT>::value &&
+              std::is_default_constructible<intIRT>::value &&
+              std::is_destructible<intIRT>::value, "");
+
+typedef std::unordered_set<Counter<int>, std::hash<Counter<int>>,
+                           std::equal_to<Counter<int>>,
+                           min_allocator<Counter<int>>> set_type;
+using minIRT = set_type::insert_return_type;
+
+static_assert(std::is_move_constructible<minIRT>::value &&
+              std::is_move_assignable<minIRT>::value &&
+              std::is_default_constructible<minIRT>::value &&
+              std::is_destructible<minIRT>::value, "");
+
+static void doit()
+{
+    {
+        intIRT a, b;
+        std::swap(a, b);
+
+        minIRT c, d;
+        std::swap(c, d);
+    }
+
+    {
+        set_type st = {0};
+        set_type::node_type nh = st.extract(st.begin());
+        set_type::insert_return_type irt = st.insert(std::move(nh));
+        assert(irt.inserted);
+        assert(irt.position == st.begin());
+        assert(irt.node.empty());
+    }
+
+    {
+        set_type st = {0};
+        set_type::node_type nh = st.extract(st.begin());
+        st.insert(0);
+        set_type::insert_return_type irt = st.insert(std::move(nh));
+        assert(!irt.inserted);
+        assert(irt.position == st.begin());
+        assert(!irt.node.empty());
+    }
+
+    {
+        set_type st;
+        set_type::node_type nh;
+        set_type::insert_return_type irt = st.insert(std::move(nh));
+        assert(!irt.inserted);
+        assert(irt.position == st.end());
+        assert(irt.node.empty());
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_extract
+{
+using the_set = std::unordered_set<int>;
+
+static void doit()
+{
+    the_set s;
+    s.insert(1);
+    s.insert(2);
+    s.insert(3);
+    assert(s.size() == 3);
+
+    the_set::node_type handle = s.extract(2);
+    assert(s.size() == 2);
+    assert(s.count(1) == 1 && s.count(3) == 1);
+    the_set::iterator i = s.begin();
+    std::advance(i, 2);
+    assert(i == s.end());
+}
+}
+
+namespace test_count_dtors
+{
+typedef std::unordered_set<Counter<int>> set_type;
+
+static void doit()
+{
+    {
+        set_type dtc;
+        for (int i = 0; i != 10; ++i)
+            dtc.emplace(i);
+
+        assert(Counter_base::gConstructed == 10);
+        assert(dtc.size() == 10);
+
+        set_type::node_type nh3 = dtc.extract(Counter<int>(3));
+        set_type::node_type nh0 = dtc.extract(Counter<int>(0));
+        set_type::node_type nh9 = dtc.extract(Counter<int>(9));
+
+        assert(Counter_base::gConstructed == 10);
+        assert(dtc.size() == 7);
+
+        dtc.insert(std::move(nh3));
+        assert(dtc.size() == 8);
+
+        assert(Counter_base::gConstructed == 10);
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+namespace test_min_alloc
+{
+typedef std::unordered_set<int, std::hash<int>, std::equal_to<int>, min_allocator<int>> set_type;
+
+static void doit()
+{
+    set_type st;
+    st.insert(10);
+    set_type::node_type nt = st.extract(10);
+    assert(!nt.empty());
+    assert(st.empty());
+    st.insert(std::move(nt));
+    assert(st.size() == 1);
+}
+}
+
+namespace test_handle_operations
+{
+typedef std::unordered_set<Counter<int>, std::hash<Counter<int>>, std::equal_to<Counter<int>>, min_allocator<Counter<int>>> set_type;
+
+static void doit()
+{
+    set_type::node_type nh;
+    assert(!static_cast<bool>(nh));
+
+    {
+        set_type st = {1, 2, 3, 4, 5};
+        assert(Counter_base::gConstructed == 5);
+        while (!st.empty())
+        {
+            nh = st.extract(st.begin());
+        }
+        assert(st.size() == 0);
+        assert(Counter_base::gConstructed == 1);
+        assert(static_cast<bool>(nh));
+    }
+
+    {
+        set_type other;
+        other.insert(std::move(nh));
+        assert(other.size() == 1);
+        assert(!static_cast<bool>(nh));
+    }
+
+    assert(Counter_base::gConstructed == 0);
+
+    {
+        set_type::node_type a, b;
+        std::swap(a, b);
+        set_type s = {42, 24};
+        assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+        a = s.extract(s.begin());
+        a.swap(b);
+        assert(!static_cast<bool>(a) && static_cast<bool>(b));
+        s.insert(std::move(b));
+        assert(!static_cast<bool>(a) && !static_cast<bool>(b));
+        a = s.extract(s.begin());
+        b = s.extract(s.begin());
+        assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+        Counter<int>* aval = &a.value();
+        Counter<int>* bval = &b.value();
+        assert(aval->get() == 24);
+        assert(bval->get() == 42);
+
+        swap(a, b);
+        assert(static_cast<bool>(a) && static_cast<bool>(b));
+
+        aval = &a.value();
+        bval = &b.value();
+        assert(aval->get() == 42);
+        assert(bval->get() == 24);
+    }
+
+    assert(Counter_base::gConstructed == 0);
+}
+}
+
+int main()
+{
+    test_irt::doit();
+    test_extract::doit();
+    test_count_dtors::doit();
+    test_min_alloc::doit();
+    test_handle_operations::doit();
+}

libcxx/test/std/containers/unord/unord.set/merge.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14
+
+// <unordered_set>
+
+// class unordered_set
+
+// template <class C2>
+//   void merge(unordered_set<key_type, C2, allocator_type>& source);
+
+#include <unordered_set>
+#include "Counter.h"
+
+template <class Set>
+bool set_equal(const Set& set, Set other)
+{
+    return set == other;
+}
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+template <class T>
+struct throw_hasher
+{
+    bool& should_throw_;
+
+    throw_hasher(bool& should_throw) : should_throw_(should_throw) {}
+
+    typedef size_t result_type;
+    typedef T argument_type;
+
+    size_t operator()(const T& p) const
+    {
+        if (should_throw_)
+            throw 0;
+        return std::hash<T>()(p);
+    }
+};
+#endif
+
+int main()
+{
+    {
+        std::unordered_set<int> src{1, 3, 5};
+        std::unordered_set<int> dst{2, 4, 5};
+        dst.merge(src);
+        assert(set_equal(src, {5}));
+        assert(set_equal(dst, {1, 2, 3, 4, 5}));
+    }
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+    {
+        bool do_throw = false;
+        typedef std::unordered_set<Counter<int>, throw_hasher<Counter<int>>> set_type;
+        set_type src({1, 3, 5}, 0, throw_hasher<Counter<int>>(do_throw));
+        set_type dst({2, 4, 5}, 0, throw_hasher<Counter<int>>(do_throw));
+
+        assert(Counter_base::gConstructed == 6);
+
+        do_throw = true;
+        try
+        {
+            dst.merge(src);
+        }
+        catch (int)
+        {
+            do_throw = false;
+        }
+        assert(!do_throw);
+        assert(set_equal(src, set_type({1, 3, 5}, 0, throw_hasher<Counter<int>>(do_throw))));
+        assert(set_equal(dst, set_type({2, 4, 5}, 0, throw_hasher<Counter<int>>(do_throw))));
+    }
+#endif
+    assert(Counter_base::gConstructed == 0);
+    struct equal
+    {
+        equal() = default;
+
+        bool operator()(const Counter<int>& lhs, const Counter<int>& rhs) const
+        {
+            return lhs == rhs;
+        }
+    };
+    struct hasher
+    {
+        hasher() = default;
+        typedef Counter<int> argument_type;
+        typedef size_t result_type;
+        size_t operator()(const Counter<int>& p) const { return std::hash<Counter<int>>()(p); }
+    };
+    {
+        typedef std::unordered_set<Counter<int>, std::hash<Counter<int>>, std::equal_to<Counter<int>>> first_set_type;
+        typedef std::unordered_set<Counter<int>, hasher, equal> second_set_type;
+        typedef std::unordered_multiset<Counter<int>, hasher, equal> third_set_type;
+
+        first_set_type first{1, 2, 3};
+        second_set_type second{2, 3, 4};
+        third_set_type third{1, 3};
+
+        assert(Counter_base::gConstructed == 8);
+
+        first.merge(second);
+        first.merge(std::move(second));
+        first.merge(third);
+        first.merge(std::move(third));
+
+        assert(set_equal(first, {1, 2, 3, 4}));
+        assert(set_equal(second, {2, 3}));
+        assert(set_equal(third, {1, 3}));
+
+        assert(Counter_base::gConstructed == 8);
+    }
+    assert(Counter_base::gConstructed == 0);
+    {
+        std::unordered_set<int> first;
+        {
+            std::unordered_set<int> second;
+            first.merge(second);
+            first.merge(std::move(second));
+        }
+        {
+            std::unordered_multiset<int> second;
+            first.merge(second);
+            first.merge(std::move(second));
+        }
+    }
+}

libcxx/test/support/Counter.h

 namespace std {
 
 template <class T>
 struct hash<Counter<T> >
 {
     typedef Counter<T> argument_type;
     typedef std::size_t result_type;
 
-    std::size_t operator()(const Counter<T>& x) const {return std::hash<T>(x.get());}
+    std::size_t operator()(const Counter<T>& x) const {return std::hash<T>()(x.get());}
 };
 }
 
 #endif