CKTIS / C++
std::priority_queue — prednostna vrsta
std::priority_queue omogoča dostop do elementa z najvišjo prednostjo, ne do najprej vstavljenega elementa. Privzeto je na vrhu največja vrednost; std::greater<T> obrne vrstni red.
Različica: C++23; repository compiler flag, production runtime not attested
Sintaksa
#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 iz <queue> je vsebniški adapter, ki vzdržuje kopico, ne pa vrste FIFO. Privzeto uporablja std::vector<T> in std::less<T>, zato top() označuje največjo vrednost. Različica z std::greater<T> označuje najmanjšo vrednost in zahteva <functional>.
push() vstavi vrednost, medtem ko emplace() ustvari element v vsebniku in obnovi lastnost kopice. top() omogoča samo branje. pop() odstrani vrhnji element in vrne void: potrebne vrednosti pred odstranitvijo kopirajte. Pred top() in pop() preverite empty(); obe operaciji zahtevata neprazno vrsto.
Primerjalnik mora določati strogo šibko urejenost. Compare(a, b) == true pomeni, da je a v tej urejenosti pred b in ima zato nižjo prednost pri odstranjevanju. Adapter ne ponuja iteratorjev ali operacije za spreminjanje prednosti poljubnega elementa.
top() ima konstantno zahtevnost. Obnavljanje kopice med operacijami push(), emplace() in pop() zahteva O(log n) primerjav. Vstavljanje vključuje tudi strošek osnovnega vsebnika: ponovna alokacija privzetega std::vector<T> lahko posamezno vstavljanje spremeni v linearno operacijo.
Primer izpiše iste podatke v padajočem in naraščajočem vrstnem redu ter izprazni obe vrsti. Ta vnos obravnava C++23; povezani delovni osnutek je novejši in ni zamrznjeno besedilo C++23.
Primeri
#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' : ' ');
}
}
Rezultat
7 4 1 1 1 1 4 7
Prikazana koda in navedeni rezultat sta bila preverjena v izoliranem okolju z metodo, zapisano v dokazilu o preverjanju te natančne različice.