Namespaces
Variants

std:: is_heap

From cppreference.net
C++
Algorithm library
Constrained algorithms and algorithms on ranges (C++20)
Constrained algorithms, e.g. ranges::copy , ranges::sort , ...
Execution policies (C++17)
Non-modifying sequence operations
Batch operations
(C++17)
Search operations
Modifying sequence operations
Copy operations
(C++11)
(C++11)
(C++11)
Swap operations
Transformation operations
Generation operations
Removing operations
Order-changing operations
(until C++17) (C++11)
(C++20) (C++20)
Sampling operations
(C++17)

Sorting and related operations
Partitioning operations
Sorting operations
Binary search operations
(on partitioned ranges)
Set operations (on sorted ranges)
Merge operations (on sorted ranges)
Heap operations
is_heap
(C++11)
(C++11)
Minimum/maximum operations
Lexicographical comparison operations
(C++20)
Permutation operations
C library
Numeric operations
Operations on uninitialized memory
Definiert im Header <algorithm>
template < class RandomIt >
bool is_heap ( RandomIt first, RandomIt last ) ;
(1) (seit C++11)
(constexpr seit C++20)
template < class ExecutionPolicy, class RandomIt >

bool is_heap ( ExecutionPolicy && policy,

RandomIt first, RandomIt last ) ;
(2) (seit C++17)
template < class RandomIt, class Compare >
bool is_heap ( RandomIt first, RandomIt last, Compare comp ) ;
(3) (seit C++11)
(constexpr seit C++20)
template < class ExecutionPolicy, class RandomIt, class Compare >

bool is_heap ( ExecutionPolicy && policy,

RandomIt first, RandomIt last, Compare comp ) ;
(4) (seit C++17)

Überprüft, ob [ first , last ) ein Heap ist.

1) Die zu prüfende Heap-Eigenschaft bezieht sich auf operator < (bis C++20) std:: less { } (seit C++20) .
3) Die zu prüfende Heap-Eigenschaft bezieht sich auf comp .
2,4) Gleich wie (1,3) , aber ausgeführt gemäß policy .
Diese Überladungen nehmen nur dann an der Überladungsauflösung teil, wenn alle folgenden Bedingungen erfüllt sind:

std:: is_execution_policy_v < std:: decay_t < ExecutionPolicy >> ist true .

(bis C++20)

std:: is_execution_policy_v < std:: remove_cvref_t < ExecutionPolicy >> ist true .

(seit C++20)

Inhaltsverzeichnis

Parameter

first, last - das Paar von Iteratoren, das den Bereich der zu prüfenden Elemente definiert
policy - die zu verwendende Ausführungsrichtlinie
comp - Vergleichsfunktionsobjekt (d.h. ein Objekt, das die Anforderungen von Compare erfüllt), das true zurückgibt, wenn das erste Argument kleiner als das zweite ist.

Die Signatur der Vergleichsfunktion sollte äquivalent zu Folgendem sein:

bool cmp ( const Type1 & a, const Type2 & b ) ;

Obwohl die Signatur keine const & benötigt, darf die Funktion die übergebenen Objekte nicht modifizieren und muss alle Werte der Typen (möglicherweise const) Type1 und Type2 unabhängig von der Wertkategorie akzeptieren können (daher ist Type1 & nicht erlaubt , ebenso wenig wie Type1 , es sei denn, für Type1 ist eine Verschiebung äquivalent zu einer Kopie (seit C++11) ).
Die Typen Type1 und Type2 müssen so beschaffen sein, dass ein Objekt vom Typ RandomIt dereferenziert und dann implizit in beide konvertiert werden kann.

Typanforderungen
-
RandomIt muss die Anforderungen von LegacyRandomAccessIterator erfüllen.
-
Compare muss die Anforderungen von Compare erfüllen.

Rückgabewert

true wenn der Bereich ein Heap bezüglich des entsprechenden Vergleichsoperators ist, false andernfalls.

Komplexität

Gegeben N als std:: distance ( first, last ) :

1,2) O(N) Vergleiche mit operator < (bis C++20) std:: less { } (seit C++20) .
3,4) O(N) Anwendungen der Vergleichsfunktion comp .

Ausnahmen

Die Überladungen mit einem Template-Parameter namens ExecutionPolicy melden Fehler wie folgt:

  • Wenn die Ausführung einer als Teil des Algorithmus aufgerufenen Funktion eine Exception wirft und ExecutionPolicy einer der Standard-Policies ist, wird std::terminate aufgerufen. Für jede andere ExecutionPolicy ist das Verhalten implementierungsdefiniert.
  • Wenn der Algorithmus keinen Speicher allozieren kann, wird std::bad_alloc geworfen.

Beispiel

Diesen Code ausführen 
#include <algorithm>
#include <bit>
#include <iostream>
#include <vector>
int main()
{
    std::vector<int> v{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9};
    std::cout << "initially, v:\n";
    for (const auto& i : v)
        std::cout << i << ' ';
    std::cout << '\n';
    if (!std::is_heap(v.begin(), v.end()))
    {
        std::cout << "making heap...\n";
        std::make_heap(v.begin(), v.end());
    }
    std::cout << "after make_heap, v:\n";
    for (auto t{1U}; const auto& i : v)
        std::cout << i << (std::has_single_bit(++t) ? " | " : " ");
    std::cout << '\n';
}

Ausgabe: 

initially, v:
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
making heap...
after make_heap, v:
9 | 6 9 | 5 5 9 7 | 1 1 3 5 8 3 4 2 |

Siehe auch

(C++11)
findet den größten Teilbereich, der einen Max-Heap darstellt
(Funktions-Template)
erstellt einen Max-Heap aus einer Reihe von Elementen
(Funktions-Template)
fügt ein Element zu einem Max-Heap hinzu
(Funktions-Template)
entfernt das größte Element aus einem Max-Heap
(Funktions-Template)
wandelt einen Max-Heap in eine aufsteigend sortierte Elementreihe um
(Funktions-Template)
(C++20)
prüft, ob der gegebene Bereich einen Max-Heap darstellt
(Algorithmus-Funktionsobjekt)