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

[var-const]

Use the actual patch number.

[var-const]

Formatting.

[ldionne]

This looks pretty good to me, with some suggestions. I'm especially curious to see what it looks like once we've addressed the issue of using the proper ranges:: vs std:: operations (iter_swap & friends), as we discussed offline.

libcxx/include/__algorithm/partial_sort.h

42–48

Instead, I think _LIBCPP_DEBUG_RANDOMIZE_RANGE should support (Iter first, Sentinel last). You can call std::ranges::next from within _LIBCPP_DEBUG_RANDOMIZE_RANGE when Iter != Sentinel.

You should wait for @philnik to land his patch about replacing the macro by a function. Also, we should probably move it to a separate header to avoid dragging parts of <ranges> in any header that requires __libcpp_debug_randomize_range (or whatever the name was).

53

I find the layering a bit confusing here. We've got: partial_sort -> __partial_sort_impl -> __partial_sort. I would expect either partial_sort -> __partial_sort -> __partial_sort_impl (so just swap the names of __partial_sort and __partial_sort_impl), or you could even inline __partial_sort_impl into __partial_sort and start calling the latter instead of the former from public functions, since __partial_sort is only used here.

libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort/ranges_partial_sort.pass.cpp

68

This is not the expected sequence since you are only checking a subsequence of it. It's really the full sorted sequence. IMO this renaming (or similar) would make it easier, otherwise one might try to understand why the expected sequence has N elements when we're partially sorting mid_index <= N elements.

76–77

This makes it easier to understand what the std::equal is comparing.

89–90

Same reformatting.

96

Maybe this is closer to what it does? When I think of "cases", I think of what's tested in check() below.

[var-const]

@ldionne I took a stab at the _Tag approach we discussed, please let me know what you think. Among other things, do you think having algorithms default to _STLClassic be a good idea? It would avoid the need to update most callers.

[var-const]

Address feedback.

[var-const]

libcxx-generate-files

[var-const]

libcxx/include/__algorithm/sift_down.h

53 ↗

(On Diff #441915)

@huixie90 This should call ranges::iter_move when the function is invoked from a range algorithm (and just std::move(*__start)) when invoked from classic algorithms). Let me know what you think.

[philnik]

libcxx/include/__algorithm/basic_operations.h

30 ↗

