Re: [PATH][_GLIBCXX_DEBUG] Fix unordered container merge

["François Dumont" <frs.dumont@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 16174 bytes --]

Yet another version this time with only 1 guard implementation. The 
predicate to invalidate the safe iterators has been externalized.

Ok to commit ?


On 06/11/21 2:51 pm, François Dumont wrote:
> You were right to delay your reply. Here is a new version with less 
> code duplication and a bug fix in the new _UContMergeGuard where we 
> were using it->second rather than it->first to get the key.
>
> Note also that the change to _M_merge_multi implementation is also 
> important because otherwise we might be trying to extract a key from a 
> destructed node.
>
>     libstdc++: [_GLIBCXX_DEBUG] Implement unordered container merge
>
>     The _GLIBCXX_DEBUG unordered containers need a dedicated merge 
> implementation
>     so that any existing iterator on the transfered nodes is properly 
> invalidated.
>
>     Add typedef/using declaration for everything used as-is from 
> normal implementation.
>
>     libstdc++-v3/ChangeLog:
>
>             * include/bits/hashtable_policy.h (__distance_fw): Replace 
> class keyword with
>             typename.
>             * include/bits/hashtable.h 
> (_Hashtable<>::_M_merge_unique): Remove noexcept
>             qualification. Use const_iterator for node 
> extraction/reinsert.
>             (_Hashtable<>::_M_merge_multi): Likewise. Compute new hash 
> code before extract.
>             * include/debug/safe_container.h (_Safe_container<>): Make 
> all methods
>             protected.
>             * include/debug/safe_unordered_container.h
> (_Safe_unordered_container<>::_UContMergeGuard<_ExtractKey, _Source>): 
> New.
> (_Safe_unordered_container<>::_S_uc_guard<_ExtractKey, _Source>): New.
> (_Safe_unordered_container<>::_UMContMergeGuard<_ExtractKey, 
> _Source>): New.
> (_Safe_unordered_container<>::_S_umc_guard<_ExtractKey, _Source>): New.
> (_Safe_unordered_container<>::_M_invalide_all): Make public.
>             (_Safe_unordered_container<>::_M_invalide_if): Likewise.
> (_Safe_unordered_container<>::_M_invalide_local_if): Likewise.
>             * include/debug/unordered_map
>             (unordered_map<>::mapped_type, pointer, const_pointer): 
> New typedef.
>             (unordered_map<>::reference, const_reference, 
> difference_type): New typedef.
>             (unordered_map<>::get_allocator, empty, size, max_size): 
> Add usings.
>             (unordered_map<>::bucket_count, max_bucket_count, bucket): 
> Add usings.
>             (unordered_map<>::hash_function, key_equal, count, 
> contains): Add usings.
>             (unordered_map<>::operator[], at, rehash, reserve): Add 
> usings.
>             (unordered_map<>::merge): New.
>             (unordered_multimap<>::mapped_type, pointer, 
> const_pointer): New typedef.
>             (unordered_multimap<>::reference, const_reference, 
> difference_type): New typedef.
>             (unordered_multimap<>::get_allocator, empty, size, 
> max_size): Add usings.
>             (unordered_multimap<>::bucket_count, max_bucket_count, 
> bucket): Add usings.
>             (unordered_multimap<>::hash_function, key_equal, count, 
> contains): Add usings.
>             (unordered_multimap<>::rehash, reserve): Add usings.
>             (unordered_multimap<>::merge): New.
>             * include/debug/unordered_set
>             (unordered_set<>::mapped_type, pointer, const_pointer): 
> New typedef.
>             (unordered_set<>::reference, const_reference, 
> difference_type): New typedef.
>             (unordered_set<>::get_allocator, empty, size, max_size): 
> Add usings.
>             (unordered_set<>::bucket_count, max_bucket_count, bucket): 
> Add usings.
>             (unordered_set<>::hash_function, key_equal, count, 
> contains): Add usings.
>             (unordered_set<>::rehash, reserve): Add usings.
>             (unordered_set<>::merge): New.
>             (unordered_multiset<>::mapped_type, pointer, 
> const_pointer): New typedef.
>             (unordered_multiset<>::reference, const_reference, 
> difference_type): New typedef.
>             (unordered_multiset<>::get_allocator, empty, size, 
> max_size): Add usings.
>             (unordered_multiset<>::bucket_count, max_bucket_count, 
> bucket): Add usings.
>             (unordered_multiset<>::hash_function, key_equal, count, 
> contains): Add usings.
>             (unordered_multiset<>::rehash, reserve): Add usings.
>             (unordered_multiset<>::merge): New.
>             * 
> testsuite/23_containers/unordered_map/debug/merge1_neg.cc: New test.
>             * 
> testsuite/23_containers/unordered_map/debug/merge2_neg.cc: New test.
>             * 
> testsuite/23_containers/unordered_map/debug/merge3_neg.cc: New test.
>             * 
> testsuite/23_containers/unordered_map/debug/merge4_neg.cc: New test.
>             * 
> testsuite/23_containers/unordered_multimap/debug/merge1_neg.cc: New test.
>             * 
> testsuite/23_containers/unordered_multimap/debug/merge2_neg.cc: New test.
>             * 
> testsuite/23_containers/unordered_multimap/debug/merge3_neg.cc: New test.
>             * 
> testsuite/23_containers/unordered_multimap/debug/merge4_neg.cc: New test.
>             * 
> testsuite/23_containers/unordered_multiset/debug/merge1_neg.cc: New test.
>             * 
> testsuite/23_containers/unordered_multiset/debug/merge2_neg.cc: New test.
>             * 
> testsuite/23_containers/unordered_multiset/debug/merge3_neg.cc: New test.
>             * 
> testsuite/23_containers/unordered_multiset/debug/merge4_neg.cc: New test.
>             * 
> testsuite/23_containers/unordered_set/debug/merge1_neg.cc: New test.
>             * 
> testsuite/23_containers/unordered_set/debug/merge2_neg.cc: New test.
>             * 
> testsuite/23_containers/unordered_set/debug/merge3_neg.cc: New test.
>             * 
> testsuite/23_containers/unordered_set/debug/merge4_neg.cc: New test.
>             * testsuite/util/testsuite_abi.h: [_GLIBCXX_DEBUG] Use 
> normal unordered container implementation.
>
> Tested under Linux x86_64.
>
> Ok to commit ?
>
> François
>
> On 25/10/21 8:08 pm, François Dumont wrote:
>> New patch with the proposed workaround below.
>>
>> I also slightly change the _M_merge_multi implementation so that if 
>> the new hash code computation raise an exception the node is simply 
>> not extracted rather than extracted and then released. This way, if 
>> it takes place on the 1st moved node the _GLIBCXX_DEBUG mode won't 
>> try to invalidate anything because the source size won't have changed.
>>
>> Ok to commit ?
>>
>> François
>>
>>
>> On 16/10/21 4:52 pm, Jonathan Wakely wrote:
>>>
>>>
>>> On Sat, 16 Oct 2021, 14:49 François Dumont via Libstdc++, 
>>> <libstdc++@gcc.gnu.org <mailto:libstdc%2B%2B@gcc.gnu.org>> wrote:
>>>
>>>     Hi
>>>
>>>          Here is the new proposal. My only concern is that we are
>>>     also using
>>>     hash or equal_to functors in the guard destructor.
>>>
>>>
>>>
>>> Can we catch any exception there, invalidate all iterators, and not 
>>> rethrow the exception?
>>>
>>>
>>>          I am going to enhance merge normal implementation to make
>>>     use of
>>>     the cached hash code when hash functors are the same between the
>>>     source
>>>     and destination of nodes. Maybe I'll be able to make use of it
>>>     in Debug
>>>     implementation too.
>>>
>>>     François
>>>
>>>
>>>     On 14/10/21 10:23 am, Jonathan Wakely wrote:
>>>     > On Wed, 13 Oct 2021 at 18:10, François Dumont via Libstdc++
>>>     > <libstdc++@gcc.gnu.org <mailto:libstdc%2B%2B@gcc.gnu.org>> wrote:
>>>     >> Hi
>>>     >>
>>>     >>       libstdc++: [_GLIBCXX_DEBUG] Implement unordered
>>>     container merge
>>>     >>
>>>     >>       The _GLIBCXX_DEBUG unordered containers need a
>>>     dedicated merge
>>>     >> implementation
>>>     >>       so that any existing iterator on the transfered nodes
>>>     is properly
>>>     >> invalidated.
>>>     >>
>>>     >>       Add typedef/using declaration for everything used as-is
>>>     from normal
>>>     >> implementation.
>>>     >>
>>>     >>       libstdc++-v3/ChangeLog:
>>>     >>
>>>     >>               * include/debug/safe_container.h
>>>     (_Safe_container<>): Make
>>>     >> all methods
>>>     >>               protected.
>>>     >>               * include/debug/safe_unordered_container.h
>>>     >>  (_Safe_unordered_container<>::_M_invalide_all): Make public.
>>>     >>  (_Safe_unordered_container<>::_M_invalide_if): Likewise.
>>>     >> (_Safe_unordered_container<>::_M_invalide_local_if): Likewise.
>>>     >>               * include/debug/unordered_map
>>>     >>  (unordered_map<>::mapped_type, pointer, const_pointer): New
>>>     >> typedef.
>>>     >>  (unordered_map<>::reference, const_reference,
>>>     >> difference_type): New typedef.
>>>     >>  (unordered_map<>::get_allocator, empty, size, max_size):
>>>     >> Add usings.
>>>     >>  (unordered_map<>::bucket_count, max_bucket_count, bucket):
>>>     >> Add usings.
>>>     >>  (unordered_map<>::hash_function, key_equal, count,
>>>     >> contains): Add usings.
>>>     >>  (unordered_map<>::operator[], at, rehash, reserve): Add usings.
>>>     >>               (unordered_map<>::merge): New.
>>>     >>  (unordered_multimap<>::mapped_type, pointer,
>>>     >> const_pointer): New typedef.
>>>     >>  (unordered_multimap<>::reference, const_reference,
>>>     >> difference_type): New typedef.
>>>     >>  (unordered_multimap<>::get_allocator, empty, size,
>>>     >> max_size): Add usings.
>>>     >>  (unordered_multimap<>::bucket_count, max_bucket_count,
>>>     >> bucket): Add usings.
>>>     >>  (unordered_multimap<>::hash_function, key_equal, count,
>>>     >> contains): Add usings.
>>>     >>  (unordered_multimap<>::rehash, reserve): Add usings.
>>>     >>  (unordered_multimap<>::merge): New.
>>>     >>               * include/debug/unordered_set
>>>     >>  (unordered_set<>::mapped_type, pointer, const_pointer): New
>>>     >> typedef.
>>>     >>  (unordered_set<>::reference, const_reference,
>>>     >> difference_type): New typedef.
>>>     >>  (unordered_set<>::get_allocator, empty, size, max_size):
>>>     >> Add usings.
>>>     >>  (unordered_set<>::bucket_count, max_bucket_count, bucket):
>>>     >> Add usings.
>>>     >>  (unordered_set<>::hash_function, key_equal, count,
>>>     >> contains): Add usings.
>>>     >>               (unordered_set<>::rehash, reserve): Add usings.
>>>     >>               (unordered_set<>::merge): New.
>>>     >>  (unordered_multiset<>::mapped_type, pointer,
>>>     >> const_pointer): New typedef.
>>>     >>  (unordered_multiset<>::reference, const_reference,
>>>     >> difference_type): New typedef.
>>>     >>  (unordered_multiset<>::get_allocator, empty, size,
>>>     >> max_size): Add usings.
>>>     >>  (unordered_multiset<>::bucket_count, max_bucket_count,
>>>     >> bucket): Add usings.
>>>     >>  (unordered_multiset<>::hash_function, key_equal, count,
>>>     >> contains): Add usings.
>>>     >>  (unordered_multiset<>::rehash, reserve): Add usings.
>>>     >>  (unordered_multiset<>::merge): New.
>>>     >>               *
>>>     >> testsuite/23_containers/unordered_map/debug/merge1_neg.cc:
>>>     New test.
>>>     >>               *
>>>     >> testsuite/23_containers/unordered_map/debug/merge2_neg.cc:
>>>     New test.
>>>     >>               *
>>>     >> testsuite/23_containers/unordered_map/debug/merge3_neg.cc:
>>>     New test.
>>>     >>               *
>>>     >> testsuite/23_containers/unordered_map/debug/merge4_neg.cc:
>>>     New test.
>>>     >>               *
>>>     >>
>>>     testsuite/23_containers/unordered_multimap/debug/merge1_neg.cc:
>>>     New test.
>>>     >>               *
>>>     >>
>>>     testsuite/23_containers/unordered_multimap/debug/merge2_neg.cc:
>>>     New test.
>>>     >>               *
>>>     >>
>>>     testsuite/23_containers/unordered_multimap/debug/merge3_neg.cc:
>>>     New test.
>>>     >>               *
>>>     >>
>>>     testsuite/23_containers/unordered_multimap/debug/merge4_neg.cc:
>>>     New test.
>>>     >>               *
>>>     >>
>>>     testsuite/23_containers/unordered_multiset/debug/merge1_neg.cc:
>>>     New test.
>>>     >>               *
>>>     >>
>>>     testsuite/23_containers/unordered_multiset/debug/merge2_neg.cc:
>>>     New test.
>>>     >>               *
>>>     >>
>>>     testsuite/23_containers/unordered_multiset/debug/merge3_neg.cc:
>>>     New test.
>>>     >>               *
>>>     >>
>>>     testsuite/23_containers/unordered_multiset/debug/merge4_neg.cc:
>>>     New test.
>>>     >>               *
>>>     >> testsuite/23_containers/unordered_set/debug/merge1_neg.cc:
>>>     New test.
>>>     >>               *
>>>     >> testsuite/23_containers/unordered_set/debug/merge2_neg.cc:
>>>     New test.
>>>     >>               *
>>>     >> testsuite/23_containers/unordered_set/debug/merge3_neg.cc:
>>>     New test.
>>>     >>               *
>>>     >> testsuite/23_containers/unordered_set/debug/merge4_neg.cc:
>>>     New test.
>>>     >>               * testsuite/util/testsuite_abi.h:
>>>     [_GLIBCXX_DEBUG] Use
>>>     >> normal unordered container implementation.
>>>     >>
>>>     >> Tested under Linux x86_64.
>>>     >>
>>>     >> Ok to commit ?
>>>     > Yes, thanks. But ...
>>>     >
>>>     > This looks like an improvement over what we have now, but not 100%
>>>     > correct. The merge functions can exit via exception (if any hash
>>>     > function or equality predicate throws), and if that happens
>>>     the safe
>>>     > iterators will not get invalidated. I think we need to call
>>>     > _Base::merge in a try-block, and do the iterator invalidation
>>>     whether
>>>     > we return normally or via an exception.
>>>     >
>>>     > Something like:
>>>     >
>>>     >    template<typename _H2, typename _P2>
>>>     >      void
>>>     >      merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
>>>     >      {
>>>     >        struct _Guard
>>>     >        {
>>>     >          _Guard(unordered_set& __source) noexcept
>>>     >          : _M_source(__source), _M_size(__source.size())
>>>     >          { }
>>>     >
>>>     >          ~_Guard()
>>>     >          {
>>>     >            const size_type __size = _M_source.size();
>>>     >            if (__size != _M_size)
>>>     >              {
>>>     >                if (__size == 0)
>>>     >                  _M_source._M_invalidate_all();
>>>     >                else
>>>     >                  {
>>>     >                    auto __pred = [&__source](auto __it)
>>>     >                                  { return
>>>     __source.count(*__it) == 0; };
>>>     > __source._M_invalidate_if(__pred);
>>>     > __source._M_invalidate_local_if(__pred);
>>>     >                  }
>>>     >              }
>>>     >          }
>>>     >
>>>     >          _Guard(const _Guard&) = delete;
>>>     >
>>>     >          unordered_set& _M_source;
>>>     >          const size_type _M_size;
>>>     >        };
>>>     >        _Guard __guard(__source);
>>>     >        _Base::merge(__source._M_base());
>>>     >      }
>>>     >
>>>
>>
>


