Second half of C++17's splicing maps and sets

This commit adds a merge member function to all the map and set containers,
which splices nodes from the source container. This completes support for
P0083r3.

Differential revision: https://reviews.llvm.org/D48896

git-svn-id: https://llvm.org/svn/llvm-project/libcxx/trunk@345744 91177308-0d34-0410-b5e6-96231b3b80d8

16 files changed, 1874 insertions, 68 deletions

diff --git a/include/__hash_table b/include/__hash_table
index c77de961b..69ed8dd8b 100644
--- a/include/__hash_table
+++ b/include/__hash_table
@@ -1058,8 +1058,26 @@ public:
         );
     }
 
+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);
 
@@ -1170,6 +1188,9 @@ public:
     _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
@@ -1177,6 +1198,9 @@ public:
     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
@@ -1849,73 +1873,112 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::clear() _NOEXCEPT
     }
 }
 
+
+// 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)
     {
-        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();
+        rehash(_VSTD::max<size_type>(2 * __bc + !__is_hash_power2(__bc),
+                                     size_type(ceil(float(size() + 1) / max_load_factor()))));
+    }
+    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);
+    // insert_after __bucket_list_[__chash], or __first_node if bucket is null
+    __next_pointer __pn = __bucket_list_[__chash];
+    if (__pn == nullptr)
+    {
+        __pn =__p1_.first().__ptr();
+        __nd->__next_ = __pn->__next_;
+        __pn->__next_ = __nd->__ptr();
+        // fix up __bucket_list_
+        __bucket_list_[__chash] = __pn;
+        if (__nd->__next_ != nullptr)
+            __bucket_list_[__constrain_hash(__nd->__next_->__hash(), __bc)] = __nd->__ptr();
+    }
+    else
+    {
+        __nd->__next_ = __pn->__next_;
+        __pn->__next_ = __nd->__ptr();
+    }
+    ++size();
+}
+
+template <class _Tp, class _Hash, class _Equal, class _Alloc>
+pair<typename __hash_table<_Tp, _Hash, _Equal, _Alloc>::iterator, bool>
+__hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_unique(__node_pointer __nd)
+{
+    __nd->__hash_ = hash_function()(__nd->__value_);
+    __next_pointer __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)
     {
@@ -1923,20 +1986,9 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __c
                        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;
@@ -1947,8 +1999,8 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __c
             //      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;
@@ -1956,6 +2008,35 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __c
                     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)
@@ -1966,6 +2047,17 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_insert_multi(__node_pointer __c
         }
     }
     ++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
@@ -2217,6 +2309,32 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_extract(
 }
 
 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
@@ -2244,6 +2362,27 @@ __hash_table<_Tp, _Hash, _Equal, _Alloc>::__node_handle_insert_multi(
     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>
diff --git a/include/__node_handle b/include/__node_handle
index 567f8b047..a9cf3b721 100644
--- a/include/__node_handle
+++ b/include/__node_handle
@@ -26,9 +26,6 @@ _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;
diff --git a/include/__tree b/include/__tree
index 3b3586ca6..aa7370bfb 100644
--- a/include/__tree
+++ b/include/__tree
@@ -1341,15 +1341,20 @@ public:
 
 #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>
@@ -1358,6 +1363,9 @@ public:
     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
@@ -1365,6 +1373,9 @@ public:
     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>
@@ -1384,7 +1395,7 @@ public:
 
     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);
@@ -2129,10 +2140,9 @@ __tree<_Tp, _Compare, _Allocator>::__find_equal(const_iterator __hint,
 }
 
 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;
@@ -2384,7 +2394,7 @@ __tree<_Tp, _Compare, _Allocator>::__node_insert_multi(const_iterator __p,
 
 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;
@@ -2472,6 +2482,30 @@ __tree<_Tp, _Compare, _Allocator>::__node_handle_extract(const_iterator __p)
 }
 
 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
