1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9// <algorithm>
10
11// template<RandomAccessIterator Iter, StrictWeakOrder<auto, Iter::value_type> Compare>
12// requires ShuffleIterator<Iter> && CopyConstructible<Compare>
13// constexpr void // constexpr in C++20
14// nth_element(Iter first, Iter nth, Iter last, Compare comp);
15
16#include <algorithm>
17#include <cassert>
18#include <functional>
19
20#include "test_macros.h"
21#include "test_iterators.h"
22#include "MoveOnly.h"
23
24template<class T, class Iter>
25TEST_CONSTEXPR_CXX20 bool test()
26{
27 int orig[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
28 T work[15] = {3,1,4,1,5, 9,2,6,5,3, 5,8,9,7,9};
29 for (int n = 0; n < 15; ++n) {
30 for (int m = 0; m < n; ++m) {
31 std::nth_element(Iter(work), Iter(work+m), Iter(work+n), std::greater<T>());
32 assert(std::is_permutation(work, work+n, orig));
33 // No element to m's left is less than m.
34 for (int i = 0; i < m; ++i) {
35 assert(!(work[i] < work[m]));
36 }
37 // No element to m's right is greater than m.
38 for (int i = m; i < n; ++i) {
39 assert(!(work[i] > work[m]));
40 }
41 std::copy(orig, orig+15, work);
42 }
43 }
44
45 {
46 T input[] = {3,1,4,1,5,9,2};
47 std::nth_element(Iter(input), Iter(input+4), Iter(input+7), std::greater<T>());
48 assert(input[4] == 2);
49 assert(input[5] + input[6] == 1 + 1);
50 }
51
52 {
53 T input[] = {0, 1, 2, 3, 4, 5, 7, 6};
54 std::nth_element(Iter(input), Iter(input + 6), Iter(input + 8), std::greater<T>());
55 assert(input[6] == 1);
56 assert(input[7] == 0);
57 }
58
59 {
60 T input[] = {1, 0, 2, 3, 4, 5, 6, 7};
61 std::nth_element(Iter(input), Iter(input + 1), Iter(input + 8), std::greater<T>());
62 assert(input[0] == 7);
63 assert(input[1] == 6);
64 }
65
66 return true;
67}
68
69int main(int, char**)
70{
71 test<int, random_access_iterator<int*> >();
72 test<int, int*>();
73
74#if TEST_STD_VER >= 11
75 test<MoveOnly, random_access_iterator<MoveOnly*>>();
76 test<MoveOnly, MoveOnly*>();
77#endif
78
79#if TEST_STD_VER >= 20
80 static_assert(test<int, random_access_iterator<int*>>());
81 static_assert(test<int, int*>());
82 static_assert(test<MoveOnly, random_access_iterator<MoveOnly*>>());
83 static_assert(test<MoveOnly, MoveOnly*>());
84#endif
85
86 return 0;
87}
88

source code of libcxx/test/std/algorithms/alg.sorting/alg.nth.element/nth_element_comp.pass.cpp