priority_queue classe

Um adaptador de contentor que mantém uma coleção de elementos onde o elemento de maior (ou prioridade máxima) está sempre acessível no topo. Pode adicionar novos elementos e remover ou examinar o elemento superior, mas não pode aceder diretamente aos elementos do meio da coleção.

Sintaxe

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

Parâmetros

Type
O tipo de dado elemento a armazenar no priority_queue.

Container
O tipo do recipiente subjacente que armazena os elementos para o priority_queue.

Compare
O tipo que fornece um objeto de função que compara dois valores de elementos como chaves de ordenação para determinar a sua ordem relativa no priority_queue. Este argumento é opcional. O predicado less<typename Container::value_type> binário é o padrão.

Observações

Os elementos da classe Type especificados no primeiro parâmetro template de um priority_queue objeto são equivalentes e value_type devem corresponder ao tipo de elemento na classe Container de contentor subjacente especificada pelo segundo parâmetro template. Tem Type de ser atribuível, o que significa que podes copiar objetos desse tipo e atribuir valores a variáveis desse tipo.

Utiliza priority_queue uma função de comparação para determinar quais os elementos que têm maior prioridade. Esta função de comparação é um objeto de função da classe Traits. Para trabalhar com priority_queue, os seus elementos só precisam de suportar a comparação usando o operador menor que (<) para que possa organizar os elementos por ordem.

Pode alterar o tipo de contentor subjacente usado pelo priority_queue. Podes querer fazer isso por razões de desempenho. O padrão, vector, é geralmente o melhor para a localidade da cache porque os elementos são armazenados em armazenamento contíguo, e faz menos alocações à medida que cresce. Mas talvez consideres deque se tens filas muito grandes ou ilimitadas e se mover elementos é caro. Para mais informações sobre classes de contentores subjacentes adequadas, consulte container_type.

Adicionar e remover elementos de um priority_queue tem complexidade logarítmica. Aceder a elementos em tem priority_queue complexidade constante.

A C++ Standard Library define outros adaptadores de contentores que pode usar para armazenar os elementos nos seus priority_queue: stack, queue, e priority_queue:

• A stack Classe suporta uma estrutura de dados de último a entrar, primeiro a sair (LIFO). Considere uma pilha de placas: pode inserir, inspecionar ou remover elementos (placas) apenas do topo da pilha, que é o último elemento na extremidade do recipiente base.
• A queue Classe suporta uma estrutura de dados first-in, first-out (FIFO). Considere as pessoas em fila. Adiciona-se elementos (pessoas) ao final da fila e retira-se da frente da fila. Tanto a frente como o verso de uma linha podem ser inspecionados.
• A priority_queue classe ordena os seus elementos de modo a que o maior elemento esteja sempre no topo. Suporta a inserção de um elemento e a inspeção e remoção do elemento superior.

Examples

• Verifica se está priority_queue vazio
• Elementos de pop e verificar o tamanho da fila
• Use recipientes e comparadores personalizados
• Empurra os elementos e lê o topo
• Obtenha o número de elementos
• Aceder ao elemento superior
• Usa o pseudónimo priority_queue value_type
• Use um tipo de dado definido pelo utilizador

Construtores

Construtor	Description
priority_queue	Constrói um priority_queue que é vazio ou que é uma cópia de um intervalo de um objeto contentor base ou de outro priority_queue.

Typedefs (definições de tipos)

Nome do tipo	Description
container_type	Um tipo que fornece o recipiente base que adapta priority_queue .
size_type	Um tipo inteiro sem sinal que pode representar o número de elementos num priority_queue.
value_type	Um tipo que representa o tipo de objeto armazenado como elemento num priority_queue.

Funções de membro

Função de membro	Description
empty	Testa se está priority_queue vazio.
pop	Remove o maior elemento da priority_queue posição superior.
push	Adiciona um elemento à fila de prioridade com base na prioridade do elemento de operator<.
size	Devolve o número de elementos no priority_queue.
top	Devolve uma referência const ao maior elemento no topo do priority_queue.

Requerimentos

Cabeçalho:<queue>

Espaço de nomes:std

priority_queue::container_type

Um tipo que fornece o recipiente base a adaptar.

typedef Container container_type;

Observações

O tipo é um sinônimo para o parâmetro de modelo Container.

