CKTIS / C++
std::priority_queue — Prioritätswarteschlange
std::priority_queue stellt das Element mit der höchsten Priorität bereit, nicht das zuerst eingefügte. Standardmäßig steht der größte Wert oben; std::greater<T> kehrt die Reihenfolge um.
Version: 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 aus <queue> ist ein Container-Adapter, der einen Heap verwaltet, keine FIFO-Warteschlange. Standardmäßig verwendet er std::vector<T> und std::less<T>, sodass top() den größten Wert bezeichnet. Die Variante mit std::greater<T> bezeichnet den kleinsten Wert; sie benötigt <functional>.
push() fügt einen Wert ein, während emplace() ein Element im Container konstruiert und die Heap-Eigenschaft wiederherstellt. top() ermöglicht nur lesenden Zugriff. pop() entfernt das oberste Element und gibt void zurück: Kopiere benötigte Werte vor dem Entfernen. Prüfe vor top() und pop() empty(); beide Operationen erfordern eine nicht leere Warteschlange.
Der Vergleicher muss eine strikte schwache Ordnung definieren. Compare(a, b) == true bedeutet, dass a in dieser Ordnung vor b kommt und beim Entnehmen eine niedrigere Priorität hat. Der Adapter stellt weder Iteratoren noch eine Operation zum Ändern der Priorität eines beliebigen Elements bereit.
top() hat konstante Kosten. Die Wiederherstellung des Heaps bei push(), emplace() und pop() erfordert O(log n) Vergleiche. Beim Einfügen kommen auch die Kosten des zugrunde liegenden Containers hinzu: Eine Neuzuweisung des standardmäßigen std::vector<T> kann ein einzelnes Einfügen linear machen.
Das Beispiel gibt dieselben Daten absteigend und aufsteigend aus und leert dabei beide Warteschlangen. Dieser Eintrag bezieht sich auf C++23; der verlinkte Arbeitsentwurf ist neuer und kein eingefrorener C++23-Text.
Beispiele
#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' : ' ');
}
}
Ergebnis
7 4 1 1 1 1 4 7
Der angezeigte Code und das angegebene Ergebnis wurden in einer isolierten Umgebung mit der im Prüfnachweis für genau diese Version dokumentierten Methode verifiziert.