[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

77

nit: would MoveOnly.hwork?

[ldionne]

LGTM % comments and CI

libcxx/include/__algorithm/partial_sort_copy.h

34

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.

51

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.

55

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

2

This is part of another commit.

[huixie90]

libcxx/include/__algorithm/partial_sort_copy.h

34

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

55

@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

34

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.

51

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.

55

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

81–84 ↗

(On Diff #448217)

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

81–84 ↗

(On Diff #448217)

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,`TODO <https://llvm.org/TODO>`_,✅
 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_MAKE_HEAP_H
 #define _LIBCPP___ALGORITHM_MAKE_HEAP_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__algorithm/iterator_operations.h>
 #include <__algorithm/sift_down.h>
 #include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
 #include <__iterator/iterator_traits.h>
 #include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator, class _Proj>
 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, _Proj&& __proj) {
   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, _CompRef>(__first, __comp_ref, __n, __first + __start, __proj);
     }
   }
 }
 
 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);
+  std::__make_heap<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp, __identity());
 }
 
 template <class _RandomAccessIterator>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
 void make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last) {
   std::make_heap(std::move(__first), std::move(__last),
       __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_MAKE_HEAP_H

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

 #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, class _Sentinel>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator, class _Sentinel, class _Proj = __identity>
 _LIBCPP_CONSTEXPR_AFTER_CXX17
-_RandomAccessIterator __partial_sort_impl(
-    _RandomAccessIterator __first, _RandomAccessIterator __middle, _Sentinel __last, _Compare __comp) {
+_RandomAccessIterator __partial_sort_impl(_RandomAccessIterator __first, _RandomAccessIterator __middle,
+    _Sentinel __last, _Compare __comp, _Proj&& __proj = __identity()) {
   if (__first == __middle) {
     return _IterOps<_AlgPolicy>::next(__middle, __last);
   }
 
-  std::__make_heap<_AlgPolicy, _Compare>(__first, __middle, __comp);
+  std::__make_heap<_AlgPolicy, _Compare>(__first, __middle, __comp, __proj);
 
   typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first;
   _RandomAccessIterator __i = __middle;
   for (; __i != __last; ++__i)
   {
-      if (__comp(*__i, *__first))
+      if (std::__invoke(__comp, std::__invoke(__proj, *__i), std::__invoke(__proj, *__first)))
       {
           _IterOps<_AlgPolicy>::iter_swap(__i, __first);
-          std::__sift_down<_AlgPolicy, _Compare>(__first, __comp, __len, __first);
+          std::__sift_down<_AlgPolicy, _Compare>(__first, __comp, __len, __first, __proj);
       }
 
   }
-  std::__sort_heap<_AlgPolicy, _Compare>(std::move(__first), std::move(__middle), __comp);
+  std::__sort_heap<_AlgPolicy, _Compare>(std::move(__first), std::move(__middle), __comp, __proj);
 
   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) {

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/sift_down.h>
 #include <__algorithm/sort_heap.h>
 #include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
 #include <__iterator/iterator_traits.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;
     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, _Compare>(__result_first, __r, __comp, __proj2);
         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, _Compare>(__result_first, __comp, __len, __result_first, __proj2);
             }
-        std::__sort_heap<_AlgPolicy, _Compare>(__result_first, __r, __comp);
+        std::__sort_heap<_AlgPolicy, _Compare>(__result_first, __r, __comp, __proj2);
     }
-    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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_POP_HEAP_H
 #define _LIBCPP___ALGORITHM_POP_HEAP_H
 
 #include <__algorithm/comp.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 <__functional/identity.h>
+#include <__functional/invoke.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>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator, class _Proj>
 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) {
+    typename iterator_traits<_RandomAccessIterator>::difference_type __len, _Proj&& __proj) {
   _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, _CompRef>(__first, __comp_ref, __len, __proj);
     --__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, _CompRef>(__first, __hole, __comp_ref, __hole - __first, __proj);
     }
   }
 }
 
 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);
+  std::__pop_heap<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp, __len, __identity());
 }
 
 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

 //===----------------------------------------------------------------------===//
 //
 // 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_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 <__functional/identity.h>
+#include <__functional/invoke.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>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator, class _Proj>
 _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
 void __sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
-        typename iterator_traits<_RandomAccessIterator>::difference_type __len) {
+        typename iterator_traits<_RandomAccessIterator>::difference_type __len, _Proj&& __proj) {
   using value_type = typename iterator_traits<_RandomAccessIterator>::value_type;
 
   if (__len > 1) {
     __len = (__len - 2) / 2;
     _RandomAccessIterator __ptr = __first + __len;
 
-    if (__comp(*__ptr, *--__last)) {
+    if (std::__invoke(__comp, std::__invoke(__proj, *__ptr), std::invoke(__proj, *--__last))) {
       value_type __t(_IterOps<_AlgPolicy>::__iter_move(__last));
       do {
         *__last = _IterOps<_AlgPolicy>::__iter_move(__ptr);
         __last = __ptr;
         if (__len == 0)
           break;
         __len = (__len - 1) / 2;
         __ptr = __first + __len;
-      } while (__comp(*__ptr, __t));
+      } while (std::__invoke(__comp, std::__invoke(__proj, *__ptr), std::__invoke(__proj, __t)));
 
       *__last = std::move(__t);
     }
   }
 }
 
