Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / C++

std::pop_heap — przeniesienie korzenia kopca na koniec

std::pop_heap przenosi korzeń niepustego kopca na koniec zakresu i odtwarza kopiec w pozostałym prefiksie. Nie usuwa elementu z kontenera. W std::vector można usunąć wyodrębniony element przez pop_back() tylko wtedy, gdy zakres kopca kończy się na końcu wektora.

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

Składnia

#include <algorithm>

std::pop_heap(first, last);
std::pop_heap(first, last, comp);

std::pop_heap z <algorithm> działa na zakresie [first, last). Przenosi dotychczasowy korzeń pod last - 1 i odtwarza kopiec w [first, last - 1). Domyślnie korzeniem jest największy element. Przeciążenie z comp używa podanej relacji porządkującej; oba przeciążenia zwracają void.

Zakres musi już być niepustym kopcem według tego samego porządku. Iteratory muszą zapewniać dostęp swobodny, a elementy umożliwiać zamianę, konstrukcję przez przeniesienie i przypisanie przez przeniesienie. Komparator musi definiować ścisły słaby porządek. Wywołanie dla pustego zakresu lub zakresu niebędącego kopcem narusza warunki wstępne.

Algorytm nie zmniejsza kontenera. Po wywołaniu odczytaj wyodrębniony element przez *(last - 1). W przypadku std::vector możesz użyć back() do jego odczytania i pop_back() do jego usunięcia tylko wtedy, gdy last jest równe end() wektora. Jeśli zakres kończy się wcześniej, te metody odczytają i usuną inny element. Przed kolejnym wywołaniem wyklucz poprzednio wyodrębniony element z zakresu. Liczba porównań wynosi najwyżej 2 * log2(N), gdzie N = last - first.

Przykład buduje kopiec przez std::make_heap i wypisuje wyłącznie gwarantowane wyniki, nie wewnętrzny układ kopca. Uruchomiono pokazany kod bez zmian, a jego standardowe wyjście dokładnie odpowiadało podanemu wynikowi. Źródłem jest rozwijany szkic standardu, a nie zamrożony tekst C++23.

Przykłady

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{4, 1, 7, 3};
    std::make_heap(values.begin(), values.end());

    std::pop_heap(values.begin(), values.end());
    std::cout << "extracted=" << values.back() << '\n';
    std::cout << "size_before=" << values.size() << '\n';

    values.pop_back();
    std::cout << "size_after=" << values.size() << '\n';
    std::cout << "next=" << values.front() << '\n';
    std::cout << "heap=" << std::boolalpha
              << std::is_heap(values.begin(), values.end()) << '\n';
}

Wynik

extracted=7
size_before=4
size_after=3
next=4
heap=true

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

Źródła