[-- Attachment #2: merge.patch --]
[-- Type: text/x-patch, Size: 34367 bytes --]

diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 25c45d3ba85..0e949d73614 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -1065,14 +1065,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       /// Merge from a compatible container into one with unique keys.
       template<typename _Compatible_Hashtable>
 	void
-	_M_merge_unique(_Compatible_Hashtable& __src) noexcept
+	_M_merge_unique(_Compatible_Hashtable& __src)
 	{
 	  static_assert(is_same_v<typename _Compatible_Hashtable::node_type,
 	      node_type>, "Node types are compatible");
 	  __glibcxx_assert(get_allocator() == __src.get_allocator());
 
 	  auto __n_elt = __src.size();
-	  for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
+	  for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
 	    {
 	      auto __pos = __i++;
 	      const key_type& __k = _ExtractKey{}(*__pos);
@@ -1093,15 +1093,22 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       /// Merge from a compatible container into one with equivalent keys.
       template<typename _Compatible_Hashtable>
 	void
-	_M_merge_multi(_Compatible_Hashtable& __src) noexcept
+	_M_merge_multi(_Compatible_Hashtable& __src)
 	{
 	  static_assert(is_same_v<typename _Compatible_Hashtable::node_type,
 	      node_type>, "Node types are compatible");
 	  __glibcxx_assert(get_allocator() == __src.get_allocator());
 
 	  this->reserve(size() + __src.size());
-	  for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
-	    _M_reinsert_node_multi(cend(), __src.extract(__i++));
+	  for (auto __i = __src.cbegin(), __end = __src.cend(); __i != __end;)
+	    {
+	      auto __pos = __i++;
+	      const key_type& __k = _ExtractKey{}(*__pos);
+	      __hash_code __code = this->_M_hash_code(__k);
+	      auto __nh = __src.extract(__pos);
+	      _M_insert_multi_node(nullptr, __code, __nh._M_ptr);
+	      __nh._M_ptr = nullptr;
+	    }
 	}
 #endif // C++17
 
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 8c72043e368..c0295b75963 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -60,19 +60,19 @@ namespace __detail
 
   // Helper function: return distance(first, last) for forward
   // iterators, or 0/1 for input iterators.
-  template<class _Iterator>
+  template<typename _Iterator>
     inline typename std::iterator_traits<_Iterator>::difference_type
     __distance_fw(_Iterator __first, _Iterator __last,
 		  std::input_iterator_tag)
     { return __first != __last ? 1 : 0; }
 
-  template<class _Iterator>
+  template<typename _Iterator>
     inline typename std::iterator_traits<_Iterator>::difference_type
     __distance_fw(_Iterator __first, _Iterator __last,
 		  std::forward_iterator_tag)
     { return std::distance(__first, __last); }
 
-  template<class _Iterator>
+  template<typename _Iterator>
     inline typename std::iterator_traits<_Iterator>::difference_type
     __distance_fw(_Iterator __first, _Iterator __last)
     { return __distance_fw(__first, __last,
diff --git a/libstdc++-v3/include/debug/safe_container.h b/libstdc++-v3/include/debug/safe_container.h
index 97c47167fe8..5de55d69f34 100644
--- a/libstdc++-v3/include/debug/safe_container.h
+++ b/libstdc++-v3/include/debug/safe_container.h
@@ -78,7 +78,6 @@ namespace __gnu_debug
       { }
 #endif
 
-    public:
       // Copy assignment invalidate all iterators.
       _Safe_container&
       operator=(const _Safe_container&) _GLIBCXX_NOEXCEPT
diff --git a/libstdc++-v3/include/debug/safe_unordered_container.h b/libstdc++-v3/include/debug/safe_unordered_container.h
index aae1e2dab60..ce9d9ea4091 100644
--- a/libstdc++-v3/include/debug/safe_unordered_container.h
+++ b/libstdc++-v3/include/debug/safe_unordered_container.h
@@ -72,6 +72,96 @@ namespace __gnu_debug
 		{ return __it != __local_end; });
       }
 
+#if __cplusplus > 201402L
+      template<typename _ExtractKey, typename _Source>
+	struct _UContInvalidatePred
+	{
+	  template<typename _Iterator>
+	    bool
+	    operator()(_Iterator __it) const
+	    { return _M_source.count(_ExtractKey{}(*__it)) == 0; }
+
+	  const _Source& _M_source;
+	};
+
+      template<typename _ExtractKey, typename _Source>
+	struct _UMContInvalidatePred
+	{
+	  template<typename _Iterator>
+	    bool
+	    operator()(_Iterator __it) const
+	    {
+	      auto __rng =
+		_M_source._M_base().equal_range(_ExtractKey{}(*__it));
+	      for (auto __rit = __rng.first;
+		   __rit != __rng.second; ++__rit)
+		{
+		  if (__it == __rit)
+		    return false;
+		}
+
+	      return true;
+	    }
+
+	  const _Source& _M_source;
+	};
+
+      template<typename _Source, typename _InvalidatePred>
+	struct _UContMergeGuard
+	{
+	  _UContMergeGuard(_Source& __src) noexcept
+	  : _M_source(__src), _M_size(__src.size()), _M_pred { __src }
+	  { }
+
+	  _UContMergeGuard(const _UContMergeGuard&) = delete;
+
+	  ~_UContMergeGuard()
+	  {
+	    const std::size_t __size = _M_source.size();
+	    if (__size == _M_size)
+	      return;
+
+	    __try
+	      {
+		if (__size == 0)
+		  _M_source._M_invalidate_all();
+		else
+		  {
+		    _M_source._M_invalidate_if(_M_pred);
+		    _M_source._M_invalidate_local_if(_M_pred);
+		  }
+	      }
+	    __catch(...)
+	      {
+		_M_source._M_invalidate_all();
+	      }
+	  }
+
+	  _Source& _M_source;
+	  const std::size_t _M_size;
+	  _InvalidatePred _M_pred;
+	};
+
+      template<typename _ExtractKey, typename _Source>
+	static _UContMergeGuard<_Source,
+				_UContInvalidatePred<_ExtractKey, _Source>>
+	_S_uc_guard(_ExtractKey, _Source& __src)
+	{
+	  typedef _UContInvalidatePred<_ExtractKey, _Source> _InvalidatePred;
+	  return _UContMergeGuard<_Source, _InvalidatePred>(__src);
+	}
+
+      template<typename _ExtractKey, typename _Source>
+	static _UContMergeGuard<_Source,
+				_UMContInvalidatePred<_ExtractKey, _Source>>
+	_S_umc_guard(_ExtractKey, _Source& __src)
+	{
+	  typedef _UMContInvalidatePred<_ExtractKey, _Source> _InvalidatePred;
+	  return _UContMergeGuard<_Source, _InvalidatePred>(__src);
+	}
+#endif // C++17
+
+    public:
       void
       _M_invalidate_all()
       {
diff --git a/libstdc++-v3/include/debug/unordered_map b/libstdc++-v3/include/debug/unordered_map
index bb697d364ea..d6e184a2e99 100644
--- a/libstdc++-v3/include/debug/unordered_map
+++ b/libstdc++-v3/include/debug/unordered_map
@@ -97,7 +97,12 @@ namespace __debug
 
       typedef typename _Base::key_type			key_type;
       typedef typename _Base::value_type		value_type;
+      typedef typename _Base::mapped_type		mapped_type;
 
+      typedef typename _Base::pointer			pointer;
+      typedef typename _Base::const_pointer		const_pointer;
+      typedef typename _Base::reference			reference;
+      typedef typename _Base::const_reference		const_reference;
       typedef __gnu_debug::_Safe_iterator<
 	_Base_iterator, unordered_map>			iterator;
       typedef __gnu_debug::_Safe_iterator<
@@ -106,6 +111,7 @@ namespace __debug
 	_Base_local_iterator, unordered_map>		local_iterator;
       typedef __gnu_debug::_Safe_local_iterator<
 	_Base_const_local_iterator, unordered_map>	const_local_iterator;
+      typedef typename _Base::difference_type		difference_type;
 
       unordered_map() = default;
 
@@ -209,6 +215,11 @@ namespace __debug
 	return *this;
       }
 
+      using _Base::get_allocator;
+      using _Base::empty;
+      using _Base::size;
+      using _Base::max_size;
+
       void
       swap(unordered_map& __x)
 	noexcept( noexcept(declval<_Base&>().swap(__x)) )
@@ -291,6 +302,10 @@ namespace __debug
 	return { _Base::cend(__b), this };
       }
 
+      using _Base::bucket_count;
+      using _Base::max_bucket_count;
+      using _Base::bucket;
+
       size_type
       bucket_size(size_type __b) const
       {
@@ -298,6 +313,8 @@ namespace __debug
 	return _Base::bucket_size(__b);
       }
 
+      using _Base::load_factor;
+
       float
       max_load_factor() const noexcept
       { return _Base::max_load_factor(); }
@@ -538,9 +555,38 @@ namespace __debug
 	return { _Base::insert(__hint.base(), std::move(__nh)), this };
       }
 
-      using _Base::merge;
+      template<typename _H2, typename _P2>
+	void
+	merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
+	{
+	  auto __guard
+	    = _Safe::_S_uc_guard(std::__detail::_Select1st{}, __source);
+	  _Base::merge(__source._M_base());
+	}
+
+      template<typename _H2, typename _P2>
+	void
+	merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
+	{ merge(__source); }
+
+      template<typename _H2, typename _P2>
+	void
+	merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
+	{
+	  auto __guard
+	    = _Safe::_S_umc_guard(std::__detail::_Select1st{}, __source);
+	  _Base::merge(__source._M_base());
+	}
+
+      template<typename _H2, typename _P2>
+	void
+	merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
+	{ merge(__source); }
 #endif // C++17
 
+      using _Base::hash_function;
+      using _Base::key_eq;
+
       iterator
       find(const key_type& __key)
       { return { _Base::find(__key), this }; }
@@ -567,6 +613,11 @@ namespace __debug
 	{ return { _Base::find(__k), this }; }
 #endif
 
+      using _Base::count;
+#if __cplusplus > 201703L
+      using _Base::contains;
+#endif
+
       std::pair<iterator, iterator>
       equal_range(const key_type& __key)
       {
@@ -605,6 +656,9 @@ namespace __debug
 	}
 #endif
 
+      using _Base::operator[];
+      using _Base::at;
+
       size_type
       erase(const key_type& __key)
       {
@@ -651,6 +705,9 @@ namespace __debug
 	return { __next, this };
       }
 
+      using _Base::rehash;
+      using _Base::reserve;
+
       _Base&
       _M_base() noexcept	{ return *this; }
 
@@ -843,7 +900,12 @@ namespace __debug
 
       typedef typename _Base::key_type			key_type;
       typedef typename _Base::value_type		value_type;
+      typedef typename _Base::mapped_type		mapped_type;
 
+      typedef typename _Base::pointer			pointer;
+      typedef typename _Base::const_pointer		const_pointer;
+      typedef typename _Base::reference			reference;
+      typedef typename _Base::const_reference		const_reference;
       typedef __gnu_debug::_Safe_iterator<
 	_Base_iterator, unordered_multimap>		iterator;
       typedef __gnu_debug::_Safe_iterator<
@@ -852,6 +914,7 @@ namespace __debug
 	_Base_local_iterator, unordered_multimap>	local_iterator;
       typedef __gnu_debug::_Safe_local_iterator<
 	_Base_const_local_iterator, unordered_multimap>	const_local_iterator;
+      typedef typename _Base::difference_type		difference_type;
 
       unordered_multimap() = default;
 
@@ -952,6 +1015,11 @@ namespace __debug
 	return *this;
       }
 