-template <class _AlgPolicy, class _RandomAccessIterator, class _Compare>
+template <class _AlgPolicy, class _RandomAccessIterator, class _Compare, class _Proj>
 inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
-void __push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) {
+void __push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp, _Proj&& __proj) {
   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);
+  std::__sift_up<_AlgPolicy, _CompRef>(std::move(__first), std::move(__last), __comp, __len, __proj);
 }
 
 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);
+  std::__push_heap<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp, __identity());
 }
 
 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_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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_RANGES_MAKE_HEAP_H
 #define _LIBCPP___ALGORITHM_RANGES_MAKE_HEAP_H
 
 #include <__algorithm/iterator_operations.h>
 #include <__algorithm/make_heap.h>
-#include <__algorithm/make_projected.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>

 namespace ranges {
 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);
-    std::__make_heap<_RangeAlgPolicy>(std::move(__first), __last_iter, __projected_comp);
+    std::__make_heap<_RangeAlgPolicy>(std::move(__first), __last_iter, __comp, __proj);
 
     return __last_iter;
   }
 
   template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity>
     requires sortable<_Iter, _Comp, _Proj>
   _LIBCPP_HIDE_FROM_ABI constexpr
   _Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {

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_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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_RANGES_POP_HEAP_H
 #define _LIBCPP___ALGORITHM_RANGES_POP_HEAP_H
 
 #include <__algorithm/iterator_operations.h>
-#include <__algorithm/make_projected.h>
 #include <__algorithm/pop_heap.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>

 
 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);
-    std::__pop_heap<_RangeAlgPolicy>(std::move(__first), __last_iter, __projected_comp, __len);
+    std::__pop_heap<_RangeAlgPolicy>(std::move(__first), __last_iter, __comp, __len, __proj);
 
     return __last_iter;
   }
 
   template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity>
     requires sortable<_Iter, _Comp, _Proj>
   _LIBCPP_HIDE_FROM_ABI constexpr
   _Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {

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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_RANGES_PUSH_HEAP_H
 #define _LIBCPP___ALGORITHM_RANGES_PUSH_HEAP_H
 
 #include <__algorithm/iterator_operations.h>
-#include <__algorithm/make_projected.h>
 #include <__algorithm/push_heap.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>

 namespace ranges {
 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);
-    std::__push_heap<_RangeAlgPolicy>(std::move(__first), __last_iter, __projected_comp);
+    std::__push_heap<_RangeAlgPolicy>(std::move(__first), __last_iter, __comp, __proj);
 
     return __last_iter;
   }
 
   template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity>
     requires sortable<_Iter, _Comp, _Proj>
   _LIBCPP_HIDE_FROM_ABI constexpr
   _Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {

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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_RANGES_SORT_HEAP_H
 #define _LIBCPP___ALGORITHM_RANGES_SORT_HEAP_H
 
 #include <__algorithm/iterator_operations.h>
-#include <__algorithm/make_projected.h>
 #include <__algorithm/sort_heap.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>

 namespace ranges {
 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);
-    std::__sort_heap<_RangeAlgPolicy>(std::move(__first), __last_iter, __projected_comp);
+    std::__sort_heap<_RangeAlgPolicy>(std::move(__first), __last_iter, __comp, __proj);
 
     return __last_iter;
   }
 
   template <random_access_iterator _Iter, sentinel_for<_Iter> _Sent, class _Comp = ranges::less, class _Proj = identity>
     requires sortable<_Iter, _Comp, _Proj>
   _LIBCPP_HIDE_FROM_ABI constexpr
   _Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {

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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_SIFT_DOWN_H
 #define _LIBCPP___ALGORITHM_SIFT_DOWN_H
 
 #include <__algorithm/iterator_operations.h>
 #include <__assert>
 #include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
 #include <__iterator/iterator_traits.h>
 #include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator, class _Proj>
 _LIBCPP_CONSTEXPR_AFTER_CXX11 void
 __sift_down(_RandomAccessIterator __first, _Compare __comp,
             typename iterator_traits<_RandomAccessIterator>::difference_type __len,
-            _RandomAccessIterator __start)
+            _RandomAccessIterator __start, _Proj&& __proj)
 {
     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
     // right-child of __start is at 2 * __start + 2
     difference_type __child = __start - __first;
 
     if (__len < 2 || (__len - 2) / 2 < __child)
         return;
 
     __child = 2 * __child + 1;
     _RandomAccessIterator __child_i = __first + __child;
 
-    if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + difference_type(1)))) {
+    if ((__child + 1) < __len && std::__invoke(__comp,
+        std::__invoke( __proj, *__child_i ),
+        std::__invoke( __proj, *(__child_i + difference_type(1))) )
+    ) {
         // right-child exists and is greater than left-child
         ++__child_i;
         ++__child;
     }
 
     // check if we are in heap-order
-    if (__comp(*__child_i, *__start))
+    if (std::__invoke(__comp, std::__invoke(__proj, *__child_i), std::__invoke(__proj, *__start)))
         // we are, __start is larger than its largest child
         return;
 
     value_type __top(_Ops::__iter_move(__start));
     do
     {
         // we are not in heap-order, swap the parent with its largest child
         *__start = _Ops::__iter_move(__child_i);
         __start = __child_i;
 
         if ((__len - 2) / 2 < __child)
             break;
 
         // recompute the child based off of the updated parent
         __child = 2 * __child + 1;
         __child_i = __first + __child;
 
-        if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + difference_type(1)))) {
+        if ((__child + 1) < __len && std::__invoke(__comp,
+            std::__invoke( __proj, *__child_i ),
+            std::__invoke( __proj, *(__child_i + difference_type(1))) )
+        ) {
             // right-child exists and is greater than left-child
             ++__child_i;
             ++__child;
         }
 
         // check if we are in heap-order
-    } while (!__comp(*__child_i, __top));
+    } while (!std::__invoke(__comp, std::__invoke(__proj, *__child_i), std::__invoke(__proj, __top)));
     *__start = _VSTD::move(__top);
 }
 
