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);
+
+ 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
