CKTIS / C++
std::priority_queue — prioriteitswachtrij
std::priority_queue geeft toegang tot het element met de hoogste prioriteit, niet tot het element dat het eerst is toegevoegd. Standaard staat de grootste waarde bovenaan; std::greater<T> keert de volgorde om.
Versie: 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 uit <queue> is een containeradapter die een heap bijhoudt, geen FIFO-wachtrij. Standaard gebruikt deze std::vector<T> en std::less<T>, zodat top() de grootste waarde aanwijst. De variant met std::greater<T> wijst de kleinste waarde aan en vereist <functional>.
push() voegt een waarde toe, terwijl emplace() een element in de container construeert en de heap-eigenschap herstelt. top() biedt alleen-lezen toegang. pop() verwijdert het bovenste element en retourneert void: kopieer benodigde waarden voordat je ze verwijdert. Controleer empty() vóór top() en pop(); beide bewerkingen vereisen een niet-lege wachtrij.
De comparator moet een strikte zwakke ordening definiëren. Compare(a, b) == true betekent dat a in die ordening vóór b komt en dus een lagere verwijderprioriteit heeft. De adapter biedt geen iterators en ook geen bewerking om de prioriteit van een willekeurig element te wijzigen.
top() heeft constante kosten. Het herstellen van de heap tijdens push(), emplace() en pop() vereist O(log n) vergelijkingen. Toevoegen brengt ook de kosten van de onderliggende container met zich mee: het opnieuw toewijzen van de standaard-std::vector<T> kan één invoeging lineair maken.
Het voorbeeld drukt dezelfde gegevens af in aflopende en oplopende volgorde en maakt beide wachtrijen leeg. Dit item richt zich op C++23; het gekoppelde werkdocument is nieuwer en is geen bevroren C++23-tekst.
Voorbeelden
#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' : ' ');
}
}
Resultaat
7 4 1 1 1 1 4 7
De getoonde code en het opgegeven resultaat zijn in een geïsoleerde omgeving geverifieerd met de methode die in het verificatiebewijs voor exact deze versie is vastgelegd.