-template <class _AlgPolicy, class _Compare, class _RandomAccessIterator>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator, class _Proj>
 _LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator
 __floyd_sift_down(_RandomAccessIterator __first, _Compare __comp,
-                  typename iterator_traits<_RandomAccessIterator>::difference_type __len)
+                  typename iterator_traits<_RandomAccessIterator>::difference_type __len, _Proj&& __proj)
 {
     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;
 
     while (true) {
         __child_i += difference_type(__child + 1);
         __child = 2 * __child + 1;
 
-        if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + difference_type(1)))) {
+        if ((__child + 1) < __len && std::__invoke(__comp,
+            std::__invoke( __proj, *__child_i ),
+            std::__invoke( __proj, *(__child_i + difference_type(1))) )
+        ) {
             // right-child exists and is greater than left-child
             ++__child_i;
             ++__child;
         }
 
         // swap __hole with its largest child
         *__hole = _IterOps<_AlgPolicy>::__iter_move(__child_i);
         __hole = __child_i;

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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_SORT_HEAP_H
 #define _LIBCPP___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 <__functional/identity.h>
+#include <__functional/invoke.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>
+template <class _AlgPolicy, class _Compare, class _RandomAccessIterator, class _Proj>
 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, _Proj&& __proj) {
   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, _CompRef>(__first, __last, __comp_ref, __n, __proj);
 }
 
 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);
+  std::__sort_heap<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __comp, __identity());
 }
 
 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<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 "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>);
+
+struct Uncopyable {
+  Uncopyable(int&&);
+  Uncopyable(const int&) = delete;
+};
+// !indirectly_copyable<I1, I2>
+static_assert(!HasPartialSortCopyIter<int*, int*, Uncopyable*>);
+
+// !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<Uncopyable*>>);
+
+// !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
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// <algorithm>
+//
+// Range algorithms should support the case where the ranges they operate on have different value types and the given
+// projection functors are different (each projection applies to a different value type).
+
+#include <algorithm>
+
+#include <array>
+#include <iterator>
+#include <ranges>
+#include <utility>
+
+// (in1, in2, ...)
+template <class Func, std::ranges::range Input1, std::ranges::range Input2, class ...Args>
+constexpr void test(Func&& func, Input1& in1, Input2& in2, Args&& ...args) {
+  func(in1.begin(), in1.end(), in2.begin(), in2.end(), std::forward<Args>(args)...);
+  func(in1, in2, std::forward<Args>(args)...);
+}
+
+constexpr bool test_all() {
+  struct A {
+    int x = 0;
+
+    constexpr A() = default;
+    constexpr A(int value) : x(value) {}
+    constexpr operator int() const { return x; }
+
+    constexpr auto operator<=>(const A&) const = default;
+  };
+
+  std::array in = {1, 2, 3};
+  std::array in2 = {A{4}, A{5}, A{6}};
+
+  std::array output = {7, 8, 9, 10, 11, 12};
+  auto out = output.begin();
+  std::array output2 = {A{7}, A{8}, A{9}, A{10}, A{11}, A{12}};
+  auto out2 = output2.begin();
+
+  std::ranges::equal_to eq;
+  std::ranges::less less;
+  auto sum = [](int lhs, A rhs) { return lhs + rhs.x; };
+  auto proj1 = [](int x) { return x * -1; };
+  auto proj2 = [](A a) { return a.x * -1; };
+
+  test(std::ranges::equal, in, in2, eq, proj1, proj2);
+  test(std::ranges::lexicographical_compare, in, in2, eq, proj1, proj2);
+  //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, 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));