[PATCH 2/2] libstdc++: Directly implement ranges::sort [PR100795]
Patrick Palka
ppalka@redhat.com
Tue Jun 10 01:04:25 GMT 2025
As with the previous patch, this patch reimplements ranges::sort
directly instead of incorrectly forwarding to std::sort. In addition to
the compatibility changes listed in the previous patch we also:
- use ranges::iter_swap instead of std::iter_swap
- use ranges::move_backward instead of std::move_backward
- use __bit_floor and __to_unsigned_like instead of __lg
We also need to extend std::__lg to support integer-class types.
PR libstdc++/100795
PR libstdc++/118209
libstdc++-v3/ChangeLog:
* include/bits/ranges_algo.h (__detail::__move_median_to_first):
New, based on the stl_algo.h implementation.
(__detail::__unguarded_liner_insert): Likewise.
(__detail::__insertion_sort): Likewise.
(__detail::__sort_threshold): Likewise.
(__detail::__unguarded_insertion_sort): Likewise.
(__detail::__final_insertion_sort): Likewise.
(__detail::__unguarded_partition): Likewise.
(__detail::__unguarded_partition_pivot): Likewise.
(__detail::__heap_select): Likewise.
(__detail::__partial_sort): Likewise.
(__detail::__introsort_loop): Likewise.
(__sort_fn::operator()): Reimplement in terms of the above.
* libstdc++-v3/testsuite/25_algorithms/sort/118209.cc: New test.
* libstdc++-v3/testsuite/25_algorithms/sort/constrained.cc
(test03): New test.
---
libstdc++-v3/include/bits/ranges_algo.h | 210 +++++++++++++++++-
.../testsuite/25_algorithms/sort/118209.cc | 23 ++
.../25_algorithms/sort/constrained.cc | 31 +++
3 files changed, 260 insertions(+), 4 deletions(-)
create mode 100644 libstdc++-v3/testsuite/25_algorithms/sort/118209.cc
diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h
index f84e0c42d76a..67bdf4287241 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -32,6 +32,7 @@
#if __cplusplus > 201703L
+#include <bit> // __bit_floor
#if __cplusplus > 202002L
#include <optional>
#endif
@@ -2166,6 +2167,184 @@ namespace ranges
inline constexpr __is_heap_fn is_heap{};
+ namespace __detail
+ {
+ template<typename _Iter, typename _Comp, typename _Proj>
+ constexpr void
+ __move_median_to_first(_Iter __result, _Iter __a, _Iter __b, _Iter __c,
+ _Comp __comp, _Proj __proj)
+ {
+ if (std::__invoke(__comp,
+ std::__invoke(__proj, *__a),
+ std::__invoke(__proj, *__b)))
+ {
+ if (std::__invoke(__comp,
+ std::__invoke(__proj, *__b),
+ std::__invoke(__proj, *__c)))
+ ranges::iter_swap(__result, __b);
+ else if (std::__invoke(__comp,
+ std::__invoke(__proj, *__a),
+ std::__invoke(__proj, *__c)))
+ ranges::iter_swap(__result, __c);
+ else
+ ranges::iter_swap(__result, __a);
+ }
+ else if (std::__invoke(__comp,
+ std::__invoke(__proj, *__a),
+ std::__invoke(__proj, *__c)))
+ ranges::iter_swap(__result, __a);
+ else if (std::__invoke(__comp,
+ std::__invoke(__proj, *__b),
+ std::__invoke(__proj, *__c)))
+ ranges::iter_swap(__result, __c);
+ else
+ ranges::iter_swap(__result, __b);
+ }
+
+ template<typename _Iter, typename _Comp, typename _Proj>
+ constexpr void
+ __unguarded_linear_insert(_Iter __last, _Comp __comp, _Proj __proj)
+ {
+ iter_value_t<_Iter> __val = ranges::iter_move(__last);
+ _Iter __next = __last;
+ --__next;
+ while (std::__invoke(__comp,
+ std::__invoke(__proj, __val),
+ std::__invoke(__proj, *__next)))
+ {
+ *__last = ranges::iter_move(__next);
+ __last = __next;
+ --__next;
+ }
+ *__last = std::move(__val);
+ }
+
+ template<typename _Iter, typename _Comp, typename _Proj>
+ constexpr void
+ __insertion_sort(_Iter __first, _Iter __last, _Comp __comp, _Proj __proj)
+ {
+ if (__first == __last) return;
+
+ for (_Iter __i = __first + 1; __i != __last; ++__i)
+ {
+ if (std::__invoke(__comp,
+ std::__invoke(__proj, *__i),
+ std::__invoke(__proj, *__first)))
+ {
+ iter_value_t<_Iter> __val = ranges::iter_move(__i);
+ ranges::move_backward(__first, __i, __i + 1);
+ *__first = std::move(__val);
+ }
+ else
+ __detail::__unguarded_linear_insert(__i, __comp, __proj);
+ }
+ }
+
+ template<typename _Iter, typename _Comp, typename _Proj>
+ constexpr void
+ __unguarded_insertion_sort(_Iter __first, _Iter __last,
+ _Comp __comp, _Proj __proj)
+ {
+ for (_Iter __i = __first; __i != __last; ++__i)
+ __detail::__unguarded_linear_insert(__i, __comp, __proj);
+ }
+
+ inline constexpr int __sort_threshold = 16;
+
+ template<typename _Iter, typename _Comp, typename _Proj>
+ constexpr void
+ __final_insertion_sort(_Iter __first, _Iter __last,
+ _Comp __comp, _Proj __proj)
+ {
+ if (__last - __first > __sort_threshold)
+ {
+ __detail::__insertion_sort(__first, __first + __sort_threshold,
+ __comp, __proj);
+ __detail::__unguarded_insertion_sort(__first + __sort_threshold, __last,
+ __comp, __proj);
+ }
+ else
+ __detail::__insertion_sort(__first, __last, __comp, __proj);
+ }
+
+ template<typename _Iter, typename _Comp, typename _Proj>
+ constexpr _Iter
+ __unguarded_partition(_Iter __first, _Iter __last, _Iter __pivot,
+ _Comp __comp, _Proj __proj)
+ {
+ while (true)
+ {
+ while (std::__invoke(__comp,
+ std::__invoke(__proj, *__first),
+ std::__invoke(__proj, *__pivot)))
+ ++__first;
+ --__last;
+ while (std::__invoke(__comp,
+ std::__invoke(__proj, *__pivot),
+ std::__invoke(__proj, *__last)))
+ --__last;
+ if (!(__first < __last))
+ return __first;
+ ranges::iter_swap(__first, __last);
+ ++__first;
+ }
+ }
+
+ template<typename _Iter, typename _Comp, typename _Proj>
+ constexpr _Iter
+ __unguarded_partition_pivot(_Iter __first, _Iter __last,
+ _Comp __comp, _Proj __proj)
+ {
+ _Iter __mid = __first + (__last - __first) / 2;
+ __detail::__move_median_to_first(__first, __first + 1, __mid, __last - 1,
+ __comp, __proj);
+ return __detail::__unguarded_partition(__first + 1, __last, __first,
+ __comp, __proj);
+ }
+
+ template<typename _Iter, typename _Comp, typename _Proj>
+ constexpr void
+ __heap_select(_Iter __first, _Iter __middle, _Iter __last,
+ _Comp __comp, _Proj __proj)
+ {
+ ranges::make_heap(__first, __middle, __comp, __proj);
+ for (_Iter __i = __middle; __i < __last; ++__i)
+ if (std::__invoke(__comp,
+ std::__invoke(__proj, *__i),
+ std::__invoke(__proj, *__first)))
+ __detail::__pop_heap(__first, __middle, __i, __comp, __proj);
+ }
+
+ template<typename _Iter, typename _Compare, typename _Proj>
+ constexpr void
+ __partial_sort(_Iter __first, _Iter __middle, _Iter __last,
+ _Compare __comp, _Proj __proj)
+ {
+ __detail::__heap_select(__first, __middle, __last, __comp, __proj);
+ ranges::sort_heap(__first, __middle, __comp, __proj);
+ }
+
+ template<typename _Iter, typename _Comp, typename _Proj>
+ constexpr void
+ __introsort_loop(_Iter __first, _Iter __last, unsigned __depth_limit,
+ _Comp __comp, _Proj __proj)
+ {
+ while (__last - __first > __sort_threshold)
+ {
+ if (__depth_limit == 0)
+ {
+ __detail::__partial_sort(__first, __last, __last, __comp, __proj);
+ return;
+ }
+ --__depth_limit;
+ _Iter __cut = __detail::__unguarded_partition_pivot(__first, __last,
+ __comp, __proj);
+ __detail::__introsort_loop(__cut, __last, __depth_limit, __comp, __proj);
+ __last = __cut;
+ }
+ }
+ } // namespace __detail
+
struct __sort_fn
{
template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
@@ -2175,10 +2354,33 @@ namespace ranges
operator()(_Iter __first, _Sent __last,
_Comp __comp = {}, _Proj __proj = {}) const
{
- auto __lasti = ranges::next(__first, __last);
- _GLIBCXX_STD_A::sort(std::move(__first), __lasti,
- __detail::__make_comp_proj(__comp, __proj));
- return __lasti;
+ if constexpr (!same_as<_Iter, _Sent>)
+ return (*this)(__first, ranges::next(__first, __last),
+ std::move(__comp), std::move(__proj));
+ else
+ {
+ if (__first != __last)
+ {
+ auto __n = __detail::__to_unsigned_like(__last - __first);
+ unsigned __log_n;
+ if constexpr (is_class_v<iter_difference_t<_Iter>>)
+ {
+ // FIXME: <bit> doesn't handle integer-class types.
+ __log_n = 0;
+ while (__n != 1)
+ {
+ __n >>= 1;
+ ++__log_n;
+ }
+ }
+ else
+ __log_n = std::__bit_floor(__n);
+ __detail::__introsort_loop(__first, __last, __log_n * 2,
+ __comp, __proj);
+ __detail::__final_insertion_sort(__first, __last, __comp, __proj);
+ }
+ return __last;
+ }
}
template<random_access_range _Range,
diff --git a/libstdc++-v3/testsuite/25_algorithms/sort/118209.cc b/libstdc++-v3/testsuite/25_algorithms/sort/118209.cc
new file mode 100644
index 000000000000..6d8fa5fd5966
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/sort/118209.cc
@@ -0,0 +1,23 @@
+// PR libstdc++ - ranges::sort doesn't use iter_move, cannot sort zip of move-only type
+// { dg-do compile { target c++23 } }
+
+#include <algorithm>
+#include <ranges>
+#include <vector>
+
+struct F {
+ int a = -1;
+ explicit F(int d) : a(d) { }
+ F(const F&) = delete;
+ F(F&& o) : a(o.a) { }
+ void operator=(const F&) = delete;
+ F& operator=(F&& o) { return *this; }
+ auto operator<=>(const F&) const = default;
+};
+
+int main () {
+ int a[] = {3,2,1};
+ std::vector<F> v(a, a+3);
+ std::ranges::sort(v); // OK
+ std::ranges::sort(std::views::zip(v, v)); // didn't compile
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/sort/constrained.cc b/libstdc++-v3/testsuite/25_algorithms/sort/constrained.cc
index 82754af96430..930dbd77a376 100644
--- a/libstdc++-v3/testsuite/25_algorithms/sort/constrained.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/sort/constrained.cc
@@ -20,6 +20,7 @@
#include <algorithm>
#include <random>
+#include <ranges>
#include <vector>
#include <testsuite_hooks.h>
#include <testsuite_iterators.h>
@@ -72,9 +73,39 @@ test02()
&& ranges::equal(x, y, {}, &X::i, &X::i));
}
+constexpr bool
+test03()
+{
+ // PR libstdc++/100795 - ranges::sort should not use std::sort 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> );
+
+ ranges::sort(w);
+ VERIFY( ranges::equal(w, v) );
+
+ ranges::sort(w, std::ranges::greater{});
+ VERIFY( ranges::equal(w, v | std::views::reverse) );
+
+ ranges::sort(w, std::ranges::greater{}, std::negate{});
+ VERIFY( ranges::equal(w, v) );
+
+ return true;
+}
+
int
main()
{
test01();
static_assert(test02());
+ static_assert(test03());
}
--
2.50.0.rc1.89.g8db3019401
More information about the Libstdc++
mailing list