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 23struct 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 32void 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 48int 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