Baza znanjaIzpitno središče
SLSlovenščina
Izberi jezik13

CKTIS / C++

std::is_heap — preverjanje lastnosti kopice

std::is_heap preveri, ali obseg izpolnjuje lastnost kopice, ne da bi spremenila njegove elemente. Privzeto prepozna največjo kopico; z lastnim primerjalnikom lahko preverite drugačen vrstni red, na primer najmanjšo kopico.

Različica: C++23; repository compiler flag, production runtime not attested

Sintaksa

#include <algorithm>
std::is_heap(first, last)
std::is_heap(first, last, comp)

std::is_heap, deklarirana v <algorithm>, po preverjanju obsega [first, last) vrne bool. Zahteva veljaven obseg in iteratorje z naključnim dostopom, kot so iteratorji std::array ali std::vector. Kopice ne ustvari ali popravi in elementov ne preuredi. Prazen obseg ali obseg z enim elementom izpolnjuje pogoj.

Za vsak indeks otroka i > 0 je indeks starša (i - 1) / 2, pri čemer se uporabi celoštevilsko deljenje. Pogoj kopice zahteva, da je comp(parent, child) enak false. Privzeta primerjava std::less{} za števila ustvari največjo kopico: starš ni manjši od otroka. std::greater<int>{} preveri najmanjšo kopico. Primerjalnik mora določati strogo šibko urejenost; uporabite enako urejenost kot pri izdelavi kopice.

Kopici ni treba biti urejena: med sorojenci ni zahtevano nobeno relativno zaporedje. Preverjanje ima linearno časovno zahtevnost glede na število elementov. Rezultat je enakovreden preverjanju std::is_heap_until(first, last, comp) == last; ta druga funkcija pomaga poiskati prvo kršitev. Za izdelavo kopice uporabite std::make_heap.

Primer najprej prepozna največjo kopico, jo nato zavrne kot najmanjšo kopico in nazadnje po prireditvi values[3] = 10 zazna kršitev glede na starša z vrednostjo 5. Prikazane preobremenitve brez izvajalne politike so constexpr; na voljo so tudi preobremenitve z izvajalno politiko. Ta vnos obravnava C++23. Vir je razvijajoči se osnutek standarda, zastavica prevajalnika v repozitoriju pa ne potrjuje produkcijskega okolja.

Primeri

#include <algorithm>
#include <array>
#include <functional>
#include <iostream>

int main() {
    std::array<int, 5> values{9, 5, 8, 1, 3};
    std::cout << std::boolalpha;
    std::cout << std::is_heap(values.begin(), values.end()) << '\n';
    std::cout << std::is_heap(values.begin(), values.end(),
                              std::greater<int>{}) << '\n';
    values[3] = 10;
    std::cout << std::is_heap(values.begin(), values.end()) << '\n';
}

Rezultat

true
false
false

Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.

Viri