[libc++][ranges] Implement `ranges::nth_element`.

[var-const]

Use the actual patch number.

[var-const]

libcxx/include/__algorithm/nth_element.h

40

The ABI annotation was missing.

[var-const]

Rebase on main.

[philnik]

libcxx/include/__algorithm/nth_element.h

28

Could you do the whitespace formatting in a different patch?

libcxx/include/__algorithm/ranges_nth_element.h

47

libcxx/test/std/algorithms/alg.sorting/alg.nth.element/ranges_nth_element.pass.cpp

73

I don't think we should do that. It's quite fragile and we even have _LIBCPP_DEBUG_RANDOMIZE_RANGE to avoid that users depend on the exact output.

147

196

Descending?

247

I don't think this should be here.

276

Also this.

[ldionne]

All in all, LGTM with some comments.

You should poke the CI.

libcxx/include/__algorithm/nth_element.h

28

+1, it'll make it possible to ignore it for git blame. We should really strive to do these mostly-whitespace changes in NFC patches, otherwise we'll destroy our ability to git blame, and we'll pay for that in the future.

libcxx/test/std/algorithms/alg.sorting/alg.nth.element/ranges_nth_element.pass.cpp

73

I agree. I think this is going to be brittle if we make changes to our algorithms. Also, if you remove this, you can (and should) still check that the value of the nth element is as expected (i.e. instead of passing an expected array, you can pass an expected value (or iterator to validate the position)).

165–169

IMO this is a bit complicated, we could instead just manually call test_all_cases with each (input, n, expected) combination. And that would allow getting rid of the array<array<...>> overload of test_all_cases, which I had to pause quite a bit on.

215

Instead of having multiple test_iterator_n functions, I would do something like this (IMO it localizes things which makes it more obvious where they are used):

constexpr void test_iterators() {
  auto check = []<class Iter, class Sent> {
    // all checks
  };

  check.operator()<random_access_iterator<int*>, random_access_iterator<int*>>();
  check.operator()<random_access_iterator<int*>, sentinel_wrapper<random_access_iterator<int*>>>();

  // etc.
}

If you dislike the lambda, you could define it as a function template named e.g. test_iterators_impl, but the point here is to make it obvious that it's only an implementation detail of test_iterators. Otherwise, I'd have to check whether test_iterators_1 is somehow called from elsewhere in the file, and whether that might be the reason for giving it a "global" name.

[huixie90]

libcxx/include/__algorithm/nth_element.h

76

similar for other reiviews, ranges overload require the implementation to use iter_move and iter_swap

159

ranges overload needs to use iter_swap. same for the rest of swaps

[var-const]

Address feedback.

libcxx/include/__algorithm/nth_element.h

76

Thanks a lot for finding this issue! Will fix in a follow-up.

159

Same as the other comment -- will fix in a follow-up.

libcxx/test/std/algorithms/alg.sorting/alg.nth.element/ranges_nth_element.pass.cpp

73

Thanks, this makes the tests way less verbose. Rather than passing values explicitly, it seems easier to create a copy of the input and sort it, then compare the nth elements between the partially-sorted and fully-sorted sequences.

165–169

