Namensräume
Varianten
Aktionen

std::priority_queue

Von cppreference.com
< cpp‎ | container
 
C++
 
Container-Bibliothek
 
std::priority_queue
 
Definiert in Header <queue>
template<

    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>

> class priority_queue;

Die Prioritätswarteschlange ist ein Container-Adapter, der eine konstante Zeit für die Suche nach dem größten (standardmäßig) Element bietet, auf Kosten von logarithmischer Einfügung und Extraktion.

Ein vom Benutzer bereitgestellter Compare kann angegeben werden, um die Reihenfolge zu ändern, z. B. würde die Verwendung von std::greater<T> dazu führen, dass das kleinste Element als top() erscheint.

Die Arbeit mit einer priority_queue ähnelt der Verwaltung eines Heaps in einem beliebigen Random-Access-Container, mit dem Vorteil, dass der Heap nicht versehentlich ungültig gemacht werden kann.

Alle Memberfunktionen von std::priority_queue sind constexpr: Es ist möglich, std::priority_queue-Objekte in der Auswertung eines konstanten Ausdrucks zu erstellen und zu verwenden.

std::priority_queue-Objekte können jedoch im Allgemeinen nicht constexpr sein, da dynamisch zugewiesener Speicher in derselben Auswertung eines konstanten Ausdrucks freigegeben werden muss.

 (seit C++26)

Inhalt

[edit] Template-Parameter

T - Der Typ der gespeicherten Elemente. Das Programm ist fehlerhaft, wenn T nicht vom gleichen Typ wie Container::value_type ist.
Container - Der Typ des zugrunde liegenden Containers, der zum Speichern der Elemente verwendet werden soll. Der Container muss die Anforderungen eines SequenceContainers erfüllen, und seine Iteratoren müssen die Anforderungen eines LegacyRandomAccessIterators erfüllen. Zusätzlich muss er die folgenden Funktionen mit der üblichen Semantik bereitstellen:

Die Standardcontainer std::vector (einschließlich std::vector<bool>) und std::deque erfüllen diese Anforderungen.

Compare - Ein Compare-Typ, der eine strikte schwache Ordnung bereitstellt.

Beachten Sie, dass der Compare-Parameter so definiert ist, dass er true zurückgibt, wenn sein erstes Argument in einer schwachen Ordnung *vor* seinem zweiten Argument liegt. Da die Prioritätswarteschlange jedoch die größten Elemente zuerst ausgibt, werden die Elemente, die "davor" liegen, tatsächlich zuletzt ausgegeben. Das heißt, die Spitze der Warteschlange enthält das "letzte" Element gemäß der schwachen Ordnung, die durch Compare auferlegt wird.

[edit] Member-Typen

Mitgliedertyp Definition
container_type Container[edit]
value_compare Compare
value_type Container::value_type[edit]
size_type Container::size_type[edit]
Referenz Container::reference[edit]
const_reference Container::const_reference[edit]

[edit] Member-Objekte

Member-Name Definition
Container c
 der zugrunde liegende Container
(protected member object) [edit]
Compare comp
 das Vergleichsfunktions-Objekt
(geschütztes Member-Objekt)

[edit] Member-Funktionen

 konstruiert die priority_queue
(public member function) [edit]
 destruiert die priority_queue
(public member function) [edit]
 weist Werte dem Container-Adapter zu
(public member function) [edit]
Elementzugriff
 greift auf das oberste Element zu
(public member function) [edit]
Kapazität
 prüft, ob der Container-Adapter leer ist
(public member function) [edit]
 Gibt die Anzahl der Elemente zurück
(public member function) [edit]
Modifizierer
 fügt ein Element ein und sortiert den zugrunde liegenden Container
(public member function) [edit]
(C++23)
 fügt einen Bereich von Elementen ein und sortiert den zugrunde liegenden Container
(public member function) [edit]
(C++11)
 konstruiert das Element an Ort und Stelle und sortiert den zugrunde liegenden Container
(public member function) [edit]
 entfernt das oberste Element
(public member function) [edit]
(C++11)
 tauscht die Inhalte
(public member function) [edit]

[edit] Nicht-Member-Funktionen

