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// Test std::sort stability randomization
12
13// UNSUPPORTED: c++03
14// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_DEBUG_RANDOMIZE_UNSPECIFIED_STABILITY
15
16#include <algorithm>
17#include <array>
18#include <cassert>
19#include <functional>
20#include <iterator>
21#include <vector>
22
23#include "test_macros.h"
24
25struct EqualType {
26 int value = 0;
27 constexpr bool operator<(const EqualType&) const { return false; }
28};
29
30std::vector<EqualType> deterministic() {
31 static constexpr int kSize = 100;
32 std::vector<EqualType> v;
33 v.resize(new_size: kSize);
34 for (int i = 0; i < kSize; ++i) {
35 v[i].value = kSize / 2 - i * (i % 2 ? -1 : 1);
36 }
37 std::less<EqualType> comp;
38 std::__sort_dispatch<std::_ClassicAlgPolicy>(v.begin(), v.end(), comp);
39 return v;
40}
41
42void test_randomization() {
43 static constexpr int kSize = 100;
44 std::vector<EqualType> v;
45 v.resize(new_size: kSize);
46 for (int i = 0; i < kSize; ++i) {
47 v[i].value = kSize / 2 - i * (i % 2 ? -1 : 1);
48 }
49 auto deterministic_v = deterministic();
50 std::sort(first: v.begin(), last: v.end());
51 bool all_equal = true;
52 for (int i = 0; i < kSize; ++i) {
53 if (v[i].value != deterministic_v[i].value) {
54 all_equal = false;
55 }
56 }
57 assert(!all_equal);
58}
59
60void test_same() {
61 static constexpr int kSize = 100;
62 std::vector<EqualType> v;
63 v.resize(new_size: kSize);
64 for (int i = 0; i < kSize; ++i) {
65 v[i].value = kSize / 2 - i * (i % 2 ? -1 : 1);
66 }
67 auto snapshot_v = v;
68 auto snapshot_custom_v = v;
69 std::sort(first: v.begin(), last: v.end());
70 std::sort(first: snapshot_v.begin(), last: snapshot_v.end());
71 std::sort(first: snapshot_custom_v.begin(), last: snapshot_custom_v.end(),
72 comp: [](const EqualType&, const EqualType&) { return false; });
73 bool all_equal = true;
74 for (int i = 0; i < kSize; ++i) {
75 if (v[i].value != snapshot_v[i].value || v[i].value != snapshot_custom_v[i].value) {
76 all_equal = false;
77 }
78 }
79 assert(all_equal);
80}
81
82#if TEST_STD_VER > 17
83constexpr bool test_constexpr() {
84 std::array<EqualType, 10> v;
85 for (int i = 9; i >= 0; --i) {
86 v[9 - i].value = i;
87 }
88 std::sort(v.begin(), v.end());
89 return std::is_sorted(v.begin(), v.end());
90}
91#endif
92
93int main(int, char**) {
94 test_randomization();
95 test_same();
96#if TEST_STD_VER > 17
97 static_assert(test_constexpr(), "");
98#endif
99 return 0;
100}
101

source code of libcxx/test/libcxx/algorithms/sort_stability.pass.cpp