On Fri, 27 Feb 2026 at 11:05 +0100, Tomasz Kaminski wrote:
Resending to libstdc++-patches, that I have accidentally dropped.On Fri, Feb 27, 2026 at 11:03 AM Tomasz Kaminski <[email protected]> wrote:On Thu, Feb 26, 2026 at 2:33 PM Nathan Myers <[email protected]> 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. * 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. (_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. ---LGTM only small changes: * remove the abort (and related includes) or replace with glibcxx assert * some copy-pasted comment about DR to be removed * stylistic suggestion regarding --/++ I wondered about delegating non-TR functions to the tr ones (we can check if K type is not same key_type to check for equivalent elements), but I think such change to existing function would be too late for GCC-16, and something we could consider doing at bengining of GCC-17. This change is more conservative and does not affect pre-C++20 changes.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); + + // _GLIBCXX_RESOLVE_LIB_DEFECTS + // DR 761. unordered_map needs an at() member function.I doubt this defect applied to heterogeneous overloads of at, remove the comment.
Right, the defect was fixed nearly 20 years ago, it never affected these new functions, and we should not have a comment suggesting that we implemented some change to these functions as a result of LWG 761. I think we shouldn't even have the comment for the original unordered_map::at overloads, because they were in C++11 from its initial publication, so LWG 761 was just a change between two C++0x drafts, and we don't need to document that we implement a change from the published standard (because we don't). But cleaning that up by removing the existing comment is separate from this change. Please just don't add another copy of the comment.
+ 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 + * 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. * * 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 +#endifRemove it.
Definitely. We don't want to include that here. If we wanted to call abort, we'd just do it as __builtin_abort().
#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; - } - 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);Put --__before as separate statemnt before if, the -- is easy to miss,
Agreed.
and line count is not metric to optimize for. I am ok if that get's changed only in this new function.+ 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);Same comment about ++.+ 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();That should be __glibcxx_assert at most, but seem like this would be bug in implementation and not user input.
Yes, is this just checking that the tree structure has not been corrupted? I don't think we want that unconditionally. Maybe as __glibcxx_assert, or guarded by #ifdef _GLIBCXX_DEBUG.
+ _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
