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

[erik.pilkington]

Summary

This was originally part of https://reviews.llvm.org/D46845, but I decided to split it out to clean up the diff. From that patch's description:

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.

Thanks for taking a look!
Erik

[erik.pilkington]

In this new patch:

• Rebase on top of changes in https://reviews.llvm.org/D46845
• Move in some forward decls that I accidentally left in https://reviews.llvm.org/D46845
• Add some missing visibility attributes
• Add merge to header summaries

[erik.pilkington]

Ping!

[erik.pilkington]

Ping!

[erik.pilkington]

Ping!

[erik.pilkington]

Ping! In the new patch:

• Uncomment __cpp_lib_node_extract, reverting r340544
• Rebase/Clean up the diff a bit

[erik.pilkington]

Ping!

[erik.pilkington]

Ping!

[erik.pilkington]

Ping!

[erik.pilkington]

Pong!

[ldionne]

When merging a multi-container into a unique-container (e.g. map.merge(multimap) or set.merge(multiset)), I think we could do the following optimization: Once we've inserted an element from the multimap into the map, we could skip all the following equivalent elements in the multimap without having to perform a search in the map each time (since we know we won't insert the element anyway). Actually, I think we could do the same when we've found an element in the map and don't insert anything too. Basically something like this:

template <class _Tp, class _Compare, class _Allocator>
template <class _Tree>
_LIBCPP_INLINE_VISIBILITY
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) {
            // Here, increment __i until the key in the source is not equivalent to the key we found in *this.
            continue;
        } else {
            __source.__remove_node_pointer(__src_ptr);
            __insert_node_at(__parent, __child,
                             static_cast<__node_base_pointer>(__src_ptr));
            // Here, increment __i until the key in the source is not equivalent to the key we just inserted in *this.
        }
    }
}

I guess the underlying idea is to move forward as much as possible in __source once we've put our hands on an element in *this, since we don't have to re-lookup in *this as long as the keys in __source are equivalent to the one we just processed. Do you think this optimization is (1) valid and (2) worth trying out?

libcxx/include/__hash_table

1879

Can you add a quick comment that documents what this does, and what it returns?

1910

Ditto for documentation.

1940

Consider using a more descriptive name for __ndptr.

1958

Ditto for documentation.

2303

Consider using __source.remove(__it).release(); ++it; instead -- it's a bit more straightforward. Also, I think you could hoist the ++__it outside of the if altogether and get rid of the else branch.

2356

Same comment as above for __it++.

libcxx/include/__tree

2500

Do I understand correctly that __child != nullptr if and only if the key is already in *this, in which case we continue to skip the insertion (because that is a container with unique keys)?

The comment in __find_equal says

// Find place to insert if __v doesn't exist
// Set __parent to parent of null leaf
// Return reference to null leaf
// If __v exists, set parent to node of __v and return reference to node of __v

It looks like the "more correct" check to see whether the key already exists in *this would have been if (__child == __parent) -- is that correct?

2502

This doesn't throw, right? Would it make sense to mark __remove_node_pointer as noexcept? __tree_remove already is.

2503

This doesn't throw, right? Would it make sense to mark __insert_node_at as noexcept? __tree_balance_after_insert already is.

2557

So this always returns a reference to the null leaf that should be replaced by the new node, correct?

2562

Regarding static casting from __node_pointer to __node_base_pointer -- is this actually guaranteed to work for fancy pointer types? I don't think it is -- I think only casting to void_ptr and then back to __node_base_pointer would work per the Allocator concept requirements.

Note that in practice, a fancy pointer that would not support that would be misbehaved. Also, this problem already exists elsewhere in the code. I'm asking just for curiosity, I don't expect you to act on this comment in any way.

libcxx/include/map

946

Does this have to be public? Would doing otherwise require adding awkward friend declarations?

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

18

I think you mean map<key_type, value_type, C2, allocator_type>& source);. Also, you should mention the && overload.

Can you also please add tests that perform dst.merge(std::move(src)) before having done dst.merge(src) (the non-move version). Right now, we only seem to test that dst.merge(std::move(src)) works when the operation is a no-op anyway.

