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 sort_heap(Iter first, Iter last);
15
16#include <algorithm>
17#include <cassert>
18#include <random>
19#include <vector>
20
21#include "test_macros.h"
22
23struct Stats {
24 int compared = 0;
25 int copied = 0;
26 int moved = 0;
27} stats;
28
29struct MyInt {
30 int value;
31 explicit MyInt(int xval) : value(xval) {}
32 MyInt(const MyInt& other) : value(other.value) { ++stats.copied; }
33 MyInt(MyInt&& other) : value(other.value) { ++stats.moved; }
34 MyInt& operator=(const MyInt& other) {
35 value = other.value;
36 ++stats.copied;
37 return *this;
38 }
39 MyInt& operator=(MyInt&& other) {
40 value = other.value;
41 ++stats.moved;
42 return *this;
43 }
44 friend bool operator<(const MyInt& a, const MyInt& b) {
45 ++stats.compared;
46 return a.value < b.value;
47 }
48};
49
50int main(int, char**) {
51 constexpr int N = (1 << 20);
52 std::vector<MyInt> v;
53 v.reserve(n: N);
54 std::mt19937 g;
55 for (int i = 0; i < N; ++i) {
56 v.emplace_back(args&: i);
57 }
58 for (int logn = 10; logn <= 20; ++logn) {
59 const int n = (1 << logn);
60 auto first = v.begin();
61 auto last = v.begin() + n;
62 const int debug_elements = std::min(a: 100, b: n);
63 // Multiplier 2 because of comp(a,b) comp(b, a) checks.
64 const int debug_comparisons = 2 * (debug_elements + 1) * debug_elements;
65 (void)debug_comparisons;
66 std::shuffle(first: first, last: last, g&: g);
67 std::make_heap(first: first, last: last);
68 // The exact stats of our current implementation are recorded here.
69 stats = {};
70 std::sort_heap(first: first, last: last);
71 LIBCPP_ASSERT(stats.copied == 0);
72 LIBCPP_ASSERT(stats.moved <= 2 * n + n * logn);
73#if defined(_LIBCPP_HARDENING_MODE) && _LIBCPP_HARDENING_MODE != _LIBCPP_HARDENING_MODE_DEBUG
74 LIBCPP_ASSERT(stats.compared <= n * logn);
75#else
76 LIBCPP_ASSERT(stats.compared <= 2 * n * logn + debug_comparisons);
77#endif
78 LIBCPP_ASSERT(std::is_sorted(first: first, last: last));
79 }
80 return 0;
81}
82

source code of libcxx/test/std/algorithms/alg.sorting/alg.heap.operations/sort.heap/complexity.pass.cpp