1 //===----------------------------------------------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is dual licensed under the MIT and the University of Illinois Open
6 // Source Licenses. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9
10 // <algorithm>
11
12 // template<RandomAccessIterator Iter, StrictWeakOrder<auto, Iter::value_type> Compare>
13 // requires ShuffleIterator<Iter>
14 // && CopyConstructible<Compare>
15 // void
16 // stable_sort(Iter first, Iter last, Compare comp);
17
18 #include <algorithm>
19 #include <functional>
20 #include <vector>
21 #include <cassert>
22 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
23 #include <memory>
24
25 struct indirect_less
26 {
27 template <class P>
operator ()indirect_less28 bool operator()(const P& x, const P& y)
29 {return *x < *y;}
30 };
31
32 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
33
34 struct first_only
35 {
operator ()first_only36 bool operator()(const std::pair<int, int>& x, const std::pair<int, int>& y)
37 {
38 return x.first < y.first;
39 }
40 };
41
test()42 void test()
43 {
44 typedef std::pair<int, int> P;
45 const int N = 1000;
46 const int M = 10;
47 std::vector<P> v(N);
48 int x = 0;
49 int ver = 0;
50 for (int i = 0; i < N; ++i)
51 {
52 v[i] = P(x, ver);
53 if (++x == M)
54 {
55 x = 0;
56 ++ver;
57 }
58 }
59 for (int i = 0; i < N - M; i += M)
60 {
61 std::random_shuffle(v.begin() + i, v.begin() + i + M);
62 }
63 std::stable_sort(v.begin(), v.end(), first_only());
64 assert(std::is_sorted(v.begin(), v.end()));
65 }
66
main()67 int main()
68 {
69 test();
70
71 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
72 {
73 std::vector<std::unique_ptr<int> > v(1000);
74 for (int i = 0; i < v.size(); ++i)
75 v[i].reset(new int(i));
76 std::stable_sort(v.begin(), v.end(), indirect_less());
77 assert(std::is_sorted(v.begin(), v.end(), indirect_less()));
78 assert(*v[0] == 0);
79 assert(*v[1] == 1);
80 assert(*v[2] == 2);
81 }
82 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
83 }
84