[libc++][ranges] Implement `std::ranges::partial_sort_copy`.

[var-const]

Fix the CI and rebase.

[huixie90]

libcxx/docs/Status/RangesAlgorithms.csv

62

can fill in the patch number

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

78

nit: would MoveOnly.hwork?

[ldionne]

LGTM % comments and CI

libcxx/include/__algorithm/partial_sort_copy.h

37

This is a pre-existing issue, but I think our implementation doesn't work for single-pass input iterators, since we go over the input range twice. Since this is a pre-existing issue, let's fix it after the dust has settled with the release, but let's please make sure to remember. We should start filing bugs for issues like this that we encounter, to make sure they are not forgotten.

55

As we discussed just now, IMO this is better since it shields __sort_heap & friends from having to know about projections. I don't have a strong preference though, I'll defer to your judgement/preference.

59

We are recomputing next(__first, __last) here, however this wouldn't work for a single-pass input iterator. Fortunately, we just computed that in the loop above, so it should be possible to extract it from there. Definitely not for this patch, as this will fail when we have a test for single-pass input iterators anyway.

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

1

This is part of another commit.

[huixie90]

libcxx/include/__algorithm/partial_sort_copy.h

37

@ldionne, Could you please clarify a bit more? the input range [__first, __last) seems to be iterated only once unless I missed anything?

59

@ldionne, I don't think we are recomputing it or multi-passing the range. __first at this stage is already pointing to very end if not the __last. We are never going to iterating from the beginning but only iterating from the point that we haven't iterated yet. or do I miss anything?

[var-const]

Address feedback and rebase.

libcxx/docs/Status/RangesAlgorithms.csv

62

Thanks!

libcxx/include/__algorithm/partial_sort_copy.h

37

In either case, I've added it to my backlog to prepare a robust test that we support single-pass input iterators in all the relevant algorithms.

55

Unfortunately, for this to work, __make_projected_comp would have to support C++03. I took a stab at it: https://reviews.llvm.org/D130611, and it's a bit ugly. Let's discuss in the linked patch -- I can submit it as a follow up.

59

From the offline discussion, this is probably unnecessary because __first should already point to __last. I'm a little reluctant to remove this from this patch, though -- it seems like it should be a no-op in that case, but if the assumption is somehow wrong, the function would be broken. I'll do a follow-up instead.

[var-const]

Rebase.

[var-const]

Address feedback (__make_projected now supports the C++03 mode).

[var-const]

Fix the CI.

[huixie90]

libcxx/include/__algorithm/make_projected.h

84–87

why is the enable_if logic written twice?
Also, usually for sfinae multiple overloads, we use non-type template parameter

template <class A, enable_if<C>* = nullptr>

[var-const]

Address feedback and rebase.

libcxx/include/__algorithm/make_projected.h

84–87

Thanks for spotting!

[var-const]

