priority_queue Klasa

Klasa adaptera kontenera szablonu, która zapewnia ograniczenie funkcjonalności ograniczające dostęp do najwyższego elementu podstawowego typu kontenera, który jest zawsze największym lub najwyższym priorytetem. Nowe elementy można dodać do elementu priority_queue , a górny element priority_queue elementu można sprawdzić lub usunąć.

Składnia

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

Parametry

Type
Typ danych elementu, który ma być przechowywany w obiekcie priority_queue.

Container
Typ kontenera bazowego używanego do implementowania elementu priority_queue.

Compare
Typ, który udostępnia obiekt funkcji, który może porównać dwie wartości elementu jako klucze sortowania, aby określić ich względną kolejność w obiekcie priority_queue. Ten argument jest opcjonalny, a predykat less<typename Container::value_type> binarny jest wartością domyślną.

Uwagi

Elementy klasy określone w pierwszym parametrze szablonu obiektu kolejki są synonimami value_type i muszą odpowiadać typowi elementu w podstawowej klasie Type Container kontenera określonej przez drugi parametr szablonu. Element Type musi być przypisywany, aby można było skopiować obiekty tego typu i przypisać wartości do zmiennych tego typu.

Kolejność priority_queue steruje sekwencją przez wywołanie przechowywanego obiektu funkcji klasy Traits. Ogólnie rzecz biorąc, elementy muszą być jedynie mniej niż porównywalne do ustalenia tej kolejności: tak aby, biorąc pod uwagę dwa elementy, można określić, że są one równoważne (w sensie, że ani nie jest mniejszy niż drugi) lub że jeden jest mniejszy niż drugi. Skutkuje to ustaleniem kolejności dla elementów nierównoważnych. Ze strony bardziej technicznej, funkcja porównywania jest predykatem binarnym, który wymusza ścisłe słabe porządkowanie w standardowym sensie matematycznym.

Odpowiednie bazowe klasy kontenerów obejmują priority_queue deque klasę i domyślny vector klasę lub dowolny inny kontener sekwencji, który obsługuje operacje front, push_backi pop_back iteratora dostępu losowego. Podstawowa klasa kontenera jest hermetyzowana w ramach adaptera kontenera, który uwidacznia tylko ograniczony zestaw funkcji składowych kontenera sekwencji jako interfejs publiczny.

Dodawanie elementów do obu elementów i usuwanie ich z priority_queue obu elementów ma złożoność logarytmiczna. Uzyskiwanie dostępu do elementów w obiekcie ma stałą priority_queue złożoność.

Istnieją trzy typy adapterów kontenerów zdefiniowanych przez standardową bibliotekę języka C++: stack, queuei priority_queue. Każda z nich ogranicza funkcjonalność niektórych bazowych klas kontenerów w celu zapewnienia precyzyjnie kontrolowanego interfejsu standardowej struktury danych.

• Klasa stack obsługuje strukturę danych liFO (last-in, last-in, first-out). Dobry analog do myślenia byłby stos płyt. Elementy (płyty) mogą być wstawiane, sprawdzane lub usuwane tylko z góry stosu, który jest ostatnim elementem na końcu kontenera podstawowego. Ograniczenie dostępu tylko do górnego elementu jest powodem używania stack klasy.

• Klasa queue obsługuje strukturę danych first-in, first-out (FIFO). Dobry analog do myślenia byłoby ludzie w kolejce do kasjera bankowego. Elementy (osoby) można dodać z tyłu wiersza i są usuwane z przodu linii. Zarówno z przodu, jak i z tyłu linii mogą być sprawdzane. Ograniczenie dostępu tylko do elementów przednich i tylnych w ten sposób jest powodem używania queue klasy.

• Klasa priority_queue porządkuje elementy tak, aby największy element był zawsze na najwyższym miejscu. Obsługuje on wstawianie elementu oraz inspekcję i usuwanie górnego elementu. Dobry analogia, aby pamiętać, byłoby ludzi w kolejce, gdzie są ułożone według wieku, wzrostu lub innego kryterium.

Konstruktory

Konstruktor	opis
priority_queue	Tworzy obiekt priority_queue , który jest pusty lub jest kopią zakresu podstawowego obiektu kontenera lub innego priority_queueobiektu .

Typedefs

Nazwa typu	opis
container_type	Typ, który zapewnia kontener podstawowy do dostosowania przez element priority_queue.
size_type	Niepodpisany typ liczb całkowitych, który może reprezentować liczbę elementów w obiekcie priority_queue.
value_type	Typ reprezentujący typ obiektu przechowywanego jako element w obiekcie priority_queue.

