[libc++][ranges] Implement modifying heap algorithms:

[var-const]

Summary

• ranges::make_heap;
• ranges::push_heap;
• ranges::pop_heap;
• ranges::sort_heap.

[var-const]

Use the actual patch number.

[var-const]

libcxx/include/__algorithm/make_heap.h

26–33

Note: a few of these existing internal functions were missing the _LIBCPP_HIDE_FROM_ABI annotation. I presume adding it won't cause any problems?

41

The main purpose of this function is to avoid leaking the __comp_ref_type quirk from this file (similarly for the other heap headers).

libcxx/include/__algorithm/ranges_pop_heap.h

43

Note: the Standard specifies that the range has to be non-empty in pop.heap:

Preconditions: The range [first, last) is a valid **non-empty** heap

However, our existing non-ranges version of pop_heap is simply a no-op for an empty range, and the same is true for GCC and MSVC. Please let me know whether you think being strict with this check adds any benefit.

[var-const]

Fix the CI.

[var-const]

Rebase on main.

[ldionne]

libcxx/include/__algorithm/make_heap.h

26–33

It must have been because they didn't want to always_inline those functions back in the days. Adding it is the correct thing to do since we don't use always_inline for ABI anymore.

libcxx/include/__algorithm/ranges_make_heap.h

46

Probably applies elsewhere too.

libcxx/include/__algorithm/ranges_pop_heap.h

43

I would add a _LIBCPP_ASSERT to be strict about this. Users are likely to use the last element of the range after calling pop_heap (because that's the element they popped), and that would be UB if our pop_heap returns silently when the range is empty.

[var-const]

libcxx/include/__algorithm/ranges_pop_heap.h

43

Just to clarify, do you mean also adding it to the classic algorithm, or just to the ranges version? In the former case, would that require a release note?

[huixie90]

libcxx/include/__algorithm/make_heap.h

33

I think __sift_down does not use iter_move or iter_swap. This is not correct for ranges algorithms

libcxx/include/__algorithm/pop_heap.h

33

I believe this needs to call ranges::iter_move for the ranges version

40

same as above

43

I think this does not do the right thing for ranges overload

libcxx/include/__algorithm/push_heap.h

35–37

should use iter_move for ranges overload

libcxx/include/__algorithm/sort_heap.h

31

This won't call the ranges::iter_move for the ranges overload

[var-const]

Address feedback.

libcxx/include/__algorithm/pop_heap.h

33

Thanks _a lot_ for finding this! I'd prefer to address this for all recently-implemented algorithms in a follow-up patch -- would that work for you?

libcxx/include/__algorithm/ranges_pop_heap.h

43

From offline discussion: we should add an assertion for the classic version as well. A release note is not necessary because it's undefined behavior.

[huixie90]

libcxx/include/__algorithm/pop_heap.h

33

Yes. sounds good to me.
I am going to create a test utility which adapts our existing test_iterators, and simulate the proxy iterator behaviour (like zip iterator). and all permutation algorithms would test against these kinds of iterators

[var-const]

Fix the CI.

[var-const]

Fix the CI.

[ldionne]

libcxx/include/__algorithm/make_heap.h

40

I would suggest:

1. Swapping the names __make_heap_impl and __make_heap.
2. Inlining the new __make_heap_impl into the new __make_heap
3. Removing __make_heap_impl, which isn't used anywhere anymore.

This gives:

template <class _RandomAccessIterator, class _Compare>
inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
void __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) {
  using _Comp_ref = typename __comp_ref_type<_Compare>::type;
  _Comp_ref __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<_Compare>(__first, __comp_ref, __n, __first + __start);
    }
  }
}

I think the same comment applies to all the other heap algorithms.

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/pop.heap/assert.pop_heap.pass.cpp

10 ↗

(On Diff #440683)

This is not needed -- we support basic assertions even when the "debug" mode is disabled.

It's kind of messy right now (I'm in the process of cleaning that up), but basically Debug Mode = heavyweight checks that change ABI and/or complexity, and Assertions = lightweight checks that don't impact ABI/complexity.

Debug Mode implies Assertions, but not the other way around. Here you only need to turn Assertions on with _LIBCPP_ENABLE_ASSERTIONS=1 to test this.

This comment applies to the other assert.FOO tests.

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/pop.heap/assert.ranges_pop_heap.pass.cpp

15–24 ↗

