[libc++] [P0879] constexpr heap and partial_sort algorithms

[• Quuxplusone]

Summary

Now the only ones we're still missing from P0879 are sort and nth_element.

(nth_element is actually not trivial, because the existing implementation uses a goto label.)

[• Quuxplusone]

Rebase on D93443. @ldionne ping (after D93443)!

[ldionne]

Generally looks good, I'm just asking for a bit more manual testing. Thanks a lot for working on this, I love that we're removing dependencies on <random>.

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

26–34

Can you please also add a few dumb hand-written test cases? You know I love those, right?

Same for the other algorithms whose tests have been rewritten.

[• Quuxplusone]

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

26–34

The trick for make_heap is that there are multiple possible outputs (theoretically): heapifying {1,2,3} might give you {3,1,2} or it might give you {3,2,1}. Both possibilities are equally conforming, even though I would guess that all implementations really do the same thing in practice.

How much do we care about that? Do we mind hard-coding one of the outputs as "blessed"?

Anyway, I'm resisting out of laziness — couldn't someone else add ad-hoc tests in a separate commit? — but maybe it'd help to see an example of the kind of test you're thinking of. I mean would it just be like this?

TEST_CONSTEXPR_CXX20 bool test_simple() {
    int a[] = {5,2,4,1,3};
    std::push_heap(a, a+5);
    int expected[] = {5,3,4,1,2};
    assert(std::equal(a, a+5, expected, expected+5));
    return true;
}

TEST_CONSTEXPR_CXX20 bool test_simple() {
    int a[] = {5,2,4,1,3};
    std::pop_heap(a, a+5);
    int expected[] = {4,2,3,1,5};
    assert(std::equal(a, a+5, expected, expected+5));
    return true;
}

[ldionne]

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

26–34

What I want is pretty trivial, just "unroll" a few cases from your loop so they are more explicit. I want the tests to be as dumb as possible, because imagine for instance if there was a mistake in your loop conditions and it never ran? The test would be useless. Having at least a few really dumb tests removes this sort of issue.

Of course, there's a balance to strike. It doesn't always make sense to push too far with this sort of defensive behavior, but here it's pretty easy. For make_heap, something like this would satisfy me:

{
    int input[] = {3, 4, 1, 2, 5};
    std::make_heap(Iter(input), Iter(input + 5));
    assert(std::is_heap(input, input + 5));
    std::pop_heap(input, input + 5); assert(input[4] == 5);
    std::pop_heap(input, input + 4); assert(input[3] == 4);
    std::pop_heap(input, input + 3); assert(input[2] == 3);
    std::pop_heap(input, input + 2); assert(input[1] == 2);
    std::pop_heap(input, input + 1); assert(input[0] == 1);
}

You can put that inside test() itself. Does that make sense to you?

Another way to think about this: Imagine you're a user and you try to use libc++'s std::make_heap. Imagine the very first and most basic thing you might write just to try it out. Wouldn't it be a huge embarrassment if it didn't work for some reason? Well, we might as well just check-in a few of the most common and dumb examples of how to use facilities to guard us from that.

[• Quuxplusone]

Add "simple" ad-hoc tests at @ldionne's request.
Poke buildkite.

[• Quuxplusone]

Poke buildbot. (The last build https://reviews.llvm.org/B86646 seems to have failed in a devopsy way, and clicking "Restart Builds" just tells me I haven't got permissions for that.)

[• Quuxplusone]

Poke buildkite yet again. ( https://reviews.llvm.org/B86662 failed in the same way.)

[• Quuxplusone]

Poke buildkite yet again. One day it'll finish a build.

[• Quuxplusone]

@ldionne: I don't think buildkite is ever going to finish a build here. I propose that you approve this revision and I just go again and land it, and we'll see what happens with the buildbots after that. (If it somehow does break buildbots, we can revert it.) Thoughts?

[ldionne]

In D93512#2525171, @Quuxplusone wrote:

@ldionne: I don't think buildkite is ever going to finish a build here. I propose that you approve this revision and I just go again and land it, and we'll see what happens with the buildbots after that. (If it somehow does break buildbots, we can revert it.) Thoughts?

I've restarted the failing job. I've been having a few issues with the builders for the past 2 days. The laptops are being overworked :-)

Let's land this once https://buildkite.com/llvm-project/libcxx-ci/builds/1140 has succeeded.

libcxx/include/algorithm

     void
     stable_sort(RandomAccessIterator first, RandomAccessIterator last);
 
 template <class RandomAccessIterator, class Compare>
     void
     stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
 
 template <class RandomAccessIterator>
-    void
+    constexpr void                    // constexpr in C++20
     partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);
 
 template <class RandomAccessIterator, class Compare>
-    void
+    constexpr void                    // constexpr in C++20
     partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);
 
 template <class InputIterator, class RandomAccessIterator>
-    RandomAccessIterator
+    constexpr RandomAccessIterator    // constexpr in C++20
     partial_sort_copy(InputIterator first, InputIterator last,
                       RandomAccessIterator result_first, RandomAccessIterator result_last);
 
 template <class InputIterator, class RandomAccessIterator, class Compare>
-    RandomAccessIterator
+    constexpr RandomAccessIterator    // constexpr in C++20
     partial_sort_copy(InputIterator first, InputIterator last,
                       RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);
 
 template <class RandomAccessIterator>
     void
     nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
 
 template <class RandomAccessIterator, class Compare>

                              InputIterator2 first2, InputIterator2 last2, OutputIterator result);
 
 template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
     constexpr OutputIterator                         // constexpr in C++20
     set_symmetric_difference(InputIterator1 first1, InputIterator1 last1,
                              InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);
 
 template <class RandomAccessIterator>
-    void
+    constexpr void                                   // constexpr in C++20
     push_heap(RandomAccessIterator first, RandomAccessIterator last);
 
 template <class RandomAccessIterator, class Compare>
-    void
+    constexpr void                                   // constexpr in C++20
     push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
 
 template <class RandomAccessIterator>
-    void
+    constexpr void                                   // constexpr in C++20
     pop_heap(RandomAccessIterator first, RandomAccessIterator last);
 
 template <class RandomAccessIterator, class Compare>
-    void
+    constexpr void                                   // constexpr in C++20
     pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
 
 template <class RandomAccessIterator>
-    void
+    constexpr void                                   // constexpr in C++20
     make_heap(RandomAccessIterator first, RandomAccessIterator last);
 
 template <class RandomAccessIterator, class Compare>
-    void
+    constexpr void                                   // constexpr in C++20
     make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
 
 template <class RandomAccessIterator>
-    void
+    constexpr void                                   // constexpr in C++20
     sort_heap(RandomAccessIterator first, RandomAccessIterator last);
 
 template <class RandomAccessIterator, class Compare>
-    void
+    constexpr void                                   // constexpr in C++20
     sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
 
 template <class RandomAccessIterator>
     constexpr bool   // constexpr in C++20
     is_heap(RandomAccessIterator first, RandomAccessiterator last);
 
 template <class RandomAccessIterator, class Compare>
     constexpr bool   // constexpr in C++20

 is_heap(_RandomAccessIterator __first, _RandomAccessIterator __last)
 {
     return _VSTD::is_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
 }
 
 // push_heap
 
 template <class _Compare, class _RandomAccessIterator>