Classes de contentores subjacentes adequadas para priority_queue incluem deque Class, a Class padrãovector, ou qualquer outro contentor de sequência que suporte as operações de front, push_back, e pop_back um iterador de acesso aleatório. O adaptador de contentor encapsula a classe de contentor subjacente e expõe apenas um conjunto limitado das funções membros do contentor de sequência como interface pública.

Para um exemplo de como declarar e usar container_type, veja Usar contentores e comparadores personalizados

priority_queue::empty

Testa se a priority_queue está vazio.

bool empty() const;

Valor de retorno

true se o priority_queue for vazio; false se o priority_queue for não vazio.

Exemplo: Verifica se o priority_queue está vazio

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

Remove o maior elemento da priority_queue posição superior.

void pop();

Observações

O priority_queue deve ser não vazio para usar esta função elemento. O topo do recipiente priority_queue contém sempre o maior elemento do recipiente.

Exemplo: Elementos de pop e tamanho do cheque

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

Cria um priority_queue que está vazio ou que copia um intervalo de um objeto contentor base ou de outro 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);

Parâmetros

_comp
A função de comparação de tipo constTraits usada para ordenar os elementos no priority_queue, que por defeito é a função de comparação do contentor base.

_Cont
O recipiente base do qual o construído priority_queue deve ser uma cópia.

right
O priority_queue cujo conjunto construído deve ser uma cópia.

first
A posição do primeiro elemento no intervalo de elementos a copiar.

last
A posição do primeiro elemento para além do alcance dos elementos a copiar.

Observações

Cada um dos três primeiros construtores especifica uma inicial priority_queuevazia , o segundo também especifica o tipo de função de comparação (comp) a usar para estabelecer a ordem dos elementos e o terceiro especifica explicitamente o container_type (_Cont) a ser usado. A palavra-chave explicit suprime certos tipos de conversão automática de tipos.

O quarto construtor especifica uma cópia do priority_queue right.

Os três últimos construtores copiam o intervalo [first, last) de algum contentor e usam os valores para inicializar a priority_queue com uma explicitez crescente na especificação do tipo de função de comparação da classe Traits e container_type.

Exemplo: Usar contentores e comparadores personalizados

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

Adiciona um elemento à fila de prioridade com base na prioridade do elemento de operator<.

void push(const Type& val);

Parâmetros

val
O elemento a adicionar ao topo do priority_queue.

Observações

O topo do priority_queue contém o maior elemento do recipiente.

Exemplo: Empurrar elementos e ler o topo

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

Devolve o número de elementos no priority_queue.

size_type size() const;

Valor de retorno

O comprimento atual do priority_queue.

Exemplo: Obtenha o número de elementos no 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

Um tipo inteiro sem sinal que representa o número de elementos num priority_queue.

typedef typename Container::size_type size_type;

Observações

Este tipo é sinónimo do size_type recipiente base que o priority_queue adapta.

Exemplo: Aceder ao elemento superior

Para um exemplo de como declarar e usar size_type, veja Obter o número de elementos

priority_queue::top

Devolve uma referência const ao maior elemento no topo do priority_queue.

const_reference top() const;

Valor de retorno

Uma referência ao maior elemento, determinado pela Traits função, objeto do priority_queue.

Observações

O priority_queue deve ser não vazio para usar esta função elemento.

Exemplo: Obtenha o elemento superior do 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

Um tipo que representa o tipo de objeto armazenado como elemento num priority_queue.

typedef typename Container::value_type value_type;

Observações

Este tipo é sinónimo do value_type recipiente base que o priority_queue adapta.

Exemplo: Usa o falso 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.

Exemplo: Usar um tipo de dado definido pelo utilizador

Para usar priority_queue com elementos de tipo definidos pelo utilizador, deve fornecer uma forma de comparar os elementos. Pode definir operator< para o seu tipo ou fornecer um objeto de função de comparação personalizado.

O exemplo seguinte demonstra um priority_queue que armazena Task objetos, ordenados por nível de prioridade. As tarefas com valores de prioridade mais elevadas estão no topo da fila.

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

Observações

Se quiser uma ordem diferente (por exemplo, valores mais baixos primeiro), forneça um comparador personalizado:

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;

Consulte também

Segurança de threads na biblioteca padrão C++
Referência da biblioteca padrão do C++