CKTIS / C++
std::priority_queue — prioritetni red
std::priority_queue omogućuje pristup elementu s najvišim prioritetom, a ne onome koji je prvi umetnut. Prema zadanim postavkama na vrhu je najveća vrijednost; std::greater<T> obrće redoslijed.
Verzija: 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> adapter je spremnika koji održava hrpu, a ne FIFO red. Prema zadanim postavkama koristi std::vector<T> i std::less<T>, pa top() označava najveću vrijednost. Inačica sa std::greater<T> označava najmanju vrijednost i zahtijeva <functional>.
push() umeće vrijednost, dok emplace() konstruira element u spremniku i obnavlja svojstvo hrpe. top() omogućuje pristup samo za čitanje. pop() uklanja vrh i vraća void: potrebnu vrijednost kopirajte prije uklanjanja. Prije top() i pop() provjerite empty(); obje operacije zahtijevaju neprazan red.
Komparator mora definirati strogo slabo uređenje. Compare(a, b) == true znači da a u tom uređenju prethodi elementu b te ima niži prioritet pri uklanjanju. Adapter ne izlaže iteratore ni operaciju za promjenu prioriteta proizvoljnog elementa.
top() ima konstantnu složenost. Obnavljanje hrpe tijekom push(), emplace() i pop() zahtijeva O(log n) usporedbi. Umetanje uključuje i trošak temeljnog spremnika: ponovna alokacija zadanog std::vector<T> može pojedinačno umetanje učiniti linearnim.
Primjer ispisuje iste podatke silaznim i uzlaznim redoslijedom te pritom prazni oba reda. Ovaj se zapis odnosi na C++23; povezani radni nacrt noviji je i nije zamrznuti tekst C++23.
Primjeri
#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
Prikazani kôd i navedeni rezultat provjereni su u izoliranom okruženju metodom zabilježenom u dokazu provjere za ovu točnu verziju.