+      using _Base::get_allocator;
+      using _Base::empty;
+      using _Base::size;
+      using _Base::max_size;
+
       void
       swap(unordered_multimap& __x)
 	noexcept( noexcept(declval<_Base&>().swap(__x)) )
@@ -1034,6 +1102,10 @@ namespace __debug
 	return { _Base::cend(__b), this };
       }
 
+      using _Base::bucket_count;
+      using _Base::max_bucket_count;
+      using _Base::bucket;
+
       size_type
       bucket_size(size_type __b) const
       {
@@ -1192,9 +1264,38 @@ namespace __debug
 	return { _Base::insert(__hint.base(), std::move(__nh)), this };
       }
 
-      using _Base::merge;
+      template<typename _H2, typename _P2>
+	void
+	merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
+	{
+	  auto __guard
+	    = _Safe::_S_umc_guard(std::__detail::_Select1st{}, __source);
+	  _Base::merge(__source._M_base());
+	}
+
+      template<typename _H2, typename _P2>
+	void
+	merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
+	{ merge(__source); }
+
+      template<typename _H2, typename _P2>
+	void
+	merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
+	{
+	  auto __guard
+	    = _Safe::_S_uc_guard(std::__detail::_Select1st{}, __source);
+	  _Base::merge(__source._M_base());
+	}
+
+      template<typename _H2, typename _P2>
+	void
+	merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>&& __source)
+	{ merge(__source); }
 #endif // C++17
 
