Condividi tramite

Classe priority_queue

  • Articolo

Classe di adattatori di contenitori di modelli che fornisce una restrizione di funzionalità, limitando l'accesso all'elemento iniziale di un tipo di contenitore sottostante, che è sempre il più grande o quello con la priorità più elevata. È possibile aggiungere nuovi elementi all'oggetto priority_queue e l'elemento superiore di priority_queue può essere ispezionato o rimosso.

Sintassi

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

Parametri

Type
Tipo di dati degli elementi da archiviare in priority_queue.

Container
Tipo del contenitore sottostante utilizzato per implementare .priority_queue

Compare
Tipo che fornisce un oggetto funzione in grado di confrontare due valori di elemento come chiavi di ordinamento per determinare il relativo ordine nell'oggetto priority_queue. Questo argomento è facoltativo e il predicato binario less<typename Container::value_type> rappresenta il valore predefinito.

Osservazioni:

Gli elementi della classe Type stipulati nel primo parametro modello di un oggetto queue sono sinonimi value_type e devono corrispondere al tipo di elemento nella classe Container contenitore sottostante stipulato dal secondo parametro di modello. Deve Type essere assegnabile, in modo che sia possibile copiare oggetti di tale tipo e assegnare valori alle variabili di tale tipo.

Ordina priority_queue la sequenza che controlla chiamando un oggetto funzione archiviato della classe Traits. In generale, gli elementi devono essere semplicemente meno di paragonabili per stabilire questo ordine: in modo che, dato qualsiasi due elementi, possa essere determinato che sono equivalenti (nel senso che nessuno è minore dell'altro) o che uno è minore dell'altro. Di conseguenza, l'ordinamento viene eseguito tra gli elementi non equivalenti. A un livello più tecnico, la funzione di confronto è un predicato binario che provoca un ordinamento di tipo "strict weak" nel senso matematico standard.

Classi contenitore sottostanti adatte per priority_queue includere deque Classe e classe predefinita vector o qualsiasi altro contenitore di sequenza che supporta le operazioni di front, push_backe e pop_back un iteratore ad accesso casuale. La classe del contenitore sottostante è incapsulata nell'adattatore di contenitori, che espone solo il set limitato di funzioni membro dei contenitori di sequenza come interfaccia pubblica.

L'aggiunta di elementi e la rimozione di elementi da una priority_queue hanno complessità logaritmica. L'accesso agli elementi in una priority_queue ha una complessità costante.

Esistono tre tipi di adattatori di contenitori definiti dalla libreria standard C++: stack, queuee priority_queue. Ognuno di essi limita la funzionalità di una classe contenitore sottostante per fornire un'interfaccia controllata con precisione a una struttura di dati standard.

  • La stack classe supporta una struttura di dati LIFO (Last-In, First-Out). Una buona analogia è costituita da una pila di piatti. Gli elementi (piatti) possono essere inseriti, ispezionati o rimossi solo dalla cima della pila/stack, ovvero l'ultimo elemento alla fine del contenitore di base. La restrizione per accedere solo all'elemento principale è il motivo dell'uso della stack classe .

  • La queue classe supporta una struttura di dati FIFO (First-In First-In, First-Out). Una buona analogia è costituita da persone in coda davanti allo sportello di una banca. Gli elementi (persone) possono essere aggiunti alla fine della fila e vengono rimossi dalla parte iniziale della fila. È possibile ispezionare sia l'inizio che la fine della fila. La restrizione per accedere solo agli elementi front-end e back in questo modo è il motivo dell'uso della queue classe .

  • La priority_queue classe ordina i relativi elementi in modo che l'elemento più grande sia sempre nella posizione superiore. Supporta l'inserimento di un elemento e l'ispezione e la rimozione del primo elemento. Una buona analogia da tenere a mente sarebbe la gente che si allinea dove sono disposti per età, altezza o altri criteri.

Costruttori

Costruttore Descrizione
priority_queue Costruisce una priority_queue vuota o che rappresenta una copia di un intervallo di un oggetto contenitore di base o di un'altra priority_queue.

Typedef

Nome tipo Descrizione
container_type Tipo che fornisce il contenitore di base che deve essere adattato da un oggetto priority_queue.
size_type Tipo Unsigned Integer in grado di rappresentare il numero di elementi di un priority_queue.
value_type Tipo che rappresenta il tipo di oggetto archiviato come elemento in priority_queue.

Funzioni membro

Funzione membro Descrizione
empty Verifica se priority_queue è vuoto.
pop Rimuove l'elemento più grande dalla posizione iniziale della priority_queue.
push Aggiunge un elemento alla coda di priorità in base alla priorità dell'elemento da operator<.
size Restituisce il numero di elementi nel priority_queue.
top Restituisce un riferimento const all'elemento più grande all'inizio della priority_queue.

Requisiti

Intestazione: <queue>

Spazio dei nomi: std

priority_queue::container_type

Tipo che fornisce il contenitore di base da adattare.

typedef Container container_type;

Osservazioni:

Il tipo è un sinonimo del parametro di modello Container. La classe deque contenitore della sequenza della libreria standard C++ e la classe vector predefinita soddisfano i requisiti da usare come contenitore di base per un priority_queue oggetto . È anche possibile usare tipi definiti dall'utente che soddisfano i requisiti.

Per altre informazioni su Container, vedere la sezione Osservazioni dell'argomento priority_queue Classe .

Esempio

Vedere l'esempio per priority_queue un esempio di come dichiarare e usare container_type.

priority_queue::empty

Verifica se un priority_queue è vuoto.

bool empty() const;

Valore restituito

true se l'oggetto priority_queue è vuoto; false se l'oggetto priority_queue è non vuoto.

Esempio

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

Rimuove l'elemento più grande dalla posizione iniziale della priority_queue.

void pop();

Osservazioni:

Deve priority_queue essere nonempty per applicare la funzione membro. La parte superiore di priority_queue è sempre occupata dall'elemento più grande nel contenitore.

Esempio

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

Costruisce un oggetto priority_queue vuoto o che è una copia di un intervallo di un oggetto contenitore di base o di un altro priority_queueoggetto .

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

Parametri

_comp
Funzione di confronto di tipo constTraits utilizzata per ordinare gli elementi in priority_queue, che per impostazione predefinita confronta la funzione del contenitore di base.

_Cont
Contenitore di base di cui l'oggetto costruito priority_queue deve essere una copia.

right
Oggetto priority_queue del quale il set costruito deve essere una copia.

first
Posizione del primo elemento nell'intervallo di elementi da copiare.

last
Posizione del primo elemento oltre l'intervallo di elementi da copiare.

Osservazioni:

Ognuno dei primi tre costruttori specifica un oggetto iniziale priority_queuevuoto, il secondo specifica anche il tipo di funzione di confronto (comp) da utilizzare per stabilire l'ordine degli elementi e il terzo specificando in modo esplicito (container_type_Cont) da utilizzare. La parola chiave explicit elimina alcuni tipi di conversione automatica del tipo.

Il quarto costruttore specifica una copia dell'oggetto priority_queue right.

Gli ultimi tre costruttori copiano l'intervallo [first, last) di alcuni contenitori e usano i valori per inizializzare un priority_queue oggetto con maggiore esplicitità specificando il tipo di funzione di confronto della classe Traits e container_type.

Esempio

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

Aggiunge un elemento alla coda di priorità in base alla priorità dell'elemento da operator<.

void push(const Type& val);

Parametri

val
Elemento aggiunto all'inizio dell'oggetto priority_queue.

Osservazioni:

La parte superiore di priority_queue è la posizione occupata dall'elemento più grande nel contenitore.

Esempio

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

Restituisce il numero di elementi nel priority_queue.

size_type size() const;

Valore restituito

Lunghezza corrente dell'oggetto priority_queue.

Esempio

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

Tipo Unsigned Integer in grado di rappresentare il numero di elementi di un priority_queue.

typedef typename Container::size_type size_type;

Osservazioni:

Il tipo è un sinonimo size_type del contenitore di base adattato da priority_queue.

Esempio

Vedere l'esempio per size un esempio di come dichiarare e usare size_type.

priority_queue::top

Restituisce un riferimento const all'elemento più grande all'inizio della priority_queue.

const_reference top() const;

Valore restituito

Riferimento all'elemento più grande, come determinato dalla Traits funzione , oggetto dell'oggetto priority_queue.

Osservazioni:

Deve priority_queue essere nonempty per applicare la funzione membro.

Esempio

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

Tipo che rappresenta il tipo di oggetto archiviato come elemento in priority_queue.

typedef typename Container::value_type value_type;

Osservazioni:

Il tipo è un sinonimo value_type del contenitore di base adattato da priority_queue.

Esempio

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

Vedi anche

Thread Safety in the C++ Standard Library (Sicurezza dei thread nella libreria standard C++)
Informazioni di riferimento per la libreria standard C++