[PATCH 3/3] libstdc++: Reuse predicates in std::search and std::is_permutation

[Tomasz Kaminski]

On Wed, Oct 15, 2025 at 1:16 PM Jonathan Wakely <jwakely@redhat.com> wrote:

> On Thu, 25 Sept 2025 at 15:22, Jonathan Wakely <jwakely@redhat.com> wrote:
> >
> > Hoist construction of the call wrappers out of the loop when we're
> > repeatedly creating a call wrapper with the same bound arguments.
> >
> > We need to be careful about iterators that return proxy references,
> > because bind1st(pred, *first) could bind a reference to a prvalue proxy
> > reference returned by *first. That would then be an invalid reference by
> > the time we invoked the call wrapper.
> >
> > If we dereference the iterator first and store the result of that on the
> > stack, then we don't have a prvalue proxy reference, and can bind it (or
> > the value it refers to) into the call wrapper:
> >
> >   auto&& val = *first; // lifetime extension
> >   auto wrapper = bind1st(pred, val);
> >   for (;;)
> >     /* use wrapper */;
> >
> > This ensures that the reference returned from *first outlives the call
> > wrapper, whether it's a proxy reference or not.
>
> After reviewing https://cplusplus.github.io/LWG/issue2962 I wonder if
> this should be:
>
>   const iter_value_t<Iterator>& val = *first;
>
> instead of using auto&& val.
>
With https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p2408r5.html
these algorithms
must work for range iterators, including a zip iterator for which
reference_type is pair<T&, U&>,
and iter_value is pair<T, U>. So the change to:
  const iter_value_t<Iterator>& val = *first;
Would require creating a pair<T, U> from pair<T&, U&> which will not work
for if type
is only move constructible. These algorithms seem to work even for
non-movable types.

>
> The difference is that we would coerce a proxy reference to the value
> type and then bind a reference to that, rather than binding to the
> proxy reference.

I do not think we could coerce proxy reference to value_type if we haven't
required
indirectly storable.

>


> I don't think it really matters, because the algo requirements already
> say that pred(*first, v) must work an be equal to pred(u, v) so the
> pred can't require that its arguments are exactly value_type, it has
> to work with the reference type too.
>
These changes were made for search and is_permutation, that I believe never
feed value type
to predicate, just *iterator. The range version of them do not require
ability to store a copy of
the input,

In short, I think you got it right, do not break it.

