[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 ↗

(On Diff #164064)

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

1910 ↗

(On Diff #164064)

Ditto for documentation.

1940 ↗

(On Diff #164064)

Consider using a more descriptive name for __ndptr.

1958 ↗

(On Diff #164064)

Ditto for documentation.

2303 ↗

(On Diff #164064)

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 ↗

(On Diff #164064)

Same comment as above for __it++.

libcxx/include/__tree

2500 ↗

(On Diff #164064)

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 ↗

(On Diff #164064)

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

2503 ↗

(On Diff #164064)

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

2557 ↗

(On Diff #164064)

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

2562 ↗

(On Diff #164064)

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 ↗

(On Diff #164064)

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

17 ↗

(On Diff #164064)

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 ↗

(On Diff #164064)

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

1940 ↗

(On Diff #164064)

Sure, new patch calls this __existing_node

2303 ↗

(On Diff #164064)

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

2356 ↗

(On Diff #164064)

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 ↗

(On Diff #164064)

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 ↗

(On Diff #164064)

Yep, I agree. New patch adds _NOEXCEPT.

2557 ↗

(On Diff #164064)

Yep, thats my understanding as well.

2562 ↗

(On Diff #164064)

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 ↗

(On Diff #164064)

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

17 ↗

(On Diff #164064)

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 ↗

(On Diff #171864)

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 ↗

(On Diff #164064)

Good catch.

libcxx/include/__tree

2500 ↗

(On Diff #164064)

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

2562 ↗

(On Diff #164064)

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

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

Fixed in r345834.

[mstorsjo]

libcxx/trunk/include/set

710

Thank you!

libcxx/trunk/include/__hash_table

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

 #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
if (size() > 0)
         __p1_.first().__next_ = nullptr;
         size_type __bc = bucket_count();
         for (size_type __i = 0; __i < __bc; ++__i)
             __bucket_list_[__i] = nullptr;
         size() = 0;
     }
 }
 
+
+// Prepare the container for an insertion of the value __value with the hash
+// __hash. This does a lookup into the container to see if __value is already
+// present, and performs a rehash if necessary. Returns a pointer to the
+// existing element if it exists, otherwise nullptr.
+//
+// Note that this function does forward exceptions if key_eq() throws, and never
+// mutates __value or actually inserts into the map.
 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)
+_LIBCPP_INLINE_VISIBILITY
+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)
-        {
-            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();
-        }
-        __ndptr = __nd->__ptr();
-        // increment size
-        ++size();
+    return nullptr;
+}
+
+// Insert the node __nd into the container by pushing it into the right bucket,
+// and updating size(). Assumes that __nd->__hash is up-to-date, and that
+// rehashing has already occurred and that no element with the same key exists
+// in the map.
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+_LIBCPP_INLINE_VISIBILITY
+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);
+}
+
+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 __existing_node =
+        __node_insert_unique_prepare(__nd->__hash(), __nd->__value_);
+
+    // Insert the node, unless it already exists in the container.
+    bool __inserted = false;
+    if (__existing_node == nullptr)
+    {
+        __node_insert_unique_perform(__nd);
+        __existing_node = __nd->__ptr();
         __inserted = true;
     }
-__done:
 #if _LIBCPP_DEBUG_LEVEL >= 2
-    return pair<iterator, bool>(iterator(__ndptr, this), __inserted);
+    return pair<iterator, bool>(iterator(__existing_node, this), __inserted);
 #else
-    return pair<iterator, bool>(iterator(__ndptr), __inserted);
+    return pair<iterator, bool>(iterator(__existing_node), __inserted);
 #endif
 }
 
+// Prepare the container for an insertion of the value __cp_val with the hash
+// __cp_hash. This does a lookup into the container to see if __cp_value is
+// already present, and performs a rehash if necessary. Returns a pointer to the
+// last occurance of __cp_val in the map.
+//
+// Note that this function does forward exceptions if key_eq() throws, and never
+// mutates __value or actually inserts into the map.
 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;
+}
+
+// Insert the node __cp into the container after __pn (which is the last node in
+// the bucket that compares equal to __cp). Rehashing, and checking for
+// uniqueness has already been performed (in __node_insert_multi_prepare), so
+// all we need to do is update the bucket and size(). Assumes that __cp->__hash
+// is up-to-date.
+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>

 __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>
+_LIBCPP_INLINE_VISIBILITY
+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 __existing_node =
+            __node_insert_unique_prepare(__hash, __src_ptr->__value_);
+        auto __prev_iter = __it++;
+        if (__existing_node == nullptr)
+        {
+            (void)__source.remove(__prev_iter).release();
+            __src_ptr->__hash_ = __hash;
+            __node_insert_unique_perform(__src_ptr);
+        }
+    }
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
 template <class _NodeHandle>
 _LIBCPP_INLINE_VISIBILITY
 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();

 {
     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>
+_LIBCPP_INLINE_VISIBILITY
+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;

libcxx/trunk/include/__node_handle

 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 #if _LIBCPP_STD_VER > 14
 
-// FIXME: Uncomment this when we support the 'merge' functionality.
-// #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,
           template <class, class> class _MapOrSetSpecifics>
 class _LIBCPP_TEMPLATE_VIS __basic_node_handle
     : public _MapOrSetSpecifics<

libcxx/trunk/include/__tree

#else
     template <class _Vp>
     _LIBCPP_INLINE_VISIBILITY
     iterator __insert_multi(const_iterator __p, _Vp&& __v) {
         return __emplace_hint_multi(__p, _VSTD::forward<_Vp>(__v));
     }
 
 #endif // !_LIBCPP_CXX03_LANG
 
+    _LIBCPP_INLINE_VISIBILITY
     pair<iterator, bool> __node_insert_unique(__node_pointer __nd);
+    _LIBCPP_INLINE_VISIBILITY
     iterator             __node_insert_unique(const_iterator __p,
                                               __node_pointer __nd);
 
+    _LIBCPP_INLINE_VISIBILITY
     iterator __node_insert_multi(__node_pointer __nd);
+    _LIBCPP_INLINE_VISIBILITY
     iterator __node_insert_multi(const_iterator __p, __node_pointer __nd);
 
 
-    _LIBCPP_INLINE_VISIBILITY iterator __remove_node_pointer(__node_pointer);
+    _LIBCPP_INLINE_VISIBILITY iterator
+    __remove_node_pointer(__node_pointer) _NOEXCEPT;
 
 #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);
 #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,
                           __node_base_pointer& __child,
-                          __node_base_pointer __new_node);
+                          __node_base_pointer __new_node) _NOEXCEPT;
 
     template <class _Key>
         iterator find(const _Key& __v);
     template <class _Key>
         const_iterator find(const _Key& __v) const;
 
     template <class _Key>
         size_type __count_unique(const _Key& __k) const;
__tree<_Tp, _Compare, _Allocator>::__find_equal(const_iterator __hint,
     }
     // else __v == *__hint
     __parent = static_cast<__parent_pointer>(__hint.__ptr_);
     __dummy = static_cast<__node_base_pointer>(__hint.__ptr_);
     return __dummy;
 }
 
 template <class _Tp, class _Compare, class _Allocator>
-void
-__tree<_Tp, _Compare, _Allocator>::__insert_node_at(__parent_pointer     __parent,
-                                                    __node_base_pointer& __child,
-                                                    __node_base_pointer  __new_node)
+void __tree<_Tp, _Compare, _Allocator>::__insert_node_at(
+    __parent_pointer __parent, __node_base_pointer& __child,
+    __node_base_pointer __new_node) _NOEXCEPT
 {
     __new_node->__left_   = nullptr;
     __new_node->__right_  = nullptr;
     __new_node->__parent_ = __parent;
     // __new_node->__is_black_ is initialized in __tree_balance_after_insert
     __child = __new_node;
     if (__begin_node()->__left_ != nullptr)
         __begin_node() = static_cast<__iter_pointer>(__begin_node()->__left_);
__tree<_Tp, _Compare, _Allocator>::__node_insert_multi(const_iterator __p,
     __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>::__remove_node_pointer(__node_pointer __ptr)
+__tree<_Tp, _Compare, _Allocator>::__remove_node_pointer(__node_pointer __ptr) _NOEXCEPT
 {
     iterator __r(__ptr);
     ++__r;
     if (__begin_node() == __ptr)
         __begin_node() = __r.__ptr_;
     --size();
     __tree_remove(__end_node()->__left_,
                   static_cast<__node_base_pointer>(__ptr));

 __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>
+_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)
+            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>
 _LIBCPP_INLINE_VISIBILITY
 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_;
__tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi(
     __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>
+_LIBCPP_INLINE_VISIBILITY
+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);

libcxx/trunk/include/map

template <class M>
         iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);        // C++17
 
     iterator  erase(const_iterator position);
     iterator  erase(iterator position); // C++14
     size_type erase(const key_type& k);
     iterator  erase(const_iterator first, const_iterator last);
     void clear() noexcept;
 
+    template<class C2>
+      void merge(map<Key, T, C2, Allocator>& source);         // C++17
+    template<class C2>
+      void merge(map<Key, T, C2, Allocator>&& source);        // C++17
+    template<class C2>
+      void merge(multimap<Key, T, C2, Allocator>& source);    // C++17
+    template<class C2>
+      void merge(multimap<Key, T, C2, Allocator>&& source);   // C++17
+
     void swap(map& m)
         noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
             is_nothrow_swappable<key_compare>::value); // C++17
 
     // observers:
     allocator_type get_allocator() const noexcept;
     key_compare    key_comp()      const;
     value_compare  value_comp()    const;
public:
     iterator insert(const_iterator hint, node_type&& nh);                             // C++17
 
     iterator  erase(const_iterator position);
     iterator  erase(iterator position); // C++14
     size_type erase(const key_type& k);
     iterator  erase(const_iterator first, const_iterator last);
     void clear() noexcept;
 
+    template<class C2>
+      void merge(multimap<Key, T, C2, Allocator>& source);    // C++17
+    template<class C2>
+      void merge(multimap<Key, T, C2, Allocator>&& source);   // C++17
+    template<class C2>
+      void merge(map<Key, T, C2, Allocator>& source);         // C++17
+    template<class C2>
+      void merge(map<Key, T, C2, Allocator>&& source);        // C++17
+
     void swap(multimap& m)
         noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
             is_nothrow_swappable<key_compare>::value); // C++17
 
     // observers:
     allocator_type get_allocator() const noexcept;
     key_compare    key_comp()      const;
     value_compare  value_comp()    const;
public:
     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
 
+    template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
+        friend class _LIBCPP_TEMPLATE_VIS map;
+    template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
+        friend class _LIBCPP_TEMPLATE_VIS multimap;
+
     _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())) {}
 
#if _LIBCPP_STD_VER > 14
     {
         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.__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.__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.__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.__tree_);
+    }
 #endif
 
     _LIBCPP_INLINE_VISIBILITY
     void swap(map& __m)
         _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
         {__tree_.swap(__m.__tree_);}
 
     _LIBCPP_INLINE_VISIBILITY
public:
     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
 
+    template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
+        friend class _LIBCPP_TEMPLATE_VIS map;
+    template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
+        friend class _LIBCPP_TEMPLATE_VIS multimap;
+
     _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())) {}
 
node_type extract(key_type const& __key)
         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.__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.__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.__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.__tree_);
+    }
 #endif
 
     _LIBCPP_INLINE_VISIBILITY
     void clear() _NOEXCEPT {__tree_.clear();}
 
     _LIBCPP_INLINE_VISIBILITY
     void swap(multimap& __m)
         _NOEXCEPT_(__is_nothrow_swappable<__base>::value)

libcxx/trunk/include/set

public:
     iterator insert(const_iterator hint, node_type&& nh);                             // C++17
 
     iterator  erase(const_iterator position);
     iterator  erase(iterator position);  // C++14
     size_type erase(const key_type& k);
     iterator  erase(const_iterator first, const_iterator last);
     void clear() noexcept;
 
+    template<class C2>
+      void merge(set<Key, C2, Allocator>& source);         // C++17
+    template<class C2>
+      void merge(set<Key, C2, Allocator>&& source);        // C++17
+    template<class C2>
+      void merge(multiset<Key, C2, Allocator>& source);    // C++17
+    template<class C2>
+      void merge(multiset<Key, C2, Allocator>&& source);   // C++17
+
     void swap(set& s)
         noexcept(
             __is_nothrow_swappable<key_compare>::value &&
             (!allocator_type::propagate_on_container_swap::value ||
              __is_nothrow_swappable<allocator_type>::value));
 
     // observers:
     allocator_type get_allocator() const noexcept;
public:
     iterator insert(const_iterator hint, node_type&& nh);                             // C++17
 
     iterator  erase(const_iterator position);
     iterator  erase(iterator position);  // C++14
     size_type erase(const key_type& k);
     iterator  erase(const_iterator first, const_iterator last);
     void clear() noexcept;
 
+    template<class C2>
+      void merge(multiset<Key, C2, Allocator>& source);    // C++17
+    template<class C2>
+      void merge(multiset<Key, C2, Allocator>&& source);   // C++17
+    template<class C2>
+      void merge(set<Key, C2, Allocator>& source);         // C++17
+    template<class C2>
+      void merge(set<Key, C2, Allocator>&& source);        // C++17
+
     void swap(multiset& s)
         noexcept(
             __is_nothrow_swappable<key_compare>::value &&
             (!allocator_type::propagate_on_container_swap::value ||
              __is_nothrow_swappable<allocator_type>::value));
 
     // observers:
     allocator_type get_allocator() const noexcept;

 #include <version>
 
 #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 _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
 
+    template <class _Key2, class _Compare2, class _Alloc2>
+        friend class _LIBCPP_TEMPLATE_VIS set;
+    template <class _Key2, class _Compare2, class _Alloc2>
+        friend class _LIBCPP_TEMPLATE_VIS multiset;
+
     _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()) {}
 
#if _LIBCPP_STD_VER > 14
     {
         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.__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.__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.__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.__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();}
public:
     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
 
+    template <class _Key2, class _Compare2, class _Alloc2>
+        friend class _LIBCPP_TEMPLATE_VIS set;
+    template <class _Key2, class _Compare2, class _Alloc2>
+        friend class _LIBCPP_TEMPLATE_VIS multiset;
+
     // 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()) {}
#if _LIBCPP_STD_VER > 14
     {
         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.__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.__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.__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.__tree_);
+    }
 #endif
 
     _LIBCPP_INLINE_VISIBILITY
     void swap(multiset& __s)
         _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
         {__tree_.swap(__s.__tree_);}
 
     _LIBCPP_INLINE_VISIBILITY

libcxx/trunk/include/unordered_map

template <class M>
         iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);        // C++17
 
     iterator erase(const_iterator position);
     iterator erase(iterator position);  // C++14
     size_type erase(const key_type& k);
     iterator erase(const_iterator first, const_iterator last);
     void clear() noexcept;
 
+    template<class H2, class P2>
+      void merge(unordered_map<Key, T, H2, P2, Allocator>& source);         // C++17
+    template<class H2, class P2>
+      void merge(unordered_map<Key, T, H2, P2, Allocator>&& source);        // C++17
+    template<class H2, class P2>
+      void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source);    // C++17
+    template<class H2, class P2>
+      void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source);   // C++17
+
     void swap(unordered_map&)
         noexcept(
             (!allocator_type::propagate_on_container_swap::value ||
              __is_nothrow_swappable<allocator_type>::value) &&
             __is_nothrow_swappable<hasher>::value &&
             __is_nothrow_swappable<key_equal>::value);
 
     hasher hash_function() const;
public:
     iterator insert(const_iterator hint, node_type&& nh);      // C++17
 
     iterator erase(const_iterator position);
     iterator erase(iterator position);  // C++14
     size_type erase(const key_type& k);
     iterator erase(const_iterator first, const_iterator last);
     void clear() noexcept;
 
+    template<class H2, class P2>
+      void merge(unordered_multimap<Key, T, H2, P2, Allocator>& source);    // C++17
+    template<class H2, class P2>
+      void merge(unordered_multimap<Key, T, H2, P2, Allocator>&& source);   // C++17
+    template<class H2, class P2>
+      void merge(unordered_map<Key, T, H2, P2, Allocator>& source);         // C++17
+    template<class H2, class P2>
+      void merge(unordered_map<Key, T, H2, P2, Allocator>&& source);        // C++17
+
     void swap(unordered_multimap&)
         noexcept(
             (!allocator_type::propagate_on_container_swap::value ||
              __is_nothrow_swappable<allocator_type>::value) &&
             __is_nothrow_swappable<hasher>::value &&
             __is_nothrow_swappable<key_equal>::value);
 
     hasher hash_function() const;
friend _LIBCPP_INLINE_VISIBILITY
         {return __x.__i_ != __y.__i_;}
 
     template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_map;
     template <class, class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
     template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_iterator;
     template <class> friend class _LIBCPP_TEMPLATE_VIS __hash_const_local_iterator;
 };
 
+template <class _Key, class _Tp, class _Hash, class _Pred, class _Alloc>
+class unordered_multimap;
+
 template <class _Key, class _Tp, class _Hash = hash<_Key>, class _Pred = equal_to<_Key>,
           class _Alloc = allocator<pair<const _Key, _Tp> > >
 class _LIBCPP_TEMPLATE_VIS unordered_map
 {
 public:
     // types
     typedef _Key                                           key_type;
     typedef _Tp                                            mapped_type;
public:
     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
 
+    template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>
+        friend class _LIBCPP_TEMPLATE_VIS unordered_map;
+    template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>
+        friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
+
     _LIBCPP_INLINE_VISIBILITY
     unordered_map()
         _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
         {
 #if _LIBCPP_DEBUG_LEVEL >= 2
             __get_db()->__insert_c(this);
 #endif
         }
node_type extract(key_type const& __key)
         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.__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.__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.__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.__table_);
+    }
 #endif
 
     _LIBCPP_INLINE_VISIBILITY
     void swap(unordered_map& __u)
         _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
         { __table_.swap(__u.__table_);}
 
     _LIBCPP_INLINE_VISIBILITY
public:
     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
 
+    template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>
+        friend class _LIBCPP_TEMPLATE_VIS unordered_map;
+    template <class _Key2, class _Tp2, class _Hash2, class _Pred2, class _Alloc2>
+        friend class _LIBCPP_TEMPLATE_VIS unordered_multimap;
+
     _LIBCPP_INLINE_VISIBILITY
     unordered_multimap()
         _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
         {
 #if _LIBCPP_DEBUG_LEVEL >= 2
             __get_db()->__insert_c(this);
 #endif
         }
node_type extract(key_type const& __key)
         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.__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.__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.__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.__table_);