Funkcje składowe

Funkcja składowa	opis
empty	Sprawdza, czy element priority_queue jest pusty.
pop	Usuwa największy element elementu priority_queue z górnej pozycji.
push	Dodaje element do kolejki priorytetów na podstawie priorytetu elementu z klasy operator<.
size	Zwraca liczbę elementów w elem.priority_queue
top	Zwraca odwołanie const do największego elementu w górnej części .priority_queue

Wymagania

Nagłówek: <queue>

Przestrzeń nazw: std

priority_queue::container_type

Typ, który zapewnia kontener podstawowy do dostosowania.

typedef Container container_type;

Uwagi

Typ jest synonimem parametru Containerszablonu . Klasa deque kontenera sekwencji biblioteki standardowej języka C++ i domyślna klasa vector spełniają wymagania, które mają być używane jako kontener podstawowy dla priority_queue obiektu. Typy zdefiniowane przez użytkownika spełniające wymagania mogą być również używane.

Aby uzyskać więcej informacji na temat Container, zobacz sekcję priority_queue Uwagi w temacie Klasa .

Przykład

Zobacz przykład, aby zapoznać się z przykładem priority_queue sposobu deklarowania i używania elementu container_type.

priority_queue::empty

Sprawdza, czy element priority_queue jest pusty.

bool empty() const;

Wartość zwracana

true jeśli wartość jest pusta priority_queue ; false jeśli wartość jest pusta priority_queue .

Przykład

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

Usuwa największy element elementu priority_queue z górnej pozycji.

void pop();

Uwagi

Aby priority_queue zastosować funkcję składową, musi być nieistniena. Górna część elementu priority_queue jest zawsze zajmowana przez największy element w kontenerze.

Przykład

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

Tworzy obiekt priority_queue , który jest pusty lub jest kopią zakresu podstawowego obiektu kontenera lub innego priority_queueobiektu .

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);

Parametry

_comp
Funkcja porównania typu constTraits używana do porządkowenia elementów w priority_queueobiekcie , która domyślnie porównuje funkcję kontenera podstawowego.

_Cont
Podstawowy kontener, którego skonstruowany priority_queue ma być kopią.

right
Element priority_queue , z którego skonstruowany zestaw ma być kopią.

first
Położenie pierwszego elementu w zakresie elementów do skopiowania.

last
Położenie pierwszego elementu poza zakresem elementów do skopiowania.

Uwagi

Każdy z pierwszych trzech konstruktorów określa pusty początkowy , priority_queuedrugi określa również typ funkcji porównania (comp) do użycia w ustaleniu kolejności elementów, a trzeci jawnie określając container_type (_Cont) do użycia. Słowo kluczowe explicit pomija niektóre rodzaje automatycznej konwersji typów.

Czwarty konstruktor określa kopię elementu priority_queue right.

Ostatnie trzy konstruktory kopiują zakres [first, last) niektórych kontenerów i używają wartości, aby zainicjować priority_queue element z rosnącą jawnością w określaniu typu funkcji porównania klasy Traits i container_type.

Przykład

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

Dodaje element do kolejki priorytetów na podstawie priorytetu elementu z klasy operator<.

void push(const Type& val);

Parametry

val
Element dodany w górnej części elementu priority_queue.

Uwagi

Górna część elementu priority_queue to pozycja zajmowana przez największy element w kontenerze.

Przykład

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

Zwraca liczbę elementów w elem.priority_queue

size_type size() const;

Wartość zwracana

Bieżąca długość obiektu priority_queue.

Przykład

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

Niepodpisany typ liczb całkowitych, który może reprezentować liczbę elementów w obiekcie priority_queue.

typedef typename Container::size_type size_type;

Uwagi

Typ jest synonimem size_type kontenera podstawowego dostosowanego przez element priority_queue.

Przykład

Zobacz przykład, aby zapoznać się z przykładem size sposobu deklarowania i używania elementu size_type.

priority_queue::top

Zwraca odwołanie const do największego elementu w górnej części .priority_queue

const_reference top() const;

Wartość zwracana

Odwołanie do największego elementu określonego Traits przez funkcję obiektu priority_queue.

Uwagi

Aby priority_queue zastosować funkcję składową, musi być nieistniena.

Przykład

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

Typ reprezentujący typ obiektu przechowywanego jako element w obiekcie priority_queue.

typedef typename Container::value_type value_type;

Uwagi

Typ jest synonimem value_type kontenera podstawowego dostosowanego przez element priority_queue.

Przykład

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

Zobacz też

Bezpieczeństwo wątku w standardowej bibliotece C++
Dokumentacja standardowej biblioteki C++