[PATCHv9] libstdc++: container heterogeneous insertion (P2363) [PR117402]
Tomasz Kaminski
tkaminsk@redhat.com
Fri Feb 27 13:00:43 GMT 2026
On Fri, Feb 27, 2026 at 1:57 PM Nathan Myers <ncm@cantrip.org> wrote:
> Thank you.
>
> On 2/27/26 7:38 AM, Jonathan Wakely wrote:
> > On Thu, 26 Feb 2026 at 08:30 -0500, Nathan Myers wrote:
> >> Changes in v9:
> >> * 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 ...
>
> Oops.
>
> >> * 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.
>
> OK.
>
>
> >> 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?
>
> Good catch. It is left over from an early edit.
>
> >> +
> >> + // _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;
> >> + }
> >> };
>
> I will clean all this up.
>
> >> @@ -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"
>
> OK
>
> >> + * 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>
> >> @@ -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.
>
> I have a fair bit more of this.
>
>
> >> 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?
>
> Yes. The old headers were left in just to minimize text churn.
>
There is a lot of deduplication like that that could be done in the new
overloads,
but I think this would be good thing to tackle early in GCC-17, and for
this patch
simply leave old paths unaffected? The code-size remains the same, as they
are diffrent specializations anway.
>
> >> template<typename _Key, typename _Val, typename _KeyOfValue,
> >> typename _Compare, typename _Alloc>
> >> template <typename _Kt>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20260227/4edffd5f/attachment-0001.htm>
More information about the Libstdc++
mailing list