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

[var-const]

Use the actual patch number.

[var-const]

libcxx/include/__algorithm/nth_element.h

32–38

The ABI annotation was missing.

[var-const]

Rebase on main.

[philnik]

libcxx/include/__algorithm/nth_element.h

31

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

31

+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

71

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

97

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

[var-const]

Address feedback.

libcxx/include/__algorithm/nth_element.h

71

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

97

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

239

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

243

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,n/a,In progress
 Permutation,partial_sort,Konstantin Varlamov,n/a,In progress
-Permutation,nth_element,Not assigned,n/a,Not started
+Permutation,nth_element,Konstantin Varlamov,`TODO <https://llvm.org/TODO>`_,Not started
 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_max.h
   __algorithm/ranges_max_element.h
   __algorithm/ranges_min.h
   __algorithm/ranges_min_element.h
   __algorithm/ranges_minmax.h
   __algorithm/ranges_minmax_element.h
   __algorithm/ranges_mismatch.h
   __algorithm/ranges_none_of.h
+  __algorithm/ranges_nth_element.h
   __algorithm/ranges_replace.h
   __algorithm/ranges_replace_if.h
   __algorithm/ranges_reverse.h
   __algorithm/ranges_sort.h
   __algorithm/ranges_swap_ranges.h
   __algorithm/ranges_transform.h
   __algorithm/ranges_upper_bound.h
   __algorithm/remove.h

libcxx/include/__algorithm/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_NTH_ELEMENT_H
 #define _LIBCPP___ALGORITHM_NTH_ELEMENT_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/sort.h>
 #include <__config>
 #include <__debug>
 #include <__iterator/iterator_traits.h>
+#include <__utility/move.h>
 #include <__utility/swap.h>
 
 #if defined(_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY)
 #  include <__algorithm/shuffle.h>
 #endif
 
 #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
-        }
-    }
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+bool __nth_element_find_guard(_RandomAccessIterator& __i, _RandomAccessIterator& __j,
+                              _RandomAccessIterator __m, _Compare __comp) {
 }
 
 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