(C++11)
 spezialisiert den Algorithmus std::swap
(function template) [edit]

[edit] Hilfsklassen

(C++11)
 spezialisiert das std::uses_allocator Typ-Trait
(Klassenvorlagenspezialisierung) [edit]
(C++23)
 Formatierungsunterstützung für std::priority_queue
(Klassenvorlagenspezialisierung) [edit]

Deduction Guides

 (seit C++17)

[edit] Anmerkungen

Feature-Test-Makro Wert Std Feature
__cpp_lib_containers_ranges 202202L (C++23) Bereichsweise Konstruktion und Einfügung für Container
__cpp_lib_constexpr_containers 202502L (C++26) constexpr std::priority_queue

[edit] Beispiel

Führen Sie diesen Code aus
#include <functional>
#include <iostream>
#include <queue>
#include <string_view>
#include <vector>
 
template<typename T>
void pop_println(std::string_view rem, T& pq)
{
    std::cout << rem << ": ";
    for (; !pq.empty(); pq.pop())
        std::cout << pq.top() << ' ';
    std::cout << '\n';
}
 
template<typename T>
void println(std::string_view rem, const T& v)
{
    std::cout << rem << ": ";
    for (const auto& e : v)
        std::cout << e << ' ';
    std::cout << '\n';
}
 
int main()
{
    const auto data = {1, 8, 5, 6, 3, 4, 0, 9, 7, 2};
    println("data", data);
 
    std::priority_queue<int> max_priority_queue;
 
    // Fill the priority queue.
    for (int n : data)
        max_priority_queue.push(n);
 
    pop_println("max_priority_queue", max_priority_queue);
 
    // std::greater<int> makes the max priority queue act as a min priority queue.
    std::priority_queue<int, std::vector<int>, std::greater<int>>
        min_priority_queue1(data.begin(), data.end());
 
    pop_println("min_priority_queue1", min_priority_queue1);
 
    // Second way to define a min priority queue.
    std::priority_queue min_priority_queue2(data.begin(), data.end(), std::greater<int>());
 
    pop_println("min_priority_queue2", min_priority_queue2);
 
    // Using a custom function object to compare elements.
    struct
    {
        bool operator()(const int l, const int r) const { return l > r; }
    } customLess;
 
    std::priority_queue custom_priority_queue(data.begin(), data.end(), customLess);
 
    pop_println("custom_priority_queue", custom_priority_queue);
 
    // Using lambda to compare elements.
    auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1); };
    std::priority_queue<int, std::vector<int>, decltype(cmp)> lambda_priority_queue(cmp);
 
    for (int n : data)
        lambda_priority_queue.push(n);
 
    pop_println("lambda_priority_queue", lambda_priority_queue);
}

Ausgabe

data: 1 8 5 6 3 4 0 9 7 2
max_priority_queue: 9 8 7 6 5 4 3 2 1 0
min_priority_queue1: 0 1 2 3 4 5 6 7 8 9
min_priority_queue2: 0 1 2 3 4 5 6 7 8 9
custom_priority_queue: 0 1 2 3 4 5 6 7 8 9
lambda_priority_queue: 8 9 6 7 4 5 2 3 0 1

[edit] Fehlerberichte

Die folgenden Verhaltensändernden Fehlerberichte wurden rückwirkend auf zuvor veröffentlichte C++-Standards angewendet.

DR angewendet auf Verhalten wie veröffentlicht Korrigiertes Verhalten
LWG 307 C++98 Container konnte nicht std::vector<bool> sein erlaubt
LWG 2566 C++98 Fehlende Anforderung für Container::value_type fehlerhaft, wenn T nicht vom gleichen Typ wie Container::value_type ist
LWG 2684 C++98 priority_queue nimmt einen Comparator entgegen
aber es fehlte der Member-Typedef dafür		 hinzugefügt

[edit] Siehe auch

 reservierbares, zusammenhängendes Array
(Klassenvorlage) [edit]
 speichereffizientes dynamisches Bitset
(class template specialization) [edit]
 Doppelt-endende Warteschlange
(Klassenvorlage) [edit]
Retrieved from "https://cppreference.de/mwiki/index.php?title=cpp/container/priority_queue&oldid=180915"