Condividi tramite

Classe priority_queue

Adattatore di contenitori che gestisce una raccolta di elementi in cui l'elemento più grande (o con priorità più alta) è sempre accessibile nella parte superiore. È possibile aggiungere nuovi elementi e rimuovere o esaminare l'elemento superiore, ma non è possibile accedere direttamente agli elementi al centro della raccolta.

Sintassi

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

Parametri

Type
Tipo di dati dell'elemento priority_queueda archiviare in .

Container
Tipo del contenitore sottostante che archivia gli elementi per l'oggetto priority_queue.

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

Osservazioni:

Gli elementi della classe Type specificati nel primo parametro modello di un priority_queue oggetto sono equivalenti a value_type e devono corrispondere al tipo di elemento nella classe Container contenitore sottostante specificata dal secondo parametro di modello. Deve Type essere assegnabile, il che significa che è possibile copiare oggetti di tale tipo e assegnare valori alle variabili di tale tipo.

priority_queue usa una funzione di confronto per determinare quali elementi hanno priorità più alta. Questa funzione di confronto è un oggetto funzione della classe Traits. Per usare priority_queue, gli elementi devono supportare solo il confronto usando l'operatore less-than () in< modo che possa disporre gli elementi in ordine.

È possibile modificare il tipo di contenitore sottostante usato da priority_queue. È possibile eseguire questa operazione per motivi di prestazioni. L'impostazione predefinita, vector, è in genere ottimale per la località della cache perché gli elementi vengono archiviati in un archivio contiguo e comporta un minor numero di allocazioni man mano che aumenta. Tuttavia, è consigliabile prendere in considerazione deque se sono presenti code molto grandi o non associate e gli elementi mobili sono costosi. Per altre informazioni sulle classi di contenitori sottostanti appropriate, vedere container_type.

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

La libreria standard C++ definisce altri adattatori di contenitori che è possibile usare per archiviare gli elementi in priority_queue: stack, queuee priority_queue:

  • La stack classe supporta una struttura di dati LIFO (Last-In, First-Out). Si consideri uno stack di lastre: è possibile inserire, ispezionare o rimuovere elementi (lastre) solo dalla parte superiore dello stack, che è l'ultimo elemento alla fine del contenitore di base.
  • La queue classe supporta una struttura di dati FIFO (First-In First-In, First-Out). Si considerino le persone in una riga. Aggiungere elementi (persone) alla parte posteriore della riga e rimuoverli dalla parte anteriore della riga. Sia la parte anteriore che la parte posteriore di una linea possono essere ispezionate.
  • La priority_queue classe ordina i relativi elementi in modo che l'elemento più grande sia sempre nella parte superiore. Supporta l'inserimento di un elemento e l'ispezione e la rimozione del primo elemento.

Esempi

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 adattato dall'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.

Classi contenitore sottostanti adatte per priority_queue includere deque Classe, Classe predefinita vectoro qualsiasi altro contenitore di sequenza che supporta le operazioni di front, push_backe e pop_back un iteratore ad accesso casuale. L'adattatore del contenitore incapsula la classe contenitore sottostante ed espone solo un set limitato di funzioni membro del contenitore sequenza come interfaccia pubblica.

Per un esempio di come dichiarare e usare container_type, vedere Usare contenitori e comparer personalizzati

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: Controllare se è priority_queue vuoto

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

L'oggetto priority_queue deve essere nonempty per utilizzare questa funzione membro. La parte superiore dell'oggetto priority_queue contiene sempre l'elemento più grande nel contenitore.

Esempio: Elementi Pop e dimensioni check

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

Crea un oggetto priority_queue vuoto o che copia un intervallo da un oggetto contenitore di base o da 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: Usare contenitori e comparer personalizzati

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

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

void push(const Type& val);

Parametri

val
Elemento da aggiungere all'inizio dell'oggetto priority_queue.

Osservazioni:

La parte superiore di priority_queue contiene l'elemento più grande nel contenitore.

Esempio: Eseguire il push degli elementi e leggere la parte superiore

// 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: ottenere il numero di elementi nell'oggetto 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

Tipo integer senza segno che rappresenta il numero di elementi in un oggetto priority_queue.

typedef typename Container::size_type size_type;

Osservazioni:

Questo tipo è un sinonimo size_type del contenitore di base adattato dall'oggetto priority_queue .

Esempio: Accedere all'elemento principale

Per un esempio di come dichiarare e usare size_type, vedere Ottenere il numero di elementi

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:

L'oggetto priority_queue deve essere nonempty per utilizzare questa funzione membro.

Esempio: Ottenere l'elemento principale dell'oggetto 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

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

typedef typename Container::value_type value_type;

Osservazioni:

Questo tipo è un sinonimo value_type del contenitore di base adattato dall'oggetto priority_queue .

Esempio: usare l'alias priority_queue value_type

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

Esempio: Usare un tipo di dati definito dall'utente

Per usare priority_queue con elementi di tipo definiti dall'utente, è necessario fornire un modo per confrontare gli elementi. È possibile definire operator< per il tipo o fornire un oggetto funzione di confronto personalizzato.

Nell'esempio seguente viene illustrato un priority_queue oggetto che archivia Task gli oggetti, ordinati in base al livello di priorità. Le attività con valori di priorità più alta si trovano nella parte superiore della coda.

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

Osservazioni:

Se si desidera un ordinamento diverso (ad esempio, valori inferiori per primi), specificare un confronto personalizzato:

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;

Vedi anche

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

  • Last updated on