(no longer applies now that we're not checking for the exact output)

247

Same as the other review -- this is necessary to compare the value of the nth element.

276

(see the other comment)

[var-const]

Fix the CI.

[var-const]

• Don't randomize the range if nth == last -- otherwise, the function isn't a no-op;
• rebase on main.

[var-const]

libcxx/include/__algorithm/nth_element.h

238

I think this condition is necessary -- otherwise, the function isn't a no-op when __nth == __last. The standard doesn't say it should be a no-op explicitly, but nevertheless, it seems strange to have a call to nth_element(vector.begin(), vector.end(), vector.end()); reshuffle the vector.

[var-const]

Fix wrong interval

[var-const]

Fix the interval.

[huixie90]

libcxx/include/__algorithm/nth_element.h

242

question: why do we need inline in these function templates?

[var-const]

Fix the CI.

[var-const]

Rebase on main.

libcxx/docs/Status/RangesAlgorithms.csv

 Permutation,rotate,Nikolas Klauser,`D124122 <https://llvm.org/D124122>`_,Under review
 Permutation,shuffle,Not assigned,n/a,Not started
 Permutation,unique,Not assigned,n/a,Not started
 Permutation,partition,Not assigned,n/a,Not started
 Permutation,stable_partition,Not assigned,n/a,Not started
 Permutation,sort,Konstantin Varlamov,`D127557 <https://llvm.org/D127557>`_,✅
 Permutation,stable_sort,Konstantin Varlamov,`D127834 <https://llvm.org/D127834>`_,✅
 Permutation,partial_sort,Konstantin Varlamov,n/a,In progress
-Permutation,nth_element,Not assigned,n/a,Not started
+Permutation,nth_element,Konstantin Varlamov,`D128149 <https://llvm.org/D128149>`_,✅
 Permutation,inplace_merge,Not assigned,n/a,Not started
 Permutation,make_heap,Not assigned,n/a,Not started
 Permutation,push_heap,Not assigned,n/a,Not started
 Permutation,pop_heap,Not assigned,n/a,Not started
 Permutation,sort_heap,Not assigned,n/a,Not started
 Permutation,prev_permutation,Not assigned,n/a,Not started
 Permutation,next_permutation,Not assigned,n/a,Not started
 Uninitialised memory,uninitialized_copy,Konstantin Varlamov,`D116023 <https://llvm.org/D116023>`_,✅

libcxx/include/CMakeLists.txt

set(files
   __algorithm/ranges_min.h
   __algorithm/ranges_min_element.h
   __algorithm/ranges_minmax.h
   __algorithm/ranges_minmax_element.h
   __algorithm/ranges_mismatch.h
   __algorithm/ranges_move.h
   __algorithm/ranges_move_backward.h
   __algorithm/ranges_none_of.h
+  __algorithm/ranges_nth_element.h
   __algorithm/ranges_remove.h
   __algorithm/ranges_remove_if.h
   __algorithm/ranges_replace.h
   __algorithm/ranges_replace_if.h
   __algorithm/ranges_reverse.h
   __algorithm/ranges_set_difference.h
   __algorithm/ranges_sort.h
   __algorithm/ranges_stable_sort.h

libcxx/include/__algorithm/nth_element.h

 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/sort.h>
 #include <__config>
 #include <__debug>
 #include <__debug_utils/randomize_range.h>
 #include <__iterator/iterator_traits.h>
+#include <__utility/move.h>
 #include <__utility/swap.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template<class _Compare, class _RandomAccessIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX11 bool
 __nth_element_find_guard(_RandomAccessIterator& __i, _RandomAccessIterator& __j,
                          _RandomAccessIterator __m, _Compare __comp)
 {
     // manually guard downward moving __j against __i
     while (true) {
         if (__i == --__j) {
             return false;
         }
         if (__comp(*__j, *__m)) {
             return true;  // found guard for downward moving __j, now use unguarded partition
         }
     }
 }
 
 template <class _Compare, class _RandomAccessIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX11 void
 __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
 {
     // _Compare is known to be a reference type
while (true)
             _VSTD::__sort3<_Compare>(__first, ++__m, --__last, __comp);
             return;
             }
         }
         if (__len <= __limit)
         {
             _VSTD::__selection_sort<_Compare>(__first, __last, __comp);
             return;
         }
         // __len > __limit >= 3
         _RandomAccessIterator __m = __first + __len/2;
         _RandomAccessIterator __lm1 = __last;
         unsigned __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, --__lm1, __comp);
         // *__m is median
         // partition [__first, __m) < *__m and *__m <= [__m, __last)
         // (this inhibits tossing elements equivalent to __m around unnecessarily)
         _RandomAccessIterator __i = __first;
