diff mbox series

[PATH,_GLIBCXX_DEBUG] Fix unordered container merge

Message ID 4eec3fb9-851e-3e4e-f9f4-1110db3af747@gmail.com
State New
Headers show
Series [PATH,_GLIBCXX_DEBUG] Fix unordered container merge | expand

Commit Message

François Dumont Oct. 13, 2021, 5:10 p.m. UTC
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 ?

François

Comments

Jonathan Wakely Oct. 14, 2021, 8:23 a.m. UTC | #1
On Wed, 13 Oct 2021 at 18:10, François Dumont via Libstdc++
<libstdc++@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());
    }
François Dumont Oct. 16, 2021, 1:47 p.m. UTC | #2
Hi

     Here is the new proposal. My only concern is that we are also using 
hash or equal_to functors in the guard destructor.

     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> 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());
>      }
>
Jonathan Wakely Oct. 16, 2021, 2:52 p.m. UTC | #3
On Sat, 16 Oct 2021, 14:49 François Dumont via Libstdc++, <
libstdc++@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> 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());
> >      }
> >
>
>
François Dumont Oct. 21, 2021, 4:51 p.m. UTC | #4
I eventually would like to propose a different approach.

I am adding a hook in normal implementation to let the _GLIBCXX_DEBUG 
code know when a node is being extracted. This way invalidation is only 
done by comparing nodes, no need to compute hash code for this operation.

The only drawback is that for each extraction we have a linear research 
on iterators to invalidate the correct one. I will implement next an 
optimization when hasher/equal_to are noexcept.

This patch also remove the invalid noexcept qualification on the 
_Hashtable merge methods and make use of const_iterator as it is what is 
expected by the extract.

Tested under Linux x86_64.

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());
>     >      }
>     >
>
Jonathan Wakely Oct. 21, 2021, 4:55 p.m. UTC | #5
On Thu, 21 Oct 2021 at 17:52, François Dumont <frs.dumont@gmail.com> wrote:

> I eventually would like to propose a different approach.
>
> I am adding a hook in normal implementation to let the _GLIBCXX_DEBUG code
> know when a node is being extracted. This way invalidation is only done by
> comparing nodes, no need to compute hash code for this operation.
>

Ugh, this is horrible, I don't like the normal mode depending on the debug
mode (even if it's just having to add hooks like this).

The previous patch seemed fine to me. Already an improvement on what is on
trunk now.
François Dumont Oct. 22, 2021, 5:22 a.m. UTC | #6
On 21/10/21 6:55 pm, Jonathan Wakely wrote:
>
>
> On Thu, 21 Oct 2021 at 17:52, François Dumont <frs.dumont@gmail.com 
> <mailto:frs.dumont@gmail.com>> wrote:
>
>     I eventually would like to propose a different approach.
>
>     I am adding a hook in normal implementation to let the
>     _GLIBCXX_DEBUG code know when a node is being extracted. This way
>     invalidation is only done by comparing nodes, no need to compute
>     hash code for this operation.
>
>
> Ugh, this is horrible, I don't like the normal mode depending on the 
> debug mode (even if it's just having to add hooks like this).

Yes, I was relunctant to do so but in this case I was not able to find 
another way to provide the same result as here.

Ok, I'll come back to the other patch and just invalidate all iterators 
in case of exception.

>
> The previous patch seemed fine to me. Already an improvement on what 
> is on trunk now.
>
François Dumont Oct. 25, 2021, 6:08 p.m. UTC | #7
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());
>     >      }
>     >
>
diff mbox series

Patch

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..06d0e91282c 100644
--- a/libstdc++-v3/include/debug/safe_unordered_container.h
+++ b/libstdc++-v3/include/debug/safe_unordered_container.h
@@ -72,6 +72,7 @@  namespace __gnu_debug
 		{ return __it != __local_end; });
       }
 