> >
> > For C++98 compatibility in __search we can use __decltype(expr) instead
> > of auto&&.
> >
> > libstdc++-v3/ChangeLog:
> >
> >         * include/bits/stl_algobase.h (__search, __is_permutation):
> >         Reuse predicate instead of creating a new one each time.
> >         * include/bits/stl_algo.h (__is_permutation): Likewise.
> > ---
> >
> > Tested powerpc64le-linux and x86_64-linux.
> >
> > This part wasn't previously reviewed at all on the forge.
> >
> >  libstdc++-v3/include/bits/stl_algo.h     | 14 ++++--------
> >  libstdc++-v3/include/bits/stl_algobase.h | 29 +++++++++++-------------
> >  2 files changed, 18 insertions(+), 25 deletions(-)
> >
> > diff --git a/libstdc++-v3/include/bits/stl_algo.h
> b/libstdc++-v3/include/bits/stl_algo.h
> > index 7ff5dd84a97a..bbd1800af779 100644
> > --- a/libstdc++-v3/include/bits/stl_algo.h
> > +++ b/libstdc++-v3/include/bits/stl_algo.h
> > @@ -3531,18 +3531,14 @@ _GLIBCXX_END_INLINE_ABI_NAMESPACE(_V2)
> >
> >        for (_ForwardIterator1 __scan = __first1; __scan != __last1;
> ++__scan)
> >         {
> > -         if (__scan != std::__find_if(__first1, __scan,
> > -                                      __gnu_cxx::__ops::bind1st(__pred,
> > -
> *__scan)))
> > +         auto&& __scan_val = *__scan;
> > +         auto __scaneq = __gnu_cxx::__ops::bind1st(__pred, __scan_val);
> > +         if (__scan != std::__find_if(__first1, __scan, __scaneq))
> >             continue; // We've seen this one before.
> >
> > -         auto __matches = std::__count_if(__first2, __last2,
> > -
> __gnu_cxx::__ops::bind1st(__pred,
> > -
> *__scan));
> > +         auto __matches = std::__count_if(__first2, __last2, __scaneq);
> >           if (0 == __matches
> > -             || std::__count_if(__scan, __last1,
> > -                                __gnu_cxx::__ops::bind1st(__pred,
> *__scan))
> > -             != __matches)
> > +               || std::__count_if(__scan, __last1, __scaneq) !=
> __matches)
> >             return false;
> >         }
> >        return true;
> > diff --git a/libstdc++-v3/include/bits/stl_algobase.h
> b/libstdc++-v3/include/bits/stl_algobase.h
> > index 03f64fb3e6c3..443cbef76dee 100644
> > --- a/libstdc++-v3/include/bits/stl_algobase.h
> > +++ b/libstdc++-v3/include/bits/stl_algobase.h
> > @@ -2149,21 +2149,21 @@ _GLIBCXX_END_NAMESPACE_ALGO
> >        if (__first1 == __last1 || __first2 == __last2)
> >         return __first1;
> >
> > +      __decltype(*__first2) __first2_val(*__first2);
> > +      __decltype(__gnu_cxx::__ops::bind2nd(__predicate, __first2_val))
> > +       __match_first = __gnu_cxx::__ops::bind2nd(__predicate,
> __first2_val);
> > +
> >        // Test for a pattern of length 1.
> >        _ForwardIterator2 __p1(__first2);
> >        if (++__p1 == __last2)
> > -       return std::__find_if(__first1, __last1,
> > -                             __gnu_cxx::__ops::bind2nd(__predicate,
> > -                                                       *__first2));
> > +       return std::__find_if(__first1, __last1, __match_first);
> >
> >        // General case.
> >        _ForwardIterator1 __current = __first1;
> >
> >        for (;;)
> >         {
> > -         __first1 =
> > -           std::__find_if(__first1, __last1,
> > -                          __gnu_cxx::__ops::bind2nd(__predicate,
> *__first2));
> > +         __first1 = std::__find_if(__first1, __last1, __match_first);
> >
> >           if (__first1 == __last1)
> >             return __last1;
> > @@ -2184,6 +2184,7 @@ _GLIBCXX_END_NAMESPACE_ALGO
> >         }
> >        return __first1;
> >      }
> > +#undef __match_first
> >
> >  #if __cplusplus >= 201103L
> >    template<typename _ForwardIterator1, typename _ForwardIterator2,
> > @@ -2208,18 +2209,14 @@ _GLIBCXX_END_NAMESPACE_ALGO
> >        std::advance(__last2, std::distance(__first1, __last1));
> >        for (_ForwardIterator1 __scan = __first1; __scan != __last1;
> ++__scan)
> >         {
> > -         if (__scan != std::__find_if(__first1, __scan,
> > -                                      __gnu_cxx::__ops::bind1st(__pred,
> > -
> *__scan)))
> > +         auto&& __scan_val = *__scan;
> > +         auto __scaneq = __gnu_cxx::__ops::bind1st(__pred, __scan_val);
> > +         if (__scan != std::__find_if(__first1, __scan, __scaneq))
> >             continue; // We've seen this one before.
> >
> > -         auto __matches
> > -           = std::__count_if(__first2, __last2,
> > -                             __gnu_cxx::__ops::bind1st(__pred,
> *__scan));
> > -         if (0 == __matches ||
> > -             std::__count_if(__scan, __last1,
> > -                             __gnu_cxx::__ops::bind1st(__pred, *__scan))
> > -             != __matches)
> > +         auto __matches = std::__count_if(__first2, __last2, __scaneq);
> > +         if (0 == __matches
> > +               || std::__count_if(__scan, __last1, __scaneq) !=
> __matches)
> >             return false;
> >         }
> >        return true;
> > --
> > 2.51.0
> >
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20251015/89a51c56/attachment.htm>