PR libstdc++/100795
libstdc++-v3/ChangeLog:
* include/bits/ranges_algo.h (__detail::__introselect): New,
based on the stl_algo.h implementation.
(nth_element_fn::operator()): Reimplement in terms of the above.
* testsuite/25_algorithms/nth_element/constrained.cc:
---
libstdc++-v3/include/bits/ranges_algo.h | 47 +++++++++++++++++--
.../25_algorithms/nth_element/constrained.cc | 31 ++++++++++++
2 files changed, 73 insertions(+), 5 deletions(-)
diff --git a/libstdc++-v3/include/bits/ranges_algo.h
b/libstdc++-v3/include/bits/ranges_algo.h
index a9924cd9c49e..b12da2af1263 100644
--- a/libstdc++-v3/include/bits/ranges_algo.h
+++ b/libstdc++-v3/include/bits/ranges_algo.h
@@ -2805,6 +2805,33 @@ namespace ranges
inline constexpr __is_sorted_fn is_sorted{};
+ namespace __detail
+ {
+ template<typename _Iter, typename _Comp>
+ constexpr void
+ __introselect(_Iter __first, _Iter __nth, _Iter __last,
+ iter_difference_t<_Iter> __depth_limit, _Comp __comp)
+ {
+ while (__last - __first > 3)
+ {
+ if (__depth_limit == 0)
+ {
+ __detail::__heap_select(__first, __nth + 1, __last, __comp);
+ // Place the nth largest element in its final position.
+ ranges::iter_swap(__first, __nth);
+ return;
+ }
+ --__depth_limit;
+ _Iter __cut = __detail::__unguarded_partition_pivot(__first,
__last, __comp);
+ if (__cut <= __nth)
+ __first = __cut;
+ else
+ __last = __cut;
+ }
+ __detail::__insertion_sort(__first, __last, __comp);
+ }
+ } // namespace __detail
+
struct __nth_element_fn
{
template<random_access_iterator _Iter, sentinel_for<_Iter> _Sent,
@@ -2814,11 +2841,21 @@ namespace ranges
operator()(_Iter __first, _Iter __nth, _Sent __last,
_Comp __comp = {}, _Proj __proj = {}) const
{
- auto __lasti = ranges::next(__first, __last);
- _GLIBCXX_STD_A::nth_element(std::move(__first), std::move(__nth),
- __lasti,
- __detail::__make_comp_proj(__comp, __proj));
- return __lasti;
+ if constexpr (!same_as<_Iter, _Sent>)
+ return (*this)(__first, __nth, ranges::next(__first, __last),
+ std::move(__comp), std::move(__proj));
+ else
+ {
+ if (__first == __last || __nth == __last)
+ return __last;
+
+ auto __comp_proj = __detail::__make_comp_proj(__comp, __proj);
+ auto __n = __detail::__to_unsigned_like(__last - __first);
+ __detail::__introselect(__first, __nth, __last,
+ std::__bit_width(__n) * 2,
+ __comp_proj);
+ return __last;
+ }
}
template<random_access_range _Range,
diff --git a/libstdc++-v3/testsuite/25_algorithms/nth_element/constrained.cc
b/libstdc++-v3/testsuite/25_algorithms/nth_element/constrained.cc
index 3189b225610e..8cb1625dd4d5 100644
--- a/libstdc++-v3/testsuite/25_algorithms/nth_element/constrained.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/nth_element/constrained.cc
@@ -20,6 +20,7 @@
#include <algorithm>
#include <random>
+#include <ranges>
#include <testsuite_hooks.h>
#include <testsuite_iterators.h>
@@ -67,9 +68,39 @@ test02()
return x[3] == 4;
}
+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::nth_element(w, w.begin() + 10);
+ VERIFY( w[10] == 10 );
+
+ ranges::nth_element(w, w.begin() + 5, std::ranges::greater{});
+ VERIFY( w[5] == 19 - 5 );
+
+ ranges::nth_element(w, w.begin() + 15, std::ranges::greater{},
std::negate{});
+ VERIFY( w[15] == 15 );
+
+ return true;
+}
+
int
main()
{
test01();
static_assert(test02());
+ static_assert(test03());
}
--
2.50.0.131.gcf6f63ea6b