@@ -2507,6 +2541,28 @@ __tree<_Tp, _Compare, _Allocator>::__node_handle_insert_multi(
     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>
diff --git a/include/map b/include/map
index cfd828058..472ac314b 100644
--- a/include/map
+++ b/include/map
@@ -167,6 +167,15 @@ public:
     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
@@ -368,6 +377,15 @@ public:
     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
@@ -926,6 +944,11 @@ public:
     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_(
@@ -1300,6 +1323,38 @@ public:
     {
         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
@@ -1615,6 +1670,11 @@ public:
     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_(
@@ -1882,6 +1942,38 @@ public:
         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
diff --git a/include/set b/include/set
index f2ce6ea2f..80cc7b04c 100644
--- a/include/set
+++ b/include/set
@@ -128,6 +128,15 @@ public:
     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 &&
@@ -316,6 +325,15 @@ public:
     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 &&
@@ -410,6 +428,9 @@ swap(multiset<Key, Compare, Allocator>& x, multiset<Key, Compare, Allocator>& y)
 
 _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
@@ -449,6 +470,11 @@ public:
     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_(
@@ -681,6 +707,38 @@ public:
     {
         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
@@ -891,6 +949,11 @@ public:
     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()
@@ -1122,6 +1185,38 @@ public:
     {
         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
diff --git a/include/unordered_map b/include/unordered_map
index fc3cfb6a9..6f60749c9 100644
--- a/include/unordered_map
+++ b/include/unordered_map
@@ -153,6 +153,15 @@ public:
     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 ||
@@ -325,6 +334,15 @@ public:
     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 ||
@@ -808,6 +826,9 @@ public:
     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
@@ -865,6 +886,11 @@ public:
     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)
@@ -1188,6 +1214,39 @@ public:
         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
@@ -1646,6 +1705,11 @@ public:
     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)
@@ -1847,6 +1911,39 @@ public:
         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
diff --git a/include/unordered_set b/include/unordered_set
index a219fa609..de23ca2a3 100644
--- a/include/unordered_set
+++ b/include/unordered_set
@@ -127,6 +127,15 @@ public:
     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&>())) &&
@@ -282,6 +291,15 @@ public:
     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&>())) &&
@@ -348,6 +366,9 @@ template <class Value, class Hash, class Pred, class Alloc>
 
 _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
@@ -385,6 +406,11 @@ public:
     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)
@@ -590,6 +616,39 @@ public:
     {
         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
@@ -938,6 +997,11 @@ public:
     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)
@@ -1102,6 +1166,39 @@ public:
     {
         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
diff --git a/include/version b/include/version
index 6e61693cf..aca84f8ed 100644
--- a/include/version
+++ b/include/version
@@ -110,6 +110,7 @@ __cpp_lib_void_t                            201411L <type_traits>
 # 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
diff --git a/test/std/containers/associative/map/map.modifiers/merge.pass.cpp b/test/std/containers/associative/map/map.modifiers/merge.pass.cpp
new file mode 100644
index 000000000..4fef2425a
--- /dev/null
+++ b/test/std/containers/associative/map/map.modifiers/merge.pass.cpp
@@ -0,0 +1,149 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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));
+        }
+    }
+}
diff --git a/test/std/containers/associative/multimap/multimap.modifiers/merge.pass.cpp b/test/std/containers/associative/multimap/multimap.modifiers/merge.pass.cpp
new file mode 100644
index 000000000..71f3c0b39
--- /dev/null
+++ b/test/std/containers/associative/multimap/multimap.modifiers/merge.pass.cpp
@@ -0,0 +1,149 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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));
+        }
+    }
+}
diff --git a/test/std/containers/associative/multiset/merge.pass.cpp b/test/std/containers/associative/multiset/merge.pass.cpp
new file mode 100644
index 000000000..516e27de3
--- /dev/null
+++ b/test/std/containers/associative/multiset/merge.pass.cpp
@@ -0,0 +1,148 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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));
+        }
+    }
+}
diff --git a/test/std/containers/associative/set/merge.pass.cpp b/test/std/containers/associative/set/merge.pass.cpp
new file mode 100644
index 000000000..0896596d9
--- /dev/null
+++ b/test/std/containers/associative/set/merge.pass.cpp
@@ -0,0 +1,148 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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));
+        }
+    }
+}
diff --git a/test/std/containers/unord/unord.map/unord.map.modifiers/merge.pass.cpp b/test/std/containers/unord/unord.map/unord.map.modifiers/merge.pass.cpp
new file mode 100644
index 000000000..d525b1add
--- /dev/null
+++ b/test/std/containers/unord/unord.map/unord.map.modifiers/merge.pass.cpp
@@ -0,0 +1,161 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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));
+        }
+    }
+}
diff --git a/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/merge.pass.cpp b/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/merge.pass.cpp
new file mode 100644
index 000000000..d01862094
--- /dev/null
+++ b/test/std/containers/unord/unord.multimap/unord.multimap.modifiers/merge.pass.cpp
@@ -0,0 +1,161 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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));
+        }
+    }
+}
diff --git a/test/std/containers/unord/unord.multiset/merge.pass.cpp b/test/std/containers/unord/unord.multiset/merge.pass.cpp
new file mode 100644
index 000000000..0bf8d358f
--- /dev/null
+++ b/test/std/containers/unord/unord.multiset/merge.pass.cpp
@@ -0,0 +1,158 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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));
+        }
+    }
+}
diff --git a/test/std/containers/unord/unord.set/merge.pass.cpp b/test/std/containers/unord/unord.set/merge.pass.cpp
new file mode 100644
index 000000000..ebf03cd56
--- /dev/null
+++ b/test/std/containers/unord/unord.set/merge.pass.cpp
@@ -0,0 +1,158 @@
+//===----------------------------------------------------------------------===//
+//
+//                     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));
+        }
+    }
+}