This comment applies to the other containers as well.

[rsmith]

In D48896#1274779, @ldionne wrote:

When merging a multi-container into a unique-container (e.g. map.merge(multimap) or set.merge(multiset)), I think we could do the following optimization: Once we've inserted an element from the multimap into the map, we could skip all the following equivalent elements in the multimap without having to perform a search in the map each time (since we know we won't insert the element anyway).

We can only do that if the comparators divide elements into the same equivalence classes, which we cannot know in general. (We can do this optimization if we can prove the comparator is a pure stateless function, but we probably can't detect that -- even an empty class type could store its state outside the class.) However, if the source and destination have the same comparator, and that comparator is std::less<T>, then I think it's correct to do this optimization.

[rsmith]

In D48896#1274919, @rsmith wrote:

In D48896#1274779, @ldionne wrote:

When merging a multi-container into a unique-container (e.g. map.merge(multimap) or set.merge(multiset)), I think we could do the following optimization: Once we've inserted an element from the multimap into the map, we could skip all the following equivalent elements in the multimap without having to perform a search in the map each time (since we know we won't insert the element anyway).

We can only do that if the comparators divide elements into the same equivalence classes, which we cannot know in general. (We can do this optimization if we can prove the comparator is a pure stateless function, but we probably can't detect that -- even an empty class type could store its state outside the class.) However, if the source and destination have the same comparator, and that comparator is std::less<T>, then I think it's correct to do this optimization.

Hmm, actually, we can probably do this in more cases than that. If we use the *destination's* comparator to check for equivalent elements instead of the source's comparator (under the assumption that the destination order is usually the same as the source order), this would work. But more generally, can we just provide the location of the most-recently-inserted element as an insertion hint and get this optimization as a special case of a more general optimization? But maybe that's actually what you were suggesting (the difference is hidden behind the "key in the source is not equivalent to the [other] key" comments -- equivalent according to which comparator?).

[ldionne]

In D48896#1274919, @rsmith wrote:

In D48896#1274779, @ldionne wrote:

When merging a multi-container into a unique-container (e.g. map.merge(multimap) or set.merge(multiset)), I think we could do the following optimization: Once we've inserted an element from the multimap into the map, we could skip all the following equivalent elements in the multimap without having to perform a search in the map each time (since we know we won't insert the element anyway).

