1  //===----------------------------------------------------------------------===//
2  //
3  // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4  // See https://llvm.org/LICENSE.txt for license information.
5  // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6  //
7  //===----------------------------------------------------------------------===//
8  
9  // UNSUPPORTED: c++03, c++11
10  
11  // <algorithm>
12  
13  // template<class Iter>
14  //   void make_heap(Iter first, Iter last);
15  
16  #include <algorithm>
17  #include <cassert>
18  #include <random>
19  
20  #include "test_macros.h"
21  
22  struct Stats {
23    int compared = 0;
24    int copied = 0;
25    int moved = 0;
26  } stats;
27  
28  struct MyInt {
29    int value;
MyIntMyInt30    explicit MyInt(int xval) : value(xval) {}
MyIntMyInt31    MyInt(const MyInt& other) : value(other.value) { ++stats.copied; }
MyIntMyInt32    MyInt(MyInt&& other) : value(other.value) { ++stats.moved; }
operator =MyInt33    MyInt& operator=(const MyInt& other) {
34      value = other.value;
35      ++stats.copied;
36      return *this;
37    }
operator =MyInt38    MyInt& operator=(MyInt&& other) {
39      value = other.value;
40      ++stats.moved;
41      return *this;
42    }
operator <(const MyInt & a,const MyInt & b)43    friend bool operator<(const MyInt& a, const MyInt& b) {
44      ++stats.compared;
45      return a.value < b.value;
46    }
47  };
48  
main(int,char **)49  int main(int, char**)
50  {
51    const int N = 100'000;
52    std::vector<MyInt> v;
53    v.reserve(N);
54    std::mt19937 g;
55    for (int i = 0; i < N; ++i)
56      v.emplace_back(g());
57  
58    // The exact stats of our current implementation are recorded here.
59    // If something changes to make them go a bit up or down, that's probably fine,
60    // and we can just update this test.
61    // But if they suddenly leap upward, that's a bad thing.
62  
63    stats = {};
64    std::make_heap(v.begin(), v.end());
65    assert(stats.copied == 0);
66    assert(stats.moved == 153'486);
67  #if _LIBCPP_HARDENING_MODE != _LIBCPP_HARDENING_MODE_DEBUG
68    assert(stats.compared == 188'285);
69  #endif
70  
71    assert(std::is_heap(v.begin(), v.end()));
72  
73    return 0;
74  }
75