-    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
-    const difference_type __limit = 7;
-    while (true)
-    {
-        if (__nth == __last)
-            return;
-        difference_type __len = __last - __first;
-        switch (__len)
-        {
-        case 0:
-        case 1:
-            return;
-        case 2:
-            if (__comp(*--__last, *__first))
-                swap(*__first, *__last);
-            return;
-        case 3:
-            {
-            _RandomAccessIterator __m = __first;
-            _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;
-        _RandomAccessIterator __j = __lm1;
-        // j points beyond range to be tested, *__lm1 is known to be <= *__m
-        // The search going up is known to be guarded but the search coming down isn't.
-        // Prime the downward search with a guard.
-        if (!__comp(*__i, *__m))  // if *__first == *__m
-        {
-            // *__first == *__m, *__first doesn't go in first part
-            if (_VSTD::__nth_element_find_guard<_Compare>(__i, __j, __m, __comp)) {
-                swap(*__i, *__j);
-                ++__n_swaps;
-            } else {
-                // *__first == *__m, *__m <= all other elements
-                // Partition instead into [__first, __i) == *__first and *__first < [__i, __last)
-                ++__i;  // __first + 1
-                __j = __last;
-                if (!__comp(*__first, *--__j)) {  // we need a guard if *__first == *(__last-1)
-                    while (true) {
-                        if (__i == __j) {
-                            return;  // [__first, __last) all equivalent elements
-                        } else if (__comp(*__first, *__i)) {
-                            swap(*__i, *__j);
-                            ++__n_swaps;
-                            ++__i;
-                            break;
-                        }
-                        ++__i;
-                    }
-                }
-                // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1
-                if (__i == __j) {
-                    return;
-                }
-                while (true) {
-                    while (!__comp(*__first, *__i))
-                        ++__i;
-                    while (__comp(*__first, *--__j))
-                        ;
-                    if (__i >= __j)
-                        break;
-                    swap(*__i, *__j);
-                    ++__n_swaps;
-                    ++__i;
-                }
-                // [__first, __i) == *__first and *__first < [__i, __last)
-                // The first part is sorted,
-                if (__nth < __i) {
-                    return;
-                }
-                // __nth_element the second part
-                // _VSTD::__nth_element<_Compare>(__i, __nth, __last, __comp);
-                __first = __i;
-                continue;
-            }
-        }
-        ++__i;
-        // j points beyond range to be tested, *__lm1 is known to be <= *__m
-        // if not yet partitioned...
-        if (__i < __j)
-        {
-            // known that *(__i - 1) < *__m
-            while (true)
-            {
-                // __m still guards upward moving __i
-                while (__comp(*__i, *__m))
-                    ++__i;
-                // It is now known that a guard exists for downward moving __j
-                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);
-            ++__n_swaps;
-        }
-        // [__first, __i) < *__i and *__i <= [__i+1, __last)
-        if (__nth == __i)
-            return;
-        if (__n_swaps == 0)
-        {
-            // We were given a perfectly partitioned sequence.  Coincidence?
-            if (__nth < __i)
-            {
-                // Check for [__first, __i) already sorted
-                __j = __m = __first;
-                while (true) {
-                    if (++__j == __i) {
-                        // [__first, __i) sorted
-                        return;
-                    }
-                    if (__comp(*__j, *__m)) {
-                        // not yet sorted, so sort
-                        break;
-                    }
-                    __m = __j;
-                }
-            }
-            else
-            {
-                // Check for [__i, __last) already sorted
-                __j = __m = __i;
-                while (true) {
-                    if (++__j == __last) {
-                        // [__i, __last) sorted
-                        return;
-                    }
-                    if (__comp(*__j, *__m)) {
-                        // not yet sorted, so sort
-                        break;
-                    }
-                    __m = __j;
-                }
-            }
-        }
-        // __nth_element on range containing __nth
-        if (__nth < __i)
-        {
-            // _VSTD::__nth_element<_Compare>(__first, __nth, __i, __comp);
-            __last = __i;
-        }
-        else
-        {
-            // _VSTD::__nth_element<_Compare>(__i+1, __nth, __last, __comp);
-            __first = ++__i;
-        }
-    }
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+void __nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last,
+                   _Compare __comp) {
+  using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type;
+
+  while (true) {
+
+          std::__sort3<_Compare>(__first, ++__m, --__last, __comp);
+
+    if (__len <= __limit) {
+      std::__selection_sort<_Compare>(__first, __last, __comp);
+
+    unsigned __n_swaps = std::__sort3<_Compare>(__first, __m, --__lm1, __comp);
+      if (std::__nth_element_find_guard<_Compare>(__i, __j, __m, __comp)) {
+
+
+
+        // std::__nth_element<_Compare>(__i, __nth, __last, __comp);
+
+    if (__i < __j) {
+      while (true) {
+
+
+
+    if (__i != __m && __comp(*__m, *__i)) {
+
+    if (__n_swaps == 0) {
+      if (__nth < __i) {
+
+      } else {
+
+    if (__nth < __i) {
+      // std::__nth_element<_Compare>(__first, __nth, __i, __comp);
+    } else {
+      // std::__nth_element<_Compare>(__i+1, __nth, __last, __comp);
 }
 
 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) {
   _LIBCPP_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);
+
   _LIBCPP_DEBUG_RANDOMIZE_RANGE(__first, __nth);
   if (__nth != __last) {
     _LIBCPP_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 = __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_max.h>
 #include <__algorithm/ranges_max_element.h>
 #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_none_of.h>
+#include <__algorithm/ranges_nth_element.h>
 #include <__algorithm/ranges_replace.h>
 #include <__algorithm/ranges_replace_if.h>
 #include <__algorithm/ranges_reverse.h>
 #include <__algorithm/ranges_sort.h>
 #include <__algorithm/ranges_swap_ranges.h>
 #include <__algorithm/ranges_transform.h>
 #include <__algorithm/ranges_upper_bound.h>
 #include <__algorithm/remove.h>

libcxx/include/module.modulemap.in

module __algorithm {
       module ranges_max                      { private header "__algorithm/ranges_max.h" }
       module ranges_max_element              { private header "__algorithm/ranges_max_element.h" }
       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_none_of                  { private header "__algorithm/ranges_none_of.h" }
+      module ranges_nth_element              { private header "__algorithm/ranges_nth_element.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_sort                     { private header "__algorithm/ranges_sort.h" }
       module ranges_swap_ranges              { private header "__algorithm/ranges_swap_ranges.h" }
       module ranges_transform                { private header "__algorithm/ranges_transform.h" }
       module ranges_upper_bound              { private header "__algorithm/ranges_upper_bound.h" }
       module remove                          { private header "__algorithm/remove.h" }

libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.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
 //
 //===----------------------------------------------------------------------===//
 
#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

 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
#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

 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 

 #include <__algorithm/ranges_max.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_max.h'}}
 #include <__algorithm/ranges_max_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_max_element.h'}}
 #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_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_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_sort.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_sort.h'}}
 #include <__algorithm/ranges_swap_ranges.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_swap_ranges.h'}}
 #include <__algorithm/ranges_transform.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_transform.h'}}
 #include <__algorithm/ranges_upper_bound.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_upper_bound.h'}}
 #include <__algorithm/remove.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/remove.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 <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,
+    [[maybe_unused]] std::array<T, N> expected) {
+  // Different implementations produce differing output that still satisfies the algorithm requirements, so we can only
+  // check for specific output in the libc++ implementation.
+  LIBCPP_ASSERT(partially_sorted == expected);
+  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;
+
+  // 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::array<int, N> expected) {
+  { // (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);
+    verify_nth(partially_sorted, nth_index, last, expected);
+  }
+
+  { // (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);
+    verify_nth(partially_sorted, nth_index, last, expected);
+  }
+}
+
+template <class Iter, class Sent, size_t N>
+constexpr void test_all_cases(std::array<int, N> input, std::array<std::array<int, N>, N> expected_array) {
+  for (int n = 0; n != N; ++n) {
+    test_one<Iter, Sent, N>(input, n, expected_array[n]);
+  }
+  test_one<Iter, Sent, N>(input, N, input);
+}
+
+template <class Iter, class Sent, size_t N>
+constexpr void test_all_cases(std::array<int, N> input, std::array<int, N> expected) {
+  for (int n = 0; n != N; ++n) {
+    test_one<Iter, Sent, N>(input, n, expected);
+  }
+  test_one<Iter, Sent, N>(input, N, input);
+}
+
+template <class Iter, class Sent>
+constexpr void test_iterators_2() {
+  { // Empty sequence.
+    test_one<Iter, Sent, 0>({}, 0, {});
+  }
+
+  { // 1-element sequence.
+    test_one<Iter, Sent, 1>({1}, 0, {1});
+    test_one<Iter, Sent, 1>({1}, 1, {1});
+  }
+
+  { // 3-element sequence.
+    std::array input = {2, 1};
+    std::array expected = {1, 2};
+    test_all_cases<Iter, Sent>(input, expected);
+  }
+
+  { // 3-element sequence.
+    std::array input = {2, 1, 3};
+    std::array expected = {1, 2, 3};
+    test_all_cases<Iter, Sent>(input, expected);
+  }
+
+  { // Longer sequence.
+    std::array input = {2, 1, 3, 6, 8, 4, 11, 5};
+    std::array expected1 = {1, 2, 3, 4, 5, 6, 11, 8};
+    std::array expected2 = {2, 1, 3, 4, 5, 6, 11, 8};
+    std::array expected3 = {2, 1, 3, 4, 5, 6, 8, 11};
+
+    std::array<decltype(input), input.size()> expected_array = {
+      expected1, expected1, expected1, expected1, expected2, expected3, expected3, expected3
+    };
+
+    test_all_cases<Iter, Sent>(input, expected_array);
+  }
+
+  { // Longer sequence with duplicates.
+    std::array input = {2, 1, 3, 6, 2, 8, 6};
+    std::array expected = {1, 2, 2, 3, 6, 6, 8};
+    test_all_cases<Iter, Sent>(input, expected);
+  }
+
+  { // All elements are the same.
+    std::array input = {1, 1, 1, 1};
+    test_all_cases<Iter, Sent>(input, input);
+  }
+
+  { // nth element is in the right place.
+    std::array input = {6, 5, 3, 1, 4, 2};
+    std::array expected = {1, 2, 3, 4, 5, 6};
+    constexpr size_t N = input.size();
+
+    test_one<Iter, Sent, N>(input, 2, expected);
+  }
+
+  { // Already sorted.
+    std::array input = {1, 2, 3, 4, 5, 6};
+    test_all_cases<Iter, Sent>(input, input);
+  }
+
+  { // Reverse sorted.
+    std::array input = {6, 5, 4, 3, 2, 1};
+    std::array expected = {1, 2, 3, 4, 5, 6};
+    test_all_cases<Iter, Sent>(input, expected);
+  }
+
+  { // Repeating pattern.
+    std::array input = {2, 1, 2, 1, 2, 1};
+    std::array expected = {1, 1, 1, 2, 2, 2};
+    test_all_cases<Iter, Sent>(input, expected);
+  }
+}
+
+template <class Iter>
+constexpr void test_iterators_1() {
+  test_iterators_2<Iter, Iter>();
+  test_iterators_2<Iter, sentinel_wrapper<Iter>>();
+}
+
+constexpr void test_iterators() {
+  test_iterators_1<random_access_iterator<int*>>();
+  test_iterators_1<contiguous_iterator<int*>>();
+  test_iterators_1<int*>();
+}
+
+constexpr bool test() {
+  test_iterators();
+
+  { // A custom comparator works.
+    const std::array input = {1, 2, 3, 4, 5};
+    std::array expected = {5, 4, 3, 2, 1};
+    std::ranges::greater comp;
+
+    {
+      auto in = input;
+      auto last = std::ranges::nth_element(in.begin(), in.begin() + 1, in.end(), comp);
+      assert(in == expected);
+      assert(last == in.end());
+    }
+
+    {
+      auto in = input;
+      auto last = std::ranges::nth_element(in, in.begin() + 1, comp);
+      assert(in == expected);
+      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}};
+    std::array expected = {A{1}, A{2}, A{3}};
+
+    {
+      auto in = input;
+      auto last = std::ranges::nth_element(in.begin(), in.begin() + 1, in.end(), {}, &A::a);
+      assert(in == expected);
+      assert(last == in.end());
+    }
+
+    {
+      auto in = input;
+      auto last = std::ranges::nth_element(in, in.begin() + 1, {}, &A::a);
+      assert(in == expected);
+      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}};
+    std::array expected = {S{1}, S{2}, S{3}};
+
+    {
+      auto in = input;
+      auto last = std::ranges::nth_element(in.begin(), in.begin() + 1, in.end(), &S::comparator, &S::projection);
+      assert(in == expected);
+      assert(last == in.end());
+    }
+
+    {
+      auto in = input;
+      auto last = std::ranges::nth_element(in, in.begin() + 1, &S::comparator, &S::projection);
+      assert(in == expected);
+      assert(last == in.end());
+    }
+  }
+
+  { // The comparator can return any type that's convertible to `bool`.
+    const std::array input = {2, 1, 3};
+    std::array expected = {1, 2, 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 == expected);
+      assert(last == in.end());
+    }
+
+    {
+      std::array in = input;
+      auto last = std::ranges::nth_element(in, in.begin() + 1, pred);
+      assert(in == expected);
+      assert(last == in.end());
+    }
+  }
+
+  { // `std::ranges::dangling` is returned.
+    [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) result =
+        std::ranges::nth_element(std::array{1, 2, 3}, 0);
+  }
+
+  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

 //===----------------------------------------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 

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