We can only do that if the comparators divide elements into the same equivalence classes, which we cannot know in general. (We can do this optimization if we can prove the comparator is a pure stateless function, but we probably can't detect that -- even an empty class type could store its state outside the class.) However, if the source and destination have the same comparator, and that comparator is std::less<T>, then I think it's correct to do this optimization.

Ah, so you mean if the two comparators were both valid but different strict weak orderings? Yes, I guess that kills my optimization in the general case. I think it would be possible to enable the optimization whenever the comparators for the map and the multimap are both stateless (std::is_empty) and the same. Then, I don't see a way they could be different orderings. (Note that we'd have to prove that a stateless comparator can't break this optimization by using global variables, which I think can be proven)

[ldionne]

In D48896#1274938, @rsmith wrote:

In D48896#1274919, @rsmith wrote:

We can only do that if the comparators divide elements into the same equivalence classes, which we cannot know in general. (We can do this optimization if we can prove the comparator is a pure stateless function, but we probably can't detect that -- even an empty class type could store its state outside the class.) However, if the source and destination have the same comparator, and that comparator is std::less<T>, then I think it's correct to do this optimization.

Hmm, actually, we can probably do this in more cases than that. If we use the *destination's* comparator to check for equivalent elements instead of the source's comparator (under the assumption that the destination order is usually the same as the source order), this would work.

Using the destination's comparator to perform this optimization is clever, and I believe it would work. This is much better than using the source's comparator when std::is_empty<SourceComparator> and std::is_same<SourceComparator, DestinationComparator> are both true.

But more generally, can we just provide the location of the most-recently-inserted element as an insertion hint and get this optimization as a special case of a more general optimization? But maybe that's actually what you were suggesting (the difference is hidden behind the "key in the source is not equivalent to the [other] key" comments -- equivalent according to which comparator?).

The insertion hint idea did cross my mind when I was thinking about this but I did not pursue it further. I think it may be a cleaner way to achieve what I'm suggesting.

[erik.pilkington]

Address review comments. Thanks!

[erik.pilkington]

In D48896#1274970, @ldionne wrote:

In D48896#1274938, @rsmith wrote:

In D48896#1274919, @rsmith wrote:

We can only do that if the comparators divide elements into the same equivalence classes, which we cannot know in general. (We can do this optimization if we can prove the comparator is a pure stateless function, but we probably can't detect that -- even an empty class type could store its state outside the class.) However, if the source and destination have the same comparator, and that comparator is std::less<T>, then I think it's correct to do this optimization.

Hmm, actually, we can probably do this in more cases than that. If we use the *destination's* comparator to check for equivalent elements instead of the source's comparator (under the assumption that the destination order is usually the same as the source order), this would work.

Using the destination's comparator to perform this optimization is clever, and I believe it would work. This is much better than using the source's comparator when std::is_empty<SourceComparator> and std::is_same<SourceComparator, DestinationComparator> are both true.

But more generally, can we just provide the location of the most-recently-inserted element as an insertion hint and get this optimization as a special case of a more general optimization? But maybe that's actually what you were suggesting (the difference is hidden behind the "key in the source is not equivalent to the [other] key" comments -- equivalent according to which comparator?).

The insertion hint idea did cross my mind when I was thinking about this but I did not pursue it further. I think it may be a cleaner way to achieve what I'm suggesting.

I think the insertion hint idea is really slick. I tried it out, and it does provide some pretty significant improvements, particularly when merging multi-containers that have a lot of duplicate keys. I would probably prefer doing it in a follow-up though, rather than complicating this "just get it working naively" patch.

libcxx/include/__hash_table

1879

Sure, sorry, I was just trying to conform to libcxx's "no comments" rule ;)

1940

Sure, new patch calls this __existing_node

2303

Sure, I agree that simplifies this. The new patch hoists the ++__it out of the if.

2356

I don't think that __source.remove(__it).release(); ++it; works here because after __source.remove(__it), __it is no longer a valid iterator, so you can't increment it.

libcxx/include/__tree

2500

Do I understand correctly that __child != nullptr if and only if the key is already in *this, in which case we continue to skip the insertion (because that is a container with unique keys)?

Yep, exactly.

It looks like the "more correct" check to see whether the key already exists in *this would have been if (child == parent) -- is that correct?

__child == __parent and __child != nullptr should be equivalent. It looks like other users of __find_equal check __child != nullptr, why do you say that __child == __parent is "more correct"?

2502

Yep, I agree. New patch adds _NOEXCEPT.

2557

Yep, thats my understanding as well.

2562

Yep, I think you're analysis is right. Every (fancy) pointer conversion needs to go through void, but this doesn't. We actually do this a lot in this file. Do you think this actually matters in practice? Maybe @mclow.lists @EricWF have some thoughts?

libcxx/include/map

946

Yep, in order for m1.merge(m2) to work, someone needs access to both m1 and m2's __tree_s, which are currently private. On second thought, I think I'll just add the friend declarations, since it makes this a bit more explicit.

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

18

Sure, done in the new patch.

[ldionne]

In D48896#1281777, @erik.pilkington wrote:

I think the insertion hint idea is really slick. I tried it out, and it does provide some pretty significant improvements, particularly when merging multi-containers that have a lot of duplicate keys. I would probably prefer doing it in a follow-up though, rather than complicating this "just get it working naively" patch.

Works for me.

[ldionne]

LGTM after rewording the comment. Please do not forget to submit a follow-up for the optimization.

Thanks for the great work and for the patience in getting this reviewed.

libcxx/include/__hash_table

1356

Please reword this comment in terms of "assumes that rehashing has already occurred and that no element with the same key exists in the map" (or something like that). Don't assume people have called __node_insert_unique_prepare before -- this sort of comment can get stale.

2356

Good catch.

libcxx/include/__tree

2500

I found it matched the comment in __find_equal more closely, but that's subjective. Leave as-is.

2562

It probably doesn't matter in practice. My experience using fancy pointers is that none of the standard libraries work with them. Only Boost.Container does.

[erik.pilkington]

Thanks for reviewing!

libcxx/include/__node_handle

29 ↗

(On Diff #171864)

(FYI: I moved this to <version> in the final commit)

[mstorsjo]

libcxx/trunk/include/set

710 ↗

(On Diff #171960)

This broke certain cases of compilation with mingw-w64 headers, e.g. cases if <random> was included before <set>.

The root cause turned out to be that the mingw-w64 header yvals.h contains #define _C2 1: https://sourceforge.net/p/mingw-w64/mingw-w64/ci/master/tree/mingw-w64-headers/crt/yvals.h#l179

Similar versions of yvals.h from MSVC also contain a similar definition up to as recent as MSVC 2015 (no longer in 2017 though), where it is defined like this:

#define _C2                     1       /* 0 if not 2's complement */

Given this predecent and the fact that both libcxx and the other platform headers need to cooperate within the namespace of reserved identifiers starting with an underscore, would you consider using a different identifier here?

[ldionne]

libcxx/trunk/include/set

710 ↗

(On Diff #171960)

Fixed in r345834.

[mstorsjo]

libcxx/trunk/include/set

710 ↗

(On Diff #171960)

Thank you!

libcxx/include/__hash_table

     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

 #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 _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 _Table>
+    _LIBCPP_INLINE_VISIBILITY
+    void __node_handle_merge_multi(_Table& __source);
 
     template <class _NodeHandle>
     _LIBCPP_INLINE_VISIBILITY
     _NodeHandle __node_handle_extract(key_type const& __key);
     template <class _NodeHandle>
     _LIBCPP_INLINE_VISIBILITY
     _NodeHandle __node_handle_extract(const_iterator __it);
 #endif

         return const_local_iterator(nullptr, __n, bucket_count());
 #endif
     }
 
 #if _LIBCPP_DEBUG_LEVEL >= 2
 
     bool __dereferenceable(const const_iterator* __i) const;
     bool __decrementable(const const_iterator* __i) const;
     bool __addable(const const_iterator* __i, ptrdiff_t __n) const;
     bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;
 
 #endif  // _LIBCPP_DEBUG_LEVEL >= 2
 
 private:
     void __rehash(size_type __n);
 
 #ifndef _LIBCPP_CXX03_LANG

         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>

 _NodeHandle
 __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract(
     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 _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);
     size_type __bc = bucket_count();
     if (__n > __bc)
         __rehash(__n);
     else if (__n < __bc)
     {
         __n = _VSTD::max<size_type>
               (
                   __n,
                   __is_hash_power2(__bc) ? __next_hash_pow2(size_t(ceil(float(size()) / max_load_factor()))) :
                                            __next_prime(size_t(ceil(float(size()) / max_load_factor())))
               );

libcxx/include/__tree

 
 #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 _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 _Tree>
+    _LIBCPP_INLINE_VISIBILITY
+    void __node_handle_merge_multi(_Tree& __source);
 
 
     template <class _NodeHandle>
     _LIBCPP_INLINE_VISIBILITY
     _NodeHandle __node_handle_extract(key_type const&);
     template <class _NodeHandle>
     _LIBCPP_INLINE_VISIBILITY
     _NodeHandle __node_handle_extract(const_iterator);

 _NodeHandle
 __tree<_Tp, _Compare, _Allocator>::__node_handle_extract(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_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);
+        __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();
     __node_pointer __ptr = __nh.__ptr_;
     __parent_pointer __parent;
     __node_base_pointer& __child = __find_leaf_high(
         __parent, _NodeTypes::__get_key(__ptr->__value_));
     __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__ptr));
     __nh.__release();

     __parent_pointer __parent;
     __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 _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

         map(_InputIterator __f, _InputIterator __l,
             const key_compare& __comp = key_compare())
         : __tree_(__vc(__comp))
         {
             insert(__f, __l);
         }
 
     template <class _InputIterator>
     _LIBCPP_INLINE_VISIBILITY
         map(_InputIterator __f, _InputIterator __l,
             const key_compare& __comp, const allocator_type& __a)
         : __tree_(__vc(__comp), typename __base::allocator_type(__a))
         {
             insert(__f, __l);
         }
 
 #if _LIBCPP_STD_VER > 11

     {
         return __tree_.template __node_handle_extract<node_type>(__key);
     }
     _LIBCPP_INLINE_VISIBILITY
     node_type extract(const_iterator __it)
     {
         return __tree_.template __node_handle_extract<node_type>(__it.__i_);
     }
+    template <class _C2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(map<key_type, mapped_type, _C2, allocator_type>& __source)
+    {
+        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+                       "merging container with incompatible allocator");
+        __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)
+    {
+        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+                       "merging container with incompatible allocator");
+        __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)
+    {
+        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+                       "merging container with incompatible allocator");
+        __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)
+    {
+        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+                       "merging container with incompatible allocator");
+        __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

         return __tree_.template __node_handle_extract<node_type>(__key);
     }
     _LIBCPP_INLINE_VISIBILITY
     node_type extract(const_iterator __it)
     {
         return __tree_.template __node_handle_extract<node_type>(
             __it.__i_);
     }
+    template <class _C2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(multimap<key_type, mapped_type, _C2, allocator_type>& __source)
+    {
+        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+                       "merging container with incompatible allocator");
+        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)
+    {
+        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+                       "merging container with incompatible allocator");
+        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)
+    {
+        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+                       "merging container with incompatible allocator");
+        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)
+    {
+        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+                       "merging container with incompatible allocator");
+        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)

