Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / C++

std::is_heap — sprawdzanie własności kopca

std::is_heap sprawdza, czy zakres spełnia własność kopca, bez zmiany jego elementów. Domyślnie rozpoznaje kopiec maksymalny; własny komparator pozwala sprawdzać inny porządek, na przykład kopiec minimalny.

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

Składnia

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

std::is_heap z nagłówka <algorithm> zwraca bool, sprawdzając zakres [first, last). Potrzebuje poprawnego zakresu i iteratorów dostępu swobodnego, takich jak iteratory std::array lub std::vector. Nie buduje ani nie naprawia kopca i nie przestawia elementów. Zakres pusty lub jednoelementowy spełnia warunek.

Dla każdego indeksu dziecka i > 0 rodzic ma indeks (i - 1) / 2, z dzieleniem całkowitym. Warunek kopca wymaga, aby comp(parent, child) było false. Domyślne porównanie std::less{} oznacza dla liczb kopiec maksymalny: rodzic nie jest mniejszy od dziecka. std::greater<int>{} sprawdza kopiec minimalny. Komparator musi definiować ścisły słaby porządek; używaj tego samego porządku co przy budowaniu kopca.

Kopiec nie musi być posortowany: porządek między rodzeństwem nie jest wymagany. Koszt sprawdzania jest liniowy względem liczby elementów. Wynik odpowiada sprawdzeniu, czy std::is_heap_until(first, last, comp) == last; ta druga funkcja pomaga znaleźć pierwsze naruszenie. Do zbudowania kopca służy std::make_heap.

Przykład najpierw rozpoznaje kopiec maksymalny, następnie odrzuca go jako minimalny, a po przypisaniu values[3] = 10 wykrywa naruszenie relacji z rodzicem o wartości 5. Pokazane przeciążenia bez polityki wykonania są constexpr; dostępne są również przeciążenia z polityką wykonania. Wpis dotyczy C++23. Źródło jest rozwijanym szkicem standardu, a flaga kompilatora w repozytorium nie potwierdza środowiska produkcyjnego.

Przykłady

#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';
}

Wynik

true
false
false

Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.

Źródła