[Note: fails 23_containers/multiset/modifiers/emplace/92878_92947.cc
but with no error messages.]
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:
uno uno uno uno
set map set map mset mmap
+ + insert
+ + op[], at, try_emplace,
insert_or_assign
+ + + + bucket
The insert* and try_emplace members also get a hinted overload.
Nothing is added to the multiset or multimap tree containers.
The new overloads enforce concept __heterogeneous_tree_key or
__heterogeneous_hash_key, as in P2077, to enforce 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.
Doxygen annotations are improved.
libstdc++-v3/ChangeLog:
PR libstdc++/117402
* include/bits/stl_map.h: Add new overloads.
* include/bits/stl_set.h: Same.
* include/bits/unordered_map.h: Same.
* include/bits/unordered_set.h: Same.
* include/bits/hashtable.h: Add supporting overloads.
* include/bits/stl_tree.h: Same.
* include/bits/hashtable_policy.h: Same.
* include/bits/version.def: Add feature macro.
* include/bits/version.h: Regenerate.
* 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 | 85 +++++-----
libstdc++-v3/include/bits/hashtable_policy.h | 61 +++++++-
libstdc++-v3/include/bits/stl_map.h | 126 ++++++++++++++-
libstdc++-v3/include/bits/stl_set.h | 20 +++
libstdc++-v3/include/bits/stl_tree.h | 128 ++++++++++++++--
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 ++
.../map/modifiers/hetero/insert.cc | 141 +++++++++++++++++
.../set/modifiers/hetero/insert.cc | 60 ++++++++
.../unordered_map/modifiers/hetero/insert.cc | 145 ++++++++++++++++++
.../modifiers/hetero/insert.cc | 44 ++++++
.../modifiers/hetero/insert.cc | 44 ++++++
.../unordered_set/modifiers/hetero/insert.cc | 75 +++++++++
15 files changed, 1020 insertions(+), 55 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 113f5031eaf..e0b2ec630dd 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -607,7 +607,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if constexpr (__unique_keys::value)
{
- if (auto __loc = _M_locate(__k))
+ if (auto __loc = _M_locate_tr(__k))
continue; // Found existing element with equivalent key
else
{
@@ -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)
{
@@ -888,6 +895,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
size_type _M_bucket_index = size_type(-1);
};
+ // This is preserved just for ABI stability.
+ __location_type
+ _M_locate(const key_type& __k) const;
+
// Adaptive lookup to find key, or which bucket it would be in.
// For a container smaller than the small size threshold use a linear
// search through the whole container, just testing for equality.
@@ -902,11 +913,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// The _M_before pointer might point to _M_before_begin, so must not be
// cast to __node_ptr, and it must not be used to modify *_M_before
// except in non-const member functions, such as erase.
- __location_type
- _M_locate(const key_type& __k) const;
-
- // We would like to extend _M_locate for heterogeneous
- // keys, and use try_emplace as is, but ABI forbids it.
template <typename _HetKey>
__location_type
_M_locate_tr(const _HetKey& __k) const;
@@ -1071,7 +1077,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
else
return _M_emplace_multi(__hint, __v);
}
-
__ireturn_type
insert(value_type&& __v)
{
@@ -1095,9 +1100,10 @@ _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))
+ if (auto __loc = _M_locate_tr(__k))
return { iterator(__loc), false };
else
{
@@ -1115,6 +1121,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
@@ -1203,7 +1227,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
{
__glibcxx_assert(get_allocator() == __nh.get_allocator());
- if (auto __loc = _M_locate(__nh._M_key()))
+ if (auto __loc = _M_locate_tr(__nh._M_key()))
{
__ret.node = std::move(__nh);
__ret.position = iterator(__loc);
@@ -1331,7 +1355,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
const auto __next = __prev->_M_nxt;
const auto& __node = static_cast<__node_type&>(*__next);
const key_type& __k = _ExtractKey{}(__node._M_v());
- const auto __loc = _M_locate(__k);
+ const auto __loc = _M_locate_tr(__k);
if (__loc)
{
__prev = __next;
@@ -1365,7 +1389,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
--__n_elt;
auto __pos = __i++;
const key_type& __k = _ExtractKey{}(*__pos);
- const auto __loc = _M_locate(__k);
+ const auto __loc = _M_locate_tr(__k);
if (__loc)
continue;
@@ -1948,7 +1972,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
find(const key_type& __k)
-> iterator
- { return iterator(_M_locate(__k)); }
+ { return iterator(_M_locate_tr(__k)); }
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
@@ -1959,7 +1983,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
find(const key_type& __k) const
-> const_iterator
- { return const_iterator(_M_locate(__k)); }
+ { return const_iterator(_M_locate_tr(__k)); }
#ifdef __glibcxx_generic_unordered_lookup // C++ >= 20 && HOSTED
template<typename _Key, typename _Value, typename _Alloc,
@@ -2283,6 +2307,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return nullptr;
}
+ // This non-inline interface remains just for ABI stability.
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
typename _Hash, typename _RangeHash, typename _Unused,
@@ -2292,32 +2317,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_locate(const key_type& __k) const
-> __location_type
- {
- __location_type __loc;
- const auto __size = size();
-
- if (__size <= __small_size_threshold())
- {
- __loc._M_before = pointer_traits<__node_base_ptr>::
- pointer_to(const_cast<__node_base&>(_M_before_begin));
- while (__loc._M_before->_M_nxt)
- {
- if (this->_M_key_equals(__k, *__loc._M_node()))
- return __loc;
- __loc._M_before = __loc._M_before->_M_nxt;
- }
- __loc._M_before = nullptr; // Didn't find it.
- }
-
- __loc._M_hash_code = this->_M_hash_code(__k);
- __loc._M_bucket_index = _M_bucket_index(__loc._M_hash_code);
-
- if (__size > __small_size_threshold())
- __loc._M_before = _M_find_before_node(__loc._M_bucket_index, __k,
- __loc._M_hash_code);
-
- return __loc;
- }
+ { return _M_locate_tr(__k); }
template<typename _Key, typename _Value, typename _Alloc,
typename _ExtractKey, typename _Equal,
@@ -2328,7 +2328,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Hashtable<_Key, _Value, _Alloc, _ExtractKey, _Equal,
_Hash, _RangeHash, _Unused, _RehashPolicy, _Traits>::
_M_locate_tr(const _HetKey& __k) const
- -> __location_type
+ -> __location_type
{
__location_type __loc;
const auto __size = size();
@@ -2418,7 +2418,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__kp = std::__addressof(__key);
}
- if (auto __loc = _M_locate(*__kp))
+ if (auto __loc = _M_locate_tr(*__kp))
// There is already an equivalent node, no insertion.
return { iterator(__loc), false };
else
@@ -2436,6 +2436,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__node._M_node = nullptr;
return { __pos, true };
}
+
#pragma GCC diagnostic pop
template<typename _Key, typename _Value, typename _Alloc,
@@ -2676,7 +2677,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
erase(const key_type& __k)
-> size_type
{
- auto __loc = _M_locate(__k);
+ auto __loc = _M_locate_tr(__k);
if (!__loc)
return 0;
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h
b/libstdc++-v3/include/bits/hashtable_policy.h
index 6d7bde1e785..ec082485b18 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -872,6 +872,35 @@ namespace __detail
__throw_out_of_range(__N("unordered_map::at"));
return __ite->second;
}
+
+#if __glibcxx_associative_heterogeneous_insertion
+ // 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;
+ }
+#endif
};
template<typename _Key, typename _Val, typename _Alloc, typename _Equal,
@@ -901,6 +930,35 @@ namespace __detail
return __pos->second;
}
+#if __glibcxx_associative_heterogeneous_insertion
+ // 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;
+ }
+#endif
+
template<typename _Key, typename _Val, typename _Alloc, typename _Equal,
typename _Hash, typename _RangeHash, typename _Unused,
typename _RehashPolicy, typename _Traits>
@@ -1413,8 +1471,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&>{},
diff --git a/libstdc++-v3/include/bits/stl_map.h
b/libstdc++-v3/include/bits/stl_map.h
index 9a0f3086188..fa18ad9acee 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
+#if __glibcxx_associative_heterogeneous_insertion // P2363R5
+ 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;
}
+#if __glibcxx_associative_heterogeneous_insertion // P2363R5
+ 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;
}
+#if __glibcxx_associative_heterogeneous_insertion // P2363R5
+ 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};
}
+#if __glibcxx_associative_heterogeneous_insertion // P2363R5
+ 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 // P2363R5
+ 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 // P2363R5
+ template <__heterogeneous_tree_key<map> _Kt, typename _Mapped>
+ pair<iterator, bool>
+ insert_or_assign(_Kt&& __k, _Mapped&& __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<_Mapped>(__obj)));
+ return {__i, true};
+ }
+ (*__i).second = std::forward<_Mapped>(__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 // P2363R5
+ template <__heterogeneous_tree_key<map> _Kt, typename _Mapped>
+ iterator
+ insert_or_assign(const_iterator __hint, _Kt&& __k, _Mapped&& __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<_Mapped>(__obj)));
+ }
+ __i = iterator(__true_hint.first);
+ (*__i).second = std::forward<_Mapped>(__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 47f7b7062b8..26656d387c4 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
+#if __glibcxx_associative_heterogeneous_insertion // P2363R5
+ template <__heterogeneous_tree_key<set> _Kt>
+ pair<iterator, bool>
+ insert(_Kt&& __x)
+ {
+ auto __p = _M_t._M_insert_unique(__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
@@ -576,6 +589,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
insert(const_iterator __position, value_type&& __x)
{ return _M_t._M_insert_unique_(__position, std::move(__x)); }
#endif
+#if __glibcxx_associative_heterogeneous_insertion // P2363R5
+ template <__heterogeneous_tree_key<set> _Kt>
+ iterator
+ insert(const_iterator __position, _Kt&& __x)
+ { return _M_t._M_insert_unique_(__position, __x); }
+#endif
+ ///@}
/**
* @brief A template function that attempts to insert a range
diff --git a/libstdc++-v3/include/bits/stl_tree.h
b/libstdc++-v3/include/bits/stl_tree.h
index 44ffa626183..6147c340778 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -1459,6 +1459,12 @@ namespace __rb_tree
pair<_Base_ptr, _Base_ptr>
_M_get_insert_unique_pos(const key_type& __k);
+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26, P2363
+ template <typename _Kt>
+ pair<_Base_ptr, _Base_ptr>
+ _M_get_insert_unique_pos_tr(const _Kt& __k);
+#endif
+
pair<_Base_ptr, _Base_ptr>
_M_get_insert_equal_pos(const key_type& __k);
@@ -1466,6 +1472,13 @@ namespace __rb_tree
_M_get_insert_hint_unique_pos(const_iterator __pos,
const key_type& __k);
+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26, P2363
+ template <typename _Kt>
+ pair<_Base_ptr, _Base_ptr>
+ _M_get_insert_hint_unique_pos_tr(
+ const_iterator __pos, const _Kt& __k);
+#endif
+
pair<_Base_ptr, _Base_ptr>
_M_get_insert_hint_equal_pos(const_iterator __pos,
const key_type& __k);
@@ -1539,7 +1552,7 @@ namespace __rb_tree
_M_lower_bound(_Base_ptr __x, _Base_ptr __y,
const _Key& __k) const;
-#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+#ifdef __glibcxx_associative_heterogeneous_erasure // C++23, P2077
template <typename _HetKey>
_Base_ptr
_M_lower_bound_tr(
@@ -1550,7 +1563,7 @@ namespace __rb_tree
_M_upper_bound(_Base_ptr __x, _Base_ptr __y,
const _Key& __k) const;
-#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+#ifdef __glibcxx_associative_heterogeneous_erasure // C++23, P2077
template <typename _HetKey>
_Base_ptr
_M_upper_bound_tr(
@@ -1864,7 +1877,7 @@ namespace __rb_tree
size_type
erase(const key_type& __x);
-#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+#ifdef __glibcxx_associative_heterogeneous_erasure // C++23, P2077
template <typename _HetKey>
size_type
_M_erase_tr(const _HetKey& __x);
@@ -2068,7 +2081,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)
{
@@ -2218,7 +2231,7 @@ namespace __rb_tree
return __nh;
}
-#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+#ifdef __glibcxx_associative_heterogeneous_erasure // C++23, P2077
template <typename _HetKey>
node_type
_M_extract_tr(const _HetKey& __k)
@@ -2319,6 +2332,10 @@ namespace __rb_tree
_M_node(__t._M_create_node(std::forward<_Args>(__args)...))
{ }
+ explicit _Auto_node(_Rb_tree& __t)
+ : _M_t(__t), _M_node(nullptr)
+ { }
+
~_Auto_node()
{
if (_M_node)
@@ -2645,7 +2662,7 @@ namespace __rb_tree
return __y;
}
-#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+#ifdef __glibcxx_associative_heterogeneous_erasure // C++23, P2077
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
template <typename _HetKey>
@@ -2679,7 +2696,7 @@ namespace __rb_tree
return __y;
}
-#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+#ifdef __glibcxx_associative_heterogeneous_erasure // C++23, P2077
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
template <typename _HetKey>
@@ -2826,6 +2843,39 @@ namespace __rb_tree
return _Res(__j._M_node, _Base_ptr());
}
+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26, P2363
+ template<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ template <typename _Kt>
+ auto
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _M_get_insert_unique_pos_tr(const _Kt& __k)
+ -> pair<_Base_ptr, _Base_ptr>
+ {
+ 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());
+ }
+#endif
+
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
@@ -2952,6 +3002,64 @@ namespace __rb_tree
return _Res(__position._M_node, _Base_ptr());
}
+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26, P2363
+ template<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ template <typename _Kt>
+ auto
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _M_get_insert_hint_unique_pos_tr(
+ const_iterator __position, const _Kt& __k)
+ -> pair<_Base_ptr, _Base_ptr>
+ {
+ 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());
+ }
+#endif
+
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
#if __cplusplus >= 201103L
@@ -3171,7 +3279,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,
@@ -3211,7 +3319,7 @@ namespace __rb_tree
return __old_size - size();
}
-#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+#ifdef __glibcxx_associative_heterogeneous_erasure // C++23, P2077
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
template <typename _HetKey>
@@ -3334,7 +3442,7 @@ namespace __rb_tree
};
#endif // C++17
-#if __glibcxx_associative_heterogeneous_erasure // C++23, P2077
+#ifdef __glibcxx_associative_heterogeneous_erasure // C++23, P2077
template <typename _Kt, typename _Container>
concept __heterogeneous_tree_key =
__transparent_comparator<typename _Container::key_compare> &&
diff --git a/libstdc++-v3/include/bits/unordered_map.h
b/libstdc++-v3/include/bits/unordered_map.h
index 193c1795c07..8313fa83dba 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)...);
}
+#if __glibcxx_associative_heterogeneous_insertion // P2363R5
+ 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
+#if __glibcxx_associative_heterogeneous_insertion // P2363R5
+ 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;
}
+#if __glibcxx_associative_heterogeneous_insertion // P2363R5
+ template <__heterogeneous_hash_key<unordered_map> _Kt, typename _Mapped>
+ pair<iterator, bool>
+ insert_or_assign(_Kt&& __k, _Mapped&& __obj)
+ {
+ auto __ret = _M_h.try_emplace(
+ cend(), std::forward<_Kt>(__k), std::forward<_Mapped>(__obj));
+ if (!__ret.second)
+ __ret.first->second = std::forward<_Mapped>(__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;
}
+
+#if __glibcxx_associative_heterogeneous_insertion // P2363R5
+ template <__heterogeneous_hash_key<unordered_map> _Kt, typename _Mapped>
+ iterator
+ insert_or_assign(const_iterator __hint, _Kt&& __k, _Mapped&& __obj)
+ {
+ auto __ret = _M_h.try_emplace(__hint,
+ std::forward<_Kt>(__k), std::forward<_Mapped>(__obj));
+ if (!__ret.second)
+ __ret.first->second = std::forward<_Mapped>(__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)]; }
+
+#if __glibcxx_associative_heterogeneous_insertion // P2363R5
+ 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); }
+#if __glibcxx_associative_heterogeneous_insertion // P2363R5
+ 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); }
+
+#if __glibcxx_associative_heterogeneous_insertion // P2363R5
+ 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); }
+#if __glibcxx_associative_heterogeneous_insertion // P2363R5
+ 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); }
+#if __glibcxx_associative_heterogeneous_insertion // P2363R5
+ 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 b15f25be7fb..35dfc1d42b0 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 937ea09ad78..a963c21ee5c 100644
--- a/libstdc++-v3/include/bits/version.def
+++ b/libstdc++-v3/include/bits/version.def
@@ -2262,6 +2262,14 @@ ftms = {
};
};
+ftms = {
+ name = associative_heterogeneous_insertion;
+ values = {
+ v = 202306;
+ cxxmin = 26;
+ };
+};
+
// Standard test specifications.
stds[97] = ">= 199711L";
stds[03] = ">= 199711L";
diff --git a/libstdc++-v3/include/bits/version.h
b/libstdc++-v3/include/bits/version.h
index ed1794f4c0d..13bf1c5eaac 100644
--- a/libstdc++-v3/include/bits/version.h
+++ b/libstdc++-v3/include/bits/version.h
@@ -2536,4 +2536,14 @@
#endif /* !defined(__cpp_lib_is_implicit_lifetime) */
#undef __glibcxx_want_is_implicit_lifetime
+#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
+
#undef __glibcxx_want_all
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..e402cc28a5c
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/map/modifiers/hetero/insert.cc
@@ -0,0 +1,141 @@
+// { dg-do compile { target c++26 } }
+
+#include <map>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <compare>
+#include <cstring>
+#include <testsuite_hooks.h>
+
+struct X {
+ std::string s;
+ friend auto operator<=>(X const& a, X const& b) = default;
+};
+
+struct Y {
+ std::string_view s;
+ Y(std::string_view sv) : s(sv) {}
+ Y(std::string const& sv) : s(sv) {}
+ operator X() const { return X(std::basic_string(s)); }
+ friend auto operator<=>(Y const& a, Y const& b) = default;
+ friend auto operator<=>(X const& a, Y const& b) { return a.s <=> b.s; }
+};
+
+struct Sum {
+ int i{};
+ Sum() = default;
+ Sum(const int a, const int b = 0) : i(a + b) {}
+ operator int() { return i; }
+ friend bool operator<=>(Sum const& a, Sum const& b) = default;
+};
+
+using cmp = std::less<void>;
+
+void test1() // op[]
+{
+ std::map<X, Sum, cmp> amap{cmp{}};
+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
+
+ amap[(Y{std::string_view{"deg"}})] = Sum{4};
+ VERIFY(amap.size() == 4);
+
+ // no const overload.
+ // auto const& amapr{amap};
+ // static_assert(!requires{ amapr[(Y{std::string_view{"deg"}})]; });
+}
+
+void test2() // at()
+{
+ std::map<X, Sum, cmp> amap{cmp{}};
+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
+
+ VERIFY(Sum{3} == amap.at(Y{std::string_view{"def"}}));
+ VERIFY(amap.size() == 3);
+
+ amap.at(Y{std::string_view{"deg"}}) = 4;
+ VERIFY(amap.size() == 4);
+
+ auto const& amapr{amap};
+ VERIFY(Sum{4} == amapr.at(Y{std::string_view{"deg"}}));
+ try
+ {
+ amapr.at(Y{std::string_view{"deh"}});
+ VERIFY(false); // Should have thrown.
+ }
+ catch (std::out_of_range&) { VERIFY(amapr.size() == 4); }
+ catch (...) { VERIFY(false); } // Wrong exception.
+}
+
+void test3() // try_emplace
+{
+ std::map<X, Sum, cmp> amap{cmp{}};
+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
+
+ { // Fail, already there
+ auto [it, res] = amap.try_emplace(Y{std::string{"def"}}, 4, 5);
+ VERIFY(!res);
+ VERIFY(amap.size() == 3);
+ }
+ { // Succeed
+ auto [it, res] = amap.try_emplace(Y{std::string{"deg"}}, 4, 5);
+ VERIFY(res);
+ VERIFY(it->first == X{"deg"});
+ VERIFY(it->second == Sum{9});
+ VERIFY(amap.size() == 4);
+ }
+ { // Hinted, fail
+ auto it = amap.try_emplace(amap.begin(), Y{std::string{"def"}}, 4, 5);
+ VERIFY(amap.size() == 3);
+ VERIFY(it->first == X{"def"});
+ VERIFY(it->second == Sum{3});
+ }
+ { // Hinted, succeed
+ auto it = amap.try_emplace(amap.begin(), Y{std::string{"deg"}}, 4, 5);
+ VERIFY(amap.size() == 4);
+ VERIFY(it->first == X{"deg"});
+ VERIFY(it->second == Sum{9});
+ }
+}
+
+void test4() // insert_or_assign
+{
+ std::map<X, Sum, cmp> amap{cmp{}};
+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
+
+ { // Fail
+ auto [it, res] = amap.insert_or_assign(Y{std::string{"def"}}, 4);
+ VERIFY(amap.size() == 3);
+ VERIFY(!res);
+ VERIFY(it->first == X{"def"});
+ VERIFY(it->second == Sum{4});
+ }
+ { // Succeed
+ auto [it, res] = amap.insert_or_assign(Y{std::string{"deg"}}, 5);
+ VERIFY(amap.size() == 4);
+ VERIFY(res);
+ VERIFY(it->first == X{"deg"});
+ VERIFY(it->second == Sum{5});
+ }
+
+ { // Hinted, fail
+ auto it = amap.insert_or_assign(amap.begin(), Y{std::string{"def"}}, 6);
+ VERIFY(amap.size() == 4);
+ VERIFY(it->first == X{"def"});
+ VERIFY(it->second == Sum{4});
+ }
+ { // Hinted, succeed
+ auto it = amap.insert_or_assign(amap.begin(), Y{std::string{"deh"}}, 7);
+ VERIFY(amap.size() == 5);
+ VERIFY(it->first == X{"deh"});
+ VERIFY(it->second == Sum{7});
+ }
+}
+
+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..765ea405a27
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/set/modifiers/hetero/insert.cc
@@ -0,0 +1,60 @@
+// { dg-do compile { target c++26 } }
+
+#include <set>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <compare>
+#include <cstring>
+#include <testsuite_hooks.h>
+
+struct X {
+ std::string s;
+ friend auto operator<=>(X const& a, X const& b) = default;
+};
+
+struct Y {
+ std::string_view s;
+ Y(std::string_view sv) : s(sv) {}
+ Y(std::string const& sv) : s(sv) {}
+ operator X() const { return X(std::basic_string(s)); }
+ friend auto operator<=>(Y const& a, Y const& b) = default;
+ friend auto operator<=>(X const& a, Y const& b) { return a.s <=> b.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 [it, res] = aset.insert(Y{std::string{"def"}});
+ VERIFY(!res);
+ VERIFY(aset.size() == 3);
+ VERIFY(it->s == std::string{"def"});
+ }
+ { // Succeed
+ auto [it, res] = aset.insert(Y{std::string{"deg"}});
+ VERIFY(res);
+ VERIFY(aset.size() == 4);
+ VERIFY(it->s == std::string{"deg"});
+ }
+
+ { // Hinted, fail
+ auto it = aset.insert(aset.begin(), Y{std::string{"def"}});
+ VERIFY(aset.size() == 4);
+ VERIFY(it->s == std::string{"def"});
+ }
+ { // Hinted, succeed
+ auto it = aset.insert(aset.begin(), Y{std::string{"deh"}});
+ VERIFY(aset.size() == 5);
+ VERIFY(it->s == std::string{"deh"});
+ }
+}
+
+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..a6d9181123a
--- /dev/null
+++
b/libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/hetero/insert.cc
@@ -0,0 +1,145 @@
+// { dg-do compile { target c++26 } }
+
+#include <unordered_map>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <functional>
+#include <compare>
+#include <testsuite_hooks.h>
+
+struct X {
+ std::string s;
+ friend bool operator==(X const& a, X const& b) = default;
+};
+
+struct Y {
+ std::string_view s;
+ Y(std::string_view sv) : s(sv) {}
+ Y(std::string const& sv) : s(sv) {}
+ operator X() const { return X(std::basic_string(s)); }
+ friend bool operator==(Y const& a, Y const& b) = default;
+ friend bool operator==(X const& a, Y const& b) { return a.s == b.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>;
+
+struct Sum {
+ int i = 0;
+ Sum(int a = 0, int b = 0) : i(a + b) {}
+ operator int() const { return i; }
+};
+
+void test1() // op[]
+{
+ std::unordered_map<X, Sum, Hash, Equal> amap;
+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
+
+ amap[ Y{std::string_view{"deg"}} ] = Sum(4);
+ VERIFY(amap.size() == 4);
+}
+
+void test2() // at()
+{
+ std::unordered_map<X, Sum, Hash, Equal> amap;
+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
+
+ VERIFY(Sum(3) == amap.at(Y{std::string_view{"def"}}));
+ VERIFY(amap.size() == 3);
+
+ amap.at(Y{std::string_view{"deg"}}) = Sum(4);
+ VERIFY(amap.size() == 4);
+
+ auto const& amapr{amap};
+ VERIFY(Sum(4) == amapr.at(Y{std::string_view{"deg"}}));
+ try
+ {
+ amapr.at(Y{std::string_view{"deh"}});
+ VERIFY(false); // Should have thrown.
+ }
+ catch (std::out_of_range&) { VERIFY(amapr.size() == 4); }
+ catch (...) { VERIFY(false); } // Wrong exception.
+}
+
+void test3() // try_emplace
+{
+ std::unordered_map<X, Sum, Hash, Equal> amap;
+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
+
+ { // Fail, already there
+ auto [it, res] = amap.try_emplace(Y{std::string_view{"def"}}, 4, 5);
+ VERIFY(!res);
+ VERIFY(amap.size() == 3);
+ }
+ { // Succeed
+ auto [it, res] = amap.try_emplace(Y{std::string_view{"deg"}}, 4, 5);
+ VERIFY(res && it->second == Sum(9));
+ VERIFY(amap.size() == 4);
+ }
+ { // Hinted, fail
+ auto it = amap.try_emplace(amap.begin(), Y{std::string_view{"def"}}, 4, 5);
+ VERIFY(amap.size() == 3);
+ VERIFY(it->first == X("def"));
+ VERIFY(it->second == Sum(3));
+ }
+ { // Hinted, succeed
+ auto it = amap.try_emplace(amap.begin(), Y{std::string_view{"deg"}}, 4, 5);
+ VERIFY(amap.size() == 4);
+ VERIFY(it->first == X("deg"));
+ VERIFY(it->second == Sum(9));
+ }
+}
+
+void test4() // insert_or_assign
+{
+ std::unordered_map<X, Sum, Hash, Equal> amap;
+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
+
+ { // Fail
+ auto [it, res] = amap.insert_or_assign(Y{std::string_view{"def"}}, 4);
+ VERIFY(!res);
+ VERIFY(amap.size() == 3);
+ VERIFY(it->second == 4);
+ }
+ { // Succeed
+ auto [it, res] = amap.insert_or_assign(Y{std::string{"deg"}}, 5);
+ VERIFY(res);
+ VERIFY(amap.size() == 4);
+ VERIFY(it->second == 5);
+ }
+
+ { // Hinted, fail
+ auto it = amap.insert_or_assign(amap.begin(), Y{std::string{"def"}}, 6);
+ VERIFY(amap.size() == 4);
+ VERIFY(it->second == 4);
+ }
+ { // Hinted, succeed
+ auto it = amap.insert_or_assign(amap.begin(), Y{std::string{"deh"}}, 7);
+ VERIFY(amap.size() == 5);
+ VERIFY(it->second == 7);
+ }
+}
+
+void test5() // bucket
+{
+ std::unordered_map<X, Sum, Hash, Equal> amap;
+ amap.insert({{X{"abc"}, 1}, {X{"def"}, 2}, {X{"ghi"}, 3}});
+
+ auto const& amapr{amap};
+ VERIFY(amapr.bucket(X{"def"}) == amapr.bucket(Y{std::string_view{"def"}}));
+}
+
+int main()
+{
+ test1();
+ test2();
+ test3();
+ test4();
+ test5();
+}
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..d67fcc05d60
--- /dev/null
+++
b/libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/hetero/insert.cc
@@ -0,0 +1,44 @@
+// { dg-do compile { target c++26 } }
+
+#include <unordered_map>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <functional>
+#include <testsuite_hooks.h>
+
+struct X {
+ std::string s;
+ friend bool operator==(X const& a, X const& b) = default;
+};
+
+struct Y {
+ std::string_view s;
+ Y(std::string_view sv) : s(sv) {}
+ Y(std::string const& sv) : s(sv) {}
+ operator X() const { return X(std::basic_string(s)); }
+ friend bool operator==(Y const& a, Y const& b) = default;
+ friend bool operator==(X const& a, Y const& b) { return a.s == b.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, int, 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{std::string{"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..b678bde56fc
--- /dev/null
+++
b/libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/hetero/insert.cc
@@ -0,0 +1,44 @@
+// { dg-do compile { target c++26 } }
+
+#include <unordered_set>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <functional>
+#include <testsuite_hooks.h>
+
+struct X {
+ std::string s;
+ friend bool operator==(X const& a, X const& b) = default;
+};
+
+struct Y {
+ std::string_view s;
+ Y(std::string_view sv) : s(sv) {}
+ Y(std::string const& sv) : s(sv) {}
+ operator X() const { return X(std::basic_string(s)); }
+ friend bool operator==(Y const& a, Y const& b) = default;
+ friend bool operator==(X const& a, Y const& b) { return a.s == b.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{std::string{"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..2c5bd583cb9
--- /dev/null
+++
b/libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/hetero/insert.cc
@@ -0,0 +1,75 @@
+// { dg-do compile { target c++26 } }
+
+#include <unordered_set>
+#include <string>
+#include <string_view>
+#include <utility>
+#include <functional>
+#include <testsuite_hooks.h>
+
+struct X {
+ std::string s;
+ friend bool operator==(X const& a, X const& b) = default;
+};
+
+struct Y {
+ std::string_view s;
+ Y(std::string_view sv) : s(sv) {}
+ Y(std::string const& sv) : s(sv) {}
+ operator X() const { return X(std::basic_string(s)); }
+ friend bool operator==(Y const& a, Y const& b) = default;
+ friend bool operator==(X const& a, Y const& b) { return a.s == b.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 [it, res] = aset.insert(Y{std::string{"def"}});
+ VERIFY(!res);
+ VERIFY(aset.size() == 3);
+ VERIFY(it->s == std::string{"def"});
+ }
+ { // Succeed
+ auto [it, res] = aset.insert(Y{std::string{"deg"}});
+ VERIFY(res);
+ VERIFY(aset.size() == 4);
+ VERIFY(it->s == std::string{"deg"});
+ }
+
+ { // Hinted, fail
+ auto it = aset.insert(aset.begin(), Y{std::string{"def"}});
+ VERIFY(aset.size() == 4);
+ VERIFY(it->s == std::string{"def"});
+ }
+ { // Hinted, succeed
+ auto it = aset.insert(aset.begin(), Y{std::string{"deh"}});
+ VERIFY(aset.size() == 5);
+ VERIFY(it->s == std::string{"deh"});
+ }
+}
+
+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{std::string{"def"}}));
+}
+
+int main()
+{
+ test1();
+ test2();
+}
--
2.52.0