+      using _Base::hash_function;
+      using _Base::key_eq;
+
       iterator
       find(const key_type& __key)
       { return { _Base::find(__key), this }; }
@@ -1221,6 +1322,11 @@ namespace __debug
 	{ return { _Base::find(__k), this }; }
 #endif
 
+      using _Base::count;
+#if __cplusplus > 201703L
+      using _Base::contains;
+#endif
+
       std::pair<iterator, iterator>
       equal_range(const key_type& __key)
       {
@@ -1309,6 +1415,9 @@ namespace __debug
 	return { __next, this };
       }
 
+      using _Base::rehash;
+      using _Base::reserve;
+
       _Base&
       _M_base() noexcept { return *this; }
 
diff --git a/libstdc++-v3/include/debug/unordered_set b/libstdc++-v3/include/debug/unordered_set
index c25910946b7..7dc91fa862d 100644
--- a/libstdc++-v3/include/debug/unordered_set
+++ b/libstdc++-v3/include/debug/unordered_set
@@ -88,6 +88,7 @@ namespace __debug
 
     public:
       typedef typename _Base::size_type			size_type;
+      typedef typename _Base::difference_type		difference_type;
       typedef typename _Base::hasher			hasher;
       typedef typename _Base::key_equal			key_equal;
       typedef typename _Base::allocator_type		allocator_type;
