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

CKTIS / C++

std::priority_queue — prioritní fronta

std::priority_queue zpřístupňuje prvek s nejvyšší prioritou, nikoli prvek vložený jako první. Ve výchozím nastavení je nahoře největší hodnota; std::greater<T> pořadí obrací.

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

Syntaxe

#include <functional>
#include <queue>
#include <vector>

std::priority_queue<T> q;
std::priority_queue<T, std::vector<T>, std::greater<T>> min_q;

std::priority_queue z <queue> je adaptér kontejneru, který udržuje haldu, nikoli frontu FIFO. Ve výchozím nastavení používá std::vector<T> a std::less<T>, takže top() označuje největší hodnotu. Varianta se std::greater<T> označuje nejmenší hodnotu a vyžaduje <functional>.

push() vloží hodnotu, zatímco emplace() vytvoří prvek v kontejneru a obnoví vlastnost haldy. top() poskytuje přístup pouze pro čtení. pop() odstraní vrchol a vrací void: potřebnou hodnotu před odstraněním zkopírujte. Před top() a pop() ověřte empty(); obě operace vyžadují neprázdnou frontu.

Komparátor musí definovat striktní slabé uspořádání. Compare(a, b) == true znamená, že a v tomto uspořádání předchází b, a má tedy nižší prioritu při odebírání. Adaptér neposkytuje iterátory ani operaci pro změnu priority libovolného prvku.

top() má konstantní náklady. Obnovení haldy při operacích push(), emplace() a pop() vyžaduje O(log n) porovnání. Vkládání zahrnuje také náklady podkladového kontejneru: realokace výchozího std::vector<T> může způsobit, že jednotlivé vložení bude lineární.

Příklad vypíše stejná data sestupně a vzestupně a obě fronty přitom vyprázdní. Tento záznam se vztahuje k C++23; odkazovaný pracovní návrh je novější a nejde o zmrazený text C++23.

Příklady

#include <functional>
#include <iostream>
#include <queue>
#include <vector>

int main() {
    std::priority_queue<int> max_q;
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_q;

    for (int value : {4, 1, 7, 1}) {
        max_q.push(value);
        min_q.push(value);
    }

    while (!max_q.empty()) {
        std::cout << max_q.top();
        max_q.pop();
        std::cout << (max_q.empty() ? '\n' : ' ');
    }
    while (!min_q.empty()) {
        std::cout << min_q.top();
        min_q.pop();
        std::cout << (min_q.empty() ? '\n' : ' ');
    }
}

Výsledek

7 4 1 1
1 1 4 7

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