libcxx/include/set

     {
         return __tree_.template __node_handle_extract<node_type>(__key);
     }
     _LIBCPP_INLINE_VISIBILITY
     node_type extract(const_iterator __it)
     {
         return __tree_.template __node_handle_extract<node_type>(__it);
     }
+    template <class _C2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(set<key_type, _C2, allocator_type>& __source)
+    {
+        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+                       "merging container with incompatible allocator");
+        __tree_.__node_handle_merge_unique(__source.__get_tree());
+    }
+    template <class _C2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(set<key_type, _C2, allocator_type>&& __source)
+    {
+        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+                       "merging container with incompatible allocator");
+        __tree_.__node_handle_merge_unique(__source.__get_tree());
+    }
+    template <class _C2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(multiset<key_type, _C2, allocator_type>& __source)
+    {
+        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+                       "merging container with incompatible allocator");
+        __tree_.__node_handle_merge_unique(__source.__get_tree());
+    }
+    template <class _C2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(multiset<key_type, _C2, allocator_type>&& __source)
+    {
+        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+                       "merging container with incompatible allocator");
+        __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();}

     {
         return __tree_.template __node_handle_extract<node_type>(__key);
     }
     _LIBCPP_INLINE_VISIBILITY
     node_type extract(const_iterator __it)
     {
         return __tree_.template __node_handle_extract<node_type>(__it);
     }