@@ -95,6 +96,10 @@ namespace __debug
       typedef typename _Base::key_type			key_type;
       typedef typename _Base::value_type		value_type;
 
+      typedef typename _Base::pointer			pointer;
+      typedef typename _Base::const_pointer		const_pointer;
+      typedef typename _Base::reference			reference;
+      typedef typename _Base::const_reference		const_reference;
       typedef __gnu_debug::_Safe_iterator<
 	_Base_iterator, unordered_set>			iterator;
       typedef __gnu_debug::_Safe_iterator<
@@ -203,6 +208,11 @@ namespace __debug
 	return *this;
       }
 
+      using _Base::get_allocator;
+      using _Base::empty;
+      using _Base::size;
+      using _Base::max_size;
+
       void
       swap(unordered_set& __x)
 	noexcept( noexcept(declval<_Base&>().swap(__x)) )
@@ -285,6 +295,9 @@ namespace __debug
 	return { _Base::cend(__b), this };
       }
 
+      using _Base::bucket_count;
+      using _Base::max_bucket_count;
+
       size_type
       bucket_size(size_type __b) const
       {
@@ -292,6 +305,9 @@ namespace __debug
 	return _Base::bucket_size(__b);
       }
 
+      using _Base::bucket;
+      using _Base::load_factor;
+
       float
       max_load_factor() const noexcept
       { return _Base::max_load_factor(); }
