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 // pop_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>
operator ()indirect_less26 bool operator()(const P& x, const P& y)
27 {return *x < *y;}
28 };
29
30 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
31
test(unsigned N)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 for (int i = N; i > 0; --i)
40 {
41 std::pop_heap(ia, ia+i, std::greater<int>());
42 assert(std::is_heap(ia, ia+i-1, std::greater<int>()));
43 }
44 std::pop_heap(ia, ia, std::greater<int>());
45 delete [] ia;
46 }
47
main()48 int main()
49 {
50 test(1000);
51
52 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
53 {
54 const int N = 1000;
55 std::unique_ptr<int>* ia = new std::unique_ptr<int> [N];
56 for (int i = 0; i < N; ++i)
57 ia[i].reset(new int(i));
58 std::random_shuffle(ia, ia+N);
59 std::make_heap(ia, ia+N, indirect_less());
60 for (int i = N; i > 0; --i)
61 {
62 std::pop_heap(ia, ia+i, indirect_less());
63 assert(std::is_heap(ia, ia+i-1, indirect_less()));
64 }
65 delete [] ia;
66 }
67 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
68 }
69