-void
+_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;

                 __ptr = __first + __len;
             } while (__comp(*__ptr, __t));
             *__last = _VSTD::move(__t);
         }
     }
 }
 
 template <class _RandomAccessIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY
+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);
 }
 
 template <class _RandomAccessIterator>
-inline _LIBCPP_INLINE_VISIBILITY
+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>());
 }
 
 // pop_heap
 
 template <class _Compare, class _RandomAccessIterator>
-void
+_LIBCPP_CONSTEXPR_AFTER_CXX11 void
 __sift_down(_RandomAccessIterator __first, _RandomAccessIterator /*__last*/,
             _Compare __comp,
             typename iterator_traits<_RandomAccessIterator>::difference_type __len,
             _RandomAccessIterator __start)
 {
     typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type;
     typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type;
     // left-child of __start is at 2 * __start + 1

     // check if we are in heap-order
     if (__comp(*__child_i, *__start))
         // we are, __start is larger than it's largest child
         return;
 
     value_type __top(_VSTD::move(*__start));
     do
     {
-        // we are not in heap-order, swap the parent with it's largest child
+        // we are not in heap-order, swap the parent with its largest child
         *__start = _VSTD::move(*__child_i);
         __start = __child_i;
 
         if ((__len - 2) / 2 < __child)
             break;
 
         // recompute the child based off of the updated parent
         __child = 2 * __child + 1;
         __child_i = __first + __child;
 
         if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) {
             // right-child exists and is greater than left-child
             ++__child_i;
             ++__child;
         }
 
         // check if we are in heap-order
     } while (!__comp(*__child_i, __top));
     *__start = _VSTD::move(__top);
 }
 
 template <class _Compare, class _RandomAccessIterator>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 __pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp,
            typename iterator_traits<_RandomAccessIterator>::difference_type __len)
 {
     if (__len > 1)
     {
         swap(*__first, *--__last);
         _VSTD::__sift_down<_Compare>(__first, __last, __comp, __len - 1, __first);
     }
 }
 
 template <class _RandomAccessIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY
+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);
 }
 
 template <class _RandomAccessIterator>
-inline _LIBCPP_INLINE_VISIBILITY
+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>());
 }
 
 // make_heap
 
 template <class _Compare, class _RandomAccessIterator>
-void
+_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, __last, __comp, __n, __first + __start);
         }
     }
 }
 
 template <class _RandomAccessIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY
+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);
 }
 
 template <class _RandomAccessIterator>
-inline _LIBCPP_INLINE_VISIBILITY
+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>());
 }
 
 // sort_heap
 
 template <class _Compare, class _RandomAccessIterator>
-void
+_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);
 }
 
 template <class _RandomAccessIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY
+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);
 }
 
 template <class _RandomAccessIterator>
-inline _LIBCPP_INLINE_VISIBILITY
+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>());
 }
 
 // partial_sort
 
 template <class _Compare, class _RandomAccessIterator>
-void
+_LIBCPP_CONSTEXPR_AFTER_CXX17 void
 __partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
              _Compare __comp)
 {
     _VSTD::__make_heap<_Compare>(__first, __middle, __comp);
     typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first;
     for (_RandomAccessIterator __i = __middle; __i != __last; ++__i)
     {
         if (__comp(*__i, *__first))
         {
             swap(*__i, *__first);
             _VSTD::__sift_down<_Compare>(__first, __middle, __comp, __len, __first);
         }
     }
     _VSTD::__sort_heap<_Compare>(__first, __middle, __comp);
 }
 
 template <class _RandomAccessIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last,
              _Compare __comp)
 {
     typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
     _VSTD::__partial_sort<_Comp_ref>(__first, __middle, __last, __comp);
 }
 
 template <class _RandomAccessIterator>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 void
 partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last)
 {
     _VSTD::partial_sort(__first, __middle, __last,
                        __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
 }
 
 // partial_sort_copy
 
 template <class _Compare, class _InputIterator, class _RandomAccessIterator>
-_RandomAccessIterator
+_LIBCPP_CONSTEXPR_AFTER_CXX17 _RandomAccessIterator
 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
                     _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
 {
     _RandomAccessIterator __r = __result_first;
     if (__r != __result_last)
     {
         for (; __first != __last && __r != __result_last; ++__first, (void) ++__r)
             *__r = *__first;
         _VSTD::__make_heap<_Compare>(__result_first, __r, __comp);
         typename iterator_traits<_RandomAccessIterator>::difference_type __len = __r - __result_first;
         for (; __first != __last; ++__first)
             if (__comp(*__first, *__result_first))
             {
                 *__result_first = *__first;
                 _VSTD::__sift_down<_Compare>(__result_first, __r, __comp, __len, __result_first);
             }
         _VSTD::__sort_heap<_Compare>(__result_first, __r, __comp);
     }
     return __r;
 }
 
 template <class _InputIterator, class _RandomAccessIterator, class _Compare>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _RandomAccessIterator
 partial_sort_copy(_InputIterator __first, _InputIterator __last,
                   _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp)
 {
     typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
     return _VSTD::__partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __comp);
 }
 
 template <class _InputIterator, class _RandomAccessIterator>
