Re: [PATCH 3/3] libstdc++: Implement ranges::find_last{, _if, _if_not} from P1223R5

[Jonathan Wakely <jwakely@redhat.com>]

On Mon, 14 Nov 2022 at 04:51, Patrick Palka via Libstdc++
<libstdc++@gcc.gnu.org> wrote:
>
> Tested on x86_64-pc-linux-gnu, does this look OK for trunk?
>
> libstdc++-v3/ChangeLog:
>
>         * include/bits/ranges_algo.h (__find_last_fn, find_last):
>         Define.
>         (__find_last_if_fn, find_last_if): Define.
>         (__find_last_if_not_fn, find_last_if_not): Define.
>         * testsuite/25_algorithms/find_last/1.cc: New test.
>         * testsuite/25_algorithms/find_last_if/1.cc: New test.
>         * testsuite/25_algorithms/find_last_if_not/1.cc: New test.
> ---
>  libstdc++-v3/include/bits/ranges_algo.h       | 123 ++++++++++++++++++
>  .../testsuite/25_algorithms/find_last/1.cc    |  90 +++++++++++++
>  .../testsuite/25_algorithms/find_last_if/1.cc |  92 +++++++++++++
>  .../25_algorithms/find_last_if_not/1.cc       |  92 +++++++++++++
>  4 files changed, 397 insertions(+)
>  create mode 100644 libstdc++-v3/testsuite/25_algorithms/find_last/1.cc
>  create mode 100644 libstdc++-v3/testsuite/25_algorithms/find_last_if/1.cc
>  create mode 100644 libstdc++-v3/testsuite/25_algorithms/find_last_if_not/1.cc
>
> diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
> index f003117c569..0e4329382eb 100644
> --- a/libstdc++-v3/include/bits/ranges_algo.h
> +++ b/libstdc++-v3/include/bits/ranges_algo.h
> @@ -3565,6 +3565,129 @@ namespace ranges
>    };
>
>    inline constexpr __iota_fn iota{};
> +
> +  struct __find_last_fn
> +  {
> +    template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, typename T, typename _Proj = identity>
> +      requires indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>, const T*>
> +      constexpr subrange<_Iter>
> +      operator()(_Iter __first, _Sent __last, const T& __value, _Proj __proj = {}) const
> +      {
> +       if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>)
> +         {
> +           _Iter __found = ranges::find(reverse_iterator<_Iter>{__last},
> +                                        reverse_iterator<_Iter>{__first},
> +                                        __value, __proj).base();
> +           if (__found == __first)
> +             return {__last, __last};
> +           else
> +             return {ranges::prev(__found), __last};
> +         }
> +       else
> +         {
> +           _Iter __found = ranges::find(__first, __last, __value, __proj);

std::move(__proj) here too, for consistency.

> +           if (__found == __last)
> +             return {__found, __found};
> +           for (;;)
> +             {
> +               __first = ranges::find(ranges::next(__first), __last, __value, __proj);

And here.

> +               if (__first == __last)
> +                 return {__found, __first};
> +               __found = __first;
> +             }
> +         }
> +      }
> +
> +    template<forward_range _Range, typename T, typename _Proj = identity>
> +      requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>, const T*>
> +      constexpr borrowed_subrange_t<_Range>
> +      operator()(_Range&& __r, const T& __value, _Proj __proj = {}) const
> +      { return (*this)(ranges::begin(__r), ranges::end(__r), __value, std::move(__proj)); }
> +  };
> +
> +  inline constexpr __find_last_fn find_last{};
> +
> +  struct __find_last_if_fn
> +  {
> +    template<forward_iterator _Iter, sentinel_for<_Iter> _Sent, typename _Proj = identity,
> +            indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>
> +      constexpr subrange<_Iter>
> +      operator()(_Iter __first, _Sent __last, _Pred __pred, _Proj __proj = {}) const
> +      {
> +       if constexpr (same_as<_Iter, _Sent> && bidirectional_iterator<_Iter>)
> +         {
> +           _Iter __found = ranges::find_if(reverse_iterator<_Iter>{__last},
> +                                           reverse_iterator<_Iter>{__first},
> +                                           __pred, __proj).base();

And here, and std::move(__pred) too, I think.

OK for trunk with those changes here (and the later cases).