Freigeben über

priority_queue-Klasse

Ein Containeradapter, der eine Sammlung von Elementen verwaltet, auf die das größte (oder höchste Prioritätselement) immer oben zugegriffen werden kann. Sie können neue Elemente hinzufügen und das oberste Element entfernen oder untersuchen, aber sie können nicht direkt auf Elemente in der Mitte der Auflistung zugreifen.

Syntax

template <class Type, class Container= vector <Type>, class Compare= less <typename Container ::value_type>>
class priority_queue

Parameter

Type
Der Elementdatentyp, der in der priority_queueDatei gespeichert werden soll.

Container
Der Typ des zugrunde liegenden Containers, der die Elemente für die priority_queue.

Compare
Der Typ, der ein Funktionsobjekt bereitstellt, das zwei Elementwerte als Sortierschlüssel vergleicht, um die relative Reihenfolge in der priority_queue. Dieses Argument ist optional. Das binäre Prädikat less<typename Container::value_type> ist der Standardwert.

Hinweise

Elemente der KlasseType, die im ersten Vorlagenparameter eines priority_queue Objekts angegeben sind, entsprechen und müssen mit dem Elementtyp in der zugrunde liegenden Containerklasse Container übereinstimmenvalue_type, die durch den zweiten Vorlagenparameter angegeben wird. Dies Type muss zuzuweisen sein, d. h., Sie können Objekte dieses Typs kopieren und Variablen dieses Typs Werte zuweisen.

Die Vergleichsfunktion priority_queue bestimmt anhand einer Vergleichsfunktion, welche Elemente eine höhere Priorität haben. Diese Vergleichsfunktion ist ein Funktionsobjekt der Klasse Traits. Um mit priority_queueihnen zu arbeiten, müssen Ihre Elemente nur den Vergleich mit dem Operator kleiner als (<) unterstützen, damit sie die Elemente in der Reihenfolge anordnen kann.

Sie können den zugrunde liegenden Containertyp ändern, der von der priority_queue. Sie können dies aus Leistungsgründen tun. Die Standardeinstellung , vectorist in der Regel am besten für die Cachelokalität geeignet, da Elemente im zusammenhängenden Speicher gespeichert werden und weniger Zuordnungen bei wächst. Aber vielleicht würden Sie überlegen deque , ob Sie sehr große oder ungebundene Warteschlangen haben und verschiebende Elemente teuer sind. Weitere Informationen zu geeigneten zugrunde liegenden Containerklassen finden Sie unter container_type.

Das Hinzufügen und Entfernen von Elementen aus beiden priority_queue hat eine logarithmische Komplexität. Zugreifen auf Elemente in einem priority_queue mit konstanter Komplexität.

Die C++-Standardbibliothek definiert andere Containeradapter, die Sie zum Speichern der Elemente in Ihrem priority_queue: stack, , queueund priority_queue:

  • Die stack Klasse unterstützt eine LAST-In-First-Out-Datenstruktur (LIFO). Betrachten Sie einen Plattenstapel: Sie können Elemente (Platten) nur vom oberen Rand des Stapels einfügen, prüfen oder entfernen, bei dem es sich um das letzte Element am Ende des Basiscontainers handelt.
  • Die queue Klasse unterstützt eine FiFO-Datenstruktur (First-In, First-Out). Betrachten Sie Personen in einer Zeile. Sie fügen Elemente (Personen) zur Rückseite der Zeile hinzu und entfernen sie von der Vorderseite der Linie. Sowohl die Vorder- als auch die Rückseite einer Linie können geprüft werden.
  • Die priority_queue Klasse ordnet ihre Elemente so an, dass das größte Element immer ganz oben liegt. Die Klasse unterstützt Einfügen eines Elements sowie die Prüfung und Entfernung des obersten Elements.

Examples

Konstruktoren

Konstruktor Beschreibung
priority_queue Erstellt ein priority_queue-Objekt, das leer oder eine Kopie eines Basiscontainerobjekts oder eines anderen priority_queue ist.

TypeDefs

Typname Beschreibung
container_type Ein Typ, der den Basiscontainer bereitstellt, der angepasst priority_queue wird.
size_type Eine Ganzzahltyp ohne Vorzeichen, der die Anzahl von Elementen in priority_queue darstellen kann.
value_type Ein Typ, der den Typ des Objekts angibt, das in einem priority_queue-Objekt als Element gespeichert wird.

Memberfunktionen

