CKTIS / C++
std::is_heap — kontrola vlastnosti haldy
std::is_heap kontroluje, či rozsah spĺňa vlastnosť haldy bez toho, aby menila jeho prvky. Predvolene rozpozná max-hromadu; vlastný komparátor umožňuje overiť iné usporiadanie, napríklad min-hromadu.
Verzia: C++23; repository compiler flag, production runtime not attested
Syntax
#include <algorithm>
std::is_heap(first, last)
std::is_heap(first, last, comp)std::is_heap deklarovaná v <algorithm> vracia bool po kontrole rozsahu [first, last). Vyžaduje platný rozsah a iterátory s náhodným prístupom, napríklad iterátory std::array alebo std::vector. Haldu nevytvára ani neopravuje a prvky nepreusporadúva. Prázdny rozsah alebo rozsah s jedným prvkom podmienku spĺňa.
Pre každý index potomka i > 0 je index rodiča (i - 1) / 2, pri celočíselnom delení. Podmienka haldy vyžaduje, aby comp(parent, child) bolo false. Predvolené porovnanie std::less{} predstavuje pre čísla max-hromadu: rodič nie je menší ako potomok. std::greater<int>{} kontroluje min-hromadu. Komparátor musí definovať striktné slabé usporiadanie; použite rovnaké usporiadanie ako pri vytváraní haldy.
Halda nemusí byť usporiadaná: medzi súrodencami sa nevyžaduje žiadne vzájomné poradie. Kontrola má lineárnu zložitosť vzhľadom na počet prvkov. Výsledok zodpovedá testu std::is_heap_until(first, last, comp) == last; táto ďalšia funkcia pomáha nájsť prvé porušenie. Na vytvorenie haldy použite std::make_heap.
Príklad najprv rozpozná max-hromadu, potom ju odmietne ako min-hromadu a napokon po priradení values[3] = 10 zistí porušenie voči rodičovi s hodnotou 5. Zobrazené preťaženia bez politiky vykonávania sú constexpr; existujú aj preťaženia s politikou vykonávania. Tento záznam sa týka C++23. Zdroj je priebežne sa vyvíjajúci návrh štandardu a príznak kompilátora v repozitári nepotvrdzuje produkčné prostredie.
Príklady
#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';
}
Výsledok
true false false
Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.