Znalostní bázeCentrum zkoušek
CSČeština
Vybrat jazyk13

CKTIS / C++

std::is_heap — kontrola vlastnosti haldy

std::is_heap kontroluje, zda rozsah splňuje vlastnost haldy, aniž by měnila jeho prvky. Ve výchozím nastavení rozpozná max-hromadu; vlastní komparátor umožňuje ověřit jiné uspořádání, například min-hromadu.

Verze: C++23; repository compiler flag, production runtime not attested

Syntaxe

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

std::is_heap deklarovaná v <algorithm> vrací bool po kontrole rozsahu [first, last). Vyžaduje platný rozsah a iterátory s náhodným přístupem, například iterátory std::array nebo std::vector. Haldu nevytváří ani neopravuje a prvky nepřeskupuje. Prázdný rozsah nebo rozsah s jedním prvkem podmínku splňuje.

Pro každý index potomka i > 0 je index rodiče (i - 1) / 2, při celočíselném dělení. Podmínka haldy vyžaduje, aby comp(parent, child) bylo false. Výchozí porovnání std::less{} představuje pro čísla max-hromadu: rodič není menší než potomek. std::greater<int>{} kontroluje min-hromadu. Komparátor musí definovat striktní slabé uspořádání; použijte stejné uspořádání jako při vytváření haldy.

Halda nemusí být seřazená: mezi sourozenci není vyžadováno žádné vzájemné pořadí. Kontrola má lineální složitost vzhledem k počtu prvků. Výsledek odpovídá testu std::is_heap_until(first, last, comp) == last; tato další funkce pomáhá najít první porušení. K vytvoření haldy použijte std::make_heap.

Příklad nejprve rozpozná max-hromadu, poté ji odmítne jako min-hromadu a nakonec po přiřazení values[3] = 10 odhalí porušení vůči rodiči s hodnotou 5. Zobrazená přetížení bez zásady provádění jsou constexpr; existují také přetížení se zásadou provádění. Tento záznam se týká C++23. Zdroj je průběžně se vyvíjející návrh standardu a příznak kompilátoru v repozitáři nepotvrzuje produkční prostředí.

Pří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ýsledek

true
false
false

Zobrazený kód a uvedený výsledek byly ověřeny v izolovaném prostředí metodou zaznamenanou v dokladu o ověření této přesné verze.

Zdroje