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?
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
> >
> >
>
>
