On Thu, 26 Feb 2026 at 08:30 -0500, Nathan Myers wrote:
Changes in v9:
- Redo code path for new map<> and set<> insertion hinted
overloads to correctly choose the place to operate on.
- Document heterogeneous map operations.
- Extend new map and set tests to exercise new code paths.
- De-duplicate some code in bits/stl_tree.h.
Changes in v8:
- Test approximate key matching in map<>::insert_or_assign.
- Give test functions meaningful names.
Changes in v7:
- Regularize comments on new #ifdefs ("C++26, no "P2363").
Changes in v6:
- More testing for op[] and at(): move-from key argument when
and only when permitted.
- Test op[] and at more: 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:
/-- 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.
You don't need to mention _M_index_to_tr twice, but see below about
this function ...
* include/bits/stl_tree.h (_M_emplace_here, _M_get_insert_unique_pos_tr,
_M_get_insert_hint_unique_pos_tr): Define new heterogeneous insertion
code path for set and map.
(_M_lower_bound_tr, _M_upper_bound_tr): Remove overloads out of
version #ifdef.
Would "Move" be more accurate than "Remove"? And they're also changed
to delegate to the 3-arg versions.
(_M_lower_bound, _M_upper_bound): Delegate to _tr version.
* 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 | 161 ++-
libstdc++-v3/include/bits/stl_set.h | 35 +
libstdc++-v3/include/bits/stl_tree.h | 233 +++--
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 | 932 ++++++++++++++++++
.../set/modifiers/hetero/insert.cc | 361 +++++++
.../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, 2477 insertions(+), 82 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..f4211eba516 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
+ 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
+ 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..211dc56012a 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);
This function is defined below, but never seems to be used.
Is it needed?
+
+ // _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..f6aa5f26ec8 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.
@@ -522,6 +523,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
* subscript. If the key does not exist, a pair with that key
* is created using default values, which is then returned.
*
+ * If a heterogeneous key __k matches a range of elements, the
+ * first is chosen.
+ *
* Lookup requires logarithmic time.
*/
mapped_type&
@@ -560,6 +564,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.
/**
@@ -568,6 +581,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
* @return A reference to the data whose key is equivalent to @a __k, if
* such a data is present in the %map.
* @throw std::out_of_range If no such data is present.
+ *
+ * If a heterogeneous key __k matches a range of elements, the
+ * first is chosen.
*/
mapped_type&
at(const key_type& __k)
@@ -578,6 +594,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 +615,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 +769,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.
*
@@ -742,10 +784,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
*
* This function attempts to build and insert a (key, value) %pair into
* the %map.
- * A %map relies on unique keys and thus a %pair is only inserted if its
- * first element (the key) is not already present in the %map.
+ * A %map relies on unique keys and thus a %pair is only constucted
"constructed"
+ * and inserted if its first element (the key) is not already present
+ * in the %map.
* If a %pair is not inserted, this function has no effect.
*
+ * If a heterogeneous key __k matches a range of elements, the
+ * first is chosen.
+ *
* Insertion requires logarithmic time.
*/
template <typename... _Args>
@@ -781,6 +827,28 @@ _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;
+ auto [__left, __node] = _M_t._M_get_insert_unique_pos_tr(__k);
+ if (__node)
+ {
+ __i = _M_t._M_emplace_here(__left == __node, __node,
+ std::piecewise_construct,
+ std::forward_as_tuple(std::forward<_Kt>(__k)),
+ std::forward_as_tuple(std::forward<_Args>(__args)...));
+ return { __i, true };
+ }
+ __i = iterator(__left);
+ return { __i, false };
+ }
+#endif
+ ///@}
+
+ ///@{
/**
* @brief Attempts to build and insert a std::pair into the %map.
*
@@ -806,6 +874,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
*
https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
* for more on @a hinting.
*
+ * If a heterogeneous key __k matches a range of elements, the
+ * first is chosen.
+ *
* Insertion requires logarithmic time (if the hint is not taken).
*/
template <typename... _Args>
@@ -845,6 +916,28 @@ _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 [__left, __node] =
+ _M_t._M_get_insert_hint_unique_pos_tr(__hint, __k);
+ if (__node)
+ {
+ __i = _M_t._M_emplace_here(__left == __node, __node,
+ std::piecewise_construct,
+ std::forward_as_tuple(std::forward<_Kt>(__k)),
+ std::forward_as_tuple(std::forward<_Args>(__args)...));
+ }
+ else __i = iterator(__left);
+ 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 +989,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
return _M_t._M_emplace_unique(std::forward<_Pair>(__x));
}
#endif
- /// @}
+ ///@}
#if __cplusplus >= 201103L
/**
@@ -929,6 +1022,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
@@ -942,9 +1036,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
* This function is not concerned about whether the insertion
* took place, and thus does not return a boolean like the
* single-argument insert() does. Note that the first
- * parameter is only a hint and can potentially improve the
- * performance of the insertion process. A bad hint would
- * cause no gains in efficiency.
+ * parameter is only a hint but can potentially improve the
+ * performance of the insertion process. A bad hint would
+ * provide no gain in efficiency.
This is better phrasing, thanks.
*
* See
*
https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints
@@ -992,6 +1086,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
@@ -1009,6 +1104,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
* If the %pair was already in the %map, the .second of the %pair
* is assigned from __obj.
*
+ * If a heterogeneous key __k matches a range of elements, the first
+ * is chosen.
+ *
* Insertion requires logarithmic time.
*/
template <typename _Obj>
@@ -1046,6 +1144,31 @@ _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;
+ auto [__left, __node] =_M_t._M_get_insert_unique_pos_tr(__k);
+ if (__node)
+ {
+ __i = _M_t._M_emplace_here(__left == __node, __node,
+ std::piecewise_construct,
+ std::forward_as_tuple(std::forward<_Kt>(__k)),
+ std::forward_as_tuple(std::forward<_Obj>(__obj)));
+ return { __i, true };
+ }
+ __i = iterator(__left);
+ (*__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
@@ -1064,6 +1187,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
* If the %pair was already in the %map, the .second of the %pair
* is assigned from __obj.
*
+ * If a heterogeneous key __k matches a range of elements, the
+ * first is chosen.
+ *
* Insertion requires logarithmic time.
*/
template <typename _Obj>
@@ -1105,9 +1231,32 @@ _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 [__left, __node] =
+ _M_t._M_get_insert_hint_unique_pos_tr(__hint, __k);
+ if (__node)
+ {
+ return _M_t._M_emplace_here(__left == __node, __node,
+ std::piecewise_construct,
+ std::forward_as_tuple(std::forward<_Kt>(__k)),
+ std::forward_as_tuple(std::forward<_Obj>(__obj)));
+ }
+ __i = iterator(__left);
+ (*__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..b93e1d8ef9d 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,24 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
}
#endif
+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
+ template <__heterogeneous_tree_key<set> _Kt>
+ pair<iterator, bool>
+ insert(_Kt&& __k)
+ {
+ auto [__left, __node] =_M_t._M_get_insert_unique_pos_tr(__k);
+ if (__node)
+ {
+ iterator __i = _M_t._M_emplace_here(
+ (__left == __node), __node, std::forward<_Kt>(__k));
+ return { __i, true };
+ }
+ return { iterator(__left), false };
+ }
+#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 +596,22 @@ _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 __hint, _Kt&& __k)
+ {
+ auto [__left, __node] =
+ _M_t._M_get_insert_hint_unique_pos_tr(__hint, __k);
+ if (__node)
+ return _M_t._M_emplace_here(
+ (__left == __node), __node, std::forward<_Kt>(__k));
+ else
+ return iterator(__left);
+ }
+#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..52a5834bcb8 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -74,6 +74,9 @@
#ifdef __glibcxx_node_extract // >= C++17
# include <bits/node_handle.h>
#endif
+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
+#include <cstdlib> // for abort
+#endif
#if __cplusplus < 201103L
# undef _GLIBCXX_USE_ALLOC_PTR_FOR_RB_TREE
@@ -1470,6 +1473,20 @@ namespace __rb_tree
_M_get_insert_hint_equal_pos(const_iterator __pos,
const key_type& __k);
+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
+ template <typename... _Args>
+ iterator
+ _M_emplace_here(bool __place_left, _Base_ptr __node, _Args&&... __args);
+
+ template <typename _Kt>
+ pair<_Base_ptr, _Base_ptr>
+ _M_get_insert_unique_pos_tr(const _Kt& __k);
+
+ template <typename _Kt>
+ pair<_Base_ptr, _Base_ptr>
+ _M_get_insert_hint_unique_pos_tr(const_iterator, const _Kt& __k);
+#endif
+
private:
#if __cplusplus >= 201103L
template<typename _Arg, typename _NodeGen>
@@ -1537,7 +1554,8 @@ namespace __rb_tree
_Base_ptr
_M_lower_bound(_Base_ptr __x, _Base_ptr __y,
- const _Key& __k) const;
+ const _Key& __k) const
+ { return _M_lower_bound_tr(__x, __y, __k); }
template <typename _Kt>
_Base_ptr
@@ -1545,7 +1563,8 @@ namespace __rb_tree
_Base_ptr
_M_upper_bound(_Base_ptr __x, _Base_ptr __y,
- const _Key& __k) const;
+ const _Key& __k) const
+ { return _M_upper_bound_tr(__x, __y, __k); }
template <typename _Kt>
_Base_ptr
@@ -1960,42 +1979,6 @@ namespace __rb_tree
return std::distance(__p.first, __p.second);
}
- template<typename _Kt,
- typename _Req = __has_is_transparent_t<_Compare, _Kt>>
- _Base_ptr
- _M_lower_bound_tr(const _Kt& __k) const
- {
- auto __x = _M_begin();
- auto __y = _M_end();
- while (__x)
- if (!_M_key_compare(_S_key(__x), __k))
- {
- __y = __x;
- __x = _S_left(__x);
- }
- else
- __x = _S_right(__x);
- return __y;
- }
-
- template<typename _Kt,
- typename _Req = __has_is_transparent_t<_Compare, _Kt>>
- _Base_ptr
- _M_upper_bound_tr(const _Kt& __k) const
- {
- auto __x = _M_begin();
- auto __y = _M_end();
- while (__x)
- if (_M_key_compare(__k, _S_key(__x)))
- {
- __y = __x;
- __x = _S_left(__x);
- }
- else
- __x = _S_right(__x);
- return __y;
- }
-
template<typename _Kt,
typename _Req = __has_is_transparent_t<_Compare, _Kt>>
pair<iterator, iterator>
@@ -2021,6 +2004,16 @@ namespace __rb_tree
}
#endif // __glibcxx_generic_associative_lookup
+ template <typename _Kt>
+ _Base_ptr
+ _M_lower_bound_tr(const _Kt& __k) const
+ { return _M_lower_bound_tr(_M_begin(), _M_end(), __k); }
+
+ template <typename _Kt>
+ _Base_ptr
+ _M_upper_bound_tr(const _Kt& __k) const
+ { return _M_upper_bound_tr(_M_begin(), _M_end(), __k); }
+
// Debugging.
bool
__rb_verify() const;
@@ -2060,7 +2053,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)
{
@@ -2446,7 +2439,7 @@ namespace __rb_tree
for (; __first != __last; ++__first)
_M_insert_equal_(end(), *__first, __roan);
}
-#endif
+#endif // C++11
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
@@ -2619,22 +2612,6 @@ namespace __rb_tree
}
}
- template<typename _Key, typename _Val, typename _KeyOfValue,
- typename _Compare, typename _Alloc>
- typename _Rb_tree<_Key, _Val, _KeyOfValue,
- _Compare, _Alloc>::_Base_ptr
- _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
- _M_lower_bound(_Base_ptr __x, _Base_ptr __y,
- const _Key& __k) const
- {
- while (__x)
- if (!_M_key_compare(_S_key(__x), __k))
- __y = __x, __x = _S_left(__x);
- else
- __x = _S_right(__x);
- return __y;
- }
-
Instead of removing the _M_lower_bound function and changing all its
callers to call _M_lower_bound_tr instead, would it make sense to just
change _M_lower_bound to be unconditionally transparent, and then
change all callers of _M_lower_bound_tr to call this?
The _tr suffix made sense to distinguish the transparent overloads
from the non-transparent ones, so that we didn't have to do overload
resolution to decide which to use (because they have different names
and so aren't really overloads). But if we don't have any
non-transparent versions at all, then we can just use the better name.
We don't need to use the foo_tr suffix to distinguish from some other
foo function, because there is no other foo function.
So change the 1-arg and 3-arg forms of _M_lower_bound and
_M_upper_bound to be transparent, and update all callers of the _tr
ones. Would that work?
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
template <typename _Kt>
@@ -2650,22 +2627,6 @@ namespace __rb_tree
return __y;
}
- template<typename _Key, typename _Val, typename _KeyOfValue,
- typename _Compare, typename _Alloc>
- typename _Rb_tree<_Key, _Val, _KeyOfValue,
- _Compare, _Alloc>::_Base_ptr
- _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
- _M_upper_bound(_Base_ptr __x, _Base_ptr __y,
- const _Key& __k) const
- {
- while (__x)
- if (_M_key_compare(__k, _S_key(__x)))
- __y = __x, __x = _S_left(__x);
- else
- __x = _S_right(__x);
- return __y;
- }
-
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
template <typename _Kt>
@@ -2830,6 +2791,56 @@ namespace __rb_tree
return _Res(__x, __y);
}
+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
+
+ // Multiple elements may compare equal to __k. Identify the first
+ // of any such elements, or insert normally.
+
+ 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>
+ {
+ if (size() == 0)
+ return { &_M_impl._M_header, &_M_impl._M_header }; // Insert as root.
+
+ _Base_ptr __x = _M_begin(), __y = __x;
+ bool __k_le_y = false;
+ do
+ {
+ __y = __x;
+ __k_le_y = ! _M_key_compare(_S_key(__x), __k);
+ __x = __k_le_y ? _S_left(__x) : _S_right(__x);
+ }
+ while (__x);
+ // If !__k_le_y, __k > *__y;
+ // If __y is rightmost, put at _M_right under *__y.
+ // else if __k < *(__y+1), put at _M_right under *__y.
+ // else __k == *(__y+1), do not insert, report (__y+1).
+ // else, __k_le_y, __k <= *__y;
+ // If __k < *__Y, put at _M_left under *__y.
+ // else __k == *__y, do not insert, report __y.
+ auto __j = iterator(__y);
+ if (! __k_le_y) // k > *__y
+ {
+ if (__y == _M_rightmost())
+ return { {}, __y }; // Place to right under __y.
+ ++__j;
+ }
+ if (_M_key_compare(__k, _S_key(__j._M_node)))
+ {
+ if (__k_le_y)
+ return { __y, __y }; // Place to left under __y.
+ else
+ return { {}, __y }; // Place to right under __y.
+ }
+ return { __j._M_node, {} }; // No insert.
+ }
+#endif
+
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
#if __cplusplus >= 201103L
@@ -2936,6 +2947,57 @@ namespace __rb_tree
return _Res(__position._M_node, _Base_ptr());
}
+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
+ 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 __hint, const _Kt& __k)
+ -> pair<_Base_ptr, _Base_ptr>
+ {
+ auto __node =__hint._M_node;
+ if (__node == _M_end())
+ {
+ if (size() > 0 && _M_key_compare(_S_key(_M_rightmost()), __k))
+ return { {}, _M_rightmost() };
+ return _M_get_insert_unique_pos_tr(__k);
+ }
+ if (_M_key_compare(__k, _S_key(__node)))
+ { // First, try before...
+ if (__node == _M_leftmost()) // begin()
+ return { _M_leftmost(), _M_leftmost() };
+ iterator __before(__node);
+ if (_M_key_compare(_S_key((--__before)._M_node), __k))
+ {
+ if (!_S_right(__before._M_node))
+ return { {}, __before._M_node }; // put right
+ return { __node, __node }; // put left;
+ }
+ return _M_get_insert_unique_pos_tr(__k);
+ }
+ if (_M_key_compare(_S_key(__node), __k))
+ { // ... then try after.
+ if (__node == _M_rightmost())
+ return { {}, _M_rightmost() };
+ iterator __after(__node);
+ if (_M_key_compare(__k, _S_key((++__after)._M_node)))
+ {
+ if (!_S_right(__node))
+ return { {}, __node };
+ return { __after._M_node, __after._M_node };
+ }
+ return _M_get_insert_unique_pos_tr(__k);
+ }
+ // Equal to __k; check if any more to the left.
+ iterator __before(__node);
+ if (__node == _M_leftmost() ||
+ _M_key_compare(_S_key((--__before)._M_node), __k))
+ { return { __node, {} }; }
+ return _M_get_insert_unique_pos_tr(__k);
+ }
+#endif
+
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
#if __cplusplus >= 201103L
@@ -3155,8 +3217,35 @@ namespace __rb_tree
return __z._M_insert(__res);
return __z._M_insert_equal_lower();
}
+
+#ifdef __glibcxx_associative_heterogeneous_insertion // C++26
+
+ // If __pos.second == &_M_impl._M_header, insert at root;
+ // else if __pos.first == __pos.second, insert at __pos.second._M_left;
+ // else insert at __pos.second._M_right, and rebalance.
+
+ template <typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ template <typename... _Args>
+ auto
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _M_emplace_here(bool __place_left, _Base_ptr __node, _Args&&... __args)
+ -> iterator
+ {
+ _Auto_node __z(*this, std::forward<_Args>(__args)...);
+ _Base_ptr __base_z = __z._M_node->_M_base_ptr();
+ if ((__place_left ? __node->_M_left : __node->_M_right) != 0)
+ std::abort();
+ _Node_traits::_S_insert_and_rebalance(
+ __place_left, __base_z, __node, _M_impl._M_header);
+ __z._M_node = nullptr;
+ ++_M_impl._M_node_count;
+ return iterator(__base_z);
+ }
#endif
+#endif // >= C++11
+
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