+    }
 #endif
 
     _LIBCPP_INLINE_VISIBILITY
     void swap(unordered_multimap& __u)
         _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
         {__table_.swap(__u.__table_);}
 
     _LIBCPP_INLINE_VISIBILITY

libcxx/trunk/include/unordered_set

public:
     iterator           insert(const_iterator hint, node_type&& nh);   // C++17
 
     iterator erase(const_iterator position);
     iterator erase(iterator position);  // C++14
     size_type erase(const key_type& k);
     iterator erase(const_iterator first, const_iterator last);
     void clear() noexcept;
 
+    template<class H2, class P2>
+      void merge(unordered_set<Key, H2, P2, Allocator>& source);         // C++17
+    template<class H2, class P2>
+      void merge(unordered_set<Key, H2, P2, Allocator>&& source);        // C++17
+    template<class H2, class P2>
+      void merge(unordered_multiset<Key, H2, P2, Allocator>& source);    // C++17
+    template<class H2, class P2>
+      void merge(unordered_multiset<Key, H2, P2, Allocator>&& source);   // C++17
+
     void swap(unordered_set&)
        noexcept(allocator_traits<Allocator>::is_always_equal::value &&
                  noexcept(swap(declval<hasher&>(), declval<hasher&>())) &&
                  noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17
 
     hasher hash_function() const;
     key_equal key_eq() const;
 
public:
     iterator insert(const_iterator hint, node_type&& nh);   // C++17
 
     iterator erase(const_iterator position);
     iterator erase(iterator position);  // C++14
     size_type erase(const key_type& k);
     iterator erase(const_iterator first, const_iterator last);
     void clear() noexcept;
 
+    template<class H2, class P2>
+      void merge(unordered_multiset<Key, H2, P2, Allocator>& source);    // C++17
+    template<class H2, class P2>
+      void merge(unordered_multiset<Key, H2, P2, Allocator>&& source);   // C++17
+    template<class H2, class P2>
+      void merge(unordered_set<Key, H2, P2, Allocator>& source);         // C++17
+    template<class H2, class P2>
+      void merge(unordered_set<Key, H2, P2, Allocator>&& source);        // C++17
+
     void swap(unordered_multiset&)
        noexcept(allocator_traits<Allocator>::is_always_equal::value &&
                  noexcept(swap(declval<hasher&>(), declval<hasher&>())) &&
                  noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17
 
     hasher hash_function() const;
     key_equal key_eq() const;
 

 #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::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
 
+    template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
+        friend class _LIBCPP_TEMPLATE_VIS unordered_set;
+    template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
+        friend class _LIBCPP_TEMPLATE_VIS unordered_multiset;
+
     _LIBCPP_INLINE_VISIBILITY
     unordered_set()
         _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
         {
 #if _LIBCPP_DEBUG_LEVEL >= 2
             __get_db()->__insert_c(this);
 #endif
         }
#if _LIBCPP_STD_VER > 14
     {
         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.__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.__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.__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.__table_);
+    }
 #endif
 
     _LIBCPP_INLINE_VISIBILITY
     void swap(unordered_set& __u)
         _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
         {__table_.swap(__u.__table_);}
 
     _LIBCPP_INLINE_VISIBILITY
public:
     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
 
+    template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
+        friend class _LIBCPP_TEMPLATE_VIS unordered_set;
+    template <class _Value2, class _Hash2, class _Pred2, class _Alloc2>
+        friend class _LIBCPP_TEMPLATE_VIS unordered_multiset;
+
     _LIBCPP_INLINE_VISIBILITY
     unordered_multiset()
         _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
         {
 #if _LIBCPP_DEBUG_LEVEL >= 2
             __get_db()->__insert_c(this);
 #endif
         }
node_type extract(const_iterator __position)
         return __table_.template __node_handle_extract<node_type>(
             __position);
     }
     _LIBCPP_INLINE_VISIBILITY
     node_type extract(key_type const& __key)
     {
         return __table_.template __node_handle_extract<node_type>(__key);
     }
