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> && CopyConstructible<Compare> 14 // void 15 // sort_heap(Iter first, Iter last, Compare comp); 16 17 #include <algorithm> 18 #include <functional> 19 #include <cassert> 20 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 21 #include <memory> 22 23 struct indirect_less 24 { 25 template <class P> 26 bool operator()(const P& x, const P& y) 27 {return *x < *y;} 28 }; 29 30 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 31 32 void test(unsigned N) 33 { 34 int* ia = new int [N]; 35 for (int i = 0; i < N; ++i) 36 ia[i] = i; 37 std::random_shuffle(ia, ia+N); 38 std::make_heap(ia, ia+N, std::greater<int>()); 39 std::sort_heap(ia, ia+N, std::greater<int>()); 40 assert(std::is_sorted(ia, ia+N, std::greater<int>())); 41 delete [] ia; 42 } 43 44 int main() 45 { 46 test(0); 47 test(1); 48 test(2); 49 test(3); 50 test(10); 51 test(1000); 52 53 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES 54 { 55 const int N = 1000; 56 std::unique_ptr<int>* ia = new std::unique_ptr<int> [N]; 57 for (int i = 0; i < N; ++i) 58 ia[i].reset(new int(i)); 59 std::random_shuffle(ia, ia+N); 60 std::make_heap(ia, ia+N, indirect_less()); 61 std::sort_heap(ia, ia+N, indirect_less()); 62 assert(std::is_sorted(ia, ia+N, indirect_less())); 63 delete [] ia; 64 } 65 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES 66 } 67