@@ -303,6 +319,9 @@ namespace __debug
 	_Base::max_load_factor(__f);
       }
 
+      using _Base::rehash;
+      using _Base::reserve;
+
       template<typename... _Args>
 	std::pair<iterator, bool>
 	emplace(_Args&&... __args)
@@ -423,9 +442,38 @@ namespace __debug
 	return { _Base::insert(__hint.base(), std::move(__nh)), this };
       }
 
-      using _Base::merge;
+      template<typename _H2, typename _P2>
+	void
+	merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
+	{
+	  auto __guard
+	    = _Safe::_S_uc_guard(std::__detail::_Identity{}, __source);
+	  _Base::merge(__source._M_base());
+	}
+
+      template<typename _H2, typename _P2>
+	void
+	merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
+	{ merge(__source); }
+
+      template<typename _H2, typename _P2>
+	void
+	merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
+	{
+	  auto __guard
+	    = _Safe::_S_umc_guard(std::__detail::_Identity{}, __source);
+	  _Base::merge(__source._M_base());
+	}
+
+      template<typename _H2, typename _P2>
+	void
+	merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
+	{ merge(__source); }
 #endif // C++17
 
+      using _Base::hash_function;
+      using _Base::key_eq;
+
       iterator
       find(const key_type& __key)
       { return { _Base::find(__key), this }; }
@@ -452,6 +500,12 @@ namespace __debug
 	{ return { _Base::find(__k), this }; }
 #endif
 
+      using _Base::count;
+
+#if __cplusplus > 201703L
+      using _Base::contains;
+#endif
+
       std::pair<iterator, iterator>
       equal_range(const key_type& __key)
       {
@@ -707,6 +761,7 @@ namespace __debug
 
     public:
       typedef typename _Base::size_type			size_type;
+      typedef typename _Base::difference_type		difference_type;
       typedef typename _Base::hasher			hasher;
       typedef typename _Base::key_equal			key_equal;
       typedef typename _Base::allocator_type		allocator_type;
@@ -714,6 +769,10 @@ namespace __debug
       typedef typename _Base::key_type			key_type;
       typedef typename _Base::value_type		value_type;
 
+      typedef typename _Base::pointer			pointer;
+      typedef typename _Base::const_pointer		const_pointer;
+      typedef typename _Base::reference			reference;
+      typedef typename _Base::const_reference		const_reference;
       typedef __gnu_debug::_Safe_iterator<
 	_Base_iterator, unordered_multiset>		iterator;
       typedef __gnu_debug::_Safe_iterator<
@@ -822,6 +881,11 @@ namespace __debug
 	return *this;
       }
 
+      using _Base::get_allocator;
+      using _Base::empty;
+      using _Base::size;
+      using _Base::max_size;
+
       void
       swap(unordered_multiset& __x)
 	noexcept( noexcept(declval<_Base&>().swap(__x)) )
@@ -904,6 +968,9 @@ namespace __debug
 	return { _Base::cend(__b), this };
       }
 
+      using _Base::bucket_count;
+      using _Base::max_bucket_count;
+
       size_type
       bucket_size(size_type __b) const
       {
@@ -911,6 +978,9 @@ namespace __debug
 	return _Base::bucket_size(__b);
       }
 
+      using _Base::bucket;
+      using _Base::load_factor;
+
       float
       max_load_factor() const noexcept
       { return _Base::max_load_factor(); }
@@ -922,6 +992,9 @@ namespace __debug
 	_Base::max_load_factor(__f);
       }
 
+      using _Base::rehash;
+      using _Base::reserve;
+
       template<typename... _Args>
 	iterator
 	emplace(_Args&&... __args)
@@ -1037,9 +1110,38 @@ namespace __debug
 	return { _Base::insert(__hint.base(), std::move(__nh)), this };
       }
 
-      using _Base::merge;
+      template<typename _H2, typename _P2>
+	void
+	merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
+	{
+	  auto __guard
+	    = _Safe::_S_umc_guard(std::__detail::_Identity{}, __source);
+	  _Base::merge(__source._M_base());
+	}
+
+      template<typename _H2, typename _P2>
+	void
+	merge(unordered_multiset<_Value, _H2, _P2, _Alloc>&& __source)
+	{ merge(__source); }
+
+      template<typename _H2, typename _P2>
+	void
+	merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
+	{
+	  auto __guard
+	    = _Safe::_S_uc_guard(std::__detail::_Identity{}, __source);
+	  _Base::merge(__source._M_base());
+	}
+
+      template<typename _H2, typename _P2>
+	void
+	merge(unordered_set<_Value, _H2, _P2, _Alloc>&& __source)
+	{ merge(__source); }
 #endif // C++17
 
+      using _Base::hash_function;
+      using _Base::key_eq;
+
       iterator
       find(const key_type& __key)
       { return { _Base::find(__key), this }; }
@@ -1066,6 +1168,12 @@ namespace __debug
 	{ return { _Base::find(__k), this }; }
 #endif
 