-inline _LIBCPP_INLINE_VISIBILITY
+inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
 _RandomAccessIterator
 partial_sort_copy(_InputIterator __first, _InputIterator __last,
                   _RandomAccessIterator __result_first, _RandomAccessIterator __result_last)
 {
     return _VSTD::partial_sort_copy(__first, __last, __result_first, __result_last,
                                    __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
 }
 

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/make.heap/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
 //
 //===----------------------------------------------------------------------===//
 
 // <algorithm>
 
 // template<RandomAccessIterator Iter>
 //   requires ShuffleIterator<Iter> && LessThanComparable<Iter::value_type>
-//   void
+//   constexpr void  // constexpr in C++20
 //   make_heap(Iter first, Iter last);
 
 #include <algorithm>
-#include <random>
 #include <cassert>
 
 #include "test_macros.h"
 #include "test_iterators.h"
+#include "MoveOnly.h"
 
-std::mt19937 randomness;
-
-void test(int N)
+template<class T, class Iter>
+TEST_CONSTEXPR_CXX20 bool test()
 {
-    int* ia = new int [N];
-    for (int i = 0; i < N; ++i)
-        ia[i] = i;
-    std::shuffle(ia, ia+N, randomness);
-    std::make_heap(ia, ia+N);
-    assert(std::is_heap(ia, ia+N));
-
-    typedef random_access_iterator<int *> RI;
-    std::shuffle(RI(ia), RI(ia+N), randomness);
-    std::make_heap(RI(ia), RI(ia+N));
-    assert(std::is_heap(RI(ia), RI(ia+N)));
-
-    delete [] ia;
+    int orig[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    T work[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    for (int n = 0; n < 15; ++n) {
+        std::make_heap(Iter(work), Iter(work+n));
+        assert(std::is_heap(work, work+n));
+        assert(std::is_permutation(work, work+n, orig));
+        std::copy(orig, orig+n, work);
+    }
+    return true;
 }
 
 int main(int, char**)
 {
-    test(0);
-    test(1);
-    test(2);
-    test(3);
-    test(10);
-    test(1000);
+    test<int, random_access_iterator<int*> >();
+    test<int, int*>();
+
+#if TEST_STD_VER >= 11
+    test<MoveOnly, random_access_iterator<MoveOnly*>>();
+    test<MoveOnly, MoveOnly*>();
+#endif
+
+#if TEST_STD_VER >= 20
+    static_assert(test<int, random_access_iterator<int*>>());
+    static_assert(test<int, int*>());
+    static_assert(test<MoveOnly, random_access_iterator<MoveOnly*>>());
+    static_assert(test<MoveOnly, MoveOnly*>());
+#endif
 
     return 0;
 }

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/make.heap/make_heap_comp.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
 //
 //===----------------------------------------------------------------------===//
 
 // <algorithm>
 
-// template<RandomAccessIterator Iter, StrictWeakOrder<auto, Iter::value_type> Compare>
-//   requires ShuffleIterator<Iter> && CopyConstructible<Compare>
-//   void
+// template<RandomAccessIterator Iter>
+//   requires ShuffleIterator<Iter> && LessThanComparable<Iter::value_type>
+//   constexpr void  // constexpr in C++20
 //   make_heap(Iter first, Iter last, Compare comp);
 
 #include <algorithm>
-#include <functional>
-#include <memory>
-#include <random>
 #include <cassert>
+#include <functional>
 
 #include "test_macros.h"
-#include "counting_predicates.h"
 #include "test_iterators.h"
+#include "MoveOnly.h"
 
-struct indirect_less
-{
-    template <class P>
-    bool operator()(const P& x, const P& y)
-        {return *x < *y;}
-};
-
-std::mt19937 randomness;
-
-void test(int N)
-{
-    int* ia = new int [N];
-    {
-    for (int i = 0; i < N; ++i)
-        ia[i] = i;
-    std::shuffle(ia, ia+N, randomness);
-    std::make_heap(ia, ia+N, std::greater<int>());
-    assert(std::is_heap(ia, ia+N, std::greater<int>()));
-
-    std::shuffle(ia, ia+N, randomness);
-    std::make_heap(random_access_iterator<int *>(ia),
-                   random_access_iterator<int *>(ia+N), std::greater<int>());
-    assert(std::is_heap(ia, ia+N, std::greater<int>()));
-    }
-
-//  Ascending
-    {
-    binary_counting_predicate<std::greater<int>, int, int> pred ((std::greater<int>()));
-    for (int i = 0; i < N; ++i)
-        ia[i] = i;
-    std::make_heap(ia, ia+N, std::ref(pred));
-    assert(pred.count() <= 3u*N);
-    assert(std::is_heap(ia, ia+N, pred));
-    }
-
-//  Descending
-    {
-    binary_counting_predicate<std::greater<int>, int, int> pred ((std::greater<int>()));
-    for (int i = 0; i < N; ++i)
-        ia[N-1-i] = i;
-    std::make_heap(ia, ia+N, std::ref(pred));
-    assert(pred.count() <= 3u*N);
-    assert(std::is_heap(ia, ia+N, pred));
-    }
-
-//  Random
-    {
-    binary_counting_predicate<std::greater<int>, int, int> pred ((std::greater<int>()));
-    std::shuffle(ia, ia+N, randomness);
-    std::make_heap(ia, ia+N, std::ref(pred));
-    assert(pred.count() <= 3u*N);
-    assert(std::is_heap(ia, ia+N, pred));
+template<class T, class Iter>
+TEST_CONSTEXPR_CXX20 bool test()
+    int orig[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    T work[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    for (int n = 0; n < 15; ++n) {
+        std::make_heap(Iter(work), Iter(work+n), std::greater<T>());
+        assert(std::is_heap(work, work+n, std::greater<T>()));
+        assert(std::is_permutation(work, work+n, orig));
+        std::copy(orig, orig+n, work);
     }
-
-    delete [] ia;
+    return true;
 }
 
 int main(int, char**)
 {
-    test(0);
-    test(1);
-    test(2);
-    test(3);
-    test(10);
-    test(1000);
-    test(10000);
-    test(100000);
+    test<int, random_access_iterator<int*> >();
+    test<int, int*>();
 
 #if TEST_STD_VER >= 11
-    {
-    const int N = 1000;
-    std::unique_ptr<int>* ia = new std::unique_ptr<int> [N];
-    for (int i = 0; i < N; ++i)
-        ia[i].reset(new int(i));
-    std::shuffle(ia, ia+N, randomness);
-    std::make_heap(ia, ia+N, indirect_less());
-    assert(std::is_heap(ia, ia+N, indirect_less()));
-    delete [] ia;
-    }
+    test<MoveOnly, random_access_iterator<MoveOnly*>>();
+    test<MoveOnly, MoveOnly*>();
+#endif
+
+#if TEST_STD_VER >= 20
+    static_assert(test<int, random_access_iterator<int*>>());
+    static_assert(test<int, int*>());
+    static_assert(test<MoveOnly, random_access_iterator<MoveOnly*>>());
+    static_assert(test<MoveOnly, MoveOnly*>());
 #endif
 
     return 0;
 }

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/pop.heap/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
 //
 //===----------------------------------------------------------------------===//
 
 // <algorithm>
 
 // template<RandomAccessIterator Iter>
 //   requires ShuffleIterator<Iter> && LessThanComparable<Iter::value_type>
-//   void
+//   constexpr void  // constexpr in C++20
 //   pop_heap(Iter first, Iter last);
 
 #include <algorithm>
-#include <random>
 #include <cassert>
+#include <functional>
 
 #include "test_macros.h"
 #include "test_iterators.h"
+#include "MoveOnly.h"
 
-std::mt19937 randomness;
-
-void test(int N)
-{
-    int* ia = new int [N];
-    for (int i = 0; i < N; ++i)
-        ia[i] = i;
-    std::shuffle(ia, ia+N, randomness);
-    std::make_heap(ia, ia+N);
-    for (int i = N; i > 0; --i)
-    {
-        std::pop_heap(ia, ia+i);
-        assert(std::is_heap(ia, ia+i-1));
-    }
-    std::pop_heap(ia, ia);
-
-
-    typedef random_access_iterator<int *> RI;
-    std::shuffle(RI(ia), RI(ia+N), randomness);
-    std::make_heap(RI(ia), RI(ia+N));
-    for (int i = N; i > 0; --i)
-    {
-        std::pop_heap(RI(ia), RI(ia+i));
-        assert(std::is_heap(RI(ia), RI(ia+i-1)));
+template<class T, class Iter>
+TEST_CONSTEXPR_CXX20 bool test()
+    T orig[15] = {9,6,9,5,5, 8,9,1,1,3, 5,3,4,7,2};
+    T work[15] = {9,6,9,5,5, 8,9,1,1,3, 5,3,4,7,2};
+    assert(std::is_heap(orig, orig+15));
+    for (int i = 15; i >= 1; --i) {
+        std::pop_heap(Iter(work), Iter(work+i));
+        assert(std::is_heap(work, work+i-1));
+        assert(std::max_element(work, work+i-1) == work);
+        assert(std::is_permutation(work, work+15, orig));
     }
-    std::pop_heap(RI(ia), RI(ia));
-
-    delete [] ia;
+    assert(std::is_sorted(work, work+15));
+    return true;
 }
 
 int main(int, char**)
 {
-    test(1000);
+    test<int, random_access_iterator<int*> >();
+    test<int, int*>();
+
+#if TEST_STD_VER >= 11
+    test<MoveOnly, random_access_iterator<MoveOnly*>>();
+    test<MoveOnly, MoveOnly*>();
+#endif
+
+#if TEST_STD_VER >= 20
+    static_assert(test<int, random_access_iterator<int*>>());
+    static_assert(test<int, int*>());
+    static_assert(test<MoveOnly, random_access_iterator<MoveOnly*>>());
+    static_assert(test<MoveOnly, MoveOnly*>());
+#endif
 
     return 0;
 }

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/pop.heap/pop_heap_comp.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
 //
 //===----------------------------------------------------------------------===//
 
 // <algorithm>
 
-// template<RandomAccessIterator Iter, StrictWeakOrder<auto, Iter::value_type> Compare>
-//   requires ShuffleIterator<Iter> && CopyConstructible<Compare>
-//   void
+// template<RandomAccessIterator Iter>
+//   requires ShuffleIterator<Iter> && LessThanComparable<Iter::value_type>
+//   constexpr void  // constexpr in C++20
 //   pop_heap(Iter first, Iter last, Compare comp);
 
 #include <algorithm>
-#include <functional>
-#include <random>
 #include <cassert>
-#include <memory>
+#include <functional>
 
 #include "test_macros.h"
 #include "test_iterators.h"
+#include "MoveOnly.h"
 
-struct indirect_less
+template<class T, class Iter>
+TEST_CONSTEXPR_CXX20 bool test()
 {
-    template <class P>
-    bool operator()(const P& x, const P& y)
-        {return *x < *y;}
-};
-
-
-std::mt19937 randomness;
-
-void test(int N)
-{
-    int* ia = new int [N];
-    for (int i = 0; i < N; ++i)
-        ia[i] = i;
-    std::shuffle(ia, ia+N, randomness);
-    std::make_heap(ia, ia+N, std::greater<int>());
-    for (int i = N; i > 0; --i)
-    {
-        std::pop_heap(ia, ia+i, std::greater<int>());
-        assert(std::is_heap(ia, ia+i-1, std::greater<int>()));
+    T orig[15] = {1,1,2,3,3, 8,4,6,5,5, 5,9,9,7,9};
+    T work[15] = {1,1,2,3,3, 8,4,6,5,5, 5,9,9,7,9};
+    assert(std::is_heap(orig, orig+15, std::greater<T>()));
+    for (int i = 15; i >= 1; --i) {
+        std::pop_heap(Iter(work), Iter(work+i), std::greater<T>());
+        assert(std::is_heap(work, work+i-1, std::greater<T>()));
+        assert(std::min_element(work, work+i-1) == work);
+        assert(std::is_permutation(work, work+15, orig));
     }
-    std::pop_heap(ia, ia, std::greater<int>());
-
-    typedef random_access_iterator<int *> RI;
-    std::shuffle(RI(ia), RI(ia+N), randomness);
-    std::make_heap(RI(ia), RI(ia+N), std::greater<int>());
-    for (int i = N; i > 0; --i)
-    {
-        std::pop_heap(RI(ia), RI(ia+i), std::greater<int>());
-        assert(std::is_heap(RI(ia), RI(ia+i-1), std::greater<int>()));
-    }
-    std::pop_heap(RI(ia), RI(ia), std::greater<int>());
-
-    delete [] ia;
+    assert(std::is_sorted(work, work+15, std::greater<T>()));
+    return true;
 }
 
 int main(int, char**)
 {
-    test(1000);
+    test<int, random_access_iterator<int*> >();
+    test<int, int*>();
 
 #if TEST_STD_VER >= 11
-    {
-    const int N = 1000;
-    std::unique_ptr<int>* ia = new std::unique_ptr<int> [N];
-    for (int i = 0; i < N; ++i)
-        ia[i].reset(new int(i));
-    std::shuffle(ia, ia+N, randomness);
-    std::make_heap(ia, ia+N, indirect_less());
-    for (int i = N; i > 0; --i)
-    {
-        std::pop_heap(ia, ia+i, indirect_less());
-        assert(std::is_heap(ia, ia+i-1, indirect_less()));
-    }
-    delete [] ia;
-    }
+    test<MoveOnly, random_access_iterator<MoveOnly*>>();
+    test<MoveOnly, MoveOnly*>();
+#endif
+
+#if TEST_STD_VER >= 20
+    static_assert(test<int, random_access_iterator<int*>>());
+    static_assert(test<int, int*>());
+    static_assert(test<MoveOnly, random_access_iterator<MoveOnly*>>());
+    static_assert(test<MoveOnly, MoveOnly*>());
 #endif
 
     return 0;
 }

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/push.heap/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
 //
 //===----------------------------------------------------------------------===//
 
 // <algorithm>
 
 // template<RandomAccessIterator Iter>
-//   requires ShuffleIterator<Iter>
-//         && LessThanComparable<Iter::value_type>
-//   void
+//   requires ShuffleIterator<Iter> && LessThanComparable<Iter::value_type>
+//   constexpr void  // constexpr in C++20
 //   push_heap(Iter first, Iter last);
 
 #include <algorithm>
-#include <random>
 #include <cassert>
+#include <functional>
 
 #include "test_macros.h"
 #include "test_iterators.h"
+#include "MoveOnly.h"
 
-std::mt19937 randomness;
-
-void test(int N)
-{
-    int* ia = new int [N];
-    for (int i = 0; i < N; ++i)
-        ia[i] = i;
-    std::shuffle(ia, ia+N, randomness);
-    for (int i = 0; i <= N; ++i)
-    {
-        std::push_heap(ia, ia+i);
-        assert(std::is_heap(ia, ia+i));
+template<class T, class Iter>
+TEST_CONSTEXPR_CXX20 bool test()
+    T orig[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    T work[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    for (int i = 1; i < 15; ++i) {
+        std::push_heap(Iter(work), Iter(work+i));
+        assert(std::is_permutation(work, work+i, orig));
+        assert(std::is_heap(work, work+i));
     }
-
-    typedef random_access_iterator<int *> RI;
-    std::shuffle(RI(ia), RI(ia+N), randomness);
-    for (int i = 0; i <= N; ++i)
-    {
-        std::push_heap(RI(ia), RI(ia+i));
-        assert(std::is_heap(RI(ia), RI(ia+i)));
-    }
-
-    delete [] ia;
+    return true;
 }
 
 int main(int, char**)
 {
-    test(1000);
+    test<int, random_access_iterator<int*> >();
+    test<int, int*>();
+
+#if TEST_STD_VER >= 11
+    test<MoveOnly, random_access_iterator<MoveOnly*>>();
+    test<MoveOnly, MoveOnly*>();
+#endif
+
+#if TEST_STD_VER >= 20
+    static_assert(test<int, random_access_iterator<int*>>());
+    static_assert(test<int, int*>());
+    static_assert(test<MoveOnly, random_access_iterator<MoveOnly*>>());
+    static_assert(test<MoveOnly, MoveOnly*>());
+#endif
 
     return 0;
 }

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/push.heap/push_heap_comp.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
 //
 //===----------------------------------------------------------------------===//
 
 // <algorithm>
 
 // template<RandomAccessIterator Iter>
-//   requires ShuffleIterator<Iter>
-//         && LessThanComparable<Iter::value_type>
-//   void
+//   requires ShuffleIterator<Iter> && LessThanComparable<Iter::value_type>
+//   constexpr void  // constexpr in C++20
 //   push_heap(Iter first, Iter last);
 
 #include <algorithm>
-#include <functional>
-#include <random>
 #include <cassert>
-#include <memory>
+#include <functional>
 
 #include "test_macros.h"
 #include "test_iterators.h"
+#include "MoveOnly.h"
 
-struct indirect_less
-{
-    template <class P>
-    bool operator()(const P& x, const P& y)
-        {return *x < *y;}
-};
-
-std::mt19937 randomness;
-
-void test(int N)
-{
-    int* ia = new int [N];
-    for (int i = 0; i < N; ++i)
-        ia[i] = i;
-    std::shuffle(ia, ia+N, randomness);
-    for (int i = 0; i <= N; ++i)
-    {
-        std::push_heap(ia, ia+i, std::greater<int>());
-        assert(std::is_heap(ia, ia+i, std::greater<int>()));
-    }
-
-    typedef random_access_iterator<int *> RI;
-    std::shuffle(RI(ia), RI(ia+N), randomness);
-    for (int i = 0; i <= N; ++i)
-    {
-        std::push_heap(RI(ia), RI(ia+i), std::greater<int>());
-        assert(std::is_heap(RI(ia), RI(ia+i), std::greater<int>()));
+template<class T, class Iter>
+TEST_CONSTEXPR_CXX20 bool test()
+    T orig[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    T work[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    for (int i = 1; i < 15; ++i) {
+        std::push_heap(Iter(work), Iter(work+i), std::greater<T>());
+        assert(std::is_permutation(work, work+i, orig));
+        assert(std::is_heap(work, work+i, std::greater<T>()));
     }
-
-    delete [] ia;
+    return true;
 }
 
 int main(int, char**)
 {
-    test(1000);
+    test<int, random_access_iterator<int*> >();
+    test<int, int*>();
 
 #if TEST_STD_VER >= 11
-    {
-    const int N = 1000;
-    std::unique_ptr<int>* ia = new std::unique_ptr<int> [N];
-    for (int i = 0; i < N; ++i)
-        ia[i].reset(new int(i));
-    std::shuffle(ia, ia+N, randomness);
-    for (int i = 0; i <= N; ++i)
-    {
-        std::push_heap(ia, ia+i, indirect_less());
-        assert(std::is_heap(ia, ia+i, indirect_less()));
-    }
-    delete [] ia;
-    }
+    test<MoveOnly, random_access_iterator<MoveOnly*>>();
+    test<MoveOnly, MoveOnly*>();
+#endif
+
+#if TEST_STD_VER >= 20
+    static_assert(test<int, random_access_iterator<int*>>());
+    static_assert(test<int, int*>());
+    static_assert(test<MoveOnly, random_access_iterator<MoveOnly*>>());
+    static_assert(test<MoveOnly, MoveOnly*>());
 #endif
 
     return 0;
 }

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/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
 //
 //===----------------------------------------------------------------------===//
 
 // <algorithm>
 
 // template<RandomAccessIterator Iter>
 //   requires ShuffleIterator<Iter> && LessThanComparable<Iter::value_type>
-//   void
+//   constexpr void  // constexpr in C++20
 //   sort_heap(Iter first, Iter last);
 
 #include <algorithm>
-#include <random>
 #include <cassert>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 
-std::mt19937 randomness;
+#include "test_macros.h"
+#include "test_iterators.h"
+#include "MoveOnly.h"
 
-void test(int N)
+template<class T, class Iter>
+TEST_CONSTEXPR_CXX20 bool test()
 {
-    int* ia = new int [N];
-    for (int i = 0; i < N; ++i)
-        ia[i] = i;
-    std::shuffle(ia, ia+N, randomness);
-    std::make_heap(ia, ia+N);
-    std::sort_heap(ia, ia+N);
-    assert(std::is_sorted(ia, ia+N));
-
-    typedef random_access_iterator<int *> RI;
-    std::shuffle(RI(ia), RI(ia+N), randomness);
-    std::make_heap(RI(ia), RI(ia+N));
-    std::sort_heap(RI(ia), RI(ia+N));
-    assert(std::is_sorted(RI(ia), RI(ia+N)));
-
-    delete [] ia;
+    int orig[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    T work[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    for (int n = 0; n < 15; ++n) {
+        std::make_heap(work, work+n);
+        std::sort_heap(Iter(work), Iter(work+n));
+        assert(std::is_sorted(work, work+n));
+        assert(std::is_permutation(work, work+n, orig));
+        std::copy(orig, orig+n, work);
+    }
+    return true;
 }
 
 int main(int, char**)
 {
-    test(0);
-    test(1);
-    test(2);
-    test(3);
-    test(10);
-    test(1000);
+    test<int, random_access_iterator<int*> >();
+    test<int, int*>();
+
+#if TEST_STD_VER >= 11
+    test<MoveOnly, random_access_iterator<MoveOnly*>>();
+    test<MoveOnly, MoveOnly*>();
+#endif
+
+#if TEST_STD_VER >= 20
+    static_assert(test<int, random_access_iterator<int*>>());
+    static_assert(test<int, int*>());
+    static_assert(test<MoveOnly, random_access_iterator<MoveOnly*>>());
+    static_assert(test<MoveOnly, MoveOnly*>());
+#endif
 
     return 0;
 }

libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/sort_heap_comp.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
 //
 //===----------------------------------------------------------------------===//
 
 // <algorithm>
 
-// template<RandomAccessIterator Iter, StrictWeakOrder<auto, Iter::value_type> Compare>
-//   requires ShuffleIterator<Iter> && CopyConstructible<Compare>
-//   void
+// template<RandomAccessIterator Iter>
+//   requires ShuffleIterator<Iter> && LessThanComparable<Iter::value_type>
+//   constexpr void  // constexpr in C++20
 //   sort_heap(Iter first, Iter last, Compare comp);
 
 #include <algorithm>
-#include <functional>
-#include <random>
 #include <cassert>
-#include <memory>
 
 #include "test_macros.h"
 #include "test_iterators.h"
 
-struct indirect_less
-{
-    template <class P>
-    bool operator()(const P& x, const P& y)
-        {return *x < *y;}
-};
-
-std::mt19937 randomness;
+#include "test_macros.h"
+#include "test_iterators.h"
+#include "MoveOnly.h"
 
-void test(int N)
+template<class T, class Iter>
+TEST_CONSTEXPR_CXX20 bool test()
 {
-    int* ia = new int [N];
-    for (int i = 0; i < N; ++i)
-        ia[i] = i;
-    std::shuffle(ia, ia+N, randomness);
-    std::make_heap(ia, ia+N, std::greater<int>());
-    std::sort_heap(ia, ia+N, std::greater<int>());
-    assert(std::is_sorted(ia, ia+N, std::greater<int>()));
-
-    typedef random_access_iterator<int *> RI;
-    std::shuffle(RI(ia), RI(ia+N), randomness);
-    std::make_heap(RI(ia), RI(ia+N), std::greater<int>());
-    std::sort_heap(RI(ia), RI(ia+N), std::greater<int>());
-    assert(std::is_sorted(RI(ia), RI(ia+N), std::greater<int>()));
-    delete [] ia;
+    int orig[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    T work[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    for (int n = 0; n < 15; ++n) {
+        std::make_heap(work, work+n, std::greater<T>());
+        std::sort_heap(Iter(work), Iter(work+n), std::greater<T>());
+        assert(std::is_sorted(work, work+n, std::greater<T>()));
+        assert(std::is_permutation(work, work+n, orig));
+        std::copy(orig, orig+n, work);
+    }
+    return true;
 }
 
 int main(int, char**)
 {
-    test(0);
-    test(1);
-    test(2);
-    test(3);
-    test(10);
-    test(1000);
+    test<int, random_access_iterator<int*> >();
+    test<int, int*>();
 
 #if TEST_STD_VER >= 11
-    {
-    const int N = 1000;
-    std::unique_ptr<int>* ia = new std::unique_ptr<int> [N];
-    for (int i = 0; i < N; ++i)
-        ia[i].reset(new int(i));
-    std::shuffle(ia, ia+N, randomness);
-    std::make_heap(ia, ia+N, indirect_less());
-    std::sort_heap(ia, ia+N, indirect_less());
-    assert(std::is_sorted(ia, ia+N, indirect_less()));
-    delete [] ia;
-    }
+    test<MoveOnly, random_access_iterator<MoveOnly*>>();
+    test<MoveOnly, MoveOnly*>();
+#endif
+
+#if TEST_STD_VER >= 20
+    static_assert(test<int, random_access_iterator<int*>>());
+    static_assert(test<int, int*>());
+    static_assert(test<MoveOnly, random_access_iterator<MoveOnly*>>());
+    static_assert(test<MoveOnly, MoveOnly*>());
 #endif
 
     return 0;
 }

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

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // <algorithm>
 
 // template<InputIterator InIter, RandomAccessIterator RAIter>
 //   requires ShuffleIterator<RAIter>
 //         && OutputIterator<RAIter, InIter::reference>
 //         && HasLess<InIter::value_type, RAIter::value_type>
 //         && LessThanComparable<RAIter::value_type>
-//   RAIter
+//   constexpr RAIter  // constexpr in C++20
 //   partial_sort_copy(InIter first, InIter last, RAIter result_first, RAIter result_last);
 
 #include <algorithm>
-#include <random>
 #include <cassert>
 
 #include "test_macros.h"
 #include "test_iterators.h"
+#include "MoveOnly.h"
 
-std::mt19937 randomness;
-
-template <class Iter>
-void
-test_larger_sorts(int N, int M)
-{
-    int* input = new int[N];
-    int* output = new int[M];
-    for (int i = 0; i < N; ++i)
-        input[i] = i;
-    std::shuffle(input, input+N, randomness);
-    int* r = std::partial_sort_copy(Iter(input), Iter(input+N), output, output+M);
-    int* e = output + std::min(N, M);
-    assert(r == e);
-    int i = 0;
-    for (int* x = output; x < e; ++x, ++i)
-        assert(*x == i);
-    delete [] output;
-    delete [] input;
-}
-
-template <class Iter>
-void
-test_larger_sorts(int N)
+template<class T, class Iter, class OutIter>
+TEST_CONSTEXPR_CXX20 bool test()
 {
-    test_larger_sorts<Iter>(N, 0);
-    test_larger_sorts<Iter>(N, 1);
-    test_larger_sorts<Iter>(N, 2);
-    test_larger_sorts<Iter>(N, 3);
-    test_larger_sorts<Iter>(N, N/2-1);
-    test_larger_sorts<Iter>(N, N/2);
-    test_larger_sorts<Iter>(N, N/2+1);
-    test_larger_sorts<Iter>(N, N-2);
-    test_larger_sorts<Iter>(N, N-1);
-    test_larger_sorts<Iter>(N, N);
-    test_larger_sorts<Iter>(N, N+1000);
-}
-
-template <class Iter>
-void
-test()
-{
-    test_larger_sorts<Iter>(0, 100);
-    test_larger_sorts<Iter>(10);
-    test_larger_sorts<Iter>(256);
-    test_larger_sorts<Iter>(257);
-    test_larger_sorts<Iter>(499);
-    test_larger_sorts<Iter>(500);
-    test_larger_sorts<Iter>(997);
-    test_larger_sorts<Iter>(1000);
-    test_larger_sorts<Iter>(1009);
+    int orig[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    T work[15] = {};
+    for (int n = 0; n < 15; ++n) {
+        for (int m = 0; m < 15; ++m) {
+            OutIter it = std::partial_sort_copy(Iter(orig), Iter(orig+n), OutIter(work), OutIter(work+m));
+            if (n <= m) {
+                assert(it == OutIter(work+n));
+                assert(std::is_permutation(OutIter(work), it, orig));
+            } else {
+                assert(it == OutIter(work+m));
+            }
+            assert(std::is_sorted(OutIter(work), it));
+            if (it != OutIter(work)) {
+                // At most m-1 elements in the input are less than the biggest element in the result.
+                int count = 0;
+                for (int i = m; i < n; ++i) {
+                    count += (T(orig[i]) < *(it - 1));
+                }
+                assert(count < m);
+            }
+        }
+    }
+    return true;
 }
 
 int main(int, char**)
 {
-    int i = 0;
-    std::partial_sort_copy(&i, &i, &i, &i+5);
-    assert(i == 0);
-    test<input_iterator<const int*> >();
-    test<forward_iterator<const int*> >();
-    test<bidirectional_iterator<const int*> >();
-    test<random_access_iterator<const int*> >();
-    test<const int*>();
+    int i = 42;
+    int j = 75;
+    std::partial_sort_copy(&i, &i, &i, &j);
+    assert(i == 42);
+    assert(j == 75);
+
+    test<int, random_access_iterator<int*>, random_access_iterator<int*> >();
+    test<int, random_access_iterator<int*>, int*>();
+    test<int, int*, random_access_iterator<int*> >();
+    test<int, int*, int*>();
+
+#if TEST_STD_VER >= 11
+    test<MoveOnly, random_access_iterator<int*>, random_access_iterator<MoveOnly*>>();
+    test<MoveOnly, random_access_iterator<int*>, MoveOnly*>();
+    test<MoveOnly, int*, random_access_iterator<MoveOnly*>>();
+    test<MoveOnly, int*, MoveOnly*>();
+#endif
+
+#if TEST_STD_VER >= 20
+    static_assert(test<int, random_access_iterator<int*>, random_access_iterator<int*>>());
+    static_assert(test<int, int*, random_access_iterator<int*>>());
+    static_assert(test<int, random_access_iterator<int*>, int*>());
+    static_assert(test<int, int*, int*>());
+    static_assert(test<MoveOnly, random_access_iterator<int*>, random_access_iterator<MoveOnly*>>());
+    static_assert(test<MoveOnly, random_access_iterator<int*>, MoveOnly*>());
+    static_assert(test<MoveOnly, int*, random_access_iterator<MoveOnly*>>());
+    static_assert(test<MoveOnly, int*, MoveOnly*>());
+#endif
 
     return 0;
 }

libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort.copy/partial_sort_copy_comp.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
 //
 //===----------------------------------------------------------------------===//
 
 // <algorithm>
 
 // template<InputIterator InIter, RandomAccessIterator RAIter, class Compare>
 //   requires ShuffleIterator<RAIter>
 //         && OutputIterator<RAIter, InIter::reference>
 //         && Predicate<Compare, InIter::value_type, RAIter::value_type>
 //         && StrictWeakOrder<Compare, RAIter::value_type>}
 //         && CopyConstructible<Compare>
-//   RAIter
+//   constexpr RAIter  // constexpr in C++20
 //   partial_sort_copy(InIter first, InIter last,
 //                     RAIter result_first, RAIter result_last, Compare comp);
 
 #include <algorithm>
-#include <functional>
-#include <random>
 #include <cassert>
+#include <functional>
 
 #include "test_macros.h"
 #include "test_iterators.h"
+#include "MoveOnly.h"
 
-std::mt19937 randomness;
-
-template <class Iter>
-void
-test_larger_sorts(int N, int M)
-{
-    int* input = new int[N];
-    int* output = new int[M];
-    for (int i = 0; i < N; ++i)
-        input[i] = i;
-    std::shuffle(input, input+N, randomness);
-    int* r = std::partial_sort_copy(Iter(input), Iter(input+N), output, output+M,
-                                    std::greater<int>());
-    int* e = output + std::min(N, M);
-    assert(r == e);
-    int i = 0;
-    for (int* x = output; x < e; ++x, ++i)
-        assert(*x == N-i-1);
-    delete [] output;
-    delete [] input;
-}
-
-template <class Iter>
-void
-test_larger_sorts(int N)
-{
-    test_larger_sorts<Iter>(N, 0);
-    test_larger_sorts<Iter>(N, 1);
-    test_larger_sorts<Iter>(N, 2);
-    test_larger_sorts<Iter>(N, 3);
-    test_larger_sorts<Iter>(N, N/2-1);
-    test_larger_sorts<Iter>(N, N/2);
-    test_larger_sorts<Iter>(N, N/2+1);
-    test_larger_sorts<Iter>(N, N-2);
-    test_larger_sorts<Iter>(N, N-1);
-    test_larger_sorts<Iter>(N, N);
-    test_larger_sorts<Iter>(N, N+1000);
-}
-
-template <class Iter>
-void
-test()
+template<class T, class Iter, class OutIter>
+TEST_CONSTEXPR_CXX20 bool test()
 {
-    test_larger_sorts<Iter>(0, 100);
-    test_larger_sorts<Iter>(10);
-    test_larger_sorts<Iter>(256);
-    test_larger_sorts<Iter>(257);
-    test_larger_sorts<Iter>(499);
-    test_larger_sorts<Iter>(500);
-    test_larger_sorts<Iter>(997);
-    test_larger_sorts<Iter>(1000);
-    test_larger_sorts<Iter>(1009);
+    int orig[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    T work[15] = {};
+    for (int n = 0; n < 15; ++n) {
+        for (int m = 0; m < 15; ++m) {
+            OutIter it = std::partial_sort_copy(Iter(orig), Iter(orig+n), OutIter(work), OutIter(work+m), std::greater<T>());
+            if (n <= m) {
+                assert(it == OutIter(work+n));
+                assert(std::is_permutation(OutIter(work), it, orig));
+            } else {
+                assert(it == OutIter(work+m));
+            }
+            assert(std::is_sorted(OutIter(work), it, std::greater<T>()));
+            if (it != OutIter(work)) {
+                // At most m-1 elements in the input are greater than the biggest element in the result.
+                int count = 0;
+                for (int i = m; i < n; ++i) {
+                    count += (T(orig[i]) > *(it - 1));
+                }
+                assert(count < m);
+            }
+        }
+    }
+    return true;
 }
 
 int main(int, char**)
 {
-    int i = 0;
-    std::partial_sort_copy(&i, &i, &i, &i+5);
-    assert(i == 0);
-    test<input_iterator<const int*> >();
-    test<forward_iterator<const int*> >();
-    test<bidirectional_iterator<const int*> >();
-    test<random_access_iterator<const int*> >();
-    test<const int*>();
+    int i = 42;
+    int j = 75;
+    std::partial_sort_copy(&i, &i, &i, &j, std::greater<int>());
+    assert(i == 42);
+    assert(j == 75);
+
+    test<int, random_access_iterator<int*>, random_access_iterator<int*> >();
+    test<int, random_access_iterator<int*>, int*>();
+    test<int, int*, random_access_iterator<int*> >();
+    test<int, int*, int*>();
+
+#if TEST_STD_VER >= 11
+    test<MoveOnly, random_access_iterator<int*>, random_access_iterator<MoveOnly*>>();
+    test<MoveOnly, random_access_iterator<int*>, MoveOnly*>();
+    test<MoveOnly, int*, random_access_iterator<MoveOnly*>>();
+    test<MoveOnly, int*, MoveOnly*>();
+#endif
+
+#if TEST_STD_VER >= 20
+    static_assert(test<int, random_access_iterator<int*>, random_access_iterator<int*>>());
+    static_assert(test<int, int*, random_access_iterator<int*>>());
+    static_assert(test<int, random_access_iterator<int*>, int*>());
+    static_assert(test<int, int*, int*>());
+    static_assert(test<MoveOnly, random_access_iterator<int*>, random_access_iterator<MoveOnly*>>());
+    static_assert(test<MoveOnly, random_access_iterator<int*>, MoveOnly*>());
+    static_assert(test<MoveOnly, int*, random_access_iterator<MoveOnly*>>());
+    static_assert(test<MoveOnly, int*, MoveOnly*>());
+#endif
 
     return 0;
 }

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

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 // <algorithm>
 
 // template<RandomAccessIterator Iter>
-//   requires ShuffleIterator<Iter>
-//         && LessThanComparable<Iter::value_type>
-//   void
+//   requires ShuffleIterator<Iter> && LessThanComparable<Iter::value_type>
+//   constexpr void  // constexpr in C++20
 //   partial_sort(Iter first, Iter middle, Iter last);
 
 #include <algorithm>
-#include <random>
 #include <cassert>
 
 #include "test_macros.h"
+#include "test_iterators.h"
+#include "MoveOnly.h"
 
-std::mt19937 randomness;
-
-void
-test_larger_sorts(int N, int M)
-{
-    assert(N != 0);
-    assert(N >= M);
-    int* array = new int[N];
-    for (int i = 0; i < N; ++i)
-        array[i] = i;
-    std::shuffle(array, array+N, randomness);
-    std::partial_sort(array, array+M, array+N);
-    for (int i = 0; i < M; ++i)
-    {
-        assert(i < N); // quiet analysis warnings
-        assert(array[i] == i);
+template<class T, class Iter>
+TEST_CONSTEXPR_CXX20 bool test()
+    int orig[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    T work[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    for (int n = 0; n < 15; ++n) {
+        for (int m = 0; m <= n; ++m) {
+            std::partial_sort(Iter(work), Iter(work+m), Iter(work+n));
+            assert(std::is_sorted(work, work+m));
+            assert(std::is_permutation(work, work+n, orig));
+            // No element in the unsorted portion is less than any element in the sorted portion.
+            for (int i = m; i < n; ++i) {
+                assert(m == 0 || !(work[i] < work[m-1]));
             }
-    delete [] array;
+            std::copy(orig, orig+15, work);
         }
-
-void
-test_larger_sorts(int N)
-{
-    test_larger_sorts(N, 0);
-    test_larger_sorts(N, 1);
-    test_larger_sorts(N, 2);
-    test_larger_sorts(N, 3);
-    test_larger_sorts(N, N/2-1);
-    test_larger_sorts(N, N/2);
-    test_larger_sorts(N, N/2+1);
-    test_larger_sorts(N, N-2);
-    test_larger_sorts(N, N-1);
-    test_larger_sorts(N, N);
+    }
+    return true;
 }
 
 int main(int, char**)
 {
-    int i = 0;
+    int i = 42;
     std::partial_sort(&i, &i, &i);
-    assert(i == 0);
-    test_larger_sorts(10);
-    test_larger_sorts(256);
-    test_larger_sorts(257);
-    test_larger_sorts(499);
-    test_larger_sorts(500);
-    test_larger_sorts(997);
-    test_larger_sorts(1000);
-    test_larger_sorts(1009);
+    assert(i == 42);
+
+    test<int, random_access_iterator<int*> >();
+    test<int, int*>();
+
+#if TEST_STD_VER >= 11
+    test<MoveOnly, random_access_iterator<MoveOnly*>>();
+    test<MoveOnly, MoveOnly*>();
+#endif
+
+#if TEST_STD_VER >= 20
+    static_assert(test<int, random_access_iterator<int*>>());
+    static_assert(test<int, int*>());
+    static_assert(test<MoveOnly, random_access_iterator<MoveOnly*>>());
+    static_assert(test<MoveOnly, MoveOnly*>());
+#endif
 
     return 0;
 }

libcxx/test/std/algorithms/alg.sorting/alg.sort/partial.sort/partial_sort_comp.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
 //
 //===----------------------------------------------------------------------===//
 
 // <algorithm>
 
 // template<RandomAccessIterator Iter, StrictWeakOrder<auto, Iter::value_type> Compare>
 //   requires ShuffleIterator<Iter>
 //         && CopyConstructible<Compare>
-//   void
+//   constexpr void  // constexpr in C++20
 //   partial_sort(Iter first, Iter middle, Iter last, Compare comp);
 
 #include <algorithm>
-#include <vector>
-#include <functional>
-#include <random>
 #include <cassert>
-#include <cstddef>
-#include <memory>
+#include <functional>
 
 #include "test_macros.h"
+#include "test_iterators.h"
+#include "MoveOnly.h"
 
-struct indirect_less
-{
-    template <class P>
-    bool operator()(const P& x, const P& y)
-        {return *x < *y;}
-};
-
-std::mt19937 randomness;
-
-void
-test_larger_sorts(int N, int M)
-{
-    assert(N != 0);
-    assert(N >= M);
-    int* array = new int[N];
-    for (int i = 0; i < N; ++i)
-        array[i] = i;
-    std::shuffle(array, array+N, randomness);
-    std::partial_sort(array, array+M, array+N, std::greater<int>());
-    for (int i = 0; i < M; ++i)
-    {
-        assert(i < N); // quiet analysis warnings
-        assert(array[i] == N-i-1);
+template<class T, class Iter>
+TEST_CONSTEXPR_CXX20 bool test()
+    int orig[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    T work[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
+    for (int n = 0; n < 15; ++n) {
+        for (int m = 0; m <= n; ++m) {
+            std::partial_sort(Iter(work), Iter(work+m), Iter(work+n), std::greater<T>());
+            assert(std::is_sorted(work, work+m, std::greater<T>()));
+            assert(std::is_permutation(work, work+n, orig));
+            // No element in the unsorted portion is greater than any element in the sorted portion.
+            for (int i = m; i < n; ++i) {
+                assert(m == 0 || !(work[i] > work[m-1]));
             }
-    delete [] array;
+            std::copy(orig, orig+15, work);
         }
-
-void
-test_larger_sorts(int N)
-{
-    test_larger_sorts(N, 0);
-    test_larger_sorts(N, 1);
-    test_larger_sorts(N, 2);
-    test_larger_sorts(N, 3);
-    test_larger_sorts(N, N/2-1);
-    test_larger_sorts(N, N/2);
-    test_larger_sorts(N, N/2+1);
-    test_larger_sorts(N, N-2);
-    test_larger_sorts(N, N-1);
-    test_larger_sorts(N, N);
+    }
+    return true;
 }
 
 int main(int, char**)
 {
-    {
-    int i = 0;
-    std::partial_sort(&i, &i, &i);
-    assert(i == 0);
-    test_larger_sorts(10);
-    test_larger_sorts(256);
-    test_larger_sorts(257);
-    test_larger_sorts(499);
-    test_larger_sorts(500);
-    test_larger_sorts(997);
-    test_larger_sorts(1000);
-    test_larger_sorts(1009);
-    }
+    int i = 42;
+    std::partial_sort(&i, &i, &i, std::greater<int>());
+    assert(i == 42);
+
+    test<int, random_access_iterator<int*> >();
+    test<int, int*>();
 
 #if TEST_STD_VER >= 11
-    {
-    std::vector<std::unique_ptr<int> > v(1000);
-    for (int i = 0; static_cast<std::size_t>(i) < v.size(); ++i)
-        v[i].reset(new int(i));
-    std::partial_sort(v.begin(), v.begin() + v.size()/2, v.end(), indirect_less());
-    for (int i = 0; static_cast<std::size_t>(i) < v.size()/2; ++i)
-        assert(*v[i] == i);
-    }
+    test<MoveOnly, random_access_iterator<MoveOnly*>>();
+    test<MoveOnly, MoveOnly*>();
+#endif
+
+#if TEST_STD_VER >= 20
+    static_assert(test<int, random_access_iterator<int*>>());
+    static_assert(test<int, int*>());
+    static_assert(test<MoveOnly, random_access_iterator<MoveOnly*>>());
+    static_assert(test<MoveOnly, MoveOnly*>());
 #endif
 
     return 0;
 }

libcxx/test/support/MoveOnly.h

TEST_CONSTEXPR_CXX14 MoveOnly(MoveOnly&& x)
         : data_(x.data_) {x.data_ = 0;}
     TEST_CONSTEXPR_CXX14 MoveOnly& operator=(MoveOnly&& x)
         {data_ = x.data_; x.data_ = 0; return *this;}
 
     constexpr int get() const {return data_;}
 
     constexpr bool operator==(const MoveOnly& x) const {return data_ == x.data_;}
     constexpr bool operator< (const MoveOnly& x) const {return data_ <  x.data_;}
+    constexpr bool operator> (const MoveOnly& x) const {return data_ >  x.data_;}
     TEST_CONSTEXPR_CXX14 MoveOnly operator+(const MoveOnly& x) const
         { return MoveOnly{data_ + x.data_}; }
     TEST_CONSTEXPR_CXX14 MoveOnly operator*(const MoveOnly& x) const
         { return MoveOnly{data_ * x.data_}; }
 };
 
 namespace std {