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