(On Diff #440683)

I am not sure that the full synopsis is useful here. Also applies to other assert.FOO tests.

[var-const]

Address feedback.

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/pop.heap/assert.pop_heap.pass.cpp

10 ↗

(On Diff #440683)

Thanks!

[var-const]

Fix order of includes.

[huixie90]

LGTM. I think you changed some signatures of some __ function to take an "Tag" template argument in the partial_sort patch and this change might need to rebase that change?

libcxx/include/algorithm

276

unresolved merge conflicts?

[Mordante]

In general looks good, but there are some small issues.

libcxx/include/__algorithm/make_heap.h

39–48

Maybe drop the inline while you're at it.

libcxx/include/__algorithm/push_heap.h

39

Can you put the break; on its own line?

53

You need to calculate __last - __first before the function call since they are moved from in this call.

libcxx/include/__algorithm/ranges_pop_heap.h

49

Here __first might be used in a moved from state.

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/make.heap/ranges_make_heap.pass.cpp

44

I think it would be good to test with all iterator categories to see only random access and contiguous are valid.

218

I really would like to see the maximum complexity to be validated for all heap operations. Especially since they all have different complexities.

[var-const]

Address feedback, fix the CI.

libcxx/include/__algorithm/make_heap.h

39–48

This seems like more than a purely mechanical change; I'd rather keep as is.

libcxx/include/__algorithm/push_heap.h

53

Thanks!

libcxx/include/algorithm

276

Sorry about that!

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/make.heap/ranges_make_heap.pass.cpp

44

This would apply to every test range algorithm test and make it more verbose without increasing coverage. The types from almost_satisfies_types.h are deliberately written to fall just short of meeting constraints of the type while satisfying all the prerequisite constraints; e.g. both RandomAccessIteratorNotDerivedFrom and RandomAccessIteratorBadIndex satisfy bidirectional_iterator. Thus, if RandomAccessIteratorNotDerivedFrom doesn't satisfy the constraints, it means that bidirectional_iterator and all the iterator concepts it refines don't satisfy, either.

218

I think this is valuable but I'd rather do a follow-up after we finished the initial implementation of range algorithms dedicated solely to testing complexity where possible.

[Mordante]

A few comments other than that LGTM! But I like to see the CI green before approving.

libcxx/include/__algorithm/push_heap.h

53

I would prefer not to use auto.

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/make.heap/ranges_make_heap.pass.cpp

44

Fair point.

218

Should we add a note on the Status page as a reminder?

[var-const]

Address feedback, fix the CI.

[var-const]

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/make.heap/ranges_make_heap.pass.cpp

218

I'll get to this pretty soon -- I don't think there should be need for a TODO.

[var-const]

Fix the CI, rebase on main.

libcxx/benchmarks/CMakeLists.txt

 #==============================================================================
 set(BENCHMARK_TESTS
     algorithms/lower_bound.bench.cpp
     algorithms/make_heap.bench.cpp
     algorithms/make_heap_then_sort_heap.bench.cpp
     algorithms/min_max_element.bench.cpp
     algorithms/pop_heap.bench.cpp
     algorithms/push_heap.bench.cpp
+    algorithms/ranges_make_heap.bench.cpp
+    algorithms/ranges_make_heap_then_sort_heap.bench.cpp
+    algorithms/ranges_pop_heap.bench.cpp
+    algorithms/ranges_push_heap.bench.cpp
     algorithms/ranges_sort.bench.cpp
+    algorithms/ranges_sort_heap.bench.cpp
     algorithms/sort.bench.cpp
     algorithms/sort_heap.bench.cpp
     algorithms/stable_sort.bench.cpp
     algorithms.partition_point.bench.cpp
     allocation.bench.cpp
     deque.bench.cpp
     filesystem.bench.cpp
     function.bench.cpp

libcxx/benchmarks/algorithms/ranges_make_heap.bench.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include <algorithm>
+
+#include "common.h"
+
+namespace {
+template <class ValueType, class Order>
+struct RangesMakeHeap {
+  size_t Quantity;
+
+  void run(benchmark::State& state) const {
+    runOpOnCopies<ValueType>(
+        state, Quantity, Order(), BatchSize::CountElements,
+        [](auto& Copy) { std::ranges::make_heap(Copy); });
+  }
+
+  std::string name() const {
+    return "BM_RangesMakeHeap" + ValueType::name() + Order::name() + "_" +
+           std::to_string(Quantity);
+  };
+};
+} // namespace
+
+int main(int argc, char** argv) {
+  benchmark::Initialize(&argc, argv);
+  if (benchmark::ReportUnrecognizedArguments(argc, argv))
+    return 1;
+  makeCartesianProductBenchmark<RangesMakeHeap, AllValueTypes, AllOrders>(Quantities);
+  benchmark::RunSpecifiedBenchmarks();
+}

libcxx/benchmarks/algorithms/ranges_make_heap_then_sort_heap.bench.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include <algorithm>
+
+#include "common.h"
+
+namespace {
+template <class ValueType, class Order>
+struct RangesMakeThenSortHeap {
+  size_t Quantity;
+
+  void run(benchmark::State& state) const {
+    runOpOnCopies<ValueType>(state, Quantity, Order(), BatchSize::CountElements,
+                             [](auto& Copy) {
+                               std::ranges::make_heap(Copy);
+                               std::ranges::sort_heap(Copy);
+                             });
+  }
+
+  std::string name() const {
+    return "BM_RangesMakeThenSortHeap" + ValueType::name() + Order::name() + "_" +
+           std::to_string(Quantity);
+  };
+};
+} // namespace
+
+int main(int argc, char** argv) {
+  benchmark::Initialize(&argc, argv);
+  if (benchmark::ReportUnrecognizedArguments(argc, argv))
+    return 1;
+  makeCartesianProductBenchmark<RangesMakeThenSortHeap, AllValueTypes, AllOrders>(Quantities);
+  benchmark::RunSpecifiedBenchmarks();
+}

libcxx/benchmarks/algorithms/ranges_pop_heap.bench.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include <algorithm>
+
+#include "common.h"
+
+namespace {
+template <class ValueType>
+struct RangesPopHeap {
+  size_t Quantity;
+
+  void run(benchmark::State& state) const {
+    runOpOnCopies<ValueType>(
+        state, Quantity, Order(), BatchSize::CountElements, [](auto& Copy) {
+          for (auto B = Copy.begin(), I = Copy.end(); I != B; --I) {
+            std::ranges::pop_heap(B, I);
+          }
+        });
+  }
+
+  std::string name() const {
+    return "BM_RangesPopHeap" + ValueType::name() + "_" + std::to_string(Quantity);
+  };
+};
+} // namespace
+
+int main(int argc, char** argv) {
+  benchmark::Initialize(&argc, argv);
+  if (benchmark::ReportUnrecognizedArguments(argc, argv))
+    return 1;
+  makeCartesianProductBenchmark<RangesPopHeap, AllValueTypes>(Quantities);
+  benchmark::RunSpecifiedBenchmarks();
+}

libcxx/benchmarks/algorithms/ranges_push_heap.bench.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include <algorithm>
+
+#include "common.h"
+
+namespace {
+template <class ValueType, class Order>
+struct RangesPushHeap {
+  size_t Quantity;
+
+  void run(benchmark::State& state) const {
+    runOpOnCopies<ValueType>(
+        state, Quantity, Order(), BatchSize::CountElements, [](auto& Copy) {
+          for (auto I = Copy.begin(), E = Copy.end(); I != E; ++I) {
+            std::ranges::push_heap(Copy.begin(), I + 1);
+          }
+        });
+  }
+
+  bool skip() const { return Order() == ::Order::Heap; }
+
+  std::string name() const {
+    return "BM_RangesPushHeap" + ValueType::name() + Order::name() + "_" +
+           std::to_string(Quantity);
+  };
+};
+} // namespace
+
+int main(int argc, char** argv) {
+  benchmark::Initialize(&argc, argv);
+  if (benchmark::ReportUnrecognizedArguments(argc, argv))
+    return 1;
+  makeCartesianProductBenchmark<RangesPushHeap, AllValueTypes, AllOrders>(Quantities);
+  benchmark::RunSpecifiedBenchmarks();
+}

libcxx/benchmarks/algorithms/ranges_sort_heap.bench.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include <algorithm>
+
+#include "common.h"
+
+namespace {
+template <class ValueType>
+struct RangesSortHeap {
+  size_t Quantity;
+
+  void run(benchmark::State& state) const {
+    runOpOnCopies<ValueType>(
+        state, Quantity, Order::Heap, BatchSize::CountElements,
+        [](auto& Copy) { std::ranges::sort_heap(Copy); });
+  }
+
+  std::string name() const {
+    return "BM_RangesSortHeap" + ValueType::name() + "_" + std::to_string(Quantity);
+  };
+};
+} // namespace
+
+int main(int argc, char** argv) {
+  benchmark::Initialize(&argc, argv);
+  if (benchmark::ReportUnrecognizedArguments(argc, argv))
+    return 1;
+  makeCartesianProductBenchmark<RangesSortHeap, AllValueTypes>(Quantities);
+  benchmark::RunSpecifiedBenchmarks();
+}

libcxx/docs/Status/RangesAlgorithms.csv

 Permutation,unique,Not assigned,n/a,Not started
 Permutation,partition,Not assigned,n/a,Not started
 Permutation,stable_partition,Not assigned,n/a,Not started
 Permutation,sort,Konstantin Varlamov,`D127557 <https://llvm.org/D127557>`_,✅
 Permutation,stable_sort,Konstantin Varlamov,n/a,In progress
 Permutation,partial_sort,Konstantin Varlamov,n/a,In progress
 Permutation,nth_element,Not assigned,n/a,Not started
 Permutation,inplace_merge,Not assigned,n/a,Not started
-Permutation,make_heap,Not assigned,n/a,Not started
-Permutation,push_heap,Not assigned,n/a,Not started
-Permutation,pop_heap,Not assigned,n/a,Not started
-Permutation,sort_heap,Not assigned,n/a,Not started
+Permutation,make_heap,Konstantin Varlamov,`D128115 <https://llvm.org/D128115>`_,✅
+Permutation,push_heap,Konstantin Varlamov,`D128115 <https://llvm.org/D128115>`_,✅
+Permutation,pop_heap,Konstantin Varlamov,`D128115 <https://llvm.org/D128115>`_,✅
+Permutation,sort_heap,Konstantin Varlamov,`D128115 <https://llvm.org/D128115>`_,✅
 Permutation,prev_permutation,Not assigned,n/a,Not started
 Permutation,next_permutation,Not assigned,n/a,Not started
 Uninitialised memory,uninitialized_copy,Konstantin Varlamov,`D116023 <https://llvm.org/D116023>`_,✅
 Uninitialised memory,uninitialized_copy_n,Konstantin Varlamov,`D116023 <https://llvm.org/D116023>`_,✅
 Uninitialised memory,uninitialized_fill,Konstantin Varlamov,`D115626 <https://llvm.org/D115626>`_,✅
 Uninitialised memory,uninitialized_fill_n,Konstantin Varlamov,`D115626 <https://llvm.org/D115626>`_,✅
 Uninitialised memory,uninitialized_move,Konstantin Varlamov,`D116023 <https://llvm.org/D116023>`_,✅
 Uninitialised memory,uninitialized_move_n,Konstantin Varlamov,`D116023 <https://llvm.org/D116023>`_,✅
 Uninitialised memory,uninitialized_default_construct,Konstantin Varlamov,`D115315 <https://llvm.org/D115315>`_,✅
 Uninitialised memory,uninitialized_default_construct_n,Konstantin Varlamov,`D115315 <https://llvm.org/D115315>`_,✅
 Uninitialised memory,uninitialized_value_construct,Konstantin Varlamov,`D115626 <https://llvm.org/D115626>`_,✅
 Uninitialised memory,uninitialized_value_construct_n,Konstantin Varlamov,`D115626 <https://llvm.org/D115626>`_,✅
 Uninitialised memory,destroy,Konstantin Varlamov,`D116078 <https://llvm.org/D116078>`_,✅
 Uninitialised memory,destroy_n,Konstantin Varlamov,`D116078 <https://llvm.org/D116078>`_,✅
 Uninitialised memory,destroy_at,Konstantin Varlamov,`D116078 <https://llvm.org/D116078>`_,✅
 Uninitialised memory,construct_at,Konstantin Varlamov,`D116078 <https://llvm.org/D116078>`_,✅

libcxx/include/CMakeLists.txt

set(files
   __algorithm/ranges_find_if_not.h
   __algorithm/ranges_for_each.h
   __algorithm/ranges_for_each_n.h
   __algorithm/ranges_is_partitioned.h
   __algorithm/ranges_is_sorted.h
   __algorithm/ranges_is_sorted_until.h
   __algorithm/ranges_lexicographical_compare.h
   __algorithm/ranges_lower_bound.h
+  __algorithm/ranges_make_heap.h
   __algorithm/ranges_max.h
   __algorithm/ranges_max_element.h
   __algorithm/ranges_min.h
   __algorithm/ranges_min_element.h
   __algorithm/ranges_minmax.h
   __algorithm/ranges_minmax_element.h
   __algorithm/ranges_mismatch.h
   __algorithm/ranges_none_of.h
+  __algorithm/ranges_pop_heap.h
+  __algorithm/ranges_push_heap.h
   __algorithm/ranges_replace.h
   __algorithm/ranges_replace_if.h
   __algorithm/ranges_reverse.h
   __algorithm/ranges_sort.h
+  __algorithm/ranges_sort_heap.h
   __algorithm/ranges_swap_ranges.h
   __algorithm/ranges_transform.h
   __algorithm/ranges_upper_bound.h
   __algorithm/remove.h
   __algorithm/remove_copy.h
   __algorithm/remove_copy_if.h
   __algorithm/remove_if.h
   __algorithm/replace.h

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/sift_down.h>
 #include <__config>
 #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 _Compare, class _RandomAccessIterator>
-_LIBCPP_CONSTEXPR_AFTER_CXX11 void
-__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
-{
-    typedef typename iterator_traits<_RandomAccessIterator>::difference_type 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)
-        {
-            _VSTD::__sift_down<_Compare>(__first, __comp, __n, __first + __start);
-        }
-    }
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+void __make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
+  using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type;
+  if (__n > 1) {
+    for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start) {
+        std::__sift_down<_Compare>(__first, __comp, __n, __first + __start);
 }
 
 template <class _RandomAccessIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-void
-make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
-{
-    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-    _VSTD::__make_heap<_Comp_ref>(__first, __last, __comp);
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+void __make_heap_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) {
+  using _Comp_ref = typename __comp_ref_type<_Compare>::type;
+  std::__make_heap<_Comp_ref>(std::move(__first), std::move(__last), __comp);
+}
+
+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_impl(std::move(__first), std::move(__last), __comp);
 }
 
 template <class _RandomAccessIterator>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-void
-make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
-{
-    _VSTD::make_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
+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/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
 //
 //===----------------------------------------------------------------------===//
 

 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _Compare, class _RandomAccessIterator>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-void
-__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
-           typename iterator_traits<_RandomAccessIterator>::difference_type __len)
-{
-    using value_type = typename iterator_traits<_RandomAccessIterator>::value_type;
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+void __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
+           typename iterator_traits<_RandomAccessIterator>::difference_type __len) {
 
-    if (__len > 1)
-    {
-        value_type __top = std::move(*__first);  // create a hole at __first
-        _RandomAccessIterator __hole = std::__floyd_sift_down<_Compare>(__first, __comp, __len);
-        --__last;
-        if (__hole == __last) {
-            *__hole = std::move(__top);
-        } else {
-            *__hole = std::move(*__last);
-            ++__hole;
-            *__last = std::move(__top);
-            std::__sift_up<_Compare>(__first, __hole, __comp, __hole - __first);
-        }
-    }
+  if (__len > 1) {
+
 }
 
 template <class _RandomAccessIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-void
-pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
-{
-    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-    _VSTD::__pop_heap<_Comp_ref>(__first, __last, __comp, __last - __first);
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+void __pop_heap_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) {
+  using _Comp_ref = typename __comp_ref_type<_Compare>::type;
+  std::__pop_heap<_Comp_ref>(std::move(__first), std::move(__last), __comp, __last - __first);
+}
+
+template <class _RandomAccessIterator, class _Compare>
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+void pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
+  std::__pop_heap_impl(std::move(__first), std::move(__last), __comp);
 }
 
 template <class _RandomAccessIterator>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-void
-pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
-{
-    _VSTD::pop_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
+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 <__config>
 #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 _Compare, class _RandomAccessIterator>
-_LIBCPP_CONSTEXPR_AFTER_CXX11 void
-__sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
-          typename iterator_traits<_RandomAccessIterator>::difference_type __len)
-{
-    typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
-    if (__len > 1)
-    {
-        __len = (__len - 2) / 2;
-        _RandomAccessIterator __ptr = __first + __len;
-        if (__comp(*__ptr, *--__last))
-        {
-            value_type __t(_VSTD::move(*__last));
-            do
-            {
-                *__last = _VSTD::move(*__ptr);
-                __last = __ptr;
-                if (__len == 0)
-                    break;
-                __len = (__len - 1) / 2;
-                __ptr = __first + __len;
-            } while (__comp(*__ptr, __t));
-            *__last = _VSTD::move(__t);
-        }
-    }
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+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) {
+
+    if (__comp(*__ptr, *--__last)) {
+      value_type __t(std::move(*__last));
+      do {
+        *__last = std::move(*__ptr);
+        if (__len == 0) break;
+
+      *__last = std::move(__t);
 }
 
 template <class _RandomAccessIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-void
-push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
-{
-    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-    _VSTD::__sift_up<_Comp_ref>(__first, __last, __comp, __last - __first);
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+void __push_heap_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) {
+  using _Comp_ref = typename __comp_ref_type<_Compare>::type;
+  std::__sift_up<_Comp_ref>(std::move(__first), std::move(__last), __comp, __last - __first);
+}
+
+template <class _RandomAccessIterator, class _Compare>
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+void push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
+  std::__push_heap_impl(std::move(__first), std::move(__last), __comp);
 }
 
 template <class _RandomAccessIterator>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-void
-push_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
-{
-    _VSTD::push_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
+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/make_projected.h>
+#include <__algorithm/sort.h>
+#include <__config>
+#include <__concepts/same_as.h>
+#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)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+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 = __make_projected_comp(__comp, __proj);
+    std::__make_heap_impl(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
+  _Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {
+    return __make_heap_fn_impl(std::move(__first), std::move(__last), __comp, __proj);
+  }
+
+  template <random_access_range _Range, class _Comp = ranges::less, class _Proj = identity>
+    requires sortable<iterator_t<_Range>, _Comp, _Proj>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  borrowed_iterator_t<_Range> operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const {
+    return __make_heap_fn_impl(ranges::begin(__r), ranges::end(__r), __comp, __proj);
+  }
+};
+
+} // namespace __make_heap
+
+inline namespace __cpo {
+  inline constexpr auto make_heap = __make_heap::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_MAKE_HEAP_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/make_projected.h>
+#include <__config>
+#include <__concepts/same_as.h>
+#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 <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+#include <__utility/forward.h>
+#include <__utility/move.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+namespace __pop_heap {
+
+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) {
+    _LIBCPP_ASSERT(__first != __last, "The heap given to pop_heap must be non-empty");
+    auto __last_iter = ranges::next(__first, __last);
+
+    auto&& __projected_comp = __make_projected_comp(__comp, __proj);
+    std::__pop_heap_impl(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
+  _Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {
+    return __pop_heap_fn_impl(std::move(__first), std::move(__last), __comp, __proj);
+  }
+
+  template <random_access_range _Range, class _Comp = ranges::less, class _Proj = identity>
+    requires sortable<iterator_t<_Range>, _Comp, _Proj>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  borrowed_iterator_t<_Range> operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const {
+    return __pop_heap_fn_impl(ranges::begin(__r), ranges::end(__r), __comp, __proj);
+  }
+};
+
+} // namespace __pop_heap
+
+inline namespace __cpo {
+  inline constexpr auto pop_heap = __pop_heap::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_POP_HEAP_H

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/make_projected.h>
+#include <__config>
+#include <__concepts/same_as.h>
+#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 <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+#include <__utility/forward.h>
+#include <__utility/move.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+namespace __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 = __make_projected_comp(__comp, __proj);
+    std::__push_heap_impl(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
+  _Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {
+    return __push_heap_fn_impl(std::move(__first), std::move(__last), __comp, __proj);
+  }
+
+  template <random_access_range _Range, class _Comp = ranges::less, class _Proj = identity>
+    requires sortable<iterator_t<_Range>, _Comp, _Proj>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  borrowed_iterator_t<_Range> operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const {
+    return __push_heap_fn_impl(ranges::begin(__r), ranges::end(__r), __comp, __proj);
+  }
+};
+
+} // namespace __push_heap
+
+inline namespace __cpo {
+  inline constexpr auto push_heap = __push_heap::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_PUSH_HEAP_H

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/make_projected.h>
+#include <__config>
+#include <__concepts/same_as.h>
+#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 <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+#include <__utility/forward.h>
+#include <__utility/move.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+namespace __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 = __make_projected_comp(__comp, __proj);
+    std::__sort_heap_impl(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
+  _Iter operator()(_Iter __first, _Sent __last, _Comp __comp = {}, _Proj __proj = {}) const {
+    return __sort_heap_fn_impl(std::move(__first), std::move(__last), __comp, __proj);
+  }
+
+  template <random_access_range _Range, class _Comp = ranges::less, class _Proj = identity>
+    requires sortable<iterator_t<_Range>, _Comp, _Proj>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  borrowed_iterator_t<_Range> operator()(_Range&& __r, _Comp __comp = {}, _Proj __proj = {}) const {
+    return __sort_heap_fn_impl(ranges::begin(__r), ranges::end(__r), __comp, __proj);
+  }
+};
+
+} // namespace __sort_heap
+
+inline namespace __cpo {
+  inline constexpr auto sort_heap = __sort_heap::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_SORT_HEAP_H

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/pop_heap.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <type_traits> // swap
+#include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _Compare, class _RandomAccessIterator>
-_LIBCPP_CONSTEXPR_AFTER_CXX17 void
-__sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
-{
-    typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
-    for (difference_type __n = __last - __first; __n > 1; --__last, (void) --__n)
-        _VSTD::__pop_heap<_Compare>(__first, __last, __comp, __n);
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+  void __sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
+  using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type;
+    std::__pop_heap<_Compare>(__first, __last, __comp, __n);
 }
 
 template <class _RandomAccessIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-void
-sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
-{
-    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-    _VSTD::__sort_heap<_Comp_ref>(__first, __last, __comp);
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX11
+void __sort_heap_impl(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare& __comp) {
+  using _Comp_ref = typename __comp_ref_type<_Compare>::type;
+  std::__sort_heap<_Comp_ref>(std::move(__first), std::move(__last), __comp);
+}
+
+template <class _RandomAccessIterator, class _Compare>
+inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17
+void sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp) {
+  std::__sort_heap_impl(std::move(__first), std::move(__last), __comp);
 }
 
 template <class _RandomAccessIterator>
-inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-void
-sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
-{
-    _VSTD::sort_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
+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 R, class Proj = identity,
   template<input_iterator I, sentinel_for<I> S, class Proj = identity,
            indirect_unary_predicate<projected<I, Proj>> Pred>
     constexpr bool ranges::is_partitioned(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::is_partitioned(R&& r, Pred pred, Proj proj = {});                // since C++20
 
+  template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+          class Proj = identity>
+    requires sortable<I, Comp, Proj>
+    constexpr I
+      ranges::push_heap(I first, S last, Comp comp = {}, Proj proj = {});                   // since C++20
+
+  template<random_access_range R, class Comp = ranges::less, class Proj = identity>
+    requires sortable<iterator_t<R>, Comp, Proj>
+    constexpr borrowed_iterator_t<R>
+      ranges::push_heap(R&& r, Comp comp = {}, Proj proj = {});                             // since C++20
+
+  template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+          class Proj = identity>
+    requires sortable<I, Comp, Proj>
+    constexpr I
+      ranges::pop_heap(I first, S last, Comp comp = {}, Proj proj = {});                    // since C++20
+
+  template<random_access_range R, class Comp = ranges::less, class Proj = identity>
+    requires sortable<iterator_t<R>, Comp, Proj>
+    constexpr borrowed_iterator_t<R>
+      ranges::pop_heap(R&& r, Comp comp = {}, Proj proj = {});                              // since C++20
+
+  template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+          class Proj = identity>
+    requires sortable<I, Comp, Proj>
+    constexpr I
+      ranges::make_heap(I first, S last, Comp comp = {}, Proj proj = {});                   // since C++20
+
+  template<random_access_range R, class Comp = ranges::less, class Proj = identity>
+    requires sortable<iterator_t<R>, Comp, Proj>
+    constexpr borrowed_iterator_t<R>
+      ranges::make_heap(R&& r, Comp comp = {}, Proj proj = {});                             // since C++20
+
+  template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+          class Proj = identity>
+    requires sortable<I, Comp, Proj>
+    constexpr I
+      ranges::sort_heap(I first, S last, Comp comp = {}, Proj proj = {});                   // since C++20
+
+  template<random_access_range R, class Comp = ranges::less, class Proj = identity>
+    requires sortable<iterator_t<R>, Comp, Proj>
+    constexpr borrowed_iterator_t<R>
+      ranges::sort_heap(R&& r, Comp comp = {}, Proj proj = {});                             // since C++20
 
   template<bidirectional_iterator I, sentinel_for<I> S>
     requires permutable<I>
     constexpr I ranges::reverse(I first, S last);                                           // since C++20
 
   template<bidirectional_range R>
     requires permutable<iterator_t<R>>
     constexpr borrowed_iterator_t<R> ranges::reverse(R&& r);                                // since C++20

 #include <__algorithm/ranges_find_if_not.h>
 #include <__algorithm/ranges_for_each.h>
 #include <__algorithm/ranges_for_each_n.h>
 #include <__algorithm/ranges_is_partitioned.h>
 #include <__algorithm/ranges_is_sorted.h>
 #include <__algorithm/ranges_is_sorted_until.h>
 #include <__algorithm/ranges_lexicographical_compare.h>
 #include <__algorithm/ranges_lower_bound.h>
+#include <__algorithm/ranges_make_heap.h>
 #include <__algorithm/ranges_max.h>
 #include <__algorithm/ranges_max_element.h>
 #include <__algorithm/ranges_min.h>
 #include <__algorithm/ranges_min_element.h>
 #include <__algorithm/ranges_minmax.h>
 #include <__algorithm/ranges_minmax_element.h>
 #include <__algorithm/ranges_mismatch.h>
 #include <__algorithm/ranges_none_of.h>
+#include <__algorithm/ranges_pop_heap.h>
+#include <__algorithm/ranges_push_heap.h>
 #include <__algorithm/ranges_replace.h>
 #include <__algorithm/ranges_replace_if.h>
 #include <__algorithm/ranges_reverse.h>
 #include <__algorithm/ranges_sort.h>
+#include <__algorithm/ranges_sort_heap.h>
 #include <__algorithm/ranges_swap_ranges.h>
 #include <__algorithm/ranges_transform.h>
 #include <__algorithm/ranges_upper_bound.h>
 #include <__algorithm/remove.h>
 #include <__algorithm/remove_copy.h>
 #include <__algorithm/remove_copy_if.h>
 #include <__algorithm/remove_if.h>
 #include <__algorithm/replace.h>

libcxx/include/module.modulemap.in

module __algorithm {
       module ranges_find_if_not              { private header "__algorithm/ranges_find_if_not.h" }
       module ranges_for_each                 { private header "__algorithm/ranges_for_each.h" }
       module ranges_for_each_n               { private header "__algorithm/ranges_for_each_n.h" }
       module ranges_is_partitioned           { private header "__algorithm/ranges_is_partitioned.h" }
       module ranges_is_sorted                { private header "__algorithm/ranges_is_sorted.h" }
       module ranges_is_sorted_until          { private header "__algorithm/ranges_is_sorted_until.h" }
       module ranges_lexicographical_compare  { private header "__algorithm/ranges_lexicographical_compare.h" }
       module ranges_lower_bound              { private header "__algorithm/ranges_lower_bound.h" }
+      module ranges_make_heap                { private header "__algorithm/ranges_make_heap.h" }
       module ranges_max                      { private header "__algorithm/ranges_max.h" }
       module ranges_max_element              { private header "__algorithm/ranges_max_element.h" }
       module ranges_min                      { private header "__algorithm/ranges_min.h" }
       module ranges_min_element              { private header "__algorithm/ranges_min_element.h" }
       module ranges_minmax                   { private header "__algorithm/ranges_minmax.h" }
       module ranges_minmax_element           { private header "__algorithm/ranges_minmax_element.h" }
       module ranges_mismatch                 { private header "__algorithm/ranges_mismatch.h" }
       module ranges_none_of                  { private header "__algorithm/ranges_none_of.h" }
+      module ranges_pop_heap                 { private header "__algorithm/ranges_pop_heap.h" }
+      module ranges_push_heap                { private header "__algorithm/ranges_push_heap.h" }
       module ranges_replace                  { private header "__algorithm/ranges_replace.h" }
       module ranges_replace_if               { private header "__algorithm/ranges_replace_if.h" }
       module ranges_reverse                  { private header "__algorithm/ranges_reverse.h" }
       module ranges_sort                     { private header "__algorithm/ranges_sort.h" }
+      module ranges_sort_heap                { private header "__algorithm/ranges_sort_heap.h" }
       module ranges_swap_ranges              { private header "__algorithm/ranges_swap_ranges.h" }
       module ranges_transform                { private header "__algorithm/ranges_transform.h" }
       module ranges_upper_bound              { private header "__algorithm/ranges_upper_bound.h" }
       module remove                          { private header "__algorithm/remove.h" }
       module remove_copy                     { private header "__algorithm/remove_copy.h" }
       module remove_copy_if                  { private header "__algorithm/remove_copy_if.h" }
       module remove_if                       { private header "__algorithm/remove_if.h" }
       module replace                         { private header "__algorithm/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::is_sorted_until(first, last, Less(&copies)); assert(copies == 0);
     (void)std::ranges::is_sorted_until(a, Less(&copies)); assert(copies == 0);
     //if (!std::is_constant_evaluated()) { (void)std::ranges::inplace_merge(first, mid, last, Less(&copies)); assert(copies == 0); }
     //if (!std::is_constant_evaluated()) { (void)std::ranges::inplace_merge(a, mid, Less(&copies)); assert(copies == 0); }
     (void)std::ranges::lexicographical_compare(first, last, first2, last2, Less(&copies)); assert(copies == 0);
     (void)std::ranges::lexicographical_compare(a, b, Less(&copies)); assert(copies == 0);
     (void)std::ranges::lower_bound(first, last, value, Less(&copies)); assert(copies == 0);
     (void)std::ranges::lower_bound(a, value, Less(&copies)); assert(copies == 0);
-    //(void)std::ranges::make_heap(first, last, Less(&copies)); assert(copies == 0);
-    //(void)std::ranges::make_heap(a, Less(&copies)); assert(copies == 0);
+    (void)std::ranges::make_heap(first, last, Less(&copies)); assert(copies == 0);
+    (void)std::ranges::make_heap(a, Less(&copies)); assert(copies == 0);
     (void)std::ranges::max(value, value, Less(&copies)); assert(copies == 0);
     (void)std::ranges::max({ value, value }, Less(&copies)); assert(copies == 0);
     (void)std::ranges::max(a, Less(&copies)); assert(copies == 0);
     (void)std::ranges::max_element(first, last, Less(&copies)); assert(copies == 0);
     (void)std::ranges::max_element(a, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::merge(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::merge(half, half, b, Less(&copies)); assert(copies == 0);
     (void)std::ranges::min(value, value, Less(&copies)); assert(copies == 0);
#endif
     //(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);
+    (void)std::ranges::pop_heap(first, last, Less(&copies)); assert(copies == 0);
+    (void)std::ranges::pop_heap(a, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::prev_permutation(first, last, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::prev_permutation(a, Less(&copies)); assert(copies == 0);
-    //(void)std::ranges::push_heap(first, last, Less(&copies)); assert(copies == 0);
-    //(void)std::ranges::push_heap(a, Less(&copies)); assert(copies == 0);
+    (void)std::ranges::push_heap(first, last, Less(&copies)); assert(copies == 0);
+    (void)std::ranges::push_heap(a, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_copy_if(first, last, first2, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_copy_if(a, first2, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_if(first, last, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_if(a, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::replace_copy_if(first, last, first2, UnaryTrue(&copies), value); assert(copies == 0);
     //(void)std::ranges::replace_copy_if(a, first2, UnaryTrue(&copies), value); assert(copies == 0);
     (void)std::ranges::replace_if(first, last, UnaryTrue(&copies), value); assert(copies == 0);
     (void)std::ranges::replace_if(a, UnaryTrue(&copies), value); assert(copies == 0);
     //(void)std::ranges::search(first, last, first2, mid2, Equal(&copies)); assert(copies == 0);
     //(void)std::ranges::search(a, b, Equal(&copies)); assert(copies == 0);
     //(void)std::ranges::search_n(first, last, count, value, Equal(&copies)); assert(copies == 0);
     //(void)std::ranges::search_n(a, count, value, Equal(&copies)); assert(copies == 0);
     //(void)std::ranges::set_difference(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::set_difference(a, b, first2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::set_intersection(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::set_intersection(a, b, first2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::set_symmetric_difference(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::set_symmetric_difference(a, b, first2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::set_union(first, mid, mid, last, first2, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::set_union(a, b, first2, Less(&copies)); assert(copies == 0);
     (void)std::ranges::sort(first, last, Less(&copies)); assert(copies == 0);
     (void)std::ranges::sort(a, Less(&copies)); assert(copies == 0);
-    //(void)std::ranges::sort_heap(first, last, Less(&copies)); assert(copies == 0);
-    //(void)std::ranges::sort_heap(a, Less(&copies)); assert(copies == 0);
+    (void)std::ranges::sort_heap(first, last, Less(&copies)); assert(copies == 0);
+    (void)std::ranges::sort_heap(a, Less(&copies)); assert(copies == 0);
     //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_partition(first, last, UnaryTrue(&copies)); assert(copies == 0); }
     //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_partition(a, UnaryTrue(&copies)); assert(copies == 0); }
     //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(first, last, Less(&copies)); assert(copies == 0); }
     //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(a, Less(&copies)); assert(copies == 0); }
 #if TEST_STD_VER > 20
     //(void)std::ranges::starts_with(first, last, first2, last2, Equal(&copies)); assert(copies == 0);
 #endif
     (void)std::ranges::transform(first, last, first2, UnaryTransform(&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::is_sorted_until(first, last, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::is_sorted_until(a, Less(), Proj(&copies)); assert(copies == 0);
     //if (!std::is_constant_evaluated()) { (void)std::ranges::inplace_merge(first, mid, last, Less(), Proj(&copies)); assert(copies == 0); }
     //if (!std::is_constant_evaluated()) { (void)std::ranges::inplace_merge(a, mid, Less(), Proj(&copies)); assert(copies == 0); }
     (void)std::ranges::lexicographical_compare(first, last, first2, last2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::lexicographical_compare(a, b, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::lower_bound(first, last, value, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::lower_bound(a, value, Less(), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::make_heap(first, last, Less(), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::make_heap(a, Less(), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::make_heap(first, last, Less(), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::make_heap(a, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::max(T(), T(), Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::max({ T(), T() }, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::max(a, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::max_element(first, last, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::max_element(a, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::merge(first, mid, mid, last, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::merge(half, half, b, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::min(T(), T(), Less(), Proj(&copies)); assert(copies == 0);
#endif
     //(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);
+    (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);
     //(void)std::ranges::prev_permutation(first, last, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::prev_permutation(a, Less(), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::push_heap(first, last, Less(), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::push_heap(a, Less(), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::push_heap(first, last, Less(), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::push_heap(a, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_copy(first, last, first2, value, Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_copy(a, first2, value, Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_copy_if(first, last, first2, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_copy_if(a, first2, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::remove(first, last, value, Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::remove(a, value, Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_if(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::remove_if(a, UnaryTrue(), Proj(&copies)); assert(copies == 0);
#endif
     //(void)std::ranges::set_intersection(first, mid, mid, last, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::set_intersection(a, b, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::set_symmetric_difference(first, mid, mid, last, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::set_symmetric_difference(a, b, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::set_union(first, mid, mid, last, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::set_union(a, b, first2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::sort(first, last, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::sort(a, Less(), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::sort_heap(first, last, Less(), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::sort_heap(a, Less(), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::sort_heap(first, last, Less(), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::sort_heap(a, Less(), Proj(&copies)); assert(copies == 0);
     //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_partition(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0); }
     //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_partition(a, UnaryTrue(), Proj(&copies)); assert(copies == 0); }
     //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(first, last, Less(), Proj(&copies)); assert(copies == 0); }
     //if (!std::is_constant_evaluated()) { (void)std::ranges::stable_sort(a, Less(), Proj(&copies)); assert(copies == 0); }
 #if TEST_STD_VER > 20
     //(void)std::ranges::starts_with(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
 #endif
     (void)std::ranges::transform(first, last, first2, UnaryTransform(), Proj(&copies)); assert(copies == 0);

libcxx/test/libcxx/private_headers.verify.cpp

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 

 #include <__algorithm/ranges_find_if_not.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_find_if_not.h'}}
 #include <__algorithm/ranges_for_each.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_for_each.h'}}
 #include <__algorithm/ranges_for_each_n.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_for_each_n.h'}}
 #include <__algorithm/ranges_is_partitioned.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_is_partitioned.h'}}
 #include <__algorithm/ranges_is_sorted.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_is_sorted.h'}}
 #include <__algorithm/ranges_is_sorted_until.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_is_sorted_until.h'}}
 #include <__algorithm/ranges_lexicographical_compare.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_lexicographical_compare.h'}}
 #include <__algorithm/ranges_lower_bound.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_lower_bound.h'}}
+#include <__algorithm/ranges_make_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_make_heap.h'}}
 #include <__algorithm/ranges_max.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_max.h'}}
 #include <__algorithm/ranges_max_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_max_element.h'}}
 #include <__algorithm/ranges_min.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_min.h'}}
 #include <__algorithm/ranges_min_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_min_element.h'}}
 #include <__algorithm/ranges_minmax.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_minmax.h'}}
 #include <__algorithm/ranges_minmax_element.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_minmax_element.h'}}
 #include <__algorithm/ranges_mismatch.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_mismatch.h'}}
 #include <__algorithm/ranges_none_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_none_of.h'}}
+#include <__algorithm/ranges_pop_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_pop_heap.h'}}
+#include <__algorithm/ranges_push_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_push_heap.h'}}
 #include <__algorithm/ranges_replace.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_replace.h'}}
 #include <__algorithm/ranges_replace_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_replace_if.h'}}
 #include <__algorithm/ranges_reverse.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_reverse.h'}}
 #include <__algorithm/ranges_sort.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_sort.h'}}
+#include <__algorithm/ranges_sort_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_sort_heap.h'}}
 #include <__algorithm/ranges_swap_ranges.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_swap_ranges.h'}}
 #include <__algorithm/ranges_transform.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_transform.h'}}
 #include <__algorithm/ranges_upper_bound.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_upper_bound.h'}}
 #include <__algorithm/remove.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/remove.h'}}
 #include <__algorithm/remove_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/remove_copy.h'}}
 #include <__algorithm/remove_copy_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/remove_copy_if.h'}}
 #include <__algorithm/remove_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/remove_if.h'}}
 #include <__algorithm/replace.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/replace.h'}}

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/make.heap/ranges_make_heap.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// <algorithm>
+
+// template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+//         class Proj = identity>
+//   requires sortable<I, Comp, Proj>
+//   constexpr I
+//     ranges::make_heap(I first, S last, Comp comp = {}, Proj proj = {});                   // since C++20
+//
+// template<random_access_range R, class Comp = ranges::less, class Proj = identity>
+//   requires sortable<iterator_t<R>, Comp, Proj>
+//   constexpr borrowed_iterator_t<R>
+//     ranges::make_heap(R&& r, Comp comp = {}, Proj proj = {});                             // since C++20
+
+#include <algorithm>
+#include <array>
+#include <concepts>
+#include <functional>
+#include <ranges>
+
+#include "almost_satisfies_types.h"
+#include "boolean_testable.h"
+#include "test_iterators.h"
+
+// SFINAE tests.
+
+using BadComparator = ComparatorNotCopyable<int*>;
+static_assert(!std::sortable<int*, BadComparator>);
+
+template <class Iter, class Sent = sentinel_wrapper<Iter>, class Comp = std::ranges::less>
+concept HasMakeHeapIt = requires(Iter first, Sent last, Comp comp) { std::ranges::make_heap(first, last, comp); };
+
+static_assert(HasMakeHeapIt<int*>);
+static_assert(!HasMakeHeapIt<RandomAccessIteratorNotDerivedFrom>);
+static_assert(!HasMakeHeapIt<RandomAccessIteratorBadIndex>);
+static_assert(!HasMakeHeapIt<int*, SentinelForNotSemiregular>);
+static_assert(!HasMakeHeapIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
+static_assert(!HasMakeHeapIt<int*, int*, BadComparator>);
+static_assert(!HasMakeHeapIt<const int*>); // Doesn't satisfy `sortable`.
+
+template <class Range, class Comp = std::ranges::less>
+concept HasMakeHeapR = requires(Range range, Comp comp) { std::ranges::make_heap(range, comp); };
+
+static_assert(HasMakeHeapR<UncheckedRange<int*>>);
+static_assert(!HasMakeHeapR<RandomAccessRangeNotDerivedFrom>);
+static_assert(!HasMakeHeapR<RandomAccessRangeBadIndex>);
+static_assert(!HasMakeHeapR<UncheckedRange<int*, SentinelForNotSemiregular>>);
+static_assert(!HasMakeHeapR<UncheckedRange<int*, SentinelForNotWeaklyEqualityComparableWith>>);
+static_assert(!HasMakeHeapR<UncheckedRange<int*>, BadComparator>);
+static_assert(!HasMakeHeapR<UncheckedRange<const int*>>); // Doesn't satisfy `sortable`.
+
+template <size_t N, class T, class Iter>
+constexpr void verify_heap(const std::array<T, N>& heapified, Iter last, std::array<T, N> expected) {
+  assert(heapified == expected);
+  assert(base(last) == heapified.data() + heapified.size());
+  assert(std::is_heap(heapified.begin(), heapified.end()));
+}
+
+template <class Iter, class Sent, size_t N>
+constexpr void test_one(const std::array<int, N> input, std::array<int, N> expected) {
+  { // (iterator, sentinel) overload.
+    auto heapified = input;
+    auto b = Iter(heapified.data());
+    auto e = Sent(Iter(heapified.data() + heapified.size()));
+
+    std::same_as<Iter> decltype(auto) last = std::ranges::make_heap(b, e);
+    verify_heap(heapified, last, expected);
+  }
+
+  { // (range) overload.
+    auto heapified = input;
+    auto b = Iter(heapified.data());
+    auto e = Sent(Iter(heapified.data() + heapified.size()));
+    auto range = std::ranges::subrange(b, e);
+
+    std::same_as<Iter> decltype(auto) last = std::ranges::make_heap(range);
+    verify_heap(heapified, last, expected);
+  }
+}
+
+template <class Iter, class Sent>
+constexpr void test_iterators_2() {
+  // Empty sequence.
+  test_one<Iter, Sent, 0>({}, {});
+  // 1-element sequence.
+  test_one<Iter, Sent, 1>({1}, {1});
+  // 2-element sequence.
+  test_one<Iter, Sent, 2>({2, 1}, {2, 1});
+  // 3-element sequence.
+  test_one<Iter, Sent, 3>({2, 1, 3}, {3, 1, 2});
+  // Longer sequence.
+  test_one<Iter, Sent, 8>({2, 1, 3, 6, 8, 4, 11, 5}, {11, 8, 4, 6, 1, 2, 3, 5});
+  // Longer sequence with duplicates.
+  test_one<Iter, Sent, 7>({2, 1, 3, 6, 2, 8, 6}, {8, 6, 6, 1, 2, 3, 2});
+  // All elements are the same.
+  test_one<Iter, Sent, 3>({1, 1, 1}, {1, 1, 1});
+  // Already heapified.
+  test_one<Iter, Sent, 5>({5, 4, 3, 1, 2}, {5, 4, 3, 1, 2});
+  // Sorted.
+  test_one<Iter, Sent, 5>({1, 2, 3, 4, 5}, {5, 4, 3, 1, 2});
+  // Reverse-sorted.
+  test_one<Iter, Sent, 5>({5, 4, 3, 2, 1}, {5, 4, 3, 2, 1});
+}
+
+template <class Iter>
+constexpr void test_iterators_1() {
+  test_iterators_2<Iter, Iter>();
+  test_iterators_2<Iter, sentinel_wrapper<Iter>>();
+}
+
+constexpr void test_iterators() {
+  test_iterators_1<random_access_iterator<int*>>();
+  test_iterators_1<contiguous_iterator<int*>>();
+  test_iterators_1<int*>();
+}
+
+constexpr bool test() {
+  test_iterators();
+
+  { // A custom comparator works.
+    const std::array input = {5, 4, 3, 2, 1};
+    std::array expected = {1, 2, 3, 5, 4};
+    {
+      auto in = input;
+      auto last = std::ranges::make_heap(in.begin(), in.end(), std::ranges::greater{});
+      assert(in == expected);
+      assert(last == in.end());
+    }
+
+    {
+      auto in = input;
+      auto last = std::ranges::make_heap(in, std::ranges::greater{});
+      assert(in == expected);
+      assert(last == in.end());
+    }
+  }
+
+  { // A custom projection works.
+    struct A {
+      int a;
+      constexpr auto operator<=>(const A&) const = default;
+    };
+
+    const std::array input = {A{2}, A{1}, A{3}};
+    std::array expected = {A{3}, A{1}, A{2}};
+    {
+      auto in = input;
+      auto last = std::ranges::make_heap(in.begin(), in.end(), {}, &A::a);
+      verify_heap(in, last, expected);
+    }
+
+    {
+      auto in = input;
+      auto last = std::ranges::make_heap(in, {}, &A::a);
+      verify_heap(in, last, expected);
+    }
+  }
+
+  { // `std::invoke` is used in the implementation.
+    struct A {
+      int i;
+      constexpr A(int i_) : i(i_) {}
+
+      constexpr bool comparator(const A& rhs) const { return i < rhs.i; }
+      constexpr const A& projection() const { return *this; }
+
+      constexpr auto operator<=>(const A&) const = default;
+    };
+
+    const std::array input = {A{2}, A{1}, A{3}};
+    std::array expected = {A{3}, A{1}, A{2}};
+    {
+      auto in = input;
+      auto last = std::ranges::make_heap(in.begin(), in.end(), &A::comparator, &A::projection);
+      verify_heap(in, last, expected);
+    }
+
+    {
+      auto in = input;
+      auto last = std::ranges::make_heap(in, &A::comparator, &A::projection);
+      verify_heap(in, last, expected);
+    }
+  }
+
+  { // The comparator can return any type that's convertible to `bool`.
+    const std::array input = {2, 1, 3};
+    std::array expected = {3, 1, 2};
+    {
+      auto in = input;
+      auto last = std::ranges::make_heap(in.begin(), in.end(), [](int i, int j) { return BooleanTestable{i < j}; });
+      verify_heap(in, last, expected);
+    }
+
+    {
+      auto in = input;
+      auto last = std::ranges::make_heap(in, [](int i, int j) { return BooleanTestable{i < j}; });
+      verify_heap(in, last, expected);
+    }
+  }
+
+  { // `std::ranges::dangling` is returned.
+    [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) result =
+        std::ranges::make_heap(std::array{1, 2, 3});
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/pop.heap/ranges_pop_heap.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// <algorithm>
+
+// template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+//         class Proj = identity>
+//   requires sortable<I, Comp, Proj>
+//   constexpr I
+//     ranges::pop_heap(I first, S last, Comp comp = {}, Proj proj = {});                    // since C++20
+//
+// template<random_access_range R, class Comp = ranges::less, class Proj = identity>
+//   requires sortable<iterator_t<R>, Comp, Proj>
+//   constexpr borrowed_iterator_t<R>
+//     ranges::pop_heap(R&& r, Comp comp = {}, Proj proj = {});                              // since C++20
+
+#include <algorithm>
+#include <array>
+#include <concepts>
+#include <functional>
+#include <ranges>
+
+#include "almost_satisfies_types.h"
+#include "boolean_testable.h"
+#include "test_iterators.h"
+
+// SFINAE tests.
+
+using BadComparator = ComparatorNotCopyable<int*>;
+static_assert(!std::sortable<int*, BadComparator>);
+
+template <class Iter, class Sent = sentinel_wrapper<Iter>, class Comp = std::ranges::less>
+concept HasPopHeapIt = requires(Iter first, Sent last, Comp comp) { std::ranges::make_heap(first, last, comp); };
+
+static_assert(HasPopHeapIt<int*>);
+static_assert(!HasPopHeapIt<RandomAccessIteratorNotDerivedFrom>);
+static_assert(!HasPopHeapIt<RandomAccessIteratorBadIndex>);
+static_assert(!HasPopHeapIt<int*, SentinelForNotSemiregular>);
+static_assert(!HasPopHeapIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
+static_assert(!HasPopHeapIt<int*, int*, BadComparator>);
+static_assert(!HasPopHeapIt<const int*>); // Doesn't satisfy `sortable`.
+
+template <class Range, class Comp = std::ranges::less>
+concept HasPopHeapR = requires(Range range, Comp comp) { std::ranges::make_heap(range, comp); };
+
+static_assert(HasPopHeapR<UncheckedRange<int*>>);
+static_assert(!HasPopHeapR<RandomAccessRangeNotDerivedFrom>);
+static_assert(!HasPopHeapR<RandomAccessRangeBadIndex>);
+static_assert(!HasPopHeapR<UncheckedRange<int*, SentinelForNotSemiregular>>);
+static_assert(!HasPopHeapR<UncheckedRange<int*, SentinelForNotWeaklyEqualityComparableWith>>);
+static_assert(!HasPopHeapR<UncheckedRange<int*>, BadComparator>);
+static_assert(!HasPopHeapR<UncheckedRange<const int*>>); // Doesn't satisfy `sortable`.
+
+template <size_t N, class T, class Iter>
+constexpr void verify_heap(const std::array<T, N>& heapified, Iter last, std::array<T, N> expected) {
+  assert(heapified == expected);
+  assert(base(last) == heapified.data() + heapified.size());
+  assert(std::is_heap(heapified.begin(), heapified.end() - 1));
+  assert(*std::max_element(heapified.begin(), heapified.end()) == heapified.back());
+}
+
+template <class Iter, class Sent, size_t N>
+constexpr void test_one(const std::array<int, N> input, std::array<int, N> expected) {
+  assert(!input.empty());
+  assert(std::is_heap(input.begin(), input.end()));
+
+  { // (iterator, sentinel) overload.
+    auto heapified = input;
+    auto b = Iter(heapified.data());
+    auto e = Sent(Iter(heapified.data() + heapified.size()));
+
+    std::same_as<Iter> decltype(auto) last = std::ranges::pop_heap(b, e);
+    verify_heap(heapified, last, expected);
+  }
+
+  { // (range) overload.
+    auto heapified = input;
+    auto b = Iter(heapified.data());
+    auto e = Sent(Iter(heapified.data() + heapified.size()));
+    auto range = std::ranges::subrange(b, e);
+
+    std::same_as<Iter> decltype(auto) last = std::ranges::pop_heap(range);
+    verify_heap(heapified, last, expected);
+  }
+}
+
+template <class Iter, class Sent>
+constexpr void test_iterators_2() {
+  // 1-element sequence.
+  test_one<Iter, Sent, 1>({1}, {1});
+  // 2-element sequence.
+  test_one<Iter, Sent, 2>({2, 1}, {1, 2});
+  // 3-element sequence.
+  test_one<Iter, Sent, 3>({3, 1, 2}, {2, 1, 3});
+  // Longer sequence.
+  test_one<Iter, Sent, 8>({11, 8, 5, 6, 4, 3, 2, 1}, {8, 6, 5, 1, 4, 3, 2, 11});
+  // Longer sequence with duplicates.
+  test_one<Iter, Sent, 8>({8, 8, 6, 6, 1, 2, 2, 3}, {8, 6, 6, 3, 1, 2, 2, 8});
+  // All elements are the same.
+  test_one<Iter, Sent, 4>({1, 1, 1, 1}, {1, 1, 1, 1});
+}
+
+template <class Iter>
+constexpr void test_iterators_1() {
+  test_iterators_2<Iter, Iter>();
+  test_iterators_2<Iter, sentinel_wrapper<Iter>>();
+}
+
+constexpr void test_iterators() {
+  test_iterators_1<random_access_iterator<int*>>();
+  test_iterators_1<contiguous_iterator<int*>>();
+  test_iterators_1<int*>();
+}
+
+constexpr bool test() {
+  test_iterators();
+
+  { // A custom comparator works.
+    const std::array input = {1, 2, 3, 5, 4};
+    std::array expected = {2, 4, 3, 5, 1};
+    auto comp = std::ranges::greater{};
+    {
+      auto in = input;
+      auto last = std::ranges::pop_heap(in.begin(), in.end(), comp);
+      assert(in == expected);
+      assert(last == in.data() + in.size());
+      assert(std::is_heap(in.begin(), in.end() - 1, comp));
+    }
+
+    {
+      auto in = input;
+      auto last = std::ranges::pop_heap(in, comp);
+      assert(in == expected);
+      assert(last == in.data() + in.size());
+      assert(std::is_heap(in.begin(), in.end() - 1, comp));
+    }
+  }
+
+  { // A custom projection works.
+    struct A {
+      int a;
+      constexpr auto operator<=>(const A&) const = default;
+    };
+
+    const std::array input = {A{3}, A{1}, A{2}};
+    std::array expected = {A{2}, A{1}, A{3}};
+    {
+      auto in = input;
+      auto last = std::ranges::pop_heap(in.begin(), in.end(), {}, &A::a);
+      verify_heap(in, last, expected);
+    }
+
+    {
+      auto in = input;
+      auto last = std::ranges::pop_heap(in, {}, &A::a);
+      verify_heap(in, last, expected);
+    }
+  }
+
+  { // `std::invoke` is used in the implementation.
+    struct A {
+      int i;
+      constexpr A(int i_) : i(i_) {}
+
+      constexpr bool comparator(const A& rhs) const { return i < rhs.i; }
+      constexpr const A& projection() const { return *this; }
+
+      constexpr auto operator<=>(const A&) const = default;
+    };
+
+    const std::array input = {A{3}, A{1}, A{2}};
+    std::array expected = {A{2}, A{1}, A{3}};
+    {
+      auto in = input;
+      auto last = std::ranges::pop_heap(in.begin(), in.end(), &A::comparator, &A::projection);
+      verify_heap(in, last, expected);
+    }
+
+    {
+      auto in = input;
+      auto last = std::ranges::pop_heap(in, &A::comparator, &A::projection);
+      verify_heap(in, last, expected);
+    }
+  }
+
+  { // The comparator can return any type that's convertible to `bool`.
+    const std::array input = {3, 1, 2};
+    std::array expected = {2, 1, 3};
+    {
+      auto in = input;
+      auto last = std::ranges::pop_heap(in.begin(), in.end(), [](int i, int j) { return BooleanTestable{i < j}; });
+      verify_heap(in, last, expected);
+    }
+
+    {
+      auto in = input;
+      auto last = std::ranges::pop_heap(in, [](int i, int j) { return BooleanTestable{i < j}; });
+      verify_heap(in, last, expected);
+    }
+  }
+
+  { // `std::ranges::dangling` is returned.
+    [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) result =
+        std::ranges::pop_heap(std::array{2, 1, 3});
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/push.heap/ranges_push_heap.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// <algorithm>
+
+// template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+//         class Proj = identity>
+//   requires sortable<I, Comp, Proj>
+//   constexpr I
+//     ranges::push_heap(I first, S last, Comp comp = {}, Proj proj = {});                   // since C++20
+//
+// template<random_access_range R, class Comp = ranges::less, class Proj = identity>
+//   requires sortable<iterator_t<R>, Comp, Proj>
+//   constexpr borrowed_iterator_t<R>
+//     ranges::push_heap(R&& r, Comp comp = {}, Proj proj = {});                             // since C++20
+
+#include <algorithm>
+#include <array>
+#include <concepts>
+#include <functional>
+#include <ranges>
+
+#include "almost_satisfies_types.h"
+#include "boolean_testable.h"
+#include "test_iterators.h"
+
+// SFINAE tests.
+
+using BadComparator = ComparatorNotCopyable<int*>;
+static_assert(!std::sortable<int*, BadComparator>);
+
+template <class Iter, class Sent = sentinel_wrapper<Iter>, class Comp = std::ranges::less>
+concept HasPushHeapIt = requires(Iter first, Sent last, Comp comp) { std::ranges::make_heap(first, last, comp); };
+
+static_assert(HasPushHeapIt<int*>);
+static_assert(!HasPushHeapIt<RandomAccessIteratorNotDerivedFrom>);
+static_assert(!HasPushHeapIt<RandomAccessIteratorBadIndex>);
+static_assert(!HasPushHeapIt<int*, SentinelForNotSemiregular>);
+static_assert(!HasPushHeapIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
+static_assert(!HasPushHeapIt<int*, int*, BadComparator>);
+static_assert(!HasPushHeapIt<const int*>); // Doesn't satisfy `sortable`.
+
+template <class Range, class Comp = std::ranges::less>
+concept HasPushHeapR = requires(Range range, Comp comp) { std::ranges::make_heap(range, comp); };
+
+static_assert(HasPushHeapR<UncheckedRange<int*>>);
+static_assert(!HasPushHeapR<RandomAccessRangeNotDerivedFrom>);
+static_assert(!HasPushHeapR<RandomAccessRangeBadIndex>);
+static_assert(!HasPushHeapR<UncheckedRange<int*, SentinelForNotSemiregular>>);
+static_assert(!HasPushHeapR<UncheckedRange<int*, SentinelForNotWeaklyEqualityComparableWith>>);
+static_assert(!HasPushHeapR<UncheckedRange<int*>, BadComparator>);
+static_assert(!HasPushHeapR<UncheckedRange<const int*>>); // Doesn't satisfy `sortable`.
+
+template <size_t N, class T, class Iter>
+constexpr void verify_heap(const std::array<T, N>& heapified, Iter last, std::array<T, N> expected) {
+  assert(heapified == expected);
+  assert(base(last) == heapified.data() + heapified.size());
+  assert(std::is_heap(heapified.begin(), heapified.end()));
+}
+
+template <class Iter, class Sent, size_t N>
+constexpr void test_one(const std::array<int, N> input, std::array<int, N> expected) {
+  if (!input.empty()) {
+    assert(std::is_heap(input.begin(), input.end() - 1));
+  }
+
+  { // (iterator, sentinel) overload.
+    auto heapified = input;
+    auto b = Iter(heapified.data());
+    auto e = Sent(Iter(heapified.data() + heapified.size()));
+
+    std::same_as<Iter> decltype(auto) last = std::ranges::push_heap(b, e);
+    verify_heap(heapified, last, expected);
+  }
+
+  { // (range) overload.
+    auto heapified = input;
+    auto b = Iter(heapified.data());
+    auto e = Sent(Iter(heapified.data() + heapified.size()));
+    auto range = std::ranges::subrange(b, e);
+
+    std::same_as<Iter> decltype(auto) last = std::ranges::push_heap(range);
+    verify_heap(heapified, last, expected);
+  }
+}
+
+template <class Iter, class Sent>
+constexpr void test_iterators_2() {
+  // Empty sequence.
+  test_one<Iter, Sent, 0>({}, {});
+  // 1-element sequence.
+  test_one<Iter, Sent, 1>({1}, {1});
+  // 2-element sequence.
+  test_one<Iter, Sent, 2>({2, 1}, {2, 1});
+  // 3-element sequence.
+  test_one<Iter, Sent, 3>({2, 1, 3}, {3, 1, 2});
+  // Longer sequence.
+  test_one<Iter, Sent, 8>({11, 6, 5, 1, 4, 3, 2, 8}, {11, 8, 5, 6, 4, 3, 2, 1});
+  // Longer sequence with duplicates.
+  test_one<Iter, Sent, 7>({8, 6, 3, 1, 2, 2, 6}, {8, 6, 6, 1, 2, 2, 3});
+  // All elements are the same.
+  test_one<Iter, Sent, 4>({1, 1, 1, 1}, {1, 1, 1, 1});
+  // Already heapified.
+  test_one<Iter, Sent, 5>({5, 4, 3, 1, 2}, {5, 4, 3, 1, 2});
+  // Reverse-sorted.
+  test_one<Iter, Sent, 5>({5, 4, 3, 2, 1}, {5, 4, 3, 2, 1});
+}
+
+template <class Iter>
+constexpr void test_iterators_1() {
+  test_iterators_2<Iter, Iter>();
+  test_iterators_2<Iter, sentinel_wrapper<Iter>>();
+}
+
+constexpr void test_iterators() {
+  test_iterators_1<random_access_iterator<int*>>();
+  test_iterators_1<contiguous_iterator<int*>>();
+  test_iterators_1<int*>();
+}
+
+constexpr bool test() {
+  test_iterators();
+
+  { // A custom comparator works.
+    const std::array input = {5, 4, 3, 2, 1};
+    std::array expected = {1, 5, 3, 2, 4};
+    {
+      auto in = input;
+      auto last = std::ranges::push_heap(in.begin(), in.end(), std::ranges::greater{});
+      assert(in == expected);
+      assert(last == in.end());
+    }
+
+    {
+      auto in = input;
+      auto last = std::ranges::push_heap(in, std::ranges::greater{});
+      assert(in == expected);
+      assert(last == in.end());
+    }
+  }
+
+  { // A custom projection works.
+    struct A {
+      int a;
+      constexpr auto operator<=>(const A&) const = default;
+    };
+
+    const std::array input = {A{2}, A{1}, A{3}};
+    std::array expected = {A{3}, A{1}, A{2}};
+    {
+      auto in = input;
+      auto last = std::ranges::push_heap(in.begin(), in.end(), {}, &A::a);
+      verify_heap(in, last, expected);
+    }
+
+    {
+      auto in = input;
+      auto last = std::ranges::push_heap(in, {}, &A::a);
+      verify_heap(in, last, expected);
+    }
+  }
+
+  { // `std::invoke` is used in the implementation.
+    struct A {
+      int i;
+      constexpr A(int i_) : i(i_) {}
+
+      constexpr bool comparator(const A& rhs) const { return i < rhs.i; }
+      constexpr const A& projection() const { return *this; }
+
+      constexpr auto operator<=>(const A&) const = default;
+    };
+
+    const std::array input = {A{2}, A{1}, A{3}};
+    std::array expected = {A{3}, A{1}, A{2}};
+    {
+      auto in = input;
+      auto last = std::ranges::push_heap(in.begin(), in.end(), &A::comparator, &A::projection);
+      verify_heap(in, last, expected);
+    }
+
+    {
+      auto in = input;
+      auto last = std::ranges::push_heap(in, &A::comparator, &A::projection);
+      verify_heap(in, last, expected);
+    }
+  }
+
+  { // The comparator can return any type that's convertible to `bool`.
+    const std::array input = {2, 1, 3};
+    std::array expected = {3, 1, 2};
+    {
+      auto in = input;
+      auto last = std::ranges::push_heap(in.begin(), in.end(), [](int i, int j) { return BooleanTestable{i < j}; });
+      verify_heap(in, last, expected);
+    }
+
+    {
+      auto in = input;
+      auto last = std::ranges::push_heap(in, [](int i, int j) { return BooleanTestable{i < j}; });
+      verify_heap(in, last, expected);
+    }
+  }
+
+  { // `std::ranges::dangling` is returned.
+    [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) result =
+        std::ranges::push_heap(std::array{1, 2, 3});
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/ranges_sort_heap.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// <algorithm>
+
+// template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
+//         class Proj = identity>
+//   requires sortable<I, Comp, Proj>
+//   constexpr I
+//     ranges::sort_heap(I first, S last, Comp comp = {}, Proj proj = {});                   // since C++20
+//
+// template<random_access_range R, class Comp = ranges::less, class Proj = identity>
+//   requires sortable<iterator_t<R>, Comp, Proj>
+//   constexpr borrowed_iterator_t<R>
+//     ranges::sort_heap(R&& r, Comp comp = {}, Proj proj = {});                             // since C++20
+
+#include <algorithm>
+#include <array>
+#include <concepts>
+#include <functional>
+#include <ranges>
+
+#include "almost_satisfies_types.h"
+#include "boolean_testable.h"
+#include "test_iterators.h"
+
+// SFINAE tests.
+
+using BadComparator = ComparatorNotCopyable<int*>;
+static_assert(!std::sortable<int*, BadComparator>);
+
+template <class Iter, class Sent = sentinel_wrapper<Iter>, class Comp = std::ranges::less>
+concept HasSortHeapIt = requires(Iter first, Sent last, Comp comp) { std::ranges::make_heap(first, last, comp); };
+
+static_assert(HasSortHeapIt<int*>);
+static_assert(!HasSortHeapIt<RandomAccessIteratorNotDerivedFrom>);
+static_assert(!HasSortHeapIt<RandomAccessIteratorBadIndex>);
+static_assert(!HasSortHeapIt<int*, SentinelForNotSemiregular>);
+static_assert(!HasSortHeapIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
+static_assert(!HasSortHeapIt<int*, int*, BadComparator>);
+static_assert(!HasSortHeapIt<const int*>); // Doesn't satisfy `sortable`.
+
+template <class Range, class Comp = std::ranges::less>
+concept HasSortHeapR = requires(Range range, Comp comp) { std::ranges::make_heap(range, comp); };
+
+static_assert(HasSortHeapR<UncheckedRange<int*>>);
+static_assert(!HasSortHeapR<RandomAccessRangeNotDerivedFrom>);
+static_assert(!HasSortHeapR<RandomAccessRangeBadIndex>);
+static_assert(!HasSortHeapR<UncheckedRange<int*, SentinelForNotSemiregular>>);
+static_assert(!HasSortHeapR<UncheckedRange<int*, SentinelForNotWeaklyEqualityComparableWith>>);
+static_assert(!HasSortHeapR<UncheckedRange<int*>, BadComparator>);
+static_assert(!HasSortHeapR<UncheckedRange<const int*>>); // Doesn't satisfy `sortable`.
+
+template <size_t N, class T, class Iter>
+constexpr void verify_sorted(const std::array<T, N>& sorted, Iter last, std::array<T, N> expected) {
+  assert(sorted == expected);
+  assert(base(last) == sorted.data() + sorted.size());
+  assert(std::is_sorted(sorted.begin(), sorted.end()));
+}
+
+template <class Iter, class Sent, size_t N>
+constexpr void test_one(const std::array<int, N> input, std::array<int, N> expected) {
+  assert(std::is_heap(input.begin(), input.end()));
+
+  { // (iterator, sentinel) overload.
+    auto sorted = input;
+    auto b = Iter(sorted.data());
+    auto e = Sent(Iter(sorted.data() + sorted.size()));
+
+    std::same_as<Iter> decltype(auto) last = std::ranges::sort_heap(b, e);
+    verify_sorted(sorted, last, expected);
+  }
+
+  { // (range) overload.
+    auto sorted = input;
+    auto b = Iter(sorted.data());
+    auto e = Sent(Iter(sorted.data() + sorted.size()));
+    auto range = std::ranges::subrange(b, e);
+
+    std::same_as<Iter> decltype(auto) last = std::ranges::sort_heap(range);
+    verify_sorted(sorted, last, expected);
+  }
+}
+
+template <class Iter, class Sent>
+constexpr void test_iterators_2() {
+  // 1-element sequence.
+  test_one<Iter, Sent, 1>({1}, {1});
+  // 2-element sequence.
+  test_one<Iter, Sent, 2>({2, 1}, {1, 2});
+  // 3-element sequence.
+  test_one<Iter, Sent, 3>({3, 1, 2}, {1, 2, 3});
+  // Longer sequence.
+  test_one<Iter, Sent, 8>({11, 8, 4, 6, 1, 2, 3, 5}, {1, 2, 3, 4, 5, 6, 8, 11});
+  // Longer sequence with duplicates.
+  test_one<Iter, Sent, 7>({8, 6, 6, 1, 2, 3, 2}, {1, 2, 2, 3, 6, 6, 8});
+  // All elements are the same.
+  test_one<Iter, Sent, 4>({1, 1, 1, 1}, {1, 1, 1, 1});
+}
+
+template <class Iter>
+constexpr void test_iterators_1() {
+  test_iterators_2<Iter, Iter>();
+  test_iterators_2<Iter, sentinel_wrapper<Iter>>();
+}
+
+constexpr void test_iterators() {
+  test_iterators_1<random_access_iterator<int*>>();
+  test_iterators_1<contiguous_iterator<int*>>();
+  test_iterators_1<int*>();
+}
+
+constexpr bool test() {
+  test_iterators();
+
+  { // A custom comparator works.
+    const std::array input = {1, 2, 3, 5, 4};
+    std::array expected = {5, 4, 3, 2, 1};
+    auto comp = std::ranges::greater{};
+    assert(std::is_heap(input.begin(), input.end(), comp));
+
+    {
+      auto in = input;
+      auto last = std::ranges::sort_heap(in.begin(), in.end(), comp);
+      assert(in == expected);
+      assert(last == in.data() + in.size());
+    }
+
+    {
+      auto in = input;
+      auto last = std::ranges::sort_heap(in, comp);
+      assert(in == expected);
+      assert(last == in.data() + in.size());
+    }
+  }
+
+  { // A custom projection works.
+    struct A {
+      int a;
+      constexpr auto operator<=>(const A&) const = default;
+    };
+
+    const std::array input = {A{3}, A{1}, A{2}};
+    std::array expected = {A{1}, A{2}, A{3}};
+    {
+      auto in = input;
+      auto last = std::ranges::sort_heap(in.begin(), in.end(), {}, &A::a);
+      verify_sorted(in, last, expected);
+    }
+
+    {
+      auto in = input;
+      auto last = std::ranges::sort_heap(in, {}, &A::a);
+      verify_sorted(in, last, expected);
+    }
+  }
+
+  { // `std::invoke` is used in the implementation.
+    struct A {
+      int i;
+      constexpr A(int i_) : i(i_) {}
+
+      constexpr bool comparator(const A& rhs) const { return i < rhs.i; }
+      constexpr const A& projection() const { return *this; }
+
+      constexpr auto operator<=>(const A&) const = default;
+    };
+
+    const std::array input = {A{3}, A{1}, A{2}};
+    std::array expected = {A{1}, A{2}, A{3}};
+    {
+      auto in = input;
+      auto last = std::ranges::sort_heap(in.begin(), in.end(), &A::comparator, &A::projection);
+      verify_sorted(in, last, expected);
+    }
+
+    {
+      auto in = input;
+      auto last = std::ranges::sort_heap(in, &A::comparator, &A::projection);
+      verify_sorted(in, last, expected);
+    }
+  }
+
+  { // The comparator can return any type that's convertible to `bool`.
+    const std::array input = {3, 1, 2};
+    std::array expected = {1, 2, 3};
+    {
+      auto in = input;
+      auto last = std::ranges::sort_heap(in.begin(), in.end(), [](int i, int j) { return BooleanTestable{i < j}; });
+      verify_sorted(in, last, expected);
+    }
+
+    {
+      auto in = input;
+      auto last = std::ranges::sort_heap(in, [](int i, int j) { return BooleanTestable{i < j}; });
+      verify_sorted(in, last, expected);
+    }
+  }
+
+  { // `std::ranges::dangling` is returned.
+    [[maybe_unused]] std::same_as<std::ranges::dangling> decltype(auto) result =
+        std::ranges::sort_heap(std::array{2, 1, 3});
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

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

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 

 //static_assert(test(std::ranges::is_heap, a));
 //static_assert(test(std::ranges::is_heap_until, a));
 static_assert(test(std::ranges::is_partitioned, a, odd));
 //static_assert(test(std::ranges::is_permutation, a, a));
 static_assert(test(std::ranges::is_sorted, a));
 static_assert(test(std::ranges::is_sorted_until, a));
 static_assert(test(std::ranges::lexicographical_compare, a, a));
 static_assert(test(std::ranges::lower_bound, a, 42));
-//static_assert(test(std::ranges::make_heap, a));
+static_assert(test(std::ranges::make_heap, a));
 static_assert(test(std::ranges::max, a));
 static_assert(test(std::ranges::max_element, a));
 //static_assert(test(std::ranges::merge, a, a, a));
 static_assert(test(std::ranges::min, a));
 static_assert(test(std::ranges::min_element, a));
 static_assert(test(std::ranges::minmax, a));
 static_assert(test(std::ranges::minmax_element, a));
 static_assert(test(std::ranges::mismatch, a, a));
 //static_assert(test(std::ranges::move, a, a));
 //static_assert(test(std::ranges::move_backward, a, a));
 //static_assert(test(std::ranges::next_permutation, a));
 static_assert(test(std::ranges::none_of, a, odd));
 //static_assert(test(std::ranges::nth_element, a, a+5));
 //static_assert(test(std::ranges::partial_sort, a, a+5));
 //static_assert(test(std::ranges::partial_sort_copy, a, a));
 //static_assert(test(std::ranges::partition, a, odd));
 //static_assert(test(std::ranges::partition_copy, a, a, a, odd));
 //static_assert(test(std::ranges::partition_point, a, odd));
-//static_assert(test(std::ranges::pop_heap, a));
+static_assert(test(std::ranges::pop_heap, a));
 //static_assert(test(std::ranges::prev_permutation, a));
-//static_assert(test(std::ranges::push_heap, 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));
 //static_assert(test(std::ranges::remove_copy_if, a, a, odd));
 //static_assert(test(std::ranges::remove_if, a, odd));
 static_assert(test(std::ranges::replace, a, 42, 43));
 //static_assert(test(std::ranges::replace_copy, a, a, 42, 43));
 //static_assert(test(std::ranges::replace_copy_if, a, a, odd, 43));
 static_assert(test(std::ranges::replace_if, a, odd, 43));
 static_assert(test(std::ranges::reverse, a));
 //static_assert(test(std::ranges::reverse_copy, a, a));
 //static_assert(test(std::ranges::rotate, a, a+5));
 //static_assert(test(std::ranges::rotate_copy, a, a+5, a));
 //static_assert(test(std::ranges::sample, a, a, 5));
 //static_assert(test(std::ranges::search, a, a));
 //static_assert(test(std::ranges::search_n, a, 10, 42));
 //static_assert(test(std::ranges::set_difference, a, a, a));
 //static_assert(test(std::ranges::set_intersection, a, a, a));
 //static_assert(test(std::ranges::set_symmetric_difference, a, a, a));
 //static_assert(test(std::ranges::set_union, a, a, a));
 //static_assert(test(std::ranges::shuffle, a, g));
 static_assert(test(std::ranges::sort, a));
-//static_assert(test(std::ranges::sort_heap, a));
+static_assert(test(std::ranges::sort_heap, a));
 //static_assert(test(std::ranges::stable_partition, a, odd));
 //static_assert(test(std::ranges::stable_sort, a));
 //static_assert(test(std::ranges::starts_with, a, a));
 static_assert(test(std::ranges::swap_ranges, a, a));
 static_assert(test(std::ranges::transform, a, a, triple));
 //static_assert(test(std::ranges::unique, a));
 //static_assert(test(std::ranges::unique_copy, a, a));
 static_assert(test(std::ranges::upper_bound, a, 42));