Memberfunktion Beschreibung
empty Testet, ob das priority_queue-Objekt ist leer.
pop Entfernt das größte Element der priority_queue von der obersten Position.
push Fügt der Prioritätswarteschlange basierend auf der Priorität des Elements ein Element hinzu operator<.
size Gibt die Anzahl von Elementen in der priority_queue zurück.
top Gibt einen konstanten Verweis auf das größte Element am oberen Rand von priority_queue zurück.

Anforderungen

Kopfball:<queue>

Namespace:std

priority_queue::container_type

Ein Typ, der den anzupassenden Basiscontainer bereitstellt.

typedef Container container_type;

Hinweise

Der Type stellt ein Synonym für den Vorlagenparameter Containerdar.

Geeignete zugrunde liegende Containerklassen für priority_queueKlassendeque, die Standardklassevector oder einen anderen Sequenzcontainer, der die Vorgänge von front, push_backund pop_back ein Iterator für zufälligen Zugriff unterstützt. Der Containeradapter kapselt die zugrunde liegende Containerklasse und macht nur einen begrenzten Satz von Sequenzcontainermemmfunktionen als öffentliche Schnittstelle verfügbar.

Ein Beispiel für das Deklarieren und Verwenden container_typefinden Sie unter Verwenden von benutzerdefinierten Containern und Vergleichern

priority_queue::empty

Testet, ob ein priority_queue-Element leer ist.

bool empty() const;

Rückgabewert

true wenn die priority_queue leer ist; false wenn dies priority_queue nicht zu ernennen ist.

Beispiel: Überprüfen, ob die Prozedur priority_queue leer ist

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;

   // Declares priority_queues with default deque base container
   priority_queue <int> q1, s2;

   q1.push(1);

   if (q1.empty())
      cout << "The priority_queue q1 is empty." << endl;
   else
      cout << "The priority_queue q1 is not empty." << endl;

   if (s2.empty())
      cout << "The priority_queue s2 is empty." << endl;
   else
      cout << "The priority_queue s2 is not empty." << endl;
}

The priority_queue q1 is not empty.
The priority_queue s2 is empty.

priority_queue::pop

Entfernt das größte Element der priority_queue von der obersten Position.

void pop();

Hinweise

Die priority_queue Funktion muss nicht in Anspruch nehmen, um diese Memberfunktion zu verwenden. Der obere Rand des priority_queue Containers enthält immer das größte Element im Container.

Beispiel: Popelemente und Prüfgröße

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;
   priority_queue <int> q1, s2;

   q1.push(10);
   q1.push(20);
   q1.push(30);

   priority_queue <int>::size_type i, iii;
   i = q1.size();
   cout << "The priority_queue length is " << i << "." << endl;

   const int& ii = q1.top();
   cout << "The element at the top of the priority_queue is " << ii << "." << endl;

   q1.pop();

   iii = q1.size();
   cout << "After a pop, the priority_queue length is " << iii << "." << endl;

   const int& iv = q1.top();
   cout << "After a pop, the element at the top of the " << "priority_queue is " << iv << "." << endl;
}

The priority_queue length is 3.
The element at the top of the priority_queue is 30.
After a pop, the priority_queue length is 2.
After a pop, the element at the top of the priority_queue is 20.

priority_queue::priority_queue

Erstellt ein leeres priority_queue Objekt oder kopiert einen Bereich aus einem Basiscontainerobjekt oder aus einem anderen priority_queue.

priority_queue();

explicit priority_queue(const Traits& _comp);

priority_queue(const Traits& _comp, const container_type& _Cont);

priority_queue(const priority_queue& right);

template <class InputIterator>
priority_queue(InputIterator first, InputIterator last);

template <class InputIterator>
priority_queue(InputIterator first, InputIterator last, const Traits& _comp);

template <class InputIterator>
priority_queue(InputIterator first, InputIterator last, const Traits& _comp, const container_type& _Cont);

Parameter

_comp
Die Vergleichsfunktion des Typs constTraits , die verwendet wird, um die Elemente in der priority_queueZeichenfolge zu sortieren, die standardmäßig die Funktion des Basiscontainers vergleicht.

_Cont
Der Basiscontainer, von dem der konstruierte priority_queue Container eine Kopie sein soll.

right
Der priority_queue konstruierte Satz soll eine Kopie sein.

first
Die Position des ersten Elements in dem zu kopierenden Elementbereich.

last
Die Position des ersten Elements nach dem zu kopierenden Elementbereich.

Hinweise