+      using _Base::count;
+
+#if __cplusplus > 201703L
+      using _Base::contains;
+#endif
+
       std::pair<iterator, iterator>
       equal_range(const key_type& __key)
       {
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge1_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge1_neg.cc
new file mode 100644
index 00000000000..6d007944918
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge1_neg.cc
@@ -0,0 +1,31 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_map>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_map<int, double>;
+
+void
+test01()
+{
+  test_type c0{ { 1, 3.5 }, { 2, 5.5 }, { 3, 7.5 }, { 5, 11.5 }, { 6, 13.5 } };
+  test_type c1{ { 1, 3.5 }, { 2, 5.5 }, { 3, 7.5 }, { 4, 9.5 } };
+
+  auto it2 = c1.find(2);
+  auto it4 = c1.find(4);
+  VERIFY( it2->second == 5.5 );
+  VERIFY( it4->second == 9.5 );
+
+  c0.merge(c1);
+
+  VERIFY( it2->second == 5.5 );
+  VERIFY( it4 != it2 ); // Invalid iterator.
+}
+
+int
+main()
+{
+  test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge2_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge2_neg.cc
new file mode 100644
index 00000000000..543cd960a5e
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge2_neg.cc
@@ -0,0 +1,32 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_map>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_map<int, int>;
+
+void
+test01()
+{
+  test_type c0{ { 1, 1 }, { 2, 2 }, { 3, 3 }, { 5, 5 }, { 6, 6 } };
+  test_type c1{ { 1, 1 }, { 2, 2 }, { 3, 3 }, { 4, 4 } };
+
+  auto it2 = c1.find(2);
+  auto it4 = c1.find(4);
+  VERIFY( it2->second == 2 );
+  VERIFY( it4->second == 4 );
+
+  c0.merge(std::move(c1));
+
+  VERIFY( it2->second == 2 );
+  VERIFY( it2 != it4 ); // Invalid iterator.
+}
+
+
+int
+main()
+{
+  test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge3_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge3_neg.cc
new file mode 100644
index 00000000000..8e234799cbf
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge3_neg.cc
@@ -0,0 +1,42 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_map>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_map<int, int>;
+
+void
+test01()
+{
+  test_type c0
+    {
+     { 1, 1 }, { 2, 2 }, { 3, 3 },
+     { 5, 5 }, { 6, 6 }, { 7, 7 }
+    };
+  std::unordered_multimap<int, int> c1
+    {
+     { 1, 1 }, { 1, 1 }, { 2, 2 }, { 2, 2 },
+     { 3, 3 }, { 3, 3 }, { 4, 4 }, { 4, 4 },
+     { 5, 5 }
+    };
+
+  auto it1 = c1.find(1);
+  auto it41 = c1.find(4);
+  auto it42 = it41;
+  ++it42;
+  VERIFY( it42->second == 4 );
+
+  c0.merge(c1);
+
+  VERIFY( it1->second == 1 );
+  VERIFY( c1.count(4) == 1 );
+  VERIFY( it41 != it42 ); // Invalid iterator.
+}
+
+int
+main()
+{
+  test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge4_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge4_neg.cc
new file mode 100644
index 00000000000..3c9c8268f8c
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/debug/merge4_neg.cc
@@ -0,0 +1,42 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_map>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_map<int, int>;
+
+void
+test01()
+{
+  test_type c0
+    {
+     { 1, 1 }, { 2, 2 }, { 3, 3 },
+     { 5, 5 }, { 6, 6 }, { 7, 7 }
+    };
+  std::unordered_multimap<int, int> c1
+    {
+     { 1, 1 }, { 1, 1 }, { 2, 2 }, { 2, 2 },
+     { 3, 3 }, { 3, 3 }, { 4, 4 }, { 4, 4 },
+     { 5, 5 }
+    };
+
+  auto it1 = c1.find(1);
+  auto it41 = c1.find(4);
+  auto it42 = it41;
+  ++it42;
+  VERIFY( it42->second == 4 );
+
+  c0.merge(std::move(c1));
+
+  VERIFY( it1->second == 1 );
+  VERIFY( c1.count(4) == 1 );
+  VERIFY( it41 != it42 ); // Invalid iterator.
+}
+
+int
+main()
+{
+  test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge1_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge1_neg.cc
new file mode 100644
index 00000000000..25b3b9e0c75
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge1_neg.cc
@@ -0,0 +1,32 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_map>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_multimap<int, int>;
+
+void
+test01()
+{
+  test_type c0
+    {
+     { 1, 1 }, { 1, 1 }, { 2, 2 },
+     { 2, 2 }, { 3, 3 }, { 3, 3 }
+    };
+  test_type c1 = c0;
+
+  auto it = c1.find(2);
+  VERIFY( it->second == 2 );
+
+  c0.merge(c1);
+
+  VERIFY( it != c1.end() ); // Invalid iterator.
+}
+
+int
+main()
+{
+  test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge2_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge2_neg.cc
new file mode 100644
index 00000000000..8d28d83b972
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge2_neg.cc
@@ -0,0 +1,32 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_map>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_multimap<int, int>;
+
+void
+test01()
+{
+  test_type c0
+    {
+     { 1, 1 }, { 1, 1 }, { 2, 2 },
+     { 2, 2 }, { 3, 3 }, { 3, 3 }
+    };
+  test_type c1 = c0;
+
+  auto it = c1.find(2);
+  VERIFY( it->second == 2 );
+
+  c0.merge(std::move(c1));
+
+  VERIFY( it != c1.end() ); // Invalid iterator.
+}
+
+int
+main()
+{
+  test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge3_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge3_neg.cc
new file mode 100644
index 00000000000..5db91a27ca0
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge3_neg.cc
@@ -0,0 +1,32 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_map>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_multimap<int, int>;
+
+void
+test01()
+{
+  test_type c0
+    {
+     { 1, 1 }, { 1, 1 }, { 2, 2 },
+     { 2, 2 }, { 3, 3 }, { 3, 3 }
+    };
+  std::unordered_map<int, int> c1{ { 1, 1 }, { 2, 2 }, { 3, 3 } };
+
+  auto it = c1.find(2);
+  VERIFY( it->second == 2 );
+
+  c0.merge(c1);
+
+  VERIFY( it != c1.end() ); // Invalid iterator.
+}
+
+int
+main()
+{
+  test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge4_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge4_neg.cc
new file mode 100644
index 00000000000..a1636703569
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multimap/debug/merge4_neg.cc
@@ -0,0 +1,32 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_map>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_multimap<int, int>;
+
+void
+test01()
+{
+  test_type c0
+    {
+     { 1, 1 }, { 1, 1 }, { 2, 2 },
+     { 2, 2 }, { 3, 3 }, { 3, 3 }
+    };
+  std::unordered_map<int, int> c1{ { 1, 1 }, { 2, 2 }, { 3, 3 } };
+
+  auto it = c1.find(2);
+  VERIFY( it->second == 2 );
+
+  c0.merge(std::move(c1));
+
+  VERIFY( it != c1.end() ); // Invalid iterator.
+}
+
+int
+main()
+{
+  test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge1_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge1_neg.cc
new file mode 100644
index 00000000000..bce8da7f6cf
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge1_neg.cc
@@ -0,0 +1,28 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_set>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_multiset<int>;
+
+void
+test01()
+{
+  test_type c0{ 1, 1, 2, 2, 3, 3 };
+  test_type c1 = c0;
+
+  auto it = c1.find(2);
+  VERIFY( *it == 2 );
+
+  c0.merge(c1);
+
+  VERIFY( it != c1.end() ); // Invalid iterator.
+}
+
+int
+main()
+{
+  test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge2_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge2_neg.cc
new file mode 100644
index 00000000000..72317a32e89
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge2_neg.cc
@@ -0,0 +1,28 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_set>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_multiset<int>;
+
+void
+test01()
+{
+  test_type c0{ 1, 1, 2, 2, 3, 3 };
+  test_type c1 = c0;
+
+  auto it = c1.find(2);
+  VERIFY( *it == 2 );
+
+  c0.merge(std::move(c1));
+
+  VERIFY( it != c1.end() ); // Invalid iterator.
+}
+
+int
+main()
+{
+  test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge3_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge3_neg.cc
new file mode 100644
index 00000000000..1b1f4870dd1
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge3_neg.cc
@@ -0,0 +1,28 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_set>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_multiset<int>;
+
+void
+test01()
+{
+  test_type c0{ 1, 1, 2, 2, 3, 3 };
+  std::unordered_set<int> c1{ 1, 2, 3 };
+
+  auto it = c1.find(2);
+  VERIFY( *it == 2 );
+
+  c0.merge(c1);
+
+  VERIFY( it != c1.end() ); // Invalid iterator.
+}
+
+int
+main()
+{
+  test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge4_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge4_neg.cc
new file mode 100644
index 00000000000..5005cf8468a
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_multiset/debug/merge4_neg.cc
@@ -0,0 +1,28 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_set>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_multiset<int>;
+
+void
+test01()
+{
+  test_type c0{ 1, 1, 2, 2, 3, 3 };
+  std::unordered_set<int> c1{ 1, 2, 3 };
+
+  auto it = c1.find(2);
+  VERIFY( *it == 2 );
+
+  c0.merge(std::move(c1));
+
+  VERIFY( it != c1.end() ); // Invalid iterator.
+}
+
+int
+main()
+{
+  test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge1_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge1_neg.cc
new file mode 100644
index 00000000000..8a2bc6e468f
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge1_neg.cc
@@ -0,0 +1,31 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_set>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_set<int>;
+
+void
+test01()
+{
+  test_type c0{ 1, 2, 3, 5, 6 };
+  test_type c1{ 1, 2, 3, 4 };
+
+  auto it2 = c1.find(2);
+  auto it4 = c1.find(4);
+  VERIFY( *it2 == 2 );
+  VERIFY( *it4 == 4 );
+
+  c0.merge(c1);
+
+  VERIFY( *it2 == 2 );
+  VERIFY( it2 != it4 ); // Invalid iterator.
+}
+
+int
+main()
+{
+  test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge2_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge2_neg.cc
new file mode 100644
index 00000000000..3ac96540770
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge2_neg.cc
@@ -0,0 +1,31 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_set>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_set<int>;
+
+void
+test01()
+{
+  test_type c0{ 1, 2, 3, 5, 6 };
+  test_type c1{ 1, 2, 3, 4 };
+
+  auto it2 = c1.find(2);
+  auto it4 = c1.find(4);
+  VERIFY( *it2 == 2 );
+  VERIFY( *it4 == 4 );
+
+  c0.merge(std::move(c1));
+
+  VERIFY( *it2 == 2 );
+  VERIFY( it2 != it4 ); // Invalid iterator.
+}
+
+int
+main()
+{
+  test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge3_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge3_neg.cc
new file mode 100644
index 00000000000..7e93b55d507
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge3_neg.cc
@@ -0,0 +1,33 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_set>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_set<int>;
+
+void
+test01()
+{
+  test_type c0{ 1, 2, 3, 5, 6, 7 };
+  std::unordered_multiset<int> c1{ 1, 1, 2, 2, 3, 3, 4, 4, 5 };
+
+  auto it1 = c1.find(1);
+  auto it41 = c1.find(4);
+  auto it42 = it41;
+  ++it42;
+  VERIFY( *it42 == 4 );
+
+  c0.merge(c1);
+
+  VERIFY( *it1 == 1 );
+  VERIFY( c1.count(4) == 1 );
+  VERIFY( it41 != it42 ); // Invalid iterator.
+}
+
+int
+main()
+{
+  test01();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge4_neg.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge4_neg.cc
new file mode 100644
index 00000000000..14c8ff63b05
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/debug/merge4_neg.cc
@@ -0,0 +1,33 @@
+// { dg-do run { target c++17 xfail *-*-* } }
+// { dg-require-debug-mode "" }
+
+#include <unordered_set>
+#include <algorithm>
+#include <testsuite_hooks.h>
+
+using test_type = std::unordered_set<int>;
+
+void
+test01()
+{
+  test_type c0{ 1, 2, 3, 5, 6, 7 };
+  std::unordered_multiset<int> c1{ 1, 1, 2, 2, 3, 3, 4, 4, 5 };
+
+  auto it1 = c1.find(1);
+  auto it41 = c1.find(4);
+  auto it42 = it41;
+  ++it42;
+  VERIFY( *it42 == 4 );
+
+  c0.merge(std::move(c1));
+
+  VERIFY( *it1 == 1 );
+  VERIFY( c1.count(4) == 1 );
+  VERIFY( it41 != it42 ); // Invalid iterator.
+}
+
+int
+main()
+{
+  test01();
+}
diff --git a/libstdc++-v3/testsuite/util/testsuite_abi.h b/libstdc++-v3/testsuite/util/testsuite_abi.h
index 667c46c33d3..4a0cf64f6fb 100644
--- a/libstdc++-v3/testsuite/util/testsuite_abi.h
+++ b/libstdc++-v3/testsuite/util/testsuite_abi.h
@@ -24,7 +24,11 @@
 #include <locale>
 #if __cplusplus >= 201103L
 # include <unordered_map>
+# ifdef _GLIBCXX_DEBUG
+namespace unord = std::_GLIBCXX_STD_C;
+# else
 namespace unord = std;
+# endif
 #else
 # include <tr1/unordered_map>
 namespace unord = std::tr1;