while (true)
                 while (!__comp(*--__j, *__m))
                     ;
                 if (__i >= __j)
                     break;
                 swap(*__i, *__j);
                 ++__n_swaps;
                 // It is known that __m != __j
                 // If __m just moved, follow it
                 if (__m == __i)
                     __m = __j;
                 ++__i;
             }
         }
         // [__first, __i) < *__m and *__m <= [__i, __last)
         if (__i != __m && __comp(*__m, *__i))
         {
             swap(*__i, *__m);
while (true)
         {
             // _VSTD::__nth_element<_Compare>(__i+1, __nth, __last, __comp);
             __first = ++__i;
         }
     }
 }
 
 template <class _RandomAccessIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-void
-nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp)
-{
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+void __nth_element_impl(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last,
+                        _Compare& __comp) {
+  if (__nth == __last)
+    return;
+
   std::__debug_randomize_range(__first, __last);
-  typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-  _VSTD::__nth_element<_Comp_ref>(__first, __nth, __last, __comp);
+
+  using _Comp_ref = typename __comp_ref_type<_Compare>::type;
+  std::__nth_element<_Comp_ref>(__first, __nth, __last, __comp);
+
   std::__debug_randomize_range(__first, __nth);
   if (__nth != __last) {
     std::__debug_randomize_range(++__nth, __last);
   }
 }
 
+template <class _RandomAccessIterator, class _Compare>
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+void nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last,
+                 _Compare __comp) {
+  std::__nth_element_impl(std::move(__first), std::move(__nth), std::move(__last), __comp);
+}
+
 template <class _RandomAccessIterator>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-void
-nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last)
-{
-    _VSTD::nth_element(__first, __nth, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+void nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last) {
+  std::nth_element(std::move(__first), std::move(__nth), std::move(__last), __less<typename
+      iterator_traits<_RandomAccessIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_NTH_ELEMENT_H

libcxx/include/__algorithm/ranges_nth_element.h

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP___ALGORITHM_RANGES_NTH_ELEMENT_H
+#define _LIBCPP___ALGORITHM_RANGES_NTH_ELEMENT_H
+
+#include <__algorithm/make_projected.h>
+#include <__algorithm/nth_element.h>
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/iterator_traits.h>
+#include <__iterator/next.h>
+#include <__iterator/projected.h>
+#include <__iterator/sortable.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+#include <__utility/forward.h>
+#include <__utility/move.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+namespace __nth_element {
+
+struct __fn {
+  template <class _Iter, class _Sent, class _Comp, class _Proj>
+  _LIBCPP_HIDE_FROM_ABI constexpr static
+  _Iter __nth_element_fn_impl(_Iter __first, _Iter __nth, _Sent __last, _Comp& __comp, _Proj& __proj) {
+    auto __last_iter = ranges::next(__first, __last);
+
+    auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
+    std::__nth_element_impl(std::move(__first), std::move(__nth), __last_iter, __projected_comp);
+
+    return __last_iter;
+  }
+
+  template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity>
+    requires sortable<_Iter, _Comp, _Proj>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  _Iter operator()(_Iter __first, _Iter __nth, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {
+    return __nth_element_fn_impl(std::move(__first), std::move(__nth), std::move(__last), __comp, __proj);
+  }
+
+  template <random_access_range _Range, class _Comp = ranges::less, class _Proj = identity>
+    requires sortable<iterator_t<_Range>, _Comp, _Proj>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  borrowed_iterator_t<_Range> operator()(_Range&& __r, iterator_t<_Range> __nth, _Comp __comp = {},
+                                         _Proj __proj = {}) const {
+    return __nth_element_fn_impl(ranges::begin(__r), std::move(__nth), ranges::end(__r), __comp, __proj);
+  }
+};
+
+} // namespace __nth_element
+
+inline namespace __cpo {
+  inline constexpr auto nth_element = __nth_element::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_NTH_ELEMENT_H

libcxx/include/algorithm

template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
            indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
     constexpr I ranges::is_sorted_until(I first, S last, Comp comp = {}, Proj proj = {});   // since C++20
 
   template<forward_range R, class Proj = identity,
            indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
     constexpr borrowed_iterator_t<R>
       ranges::is_sorted_until(R&& r, Comp comp = {}, Proj proj = {});                       // since C++20
 
+  template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+          class Proj = identity>
+    requires sortable<I, Comp, Proj>
+    constexpr I
+      ranges::nth_element(I first, I nth, S last, Comp comp = {}, Proj proj = {});            // since C++20
+
+  template<random_access_range R, class Comp = ranges::less, class Proj = identity>
+    requires sortable<iterator_t<R>, Comp, Proj>
+    constexpr borrowed_iterator_t<R>
+      ranges::nth_element(R&& r, iterator_t<R> nth, Comp comp = {}, Proj proj = {});          // since C++20
+
   template<forward_iterator I, sentinel_for<I> S, class T, class Proj = identity,
            indirect_strict_weak_order<const T*, projected<I, Proj>> Comp = ranges::less>
     constexpr I upper_bound(I first, S last, const T& value, Comp comp = {}, Proj proj = {}); // since C++20
 
   template<forward_range R, class T, class Proj = identity,
            indirect_strict_weak_order<const T*, projected<iterator_t<R>, Proj>> Comp =
              ranges::less>
     constexpr borrowed_iterator_t<R>

 #include <__algorithm/ranges_min.h>
 #include <__algorithm/ranges_min_element.h>
 #include <__algorithm/ranges_minmax.h>
 #include <__algorithm/ranges_minmax_element.h>
 #include <__algorithm/ranges_mismatch.h>
 #include <__algorithm/ranges_move.h>
 #include <__algorithm/ranges_move_backward.h>
 #include <__algorithm/ranges_none_of.h>
+#include <__algorithm/ranges_nth_element.h>
 #include <__algorithm/ranges_remove.h>
 #include <__algorithm/ranges_remove_if.h>
 #include <__algorithm/ranges_replace.h>
 #include <__algorithm/ranges_replace_if.h>
 #include <__algorithm/ranges_reverse.h>
 #include <__algorithm/ranges_set_difference.h>
 #include <__algorithm/ranges_sort.h>
 #include <__algorithm/ranges_stable_sort.h>

libcxx/include/module.modulemap.in

module __algorithm {
       module ranges_min                      { private header "__algorithm/ranges_min.h" }
       module ranges_min_element              { private header "__algorithm/ranges_min_element.h" }
       module ranges_minmax                   { private header "__algorithm/ranges_minmax.h" }
       module ranges_minmax_element           { private header "__algorithm/ranges_minmax_element.h" }
       module ranges_mismatch                 { private header "__algorithm/ranges_mismatch.h" }
       module ranges_move                     { private header "__algorithm/ranges_move.h" }
       module ranges_move_backward            { private header "__algorithm/ranges_move_backward.h" }
       module ranges_none_of                  { private header "__algorithm/ranges_none_of.h" }
+      module ranges_nth_element              { private header "__algorithm/ranges_nth_element.h" }
       module ranges_remove                   { private header "__algorithm/ranges_remove.h" }
       module ranges_remove_if                { private header "__algorithm/ranges_remove_if.h" }
       module ranges_replace                  { private header "__algorithm/ranges_replace.h" }
       module ranges_replace_if               { private header "__algorithm/ranges_replace_if.h" }
       module ranges_reverse                  { private header "__algorithm/ranges_reverse.h" }
       module ranges_set_difference           { private header "__algorithm/ranges_set_difference.h" }
       module ranges_sort                     { private header "__algorithm/ranges_sort.h" }
       module ranges_stable_sort              { private header "__algorithm/ranges_stable_sort.h" }

libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp

#endif
     (void)std::ranges::minmax_element(first, last, Less(&copies)); assert(copies == 0);
     (void)std::ranges::minmax_element(a, Less(&copies)); assert(copies == 0);
     (void)std::ranges::mismatch(first, last, first2, last2, Equal(&copies)); assert(copies == 0);
     (void)std::ranges::mismatch(a, b, Equal(&copies)); assert(copies == 0);
     //(void)std::ranges::next_permutation(first, last, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::next_permutation(a, Less(&copies)); assert(copies == 0);
     (void)std::ranges::none_of(first, last, UnaryTrue(&copies)); assert(copies == 0);
     (void)std::ranges::none_of(a, UnaryTrue(&copies)); assert(copies == 0);
-    //(void)std::ranges::nth_element(first, mid, last, Less(&copies)); assert(copies == 0);
-    //(void)std::ranges::nth_element(a, mid, Less(&copies)); assert(copies == 0);
+    (void)std::ranges::nth_element(first, mid, last, Less(&copies)); assert(copies == 0);
+    (void)std::ranges::nth_element(a, mid, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::partial_sort(first, mid, last, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::partial_sort(a, mid, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::partial_sort_copy(first, last, first2, mid2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::partial_sort_copy(a, b, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::partition(first, last, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::partition(a, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::partition_copy(first, last, first2, last2, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::partition_copy(a, first2, last2, UnaryTrue(&copies)); assert(copies == 0);

libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp

#endif
     (void)std::ranges::minmax_element(first, last, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::minmax_element(a, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::mismatch(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::mismatch(a, b, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::next_permutation(first, last, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::next_permutation(a, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::none_of(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::none_of(a, UnaryTrue(), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::nth_element(first, mid, last, Less(), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::nth_element(a, mid, Less(), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::nth_element(first, mid, last, Less(), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::nth_element(a, mid, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::partial_sort(first, mid, last, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::partial_sort(a, mid, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::partial_sort_copy(first, last, first2, mid2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::partial_sort_copy(a, b, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::partition(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::partition(a, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::partition_copy(first, last, first2, last2, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::partition_copy(a, first2, last2, UnaryTrue(), Proj(&copies)); assert(copies == 0);

libcxx/test/libcxx/private_headers.verify.cpp

 #include <__algorithm/ranges_min.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_min.h'}}
 #include <__algorithm/ranges_min_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_min_element.h'}}
 #include <__algorithm/ranges_minmax.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_minmax.h'}}
 #include <__algorithm/ranges_minmax_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_minmax_element.h'}}
 #include <__algorithm/ranges_mismatch.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_mismatch.h'}}
 #include <__algorithm/ranges_move.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_move.h'}}
 #include <__algorithm/ranges_move_backward.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_move_backward.h'}}
 #include <__algorithm/ranges_none_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_none_of.h'}}
+#include <__algorithm/ranges_nth_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_nth_element.h'}}
 #include <__algorithm/ranges_remove.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_remove.h'}}
 #include <__algorithm/ranges_remove_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_remove_if.h'}}
 #include <__algorithm/ranges_replace.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_replace.h'}}
 #include <__algorithm/ranges_replace_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_replace_if.h'}}
 #include <__algorithm/ranges_reverse.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_reverse.h'}}
 #include <__algorithm/ranges_set_difference.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_set_difference.h'}}
 #include <__algorithm/ranges_sort.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_sort.h'}}
 #include <__algorithm/ranges_stable_sort.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_stable_sort.h'}}

libcxx/test/std/algorithms/alg.sorting/alg.nth.element/ranges_nth_element.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// <algorithm>
+
+// template<random_­access_­iterator I, sentinel_­for<I> S, class Comp = ranges::less,
+//         class Proj = identity>
+//   requires sortable<I, Comp, Proj>
+//   constexpr I
+//     ranges::nth_element(I first, I nth, S last, Comp comp = {}, Proj proj = {});            // since C++20
+//
+// template<random_­access_­range R, class Comp = ranges::less, class Proj = identity>
+//   requires sortable<iterator_t<R>, Comp, Proj>
+//   constexpr borrowed_iterator_t<R>
+//     ranges::nth_element(R&& r, iterator_t<R> nth, Comp comp = {}, Proj proj = {});          // since C++20
+
+#include <algorithm>
+#include <array>
+#include <concepts>
+#include <functional>
+#include <iterator>
+#include <optional>
+#include <ranges>
+
+#include "almost_satisfies_types.h"
+#include "boolean_testable.h"
+#include "test_iterators.h"
+
+// SFINAE tests.
+
+using BadComparator = ComparatorNotCopyable<int*>;
+static_assert(!std::sortable<int*, BadComparator>);
+
+template <class Iter, class Sent = sentinel_wrapper<Iter>, class Comp = std::ranges::less>
+concept HasNthElementIt = requires(Iter first, Iter nth, Sent last, Comp comp) {
+  std::ranges::nth_element(first, nth, last, comp);
+};
+
+static_assert(HasNthElementIt<int*>);
+static_assert(!HasNthElementIt<RandomAccessIteratorNotDerivedFrom>);
+static_assert(!HasNthElementIt<RandomAccessIteratorBadIndex>);
+static_assert(!HasNthElementIt<int*, SentinelForNotSemiregular>);
+static_assert(!HasNthElementIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
+static_assert(!HasNthElementIt<int*, int*, BadComparator>);
+static_assert(!HasNthElementIt<const int*>); // Doesn't satisfy `sortable`.
+
+template <class Range, class Comp = std::ranges::less>
+concept HasNthElementR = requires(Range range, std::ranges::iterator_t<Range> nth, Comp comp) {
+  std::ranges::nth_element(range, nth, comp);
+};
+
+static_assert(HasNthElementR<UncheckedRange<int*>>);
+static_assert(!HasNthElementR<RandomAccessRangeNotDerivedFrom>);
+static_assert(!HasNthElementR<RandomAccessRangeBadIndex>);
+static_assert(!HasNthElementR<UncheckedRange<int*, SentinelForNotSemiregular>>);
+static_assert(!HasNthElementR<UncheckedRange<int*, SentinelForNotWeaklyEqualityComparableWith>>);
+static_assert(!HasNthElementR<UncheckedRange<int*>, BadComparator>);
+static_assert(!HasNthElementR<UncheckedRange<const int*>>); // Doesn't satisfy `sortable`.
+
+template <size_t N, class T, class Iter>
+constexpr void verify_nth(const std::array<T, N>& partially_sorted, size_t nth_index, Iter last, T expected_nth) {
+  // Note that the exact output of `nth_element` is unspecified and may vary between implementations.
+
+  assert(base(last) == partially_sorted.end());
+
+  auto b = partially_sorted.begin();
+  auto nth = b + nth_index;
+  auto e = partially_sorted.end();
+  if (nth == e)
+    return;
+
+  assert(*nth == expected_nth);
+
+  // All elements on the left are <= nth.
+  assert(std::all_of(b, nth, [&](const auto& v) { return v <= *nth; }));
+  // All elements on the right are >= nth.
+  assert(std::all_of(nth, e, [&](const auto& v) { return v >= *nth; }));
+
+  {
+    auto sorted = partially_sorted;
+    std::ranges::sort(sorted);
+
+    // The element at index `n` is the same as if the range were fully sorted.
+    assert(sorted[nth_index] == *nth);
+  }
+}
+
+template <class Iter, class Sent, size_t N>
+constexpr void test_one(std::array<int, N> input, size_t nth_index, std::optional<int> expected_nth = {}) {
+  assert(expected_nth || nth_index == N);
+
+  { // (iterator, sentinel) overload.
+    auto partially_sorted = input;
+    auto b = Iter(partially_sorted.data());
+    auto nth = b + nth_index;
+    auto e = Sent(Iter(partially_sorted.data() + partially_sorted.size()));
+
+    std::same_as<Iter> decltype(auto) last = std::ranges::nth_element(b, nth, e);
+    if (nth_index != N) {
+      verify_nth(partially_sorted, nth_index, last, *expected_nth);
+    } else {
+      assert(partially_sorted == input);
+    }
+  }
+
+  { // (range) overload.
+    auto partially_sorted = input;
+    auto b = Iter(partially_sorted.data());
+    auto nth = b + nth_index;
+    auto e = Sent(Iter(partially_sorted.data() + partially_sorted.size()));
+    auto range = std::ranges::subrange(b, e);
+
+    std::same_as<Iter> decltype(auto) last = std::ranges::nth_element(range, nth);
+    if (nth_index != N) {
+      verify_nth(partially_sorted, nth_index, last, *expected_nth);
+    } else {
+      assert(partially_sorted == input);
+    }
+  }
+}
+
+template <class Iter, class Sent, size_t N>
+constexpr void test_all_cases(std::array<int, N> input) {
+  auto sorted = input;
+  std::sort(sorted.begin(), sorted.end());
+
+  for (int n = 0; n != N; ++n) {
+    test_one<Iter, Sent, N>(input, n, sorted[n]);
+  }
+  test_one<Iter, Sent, N>(input, N);
+}
+
+constexpr void test_iterators() {
+  auto check = []<class Iter, class Sent> {
+    // Empty sequence.
+    test_one<Iter, Sent, 0>({}, 0);
+
+    // 1-element sequence.
+    test_all_cases<Iter, Sent>(std::array{1});
+
+    // 2-element sequence.
+    test_all_cases<Iter, Sent>(std::array{2, 1});
+
+    // 3-element sequence.
+    test_all_cases<Iter, Sent>(std::array{2, 1, 3});
+
+    // Longer sequence.
+    test_all_cases<Iter, Sent>(std::array{2, 1, 3, 6, 8, 4, 11, 5});
+
+    // Longer sequence with duplicates.
+    test_all_cases<Iter, Sent>(std::array{2, 1, 3, 6, 2, 8, 6});
+
+    // All elements are the same.
+    test_all_cases<Iter, Sent>(std::array{1, 1, 1, 1});
+
+    { // nth element is in the right place.
+      std::array input = {6, 5, 3, 1, 4, 2};
+      constexpr size_t N = input.size();
+      test_one<Iter, Sent, N>(input, 2, /*expected_nth=*/3);
+    }
+
+    // Already sorted.
+    test_all_cases<Iter, Sent>(std::array{1, 2, 3, 4, 5, 6});
+
+    // Descending.
+    test_all_cases<Iter, Sent>(std::array{6, 5, 4, 3, 2, 1});
+
+    // Repeating pattern.
+    test_all_cases<Iter, Sent>(std::array{2, 1, 2, 1, 2, 1});
+  };
+
+  check.operator()<random_access_iterator<int*>, random_access_iterator<int*>>();
+  check.operator()<random_access_iterator<int*>, sentinel_wrapper<random_access_iterator<int*>>>();
+  check.operator()<contiguous_iterator<int*>, contiguous_iterator<int*>>();
+  check.operator()<contiguous_iterator<int*>, sentinel_wrapper<contiguous_iterator<int*>>>();
+  check.operator()<int*, int*>();
+  check.operator()<int*, sentinel_wrapper<int*>>();
+}
+
+constexpr bool test() {
+  test_iterators();
+
+  { // A custom comparator works.
+    const std::array input = {1, 2, 3, 4, 5};
+    std::ranges::greater comp;
+
+    {
+      auto in = input;
+      auto last = std::ranges::nth_element(in.begin(), in.begin() + 1, in.end(), comp);
+      assert(in[1] == 4);
+      assert(last == in.end());
+    }
+
+    {
+      auto in = input;
+      auto last = std::ranges::nth_element(in, in.begin() + 1, comp);
+      assert(in[1] == 4);
+      assert(last == in.end());
+    }
+  }
+
+  { // A custom projection works.
+    struct A {
+      int a;
+      constexpr bool operator==(const A&) const = default;
+    };
+
+    const std::array input = {A{2}, A{1}, A{3}};
+
+    {
+      auto in = input;
+      auto last = std::ranges::nth_element(in.begin(), in.begin() + 1, in.end(), {}, &A::a);
+      assert(in[1] == A{2});
+      assert(last == in.end());
+    }
+
+    {
+      auto in = input;
+      auto last = std::ranges::nth_element(in, in.begin() + 1, {}, &A::a);
+      assert(in[1] == A{2});
+      assert(last == in.end());
+    }
+  }
+
+  { // `std::invoke` is used in the implementation.
+    struct S {
+      int i;
+      constexpr S(int i_) : i(i_) {}
+
+      constexpr bool comparator(const S& rhs) const { return i < rhs.i; }
+      constexpr const S& projection() const { return *this; }
+
+      constexpr bool operator==(const S&) const = default;
+    };
+
+    const std::array input = {S{2}, S{1}, S{3}};
+
+    {
+      auto in = input;
+      auto last = std::ranges::nth_element(in.begin(), in.begin() + 1, in.end(), &S::comparator, &S::projection);
+      assert(in[1] == S{2});
+      assert(last == in.end());
+    }
+
+    {
+      auto in = input;
+      auto last = std::ranges::nth_element(in, in.begin() + 1, &S::comparator, &S::projection);
+      assert(in[1] == S{2});
+      assert(last == in.end());
+    }
+  }
+
+  { // The comparator can return any type that's convertible to `bool`.
+    const std::array input = {2, 1, 3};
+    auto pred = [](int i, int j) { return BooleanTestable{i < j}; };
+
+    {
+      std::array in = input;
+      auto last = std::ranges::nth_element(in.begin(), in.begin() + 1, in.end(), pred);
+      assert(in[1] == 2);
+      assert(last == in.end());
+    }
+
+    {
+      std::array in = input;
+      auto last = std::ranges::nth_element(in, in.begin() + 1, pred);
+      assert(in[1] == 2);
+      assert(last == in.end());
+    }
+  }
+
+  { // `std::ranges::dangling` is returned.
+    std::array in{1, 2, 3};
+    [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) result =
+        std::ranges::nth_element(std::move(in), in.begin());
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp

 static_assert(test(std::ranges::min_element, a));
 static_assert(test(std::ranges::minmax, a));
 static_assert(test(std::ranges::minmax_element, a));
 static_assert(test(std::ranges::mismatch, a, a));
 static_assert(test(std::ranges::move, a, a));
 static_assert(test(std::ranges::move_backward, a, a));
 //static_assert(test(std::ranges::next_permutation, a));
 static_assert(test(std::ranges::none_of, a, odd));
-//static_assert(test(std::ranges::nth_element, a, a+5));
+static_assert(test(std::ranges::nth_element, a, a+5));
 //static_assert(test(std::ranges::partial_sort, a, a+5));
 //static_assert(test(std::ranges::partial_sort_copy, a, a));
 //static_assert(test(std::ranges::partition, a, odd));
 //static_assert(test(std::ranges::partition_copy, a, a, a, odd));
 //static_assert(test(std::ranges::partition_point, a, odd));
 //static_assert(test(std::ranges::pop_heap, a));
 //static_assert(test(std::ranges::prev_permutation, a));
 //static_assert(test(std::ranges::push_heap, a));