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> 28 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 { 36 bool operator()(const std::pair<int, int>& x, const std::pair<int, int>& y) 37 { 38 return x.first < y.first; 39 } 40 }; 41 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 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
