Znalostná bázaCentrum skúšok
SKSlovenčina
Vybrať jazyk13

CKTIS / C++

std::priority_queue — prioritný rad

std::priority_queue sprístupňuje prvok s najvyššou prioritou, nie prvok vložený ako prvý. Predvolene je navrchu najväčšia hodnota; std::greater<T> poradie obráti.

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

Syntax

#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 kontajnera, ktorý udržiava haldu, nie rad FIFO. Predvolene používa std::vector<T> a std::less<T>, takže top() označuje najväčšiu hodnotu. Variant so std::greater<T> označuje najmenšiu hodnotu a vyžaduje <functional>.

push() vloží hodnotu, zatiaľ čo emplace() vytvorí prvok v kontajneri a obnoví vlastnosť haldy. top() poskytuje prístup iba na čítanie. pop() odstráni vrchol a vracia void: potrebnú hodnotu pred odstránením skopírujte. Pred top() a pop() skontrolujte empty(); obe operácie vyžadujú neprázdny rad.

Komparátor musí definovať striktné slabé usporiadanie. Compare(a, b) == true znamená, že a v tomto usporiadaní predchádza b, a má teda nižšiu prioritu pri odoberaní. Adaptér neposkytuje iterátory ani operáciu na zmenu priority ľubovoľného prvku.

top() má konštantné náklady. Obnovenie haldy pri operáciách push(), emplace() a pop() vyžaduje O(log n) porovnaní. Vkladanie zahŕňa aj náklady podkladového kontajnera: realokácia predvoleného std::vector<T> môže spôsobiť, že jednotlivé vloženie bude lineárne.

Príklad vypíše rovnaké údaje zostupne a vzostupne a oba rady pritom vyprázdni. Tento záznam sa vzťahuje na C++23; odkazovaný pracovný návrh je novší a nejde o zmrazený text C++23.

Prí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ýsledok

7 4 1 1
1 1 4 7

Zobrazený kód a uvedený výsledok boli overené v izolovanom prostredí metódou zaznamenanou v dôkaze o overení tejto presnej verzie.

Zdroje