[PATCH v12] libstdc++: container heterogeneous insertion (P2363) [PR117402]
François Dumont
frs.dumont@gmail.com
Wed Mar 4 05:39:57 GMT 2026
On 3/3/26 22:07, Jonathan Wakely wrote:
> On Tue, 03 Mar 2026 at 12:51 -0500, Nathan Myers wrote:
>> Changes in v12
>> - Strip doxygen improvements.
>>
>> Changes in v11
>> - Delete #include, debug instrumentation that called abort.
>> - Delete spurious DR comment text.
>> - Delete unused _M_index_to_tr.
>> - Un-de-duplicate lower/upper_bound apparatus, pending cleanup
>> in gcc-17.
>> - Regularize formal argument names (e.g. __pos -> __hint) for
>> consistency and to match doxygen annotations.
>> - Move ++after, --before iterator operations to separate
>> statement for better clarity.
>> - Improve tests.
>> - Further improve, regularize doxygen annotation text.
>> - Adjust Changelog entries to match.
>>
>> Changes in v10
>> - Fix tests that had exercised non-heterogeneous insertion.
>> - Test, handle inserting to empty tree.
>> - Clean up and modernize doxygen annotations.
>>
>> 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 and formal argument names
>> made consistent with annotations and other functions.
>
>
> OK for trunk, thanks
>
>
>> libstdc++-v3/ChangeLog:
>> PR libstdc++/117402
>> * include/bits/stl_map.h (operator[], at (2x), try_emplace (2x),
>> insert_or_assign (2x)): Add overloads.
>> Also, modernize doxygen text, regularize formal argument names.
>> * include/bits/unordered_map.h (operator[], at (2x),
>> try_emplace (2x), insert_or_assign (2x), bucket (2x)): Add
>> overloads.
>> * include/bits/stl_set.h (insert (2x)): Add overloads.
>> Also, modernize doxygen text, regularize formal argument names.
>> * include/bits/unordered_set.h (insert (2x), bucket (2x)): Add
>> overloads.
>> * include/bits/hashtable.h (_M_bucket_tr, _M_insert_tr): Define.
>> * include/bits/hashtable_policy.h (_M_at_tr (2x)): 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.
>> * 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 | 26 +-
>> libstdc++-v3/include/bits/stl_map.h | 135 ++-
>> libstdc++-v3/include/bits/stl_set.h | 35 +
>> libstdc++-v3/include/bits/stl_tree.h | 146 ++-
>> 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 | 376 +++++++
>> .../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, 2420 insertions(+), 7 deletions(-)
>> create mode 100644
>> libstdc++-v3/testsuite/23_containers/map/modifiers/hetero/insert.cc
>> create mode 100644
>> libstdc++-v3/testsuite/23_containers/set/modifiers/hetero/insert.cc
>> create mode 100644
>> libstdc++-v3/testsuite/23_containers/unordered_map/modifiers/hetero/insert.cc
>> create mode 100644
>> libstdc++-v3/testsuite/23_containers/unordered_multimap/modifiers/hetero/insert.cc
>> create mode 100644
>> libstdc++-v3/testsuite/23_containers/unordered_multiset/modifiers/hetero/insert.cc
>> create mode 100644
>> libstdc++-v3/testsuite/23_containers/unordered_set/modifiers/hetero/insert.cc
>>
>> diff --git a/libstdc++-v3/include/bits/hashtable.h
>> b/libstdc++-v3/include/bits/hashtable.h
>> index 48695c013f3..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..79c36e4a02b 100644
>> --- a/libstdc++-v3/include/bits/hashtable_policy.h
>> +++ b/libstdc++-v3/include/bits/hashtable_policy.h
>> @@ -872,6 +872,26 @@ namespace __detail
>> __throw_out_of_range(__N("unordered_map::at"));
>> return __ite->second;
>> }
>> +
>> + template <typename _Kt>
I see 'template<typename _Kt>', without space between template and '<'
usually.
Is it correct coding style too ?
More information about the Libstdc++
mailing list