Fix the CI and rebase.

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,`D130070 <https://llvm.org/D130070>`_,✅
-Write,partial_sort_copy,Konstantin Varlamov,n/a,In progress
+Write,partial_sort_copy,Konstantin Varlamov,`D130532 <https://llvm.org/D130532>`_,✅
 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>`_,✅

libcxx/include/__algorithm/make_heap.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
 //
 //===----------------------------------------------------------------------===//
 

 #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 __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) {
+void __make_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;
   difference_type __n = __last - __first;
   if (__n > 1) {
     // start from the first parent, there is no need to consider children
     for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start) {
-        std::__sift_down<_AlgPolicy, _CompRef>(__first, __comp_ref, __n, __first + __start);
+        std::__sift_down<_AlgPolicy>(__first, __comp_ref, __n, __first + __start);
     }
   }
 }
 
 template <class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
   std::__make_heap<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp);

libcxx/include/__algorithm/make_projected.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_MAKE_PROJECTED_H
 #define _LIBCPP___ALGORITHM_MAKE_PROJECTED_H
 
 #include <__concepts/same_as.h>
 #include <__config>
 #include <__functional/identity.h>
 #include <__functional/invoke.h>
 #include <__type_traits/decay.h>
+#include <__type_traits/enable_if.h>
+#include <__type_traits/integral_constant.h>
 #include <__type_traits/is_member_pointer.h>
+#include <__type_traits/is_same.h>
+#include <__utility/declval.h>
 #include <__utility/forward.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 {
-
 template <class _Pred, class _Proj>
-_LIBCPP_HIDE_FROM_ABI constexpr static
-decltype(auto) __make_projected_pred(_Pred& __pred, _Proj& __proj) {
-  if constexpr (same_as<decay_t<_Proj>, identity> && !is_member_pointer_v<decay_t<_Pred>>) {
-    // Avoid creating the lambda and just use the pristine predicate -- for certain algorithms, this would enable
-    // optimizations that rely on the type of the predicate.
-    return __pred;
+struct _ProjectedPred {
+  _Pred& __pred; // Can be a unary or a binary predicate.
+  _Proj& __proj;
+
+  _LIBCPP_CONSTEXPR _ProjectedPred(_Pred& __pred_arg, _Proj& __proj_arg) : __pred(__pred_arg), __proj(__proj_arg) {}
+
+  template <class _Tp>
+  typename __invoke_of<_Pred&,
+                       decltype(std::__invoke(std::declval<_Proj&>(), std::declval<_Tp>()))
+  >::type
+  _LIBCPP_CONSTEXPR operator()(_Tp&& __v) const {
+    return std::__invoke(__pred, std::__invoke(__proj, std::forward<_Tp>(__v)));
+  }
+
+  template <class _T1, class _T2>
+  typename __invoke_of<_Pred&,
+                       decltype(std::__invoke(std::declval<_Proj&>(), std::declval<_T1>())),
+                       decltype(std::__invoke(std::declval<_Proj&>(), std::declval<_T2>()))
+  >::type
+  _LIBCPP_CONSTEXPR operator()(_T1&& __lhs, _T2&& __rhs) const {
+    return std::__invoke(__pred,
+                      std::__invoke(__proj, std::forward<_T1>(__lhs)),
+                      std::__invoke(__proj, std::forward<_T2>(__rhs)));
+  }
 
-  } else {
-    return [&](auto&& __x) {
-      return std::invoke(__pred, std::invoke(__proj, std::forward<decltype(__x)>(__x)));
-    };
-  }
-}
 
-template <class _Comp, class _Proj>
-_LIBCPP_HIDE_FROM_ABI constexpr static
-decltype(auto) __make_projected_comp(_Comp& __comp, _Proj& __proj) {
-  if constexpr (same_as<decay_t<_Proj>, identity> && !is_member_pointer_v<decay_t<_Comp>>) {
-    // Avoid creating the lambda and just use the pristine comparator -- for certain algorithms, this would enable
-    // optimizations that rely on the type of the comparator.
-    return __comp;
+template <class _Pred, class _Proj, class = void>
+struct __can_use_pristine_comp : false_type {};
 
-  } else {
-    return [&](auto&& __lhs, auto&& __rhs) {
-      return std::invoke(__comp,
-                        std::invoke(__proj, std::forward<decltype(__lhs)>(__lhs)),
-                        std::invoke(__proj, std::forward<decltype(__rhs)>(__rhs)));
-    };
-  }
+template <class _Pred, class _Proj>
+struct __can_use_pristine_comp<_Pred, _Proj, __enable_if_t<
+    !is_member_pointer<typename decay<_Pred>::type>::value && (
+#if _LIBCPP_STD_VER > 17
+      is_same<typename decay<_Proj>::type, identity>::value ||
+#endif
+      is_same<typename decay<_Proj>::type, __identity>::value
+    )
+> > : true_type {};
+
+template <class _Pred, class _Proj>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR static
+__enable_if_t<
+    !__can_use_pristine_comp<_Pred, _Proj>::value,
+    _ProjectedPred<_Pred, _Proj>
+>
+__make_projected(_Pred& __pred, _Proj& __proj) {
+  return _ProjectedPred<_Pred, _Proj>(__pred, __proj);
+}
+
+// Avoid creating the functor and just use the pristine comparator -- for certain algorithms, this would enable
+// optimizations that rely on the type of the comparator. Additionally, this results in less layers of indirection in
+// the call stack when the comparator is invoked, even in an unoptimized build.
+template <class _Pred, class _Proj, class = __enable_if_t<__can_use_pristine_comp<_Pred, _Proj>::value> >
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR static
+__enable_if_t<
+    __can_use_pristine_comp<_Pred, _Proj>::value,
+    _Pred&
+>
+__make_projected(_Pred& __pred, _Proj&) {
+  return __pred;
 }
 
+_LIBCPP_END_NAMESPACE_STD
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+
 template <class _Comp, class _Proj1, class _Proj2>
 _LIBCPP_HIDE_FROM_ABI constexpr static
 decltype(auto) __make_projected_comp(_Comp& __comp, _Proj1& __proj1, _Proj2& __proj2) {
   if constexpr (same_as<decay_t<_Proj1>, identity> && same_as<decay_t<_Proj2>, identity> &&
                 !is_member_pointer_v<decay_t<_Comp>>) {
     // Avoid creating the lambda and just use the pristine comparator -- for certain algorithms, this would enable
     // optimizations that rely on the type of the comparator.
     return __comp;

libcxx/include/__algorithm/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
 //
 //===----------------------------------------------------------------------===//
 

 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 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) {
+    _RandomAccessIterator __first, _RandomAccessIterator __middle, _Sentinel __last, _Compare&& __comp) {
   if (__first == __middle) {
     return _IterOps<_AlgPolicy>::next(__middle, __last);
   }
 
-  std::__make_heap<_AlgPolicy, _Compare>(__first, __middle, __comp);
+  std::__make_heap<_AlgPolicy>(__first, __middle, __comp);
 
   typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first;
   _RandomAccessIterator __i = __middle;
   for (; __i != __last; ++__i)
   {
       if (__comp(*__i, *__first))
       {
           _IterOps<_AlgPolicy>::iter_swap(__i, __first);
-          std::__sift_down<_AlgPolicy, _Compare>(__first, __comp, __len, __first);
+          std::__sift_down<_AlgPolicy>(__first, __comp, __len, __first);
       }
 
   }
-  std::__sort_heap<_AlgPolicy, _Compare>(std::move(__first), std::move(__middle), __comp);
+  std::__sort_heap<_AlgPolicy>(std::move(__first), std::move(__middle), __comp);
 
   return __i;
 }
 
 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::__debug_randomize_range<_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);
+  auto __last_iter = std::__partial_sort_impl<_AlgPolicy>(__first, __middle, __last, static_cast<_Comp_ref>(__comp));
 
   std::__debug_randomize_range<_AlgPolicy>(__middle, __last);
 
   return __last_iter;
 }
 
 template <class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17

libcxx/include/__algorithm/partial_sort_copy.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_PARTIAL_SORT_COPY_H
 #define _LIBCPP___ALGORITHM_PARTIAL_SORT_COPY_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/iterator_operations.h>
 #include <__algorithm/make_heap.h>
+#include <__algorithm/make_projected.h>
 #include <__algorithm/sift_down.h>
 #include <__algorithm/sort_heap.h>
 #include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
 #include <__iterator/iterator_traits.h>
+#include <__type_traits/is_callable.h>
+#include <__utility/move.h>
+#include <__utility/pair.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _AlgPolicy, class _Compare, class _InputIterator, class _RandomAccessIterator>
-_LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator
-__partial_sort_copy(_InputIterator __first, _InputIterator __last,
-                    _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
+template <class _AlgPolicy, class _Compare,
+          class _InputIterator, class _Sentinel1, class _RandomAccessIterator, class _Sentinel2,
+          class _Proj1, class _Proj2>
+_LIBCPP_CONSTEXPR_AFTER_CXX17 pair<_InputIterator, _RandomAccessIterator>
+__partial_sort_copy(_InputIterator __first, _Sentinel1 __last,
+                    _RandomAccessIterator __result_first, _Sentinel2 __result_last,
+                    _Compare&& __comp, _Proj1&& __proj1, _Proj2&& __proj2)
 {
     _RandomAccessIterator __r = __result_first;
+    auto&& __projected_comp = std::__make_projected(__comp, __proj2);
+
     if (__r != __result_last)
     {
         for (; __first != __last && __r != __result_last; ++__first, (void) ++__r)
             *__r = *__first;
-        std::__make_heap<_AlgPolicy, _Compare>(__result_first, __r, __comp);
+        std::__make_heap<_AlgPolicy>(__result_first, __r, __projected_comp);
         typename iterator_traits<_RandomAccessIterator>::difference_type __len = __r - __result_first;
         for (; __first != __last; ++__first)
-            if (__comp(*__first, *__result_first))
-            {
+            if (std::__invoke(__comp, std::__invoke(__proj1, *__first), std::__invoke(__proj2, *__result_first))) {
                 *__result_first = *__first;
-                std::__sift_down<_AlgPolicy, _Compare>(__result_first, __comp, __len, __result_first);
+                std::__sift_down<_AlgPolicy>(__result_first, __projected_comp, __len, __result_first);
             }
-        std::__sort_heap<_AlgPolicy, _Compare>(__result_first, __r, __comp);
+        std::__sort_heap<_AlgPolicy>(__result_first, __r, __projected_comp);
     }
-    return __r;
+
+    return pair<_InputIterator, _RandomAccessIterator>(
+        _IterOps<_AlgPolicy>::next(std::move(__first), std::move(__last)), std::move(__r));
 }
 
 template <class _InputIterator, class _RandomAccessIterator, class _Compare>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _RandomAccessIterator
 partial_sort_copy(_InputIterator __first, _InputIterator __last,
                   _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
 {
-    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-    return std::__partial_sort_copy<_ClassicAlgPolicy, _Comp_ref>(
-        __first, __last, __result_first, __result_last, __comp);
+  static_assert(__is_callable<_Compare, decltype(*__first), decltype(*__result_first)>::value,
+                "Comparator has to be callable");
+
+  using _Comp_ref = typename __comp_ref_type<_Compare>::type;
+  auto __result = std::__partial_sort_copy<_ClassicAlgPolicy>(__first, __last, __result_first, __result_last,
+      static_cast<_Comp_ref>(__comp), __identity(), __identity());
+  return __result.second;
 }
 
 template <class _InputIterator, class _RandomAccessIterator>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _RandomAccessIterator
 partial_sort_copy(_InputIterator __first, _InputIterator __last,
                   _RandomAccessIterator __result_first, _RandomAccessIterator __result_last)
 {
     return _VSTD::partial_sort_copy(__first, __last, __result_first, __result_last,
                                    __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_PARTIAL_SORT_COPY_H

libcxx/include/__algorithm/pop_heap.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
 //
 //===----------------------------------------------------------------------===//
 
void __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp,
   _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;
 
   using value_type = typename iterator_traits<_RandomAccessIterator>::value_type;
   if (__len > 1) {
     value_type __top = _IterOps<_AlgPolicy>::__iter_move(__first);  // create a hole at __first
-    _RandomAccessIterator __hole = std::__floyd_sift_down<_AlgPolicy, _CompRef>(__first, __comp_ref, __len);
+    _RandomAccessIterator __hole = std::__floyd_sift_down<_AlgPolicy>(__first, __comp_ref, __len);
     --__last;
 
     if (__hole == __last) {
       *__hole = std::move(__top);
     } else {
       *__hole = _IterOps<_AlgPolicy>::__iter_move(__last);
       ++__hole;
       *__last = std::move(__top);
-      std::__sift_up<_AlgPolicy, _CompRef>(__first, __hole, __comp_ref, __hole - __first);
+      std::__sift_up<_AlgPolicy>(__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.");

libcxx/include/__algorithm/push_heap.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
 //
 //===----------------------------------------------------------------------===//
 

 #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_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
-void __sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
+void __sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare&& __comp,
         typename iterator_traits<_RandomAccessIterator>::difference_type __len) {
   using value_type = typename iterator_traits<_RandomAccessIterator>::value_type;
 
   if (__len > 1) {
     __len = (__len - 2) / 2;
     _RandomAccessIterator __ptr = __first + __len;
 
     if (__comp(*__ptr, *--__last)) {

libcxx/include/__algorithm/ranges_is_heap.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
 //
 //===----------------------------------------------------------------------===//
 

 namespace __is_heap {
 
 struct __fn {
 
   template <class _Iter, class _Sent, class _Proj, class _Comp>
   _LIBCPP_HIDE_FROM_ABI constexpr
   static bool __is_heap_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) {
     auto __last_iter = ranges::next(__first, __last);
-    auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
+    auto&& __projected_comp = std::__make_projected(__comp, __proj);
 
     auto __result = std::__is_heap_until(std::move(__first), std::move(__last_iter), __projected_comp);
     return __result == __last;
   }
 
   template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Proj = identity,
             indirect_strict_weak_order<projected<_Iter, _Proj>> _Comp = ranges::less>
   _LIBCPP_HIDE_FROM_ABI constexpr

libcxx/include/__algorithm/ranges_is_heap_until.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
 //
 //===----------------------------------------------------------------------===//
 

 namespace __is_heap_until {
 
 struct __fn {
 
   template <class _Iter, class _Sent, class _Proj, class _Comp>
   _LIBCPP_HIDE_FROM_ABI constexpr
   static _Iter __is_heap_until_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) {
     auto __last_iter = ranges::next(__first, __last);
-    auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
+    auto&& __projected_comp = std::__make_projected(__comp, __proj);
 
     return std::__is_heap_until(std::move(__first), std::move(__last_iter), __projected_comp);
   }
 
   template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Proj = identity,
             indirect_strict_weak_order<projected<_Iter, _Proj>> _Comp = ranges::less>
   _LIBCPP_HIDE_FROM_ABI constexpr
   _Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {

libcxx/include/__algorithm/ranges_make_heap.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
 //
 //===----------------------------------------------------------------------===//
 

 namespace __make_heap {
 
 struct __fn {
   template <class _Iter, class _Sent, class _Comp, class _Proj>
   _LIBCPP_HIDE_FROM_ABI constexpr static
   _Iter __make_heap_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) {
     auto __last_iter = ranges::next(__first, __last);
 
-    auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
+    auto&& __projected_comp = std::__make_projected(__comp, __proj);
     std::__make_heap<_RangeAlgPolicy>(std::move(__first), __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

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

 namespace __nth_element {
 
 struct __fn {
   template <class _Iter, class _Sent, class _Comp, class _Proj>
   _LIBCPP_HIDE_FROM_ABI constexpr static
   _Iter __nth_element_fn_impl(_Iter __first, _Iter __nth, _Sent __last, _Comp& __comp, _Proj& __proj) {
     auto __last_iter = ranges::next(__first, __last);
 
-    auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
+    auto&& __projected_comp = std::__make_projected(__comp, __proj);
     std::__nth_element_impl<_RangeAlgPolicy>(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

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

 
 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);
+    auto&& __projected_comp = std::__make_projected(__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);

libcxx/include/__algorithm/ranges_partial_sort_copy.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_COPY_H
 #define _LIBCPP___ALGORITHM_RANGES_PARTIAL_SORT_COPY_H
 
 #include <__algorithm/in_out_result.h>
+#include <__algorithm/iterator_operations.h>
 #include <__algorithm/make_projected.h>
 #include <__algorithm/partial_sort_copy.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/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)
 
template <input_iterator _Iter1, sentinel_for<_Iter1> _Sent1,
             random_access_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
             class _Comp = ranges::less, class _Proj1 = identity, class _Proj2 = identity>
   requires indirectly_copyable<_Iter1, _Iter2> && sortable<_Iter2, _Comp, _Proj2> &&
            indirect_strict_weak_order<_Comp, projected<_Iter1, _Proj1>, projected<_Iter2, _Proj2>>
   _LIBCPP_HIDE_FROM_ABI constexpr
   partial_sort_copy_result<_Iter1, _Iter2>
   operator()(_Iter1 __first, _Sent1 __last, _Iter2 __result_first, _Sent2 __result_last,
              _Comp __comp = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const {
-    // TODO: implement
-    (void)__first; (void)__last; (void)__result_first; (void)__result_last; (void)__comp; (void)__proj1; (void)__proj2;
-    return {};
+    auto __result = std::__partial_sort_copy<_RangeAlgPolicy>(
+        std::move(__first), std::move(__last), std::move(__result_first), std::move(__result_last),
+        __comp, __proj1, __proj2
+    );
+    return {std::move(__result.first), std::move(__result.second)};
   }
 
   template <input_range _Range1, random_access_range _Range2, class _Comp = ranges::less,
             class _Proj1 = identity, class _Proj2 = identity>
   requires indirectly_copyable<iterator_t<_Range1>, iterator_t<_Range2>> &&
            sortable<iterator_t<_Range2>, _Comp, _Proj2> &&
            indirect_strict_weak_order<_Comp, projected<iterator_t<_Range1>, _Proj1>,
                                       projected<iterator_t<_Range2>, _Proj2>>
   _LIBCPP_HIDE_FROM_ABI constexpr
   partial_sort_copy_result<borrowed_iterator_t<_Range1>, borrowed_iterator_t<_Range2>>
   operator()(_Range1&& __range, _Range2&& __result_range, _Comp __comp = {},
              _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const {
-    // TODO: implement
-    (void)__range; (void)__result_range; (void)__comp; (void)__proj1; (void)__proj2;
-    return {};
+    auto __result = std::__partial_sort_copy<_RangeAlgPolicy>(
+        ranges::begin(__range), ranges::end(__range), ranges::begin(__result_range), ranges::end(__result_range),
+        __comp, __proj1, __proj2
+    );
+    return {std::move(__result.first), std::move(__result.second)};
   }
 
 };
 
 } // namespace __partial_sort_copy
 
 inline namespace __cpo {
   inline constexpr auto partial_sort_copy = __partial_sort_copy::__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_COPY_H

libcxx/include/__algorithm/ranges_partition.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
 //
 //===----------------------------------------------------------------------===//
 

 namespace ranges {
 namespace __partition {
 
 struct __fn {
 
   template <class _Iter, class _Sent, class _Proj, class _Pred>
   _LIBCPP_HIDE_FROM_ABI static constexpr
   subrange<__uncvref_t<_Iter>> __partition_fn_impl(_Iter&& __first, _Sent&& __last, _Pred&& __pred, _Proj&& __proj) {
-    auto&& __projected_pred = ranges::__make_projected_pred(__pred, __proj);
+    auto&& __projected_pred = std::__make_projected(__pred, __proj);
     auto __result = std::__partition<_RangeAlgPolicy>(
         std::move(__first), std::move(__last), __projected_pred, __iterator_concept<_Iter>());
 
     return {std::move(__result.first), std::move(__result.second)};
   }
 
   template <permutable _Iter, sentinel_for<_Iter> _Sent, class _Proj = identity,
             indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>

libcxx/include/__algorithm/ranges_pop_heap.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
 //
 //===----------------------------------------------------------------------===//
 

 
 struct __fn {
   template <class _Iter, class _Sent, class _Comp, class _Proj>
   _LIBCPP_HIDE_FROM_ABI constexpr static
   _Iter __pop_heap_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) {
     auto __last_iter = ranges::next(__first, __last);
     auto __len = __last_iter - __first;
 
-    auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
+    auto&& __projected_comp = std::__make_projected(__comp, __proj);
     std::__pop_heap<_RangeAlgPolicy>(std::move(__first), __last_iter, __projected_comp, __len);
 
     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

libcxx/include/__algorithm/ranges_push_heap.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
 //
 //===----------------------------------------------------------------------===//
 

 namespace __push_heap {
 
 struct __fn {
   template <class _Iter, class _Sent, class _Comp, class _Proj>
   _LIBCPP_HIDE_FROM_ABI constexpr static
   _Iter __push_heap_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) {
     auto __last_iter = ranges::next(__first, __last);
 
-    auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
+    auto&& __projected_comp = std::__make_projected(__comp, __proj);
     std::__push_heap<_RangeAlgPolicy>(std::move(__first), __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

libcxx/include/__algorithm/ranges_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
 //
 //===----------------------------------------------------------------------===//
 

 namespace __sort {
 
 struct __fn {
   template <class _Iter, class _Sent, class _Comp, class _Proj>
   _LIBCPP_HIDE_FROM_ABI constexpr static
   _Iter __sort_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) {
     auto __last_iter = ranges::next(__first, __last);
 
-    auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
+    auto&& __projected_comp = std::__make_projected(__comp, __proj);
     std::__sort_impl<_RangeAlgPolicy>(std::move(__first), __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

libcxx/include/__algorithm/ranges_sort_heap.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
 //
 //===----------------------------------------------------------------------===//
 

 namespace __sort_heap {
 
 struct __fn {
   template <class _Iter, class _Sent, class _Comp, class _Proj>
   _LIBCPP_HIDE_FROM_ABI constexpr static
   _Iter __sort_heap_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) {
     auto __last_iter = ranges::next(__first, __last);
 
-    auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
+    auto&& __projected_comp = std::__make_projected(__comp, __proj);
     std::__sort_heap<_RangeAlgPolicy>(std::move(__first), __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

libcxx/include/__algorithm/ranges_stable_partition.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
 //
 //===----------------------------------------------------------------------===//
 

 struct __fn {
 
   template <class _Iter, class _Sent, class _Proj, class _Pred>
   _LIBCPP_HIDE_FROM_ABI static
   subrange<__uncvref_t<_Iter>> __stable_partition_fn_impl(
       _Iter&& __first, _Sent&& __last, _Pred&& __pred, _Proj&& __proj) {
     auto __last_iter = ranges::next(__first, __last);
 
-    auto&& __projected_pred = ranges::__make_projected_pred(__pred, __proj);
+    auto&& __projected_pred = std::__make_projected(__pred, __proj);
     auto __result = std::__stable_partition<_RangeAlgPolicy>(
         std::move(__first), __last_iter, __projected_pred, __iterator_concept<_Iter>());
 
     return {std::move(__result), std::move(__last_iter)};
   }
 
   template <bidirectional_iterator _Iter, sentinel_for<_Iter> _Sent, class _Proj = identity,
             indirect_unary_predicate<projected<_Iter, _Proj>> _Pred>

libcxx/include/__algorithm/ranges_stable_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
 //
 //===----------------------------------------------------------------------===//
 

 namespace __stable_sort {
 
 struct __fn {
   template <class _Iter, class _Sent, class _Comp, class _Proj>
   _LIBCPP_HIDE_FROM_ABI
   static _Iter __stable_sort_fn_impl(_Iter __first, _Sent __last, _Comp& __comp, _Proj& __proj) {
     auto __last_iter = ranges::next(__first, __last);
 
-    auto&& __projected_comp = ranges::__make_projected_comp(__comp, __proj);
+    auto&& __projected_comp = std::__make_projected(__comp, __proj);
     std::__stable_sort_impl<_RangeAlgPolicy>(std::move(__first), __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

libcxx/include/__algorithm/sift_down.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
 //
 //===----------------------------------------------------------------------===//
 

 #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_CXX11 void
-__sift_down(_RandomAccessIterator __first, _Compare __comp,
+__sift_down(_RandomAccessIterator __first, _Compare&& __comp,
             typename iterator_traits<_RandomAccessIterator>::difference_type __len,
             _RandomAccessIterator __start)
 {
     using _Ops = _IterOps<_AlgPolicy>;
 
     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
     // left-child of __start is at 2 * __start + 1
do
 
         // check if we are in heap-order
     } while (!__comp(*__child_i, __top));
     *__start = _VSTD::move(__top);
 }
 
 template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
 _LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator
-__floyd_sift_down(_RandomAccessIterator __first, _Compare __comp,
+__floyd_sift_down(_RandomAccessIterator __first, _Compare&& __comp,
                   typename iterator_traits<_RandomAccessIterator>::difference_type __len)
 {
     using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type;
     _LIBCPP_ASSERT(__len >= 2, "shouldn't be called unless __len >= 2");
 
     _RandomAccessIterator __hole = __first;
     _RandomAccessIterator __child_i = __first;
     difference_type __child = 0;

libcxx/include/__algorithm/sort_heap.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
 //
 //===----------------------------------------------------------------------===//
 

 #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) {
+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);
+    std::__pop_heap<_AlgPolicy>(__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.");
 

libcxx/include/algorithm

template<input_range R1, input_range R2, class Pred = ranges::equal_to,
   template<input_iterator I, sentinel_for<I> S, class Proj = identity,
            indirect_unary_predicate<projected<I, Proj>> Pred>
     constexpr bool ranges::none_of(I first, S last, Pred pred, Proj proj = {});     // since C++20
 
   template<input_range R, class Proj = identity,
            indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
     constexpr bool ranges::none_of(R&& r, Pred pred, Proj proj = {});               // since C++20
 
+  template<input_iterator I1, sentinel_for<I1> S1,
+          random_access_iterator I2, sentinel_for<I2> S2,
+          class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
+    requires indirectly_copyable<I1, I2> && sortable<I2, Comp, Proj2> &&
+            indirect_strict_weak_order<Comp, projected<I1, Proj1>, projected<I2, Proj2>>
+    constexpr partial_sort_copy_result<I1, I2>
+      partial_sort_copy(I1 first, S1 last, I2 result_first, S2 result_last,
+                        Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});        // Since C++20
+
+  template<input_range R1, random_access_range R2, class Comp = ranges::less,
+          class Proj1 = identity, class Proj2 = identity>
+    requires indirectly_copyable<iterator_t<R1>, iterator_t<R2>> &&
+            sortable<iterator_t<R2>, Comp, Proj2> &&
+            indirect_strict_weak_order<Comp, projected<iterator_t<R1>, Proj1>,
+                                        projected<iterator_t<R2>, Proj2>>
+    constexpr partial_sort_copy_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
+      partial_sort_copy(R1&& r, R2&& result_r, Comp comp = {},
+                        Proj1 proj1 = {}, Proj2 proj2 = {});                        // Since C++20
+
   template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
            indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
     constexpr bool ranges::is_sorted(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 bool ranges::is_sorted(R&& r, Comp comp = {}, Proj proj = {});                // since C++20
 

 #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_partial_sort_copy.h>
 #include <__algorithm/ranges_partition.h>
 #include <__algorithm/ranges_partition_copy.h>
 #include <__algorithm/ranges_partition_point.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>

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::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_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::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);
     (void)std::ranges::pop_heap(first, last, Less(&copies)); assert(copies == 0);
     (void)std::ranges::pop_heap(a, Less(&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::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_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::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);
     (void)std::ranges::pop_heap(first, last, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::pop_heap(a, Less(), Proj(&copies)); assert(copies == 0);

libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort.copy/ranges_partial_sort_copy.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<input_iterator I1, sentinel_for<I1> S1,
-//              random_access_iterator I2, sentinel_for<I2> S2,
-//              class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
-//       requires indirectly_copyable<I1, I2> && sortable<I2, Comp, Proj2> &&
-//                indirect_strict_weak_order<Comp, projected<I1, Proj1>, projected<I2, Proj2>>
-//       constexpr partial_sort_copy_result<I1, I2>
-//         partial_sort_copy(I1 first, S1 last, I2 result_first, S2 result_last,
-//                           Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});                   // Since C++20
+//          random_access_iterator I2, sentinel_for<I2> S2,
+//          class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
+//   requires indirectly_copyable<I1, I2> && sortable<I2, Comp, Proj2> &&
+//            indirect_strict_weak_order<Comp, projected<I1, Proj1>, projected<I2, Proj2>>
+//   constexpr partial_sort_copy_result<I1, I2>
+//     partial_sort_copy(I1 first, S1 last, I2 result_first, S2 result_last,
+//                       Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});               // Since C++20
 //
-//     template<input_range R1, random_access_range R2, class Comp = ranges::less,
-//              class Proj1 = identity, class Proj2 = identity>
-//       requires indirectly_copyable<iterator_t<R1>, iterator_t<R2>> &&
-//                sortable<iterator_t<R2>, Comp, Proj2> &&
-//                indirect_strict_weak_order<Comp, projected<iterator_t<R1>, Proj1>,
-//                                           projected<iterator_t<R2>, Proj2>>
-//       constexpr partial_sort_copy_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
-//         partial_sort_copy(R1&& r, R2&& result_r, Comp comp = {},
-//                           Proj1 proj1 = {}, Proj2 proj2 = {});                                   // Since C++20
+// template<input_range R1, random_access_range R2, class Comp = ranges::less,
+//          class Proj1 = identity, class Proj2 = identity>
+//   requires indirectly_copyable<iterator_t<R1>, iterator_t<R2>> &&
+//            sortable<iterator_t<R2>, Comp, Proj2> &&
+//            indirect_strict_weak_order<Comp, projected<iterator_t<R1>, Proj1>,
+//                                       projected<iterator_t<R2>, Proj2>>
+//   constexpr partial_sort_copy_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
+//     partial_sort_copy(R1&& r, R2&& result_r, Comp comp = {},
+//                       Proj1 proj1 = {}, Proj2 proj2 = {});                               // Since C++20
 
 #include <algorithm>
 #include <array>
 #include <concepts>
 #include <functional>
 #include <ranges>
+#include <utility>
 
+#include "MoveOnly.h"
 #include "almost_satisfies_types.h"
 #include "test_iterators.h"
 
-// TODO: SFINAE tests.
+// Test constraints of the (iterator, sentinel) overload.
+// ======================================================
+
+template <class Iter1 = int*, class Sent1 = int*, class Iter2 = int*, class Sent2 = int*,
+          class Comp = std::ranges::less>
+concept HasPartialSortCopyIter =
+    requires(Iter1&& first1, Sent1&& last1, Iter2&& first2, Sent2&& last2, Comp&& comp) {
+      std::ranges::partial_sort_copy(std::forward<Iter1>(first1), std::forward<Sent1>(last1),
+          std::forward<Iter2>(first2), std::forward<Sent2>(last2), std::forward<Comp>(comp));
+    };
+
+static_assert(HasPartialSortCopyIter<int*, int*, int*, int*, std::ranges::less>);
+
+// !input_iterator<I1>
+static_assert(!HasPartialSortCopyIter<InputIteratorNotDerivedFrom>);
+static_assert(!HasPartialSortCopyIter<InputIteratorNotIndirectlyReadable>);
+static_assert(!HasPartialSortCopyIter<InputIteratorNotInputOrOutputIterator>);
+
+// !sentinel_for<S1, I1>
+static_assert(!HasPartialSortCopyIter<int*, SentinelForNotSemiregular>);
+static_assert(!HasPartialSortCopyIter<int*, SentinelForNotWeaklyEqualityComparableWith>);
+
+// !random_access_iterator<I2>
+static_assert(!HasPartialSortCopyIter<int*, int*, RandomAccessIteratorNotDerivedFrom>);
+static_assert(!HasPartialSortCopyIter<int*, int*, RandomAccessIteratorBadIndex>);
+
+// !sentinel_for<S2, I2>
+static_assert(!HasPartialSortCopyIter<int*, int*, int*, SentinelForNotSemiregular>);
+static_assert(!HasPartialSortCopyIter<int*, int*, int*, SentinelForNotWeaklyEqualityComparableWith>);
+
+// !indirect_unary_predicate<projected<I, Proj>>
+static_assert(!HasPartialSortCopyIter<int*, int*, int*, int*, IndirectUnaryPredicateNotPredicate>);
+static_assert(!HasPartialSortCopyIter<int*, int*, int*, int*, IndirectUnaryPredicateNotCopyConstructible>);
+
+// !indirectly_copyable<I1, I2>
+static_assert(!HasPartialSortCopyIter<int*, int*, MoveOnly*>);
+
+// !sortable<I2, Comp, Proj2>
+static_assert(!HasPartialSortCopyIter<int*, int*, const int*, const int*>);
+
+struct NoComparator {};
+// !indirect_strict_weak_order<Comp, projected<I1, Proj1>, projected<I2, Proj2>>
+static_assert(!HasPartialSortCopyIter<NoComparator*, NoComparator*, NoComparator*, NoComparator*>);
+
+// Test constraints of the (range) overload.
+// ======================================================
+
+template <class T>
+using R = UncheckedRange<T>;
+
+template <class Range1 = R<int*>, class Range2 = R<int*>, class Comp = std::ranges::less>
+concept HasPartialSortCopyRange =
+    requires(Range1&& range1, Range2&& range2, Comp&& comp) {
+      std::ranges::partial_sort_copy(std::forward<Range1>(range1), std::forward<Range2>(range2),
+          std::forward<Comp>(comp));
+    };
+
+static_assert(HasPartialSortCopyRange<R<int*>, R<int*>, std::ranges::less>);
+
+// !input_range<R1>
+static_assert(!HasPartialSortCopyRange<InputRangeNotDerivedFrom>);
+static_assert(!HasPartialSortCopyRange<InputRangeNotIndirectlyReadable>);
+static_assert(!HasPartialSortCopyRange<InputRangeNotInputOrOutputIterator>);
+
+// !random_access_range<R2>
+static_assert(!HasPartialSortCopyRange<R<int*>, RandomAccessRangeNotDerivedFrom>);
+static_assert(!HasPartialSortCopyRange<R<int*>, RandomAccessRangeBadIndex>);
+
+// !indirectly_copyable<iterator_t<R1>, iterator_t<R2>>
+static_assert(!HasPartialSortCopyRange<R<int*>, R<MoveOnly*>>);
+
+// !sortable<iterator_t<R2>, Comp, Proj2>
+static_assert(!HasPartialSortCopyRange<R<int*>, R<const int*>>);
+
+// !indirect_strict_weak_order<Comp, projected<iterator_t<R1>, Proj1>, projected<iterator_t<R2>, Proj2>>
+static_assert(!HasPartialSortCopyRange<R<NoComparator*>, R<NoComparator*>>);
+
+static_assert(std::is_same_v<std::ranges::partial_sort_copy_result<int, int>, std::ranges::in_out_result<int, int>>);
+
+template <class Iter, class Sent, class OutIter, class OutSent, size_t N>
+constexpr void test_one(
+    std::array<int, N> input, size_t input_size, size_t output_size, std::array<int, N> sorted) {
+  assert(input_size <= N);
+  assert(output_size <= N + 1); // To support testing the case where output size exceeds input size.
+
+  using ResultT = std::ranges::partial_sort_copy_result<Iter, OutIter>;
+  // To support testing the case where output size exceeds input size; also makes sure calling `out.data() + int()` is
+  // valid.
+  constexpr size_t OutputSize = N + 1;
+  size_t result_size = std::ranges::min(input_size, output_size);
+
+  auto begin = input.data();
+  auto end = input.data() + input_size;
+
+  { // (iterator, sentinel) overload.
+    std::array<int, OutputSize> out;
+    auto out_begin = out.data();
+    auto out_end = out.data() + output_size;
+
+    std::same_as<ResultT> decltype(auto) result = std::ranges::partial_sort_copy(
+        Iter(begin), Sent(Iter(end)), OutIter(out_begin), OutSent(OutIter(out_end)));
+
+    assert(base(result.in) == input.data() + input_size);
+    assert(base(result.out) == out.data() + result_size);
+
+    assert(std::ranges::equal(std::ranges::subrange(out.begin(), out.begin() + result_size),
+           std::ranges::subrange(sorted.begin(), sorted.begin() + result_size)));
+  }
+
+  { // (range) overload.
+    std::array<int, OutputSize> out;
+    auto out_begin = out.data();
+    auto out_end = out.data() + output_size;
+    auto in_range = std::ranges::subrange(Iter(begin), Sent(Iter(end)));
+    auto out_range = std::ranges::subrange(OutIter(out_begin), OutSent(OutIter(out_end)));
+
+    std::same_as<ResultT> decltype(auto) result = std::ranges::partial_sort_copy(in_range, out_range);
+
+    assert(base(result.in) == input.data() + input_size);
+    assert(base(result.out) == out.data() + result_size);
+
+    assert(std::ranges::equal(std::ranges::subrange(out.begin(), out.begin() + result_size),
+           std::ranges::subrange(sorted.begin(), sorted.begin() + result_size)));
+  }
+
+}
+
+template <class Iter, class Sent, class OutIter, class OutSent, size_t N>
+constexpr void test_all_subsequences(const std::array<int, N> input) {
+  auto sorted = input;
+  std::sort(sorted.begin(), sorted.end());
+
+  // Whole input, increasing output size. Also check the case when `output_size` exceeds input size.
+  for (size_t out_size = 0; out_size <= N + 1; ++out_size) {
+    test_one<Iter, Sent, OutIter, OutSent>(input, N, out_size, sorted);
+  }
+}
+
+template <class InIter, class Sent1, class OutIter, class Sent2>
+constexpr void test_iterators_in_sent1_out_sent2() {
+  // Empty sequence.
+  test_all_subsequences<InIter, Sent1, OutIter, Sent2, 0>({});
+
+  // 1-element sequence.
+  test_all_subsequences<InIter, Sent1, OutIter, Sent2>(std::array{1});
+
+  // 2-element sequence.
+  test_all_subsequences<InIter, Sent1, OutIter, Sent2>(std::array{2, 1});
+
+  // 3-element sequence.
+  test_all_subsequences<InIter, Sent1, OutIter, Sent2>(std::array{2, 1, 3});
+
+  // Longer sequence.
+  test_all_subsequences<InIter, Sent1, OutIter, Sent2>(std::array{2, 1, 3, 6, 8, 4, 11, 5});
+
+  // Longer sequence with duplicates.
+  test_all_subsequences<InIter, Sent1, OutIter, Sent2>(std::array{2, 1, 3, 6, 2, 8, 6});
+
+  // All elements are the same.
+  test_all_subsequences<InIter, Sent1, OutIter, Sent2>(std::array{1, 1, 1});
+
+  // Already sorted.
+  test_all_subsequences<InIter, Sent1, OutIter, Sent2>(std::array{1, 2, 3, 4, 5});
+
+  // Descending.
+  test_all_subsequences<InIter, Sent1, OutIter, Sent2>(std::array{5, 4, 3, 2, 1});
+}
+
+template <class InIter, class Sent1, class OutIter>
+constexpr void test_iterators_in_sent1_out() {
+  test_iterators_in_sent1_out_sent2<InIter, Sent1, OutIter, OutIter>();
+  test_iterators_in_sent1_out_sent2<InIter, Sent1, OutIter, sentinel_wrapper<OutIter>>();
+}
+
+template <class InIter, class Sent1>
+constexpr void test_iterators_in_sent1() {
+  test_iterators_in_sent1_out<InIter, Sent1, random_access_iterator<int*>>();
+}
+
+template <class InIter>
+constexpr void test_iterators_in() {
+  if constexpr (std::sentinel_for<InIter, InIter>) {
+    test_iterators_in_sent1<InIter, InIter>();
+  }
+  test_iterators_in_sent1<InIter, sentinel_wrapper<InIter>>();
+}
+
+constexpr void test_iterators() {
+  test_iterators_in<cpp20_input_iterator<int*>>();
+  // Omitting other iterator types to reduce the combinatorial explosion.
+  test_iterators_in<random_access_iterator<int*>>();
+  test_iterators_in<const int*>();
+}
 
 constexpr bool test() {
-  // TODO: main tests.
-  // TODO: A custom comparator works.
-  // TODO: A custom projection works.
+  test_iterators();
+
+  { // A custom comparator works.
+    const std::array in = {1, 2, 3, 4, 5};
+    std::ranges::greater comp;
+
+    {
+      std::array<int, 2> out;
+
+      auto result = std::ranges::partial_sort_copy(in.begin(), in.end(), out.begin(), out.end(), comp);
+      assert(std::ranges::equal(std::ranges::subrange(out.begin(), result.out), std::array{5, 4}));
+    }
+
+    {
+      std::array<int, 2> out;
+
+      auto result = std::ranges::partial_sort_copy(in, out, comp);
+      assert(std::ranges::equal(std::ranges::subrange(out.begin(), result.out), std::array{5, 4}));
+    }
+  }
+
+  { // A custom projection works.
+    struct A {
+      int a;
+
+      constexpr A() = default;
+      constexpr A(int value) : a(value) {}
+      constexpr auto operator<=>(const A&) const = default;
+    };
+
+    const std::array in = {2, 1, 3};
+    auto proj1 = [](int value) { return value * -1; };
+    auto proj2 = [](A value) { return value.a * -1; };
+    // The projections negate the argument, so the array will appear to be sorted in descending order: [3, 2, 1]
+    // (the projections make it appear to the algorithm as [-3, -2, -1]).
+
+    {
+      std::array<A, 2> out;
+
+      // No projections: ascending order.
+      auto result = std::ranges::partial_sort_copy(in.begin(), in.end(), out.begin(), out.end(), {});
+      assert(std::ranges::equal(std::ranges::subrange(out.begin(), result.out), std::array{1, 2}));
+      // Using projections: descending order.
+      result = std::ranges::partial_sort_copy(in.begin(), in.end(), out.begin(), out.end(), {}, proj1, proj2);
+      assert(std::ranges::equal(std::ranges::subrange(out.begin(), result.out), std::array{3, 2}));
+    }
+
+    {
+      std::array<int, 2> out;
+
+      auto result = std::ranges::partial_sort_copy(in, out, {});
+      assert(std::ranges::equal(std::ranges::subrange(out.begin(), result.out), std::array{1, 2}));
+      result = std::ranges::partial_sort_copy(in, out, {}, proj1, proj2);
+      assert(std::ranges::equal(std::ranges::subrange(out.begin(), result.out), std::array{3, 2}));
+    }
+  }
 
   return true;
 }
 
 int main(int, char**) {
   test();
   static_assert(test());
 
   return 0;
 }

libcxx/test/std/algorithms/ranges_result_alias_declarations.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(std::is_same_v<in_in_result<int, long>, swap_ranges_result<int, long>>);
 
 static_assert(std::is_same_v<in_out_result<int, long>, copy_result<int, long>>);
 static_assert(std::is_same_v<in_out_result<int, long>, copy_n_result<int, long>>);
 static_assert(std::is_same_v<in_out_result<int, long>, copy_if_result<int, long>>);
 static_assert(std::is_same_v<in_out_result<int, long>, copy_backward_result<int, long>>);
 static_assert(std::is_same_v<in_out_result<int, long>, move_result<int, long>>);
 static_assert(std::is_same_v<in_out_result<int, long>, move_backward_result<int, long>>);
-// static_assert(std::is_same_v<in_out_result<int, long>, partial_sort_copy_result<int, long>>);
+static_assert(std::is_same_v<in_out_result<int, long>, partial_sort_copy_result<int, long>>);
 // static_assert(std::is_same_v<in_out_result<int, long>, remove_copy_result<int, long>>);
 // static_assert(std::is_same_v<in_out_result<int, long>, remove_copy_if_result<int, long>>);
 // static_assert(std::is_same_v<in_out_result<int, long>, replace_copy_result<int, long>>);
 // static_assert(std::is_same_v<in_out_result<int, long>, replace_copy_if_result<int, long>>);
 // static_assert(std::is_same_v<in_out_result<int, long>, reverse_copy_result<int, long>>);
 // static_assert(std::is_same_v<in_out_result<int, long>, rotate_copy_result<int, long>>);
 static_assert(std::is_same_v<in_out_result<int, long>, set_difference_result<int, long>>);
 static_assert(std::is_same_v<in_out_result<int, long>, unary_transform_result<int, long>>);

libcxx/test/std/algorithms/ranges_robust_against_dangling.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
 //
 //===----------------------------------------------------------------------===//
 
constexpr bool test_all() {
   //using std::ranges::copy_backward_result;
   using std::ranges::copy_if_result;
   using std::ranges::for_each_result;
   using std::ranges::merge_result;
   using std::ranges::minmax_result;
   using std::ranges::mismatch_result;
   using std::ranges::move_result;
   //using std::ranges::move_backward_result;
-  //using std::ranges::partial_sort_copy_result;
+  using std::ranges::partial_sort_copy_result;
   using std::ranges::partition_copy_result;
   //using std::ranges::remove_copy_result;
   //using std::ranges::remove_copy_if_result;
   using std::ranges::reverse_copy_result;
   using std::ranges::rotate_copy_result;
   using std::ranges::set_difference_result;
   using std::ranges::set_intersection_result;
   using std::ranges::set_symmetric_difference_result;
constexpr bool test_all() {
   //dangling_1st(std::ranges::replace_copy_if, in, out, x, x);
   dangling_1st<swap_ranges_result<dangling, int*>>(std::ranges::swap_ranges, in, in2);
   dangling_2nd<swap_ranges_result<int*, dangling>>(std::ranges::swap_ranges, in, in2);
   dangling_both<swap_ranges_result<dangling, dangling>>(std::ranges::swap_ranges, in, in2);
   dangling_1st<reverse_copy_result<dangling, int*>>(std::ranges::reverse_copy, in, out);
   dangling_1st<rotate_copy_result<dangling, int*>>(std::ranges::rotate_copy, in, mid, out);
   //dangling_1st<unique_copy_result<dangling, int*>>(std::ranges::unique_copy, in, out);
   dangling_1st<partition_copy_result<dangling, int*, int*>>(std::ranges::partition_copy, in, out, out2, unary_pred);
-  //dangling_1st<partial_sort_copy_result<dangling, int*>>(std::ranges::partial_sort_copy, in, in2);
-  //dangling_2nd<partial_sort_copy_result<int*, dangling>>(std::ranges::partial_sort_copy, in, in2);
-  //dangling_both<partial_sort_copy_result<dangling, dangling>>(std::ranges::partial_sort_copy, in, in2);
+  dangling_1st<partial_sort_copy_result<dangling, int*>>(std::ranges::partial_sort_copy, in, in2);
+  dangling_2nd<partial_sort_copy_result<int*, dangling>>(std::ranges::partial_sort_copy, in, in2);
+  dangling_both<partial_sort_copy_result<dangling, dangling>>(std::ranges::partial_sort_copy, in, in2);
   dangling_1st<merge_result<dangling, int*, int*>>(std::ranges::merge, in, in2, out);
   dangling_2nd<merge_result<int*, dangling, int*>>(std::ranges::merge, in, in2, out);
   dangling_both<merge_result<dangling, dangling, int*>>(std::ranges::merge, in, in2, out);
   dangling_1st<set_difference_result<dangling, int*>>(std::ranges::set_difference, in, in2, out);
   dangling_1st<set_intersection_result<dangling, int*, int*>>(std::ranges::set_intersection, in, in2, out);
   dangling_2nd<set_intersection_result<int*, dangling, int*>>(std::ranges::set_intersection, in, in2, out);
   dangling_both<set_intersection_result<dangling, dangling, int*>>(std::ranges::set_intersection, in, in2, out);
   dangling_1st<set_symmetric_difference_result<dangling, int*, int*>>(

libcxx/test/std/algorithms/ranges_robust_against_differing_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
 //
 //===----------------------------------------------------------------------===//
 
 // UNSUPPORTED: c++03, c++11, c++14, c++17
constexpr bool test_all() {
   //test(std::ranges::is_permutation, in, in2, eq, proj1, proj2);
   test(std::ranges::includes, in, in2, less, proj1, proj2);
   test(std::ranges::find_first_of, in, in2, eq, proj1, proj2);
   test(std::ranges::mismatch, in, in2, eq, proj1, proj2);
   test(std::ranges::search, in, in2, eq, proj1, proj2);
   test(std::ranges::find_end, in, in2, eq, proj1, proj2);
   test(std::ranges::transform, in, in2, out, sum, proj1, proj2);
   test(std::ranges::transform, in, in2, out2, sum, proj1, proj2);
-  //test(std::ranges::partial_sort_copy, in, in2, output2.begin(), output2.end(), less, proj1, proj2);
+  test(std::ranges::partial_sort_copy, in, in2, less, proj1, proj2);
   test(std::ranges::merge, in, in2, out, less, proj1, proj2);
   test(std::ranges::merge, in, in2, out2, less, proj1, proj2);
   test(std::ranges::set_intersection, in, in2, out, less, proj1, proj2);
   test(std::ranges::set_intersection, in, in2, out2, less, proj1, proj2);
   test(std::ranges::set_difference, in, in2, out, less, proj1, proj2);
   test(std::ranges::set_difference, in, in2, out2, less, proj1, proj2);
   test(std::ranges::set_symmetric_difference, in, in2, out, less, proj1, proj2);
   test(std::ranges::set_symmetric_difference, in, in2, out2, less, proj1, proj2);
   test(std::ranges::set_union, in, in2, out, less, proj1, proj2);
   test(std::ranges::set_union, in, in2, out2, less, proj1, proj2);
+  //test(std::ranges::starts_with, in, in2, eq, proj1, proj2);
+  //test(std::ranges::ends_with, in, in2, eq, proj1, proj2);
 
   return true;
 }
 
 int main(int, char**) {
   test_all();
   static_assert(test_all());
 
   return 0;
 }

libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.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
 //
 //===----------------------------------------------------------------------===//
 
constexpr bool test_all() {
   //std::ranges::clamp(2, 1, 3, binary_pred);
   //test(std::ranges::is_permutation, in, in2, binary_pred);
   test(std::ranges::copy_if, in, out, unary_pred);
   //test(std::ranges::remove_copy_if, in, out, unary_pred);
   test(std::ranges::replace_if, in, unary_pred, x);
   //test(std::ranges::replace_copy_if, in, out, unary_pred, x);
   //test(std::ranges::unique_copy, in, out, binary_pred);
   test(std::ranges::partition_copy, in, out, out2, unary_pred);
-  //test(std::ranges::partial_sort_copy, in, in2, binary_pred);
+  test(std::ranges::partial_sort_copy, in, in2, binary_pred);
   test(std::ranges::merge, in, in2, out, binary_pred);
   test(std::ranges::set_difference, in, in2, out, binary_pred);
   test(std::ranges::set_intersection, in, in2, out, binary_pred);
   test(std::ranges::set_symmetric_difference, in, in2, out, binary_pred);
   test(std::ranges::set_union, in, in2, out, binary_pred);
   test(std::ranges::remove_if, in, unary_pred);
   //test(std::ranges::unique, in, binary_pred);
   test(std::ranges::partition, in, unary_pred);

libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.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
 //
 //===----------------------------------------------------------------------===//
 
constexpr bool test_all() {
   //test(std::ranges::replace_copy, in, out, x, a, &Bar::val);
   //test(std::ranges::replace_copy_if, in, out, pred, a, &Bar::val);
   // `swap_ranges` has neither a projection nor a predicate.
   // `reverse_copy` has neither a projection nor a predicate.
   // `rotate_copy` has neither a projection nor a predicate.
   // `sample` has no requirement that the given generator be invoked via `std::invoke`.
   //test(std::ranges::unique_copy, in, out, &Foo::binary_pred, &Bar::val);
   test(std::ranges::partition_copy, in, out, out2, &Foo::unary_pred, &Bar::val);
-  //test(std::ranges::partial_sort_copy, in, in2, &Foo::binary_pred, &Bar::val);
+  test(std::ranges::partial_sort_copy, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
   test(std::ranges::merge, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val);
   test(std::ranges::set_difference, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val);
   test(std::ranges::set_intersection, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val);
   test(std::ranges::set_symmetric_difference, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val);
   test(std::ranges::set_union, in, in2, out, &Foo::binary_pred, &Bar::val, &Bar::val);
   test(std::ranges::remove, in, x, &Bar::val);
   test(std::ranges::remove_if, in, &Foo::unary_pred, &Bar::val);
   // `reverse` has neither a projection nor a predicate.

libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.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
 //
 //===----------------------------------------------------------------------===//
 
//test(std::ranges::remove_copy_if, in, out, unary_pred);
     //test(std::ranges::replace_copy_if, in, out, unary_pred, x);
   }
   test(std::ranges::swap_ranges, in, in2);
   if constexpr (std::copyable<T>) {
     test(std::ranges::reverse_copy, in, out);
     test_mid(std::ranges::rotate_copy, in, mid, out);
     //test(std::ranges::unique_copy, in, out);
     test(std::ranges::partition_copy, in, out, out2, unary_pred);
-    //test_mid(std::ranges::partial_sort_copy, in, in2);
+    test(std::ranges::partial_sort_copy, in, in2);
     test(std::ranges::merge, in, in2, out);
     test(std::ranges::set_difference, in, in2, out);
     test(std::ranges::set_intersection, in, in2, out);
     test(std::ranges::set_symmetric_difference, in, in2, out);
     test(std::ranges::set_union, in, in2, out);
   }
   test(std::ranges::remove, in, x);
   test(std::ranges::remove_if, in, unary_pred);

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::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_copy, a, a));
+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));
 //static_assert(test(std::ranges::remove_copy, a, a, 42));