+
+    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.__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.__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.__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.__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/trunk/include/version

 #if _LIBCPP_STD_VER > 11
 #endif
 
 #if _LIBCPP_STD_VER > 14
 # define __cpp_lib_atomic_is_always_lock_free           201603L
 # define __cpp_lib_filesystem                           201703L
 # define __cpp_lib_invoke                               201411L
 # define __cpp_lib_void_t                               201411L
+# define __cpp_lib_node_extract                         201606L
 #endif
 
 #if _LIBCPP_STD_VER > 17
 #endif
 
 #endif  // _LIBCPP_VERSIONH

libcxx/trunk/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, value_type, C2, allocator_type>& source);
+// template <class C2>
+//   void merge(map<key_type, value_type, C2, allocator_type>&& source);
+// template <class C2>
+//   void merge(multimap<key_type, value_type, C2, allocator_type>& source);
+// template <class C2>
+//   void merge(multimap<key_type, value_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(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);
+        {
+            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(std::move(second));
+            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);
+    }
+    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/trunk/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(map<key_type, value_type, C2, allocator_type>& source);
+// template <class C2>
+//   void merge(map<key_type, value_type, C2, allocator_type>&& source);
+// template <class C2>
+//   void merge(multimap<key_type, value_type, C2, allocator_type>& source);
+// template <class C2>
+//   void merge(multimap<key_type, value_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(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);
+        {
+            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(std::move(second));
+            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);
+    }
+    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/trunk/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(set<Key, C2, Allocator>& source);
+// template <class C2>
+//   void merge(set<Key, C2, Allocator>&& source);
+// template <class C2>
+//   void merge(multiset<Key, C2, Allocator>& source);
+// template <class C2>
+//   void merge(multiset<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(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);
+        {
+            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(std::move(second));
+            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/trunk/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);
+// template <class C2>
+//   void merge(set<key_type, C2, allocator_type>&& source);
+// template <class C2>
+//   void merge(multiset<key_type, C2, allocator_type>& source);
+// template <class C2>
+//   void merge(multiset<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(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);
+        {
+            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(std::move(second));
+            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/trunk/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 H2, class P2>
+//   void merge(unordered_map<key_type, value_type, H2, P2, allocator_type>& source);
+// template <class H2, class P2>
+//   void merge(unordered_map<key_type, value_type, H2, P2, allocator_type>&& source);
+// template <class H2, class P2>
+//   void merge(unordered_multimap<key_type, value_type, H2, P2, allocator_type>& source);
+// template <class H2, class P2>
+//   void merge(unordered_multimap<key_type, value_type, H2, P2, 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(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);
+        {
+            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(std::move(second));
+            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/trunk/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 H2, class P2>
+//   void merge(unordered_map<key_type, value_type, H2, P2, allocator_type>& source);
+// template <class H2, class P2>
+//   void merge(unordered_map<key_type, value_type, H2, P2, allocator_type>&& source);
+// template <class H2, class P2>
+//   void merge(unordered_multimap<key_type, value_type, H2, P2, allocator_type>& source);
+// template <class H2, class P2>
+//   void merge(unordered_multimap<key_type, value_type, H2, P2, 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(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);
+        {
+            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(std::move(second));
+            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/trunk/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 H2, class P2>
+//   void merge(unordered_set<key_type, H2, P2, allocator_type>& source);
+// template <class H2, class P2>
+//   void merge(unordered_set<key_type, H2, P2, allocator_type>&& source);
+// template <class H2, class P2>
+//   void merge(unordered_multiset<key_type, H2, P2, allocator_type>& source);
+// template <class H2, class P2>
+//   void merge(unordered_multiset<key_type, H2, P2, 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(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);
+        {
+            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(std::move(second));
+            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/trunk/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 H2, class P2>
+//   void merge(unordered_set<key_type, H2, P2, allocator_type>& source);
+// template <class H2, class P2>
+//   void merge(unordered_set<key_type, H2, P2, allocator_type>&& source);
+// template <class H2, class P2>
+//   void merge(unordered_multiset<key_type, H2, P2, allocator_type>& source);
+// template <class H2, class P2>
+//   void merge(unordered_multiset<key_type, H2, P2, 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(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);
+        {
+            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(std::move(second));
+            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));
+        }
+    }
+}