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++,
<libstd...@gcc.gnu.org <mailto:libstdc%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++
> <libstd...@gcc.gnu.org <mailto:libstdc%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 --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index ff8af2201cd..26f55cbc51b 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -1062,16 +1062,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
/// Merge from a compatible container into one with unique keys.
- template<typename _Compatible_Hashtable>
+ template<typename _Compatible_Hashtable, typename _OnExtract>
void
- _M_merge_unique(_Compatible_Hashtable& __src) noexcept
+ _M_merge_unique(_Compatible_Hashtable& __src,
+ const _OnExtract& __on_extract)
{
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);
@@ -1080,6 +1081,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (_M_find_node(__bkt, __k, __code) == nullptr)
{
auto __nh = __src.extract(__pos);
+ __on_extract(__pos);
_M_insert_unique_node(__bkt, __code, __nh._M_ptr, __n_elt);
__nh._M_ptr = nullptr;
__n_elt = 1;
@@ -1090,17 +1092,23 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
}
/// Merge from a compatible container into one with equivalent keys.
- template<typename _Compatible_Hashtable>
+ template<typename _Compatible_Hashtable, typename _OnExtract>
void
- _M_merge_multi(_Compatible_Hashtable& __src) noexcept
+ _M_merge_multi(_Compatible_Hashtable& __src,
+ const _OnExtract& __on_extract)
{
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++;
+ auto __nh = __src.extract(__pos);
+ __on_extract(__pos);
+ _M_reinsert_node_multi(cend(), std::move(__nh));
+ }
}
#endif // C++17
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 994c7b61046..23ebd137467 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -59,19 +59,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/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h
index 2261e6685ea..e7e68c5e3eb 100644
--- a/libstdc++-v3/include/bits/unordered_map.h
+++ b/libstdc++-v3/include/bits/unordered_map.h
@@ -806,15 +806,39 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
{ _M_h.swap(__x._M_h); }
#if __cplusplus > 201402L
+ protected:
template<typename, typename, typename>
friend class std::_Hash_merge_helper;
+ template<typename _H2, typename _P2, typename _OnExtract>
+ void
+ _M_merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source,
+ const _OnExtract& __on_extract)
+ {
+ using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
+ _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source),
+ __on_extract);
+ }
+
+ template<typename _H2, typename _P2, typename _OnExtract>
+ void
+ _M_merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source,
+ const _OnExtract& __on_extract)
+ {
+ using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
+ _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source),
+ __on_extract);
+ }
+
+ public:
template<typename _H2, typename _P2>
void
merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
{
- using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
- _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
+ using _Um_ite
+ = typename unordered_map<_Key, _Tp,
+ _H2, _P2, _Alloc>::const_iterator;
+ _M_merge(__source, [](_Um_ite){ });
}
template<typename _H2, typename _P2>
@@ -826,8 +850,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
void
merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
{
- using _Merge_helper = _Hash_merge_helper<unordered_map, _H2, _P2>;
- _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
+ using _Umm_ite =
+ typename unordered_multimap<_Key, _Tp,
+ _H2, _P2, _Alloc>::const_iterator;
+ _M_merge(__source, [](_Umm_ite){ });
}
template<typename _H2, typename _P2>
@@ -1747,16 +1773,41 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
{ _M_h.swap(__x._M_h); }
#if __cplusplus > 201402L
+ protected:
template<typename, typename, typename>
friend class std::_Hash_merge_helper;
- template<typename _H2, typename _P2>
+ template<typename _H2, typename _P2, typename _OnExtract>
void
- merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
+ _M_merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source,
+ const _OnExtract& __on_extract)
{
using _Merge_helper
= _Hash_merge_helper<unordered_multimap, _H2, _P2>;
- _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
+ _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source),
+ __on_extract);
+ }
+
+ template<typename _H2, typename _P2, typename _OnExtract>
+ void
+ _M_merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source,
+ const _OnExtract& __on_extract)
+ {
+ using _Merge_helper
+ = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
+ _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source),
+ __on_extract);
+ }
+
+ public:
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_multimap<_Key, _Tp, _H2, _P2, _Alloc>& __source)
+ {
+ using _Umm_ite =
+ typename unordered_multimap<_Key, _Tp,
+ _H2, _P2, _Alloc>::const_iterator;
+ _M_merge(__source, [](_Umm_ite){ });
}
template<typename _H2, typename _P2>
@@ -1768,9 +1819,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
void
merge(unordered_map<_Key, _Tp, _H2, _P2, _Alloc>& __source)
{
- using _Merge_helper
- = _Hash_merge_helper<unordered_multimap, _H2, _P2>;
- _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
+ using _Um_ite
+ = typename unordered_map<_Key, _Tp,
+ _H2, _P2, _Alloc>::const_iterator;
+ _M_merge(__source, [](_Um_ite){ });
}
template<typename _H2, typename _P2>
diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h
index ac4a890d25a..4da83c69320 100644
--- a/libstdc++-v3/include/bits/unordered_set.h
+++ b/libstdc++-v3/include/bits/unordered_set.h
@@ -588,15 +588,39 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
{ _M_h.swap(__x._M_h); }
#if __cplusplus > 201402L
+ protected:
template<typename, typename, typename>
friend class std::_Hash_merge_helper;
+ template<typename _H2, typename _P2, typename _OnExtract>
+ void
+ _M_merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source,
+ const _OnExtract& __on_extract)
+ {
+ using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;
+ _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source),
+ __on_extract);
+ }
+
+ template<typename _H2, typename _P2, typename _OnExtract>
+ void
+ _M_merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source,
+ const _OnExtract& __on_extract)
+ {
+ using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;
+ _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source),
+ __on_extract);
+ }
+
+ public:
template<typename _H2, typename _P2>
void
merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
{
- using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;
- _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
+ using _Us_ite
+ = typename unordered_set<_Value,
+ _H2, _P2, _Alloc>::const_iterator;
+ _M_merge(__source, [](_Us_ite){ });
}
template<typename _H2, typename _P2>
@@ -608,8 +632,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
void
merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
{
- using _Merge_helper = _Hash_merge_helper<unordered_set, _H2, _P2>;
- _M_h._M_merge_unique(_Merge_helper::_S_get_table(__source));
+ using _Ums_ite
+ = typename unordered_multiset<_Value,
+ _H2, _P2, _Alloc>::const_iterator;
+ _M_merge(__source, [](_Ums_ite){ });
}
template<typename _H2, typename _P2>
@@ -1436,16 +1462,41 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
{ _M_h.swap(__x._M_h); }
#if __cplusplus > 201402L
+ protected:
template<typename, typename, typename>
friend class std::_Hash_merge_helper;
- template<typename _H2, typename _P2>
+ template<typename _H2, typename _P2, typename _OnExtract>
void
- merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
+ _M_merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source,
+ const _OnExtract& __on_extract)
{
using _Merge_helper
= _Hash_merge_helper<unordered_multiset, _H2, _P2>;
- _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
+ _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source),
+ __on_extract);
+ }
+
+ template<typename _H2, typename _P2, typename _OnExtract>
+ void
+ _M_merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source,
+ const _OnExtract& __on_extract)
+ {
+ using _Merge_helper
+ = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
+ _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source),
+ __on_extract);
+ }
+
+ public:
+ template<typename _H2, typename _P2>
+ void
+ merge(unordered_multiset<_Value, _H2, _P2, _Alloc>& __source)
+ {
+ using _UMs_ite
+ = typename unordered_multiset<_Value,
+ _H2, _P2, _Alloc>::const_iterator;
+ _M_merge(__source, [](_UMs_ite){ });
}
template<typename _H2, typename _P2>
@@ -1457,9 +1508,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
void
merge(unordered_set<_Value, _H2, _P2, _Alloc>& __source)
{
- using _Merge_helper
- = _Hash_merge_helper<unordered_multiset, _H2, _P2>;
- _M_h._M_merge_multi(_Merge_helper::_S_get_table(__source));
+ using _Us_ite
+ = typename unordered_set<_Value,
+ _H2, _P2, _Alloc>::const_iterator;
+ _M_merge(__source, [](_Us_ite){ });
}
template<typename _H2, typename _P2>
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..a00eb8fe2e0 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,52 @@ 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)
+ {
+ using __base_it_t = decltype(__source._M_base().cbegin());
+ auto __on_extract =
+ [&__source](__base_it_t __extracted_it)
+ {
+ auto __pred = [__extracted_it](auto __it)
+ { return __it == __extracted_it; };
+ __source._M_invalidate_if(__pred);
+ __source._M_invalidate_local_if(__pred);
+ };
+ this->_M_merge(__source._M_base(), __on_extract);
+ }
+
+ 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)
+ {
+ using __base_it_t = decltype(__source._M_base().cbegin());
+ auto __on_extract =
+ [&__source](__base_it_t __extracted_it)
+ {
+ auto __pred = [__extracted_it](auto __it)
+ { return __it == __extracted_it; };
+ __source._M_invalidate_if(__pred);
+ __source._M_invalidate_local_if(__pred);
+ };
+ this->_M_merge(__source._M_base(), __on_extract);
+ }
+
+ 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 +627,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 +670,9 @@ namespace __debug
}
#endif
+ using _Base::operator[];
+ using _Base::at;
+
size_type
erase(const key_type& __key)
{
@@ -651,6 +719,9 @@ namespace __debug
return { __next, this };
}
+ using _Base::rehash;
+ using _Base::reserve;
+
_Base&
_M_base() noexcept { return *this; }
@@ -843,7 +914,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 +928,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 +1029,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 +1116,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 +1278,52 @@ 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)
+ {
+ using __base_it_t = decltype(__source._M_base().cbegin());
+ auto __on_extract =
+ [&__source](__base_it_t __extracted_it)
+ {
+ auto __pred = [__extracted_it](auto __it)
+ { return __it == __extracted_it; };
+ __source._M_invalidate_if(__pred);
+ __source._M_invalidate_local_if(__pred);
+ };
+ this->_M_merge(__source._M_base(), __on_extract);
+ }
+
+ 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)
+ {
+ using __base_it_t = decltype(__source._M_base().cbegin());
+ auto __on_extract =
+ [&__source](__base_it_t __extracted_it)
+ {
+ auto __pred = [__extracted_it](auto __it)
+ { return __it == __extracted_it; };
+ __source._M_invalidate_if(__pred);
+ __source._M_invalidate_local_if(__pred);
+ };
+ this->_M_merge(__source._M_base(), __on_extract);
+ }
+
+ 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 +1350,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 +1443,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..3df02fcdef0 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,52 @@ 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)
+ {
+ using __base_it_t = decltype(__source._M_base().cbegin());
+ auto __on_extract =
+ [&__source](__base_it_t __extracted_it)
+ {
+ auto __pred = [__extracted_it](auto __it)
+ { return __it == __extracted_it; };
+ __source._M_invalidate_if(__pred);
+ __source._M_invalidate_local_if(__pred);
+ };
+ this->_M_merge(__source._M_base(), __on_extract);
+ }
+
+ 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)
+ {
+ using __base_it_t = decltype(__source._M_base().cbegin());
+ auto __on_extract =
+ [&__source](__base_it_t __extracted_it)
+ {
+ auto __pred = [__extracted_it](auto __it)
+ { return __it == __extracted_it; };
+ __source._M_invalidate_if(__pred);
+ __source._M_invalidate_local_if(__pred);
+ };
+ this->_M_merge(__source._M_base(), __on_extract);
+ }
+
+ 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 +514,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 +775,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 +783,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 +895,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 +982,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 +992,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 +1006,9 @@ namespace __debug
_Base::max_load_factor(__f);
}
+ using _Base::rehash;
+ using _Base::reserve;
+
template<typename... _Args>
iterator
emplace(_Args&&... __args)
@@ -1037,9 +1124,52 @@ 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)
+ {
+ using __base_it_t = decltype(__source._M_base().cbegin());
+ auto __on_extract =
+ [&__source](__base_it_t __extracted_it)
+ {
+ auto __pred = [__extracted_it](auto __it)
+ { return __it == __extracted_it; };
+ __source._M_invalidate_if(__pred);
+ __source._M_invalidate_local_if(__pred);
+ };
+ this->_M_merge(__source._M_base(), __on_extract);
+ }
+
+ 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)
+ {
+ using __base_it_t = decltype(__source._M_base().cbegin());
+ auto __on_extract =
+ [&__source](__base_it_t __extracted_it)
+ {
+ auto __pred = [__extracted_it](auto __it)
+ { return __it == __extracted_it; };
+ __source._M_invalidate_if(__pred);
+ __source._M_invalidate_local_if(__pred);
+ };
+ this->_M_merge(__source._M_base(), __on_extract);
+ }
+
+ 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 +1196,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;
