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// <list>
10
11// void sort();
12
13#include <algorithm>
14#include <list>
15#include <random>
16#include <vector>
17#include <cassert>
18
19#include "test_macros.h"
20#include "min_allocator.h"
21
22std::mt19937 randomness;
23
24struct Payload {
25 int val;
26 int side;
27 Payload(int v) : val(v), side(0) {}
28 Payload(int v, int s) : val(v), side(s) {}
29 bool operator<(const Payload& rhs) const { return val < rhs.val; }
30 // bool operator==(const Payload &rhs) const { return val == rhs.val;}
31};
32
33void test_stable(int N) {
34 typedef Payload T;
35 typedef std::list<T> C;
36 typedef std::vector<T> V;
37 V v;
38 for (int i = 0; i < N; ++i)
39 v.push_back(x: Payload(i / 2));
40 std::shuffle(first: v.begin(), last: v.end(), g&: randomness);
41 for (int i = 0; i < N; ++i)
42 v[i].side = i;
43
44 C c(v.begin(), v.end());
45 c.sort();
46 assert(std::distance(c.begin(), c.end()) == N);
47
48 // Are we sorted?
49 typename C::const_iterator j = c.begin();
50 for (int i = 0; i < N; ++i, ++j)
51 assert(j->val == i / 2);
52
53 // Are we stable?
54 for (C::const_iterator it = c.begin(); it != c.end(); ++it) {
55 C::const_iterator next = std::next(x: it);
56 if (next != c.end() && it->val == next->val)
57 assert(it->side < next->side);
58 }
59}
60
61int main(int, char**) {
62 {
63 int a1[] = {4, 8, 1, 0, 5, 7, 2, 3, 6, 11, 10, 9};
64 int a2[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
65 std::list<int> c1(a1, a1 + sizeof(a1) / sizeof(a1[0]));
66 c1.sort();
67 assert(c1 == std::list<int>(a2, a2 + sizeof(a2) / sizeof(a2[0])));
68 }
69#if TEST_STD_VER >= 11
70 {
71 int a1[] = {4, 8, 1, 0, 5, 7, 2, 3, 6, 11, 10, 9};
72 int a2[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11};
73 std::list<int, min_allocator<int>> c1(a1, a1 + sizeof(a1) / sizeof(a1[0]));
74 c1.sort();
75 assert((c1 == std::list<int, min_allocator<int>>(a2, a2 + sizeof(a2) / sizeof(a2[0]))));
76 }
77#endif
78
79 for (int i = 0; i < 40; ++i)
80 test_stable(N: i);
81
82 return 0;
83}
84

source code of libcxx/test/std/containers/sequences/list/list.ops/sort.pass.cpp