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

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