test/std/algorithms/alg.sorting/alg.sort/stable.sort/stable_sort_comp.pass.cpp

   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 <random>
  22 #include <cassert>
  23 #include <cstddef>
  24 #include <memory>
  25
  26 #include "test_macros.h"
  27
  28 struct indirect_less
  29 {
  30     template <class P>
  31     bool operator()(const P& x, const P& y)
  32         {return *x < *y;}
  33 };
  34
  35 std::mt19937 randomness;
  36
  37 struct first_only
  38 {
  39     bool operator()(const std::pair<int, int>& x, const std::pair<int, int>& y)
  40     {
  41         return x.first < y.first;
  42     }
  43 };
  44
  45 void test()
  46 {
  47     typedef std::pair<int, int> P;
  48     const int N = 1000;
  49     const int M = 10;
  50     std::vector<P> v(N);
  51     int x = 0;
  52     int ver = 0;
  53     for (int i = 0; i < N; ++i)
  54     {
  55         v[i] = P(x, ver);
  56         if (++x == M)
  57         {
  58             x = 0;
  59             ++ver;
  60         }
  61     }
  62     for (int i = 0; i < N - M; i += M)
  63     {
  64         std::shuffle(v.begin() + i, v.begin() + i + M, randomness);
  65     }
  66     std::stable_sort(v.begin(), v.end(), first_only());
  67     assert(std::is_sorted(v.begin(), v.end()));
  68 }
  69
  70 int main()
  71 {
  72     test();
  73
  74 #if TEST_STD_VER >= 11
  75     {
  76     std::vector<std::unique_ptr<int> > v(1000);
  77     for (int i = 0; static_cast<std::size_t>(i) < v.size(); ++i)
  78         v[i].reset(new int(i));
  79     std::stable_sort(v.begin(), v.end(), indirect_less());
  80     assert(std::is_sorted(v.begin(), v.end(), indirect_less()));
  81     assert(*v[0] == 0);
  82     assert(*v[1] == 1);
  83     assert(*v[2] == 2);
  84     }
  85 #endif
  86 }