Jeder der ersten drei Konstruktoren gibt eine leere Initiale priority_queuean, die zweite gibt auch den Typ der Vergleichsfunktion (comp) an, der verwendet werden soll, um die Reihenfolge der Elemente festzulegen, und der dritte explizit die zu verwendende (container_type) angeben _Cont . Mit dem Schlüsselwort explicit werden bestimmte Arten automatischer Typumwandlung unterdrückt.

Der vierte Konstruktor gibt eine Kopie der priority_queue right.

Die letzten drei Konstruktoren kopieren den Bereich [first, last) einiger Container und verwenden die Werte zum Initialisieren einer priority_queue mit zunehmender Explizitkeit beim Angeben des Typs der Vergleichsfunktion der Klasse Traits und container_type.

Beispiel: Verwenden von benutzerdefinierten Containern und Vergleichern

// compile with: /EHsc
#include <queue>
#include <vector>
#include <deque>
#include <list>
#include <iostream>

int main()
{
   using namespace std;

   // Declares a priority_queue with a default vector base container
   priority_queue <int> q1;
   cout << "q1 = ( ";
   while (!q1.empty())
   {
      cout << q1.top() << " ";
      q1.pop();
   }
   cout << ")" << endl;

   // Declares a priority_queue with nondefault deque base container
   priority_queue <int, deque <int>> q2;
   q2.push(5);
   q2.push(15);
   q2.push(10);
   cout << "q2 = ( ";
   while (!q2.empty())
   {
      cout << q2.top() << " ";
      q2.pop();
   }
   cout << ")" << endl;
   cout << "After printing, q2 has " << q2.size() << " elements." << endl;

   // Declares a priority_queue with a vector base container and specifies that
   // the comparison function greater is to be used for ordering elements
   priority_queue <int, vector<int>, greater<int>> q3;
   q3.push(2);
   q3.push(1);
   q3.push(3);
   cout << "q3 = ( ";
   
   while (!q3.empty())
   {
      cout << q3.top() << " ";
      q3.pop();
   }
   cout << ")" << endl;

   // Declares a priority_queue and initializes it with elements copied from another
   // container by first inserting elements into q1 and then copying q1 elements into q4
   q1.push(100);
   q1.push(200);
   priority_queue <int> q4(q1);
   cout << "q4 = ( ";
   while (!q4.empty())
   {
      cout << q4.top() << " ";
      q4.pop();
   }
   cout << ")" << endl;

   // Creates an auxiliary vector object v5 to be used to initialize q5
   vector <int> v5;
   vector <int>::iterator v5_Iter;
   v5.push_back(10);
   v5.push_back(30);
   v5.push_back(20);
   cout << "v5 = ( " ;
   for (v5_Iter = v5.begin() ; v5_Iter != v5.end() ; v5_Iter++)
   {
      cout << *v5_Iter << " ";
   }
   cout << ")" << endl;

   // Declares and initializes a priority_queue q5 by copying the
   // range v5[ first,  last) from vector v5
   priority_queue <int> q5(v5.begin(), v5.begin() + 2);
   cout << "q5 = ( ";
   while (!q5.empty())
   {
      cout << q5.top() << " ";
      q5.pop();
   }
   cout << ")" << endl;

   // Declares a priority_queue q6 with a comparison function greater and
   // initializes q6 by copying the range v5[ first,  last) from vector v5
   priority_queue <int, vector<int>, greater<int>> q6(v5.begin(), v5.begin() + 2);
   cout << "q6 = ( ";
   while (!q6.empty())
   {
      cout << q6.top() << " ";
      q6.pop();
   }
   cout << ")" << endl;
}

priority_queue::push

Fügt der Prioritätswarteschlange basierend auf der Priorität des Elements ein Element hinzu operator<.

void push(const Type& val);

Parameter

val
Das Element, das am anfang des priority_queueElements hinzugefügt werden soll.

Hinweise

Der obere Rand des priority_queue Containers enthält das größte Element im Container.

Beispiel: Pushelemente und Lesen des oberen Rands

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;
   priority_queue<int> q1;

   q1.push(10);
   q1.push(30);
   q1.push(20);

   priority_queue<int>::size_type i;
   i = q1.size();
   cout << "The priority_queue length is " << i << "." << endl;

   const int& ii = q1.top();
   cout << "The element at the top of the priority_queue is " << ii << "." << endl;
}

The priority_queue length is 3.
The element at the top of the priority_queue is 30.

priority_queue::size

Gibt die Anzahl von Elementen in der priority_queue zurück.

size_type size() const;

Rückgabewert

Die aktuelle Länge des priority_queue.

