priority_queue-Klasse

  • Artikel

Eine Vorlagencontainer-Adapterklasse, die die Funktionalität einschränkt, indem sie den Zugriff auf das oberste Element eines zugrunde liegenden Containertyps beschränkt, das immer das größte oder wichtigste Element ist. Neue Elemente können dem priority_queue und dem obersten Element des priority_queue Elements hinzugefügt werden, das geprüft oder entfernt werden kann.

Syntax

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

Parameter

Type
Der in priority_queue zu speichernde Elementdatentyp.

Container
Der Typ des zugrunde liegenden Containers, der zum Implementieren des 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, und das binäre Prädikat less<typename Container::value_type> ist der Standardwert.

Hinweise

Die im ersten Vorlagenparameter eines Warteschlangenobjekts festgelegten Elemente der Klasse Type sind synonym mit value_type dem Elementtyp in der zugrunde liegenden Containerklasse Container übereinstimmen, die vom zweiten Vorlagenparameter festgelegt ist. Die Type Zuweisung muss zulässig sein, sodass es möglich ist, Objekte dieses Typs zu kopieren und Variablen dieses Typs Werte zuzuweisen.

Die priority_queue Reihenfolge, die sie steuert, wird durch Aufrufen eines gespeicherten Funktionsobjekts der Klasse Traitssortiert. Im Allgemeinen müssen die Elemente nur kleiner als vergleichbar sein, um diese Reihenfolge festzulegen: sodass aufgrund von zwei Elementen entweder festgestellt werden kann, dass sie gleichwertig sind (im Sinne, dass keines kleiner als der andere ist) oder dass ein Element kleiner als der andere ist. Dies führt zu einer Sortierung zwischen den nicht gleichwertigen Elementen. Etwas technischer betrachtet ist die Vergleichsfunktion ein binäres Prädikat, das eine strenge schwache Sortierung im mathematischen Sinn verursacht.

Geeignete zugrunde liegende Containerklassen für priority_queue Klassendequeund die Standardklassevectoroder einen anderen Sequenzcontainer, der die Vorgänge von front, push_backund pop_back einen Iterator mit zufälligem Zugriff unterstützt. Die zugrunde liegende Containerklasse wird im Containeradapter gekapselt, der nur den begrenzten Satz der Memberfunktionen des Sequenzcontainers als öffentliche Schnittstelle verfügbar macht.

Hinzufügen und Entfernen von Elementen aus einem priority_queue; beide haben logarithmische Komplexität. Zugreifen auf Elemente in einem priority_queue mit konstanter Komplexität.

Es gibt drei Typen von Containeradaptern, die von der C++-Standardbibliothek definiert werden: stack, , queueund priority_queue. Jede schränkt die Funktionalität von einigen zugrunde liegenden Containerklassen ein, um eine präzise gesteuerte Oberfläche für eine Standarddatenstruktur anzubieten.

  • Die stack Klasse unterstützt eine LAST-In-First-Out-Datenstruktur (LIFO). Eine gute Analogie, um sich dies zu merken, ist ein Stapel von Tellern. Elemente (Teller) können eingefügt, überprüft oder nur vom Anfang des Stapels entnommen werden, was dem letzten Element am Ende des Basiscontainers entspricht. Die Einschränkung, nur auf das oberste Element zuzugreifen, ist der Grund für die Verwendung der stack Klasse.

  • Die queue Klasse unterstützt eine FiFO-Datenstruktur (First-In, First-Out). Eine gute Analogie, um sich dies zu merken, sind Personen, die an einem Bankschalter anstehen. Elemente (Personen) können am Ende der Schlange hinzugefügt werden und vom Anfang der Schlange entfernt werden. Sowohl der Anfang als auch das Ende einer Schlange können überprüft werden. Die Einschränkung für den Zugriff auf die Vorder- und Rückseitenelemente auf diese Weise ist der Grund für die Verwendung der queue Klasse.

  • Die priority_queue Klasse sortiert ihre Elemente so, dass das größte Element immer an der obersten Position liegt. Die Klasse unterstützt Einfügen eines Elements sowie die Prüfung und Entfernung des obersten Elements. Ein gutes Analoga, das sie berücksichtigen sollten, wäre es, dass Personen, die nach Alter, Höhe oder einem anderen Kriterium angeordnet sind, anordnen.

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 durch ein priority_queue-Objekt übernommen werden soll.
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

Header<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. Die Containerklasse deque C++ Standard Library und die Standardklasse vector erfüllen die Anforderungen, die als Basiscontainer für ein priority_queue Objekt verwendet werden sollen. Benutzerdefinierte Typen, die diese Anforderung erfüllen, können auch verwendet werden.

Weitere Informationen Containerfinden Sie im Abschnitt "Hinweise" des priority_queue Themas "Klasse ".

Beispiel

Ein Beispiel für priority_queue das Deklarieren und Verwenden container_typefinden Sie im Beispiel.

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

// pqueue_empty.cpp
// 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

Der priority_queue Wert muss nicht sein, um die Memberfunktion anzuwenden. Der obere Rand des Elements priority_queue wird immer von dem größten Element im Container belegt.

Beispiel

// pqueue_pop.cpp
// 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 eine priority_queue leere Oder eine Kopie eines Bereichs eines Basiscontainerobjekts oder eines 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 (_Cont) angeben container_type . 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

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

int main( )
{
   using namespace std;

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

   // Explicitly 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;

   // This method of printing out the elements of a priority_queue
   // removes the elements from the priority queue, leaving it empty
   cout << "After printing, q2 has " << q2.size( ) << " elements." << endl;

   // The third member function 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;

   // The fourth member function declares a priority_queue and
   // initializes it with elements copied from another container:
   // first, inserting elements into q1, 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;

   // The fifth member function 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;

   // The sixth member function 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 oben in der priority_queue.

Hinweise

Am oberen Rand priority_queue befindet sich die Position, die vom größten Element im Container belegt wird.

Beispiel

// pqueue_push.cpp
// 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

// pqueue_size.cpp
// 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

Eine Ganzzahltyp ohne Vorzeichen, der die Anzahl von Elementen in priority_queue darstellen kann.

typedef typename Container::size_type size_type;

Hinweise

Der Typ ist ein Synonym für den size_type von der priority_queue.

Beispiel

Ein Beispiel für size das Deklarieren und Verwenden size_typefinden Sie im Beispiel.

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

Der priority_queue Wert muss nicht sein, um die Memberfunktion anzuwenden.

Beispiel

// pqueue_top.cpp
// 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

Der Typ ist ein Synonym für den value_type von der priority_queue.

Beispiel

// pqueue_value_type.cpp
// 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.

Siehe auch

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