(On Diff #441918)

Isn't this pretty much exactly the same as _StdIterOps and _RangesIterOps (in __algorithm/iterator_operations.h), just with a bit more boiler-plate?

[huixie90]

Thanks for fixing the iter_swap and iter_move. It almost LGTM

libcxx/include/__algorithm/partial_sort.h

32

A general question on these __impl functions. There are lots of double underscore impl functions in the algorithms that are shared between different algorithms. e.g. __copy. these functions are not constrained and sometimes I am unsure what condition these functions can be used. I guess some of them are not meant to be used outside the file thus omitting any constraint checks. But it is not easy to find out if it is ok to use these impl functions. I am wondering if it is a good idea to add some comments or static_assert on these functions?

libcxx/include/__algorithm/ranges_basic_operations.h

22 ↗

(On Diff #441918)

do we need to guard this header with c++ version?

33 ↗

(On Diff #441918)

nit: could do ranges::iter_swap instead of std::ranges::iter_swap

libcxx/include/__algorithm/sift_down.h

42 ↗

(On Diff #441918)

I had a look at the implementation of _make_projected_comp, if the new range's algorithm caller pass in a member function pointer and std::identity as projection, this __comp would be kept as a member function pointer and fail to compile here calling operator()

is there any tests covering this case?

libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort/ranges_partial_sort.pass.cpp

285

is there any test case that tests zip-iterator-like behavior ?

I am working on a test iterator that does something similar with zip-iterator but much simiplied

[var-const]

Address feedback, fix the CI.

libcxx/include/__algorithm/basic_operations.h

30 ↗

(On Diff #441918)

Sorry, I completely missed that patch. You're right, it's pretty much the same idea. The only difference of any significance is that a tag can be used to make arbitrary decisions -- or rather, passing a generic tag instead of a class containing a set of operations makes it clearer that this is intended to be a generic mechanism, not limited to just iterator operations. I could imagine something like:

template <class _Tag, class _Iter>
decltype(auto) __foo_impl(_Iter __b, _Iter __e) {
  // ...
  if constexpr (same_as<_Tag, _RangeAlgorithms>)
    return __e;
}

(Of course, this could be done as if constexpr(same_as<_IterOps, _RangesIterOps>) too, but I think it is a bit less readable)

In either case, there's definitely duplication here. Let's discuss whether being more generic with tags is worth the boilerplate, and I'll consolidate the approach in this patch (whichever we decide).

(By the way, the static constexpr auto advance = ranges::advance; idea is pretty neat)

libcxx/include/__algorithm/partial_sort.h

32

I think that these functions generally start their life being intended to use only within their file, but later end up being used from outside. The fact that they aren't constrained might be deliberate -- any checks are supposed to have already been performed by the public interface. Comments are definitely useful; static_asserts might be useful as well.

libcxx/include/__algorithm/sift_down.h

42 ↗

(On Diff #441918)

This is a great catch, thanks! Do you plan to fix this in D129099 (since that patch already contains an overload of __make_projected_comp that avoids the issue)?

libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort/ranges_partial_sort.pass.cpp

285

Not yet -- I plan to add a test once your patch lands.

[huixie90]

libcxx/include/__algorithm/sift_down.h

42 ↗

(On Diff #441918)

I updated D129099 to fix the first overload. could you please double check if that is OK?

[var-const]

Address feedback, fix the CI.

[var-const]

Remove unnecessary underscores from names.

libcxx/include/__algorithm/basic_operations.h

30 ↗

(On Diff #441918)

I took a stab at consolidating the two -- the only change I did (other than adding new functions) is using the tag approach for reasons outlined above (more generic). Please let me know what you think.

[huixie90]

libcxx/include/__algorithm/iterator_operations.h

82 ↗

(On Diff #443127)

is it just return __last?

[philnik]

Could you maybe move the _IterOps changes into it's own PR? There are quite a few changes unrelated to ranges::partial_sort in here.

libcxx/include/__algorithm/basic_operations.h

30 ↗

(On Diff #441918)

FWIW we can still change it later if we want to. But for now, I don't think you are using the _Tag for anything other than calling functions from _BasicOperations, right? In that case I would definitely go for less boiler-plate.

libcxx/include/__algorithm/iterator_operations.h

38 ↗

(On Diff #443127)

I think you have to use __iter_move, since it doesn't exist pre-C++20.

68 ↗

(On Diff #443127)

Why is the std::forward required?

73 ↗

(On Diff #443127)

Why aren't this one and the next also marked _LIBCPP_CONSTEXPR_AFTER_CXX11?

82 ↗

(On Diff #443127)

+1

libcxx/include/__algorithm/lower_bound.h

30 ↗

(On Diff #443127)

The name _Tag looks quite opaque to me. How about _Namespace or something like that?

[var-const]

@philnik I have moved the changes to iterator_operations.h to https://reviews.llvm.org/D129390 and addressed the related feedback there.

It's true that we can go for the more generic version later, but it also gives me a certain peace of mind that no matter what kind of issues may come up from sharing the same implementation, they can be worked around (even if they turn out not to be related to iterator operations).

libcxx/include/__algorithm/iterator_operations.h

68 ↗

(On Diff #443127)

This is to make the implementation as similar as possible to the actual C++20 iter_move. Perhaps because the iterator type could have overloads of operator* based on whether it's an lvalue or an rvalue? FWIW, the One Ranges Proposal doesn't have forward, so it's something that must have come up during subsequent discussions. Regardless of the original motivation, it seems easier to keep it for consistency with the actual function -- what do you think?

libcxx/include/__algorithm/lower_bound.h

30 ↗

(On Diff #443127)

How about something like _AlgFamily or _InvocationContext?

libcxx/include/__algorithm/sift_down.h

42 ↗

(On Diff #441918)

Thank you!

[huixie90]

libcxx/include/__algorithm/iterator_operations.h

66–68 ↗

(On Diff #443127)

FWIW, auto return type and this explicit return type can be different. e.g for std::vector<bool>::iterator, std::move(*std::forward<_Iter>(__i)); is proxy&& and value_type&& is bool&&. However. in classic algorithm, you have to do write

value_type temp = std::move(*it);

because

auto temp = std::move(*it);

does the wrong thing for vector<bool> and friends.

So here this explicit return type does the conversion sometimes and probably IS what the caller wants

libcxx/include/__algorithm/lower_bound.h

30 ↗

(On Diff #443127)

Or _Policy and we have _RangesPolicy and _ClassicPolicy

libcxx/include/__algorithm/make_heap.h

30 ↗

(On Diff #443127)

For C++20 algorithms, we should use iter_difference_t .

the difference_type is coming from incrementable_traits when iterator_traits is not specialized

(Note this applies to all other usages of difference_type)

libcxx/include/__algorithm/pop_heap.h

28–29

For C++20 ranges algorithms, we should use iter_value_t.
because the value_type is coming from indirectly_readable_traits when iterator_traits is not specialized

This applies to all other places we use value_type

libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort/ranges_partial_sort.pass.cpp

282

btw, you can rebase and try sorting the ProxyRange to verify if iter_swap is used properly used and sorting ProxyRange of move only types to see if iter_move is properly used

[huixie90]

libcxx/include/__algorithm/make_heap.h

30 ↗

(On Diff #443127)

Actually, it is fine for this algorithm to use iterator_traits

since the input are required to model c++20 random_access_iterator and C++ 20 random_access_iterator implies c++17 input iterator and that makes sure that iterator_traits exists and consistent with c++20’s iter_differnece_t (and iter_value_t for the value_type)

I think this can be a problem only in algorithms that take c++20 input iterators, because c++ 20 input_iterators can have empty iterator_traits

[var-const]

libcxx/include/__algorithm/lower_bound.h

30 ↗

(On Diff #443127)

I really like "policy" -- went with _RangeAlgPolicy and _ClassicAlgPolicy (in https://reviews.llvm.org/D129390). Please let me know what you think.

[var-const]

libcxx/include/__algorithm/make_heap.h

30 ↗

(On Diff #443127)

Thanks a lot for spotting this. I've added checking algorithms that take input iterators to my backlog.

[var-const]

Rebase on main (including the iterator_operations.h changes from
https://reviews.llvm.org/D129390).

[var-const]

libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort/ranges_partial_sort.pass.cpp

282

I'd prefer to do this in a follow-up once this lands.

[var-const]

@philnik @huixie90 This is ready for another round of review.

[huixie90]

libcxx/include/__algorithm/partial_sort.h

32

Can we have a naming convention for this? It would be good to distinguish the purpose of __partial_sort and __partial_sort_impl at the first glance.

It would be good to distinguish

1. helper function purely for implementation of the classic algorithm (perhaps with some assumptions that the iterators are classic iterators)
2. helper function purely for the implementation of ranges algorithm (perhaps with assumptions that iterators are c++20 iterators)
3. helper function that is meant to be shared between the classic algorithm and the ranges algorithm
4. helper function can be reused any other algorithms

The reason why I was asking is that when I implemented other algorithms and I'd like to call copy, I was puzzled if I should call std::__copy or std::__copy_impl

37

question. why do we need inline here as it is already a template (we don't need to worry about ODR violation)?

[philnik]

Mostly nits, but I'd like to see the portability trap addressed. Did you add any moves in other classic algorithms? If yes, please also update them.

libcxx/include/__algorithm/partial_sort.h

36

Could you add a TODO to remove this and update __debug_randomize_range to support ranges once we implement ranges::shuffle?

100–101

Could you either not move these or static_assert that they are copy-constructible and copy-assignable to avoid portability problems?

libcxx/include/__algorithm/pop_heap.h

62

Pre-existing: Please also remove the moves or add static_asserts.

libcxx/include/__algorithm/push_heap.h

66

Also here.

libcxx/include/__algorithm/sort_heap.h

50–51

Same here.

libcxx/test/libcxx/algorithms/partial_sort_stability.pass.cpp

37–38

Shouldn't this be _ClassicAlgPolicy?

libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort/ranges_partial_sort.pass.cpp

71–73

Could you rename these to begin, middle and end? That would make it a lot easier to read IMO.

89

Why aren't you using b and m here?

106–136

Could you put this into a function? The calls below look really weird.

158–160

Why aren't these in a single line?

210–246

This should be unnecessary now, right?

248–284

And this.

[var-const]

Address feedback (partial).

libcxx/include/__algorithm/partial_sort.h

32

My intention was for __foo to be the main internal entry point, i.e., __foo functions are the public interface for internal usage, and other algorithms should call into __foo. __foo_impl would be an implementation detail local to the file (ideally I'd put it into an internal namespace as well).

I'm not sure the finer-grained distinction is necessary -- from what I've seen, we're rewriting all the internal functions to be agnostic to whether they're invoked from a classic or a range algorithm. Please let me know if there's an example where it would be helpful.

Note that in this case, I can't easily combine these two functions -- __partial_sort does randomization before and after doing actual work, and the partial_sort_stability test relies on being able to call partial_sort with and without randomization. If combining the two, one straightforward alternative would be to pass this as a boolean template parameter.

37

It was unnecessary, thanks for spotting it.

42–48

Added a TODO -- this will be much easier to implement once ranges::shuffle is implemented.

libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort/ranges_partial_sort.pass.cpp

71–73

Personally, I much prefer the shorter names in cases like this (where the meaning is easy to understand because the pattern of having begin/end is so ubiquitous, and shorter names help cut down on verbosity). However, it's not worth spending much time debating this, so I renamed like you suggested.

89

Because of std::equal -- perhaps ranges::equal was unavailable when I was first writing this. In any case, changed to use ranges::equal and begin/end.

106–136

This was suggested by @ldionne. The advantage is to have all the related code in the same scope, i.e. to avoid the details spilling out of the function.

158–160

I find it easier to read this way. Reverted.

[var-const]

Note: this was rebased on https://reviews.llvm.org/D129823 which significantly reduced the delta.

[philnik]

libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort/ranges_partial_sort.pass.cpp

106–136

By that logic, shouldn't everything be in nested lambdas in tests? You aren't capturing anything, so I really don't see how that's better than having it as an extra function. What exactly do you think is "spilling out of the function"?

[var-const]

libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort/ranges_partial_sort.pass.cpp

106–136

Let's leave this debate for another day, after the release. Changed.

[var-const]

Fix the CI, address comment.

[ldionne]

libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort/ranges_partial_sort.pass.cpp

106–136

By that logic, shouldn't everything be in nested lambdas in tests? You aren't capturing anything, so I really don't see how that's better than having it as an extra function. What exactly do you think is "spilling out of the function"?

FWIW the idea is that a top-level function exposes a name, whereas a lambda doesn't because it's a local variable in another scope. It makes it clearer that it's only an implementation detail of e.g. test_iterators() used only for avoiding code duplication. I don't mind which approach we take given that we have more important stuff to focus on right now, though.

[ldionne]

This LGTM at a glance, but I'll leave final approval to the other reviewers who had comments.

[philnik]

I currently don't have a lot of time, so I trust @ldionne's approval.

[var-const]

Address the remaining feedback, rebase on main.

[var-const]

Rebase on main.

[var-const]

Rebase on main.

[var-const]

libcxx/include/__algorithm/partial_sort.h

100–101

Ah, this is a very good catch. Added static assertions and added auditing those to my backlog.

libcxx/docs/Status/RangesAlgorithms.csv

 Write,replace_copy,Nikolas Klauser,`D129806 <https://llvm.org/D129806>`_,Under review
 Write,replace_copy_if,Nikolas Klauser,`D129806 <https://llvm.org/D129806>`_,Under review
 Write,swap_ranges,Nikolas Klauser,`D116303 <https://llvm.org/D116303>`_,✅
 Write,reverse_copy,Nikolas Klauser,`D127211 <https://llvm.org/D127211>`_,✅
 Write,rotate_copy,Nikolas Klauser,`D127211 <https://llvm.org/D127211>`_,✅
 Write,sample,Not assigned,n/a,Not started
 Write,unique_copy,Not assigned,n/a,Not started
 Write,partition_copy,Konstantin Varlamov,n/a,In progress
-Write,partial_sort_copy,Not assigned,n/a,Not started
+Write,partial_sort_copy,Konstantin Varlamov,n/a,In progress
 Merge,merge,Hui Xie,`D128611 <https://llvm.org/D128611>`_,✅
 Merge,set_difference,Hui Xie,`D128983 <https://llvm.org/D128983>`_,✅
 Merge,set_intersection,Hui Xie,`D129233 <https://llvm.org/D129233>`_,✅
 Merge,set_symmetric_difference,Hui Xie,`D129520 <https://llvm.org/D129520>`_,✅
 Merge,set_union,Hui Xie,`D129657 <https://llvm.org/D129657>`_,✅
 Permutation,remove,Nikolas Klauser,`D128618 <https://llvm.org/D128618>`_,✅
 Permutation,remove_if,Nikolas Klauser,`D128618 <https://llvm.org/D128618>`_,✅
 Permutation,reverse,Nikolas Klauser,`D125752 <https://llvm.org/D125752>`_,✅
 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,Konstantin Varlamov,`D129624 <https://llvm.org/D129624>`_,✅
 Permutation,stable_partition,Konstantin Varlamov,`D129624 <https://llvm.org/D129624>`_,✅
 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,Konstantin Varlamov,`D128149 <https://llvm.org/D128149>`_,✅
+Permutation,partial_sort,Konstantin Varlamov,`D128744 <https://llvm.org/D128744>`_,✅
 Permutation,inplace_merge,Not assigned,n/a,Not started
 Permutation,make_heap,Konstantin Varlamov,`D128115 <https://llvm.org/D128115>`_,✅
 Permutation,push_heap,Konstantin Varlamov,`D128115 <https://llvm.org/D128115>`_,✅
 Permutation,pop_heap,Konstantin Varlamov,`D128115 <https://llvm.org/D128115>`_,✅
 Permutation,sort_heap,Konstantin Varlamov,`D128115 <https://llvm.org/D128115>`_,✅
 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_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_partial_sort.h
   __algorithm/ranges_partial_sort_copy.h
   __algorithm/ranges_partition.h
   __algorithm/ranges_partition_copy.h
   __algorithm/ranges_partition_point.h
   __algorithm/ranges_pop_heap.h
   __algorithm/ranges_push_heap.h
   __algorithm/ranges_remove.h
   __algorithm/ranges_remove_copy.h

libcxx/include/__algorithm/partial_sort.h

 #include <__algorithm/iterator_operations.h>
 #include <__algorithm/make_heap.h>
 #include <__algorithm/sift_down.h>
 #include <__algorithm/sort_heap.h>
 #include <__config>
 #include <__debug>
 #include <__debug_utils/randomize_range.h>
 #include <__iterator/iterator_traits.h>
+#include <__utility/move.h>
+#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
-_LIBCPP_CONSTEXPR_AFTER_CXX17 void
-__partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
-               _Compare __comp)
-{
-    if (__first == __middle)
-        return;
-    std::__make_heap<_AlgPolicy, _Compare>(__first, __middle, __comp);
-    typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first;
-    for (_RandomAccessIterator __i = __middle; __i != __last; ++__i)
-    {
-        if (__comp(*__i, *__first))
-        {
-            _IterOps<_AlgPolicy>::iter_swap(__i, __first);
-            std::__sift_down<_AlgPolicy, _Compare>(__first, __comp, __len, __first);
-        }
-    }
-    std::__sort_heap<_AlgPolicy, _Compare>(__first, __middle, __comp);
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator, class _Sentinel>
+_LIBCPP_CONSTEXPR_AFTER_CXX17
+_RandomAccessIterator __partial_sort_impl(
+    _RandomAccessIterator __first, _RandomAccessIterator __middle, _Sentinel __last, _Compare __comp) {
+  if (__first == __middle) {
+    return _IterOps<_AlgPolicy>::next(__middle, __last);
+  }
+
+
+  _RandomAccessIterator __i = __middle;
+  for (; __i != __last; ++__i)
+
+  }
+  std::__sort_heap<_AlgPolicy, _Compare>(std::move(__first), std::move(__middle), __comp);
+
+  return __i;
+}
+
+// TODO(ranges): once `ranges::shuffle` is implemented, remove this helper and make `__debug_randomize_range` support
+// sentinels.
+template <class _AlgPolicy, class _RandomAccessIterator, class _Sentinel>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+void __maybe_randomize(_RandomAccessIterator __first, _Sentinel __last) {
+  std::__debug_randomize_range<_AlgPolicy>(__first, _IterOps<_AlgPolicy>::next(__first, __last));
+
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator, class _Sentinel>
+_LIBCPP_CONSTEXPR_AFTER_CXX17
+_RandomAccessIterator __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _Sentinel __last,
+                                     _Compare& __comp) {
+  if (__first == __middle)
+      return _IterOps<_AlgPolicy>::next(__middle, __last);
+
+  std::__maybe_randomize<_AlgPolicy>(__first, __last);
+
+  using _Comp_ref = typename __comp_ref_type<_Compare>::type;
+  auto __last_iter = std::__partial_sort_impl<_AlgPolicy, _Comp_ref>(__first, __middle, __last, __comp);
+
+  std::__maybe_randomize<_AlgPolicy>(__middle, __last);
+
+  return __last_iter;
 }
 
 template <class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
              _Compare __comp)
 {
-  std::__debug_randomize_range<_ClassicAlgPolicy>(__first, __last);
-  typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-  std::__partial_sort<_ClassicAlgPolicy, _Comp_ref>(__first, __middle, __last, __comp);
-  std::__debug_randomize_range<_ClassicAlgPolicy>(__middle, __last);
+  static_assert(std::is_copy_constructible<_RandomAccessIterator>::value, "Iterators must be copy constructible.");
+  static_assert(std::is_copy_assignable<_RandomAccessIterator>::value, "Iterators must be copy assignable.");
+
+  (void)std::__partial_sort<_ClassicAlgPolicy>(std::move(__first), std::move(__middle), std::move(__last), __comp);
 }
 
 template <class _RandomAccessIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
 {
     _VSTD::partial_sort(__first, __middle, __last,
                         __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_PARTIAL_SORT_H

libcxx/include/__algorithm/pop_heap.h

 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/iterator_operations.h>
 #include <__algorithm/push_heap.h>
 #include <__algorithm/sift_down.h>
 #include <__assert>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__utility/move.h>
+#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
 void __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp,
     typename iterator_traits<_RandomAccessIterator>::difference_type __len) {
   _LIBCPP_ASSERT(__len > 0, "The heap given to pop_heap must be non-empty");
 
   using _CompRef = typename __comp_ref_type<_Compare>::type;
   _CompRef __comp_ref = __comp;
 
if (__hole == __last) {
       std::__sift_up<_AlgPolicy, _CompRef>(__first, __hole, __comp_ref, __hole - __first);
     }
   }
 }
 
 template <class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
+  static_assert(std::is_copy_constructible<_RandomAccessIterator>::value, "Iterators must be copy constructible.");
+  static_assert(std::is_copy_assignable<_RandomAccessIterator>::value, "Iterators must be copy assignable.");
+
   typename iterator_traits<_RandomAccessIterator>::difference_type __len = __last - __first;
   std::__pop_heap<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp, __len);
 }
 
 template <class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) {
   std::pop_heap(std::move(__first), std::move(__last),
       __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_POP_HEAP_H

libcxx/include/__algorithm/push_heap.h

 #define _LIBCPP___ALGORITHM_PUSH_HEAP_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/iterator_operations.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__utility/move.h>
+#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
void __push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) {
   using _CompRef = typename __comp_ref_type<_Compare>::type;
   typename iterator_traits<_RandomAccessIterator>::difference_type __len = __last - __first;
   std::__sift_up<_AlgPolicy, _CompRef>(std::move(__first), std::move(__last), __comp, __len);
 }
 
 template <class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
+  static_assert(std::is_copy_constructible<_RandomAccessIterator>::value, "Iterators must be copy constructible.");
+  static_assert(std::is_copy_assignable<_RandomAccessIterator>::value, "Iterators must be copy assignable.");
+
   std::__push_heap<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp);
 }
 
 template <class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) {
   std::push_heap(std::move(__first), std::move(__last),
       __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_PUSH_HEAP_H

libcxx/include/__algorithm/ranges_partial_sort.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_PARTIAL_SORT_H
+#define _LIBCPP___ALGORITHM_RANGES_PARTIAL_SORT_H
+
+#include <__algorithm/iterator_operations.h>
+#include <__algorithm/make_projected.h>
+#include <__algorithm/partial_sort.h>
+#include <__concepts/same_as.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 __partial_sort {
+
+struct __fn {
+  template <class _Iter, class _Sent, class _Comp, class _Proj>
+  _LIBCPP_HIDE_FROM_ABI constexpr static
+  _Iter __partial_sort_fn_impl(_Iter __first, _Iter __middle, _Sent __last, _Comp& __comp, _Proj& __proj) {
+    auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
+    return std::__partial_sort<_RangeAlgPolicy>(std::move(__first), std::move(__middle), __last, __projected_comp);
+  }
+
+  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 __middle, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {
+    return __partial_sort_fn_impl(std::move(__first), std::move(__middle), 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> __middle, _Comp __comp = {},
+                                         _Proj __proj = {}) const {
+    return __partial_sort_fn_impl(ranges::begin(__r), std::move(__middle), ranges::end(__r), __comp, __proj);
+  }
+};
+
+} // namespace __partial_sort
+
+inline namespace __cpo {
+  inline constexpr auto partial_sort = __partial_sort::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_PARTIAL_SORT_H

libcxx/include/__algorithm/sort.h

 
 template <class _AlgPolicy, class _RandomAccessIterator, class _Comp>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void __sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Comp& __comp) {
   std::__debug_randomize_range<_AlgPolicy>(__first, __last);
 
   using _Comp_ref = typename __comp_ref_type<_Comp>::type;
   if (__libcpp_is_constant_evaluated()) {
-    std::__partial_sort<_AlgPolicy, _Comp_ref>(__first, __last, __last, _Comp_ref(__comp));
+    std::__partial_sort<_AlgPolicy>(__first, __last, __last, __comp);
 
   } else {
     using _WrappedComp = typename _WrapAlgPolicy<_AlgPolicy, _Comp_ref>::type;
     _Comp_ref __comp_ref(__comp);
     _WrappedComp __wrapped_comp(__comp_ref);
     std::__sort<_WrappedComp>(std::__unwrap_iter(__first), std::__unwrap_iter(__last), __wrapped_comp);
   }
 }

libcxx/include/__algorithm/sort_heap.h

 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/iterator_operations.h>
 #include <__algorithm/pop_heap.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__utility/move.h>
-#include <type_traits> // swap
+#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
 void __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) {
   using _CompRef = typename __comp_ref_type<_Compare>::type;
   _CompRef __comp_ref = __comp;
 
   using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type;
   for (difference_type __n = __last - __first; __n > 1; --__last, (void) --__n)
     std::__pop_heap<_AlgPolicy, _CompRef>(__first, __last, __comp_ref, __n);
 }
 
 template <class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
+  static_assert(std::is_copy_constructible<_RandomAccessIterator>::value, "Iterators must be copy constructible.");
+  static_assert(std::is_copy_assignable<_RandomAccessIterator>::value, "Iterators must be copy assignable.");
+
   std::__sort_heap<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp);
 }
 
 template <class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) {
   std::sort_heap(std::move(__first), std::move(__last),
       __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_SORT_HEAP_H

libcxx/include/algorithm

template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
     requires sortable<I, Comp, Proj>
     I ranges::stable_sort(I first, 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>
     borrowed_iterator_t<R>
       ranges::stable_sort(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::partial_sort(I first, I middle, 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::partial_sort(R&& r, iterator_t<R> middle, Comp comp = {}, Proj proj = {});    // since C++20
+
   template<class T, output_iterator<const T&> O, sentinel_for<O> S>
     constexpr O ranges::fill(O first, S last, const T& value);                              // since C++20
 
   template<class T, output_range<const T&> R>
     constexpr borrowed_iterator_t<R> ranges::fill(R&& r, const T& value);                   // since C++20
 
   template<class T, output_iterator<const T&> O>
     constexpr O ranges::fill_n(O first, iter_difference_t<O> n, const T& value);            // since C++20

 #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_partial_sort.h>
 #include <__algorithm/ranges_partition.h>
 #include <__algorithm/ranges_pop_heap.h>
 #include <__algorithm/ranges_push_heap.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>

libcxx/include/module.modulemap.in

module __algorithm {
       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_partial_sort             { private header "__algorithm/ranges_partial_sort.h" }
       module ranges_partial_sort_copy        { private header "__algorithm/ranges_partial_sort_copy.h" }
       module ranges_partition                { private header "__algorithm/ranges_partition.h" }
       module ranges_partition_copy           { private header "__algorithm/ranges_partition_copy.h" }
       module ranges_partition_point          { private header "__algorithm/ranges_partition_point.h" }
       module ranges_pop_heap                 { private header "__algorithm/ranges_pop_heap.h" }
       module ranges_push_heap                { private header "__algorithm/ranges_push_heap.h" }
       module ranges_remove                   { private header "__algorithm/ranges_remove.h" }
       module ranges_remove_copy              { private header "__algorithm/ranges_remove_copy.h" }

libcxx/test/libcxx/algorithms/partial_sort_stability.pass.cpp

 
 std::vector<MyType> deterministic() {
   static constexpr int kSize = 100;
   std::vector<MyType> v;
   v.resize(kSize);
   for (int i = 0; i < kSize; ++i) {
     v[i].value = (i % 2 ? 1 : kSize / 2 + i);
   }
-  std::__partial_sort<std::_ClassicAlgPolicy>(v.begin(), v.begin() + kSize / 2, v.end(), std::less<MyType>());
+  auto comp = std::less<MyType>();
+  std::__partial_sort_impl<std::_ClassicAlgPolicy>(v.begin(), v.begin() + kSize / 2, v.end(), comp);
   return v;
 }
 
 void test_randomization() {
   static constexpr int kSize = 100;
   std::vector<MyType> v;
   v.resize(kSize);
   for (int i = 0; i < kSize; ++i) {

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

#endif
     (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::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(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);
     //(void)std::ranges::partition_point(first, last, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::partition_point(a, UnaryTrue(&copies)); assert(copies == 0);

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

#endif
     (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::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(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);
     //(void)std::ranges::partition_point(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::partition_point(a, UnaryTrue(), Proj(&copies)); assert(copies == 0);

libcxx/test/libcxx/private_headers.verify.cpp

 #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_partial_sort.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_partial_sort.h'}}
 #include <__algorithm/ranges_partial_sort_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_partial_sort_copy.h'}}
 #include <__algorithm/ranges_partition.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_partition.h'}}
 #include <__algorithm/ranges_partition_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_partition_copy.h'}}
 #include <__algorithm/ranges_partition_point.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_partition_point.h'}}
 #include <__algorithm/ranges_pop_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_pop_heap.h'}}
 #include <__algorithm/ranges_push_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_push_heap.h'}}
 #include <__algorithm/ranges_remove.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_remove.h'}}
 #include <__algorithm/ranges_remove_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_remove_copy.h'}}

libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort/ranges_partial_sort.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::partial_sort(I first, I middle, 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::partial_sort(R&& r, iterator_t<R> middle, Comp comp = {}, Proj proj = {});    // since C++20
+
+#include <algorithm>
+#include <array>
+#include <concepts>
+#include <functional>
+#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 HasPartialSortIt = requires(Iter first, Iter mid, Sent last, Comp comp) {
+  std::ranges::partial_sort(first, mid, last, comp);
+};
+
+static_assert(HasPartialSortIt<int*>);
+static_assert(!HasPartialSortIt<RandomAccessIteratorNotDerivedFrom>);
+static_assert(!HasPartialSortIt<RandomAccessIteratorBadIndex>);
+static_assert(!HasPartialSortIt<int*, SentinelForNotSemiregular>);
+static_assert(!HasPartialSortIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
+static_assert(!HasPartialSortIt<int*, int*, BadComparator>);
+static_assert(!HasPartialSortIt<const int*>); // Doesn't satisfy `sortable`.
+
+template <class Range, class Comp = std::ranges::less>
+concept HasPartialSortR = requires(Range range, std::ranges::iterator_t<Range> mid, Comp comp) {
+  std::ranges::partial_sort(range, mid, comp);
+};
+
+static_assert(HasPartialSortR<UncheckedRange<int*>>);
+static_assert(!HasPartialSortR<RandomAccessRangeNotDerivedFrom>);
+static_assert(!HasPartialSortR<RandomAccessRangeBadIndex>);
+static_assert(!HasPartialSortR<UncheckedRange<int*, SentinelForNotSemiregular>>);
+static_assert(!HasPartialSortR<UncheckedRange<int*, SentinelForNotWeaklyEqualityComparableWith>>);
+static_assert(!HasPartialSortR<UncheckedRange<int*>, BadComparator>);
+static_assert(!HasPartialSortR<UncheckedRange<const int*>>); // Doesn't satisfy `sortable`.
+
+template <class Iter, class Sent, size_t N>
+constexpr void test_one(std::array<int, N> input, size_t mid_index, std::array<int, N> sorted) {
+  { // (iterator, sentinel) overload.
+    auto partially_sorted = input;
+    auto begin = Iter(partially_sorted.data());
+    auto mid = begin + mid_index;
+    auto end = Sent(Iter(partially_sorted.data() + partially_sorted.size()));
+
+    std::same_as<Iter> decltype(auto) last = std::ranges::partial_sort(begin, mid, end);
+    assert(std::equal(partially_sorted.begin(), partially_sorted.begin() + mid_index,
+                      sorted.begin(), sorted.begin() + mid_index));
+    assert(base(last) == partially_sorted.data() + partially_sorted.size());
+  }
+
+  { // (range) overload.
+    auto partially_sorted = input;
+    auto begin = Iter(partially_sorted.data());
+    auto mid = begin + mid_index;
+    auto end = Sent(Iter(partially_sorted.data() + partially_sorted.size()));
+    auto range = std::ranges::subrange(begin, end);
+
+    std::same_as<Iter> decltype(auto) last = std::ranges::partial_sort(range, mid);
+    assert(std::ranges::equal(begin, begin + mid_index, sorted.begin(), sorted.begin() + mid_index));
+    assert(base(last) == partially_sorted.data() + partially_sorted.size());
+  }
+}
+
+template <class Iter, class Sent, size_t N>
+constexpr void test_all_subsequences(std::array<int, N> input) {
+  auto sorted = input;
+  std::sort(sorted.begin(), sorted.end());
+
+  for (size_t n = 0; n <= N; ++n) {
+    test_one<Iter, Sent, N>(input, n, sorted);
+  }
+}
+
+template <class Iter, class Sent>
+constexpr void test_iterator_and_sentinel() {
+  // Empty sequence.
+  test_one<Iter, Sent, 0>({}, 0, {});
+
+  // 1-element sequence.
+  test_all_subsequences<Iter, Sent>(std::array{1});
+
+  // 2-element sequence.
+  test_all_subsequences<Iter, Sent>(std::array{2, 1});
+
+  // 3-element sequence.
+  test_all_subsequences<Iter, Sent>(std::array{2, 1, 3});
+
+  // Longer sequence.
+  test_all_subsequences<Iter, Sent>(std::array{2, 1, 3, 6, 8, 4, 11, 5});
+
+  // Longer sequence with duplicates.
+  test_all_subsequences<Iter, Sent>(std::array{2, 1, 3, 6, 2, 8, 6});
+
+  // All elements are the same.
+  test_all_subsequences<Iter, Sent>(std::array{1, 1, 1});
+
+  // Already sorted.
+  test_all_subsequences<Iter, Sent>(std::array{1, 2, 3, 4, 5});
+
+  // Descending.
+  test_all_subsequences<Iter, Sent>(std::array{5, 4, 3, 2, 1});
+
+  // Repeating pattern.
+  test_all_subsequences<Iter, Sent>(std::array{1, 2, 1, 2, 1, 2});
+}
+
+constexpr void test_iterators() {
+  test_iterator_and_sentinel<random_access_iterator<int*>, random_access_iterator<int*>>();
+  test_iterator_and_sentinel<random_access_iterator<int*>, sentinel_wrapper<random_access_iterator<int*>>>();
+  test_iterator_and_sentinel<contiguous_iterator<int*>, contiguous_iterator<int*>>();
+  test_iterator_and_sentinel<contiguous_iterator<int*>, sentinel_wrapper<contiguous_iterator<int*>>>();
+  test_iterator_and_sentinel<int*, int*>();
+  test_iterator_and_sentinel<int*, sentinel_wrapper<int*>>();
+}
+
+constexpr bool test() {
+  test_iterators();
+
+  { // A custom comparator works.
+    const std::array orig_in = {1, 2, 3, 4, 5};
+
+    {
+      auto in = orig_in;
+      auto b = in.begin();
+      auto m = b + 2;
+
+      auto last = std::ranges::partial_sort(b, m, in.end(), std::ranges::greater{});
+      assert(std::ranges::equal(std::ranges::subrange(b, m), std::array{5, 4}));
+      assert(last == in.end());
+    }
+
+    {
+      auto in = orig_in;
+      auto b = in.begin();
+      auto m = b + 2;
+
+      auto last = std::ranges::partial_sort(in, m, std::ranges::greater{});
+      assert(std::ranges::equal(std::ranges::subrange(b, m), std::array{5, 4}));
+      assert(last == in.end());
+    }
+  }
+
+  { // A custom projection works.
+    struct A {
+      int a;
+      constexpr bool operator==(const A&) const = default;
+    };
+
+    const std::array orig_in = {A{2}, A{3}, A{1}};
+
+    {
+      auto in = orig_in;
+      auto b = in.begin();
+      auto m = b + 2;
+
+      auto last = std::ranges::partial_sort(b, m, in.end(), {}, &A::a);
+      assert(std::ranges::equal(
+          std::ranges::subrange(b, m), std::array{A{1}, A{2}}
+      ));
+      assert(last == in.end());
+    }
+
+    {
+      auto in = orig_in;
+      auto b = in.begin();
+      auto m = b + 2;
+
+      auto last = std::ranges::partial_sort(in, m, {}, &A::a);
+      assert(std::ranges::equal(
+          std::ranges::subrange(b, m), std::array{A{1}, A{2}}
+      ));
+      assert(last == in.end());
+    }
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.compile.pass.cpp

void test_all() {
   in2_out_pred(std::ranges::set_symmetric_difference, in, in2, out, binary_pred);
   in2_out_pred(std::ranges::set_union, in, in2, out, binary_pred);
   in_pred(std::ranges::remove_if, in, unary_pred);
   //in_pred(std::ranges::unique, in, binary_pred);
   in_pred(std::ranges::partition, in, unary_pred);
   in_pred(std::ranges::stable_partition, in, unary_pred);
   in_pred(std::ranges::sort, in, binary_pred);
   in_pred(std::ranges::stable_sort, in, binary_pred);
-  //in_mid_pred(std::ranges::partial_sort, in, mid, binary_pred);
+  in_mid_pred(std::ranges::partial_sort, in, mid, binary_pred);
   in_mid_pred(std::ranges::nth_element, in, mid, binary_pred);
   //in_mid_pred(std::ranges::inplace_merge, in, mid, binary_pred);
   in_pred(std::ranges::make_heap, in, binary_pred);
   in_pred(std::ranges::push_heap, in, binary_pred);
   in_pred(std::ranges::pop_heap, in, binary_pred);
   in_pred(std::ranges::sort_heap, in, binary_pred);
   //in_pred(std::ranges::prev_permutation, in, binary_pred);
   //in_pred(std::ranges::next_permutation, in, binary_pred);
 }

libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.compile.pass.cpp

void test_all() {
   // `reverse` has neither a projection nor a predicate.
   // `rotate` has neither a projection nor a predicate.
   // `shuffle` has neither a projection nor a predicate.
   //in_pred(std::ranges::unique, in, &Foo::binary_pred, &Bar::val);
   in_pred(std::ranges::partition, in, &Foo::unary_pred, &Bar::val);
   in_pred(std::ranges::stable_partition, in, &Foo::unary_pred, &Bar::val);
   in_pred(std::ranges::sort, in, &Foo::binary_pred, &Bar::val);
   in_pred(std::ranges::stable_sort, in, &Foo::binary_pred, &Bar::val);
-  //in_mid_pred(std::ranges::partial_sort, in, mid, binary_pred);
+  in_mid_pred(std::ranges::partial_sort, in, mid, &Foo::binary_pred, &Bar::val);
   in_mid_pred(std::ranges::nth_element, in, mid, &Foo::binary_pred, &Bar::val);
   //in_mid_pred(std::ranges::inplace_merge, in, mid, binary_pred);
   in_pred(std::ranges::make_heap, in, &Foo::binary_pred, &Bar::val);
   in_pred(std::ranges::push_heap, in, &Foo::binary_pred, &Bar::val);
   in_pred(std::ranges::pop_heap, in, &Foo::binary_pred, &Bar::val);
   in_pred(std::ranges::sort_heap, in, &Foo::binary_pred, &Bar::val);
   //in_pred(std::ranges::prev_permutation, in, &Foo::binary_pred, &Bar::val);
   //in_pred(std::ranges::next_permutation, in, &Foo::binary_pred, &Bar::val);
 }

libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp

constexpr void run_tests() {
   //test(std::ranges::unique, in);
   test(std::ranges::partition, in, unary_pred);
   if (!std::is_constant_evaluated())
     test(std::ranges::stable_partition, in, unary_pred);
   test(std::ranges::sort, in);
   // TODO: `stable_sort` requires `ranges::rotate` to be implemented.
   //if (!std::is_constant_evaluated())
   //  test(std::ranges::stable_sort, in);
-  //test_mid(std::ranges::partial_sort, in, mid);
+  test_mid(std::ranges::partial_sort, in, mid);
   test_mid(std::ranges::nth_element, in, mid);
   //if (!std::is_constant_evaluated())
   //  test_mid(std::ranges::inplace_merge, in, mid);
   test(std::ranges::make_heap, in);
   test(std::ranges::push_heap, in);
   test(std::ranges::pop_heap, in);
   test(std::ranges::sort_heap, in);
   //test(std::ranges::prev_permutation, in);

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

 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::partial_sort, 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));
 static_assert(test(std::ranges::remove, a, 42));