+    template <class _C2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(multiset<key_type, _C2, allocator_type>& __source)
+    {
+        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+                       "merging container with incompatible allocator");
+        __tree_.__node_handle_merge_multi(__source.__get_tree());
+    }
+    template <class _C2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(multiset<key_type, _C2, allocator_type>&& __source)
+    {
+        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+                       "merging container with incompatible allocator");
+        __tree_.__node_handle_merge_multi(__source.__get_tree());
+    }
+    template <class _C2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(set<key_type, _C2, allocator_type>& __source)
+    {
+        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+                       "merging container with incompatible allocator");
+        __tree_.__node_handle_merge_multi(__source.__get_tree());
+    }
+    template <class _C2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(set<key_type, _C2, allocator_type>&& __source)
+    {
+        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+                       "merging container with incompatible allocator");
+        __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

libcxx/include/unordered_map

         return __table_.template __node_handle_extract<node_type>(__key);
     }
     _LIBCPP_INLINE_VISIBILITY
     node_type extract(const_iterator __it)
     {
         return __table_.template __node_handle_extract<node_type>(
             __it.__i_);
     }
+
+    template <class _H2, class _P2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& __source)
+    {
+        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+                       "merging container with incompatible allocator");
+        return __table_.__node_handle_merge_unique(__source.__get_table());
+    }
+    template <class _H2, class _P2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& __source)
+    {
+        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+                       "merging container with incompatible allocator");
+        return __table_.__node_handle_merge_unique(__source.__get_table());
+    }
+    template <class _H2, class _P2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& __source)
+    {
+        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+                       "merging container with incompatible allocator");
+        return __table_.__node_handle_merge_unique(__source.__get_table());
+    }
+    template <class _H2, class _P2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& __source)
+    {
+        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+                       "merging container with incompatible allocator");
+        return __table_.__node_handle_merge_unique(__source.__get_table());
+    }
 #endif
 
     _LIBCPP_INLINE_VISIBILITY
     void swap(unordered_map& __u)
         _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
         { __table_.swap(__u.__table_);}
 
     _LIBCPP_INLINE_VISIBILITY

         return __table_.template __node_handle_extract<node_type>(__key);
     }
     _LIBCPP_INLINE_VISIBILITY
     node_type extract(const_iterator __it)
     {
         return __table_.template __node_handle_extract<node_type>(
             __it.__i_);
     }