Beispiel: Abrufen der Anzahl der Elemente in der priority_queue

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;
   priority_queue <int> q1, q2;
   priority_queue <int>::size_type i;

   q1.push(1);
   i = q1.size();
   cout << "The priority_queue length is " << i << "." << endl;

   q1.push(2);
   i = q1.size();
   cout << "The priority_queue length is now " << i << "." << endl;
}

The priority_queue length is 1.
The priority_queue length is now 2.

priority_queue::size_type

Ein ganzzahliger Typ ohne Vorzeichen, der die Anzahl der Elemente in einem priority_queue.

typedef typename Container::size_type size_type;

Hinweise

Dieser Typ ist ein Synonym für den size_type Basiscontainer, der priority_queue angepasst wird.

Beispiel: Zugreifen auf das oberste Element

Ein Beispiel zum Deklarieren und Verwenden size_typefinden Sie unter Abrufen der Anzahl von Elementen

priority_queue::top

Gibt einen konstanten Verweis auf das größte Element am oberen Rand von priority_queue zurück.

const_reference top() const;

Rückgabewert

Ein Verweis auf das größte Element, das durch die Traits Funktion bestimmt wird, objekt des priority_queue.

Hinweise

Die priority_queue Funktion muss nicht in Anspruch nehmen, um diese Memberfunktion zu verwenden.

Beispiel: Abrufen des obersten Elements des priority_queue

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;
   priority_queue<int> q1;

   q1.push(10);
   q1.push(30);
   q1.push(20);

   priority_queue<int>::size_type i;
   i = q1.size();
   cout << "The priority_queue length is " << i << "." << endl;

   const int& ii = q1.top();
   cout << "The element at the top of the priority_queue is " << ii << "." << endl;
}

The priority_queue length is 3.
The element at the top of the priority_queue is 30.

priority_queue::value_type

Ein Typ, der den Typ des Objekts angibt, das in einem priority_queue-Objekt als Element gespeichert wird.

typedef typename Container::value_type value_type;

Hinweise

Dieser Typ ist ein Synonym für den value_type Basiscontainer, der priority_queue angepasst wird.

Beispiel: Verwenden des priority_queue value_type-Alias

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;

   // Declares priority_queues with default deque base container
   priority_queue<int>::value_type AnInt;

   AnInt = 69;
   cout << "The value_type is AnInt = " << AnInt << endl;

   priority_queue<int> q1;
   q1.push(AnInt);
   cout << "The element at the top of the priority_queue is " << q1.top() << "." << endl;
}

The value_type is AnInt = 69
The element at the top of the priority_queue is 69.

Beispiel: Verwenden eines benutzerdefinierten Datentyps

Zur Verwendung priority_queue mit benutzerdefinierten Typelementen müssen Sie eine Möglichkeit zum Vergleichen der Elemente bereitstellen. Sie können entweder für Ihren Typ definieren operator< oder ein benutzerdefiniertes Vergleichsfunktionsobjekt bereitstellen.

Im folgenden Beispiel wird ein priority_queue Objekt gespeichert Task , das nach Prioritätsebene sortiert ist. Aufgaben mit höheren Prioritätswerten befinden sich am Anfang der Warteschlange.

// compile with: /EHsc
#include <queue>
#include <iostream>
#include <string>

struct Task
{
    int priority;
    std::string name;

    // Define operator< for priority_queue ordering
    // Returns true if this task has LOWER priority than other
    // (priority_queue puts the "largest" element at the top)
    bool operator<(const Task& other) const
    {
        return priority < other.priority;
    }
};

int main()
{
    std::priority_queue<Task> tasks;

    tasks.push({3, "Low priority task"});
    tasks.push({10, "High priority task"});
    tasks.push({5, "Medium priority task"});

    std::cout << "Processing tasks by priority:\n";
    while (!tasks.empty())
    {
        const Task& t = tasks.top();
        std::cout << "  Priority " << t.priority << ": " << t.name << "\n";
        tasks.pop();
    }
}

Processing tasks by priority:
  Priority 10: High priority task
  Priority 5: Medium priority task
  Priority 3: Low priority task

Hinweise

Wenn Sie eine andere Sortierung wünschen (z. B. zuerst niedrigere Werte), geben Sie einen benutzerdefinierten Vergleich an:

struct ComparePriority
{
    bool operator()(const Task& a, const Task& b)
    {
        return a.priority > b.priority; // Lower priority value means higher priority
    }
};

std::priority_queue<Task, std::vector<Task>, ComparePriority> minQueue;

Siehe auch

Threadsicherheit in der C++-Standardbibliothek
C++-Standardbibliotheksreferenz

  • Last updated on