+    public:
       void
       _M_invalidate_all()
       {
diff --git a/libstdc++-v3/include/debug/unordered_map b/libstdc++-v3/include/debug/unordered_map
index bb697d364ea..d359d285f99 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,72 @@  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 __size = __source.size();
+	  _Base::merge(__source._M_base());
+	  if (__source.size() == __size)
+	    return;
+
+	  if (__source.empty())
+	    __source._M_invalidate_all();
+	  else
+	    {
+	      auto __pred = [&__source](auto __it)
+			    { return __source.count(__it->first) == 0; };
+	      __source._M_invalidate_if(__pred);
+	      __source._M_invalidate_local_if(__pred);
+	    }
+	}
+
+      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 __size = __source.size();
+	  _Base::merge(__source._M_base());
+	  if (__source.size() == __size)
+	    return;
+
+	  if (__source.empty())
+	    __source._M_invalidate_all();
+	  else
+	    {
+	      _GLIBCXX_STD_C::unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>&
+		__base_src = __source;
+	      auto __pred = [&__base_src](auto __it)
+		{
+		  auto __rng = __base_src.equal_range(__it->first);
+		  for (auto __rit = __rng.first; __rit != __rng.second; ++__rit)
+		    {
+		      if (__it == __rit)
+			return false;
+		    }
+
+		  return true;
+		};
+	      __source._M_invalidate_if(__pred);
+	      __source._M_invalidate_local_if(__pred);
+	    }
+	}
+
+      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 +647,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 +690,9 @@  namespace __debug
 	}
 #endif
 
+      using _Base::operator[];
+      using _Base::at;
+
       size_type
       erase(const key_type& __key)
       {
@@ -651,6 +739,9 @@  namespace __debug
 	return { __next, this };
       }
 
+      using _Base::rehash;
+      using _Base::reserve;
+
       _Base&
       _M_base() noexcept	{ return *this; }
 
@@ -843,7 +934,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 +948,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 +1049,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 +1136,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 +1298,37 @@  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)
+	{
+	  _Base::merge(__source._M_base());
+	  __source._M_invalidate_all();
+	}
+
+      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)
+	{
+	  _Base::merge(__source._M_base());
+	  __source._M_invalidate_all();
+	}
+
+      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 +1355,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 +1448,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..10f44903b8f 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,71 @@  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 __size = __source.size();
+	  _Base::merge(__source._M_base());
+	  if (__source.size() == __size)
+	    return;
+
+	  if (__source.empty())
+	    __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);
+	    }
+	}
+
+      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 __size = __source.size();
+	  _Base::merge(__source._M_base());
+	  if (__source.size() == __size)
+	    return;
+
+	  if (__source.empty())
+	    __source._M_invalidate_all();
+	  else
+	    {
+	      _GLIBCXX_STD_C::unordered_multiset<_Value, _H2, _P2, _Alloc>&
+		__base_src = __source;
+	      auto __pred = [&__base_src](auto __it)
+		{
+		  auto __rng = __base_src.equal_range(*__it);
+		  for (auto __rit = __rng.first; __rit != __rng.second; ++__rit)
+		    {
+		      if (__it == __rit)
+			return false;
+		    }
+
+		  return true;
+		};
+	      __source._M_invalidate_if(__pred);
+	      __source._M_invalidate_local_if(__pred);
+	    }
+	}
+
+      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 +533,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 +794,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 +802,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 +914,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 +1001,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 +1011,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 +1025,9 @@  namespace __debug
 	_Base::max_load_factor(__f);
       }
 
+      using _Base::rehash;
+      using _Base::reserve;
+
       template<typename... _Args>
 	iterator
 	emplace(_Args&&... __args)
@@ -1037,9 +1143,36 @@  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)
+	{
+	  _Base::merge(__source._M_base());
+	  __source._M_invalidate_all();
+	}
+
+      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)
+	{
+	  _Base::merge(__source._M_base());
+	  __source._M_invalidate_all();
+	}
+
+      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 +1199,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..69e8a6741a8
--- /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, 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(c1);
+
+  VERIFY( it2->second == 2 );
+  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;