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

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