+
+    template <class _H2, class _P2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>& __source)
+    {
+        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+                       "merging container with incompatible allocator");
+        return __table_.__node_handle_merge_multi(__source.__get_table());
+    }
+    template <class _H2, class _P2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(unordered_multimap<key_type, mapped_type, _H2, _P2, allocator_type>&& __source)
+    {
+        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+                       "merging container with incompatible allocator");
+        return __table_.__node_handle_merge_multi(__source.__get_table());
+    }
+    template <class _H2, class _P2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>& __source)
+    {
+        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+                       "merging container with incompatible allocator");
+        return __table_.__node_handle_merge_multi(__source.__get_table());
+    }
+    template <class _H2, class _P2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(unordered_map<key_type, mapped_type, _H2, _P2, allocator_type>&& __source)
+    {
+        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+                       "merging container with incompatible allocator");
+        return __table_.__node_handle_merge_multi(__source.__get_table());
+    }
 #endif
 
     _LIBCPP_INLINE_VISIBILITY
     void swap(unordered_multimap& __u)
         _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
         {__table_.swap(__u.__table_);}
 
     _LIBCPP_INLINE_VISIBILITY

libcxx/include/unordered_set

     {
         return __table_.template __node_handle_extract<node_type>(__key);
     }
     _LIBCPP_INLINE_VISIBILITY
     node_type extract(const_iterator __it)
     {
         return __table_.template __node_handle_extract<node_type>(__it);
     }
+
+    template<class _H2, class _P2>
+    _LIBCPP_INLINE_VISIBILITY
+    void merge(unordered_set<key_type, _H2, _P2, allocator_type>& __source)
+    {
+        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+                       "merging container with incompatible allocator");
+        __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)
+    {
+        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+                       "merging container with incompatible allocator");
+        __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)
+    {
+        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+                       "merging container with incompatible allocator");
+        __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)
+    {
+        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+                       "merging container with incompatible allocator");
+        __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

     _LIBCPP_INLINE_VISIBILITY
     iterator insert(const_iterator __hint, node_type&& __nh)
     {
         _LIBCPP_ASSERT(__nh.empty() || __nh.get_allocator() == get_allocator(),
             "node_type with incompatible allocator passed to unordered_multiset::insert()");
         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)
+    {
+        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+                       "merging container with incompatible allocator");
+        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)
+    {
+        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+                       "merging container with incompatible allocator");
+        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)
+    {
+        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+                       "merging container with incompatible allocator");
+        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)
+    {
+        _LIBCPP_ASSERT(__source.get_allocator() == get_allocator(),
+                       "merging container with incompatible allocator");
+        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)

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 "test_macros.h"
+#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/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 "test_macros.h"
+#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/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 "test_macros.h"
+#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/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 "test_macros.h"
+#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/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 "test_macros.h"
+#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/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 "test_macros.h"
+#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/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 "test_macros.h"
+#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/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 "test_macros.h"
+#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));
+        }
+    }
+}