On Fri, 27 Jun 2025 at 15:26, Patrick Palka <ppa...@redhat.com> wrote:
>
> On Fri, 27 Jun 2025, Jonathan Wakely wrote:
>
> > On 26/06/25 22:25 -0400, Patrick Palka wrote:
> > > PR libstdc++/100795
> > >
> > > libstdc++-v3/ChangeLog:
> > >
> > > * include/bits/ranges_algo.h (__detail::__find_if_not_n): New,
> > > based on the stl_algo.h implementation.
> > > (__detail::__stable_partition_adaptive): Likewise.
> > > (__stable_partition_fn::operator()): Reimplement in terms of
> > > the above.
> > > * testsuite/25_algorithms/stable_partition/constrained.cc
> > > (test03): New test.
> > > ---
> > > libstdc++-v3/include/bits/ranges_algo.h | 106 +++++++++++++++++-
> > > .../stable_partition/constrained.cc | 26 +++++
> > > 2 files changed, 127 insertions(+), 5 deletions(-)
> > >
> > > diff --git a/libstdc++-v3/include/bits/ranges_algo.h
> > > b/libstdc++-v3/include/bits/ranges_algo.h
> > > index 7dfd4e7ed64c..a9924cd9c49e 100644
> > > --- a/libstdc++-v3/include/bits/ranges_algo.h
> > > +++ b/libstdc++-v3/include/bits/ranges_algo.h
> > > @@ -3133,6 +3133,81 @@ namespace ranges
> > > inline constexpr __partition_fn partition{};
> > >
> > > #if _GLIBCXX_HOSTED
> > > + namespace __detail
> > > + {
> > > + /// Like find_if_not(), but uses and updates a count of the
> > > + /// remaining range length instead of comparing against an end
> > > + /// iterator.
> > > + template<typename _Iter, typename _Pred, typename _Distance>
> > > + constexpr _Iter
> > > + __find_if_not_n(_Iter __first, _Distance& __len, _Pred __pred)
> > > + {
> > > + for (; __len; --__len, (void) ++__first)
> > > + if (!__pred(*__first))
> > > + break;
> > > + return __first;
> > > + }
> > > +
> > > + template<typename _Iter, typename _Sent, typename _Pointer,
> > > + typename _Pred, typename _Distance>
> > > + _GLIBCXX26_CONSTEXPR
> > > + subrange<_Iter>
> > > + __stable_partition_adaptive(_Iter __first, _Sent __last,
> > > + _Pred __pred, _Distance __len,
> > > + _Pointer __buffer,
> > > + _Distance __buffer_size)
> > > + {
> > > + if (__len == 1)
> > > + return {__first, ranges::next(__first, 1)};
> > > +
> > > + if (__len <= __buffer_size)
> > > + {
> > > + _Iter __result1 = __first;
> > > + _Pointer __result2 = __buffer;
> > > +
> > > + // The precondition guarantees that !__pred(__first), so
> > > + // move that element to the buffer before starting the loop.
> > > + // This ensures that we only call __pred once per element.
> > > + *__result2 = ranges::iter_move(__first);
> > > + ++__result2;
> > > + ++__first;
> > > + for (; __first != __last; ++__first)
> > > + if (__pred(*__first))
> > > + {
> > > + *__result1 = ranges::iter_move(__first);
> > > + ++__result1;
> > > + }
> > > + else
> > > + {
> > > + *__result2 = ranges::iter_move(__first);
> > > + ++__result2;
> > > + }
> > > +
> > > + ranges::move(__buffer, __result2, __result1);
> > > + return {__result1, __first};
> > > + }
> > > +
> > > + _Iter __middle = __first;
> > > + ranges::advance(__middle, __len / 2);
> > > + _Iter __left_split
> > > + = __detail::__stable_partition_adaptive(__first, __middle, __pred,
> > > + __len / 2, __buffer,
> > > + __buffer_size).begin();
> > > +
> > > + // Advance past true-predicate values to satisfy this
> > > + // function's preconditions.
> > > + _Distance __right_len = __len - __len / 2;
> > > + _Iter __right_split = __detail::__find_if_not_n(__middle, __right_len,
> > > __pred);
> > > +
> > > + if (__right_len)
> > > + __right_split
> > > + = __detail::__stable_partition_adaptive(__right_split, __last,
> > > __pred,
> > > + __right_len, __buffer,
> > > __buffer_size).begin();
> > > +
> > > + return ranges::rotate(__left_split, __middle, __right_split);
> > > + }
> > > + } // namespace __detail
> > > +
> > > struct __stable_partition_fn
> > > {
> > > template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
> > > @@ -3144,11 +3219,32 @@ namespace ranges
> > > operator()(_Iter __first, _Sent __last,
> > > _Pred __pred, _Proj __proj = {}) const
> > > {
> > > - auto __lasti = ranges::next(__first, __last);
> > > - auto __middle
> > > - = std::stable_partition(std::move(__first), __lasti,
> > > - __detail::__make_pred_proj(__pred, __proj));
> > > - return {std::move(__middle), std::move(__lasti)};
> > > + auto __pred_proj = __detail::__make_pred_proj(__pred, __proj);
> > > + __first = ranges::find_if_not(__first, __last, __pred_proj);
> >
> > Does this end up going through another layer of
> > invoke(pred, invoke(proj, *i)) inside ranges::find_if_not?
> > Hopeuflly with the recent _Pred_proj changes that will get inlined,
> > but is there any reason to not just use:
> >
> > __first = ranges::find_if_not(__first, __last, __pred, __proj);
> >
> > here, and then use __pred_proj for the __stable_partition_adaptive
> > calls below?
>
> Good catch, that works nicely here (and I think this is the only such
> occurrence of passing a composite predicate/projection to a ranges algo).
> Fixed along with the accidentally Doxygen-style comment (and made
> __stable_partition_adaptive uncoditionally constexpr), like so?
OK for trunk, thanks.
Would it make sense to add a deleted overload of __make_pred_proj to
make it ill-formed to wrap a _Pred_proj in another _Pred_proj?
> Thanks a lot for the reviews!
>
> -- >8 --
>
> Subject: [PATCH 5/8] libstdc++: Directly implement ranges::stable_partition
> [PR100795]
>
> PR libstdc++/100795
>
> libstdc++-v3/ChangeLog:
>
> * include/bits/ranges_algo.h (__detail::__find_if_not_n): New,
> based on the stl_algo.h implementation.
> (__detail::__stable_partition_adaptive): Likewise.
> (__stable_partition_fn::operator()): Reimplement in terms of
> the above.
> * testsuite/25_algorithms/stable_partition/constrained.cc
> (test03): New test.
> ---
> libstdc++-v3/include/bits/ranges_algo.h | 106 +++++++++++++++++-
> .../stable_partition/constrained.cc | 26 +++++
> 2 files changed, 127 insertions(+), 5 deletions(-)
>
> diff --git a/libstdc++-v3/include/bits/ranges_algo.h
> b/libstdc++-v3/include/bits/ranges_algo.h
> index d0d3d92bd52c..a214e03d7b88 100644
> --- a/libstdc++-v3/include/bits/ranges_algo.h
> +++ b/libstdc++-v3/include/bits/ranges_algo.h
> @@ -3133,6 +3133,80 @@ namespace ranges
> inline constexpr __partition_fn partition{};
>
> #if _GLIBCXX_HOSTED
> + namespace __detail
> + {
> + // Like find_if_not(), but uses and updates a count of the
> + // remaining range length instead of comparing against an end
> + // iterator.
> + template<typename _Iter, typename _Pred, typename _Distance>
> + constexpr _Iter
> + __find_if_not_n(_Iter __first, _Distance& __len, _Pred __pred)
> + {
> + for (; __len; --__len, (void) ++__first)
> + if (!__pred(*__first))
> + break;
> + return __first;
> + }
> +
> + template<typename _Iter, typename _Sent, typename _Pointer,
> + typename _Pred, typename _Distance>
> + constexpr subrange<_Iter>
> + __stable_partition_adaptive(_Iter __first, _Sent __last,
> + _Pred __pred, _Distance __len,
> + _Pointer __buffer,
> + _Distance __buffer_size)
> + {
> + if (__len == 1)
> + return {__first, ranges::next(__first, 1)};
> +
> + if (__len <= __buffer_size)
> + {
> + _Iter __result1 = __first;
> + _Pointer __result2 = __buffer;
> +
> + // The precondition guarantees that !__pred(__first), so
> + // move that element to the buffer before starting the loop.
> + // This ensures that we only call __pred once per element.
> + *__result2 = ranges::iter_move(__first);
> + ++__result2;
> + ++__first;
> + for (; __first != __last; ++__first)
> + if (__pred(*__first))
> + {
> + *__result1 = ranges::iter_move(__first);
> + ++__result1;
> + }
> + else
> + {
> + *__result2 = ranges::iter_move(__first);
> + ++__result2;
> + }
> +
> + ranges::move(__buffer, __result2, __result1);
> + return {__result1, __first};
> + }
> +
> + _Iter __middle = __first;
> + ranges::advance(__middle, __len / 2);
> + _Iter __left_split
> + = __detail::__stable_partition_adaptive(__first, __middle, __pred,
> + __len / 2, __buffer,
> + __buffer_size).begin();
> +
> + // Advance past true-predicate values to satisfy this
> + // function's preconditions.
> + _Distance __right_len = __len - __len / 2;
> + _Iter __right_split = __detail::__find_if_not_n(__middle,
> __right_len, __pred);
> +
> + if (__right_len)
> + __right_split
> + = __detail::__stable_partition_adaptive(__right_split, __last,
> __pred,
> + __right_len, __buffer,
> __buffer_size).begin();
> +
> + return ranges::rotate(__left_split, __middle, __right_split);
> + }
> + } // namespace __detail
> +
> struct __stable_partition_fn
> {
> template<bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent,
> @@ -3144,11 +3218,33 @@ namespace ranges
> operator()(_Iter __first, _Sent __last,
> _Pred __pred, _Proj __proj = {}) const
> {
> - auto __lasti = ranges::next(__first, __last);
> - auto __middle
> - = std::stable_partition(std::move(__first), __lasti,
> - __detail::__make_pred_proj(__pred, __proj));
> - return {std::move(__middle), std::move(__lasti)};
> + __first = ranges::find_if_not(__first, __last, __pred, __proj);
> +
> + if (__first == __last)
> + return {__first, __first};
> +
> + using _DistanceType = iter_difference_t<_Iter>;
> + const _DistanceType __len = ranges::distance(__first, __last);
> +
> + auto __pred_proj = __detail::__make_pred_proj(__pred, __proj);
> +
> +#if __glibcxx_constexpr_algorithms >= 202306L // >= C++26
> + if consteval {
> + // Simulate a _Temporary_buffer of length 1:
> + iter_value_t<_Iter> __buf = ranges::iter_move(__first);
> + *__first = std::move(__buf);
> + return __detail::__stable_partition_adaptive(__first, __last,
> + __pred_proj,
> + __len, &__buf,
> + _DistanceType(1));
> + }
> +#endif
> +
> + _Temporary_buffer<_Iter, iter_value_t<_Iter>> __buf(__first,
> ptrdiff_t(__len));
> + return __detail::__stable_partition_adaptive(__first, __last,
> + __pred_proj,
> + __len, __buf.begin(),
> +
> _DistanceType(__buf.size()));
> }
>
> template<bidirectional_range _Range, typename _Proj = identity,
> diff --git
> a/libstdc++-v3/testsuite/25_algorithms/stable_partition/constrained.cc
> b/libstdc++-v3/testsuite/25_algorithms/stable_partition/constrained.cc
> index fc11c6439f9c..4dc267873ae2 100644
> --- a/libstdc++-v3/testsuite/25_algorithms/stable_partition/constrained.cc
> +++ b/libstdc++-v3/testsuite/25_algorithms/stable_partition/constrained.cc
> @@ -21,6 +21,7 @@
> // { dg-require-effective-target hosted }
>
> #include <algorithm>
> +#include <ranges>
> #include <testsuite_hooks.h>
> #include <testsuite_iterators.h>
>
> @@ -70,9 +71,34 @@ test02()
> }
> }
>
> +void
> +test03()
> +{
> + // PR libstdc++/100795 - ranges::stable_partition should not use
> + // std::stable_partition directly
> +#if __SIZEOF_INT128__
> + auto v = std::views::iota(__int128(0), __int128(20));
> +#else
> + auto v = std::views::iota(0ll, 20ll);
> +#endif
> +
> + int storage[20] = {2,5,4,3,1,6,7,9,10,8,11,14,12,13,15,16,18,0,19,17};
> + auto w = v | std::views::transform([&](auto i) -> int& { return
> storage[i]; });
> + using type = decltype(w);
> + using cat =
> std::iterator_traits<std::ranges::iterator_t<type>>::iterator_category;
> + static_assert( std::same_as<cat, std::output_iterator_tag> );
> + static_assert( std::ranges::random_access_range<type> );
> +
> + auto pred = [] (int a) { return a%2==0; };
> + ranges::stable_partition(w, pred);
> + VERIFY( ranges::all_of(w.begin(), w.begin() + 10, pred) );
> + VERIFY( ranges::none_of(w.begin() + 10, w.end(), pred) );
> +}
> +
> int
> main()
> {
> test01();
> test02();
> + test03();
> }
> --
> 2.50.0.131.gcf6f63ea6b
>
>
>
> >
> > > +
> > > + if (__first == __last)
> > > + return {__first, __first};
> > > +
> > > + using _DistanceType = iter_difference_t<_Iter>;
> > > + const _DistanceType __len = ranges::distance(__first, __last);
> > > +
> > > +#if __glibcxx_constexpr_algorithms >= 202306L // >= C++26
> > > + if consteval {
> > > + // Simulate a _Temporary_buffer of length 1:
> > > + iter_value_t<_Iter> __buf = ranges::iter_move(__first);
> > > + *__first = std::move(__buf);
> > > + return __detail::__stable_partition_adaptive(__first, __last,
> > > + __pred_proj,
> > > + __len, &__buf,
> > > + _DistanceType(1));
> > > + }
> > > +#endif
> > > +
> > > + _Temporary_buffer<_Iter, iter_value_t<_Iter>> __buf(__first,
> > > ptrdiff_t(__len));
> > > + return __detail::__stable_partition_adaptive(__first, __last,
> > > + __pred_proj,
> > > + __len, __buf.begin(),
> > > +
> > > _DistanceType(__buf.size()));
> > > }
> > >
> > > template<bidirectional_range _Range, typename _Proj = identity,
> > > diff --git
> > > a/libstdc++-v3/testsuite/25_algorithms/stable_partition/constrained.cc
> > > b/libstdc++-v3/testsuite/25_algorithms/stable_partition/constrained.cc
> > > index fc11c6439f9c..4dc267873ae2 100644
> > > --- a/libstdc++-v3/testsuite/25_algorithms/stable_partition/constrained.cc
> > > +++ b/libstdc++-v3/testsuite/25_algorithms/stable_partition/constrained.cc
> > > @@ -21,6 +21,7 @@
> > > // { dg-require-effective-target hosted }
> > >
> > > #include <algorithm>
> > > +#include <ranges>
> > > #include <testsuite_hooks.h>
> > > #include <testsuite_iterators.h>
> > >
> > > @@ -70,9 +71,34 @@ test02()
> > > }
> > > }
> > >
> > > +void
> > > +test03()
> > > +{
> > > + // PR libstdc++/100795 - ranges::stable_partition should not use
> > > + // std::stable_partition directly
> > > +#if __SIZEOF_INT128__
> > > + auto v = std::views::iota(__int128(0), __int128(20));
> > > +#else
> > > + auto v = std::views::iota(0ll, 20ll);
> > > +#endif
> > > +
> > > + int storage[20] = {2,5,4,3,1,6,7,9,10,8,11,14,12,13,15,16,18,0,19,17};
> > > + auto w = v | std::views::transform([&](auto i) -> int& { return
> > > storage[i]; });
> > > + using type = decltype(w);
> > > + using cat =
> > > std::iterator_traits<std::ranges::iterator_t<type>>::iterator_category;
> > > + static_assert( std::same_as<cat, std::output_iterator_tag> );
> > > + static_assert( std::ranges::random_access_range<type> );
> > > +
> > > + auto pred = [] (int a) { return a%2==0; };
> > > + ranges::stable_partition(w, pred);
> > > + VERIFY( ranges::all_of(w.begin(), w.begin() + 10, pred) );
> > > + VERIFY( ranges::none_of(w.begin() + 10, w.end(), pred) );
> > > +}
> > > +
> > > int
> > > main()
> > > {
> > > test01();
> > > test02();
> > > + test03();
> > > }
> > > --
> > > 2.50.0.131.gcf6f63ea6b
> > >
> > >
> >
> >
>
