Changes in v6: (Note, this was recently mis-posted as v5.)
- More testing for op[] and at(): move-from key argument when and
only when permitted.
Changes in v5:
- Fix typos in set/modifiers/hetero/insert.cc.
- Fix chart in commit message.
Changes in v4:
- Rebase on committed P2077 erasures.
- Remove conditional compilation on impl helpers in
bits/stl_tree.h, hashtable.h, hashtable_policy.h.
- Regularize ChangeLog format.
- Test propagation of heterogeneous key's value category
through to conversion to key_type.
- Test propagation of variadic-arguments' value categories
from try_emplace through to underlying constructors.
- Regularize template argument name s/_Mapped/_Obj/.
Changes in v3:
- Make tests run, and pass.
- Note added members in Changelog.
Change in v2: fix remaining regression, SEGV in 92878_92947.cc.
Implements P2353R5 "Extending associative containers with the
remaining heterogeneous overloads". Adds overloads templated on
heterogeneous key types for several members of associative
containers, particularly insertions:
un- un- un- unordered
set map mset mmap set map mset mmap
@ . . . @ . . . insert
. @ . . . @ . . op[], at, try_emplace,
insert_or_assign
. . . . @ @ @ @ bucket
(Nothing is added to the multiset or multimap tree containers.)
All the insert*() and try_emplace() members also get a hinted
overload. The at() members get const and non-const overloads.
The new overloads enforce concept __heterogeneous_tree_key or
__heterogeneous_hash_key, as in P2077, to enforce that the
function objects provided meet requirements, and that the key
supplied is not an iterator or the native key. Insertions
implicitly construct the required key_type object from the
argument, by move where permitted.
Doxygen annotations are improved.
libstdc++-v3/ChangeLog:
PR libstdc++/117402
* include/bits/stl_map.h (operator[], at (2x), try_emplace (2x),
insert_or_assign (2x)): Add overloads.
* include/bits/unordered_map.h: Same, plus...
(bucket (2x)): Add overloads.
* include/bits/stl_set.h (insert (2x)): Add overloads.
* include/bits/unordered_set.h: Same, plus...
(bucket (2x)): Add overloads.
* include/bits/hashtable.h (_M_bucket_tr, _M_insert_tr): Define.
* include/bits/hashtable_policy.h (_M_index_to_tr, _M_at_tr (2x),
_M_index_to_tr): Define.
* include/bits/stl_tree.h (_M_get_insert_unique_pos_tr,
_M_get_insert_hint_unique_pos_tr): Define.
* include/bits/version.def (associative_heterogeneous_insertion):
Define.
* include/bits/version.h: Regenerate.
* include/std/map (__glibcxx_want_associative_heterogeneous_insertion):
Define macro.
* include/std/set: Same.
* include/std/unordered_map: Same.
* include/std/unordered_set: Same.
* testsuite/23_containers/map/modifiers/hetero/insert.cc: New tests.
* testsuite/23_containers/set/modifiers/hetero/insert.cc: Same.
* testsuite/23_containers/unordered_map/modifiers/hetero/insert.cc:
Same.
* testsuite/23_containers/unordered_multimap/modifiers/hetero/insert.cc:
Same.
* testsuite/23_containers/unordered_multiset/modifiers/hetero/insert.cc:
Same.
* testsuite/23_containers/unordered_set/modifiers/hetero/insert.cc:
Same.
---
libstdc++-v3/include/bits/hashtable.h | 27 ++
libstdc++-v3/include/bits/hashtable_policy.h | 60 ++-
libstdc++-v3/include/bits/stl_map.h | 126 ++++++-
libstdc++-v3/include/bits/stl_set.h | 21 ++
libstdc++-v3/include/bits/stl_tree.h | 106 +++++-
libstdc++-v3/include/bits/unordered_map.h | 96 +++++
libstdc++-v3/include/bits/unordered_set.h | 32 ++
libstdc++-v3/include/bits/version.def | 8 +
libstdc++-v3/include/bits/version.h | 10 +
libstdc++-v3/include/std/map | 1 +
libstdc++-v3/include/std/set | 1 +
libstdc++-v3/include/std/unordered_map | 1 +
libstdc++-v3/include/std/unordered_set | 1 +
.../map/modifiers/hetero/insert.cc | 341 +++++++++++++++++
.../set/modifiers/hetero/insert.cc | 120 ++++++
.../unordered_map/modifiers/hetero/insert.cc | 353 ++++++++++++++++++
.../modifiers/hetero/insert.cc | 57 +++
.../modifiers/hetero/insert.cc | 56 +++
.../unordered_set/modifiers/hetero/insert.cc | 134 +++++++
19 files changed, 1544 insertions(+), 7 deletions(-)
create mode 100644
libstdc++-v3/testsuite/23_containers/map/modifiers/hetero/insert.cc
create mode 100644
libstdc++-v3/testsuite/23_containers/set/modifiers/hetero/insert.cc
create mode 100644
libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/hetero/insert.cc
create mode 100644
libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/hetero/insert.cc
create mode 100644
libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/hetero/insert.cc
create mode 100644
libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/hetero/insert.cc
diff --git a/libstdc++-v3/include/bits/hashtable.h
b/libstdc++-v3/include/bits/hashtable.h
index 48695c013f3..fc7a5aae595 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -700,6 +700,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
bucket(const key_type& __k) const
{ return _M_bucket_index(this->_M_hash_code(__k)); }
+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26, P2363
+ template <typename _Kt>
+ size_type
+ _M_bucket_tr(const _Kt& __k) const
+ { return _M_bucket_index(this->_M_hash_code_tr(__k)); }
+#endif
+
local_iterator
begin(size_type __bkt)
{
@@ -1097,6 +1104,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
std::pair<iterator, bool>
try_emplace(const_iterator, _KType&& __k, _Args&&... __args)
{
+ // Note we ignore the hint argument.
__hash_code __code;
size_type __bkt;
if (auto __loc = _M_locate(__k))
@@ -1117,6 +1125,24 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__node._M_node = nullptr;
return { __it, true };
}
+
+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26, P2363
+ template<typename _Kt>
+ std::pair<iterator, bool>
+ _M_insert_tr(_Kt&& __k)
+ {
+ auto __loc = _M_locate_tr(__k);
+ if (__loc)
+ return { iterator(__loc), false };
+
+ _Scoped_node __node(
+ this->_M_allocate_node(std::forward<_Kt>(__k)), this);
+ auto __it = _M_insert_unique_node(
+ __loc._M_bucket_index, __loc._M_hash_code, __node._M_node);
+ __node._M_node = nullptr;
+ return { __it, true };
+ }
+#endif
#endif
void
@@ -2363,6 +2389,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__node._M_node = nullptr;
return { __pos, true };
}
+
#pragma GCC diagnostic pop
template<typename _Key, typename _Value, typename _Alloc,
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h
b/libstdc++-v3/include/bits/hashtable_policy.h
index 6d7bde1e785..92fa6e82e5b 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -872,6 +872,33 @@ namespace __detail
__throw_out_of_range(__N("unordered_map::at"));
return __ite->second;
}
+
+ // op[] for transparent heterogeneous key
+ template <typename _Kt>
+ mapped_type&
+ _M_index_to_tr(const _Kt& __k);
+
+ // _GLIBCXX_RESOLVE_LIB_DEFECTS
+ // DR 761. unordered_map needs an at() member function.
+ template <typename _Kt>
+ mapped_type&
+ _M_at_tr(const _Kt& __k)
+ {
+ auto __ite = static_cast<__hashtable*>(this)->_M_find_tr(__k);
+ if (!__ite._M_cur)
+ __throw_out_of_range(__N("unordered_map::at"));
+ return __ite->second;
+ }
+
+ template <typename _Kt>
+ const mapped_type&
+ _M_at_tr(const _Kt& __k) const
+ {
+ auto __ite = static_cast<const __hashtable*>(this)->_M_find_tr(__k);
+ if (!__ite._M_cur)
+ __throw_out_of_range(__N("unordered_map::at"));
+ return __ite->second;
+ }
};
template<typename _Key, typename _Val, typename _Alloc, typename _Equal,
@@ -901,6 +928,33 @@ namespace __detail
return __pos->second;
}
+ // op[] for heterogeneous keys
+ template<typename _Key, typename _Val, typename _Alloc, typename _Equal,
+ typename _Hash, typename _RangeHash, typename _Unused,
+ typename _RehashPolicy, typename _Traits>
+ template <typename _Kt>
+ auto
+ _Map_base<_Key, pair<const _Key, _Val>, _Alloc, _Select1st, _Equal,
+ _Hash, _RangeHash, _Unused, _RehashPolicy, _Traits, true>::
+ _M_index_to_tr(const _Kt& __k)
+ -> mapped_type&
+ {
+ __hashtable* __h = static_cast<__hashtable*>(this);
+ __hash_code __code = __h->_M_hash_code_tr(__k);
+ size_t __bkt = __h->_M_bucket_index(__code);
+ if (auto __node = __h->_M_find_node_tr(__bkt, __k, __code))
+ return __node->_M_v().second;
+
+ typename __hashtable::_Scoped_node __node {
+ __h, std::piecewise_construct,
+ std::tuple<key_type>(__k), std::tuple<>()
+ };
+ auto __pos
+ = __h->_M_insert_unique_node(__bkt, __code, __node._M_node);
+ __node._M_node = nullptr;
+ return __pos->second;
+ }
+
template<typename _Key, typename _Val, typename _Alloc, typename _Equal,
typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits>
@@ -1413,8 +1467,7 @@ namespace __detail
template<typename _Kt>
bool
_M_key_equals_tr(const _Kt& __k,
- const _Hash_node_value<_Value,
- __hash_cached::value>& __n) const
+ const _Hash_node_value<_Value, __hash_cached::value>& __n) const
{
static_assert(
__is_invocable<const _Equal&, const _Kt&, const _Key&>{},
@@ -1439,8 +1492,7 @@ namespace __detail
template<typename _Kt>
bool
_M_equals_tr(const _Kt& __k, __hash_code __c,
- const _Hash_node_value<_Value,
- __hash_cached::value>& __n) const
+ const _Hash_node_value<_Value, __hash_cached::value>& __n) const
{
if constexpr (__hash_cached::value)
if (__c != __n._M_hash_code)
diff --git a/libstdc++-v3/include/bits/stl_map.h
b/libstdc++-v3/include/bits/stl_map.h
index 4cb0c982c3d..f4b0982af72 100644
--- a/libstdc++-v3/include/bits/stl_map.h
+++ b/libstdc++-v3/include/bits/stl_map.h
@@ -511,6 +511,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
max_size() const _GLIBCXX_NOEXCEPT
{ return _M_t.max_size(); }
+ ///@{
// [23.3.1.2] element access
/**
* @brief Subscript ( @c [] ) access to %map data.
@@ -560,6 +561,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
}
#endif
+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
+ template <__heterogeneous_tree_key<map> _Kt>
+ mapped_type&
+ operator[](_Kt&& __k)
+ { return try_emplace(std::forward<_Kt>(__k)).first->second; }
+#endif
+ ///@}
+
+ ///@{
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// DR 464. Suggestion for new member functions in standard containers.
/**
@@ -578,6 +588,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
return (*__i).second;
}
+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
+ template <__heterogeneous_tree_key<map> _Kt>
+ mapped_type&
+ at(const _Kt& __k)
+ {
+ iterator __i = lower_bound(__k);
+ if (__i == end() || key_comp()(__k, (*__i).first))
+ __throw_out_of_range(__N("map::at"));
+ return (*__i).second;
+ }
+#endif
+
const mapped_type&
at(const key_type& __k) const
{
@@ -587,6 +609,19 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
return (*__i).second;
}
+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
+ template <__heterogeneous_tree_key<map> _Kt>
+ const mapped_type&
+ at(const _Kt& __k) const
+ {
+ const_iterator __i = lower_bound(__k);
+ if (__i == end() || key_comp()(__k, (*__i).first))
+ __throw_out_of_range(__N("map::at"));
+ return (*__i).second;
+ }
+#endif
+ ///@}
+
// modifiers
#if __cplusplus >= 201103L
/**
@@ -728,6 +763,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
#endif // C++17
#ifdef __glibcxx_map_try_emplace // C++ >= 17 && HOSTED
+ ///@{
/**
* @brief Attempts to build and insert a std::pair into the %map.
*
@@ -781,6 +817,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
return {__i, false};
}
+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
+ template <__heterogeneous_tree_key<map> _Kt, typename ..._Args>
+ pair<iterator, bool>
+ try_emplace(_Kt&& __k, _Args&&... __args)
+ {
+ iterator __i = lower_bound(__k);
+ if (__i == end() || key_comp()(__k, (*__i).first))
+ {
+ __i = _M_t._M_emplace_hint_unique(__i, std::piecewise_construct,
+ std::forward_as_tuple(std::forward<_Kt>(__k)),
+ std::forward_as_tuple(std::forward<_Args>(__args)...));
+ return {__i, true};
+ }
+ return {__i, false};
+ }
+#endif
+ ///@}
+
+ ///@{
/**
* @brief Attempts to build and insert a std::pair into the %map.
*
@@ -845,6 +900,26 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
}
#endif
+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
+ template <__heterogeneous_tree_key<map> _Kt, typename ..._Args>
+ iterator
+ try_emplace(const_iterator __hint, _Kt&& __k, _Args&&... __args)
+ {
+ iterator __i;
+ auto __true_hint = _M_t._M_get_insert_hint_unique_pos_tr(__hint, __k);
+ if (__true_hint.second)
+ __i = _M_t._M_emplace_hint_unique(iterator(__true_hint.second),
+ std::piecewise_construct,
+ std::forward_as_tuple(std::forward<_Kt>(__k)),
+ std::forward_as_tuple(std::forward<_Args>(__args)...));
+ else
+ __i = iterator(__true_hint.first);
+ return __i;
+ }
+#endif
+ ///@}
+
+ ///@{
/**
* @brief Attempts to insert a std::pair into the %map.
* @param __x Pair to be inserted (see std::make_pair for easy
@@ -896,7 +971,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
return _M_t._M_emplace_unique(std::forward<_Pair>(__x));
}
#endif
- /// @}
+ ///@}
#if __cplusplus >= 201103L
/**
@@ -929,6 +1004,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
}
#endif
+ ///@{
/**
* @brief Attempts to insert a std::pair into the %map.
* @param __position An iterator that serves as a hint as to where the
@@ -992,6 +1068,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
{ _M_t._M_insert_range_unique(__first, __last); }
#if __cplusplus > 201402L
+ ///@{
/**
* @brief Attempts to insert or assign a std::pair into the %map.
* @param __k Key to use for finding a possibly existing pair in
@@ -1046,6 +1123,29 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
return {__i, false};
}
+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
+ template <__heterogeneous_tree_key<map> _Kt, typename _Obj>
+ pair<iterator, bool>
+ insert_or_assign(_Kt&& __k, _Obj&& __obj)
+ {
+ iterator __i = lower_bound(__k);
+ if (__i == end() || key_comp()(__k, (*__i).first))
+ {
+ __i = _M_t._M_emplace_hint_unique(__i,
+ std::piecewise_construct,
+ std::forward_as_tuple(std::forward<_Kt>(__k)),
+ std::forward_as_tuple(std::forward<_Obj>(__obj)));
+ return {__i, true};
+ }
+ (*__i).second = std::forward<_Obj>(__obj);
+ return {__i, false};
+ }
+#endif
+ ///@}
+#endif
+
+#if __cplusplus > 201402L
+ ///@{
/**
* @brief Attempts to insert or assign a std::pair into the %map.
* @param __hint An iterator that serves as a hint as to where the
@@ -1105,9 +1205,33 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
(*__i).second = std::forward<_Obj>(__obj);
return __i;
}
+
+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
+ template <__heterogeneous_tree_key<map> _Kt, typename _Obj>
+ iterator
+ insert_or_assign(const_iterator __hint, _Kt&& __k, _Obj&& __obj)
+ {
+ iterator __i;
+ auto __true_hint =
+ _M_t._M_get_insert_hint_unique_pos_tr(__hint, __k);
+ if (__true_hint.second)
+ {
+ return _M_t._M_emplace_hint_unique(
+ iterator(__true_hint.second),
+ std::piecewise_construct,
+ std::forward_as_tuple(std::forward<_Kt>(__k)),
+ std::forward_as_tuple(std::forward<_Obj>(__obj)));
+ }
+ __i = iterator(__true_hint.first);
+ (*__i).second = std::forward<_Obj>(__obj);
+ return __i;
+ }
+#endif
+ ///@}
#endif
#if __cplusplus >= 201103L
+ ///@{
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// DR 130. Associative erase should return an iterator.
/**
diff --git a/libstdc++-v3/include/bits/stl_set.h
b/libstdc++-v3/include/bits/stl_set.h
index d3a4c089110..d3e876039d8 100644
--- a/libstdc++-v3/include/bits/stl_set.h
+++ b/libstdc++-v3/include/bits/stl_set.h
@@ -517,6 +517,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
}
#endif
+ ///@{
/**
* @brief Attempts to insert an element into the %set.
* @param __x Element to be inserted.
@@ -548,6 +549,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
}
#endif
+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
+ template <__heterogeneous_tree_key<set> _Kt>
+ pair<iterator, bool>
+ insert(_Kt&& __x)
+ {
+ auto __p = _M_t._M_insert_unique(std::forward<_Kt>(__x));
+ return {__p.first, __p.second};
+ }
+#endif
+ ///@}
+
+ ///@{
/**
* @brief Attempts to insert an element into the %set.
* @param __position An iterator that serves as a hint as to where the
@@ -577,6 +590,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
{ return _M_t._M_insert_unique_(__position, std::move(__x)); }
#endif
+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
+ template <__heterogeneous_tree_key<set> _Kt>
+ iterator
+ insert(const_iterator __position, _Kt&& __x)
+ { return _M_t._M_insert_unique_(__position, std::forward<_Kt>(__x)); }
+#endif
+ ///@}
+
/**
* @brief A template function that attempts to insert a range
* of elements.
diff --git a/libstdc++-v3/include/bits/stl_tree.h
b/libstdc++-v3/include/bits/stl_tree.h
index 5d361b55028..ebe4810bcbc 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -1459,6 +1459,10 @@ namespace __rb_tree
pair<_Base_ptr, _Base_ptr>
_M_get_insert_unique_pos(const key_type& __k);
+ template <typename _Kt>
+ pair<_Base_ptr, _Base_ptr>
+ _M_get_insert_unique_pos_tr(const _Kt& __k);
+
pair<_Base_ptr, _Base_ptr>
_M_get_insert_equal_pos(const key_type& __k);
@@ -1466,6 +1470,11 @@ namespace __rb_tree
_M_get_insert_hint_unique_pos(const_iterator __pos,
const key_type& __k);
+ template <typename _Kt>
+ pair<_Base_ptr, _Base_ptr>
+ _M_get_insert_hint_unique_pos_tr(
+ const_iterator __pos, const _Kt& __k);
+
pair<_Base_ptr, _Base_ptr>
_M_get_insert_hint_equal_pos(const_iterator __pos,
const key_type& __k);
@@ -2060,7 +2069,7 @@ namespace __rb_tree
_M_move_assign(_Rb_tree&, false_type);
#endif
-#if __glibcxx_node_extract // >= C++17
+#ifdef __glibcxx_node_extract // >= C++17
static _Node_ptr
_S_adapt(typename _Node_alloc_traits::pointer __ptr)
{
@@ -2810,6 +2819,40 @@ namespace __rb_tree
return _Res(__j._M_node, _Base_ptr());
}
+ template<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ template <typename _Kt>
+ pair<
+ typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _Base_ptr,
+ typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _Base_ptr>
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _M_get_insert_unique_pos_tr(const _Kt& __k)
+ {
+ typedef pair<_Base_ptr, _Base_ptr> _Res;
+ _Base_ptr __x = _M_begin();
+ _Base_ptr __y = _M_end();
+ bool __comp = true;
+ while (__x)
+ {
+ __y = __x;
+ __comp = _M_key_compare(__k, _S_key(__x));
+ __x = __comp ? _S_left(__x) : _S_right(__x);
+ }
+ iterator __j = iterator(__y);
+ if (__comp)
+ {
+ if (__j == begin())
+ return _Res(__x, __y);
+ else
+ --__j;
+ }
+ if (_M_key_compare(_S_key(__j._M_node), __k))
+ return _Res(__x, __y);
+ return _Res(__j._M_node, _Base_ptr());
+ }
+
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
@@ -2936,6 +2979,65 @@ namespace __rb_tree
return _Res(__position._M_node, _Base_ptr());
}
+ template<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ template <typename _Kt>
+ pair<
+ typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _Base_ptr,
+ typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _Base_ptr>
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _M_get_insert_hint_unique_pos_tr(
+ const_iterator __position, const _Kt& __k)
+ {
+ typedef pair<_Base_ptr, _Base_ptr> _Res;
+
+ // end()
+ if (__position._M_node == _M_end())
+ {
+ if (size() > 0 && _M_key_compare(_S_key(_M_rightmost()), __k))
+ return _Res(_Base_ptr(), _M_rightmost());
+ else
+ return _M_get_insert_unique_pos_tr(__k);
+ }
+ else if (_M_key_compare(__k, _S_key(__position._M_node)))
+ {
+ // First, try before...
+ iterator __before(__position._M_node);
+ if (__position._M_node == _M_leftmost()) // begin()
+ return _Res(_M_leftmost(), _M_leftmost());
+ else if (_M_key_compare(_S_key((--__before)._M_node), __k))
+ {
+ if (!_S_right(__before._M_node))
+ return _Res(_Base_ptr(), __before._M_node);
+ else
+ return _Res(__position._M_node, __position._M_node);
+ }
+ else
+ return _M_get_insert_unique_pos_tr(__k);
+ }
+ else if (_M_key_compare(_S_key(__position._M_node), __k))
+ {
+ // ... then try after.
+ iterator __after(__position._M_node);
+ if (__position._M_node == _M_rightmost())
+ return _Res(_Base_ptr(), _M_rightmost());
+ else if (_M_key_compare(__k, _S_key((++__after)._M_node)))
+ {
+ if (!_S_right(__position._M_node))
+ return _Res(_Base_ptr(), __position._M_node);
+ else
+ return _Res(__after._M_node, __after._M_node);
+ }
+ else
+ return _M_get_insert_unique_pos_tr(__k);
+ }
+ else
+ // Equivalent keys.
+ return _Res(__position._M_node, _Base_ptr());
+ }
+
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
#if __cplusplus >= 201103L
@@ -3155,7 +3257,7 @@ namespace __rb_tree
return __z._M_insert(__res);
return __z._M_insert_equal_lower();
}
-#endif
+#endif // >= C++11
template<typename _Key, typename _Val, typename _KeyOfValue,
diff --git a/libstdc++-v3/include/bits/unordered_map.h
b/libstdc++-v3/include/bits/unordered_map.h
index 9b74cba8675..1bd2906ace4 100644
--- a/libstdc++-v3/include/bits/unordered_map.h
+++ b/libstdc++-v3/include/bits/unordered_map.h
@@ -456,6 +456,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
emplace(_Args&&... __args)
{ return _M_h.emplace(std::forward<_Args>(__args)...); }
+ ///@{
/**
* @brief Attempts to build and insert a std::pair into the
* %unordered_map.
@@ -520,6 +521,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
#endif // node_extract
#ifdef __glibcxx_unordered_map_try_emplace // C++ >= 17 && HOSTED
+ ///@{
/**
* @brief Attempts to build and insert a std::pair into the
* %unordered_map.
@@ -558,6 +560,18 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
std::forward<_Args>(__args)...);
}
+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
+ template <__heterogeneous_hash_key<unordered_map> _Kt, typename ..._Args>
+ pair<iterator, bool>
+ try_emplace(_Kt&& __k, _Args&&... __args)
+ {
+ return _M_h.try_emplace(cend(),
+ std::forward<_Kt>(__k), std::forward<_Args>(__args)...);
+ }
+#endif
+ ///@}
+
+ ///@{
/**
* @brief Attempts to build and insert a std::pair into the
* %unordered_map.
@@ -605,6 +619,17 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
}
#endif // __glibcxx_unordered_map_try_emplace
+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
+ template <__heterogeneous_hash_key<unordered_map> _Kt, typename ..._Args>
+ iterator
+ try_emplace(const_iterator __hint, _Kt&& __k, _Args&&... __args)
+ {
+ return _M_h.try_emplace(__hint,
+ std::forward<_Kt>(__k), std::forward<_Args>(__args)...).first;
+ }
+#endif
+ ///@}
+
///@{
/**
* @brief Attempts to insert a std::pair into the %unordered_map.
@@ -722,6 +747,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
#endif
#ifdef __glibcxx_unordered_map_try_emplace // >= C++17 && HOSTED
+ ///@{
/**
* @brief Attempts to insert a std::pair into the %unordered_map.
* @param __k Key to use for finding a possibly existing pair in
@@ -765,6 +791,21 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
return __ret;
}
+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
+ template <__heterogeneous_hash_key<unordered_map> _Kt, typename _Obj>
+ pair<iterator, bool>
+ insert_or_assign(_Kt&& __k, _Obj&& __obj)
+ {
+ auto __ret = _M_h.try_emplace(
+ cend(), std::forward<_Kt>(__k), std::forward<_Obj>(__obj));
+ if (!__ret.second)
+ __ret.first->second = std::forward<_Obj>(__obj);
+ return __ret;
+ }
+#endif
+ ///@}
+
+ ///@{
/**
* @brief Attempts to insert a std::pair into the %unordered_map.
* @param __hint An iterator that serves as a hint as to where the
@@ -813,6 +854,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
__ret.first->second = std::forward<_Obj>(__obj);
return __ret.first;
}
+
+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
+ template <__heterogeneous_hash_key<unordered_map> _Kt, typename _Obj>
+ iterator
+ insert_or_assign(const_iterator __hint, _Kt&& __k, _Obj&& __obj)
+ {
+ auto __ret = _M_h.try_emplace(__hint,
+ std::forward<_Kt>(__k), std::forward<_Obj>(__obj));
+ if (!__ret.second)
+ __ret.first->second = std::forward<_Obj>(__obj);
+ return __ret.first;
+ }
+#endif
+ ///@}
#endif // unordered_map_try_emplace
///@{
@@ -1089,6 +1144,15 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
mapped_type&
operator[](key_type&& __k)
{ return _M_h[std::move(__k)]; }
+
+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
+ template <__heterogeneous_hash_key<unordered_map> _Kt>
+ mapped_type&
+ operator[](_Kt&& __k)
+ {
+ return try_emplace(std::forward<_Kt>(__k)).first->second;
+ }
+#endif
///@}
///@{
@@ -1103,9 +1167,23 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
at(const key_type& __k)
{ return _M_h.at(__k); }
+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
+ template <__heterogeneous_hash_key<unordered_map> _Kt>
+ mapped_type&
+ at(const _Kt& __k)
+ { return _M_h._M_at_tr(__k); }
+#endif
+
const mapped_type&
at(const key_type& __k) const
{ return _M_h.at(__k); }
+
+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
+ template <__heterogeneous_hash_key<unordered_map> _Kt>
+ const mapped_type&
+ at(const _Kt& __k) const
+ { return _M_h._M_at_tr(__k); }
+#endif
///@}
// bucket interface.
@@ -1129,6 +1207,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
bucket_size(size_type __n) const
{ return _M_h.bucket_size(__n); }
+ ///@{
/*
* @brief Returns the bucket index of a given element.
* @param __key A key instance.
@@ -1138,6 +1217,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
bucket(const key_type& __key) const
{ return _M_h.bucket(__key); }
+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
+ template <__heterogeneous_hash_key<unordered_map> _Kt>
+ size_type
+ bucket(const _Kt& __key) const
+ { return _M_h._M_bucket_tr(__key); }
+#endif
+ ///@}
+
/**
* @brief Returns a read/write iterator pointing to the first bucket
* element.
@@ -2176,6 +2263,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
bucket_size(size_type __n) const
{ return _M_h.bucket_size(__n); }
+ ///@{
/*
* @brief Returns the bucket index of a given element.
* @param __key A key instance.
@@ -2185,6 +2273,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
bucket(const key_type& __key) const
{ return _M_h.bucket(__key); }
+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
+ template <__heterogeneous_hash_key<unordered_multimap> _Kt>
+ size_type
+ bucket(const _Kt& __key) const
+ { return _M_h._M_bucket_tr(__key); }
+#endif
+ ///@}
+
/**
* @brief Returns a read/write iterator pointing to the first bucket
* element.
diff --git a/libstdc++-v3/include/bits/unordered_set.h
b/libstdc++-v3/include/bits/unordered_set.h
index 22b2ad9caf4..044b49e6cd4 100644
--- a/libstdc++-v3/include/bits/unordered_set.h
+++ b/libstdc++-v3/include/bits/unordered_set.h
@@ -493,6 +493,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
std::pair<iterator, bool>
insert(value_type&& __x)
{ return _M_h.insert(std::move(__x)); }
+
+#if __glibcxx_associative_heterogeneous_insertion // P2363R5
+ template <__heterogeneous_hash_key<unordered_set> _Kt>
+ std::pair<iterator, bool>
+ insert(_Kt&& __x)
+ { return _M_h._M_insert_tr(std::forward<_Kt>(__x)); }
+#endif
///@}
///@{
@@ -522,6 +529,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
iterator
insert(const_iterator __hint, value_type&& __x)
{ return _M_h.insert(__hint, std::move(__x)); }
+
+#if __glibcxx_associative_heterogeneous_insertion // P2363R5
+ template <__heterogeneous_hash_key<unordered_set> _Kt>
+ iterator
+ insert(const_iterator, _Kt&& __x)
+ { return _M_h._M_insert_tr(std::forward<_Kt>(__x)).first; }
+#endif
///@}
/**
@@ -876,6 +890,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
bucket_size(size_type __n) const
{ return _M_h.bucket_size(__n); }
+ ///@{
/*
* @brief Returns the bucket index of a given element.
* @param __key A key instance.
@@ -885,6 +900,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
bucket(const key_type& __key) const
{ return _M_h.bucket(__key); }
+#if __glibcxx_associative_heterogeneous_insertion // P2363R5
+ template <__heterogeneous_hash_key<unordered_set> _Kt>
+ size_type
+ bucket(const _Kt& __key) const
+ { return _M_h._M_bucket_tr(__key); }
+#endif
+ ///@}
+
///@{
/**
* @brief Returns a read-only (constant) iterator pointing to the first
@@ -1884,6 +1907,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
bucket_size(size_type __n) const
{ return _M_h.bucket_size(__n); }
+ ///@{
/*
* @brief Returns the bucket index of a given element.
* @param __key A key instance.
@@ -1893,6 +1917,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
bucket(const key_type& __key) const
{ return _M_h.bucket(__key); }
+#if __glibcxx_associative_heterogeneous_insertion // P2363R5
+ template <__heterogeneous_hash_key<unordered_multiset> _Kt>
+ size_type
+ bucket(const _Kt& __key) const
+ { return _M_h._M_bucket_tr(__key); }
+#endif
+ ///@}
+
///@{
/**
* @brief Returns a read-only (constant) iterator pointing to the first
diff --git a/libstdc++-v3/include/bits/version.def
b/libstdc++-v3/include/bits/version.def
index 4b8e9d43ec2..01725999c52 100644
--- a/libstdc++-v3/include/bits/version.def
+++ b/libstdc++-v3/include/bits/version.def
@@ -1641,6 +1641,14 @@ ftms = {
};
};
+ftms = {
+ name = associative_heterogeneous_insertion;
+ values = {
+ v = 202306;
+ cxxmin = 26;
+ };
+};
+
ftms = {
name = is_scoped_enum;
values = {
diff --git a/libstdc++-v3/include/bits/version.h
b/libstdc++-v3/include/bits/version.h
index 7602225cb6d..b376c428ced 100644
--- a/libstdc++-v3/include/bits/version.h
+++ b/libstdc++-v3/include/bits/version.h
@@ -1811,6 +1811,16 @@
#endif /* !defined(__cpp_lib_associative_heterogeneous_erasure) */
#undef __glibcxx_want_associative_heterogeneous_erasure
+#if !defined(__cpp_lib_associative_heterogeneous_insertion)
+# if (__cplusplus > 202302L)
+# define __glibcxx_associative_heterogeneous_insertion 202306L
+# if defined(__glibcxx_want_all) ||
defined(__glibcxx_want_associative_heterogeneous_insertion)
+# define __cpp_lib_associative_heterogeneous_insertion 202306L
+# endif
+# endif
+#endif /* !defined(__cpp_lib_associative_heterogeneous_insertion) */
+#undef __glibcxx_want_associative_heterogeneous_insertion
+
#if !defined(__cpp_lib_is_scoped_enum)
# if (__cplusplus >= 202100L)
# define __glibcxx_is_scoped_enum 202011L
diff --git a/libstdc++-v3/include/std/map b/libstdc++-v3/include/std/map
index 91612cf42c4..66edadbc6dc 100644
--- a/libstdc++-v3/include/std/map
+++ b/libstdc++-v3/include/std/map
@@ -80,6 +80,7 @@
#define __glibcxx_want_nonmember_container_access
#define __glibcxx_want_tuple_like
#define __glibcxx_want_associative_heterogeneous_erasure
+#define __glibcxx_want_associative_heterogeneous_insertion
#include <bits/version.h>
#if __cplusplus >= 201703L
diff --git a/libstdc++-v3/include/std/set b/libstdc++-v3/include/std/set
index 28eef1fc490..dc550f1d0b6 100644
--- a/libstdc++-v3/include/std/set
+++ b/libstdc++-v3/include/std/set
@@ -78,6 +78,7 @@
#define __glibcxx_want_node_extract
#define __glibcxx_want_nonmember_container_access
#define __glibcxx_want_associative_heterogeneous_erasure
+#define __glibcxx_want_associative_heterogeneous_insertion
#include <bits/version.h>
#if __cplusplus >= 201703L
diff --git a/libstdc++-v3/include/std/unordered_map
b/libstdc++-v3/include/std/unordered_map
index f63be4104c5..e9cf191e749 100644
--- a/libstdc++-v3/include/std/unordered_map
+++ b/libstdc++-v3/include/std/unordered_map
@@ -57,6 +57,7 @@
#define __glibcxx_want_unordered_map_try_emplace
#define __glibcxx_want_tuple_like
#define __glibcxx_want_associative_heterogeneous_erasure
+#define __glibcxx_want_associative_heterogeneous_insertion
#include <bits/version.h>
#if __cplusplus >= 201703L
diff --git a/libstdc++-v3/include/std/unordered_set
b/libstdc++-v3/include/std/unordered_set
index 45e6a915eb9..ee16489290e 100644
--- a/libstdc++-v3/include/std/unordered_set
+++ b/libstdc++-v3/include/std/unordered_set
@@ -55,6 +55,7 @@
#define __glibcxx_want_node_extract
#define __glibcxx_want_nonmember_container_access
#define __glibcxx_want_associative_heterogeneous_erasure
+#define __glibcxx_want_associative_heterogeneous_insertion
#include <bits/version.h>
#if __cplusplus >= 201703L
diff --git
a/libstdc++-v3/testsuite/23_containers/map/modifiers/hetero/insert.cc
b/libstdc++-v3/testsuite/23_containers/map/modifiers/hetero/insert.cc
new file mode 100644
index 00000000000..73db5d28b26
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/map/modifiers/hetero/insert.cc
@@ -0,0 +1,341 @@
+// { dg-do run { target c++26 } }
+
+#include <map>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <compare>
+#include <cstring>
+#include <testsuite_hooks.h>
+
+struct Y;
+
+struct X {
+ std::string s;
+ X(std::string_view str) : s(str) {}
+ X(Y&& y);
+ X(const Y& y);
+ friend auto operator<=>(X const& a, X const& b) = default;
+};
+
+struct Y {
+ std::string s;
+ Y() = default;
+ Y(Y&& y) : s(std::move(y.s)) { y.s.clear(); }
+ Y(const Y& y) = default;
+ Y& operator=(Y&& y) { s = std::move(y.s); y.s.clear(); return *this; }
+ Y& operator=(const Y& y) = default;
+ Y(std::string_view sv) : s(sv) {}
+ Y(int n) : s(std::string('a', n)) {}
+ Y(const Y& a, const Y& b) : s(a.s + "1" + b.s) { }
+ Y(const Y& a, Y&& b) : s(a.s + "2" + b.s) { b.s.clear(); }
+ Y(Y&& a, const Y& b) : s(a.s + "3" + b.s) { a.s.clear(); }
+ Y(Y&& a, Y&& b) : s(a.s + "4" + b.s) { a.s.clear(), b.s.clear(); }
+ friend auto operator<=>(Y const& a, Y const& b) = default;
+ friend auto operator<=>(X const& a, Y const& b) { return a.s <=> b.s; }
+};
+
+X::X(Y&& y) : s(std::move(y.s)) { y.s.clear(); }
+X::X(const Y& y) : s(y.s) {}
+
+using cmp = std::less<void>;
+
+void test1() // op[]
+{
+ std::map<X, Y, cmp> amap{cmp{}};
+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
+ Y x{"dei"}, y{"deh"}, z{"deg"};
+ amap[z] = 4;
+ VERIFY(amap.size() == 4);
+ VERIFY(z.s.size() == 3); // not moved from.
+
+ amap[std::move(z)] = 5;
+ VERIFY(amap.size() == 4);
+ VERIFY(z.s.size() == 3); // not moved from.
+
+ VERIFY(amap[std::move(y)] == Y{});
+ VERIFY(amap.size() == 5);
+ VERIFY(y.s.empty()); // moved from.
+
+ amap[std::move(x)] = 7;
+ VERIFY(amap.size() == 6);
+ VERIFY(x.s.empty()); // moved from
+}
+
+void test2() // at()
+{
+ std::map<X, Y, cmp> amap{cmp{}};
+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
+
+ Y y{"def"};
+ try
+ {
+ VERIFY(2 == amap.at(y));
+ VERIFY(amap.size() == 3);
+ VERIFY(4 == (amap.at(std::move(y)) = 4));
+ VERIFY(amap.size() == 3);
+ VERIFY(y.s.size() == 3); // not moved from
+ }
+ catch(...) { VERIFY(false); }
+ try
+ {
+ amap.at(Y{"deg"}) = 4;
+ VERIFY(false); // Should have thrown.
+ }
+ catch (std::out_of_range&) { VERIFY(amap.size() == 3); }
+ catch (...) { VERIFY(false); } // Wrong exception.
+
+ auto const& amapr{amap};
+ Y z{"deh"};
+ try
+ {
+ amapr.at(std::move(z));
+ VERIFY(false); // Should have thrown.
+ }
+ catch (std::out_of_range&) { }
+ catch (...) { VERIFY(false); } // Wrong exception.
+ VERIFY(amapr.size() == 3);
+ VERIFY(z.s.size() == 3); // not moved from
+}
+
+void test3() // try_emplace
+{
+ std::map<X, Y, cmp> amap{cmp{}};
+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
+
+ { // Fail, already there
+ auto a = amap;
+ auto [it, res] = a.try_emplace(Y{"def"}, Y{"xyz"});
+ VERIFY(!res);
+ VERIFY(a.size() == 3);
+ VERIFY(a.at(Y{"def"}) == Y{2});
+ }
+ { // Fail, already there, move
+ auto a = amap;
+ Y y{"def"}, z{"xyz"};
+ auto [it, res] = a.try_emplace(std::move(y), std::move(z));
+ VERIFY(!res);
+ VERIFY(a.size() == 3);
+ VERIFY(a.at(Y{"def"}) == Y{2});
+ VERIFY(y.s.size() == 3); // not moved from
+ VERIFY(z.s.size() == 3); // not moved from
+ }
+ { // Succeed, construct
+ auto a = amap;
+ Y m("m"), n("n"), o("o"), p("p"), dek("dek");
+ {
+ auto [it, res] = a.try_emplace(Y{"deg"}, m, n);
+ VERIFY(res);
+ VERIFY(a.size() == 4);
+ VERIFY(it->first == X{"deg"});
+ VERIFY(it->second == Y{"m1n"});
+ VERIFY(m.s.size() == 1);
+ VERIFY(n.s.size() == 1);
+ }
+ {
+ auto [it, res] = a.try_emplace(Y{"deh"}, m, std::move(n));
+ VERIFY(res);
+ VERIFY(a.size() == 5);
+ VERIFY(it->first == X{"deh"});
+ VERIFY(it->second == Y{"m2n"});
+ VERIFY(m.s.size() == 1);
+ VERIFY(n.s.empty());
+ }
+ {
+ auto [it, res] = a.try_emplace(Y{"dei"}, std::move(m), o);
+ VERIFY(res);
+ VERIFY(a.size() == 6);
+ VERIFY(it->first == X{"dei"});
+ VERIFY(it->second == Y{"m3o"});
+ VERIFY(m.s.empty());
+ VERIFY(o.s.size() == 1);
+ }
+ {
+ auto [it, res] = a.try_emplace(Y{"dej"}, std::move(o), std::move(p));
+ VERIFY(res);
+ VERIFY(a.size() == 7);
+ VERIFY(it->first == X{"dej"});
+ VERIFY(it->second == Y{"o4p"});
+ VERIFY(o.s.empty());
+ VERIFY(p.s.empty());
+ }
+ {
+ auto [it, res] = a.try_emplace(std::move(dek), Y("q"), Y("r"));
+ VERIFY(res);
+ VERIFY(a.size() == 8);
+ VERIFY(dek.s.empty());
+ VERIFY(it->first == X{"dek"});
+ VERIFY(it->second == Y{"q4r"});
+ }
+ }
+ { // Succeed, move
+ auto a = amap;
+ Y y{"tuv"}, z{"xyz"};
+ auto [it, res] = a.try_emplace(std::move(y), std::move(z));
+ VERIFY(res);
+ VERIFY(it->first == X{"tuv"});
+ VERIFY(it->second == Y{"xyz"});
+ VERIFY(a.size() == 4);
+ VERIFY(y.s.empty()); // moved from
+ VERIFY(z.s.empty()); // moved from
+ }
+ { // Hinted, fail
+ auto a = amap;
+ Y y{"def"}, z{"xyz"};
+ auto it = a.try_emplace(a.begin(), std::move(y), std::move(z));
+ VERIFY(a.size() == 3);
+ VERIFY(it->first == X{"def"});
+ VERIFY(it->second == Y{2});
+ VERIFY(y.s.size() == 3); // not moved from
+ VERIFY(z.s.size() == 3); // not moved from
+ }
+ { // Hinted, fail, move
+ auto a = amap;
+ Y y{"def"}, z{"xyz"};
+ auto it = a.try_emplace(a.begin(), std::move(y), std::move(z));
+ VERIFY(a.size() == 3);
+ VERIFY(it->first == X{"def"});
+ VERIFY(it->second == Y{2});
+ VERIFY(y.s.size() == 3); // not moved from
+ VERIFY(z.s.size() == 3); // not moved from
+ }
+ { // Hinted, succeed, construct
+ auto a = amap;
+ Y m("m"), n("n"), o("o"), p("p"), dek("dek");
+ {
+ auto it = a.try_emplace(a.begin(), Y{"deg"}, m, n);
+ VERIFY(a.size() == 4);
+ VERIFY(it->first == X{"deg"});
+ VERIFY(it->second == Y{"m1n"});
+ VERIFY(m.s.size() == 1);
+ VERIFY(n.s.size() == 1);
+ }
+ {
+ auto it = a.try_emplace(a.begin(), Y{"deh"}, m, std::move(n));
+ VERIFY(a.size() == 5);
+ VERIFY(it->first == X{"deh"});
+ VERIFY(it->second == Y{"m2n"});
+ VERIFY(m.s.size() == 1);
+ VERIFY(n.s.empty());
+ }
+ {
+ auto it = a.try_emplace(a.begin(), Y{"dei"}, std::move(m), o);
+ VERIFY(a.size() == 6);
+ VERIFY(it->first == X{"dei"});
+ VERIFY(it->second == Y{"m3o"});
+ VERIFY(m.s.empty());
+ VERIFY(o.s.size() == 1);
+ }
+ {
+ auto it = a.try_emplace(a.begin(), Y{"dej"}, std::move(o), std::move(p));
+ VERIFY(a.size() == 7);
+ VERIFY(it->first == X{"dej"});
+ VERIFY(it->second == Y{"o4p"});
+ VERIFY(o.s.empty());
+ VERIFY(p.s.empty());
+ }
+ {
+ auto it = a.try_emplace(a.begin(), std::move(dek), Y("q"), Y("r"));
+ VERIFY(a.size() == 8);
+ VERIFY(dek.s.empty());
+ VERIFY(it->first == X{"dek"});
+ VERIFY(it->second == Y{"q4r"});
+ }
+ }
+ { // Hinted, succeed, move
+ auto a = amap;
+ Y y{"tuv"}, z{"xyz"};
+ auto it = a.try_emplace(a.begin(), std::move(y), std::move(z));
+ VERIFY(it->first == X{"tuv"});
+ VERIFY(it->second == Y{"xyz"});
+ VERIFY(a.size() == 4);
+ VERIFY(y.s.empty()); // moved from
+ VERIFY(z.s.empty()); // moved from
+ }
+}
+
+void test4() // insert_or_assign
+{
+ std::map<X, Y, cmp> amap{cmp{}};
+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
+
+ { // Already there, replace
+ auto a = amap;
+ Y y{"def"}, z{"xyz"};
+ auto [it, res] = a.insert_or_assign(y, z);
+ VERIFY(!res);
+ VERIFY(a.size() == 3);
+ VERIFY(a.at(Y{"def"}) == Y{"xyz"});
+ VERIFY(y.s.size() == 3); // not moved from
+ VERIFY(z.s.size() == 3); // not moved from
+ }
+ { // Already there, move
+ auto a = amap;
+ Y y{"def"}, z{"xyz"};
+ auto [it, res] = a.insert_or_assign(std::move(y), std::move(z));
+ VERIFY(!res);
+ VERIFY(a.size() == 3);
+ VERIFY(a.at(Y{"def"}) == Y{"xyz"});
+ VERIFY(y.s.size() == 3); // not moved from
+ VERIFY(z.s.empty()); // moved from
+ }
+ { // Succeed, move
+ auto a = amap;
+ Y y{"tuv"}, z{"xyz"};
+ auto [it, res] = a.insert_or_assign(std::move(y), std::move(z));
+ VERIFY(res);
+ VERIFY(it->first == X{"tuv"});
+ VERIFY(it->second == Y{"xyz"});
+ VERIFY(a.size() == 4);
+ VERIFY(y.s.empty()); // moved from
+ VERIFY(z.s.empty()); // moved from
+ }
+ { // Hinted, already there, replace
+ auto a = amap;
+ Y y{"def"}, z{"xyz"};
+ auto it = a.insert_or_assign(a.begin(), y, z);
+ VERIFY(a.size() == 3);
+ VERIFY(it->first == X{"def"});
+ VERIFY(it->second == Y{"xyz"});
+ VERIFY(y.s.size() == 3); // not moved from
+ VERIFY(z.s.size() == 3); // not moved from
+ }
+ { // Hinted, already there, move
+ auto a = amap;
+ Y y{"def"}, z{"xyz"};
+ auto it = a.insert_or_assign(a.begin(), std::move(y), std::move(z));
+ VERIFY(a.size() == 3);
+ VERIFY(it->first == X{"def"});
+ VERIFY(it->second == Y{"xyz"});
+ VERIFY(y.s.size() == 3); // not moved from
+ VERIFY(z.s.empty()); // moved from
+ }
+ { // Hinted, succeed
+ auto a = amap;
+ Y y{"tuv"}, z{"xyz"};
+ auto it = a.insert_or_assign(a.begin(), y, z);
+ VERIFY(it->first == X{"tuv"});
+ VERIFY(it->second == Y{"xyz"});
+ VERIFY(a.size() == 4);
+ VERIFY(y.s.size() == 3); // not moved from
+ VERIFY(z.s.size() == 3); // not moved from
+ }
+ { // Hinted, succeed, move
+ auto a = amap;
+ Y y{"tuv"}, z{"xyz"};
+ auto it = a.insert_or_assign(a.begin(), std::move(y), std::move(z));
+ VERIFY(it->first == X{"tuv"});
+ VERIFY(it->second == Y{"xyz"});
+ VERIFY(a.size() == 4);
+ VERIFY(y.s.empty()); // moved from
+ VERIFY(z.s.empty()); // moved from
+ }
+}
+
+int main()
+{
+ test1();
+ test2();
+ test3();
+ test4();
+}
diff --git
a/libstdc++-v3/testsuite/23_containers/set/modifiers/hetero/insert.cc
b/libstdc++-v3/testsuite/23_containers/set/modifiers/hetero/insert.cc
new file mode 100644
index 00000000000..ac13b514778
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/set/modifiers/hetero/insert.cc
@@ -0,0 +1,120 @@
+// { dg-do run { target c++26 } }
+
+#include <set>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <compare>
+#include <cstring>
+#include <testsuite_hooks.h>
+
+struct Y;
+
+struct X {
+ std::string s;
+ X(std::string_view str) : s(str) {}
+ X(Y&& y);
+ X(const Y& y);
+
+ friend auto operator<=>(X const& a, X const& b) = default;
+};
+
+struct Y {
+ std::string s;
+ Y() = default;
+ Y(std::string_view sv) : s(sv) {}
+ Y(int a, int b = 0) : s(std::string('a', a + b)) {}
+ Y(Y&& y) : s(std::move(y.s)) { y.s.clear(); }
+ Y(const Y& y) = default;
+ Y& operator=(Y&& y) { s = std::move(y.s); y.s.clear(); return *this; }
+ Y& operator=(const Y& y) = default;
+ friend auto operator<=>(Y const& a, Y const& b) = default;
+ friend auto operator<=>(X const& a, Y const& b) { return a.s <=> b.s; }
+};
+
+X::X(Y&& y) : s(std::move(y.s)) { y.s.clear(); }
+X::X(const Y& y) : s(y.s) {}
+
+using cmp = std::less<void>;
+
+void test1() // insert
+{
+ std::set<X, cmp> aset{cmp{}};
+ aset.insert({X{"abc"}, X{"def"}, X{"ghi"}});
+
+ { // Fail
+ auto a = aset;
+ Y y{"def"};
+ auto [it, res] = a.insert(y);
+ VERIFY(!res);
+ VERIFY(a.size() == 3);
+ VERIFY(it->s == "def");
+ VERIFY(y.s.size() == 3); // not moved
+ }
+ { // Fail, move
+ auto a = aset;
+ Y y{"def"};
+ auto [it, res] = a.insert(std::move(y));
+ VERIFY(!res);
+ VERIFY(a.size() == 3);
+ VERIFY(it->s == "def");
+ VERIFY(y.s.size() == 3); // not moved
+ }
+ { // Succeed
+ auto a = aset;
+ Y y{"deg"};
+ auto [it, res] = a.insert(y);
+ VERIFY(res);
+ VERIFY(a.size() == 4);
+ VERIFY(it->s == "deg");
+ VERIFY(y.s.size() == 3); // not moved
+ }
+ { // Succeed, move
+ auto a = aset;
+ Y y{"deg"};
+ auto [it, res] = a.insert(std::move(y));
+ VERIFY(res);
+ VERIFY(a.size() == 4);
+ VERIFY(it->s == "deg");
+ VERIFY(y.s.empty()); // moved
+ }
+
+
+ { // Hinted, fail
+ auto a = aset;
+ Y y{"def"};
+ auto it = a.insert(a.begin(), y);
+ VERIFY(a.size() == 3);
+ VERIFY(it->s == "def");
+ VERIFY(y.s.size() == 3); // not moved
+ }
+ { // Hinted, fail, move
+ auto a = aset;
+ Y y{"def"};
+ auto it = a.insert(a.begin(), std::move(y));
+ VERIFY(a.size() == 3);
+ VERIFY(it->s == "def");
+ VERIFY(y.s.size() == 3); // not moved
+ }
+ { // Hinted, succeed
+ auto a = aset;
+ Y y{"deh"};
+ auto it = a.insert(a.begin(), y);
+ VERIFY(a.size() == 4);
+ VERIFY(it->s == "deh");
+ VERIFY(y.s.size() == 3); // not moved
+ }
+ { // Hinted, succeed, move
+ auto a = aset;
+ Y y{"deh"};
+ auto it = a.insert(a.begin(), std::move(y));
+ VERIFY(a.size() == 4);
+ VERIFY(it->s == "deh");
+ VERIFY(y.s.empty()); // moved
+ }
+}
+
+int main()
+{
+ test1();
+}
diff --git
a/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/hetero/insert.cc
b/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/hetero/insert.cc
new file mode 100644
index 00000000000..8f7f88ce9e1
--- /dev/null
+++
b/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/hetero/insert.cc
@@ -0,0 +1,353 @@
+// { dg-do run { target c++26 } }
+
+#include <unordered_map>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <functional>
+#include <compare>
+#include <testsuite_hooks.h>
+
+struct Y;
+
+struct X {
+ std::string s;
+ X(std::string_view str) : s(str) {}
+ X(Y&& y);
+ X(const Y& y);
+ friend bool operator==(X const& a, X const& b) = default;
+};
+
+struct Y {
+ std::string s;
+ Y() = default;
+ Y(Y&& y) : s(std::move(y.s)) { y.s.clear(); }
+ Y(const Y& y) = default;
+ Y& operator=(Y&& y) { s = std::move(y.s); y.s.clear(); return *this; }
+ Y& operator=(const Y& y) = default;
+ Y(std::string_view sv) : s(sv) {}
+ Y(int n) : s(std::string('a', n)) {}
+ Y(const Y& a, const Y& b) : s(a.s + "1" + b.s) { }
+ Y(const Y& a, Y&& b) : s(a.s + "2" + b.s) { b.s.clear(); }
+ Y(Y&& a, const Y& b) : s(a.s + "3" + b.s) { a.s.clear(); }
+ Y(Y&& a, Y&& b) : s(a.s + "4" + b.s) { a.s.clear(), b.s.clear(); }
+ friend bool operator==(Y const& a, Y const& b) = default;
+ friend bool operator==(X const& a, Y const& b) { return a.s == b.s; }
+};
+
+X::X(Y&& y) : s(std::move(y.s)) { y.s.clear(); }
+X::X(const Y& y) : s(y.s) {}
+
+struct Hash {
+ using is_transparent = void;
+ template <typename T>
+ auto operator()(T const& t) const
+ { return std::hash<decltype(T::s)>{}(t.s); }
+};
+
+using Equal = std::equal_to<void>;
+
+void test1() // op[]
+{
+ std::unordered_map<X, Y, Hash, Equal> amap;
+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
+
+ Y x{"dei"}, y{"deh"}, z{"deg"};
+ amap[z] = 4;
+ VERIFY(amap.size() == 4);
+ VERIFY(z.s.size() == 3); // not moved from.
+
+ amap[std::move(z)] = 5;
+ VERIFY(amap.size() == 4);
+ VERIFY(z.s.size() == 3); // not moved from.
+
+ VERIFY(amap[std::move(y)] == Y{});
+ VERIFY(amap.size() == 5);
+ VERIFY(y.s.empty()); // moved from.
+
+ amap[std::move(x)] = 7;
+ VERIFY(amap.size() == 6);
+ VERIFY(x.s.empty()); // moved from
+}
+
+void test2() // at()
+{
+ std::unordered_map<X, Y, Hash, Equal> amap;
+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
+
+ Y x{"def"};
+ try
+ {
+ VERIFY(2 == amap.at(x));
+ VERIFY(amap.size() == 3);
+ VERIFY(x.s.size() == 3); // not moved from
+ VERIFY(4 == (amap.at(x) = 4));
+ VERIFY(amap.size() == 3);
+ VERIFY(x.s.size() == 3); // not moved from
+ }
+ catch(...) { VERIFY(false); }
+
+ Y z{"deg"};
+ try
+ {
+ amap.at(z) = 4;
+ VERIFY(false); // Should have thrown.
+ }
+ catch (std::out_of_range&) { VERIFY(amap.size() == 3); }
+ catch (...) { VERIFY(false); } // Wrong exception.
+ VERIFY(z.s.size() == 3); // not moved from
+
+ Y y{"deh"};
+ auto const& amapr{amap};
+ try
+ {
+ amapr.at(y);
+ VERIFY(false); // Should have thrown.
+ }
+ catch (std::out_of_range&) { }
+ catch (...) { VERIFY(false); } // Wrong exception.
+ VERIFY(amapr.size() == 3);
+ VERIFY(y.s.size() == 3); // not moved from
+}
+
+void test3() // try_emplace
+{
+ std::unordered_map<X, Y, Hash, Equal> amap;
+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
+
+ { // Fail, already there
+ auto a = amap;
+ auto [it, res] = a.try_emplace(Y{"def"}, Y{"xyz"});
+ VERIFY(!res);
+ VERIFY(a.size() == 3);
+ VERIFY(a.at(Y{"def"}) == Y{2});
+ }
+ { // Fail, already there, move
+ auto a = amap;
+ Y y{"def"}, z{"xyz"};
+ auto [it, res] = a.try_emplace(std::move(y), std::move(z));
+ VERIFY(!res);
+ VERIFY(a.size() == 3);
+ VERIFY(a.at(Y{"def"}) == Y{2});
+ VERIFY(y.s.size() == 3); // not moved from
+ VERIFY(z.s.size() == 3); // not moved from
+ }
+ { // Succeed, construct
+ auto a = amap;
+ Y m("m"), n("n"), o("o"), p("p"), dek("dek");
+ {
+ auto [it, res] = a.try_emplace(Y{"deg"}, m, n);
+ VERIFY(res);
+ VERIFY(a.size() == 4);
+ VERIFY(it->first == X{"deg"});
+ VERIFY(it->second == Y{"m1n"});
+ VERIFY(m.s.size() == 1);
+ VERIFY(n.s.size() == 1);
+ }
+ {
+ auto [it, res] = a.try_emplace(Y{"deh"}, m, std::move(n));
+ VERIFY(res);
+ VERIFY(a.size() == 5);
+ VERIFY(it->first == X{"deh"});
+ VERIFY(it->second == Y{"m2n"});
+ VERIFY(m.s.size() == 1);
+ VERIFY(n.s.empty());
+ }
+ {
+ auto [it, res] = a.try_emplace(Y{"dei"}, std::move(m), o);
+ VERIFY(res);
+ VERIFY(a.size() == 6);
+ VERIFY(it->first == X{"dei"});
+ VERIFY(it->second == Y{"m3o"});
+ VERIFY(m.s.empty());
+ VERIFY(o.s.size() == 1);
+ }
+ {
+ auto [it, res] = a.try_emplace(Y{"dej"}, std::move(o), std::move(p));
+ VERIFY(res);
+ VERIFY(a.size() == 7);
+ VERIFY(it->first == X{"dej"});
+ VERIFY(it->second == Y{"o4p"});
+ VERIFY(o.s.empty());
+ VERIFY(p.s.empty());
+ }
+ {
+ auto [it, res] = a.try_emplace(std::move(dek), Y("q"), Y("r"));
+ VERIFY(res);
+ VERIFY(a.size() == 8);
+ VERIFY(dek.s.empty());
+ VERIFY(it->first == X{"dek"});
+ VERIFY(it->second == Y{"q4r"});
+ }
+ }
+ { // Succeed, move
+ auto a = amap;
+ Y y{"tuv"}, z{"xyz"};
+ auto [it, res] = a.try_emplace(std::move(y), std::move(z));
+ VERIFY(res);
+ VERIFY(it->first == X{"tuv"});
+ VERIFY(it->second == Y{"xyz"});
+ VERIFY(a.size() == 4);
+ VERIFY(y.s.empty()); // moved from
+ VERIFY(z.s.empty()); // moved from
+ }
+ { // Hinted, fail
+ auto a = amap;
+ Y y{"def"}, z{"xyz"};
+ auto it = a.try_emplace(a.begin(), std::move(y), std::move(z));
+ VERIFY(a.size() == 3);
+ VERIFY(it->first == X{"def"});
+ VERIFY(it->second == Y{2});
+ VERIFY(y.s.size() == 3); // not moved from
+ VERIFY(z.s.size() == 3); // not moved from
+ }
+ { // Hinted, fail, move
+ auto a = amap;
+ Y y{"def"}, z{"xyz"};
+ auto it = a.try_emplace(a.begin(), std::move(y), std::move(z));
+ VERIFY(a.size() == 3);
+ VERIFY(it->first == X{"def"});
+ VERIFY(it->second == Y{2});
+ VERIFY(y.s.size() == 3); // not moved from
+ VERIFY(z.s.size() == 3); // not moved from
+ }
+ { // Hinted, succeed, construct
+ auto a = amap;
+ Y m("m"), n("n"), o("o"), p("p"), dek("dek");
+ {
+ auto it = a.try_emplace(a.begin(), Y{"deg"}, m, n);
+ VERIFY(a.size() == 4);
+ VERIFY(it->first == X{"deg"});
+ VERIFY(it->second == Y{"m1n"});
+ VERIFY(m.s.size() == 1);
+ VERIFY(n.s.size() == 1);
+ }
+ {
+ auto it = a.try_emplace(a.begin(), Y{"deh"}, m, std::move(n));
+ VERIFY(a.size() == 5);
+ VERIFY(it->first == X{"deh"});
+ VERIFY(it->second == Y{"m2n"});
+ VERIFY(m.s.size() == 1);
+ VERIFY(n.s.empty());
+ }
+ {
+ auto it = a.try_emplace(a.begin(), Y{"dei"}, std::move(m), o);
+ VERIFY(a.size() == 6);
+ VERIFY(it->first == X{"dei"});
+ VERIFY(it->second == Y{"m3o"});
+ VERIFY(m.s.empty());
+ VERIFY(o.s.size() == 1);
+ }
+ {
+ auto it = a.try_emplace(a.begin(), Y{"dej"}, std::move(o), std::move(p));
+ VERIFY(a.size() == 7);
+ VERIFY(it->first == X{"dej"});
+ VERIFY(it->second == Y{"o4p"});
+ VERIFY(o.s.empty());
+ VERIFY(p.s.empty());
+ }
+ {
+ auto it = a.try_emplace(a.begin(), std::move(dek), Y("q"), Y("r"));
+ VERIFY(a.size() == 8);
+ VERIFY(dek.s.empty());
+ VERIFY(it->first == X{"dek"});
+ VERIFY(it->second == Y{"q4r"});
+ }
+ }
+ { // Hinted, succeed, move
+ auto a = amap;
+ Y y{"tuv"}, z{"xyz"};
+ auto it = a.try_emplace(a.begin(), std::move(y), std::move(z));
+ VERIFY(it->first == X{"tuv"});
+ VERIFY(it->second == Y{"xyz"});
+ VERIFY(a.size() == 4);
+ VERIFY(y.s.empty()); // moved from
+ VERIFY(z.s.empty()); // moved from
+ }
+}
+
+void test4() // insert_or_assign
+{
+ std::unordered_map<X, Y, Hash, Equal> amap;
+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
+
+ { // Already there, replace
+ auto a = amap;
+ Y y{"def"}, z{"xyz"};
+ auto [it, res] = a.insert_or_assign(y, z);
+ VERIFY(!res);
+ VERIFY(a.size() == 3);
+ VERIFY(a.at(Y{"def"}) == Y{"xyz"});
+ VERIFY(y.s.size() == 3); // not moved from
+ VERIFY(z.s.size() == 3); // not moved from
+ }
+ { // Already there, move
+ auto a = amap;
+ Y y{"def"}, z{"xyz"};
+ auto [it, res] = a.insert_or_assign(std::move(y), std::move(z));
+ VERIFY(!res);
+ VERIFY(a.size() == 3);
+ VERIFY(a.at(Y{"def"}) == Y{"xyz"});
+ VERIFY(y.s.size() == 3); // not moved from
+ VERIFY(z.s.empty()); // moved from
+ }
+ { // Succeed, move
+ auto a = amap;
+ Y y{"tuv"}, z{"xyz"};
+ auto [it, res] = a.insert_or_assign(std::move(y), std::move(z));
+ VERIFY(res);
+ VERIFY(it->first == X{"tuv"});
+ VERIFY(it->second == Y{"xyz"});
+ VERIFY(a.size() == 4);
+ VERIFY(y.s.empty()); // moved from
+ VERIFY(z.s.empty()); // moved from
+ }
+ { // Hinted, already there, replace
+ auto a = amap;
+ Y y{"def"}, z{"xyz"};
+ auto it = a.insert_or_assign(a.begin(), y, z);
+ VERIFY(a.size() == 3);
+ VERIFY(it->first == X{"def"});
+ VERIFY(it->second == Y{"xyz"});
+ VERIFY(y.s.size() == 3); // not moved from
+ VERIFY(z.s.size() == 3); // not moved from
+ }
+ { // Hinted, already there, move
+ auto a = amap;
+ Y y{"def"}, z{"xyz"};
+ auto it = a.insert_or_assign(a.begin(), std::move(y), std::move(z));
+ VERIFY(a.size() == 3);
+ VERIFY(it->first == X{"def"});
+ VERIFY(it->second == Y{"xyz"});
+ VERIFY(y.s.size() == 3); // not moved from
+ VERIFY(z.s.empty()); // moved from
+ }
+ { // Hinted, succeed
+ auto a = amap;
+ Y y{"tuv"}, z{"xyz"};
+ auto it = a.insert_or_assign(a.begin(), y, z);
+ VERIFY(it->first == X{"tuv"});
+ VERIFY(it->second == Y{"xyz"});
+ VERIFY(a.size() == 4);
+ VERIFY(y.s.size() == 3); // not moved from
+ VERIFY(z.s.size() == 3); // not moved from
+ }
+ { // Hinted, succeed, move
+ auto a = amap;
+ Y y{"tuv"}, z{"xyz"};
+ auto it = a.insert_or_assign(a.begin(), std::move(y), std::move(z));
+ VERIFY(it->first == X{"tuv"});
+ VERIFY(it->second == Y{"xyz"});
+ VERIFY(a.size() == 4);
+ VERIFY(y.s.empty()); // moved from
+ VERIFY(z.s.empty()); // moved from
+ }
+}
+
+int main()
+{
+ test1();
+ test2();
+ test3();
+ test4();
+}
diff --git
a/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/hetero/insert.cc
b/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/hetero/insert.cc
new file mode 100644
index 00000000000..6430201c9c6
--- /dev/null
+++
b/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/hetero/insert.cc
@@ -0,0 +1,57 @@
+// { dg-do run { target c++26 } }
+
+#include <unordered_map>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <functional>
+#include <testsuite_hooks.h>
+
+struct Y;
+
+struct X {
+ std::string s;
+ X(std::string_view str) : s(str) {}
+ X(Y&& y);
+ X(const Y& y);
+ friend bool operator==(X const& a, X const& b) = default;
+};
+
+struct Y {
+ std::string s;
+ Y() = default;
+ Y(Y&& y) : s(std::move(y.s)) { y.s.clear(); }
+ Y(const Y& y) = default;
+ Y& operator=(Y&& y) { s = std::move(y.s); y.s.clear(); return *this; }
+ Y& operator=(const Y& y) = default;
+ Y(std::string_view sv) : s(sv) {}
+ Y(int a, int b = 0) : s(std::string('a', a + b)) {}
+ friend bool operator==(Y const& a, Y const& b) = default;
+ friend bool operator==(X const& a, Y const& b) { return a.s == b.s; }
+};
+
+X::X(Y&& y) : s(std::move(y.s)) { y.s.clear(); }
+X::X(const Y& y) : s(y.s) {}
+
+struct Hash {
+ using is_transparent = void;
+ template <typename T>
+ auto operator()(T const& t) const
+ { return std::hash<decltype(T::s)>{}(t.s); }
+};
+
+using Equal = std::equal_to<void>;
+
+void test1() // bucket
+{
+ std::unordered_multimap<X, Y, Hash, Equal> amap;
+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"def"}, 3}, {X{"ghi"}, 3}});
+
+ auto const& amapr{amap};
+ VERIFY(amapr.bucket(X{"def"}) == amapr.bucket(Y{"def"}));
+}
+
+int main()
+{
+ test1();
+}
diff --git
a/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/hetero/insert.cc
b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/hetero/insert.cc
new file mode 100644
index 00000000000..59ed43c16d2
--- /dev/null
+++
b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/hetero/insert.cc
@@ -0,0 +1,56 @@
+// { dg-do run { target c++26 } }
+
+#include <unordered_set>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <functional>
+#include <testsuite_hooks.h>
+
+struct Y;
+
+struct X {
+ std::string s;
+ X(Y&& y);
+ X(const Y& y);
+ X(std::string_view str) : s(str) {}
+ friend bool operator==(X const& a, X const& b) = default;
+};
+
+struct Y {
+ std::string s;
+ Y() = default;
+ Y(Y&& y) : s(std::move(y.s)) { y.s.clear(); }
+ Y(const Y& y) = default;
+ Y& operator=(Y&& y) { s = std::move(y.s); y.s.clear(); return *this; }
+ Y& operator=(const Y& y) = default;
+ Y(std::string_view sv) : s(sv) {}
+ friend bool operator==(Y const& a, Y const& b) = default;
+ friend bool operator==(X const& a, Y const& b) { return a.s == b.s; }
+};
+
+X::X(Y&& y) : s(std::move(y.s)) { y.s.clear(); }
+X::X(const Y& y) : s(y.s) {}
+
+struct Hash {
+ using is_transparent = void;
+ template <typename T>
+ auto operator()(T const& t) const
+ { return std::hash<decltype(T::s)>{}(t.s); }
+};
+
+using Equal = std::equal_to<void>;
+
+void test1() // bucket
+{
+ std::unordered_multiset<X, Hash, Equal> aset{};
+ aset.insert({X{"abc"}, X{"def"}, X{"def"}, X{"ghi"}});
+
+ auto const& asetr{aset};
+ VERIFY(asetr.bucket(X{"def"}) == asetr.bucket(Y{"def"}));
+}
+
+int main()
+{
+ test1();
+}
diff --git
a/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/hetero/insert.cc
b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/hetero/insert.cc
new file mode 100644
index 00000000000..320143f2ea4
--- /dev/null
+++
b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/hetero/insert.cc
@@ -0,0 +1,134 @@
+// { dg-do run { target c++26 } }
+
+#include <unordered_set>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <functional>
+#include <testsuite_hooks.h>
+
+struct Y;
+
+struct X {
+ std::string s;
+ X(std::string_view str) : s(str) {}
+ X(Y&& y);
+ X(const Y& y);
+ friend bool operator==(X const& a, X const& b) = default;
+};
+
+struct Y {
+ std::string s;
+ Y() = default;
+ Y(Y&& y) : s(std::move(y.s)) { y.s.clear(); }
+ Y(const Y& y) = default;
+ Y& operator=(Y&& y) { s = std::move(y.s); y.s.clear(); return *this; }
+ Y& operator=(const Y& y) = default;
+ Y(int a, int b = 0) : s(std::string('a', a + b)) {}
+ Y(std::string_view sv) : s(sv) {}
+ friend bool operator==(Y const& a, Y const& b) = default;
+ friend bool operator==(X const& a, Y const& b) { return a.s == b.s; }
+};
+
+X::X(Y&& y) : s(std::move(y.s)) { y.s.clear(); }
+X::X(const Y& y) : s(y.s) {}
+
+struct Hash {
+ using is_transparent = void;
+ template <typename T>
+ auto operator()(T const& t) const { return
std::hash<decltype(T::s)>{}(t.s); }
+};
+
+using Equal = std::equal_to<void>;
+
+void test1() // insert
+{
+ std::unordered_set<X, Hash, Equal> aset;
+ aset.insert({X{"abc"}, X{"def"}, X{"ghi"}});
+
+ { // Fail
+ auto a = aset;
+ Y y{"def"};
+ auto [it, res] = a.insert(y);
+ VERIFY(!res);
+ VERIFY(a.size() == 3);
+ VERIFY(it->s == "def");
+ VERIFY(y.s.size() == 3); // not moved
+ }
+ { // Fail, move
+ auto a = aset;
+ Y y{"def"};
+ auto [it, res] = a.insert(std::move(y));
+ VERIFY(!res);
+ VERIFY(a.size() == 3);
+ VERIFY(it->s == "def");
+ VERIFY(y.s.size() == 3); // not moved
+ }
+ { // Succeed
+ auto a = aset;
+ Y y{"deg"};
+ auto [it, res] = a.insert(y);
+ VERIFY(res);
+ VERIFY(a.size() == 4);
+ VERIFY(it->s == "deg");
+ VERIFY(y.s.size() == 3); // not moved
+ }
+ { // Succeed, move
+ auto a = aset;
+ Y y{"deg"};
+ auto [it, res] = a.insert(std::move(y));
+ VERIFY(res);
+ VERIFY(a.size() == 4);
+ VERIFY(it->s == "deg");
+ VERIFY(y.s.empty()); // moved
+ }
+
+
+ { // Hinted, fail
+ auto a = aset;
+ Y y{"def"};
+ auto it = a.insert(a.begin(), y);
+ VERIFY(a.size() == 3);
+ VERIFY(it->s == "def");
+ VERIFY(y.s.size() == 3); // not moved
+ }
+ { // Hinted, fail, move
+ auto a = aset;
+ Y y{"def"};
+ auto it = a.insert(a.begin(), std::move(y));
+ VERIFY(a.size() == 3);
+ VERIFY(it->s == "def");
+ VERIFY(y.s.size() == 3); // not moved
+ }
+ { // Hinted, succeed
+ auto a = aset;
+ Y y{"deh"};
+ auto it = a.insert(a.begin(), y);
+ VERIFY(a.size() == 4);
+ VERIFY(it->s == "deh");
+ VERIFY(y.s.size() == 3); // not moved
+ }
+ { // Hinted, succeed, move
+ auto a = aset;
+ Y y{"deh"};
+ auto it = a.insert(a.begin(), std::move(y));
+ VERIFY(a.size() == 4);
+ VERIFY(it->s == "deh");
+ VERIFY(y.s.empty()); // moved
+ }
+}
+
+void test2() // bucket
+{
+ std::unordered_set<X, Hash, Equal> aset{};
+ aset.insert({X{"abc"}, X{"def"}, X{"ghi"}});
+
+ auto const& asetr{aset};
+ VERIFY(asetr.bucket(X{"def"}) == asetr.bucket(Y{"def"}));
+}
+
+int main()
+{
+ test1();
+ test2();
+}
--
2.52.0
