Compartilhar via

Classe priority_queue

Um adaptador de contêiner que mantém uma coleção de elementos em que o maior elemento (ou a prioridade mais alta) está sempre acessível na parte superior. Você pode adicionar novos elementos e remover ou examinar o elemento superior, mas não pode acessar diretamente elementos no 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 dados do priority_queueelemento a ser armazenado no .

Container
O tipo do contêiner subjacente que armazena os elementos para o priority_queue.

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

Comentários

Elementos de classe Type especificados no primeiro parâmetro de modelo de um priority_queue objeto são equivalentes value_type e devem corresponder ao tipo de elemento na classe Container de contêiner subjacente especificada pelo segundo parâmetro de modelo. O Type deve ser atribuível, o que significa que você pode copiar objetos desse tipo e atribuir valores a variáveis desse tipo.

O priority_queue usa uma função de comparação para determinar quais elementos têm prioridade mais alta. Essa função de comparação é um objeto de função da classe Traits. Para trabalhar, priority_queueseus elementos só precisam dar suporte à comparação usando o operador menor que (<) para que ele possa organizar os elementos em ordem.

Você pode alterar o tipo de contêiner subjacente usado pelo priority_queue. Talvez você queira fazer isso por motivos de desempenho. O padrão, geralmente, vectoré melhor para a localidade do cache porque os elementos são armazenados no armazenamento contíguo e fazem menos alocações à medida que ele cresce. Mas talvez você considere deque se você tem filas muito grandes ou não associados e mover elementos é caro. Para obter mais informações sobre classes de contêiner subjacentes adequadas, consulte container_type.

Adicionar e remover elementos de ambos priority_queue tem complexidade logarítmica. Acessar elementos em um priority_queue apresenta uma complexidade constante.

A Biblioteca Padrão do C++ define outros adaptadores de contêiner que você pode usar para armazenar os elementos em : priority_queuestack, queuee priority_queue:

  • A classe stackdá suporte a uma estrutura de dados UEPS (último a entrar, primeiro a sair). Considere uma pilha de placas: você pode inserir, inspecionar ou remover elementos (placas) somente da parte superior da pilha, que é o último elemento no final do contêiner base.
  • A Classe queuedá suporte a uma estrutura de dados PEPS (primeiro a entrar, primeiro a sair). Considere as pessoas em uma linha. Adicione elementos (pessoas) à parte de trás da linha e remova-os da frente da linha. Tanto a frente quanto a parte de trás de uma linha podem ser inspecionadas.
  • A priority_queue classe ordena seus elementos para que o maior elemento esteja sempre na parte superior. Ele dá suporte à inserção de um elemento e a inspeção e remoção do elemento superior.

Exemplos

Construtores

Construtor Descrição
priority_queue Constrói um priority_queue que é vazio ou que é uma cópia de um intervalo de um objeto de contêiner base ou de outro priority_queue.

Typedefs

Nome do tipo Descrição
container_type Um tipo que fornece o contêiner base que o priority_queue adapta.
size_type Um tipo de inteiro sem sinal que pode representar o número de elementos em um priority_queue.
value_type Um tipo que representa o tipo de objeto armazenado como um elemento em um priority_queue.

Funções de membro

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

Requisitos

Cabeçalho: <queue>

Namespace: std

priority_queue::container_type

Um tipo que fornece o contêiner base a ser adaptado.

typedef Container container_type;

Comentários

O tipo é um sinônimo do parâmetro de modeloContainer.

Classes de contêiner subjacentes adequadas para priority_queue incluir deque Classe, classe padrão vectorou qualquer outro contêiner de sequência que dê suporte às operações de front, push_backe pop_back um iterador de acesso aleatório. O adaptador de contêiner encapsula a classe de contêiner subjacente e expõe apenas um conjunto limitado das funções de membro do contêiner de sequência como uma interface pública.

Para obter um exemplo de como declarar e usar container_type, consulte Usar contêineres e comparadores personalizados

priority_queue::empty

Testa se priority_queue está vazio.

bool empty() const;

Valor de retorno

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

Exemplo: verificar se a opção priority_queue está vazia

// 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 de priority_queue da posição superior.

void pop();

Comentários

Não priority_queue é necessário usar essa função de membro. A parte superior do priority_queue sempre contém o maior elemento no contêiner.

Exemplo: elementos pop e tamanho da verificação

// 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 de contêiner 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 do tipo constTraits usado para ordenar os elementos no priority_queue, cujo padrão é a função de comparação do contêiner base.

_Cont
O contêiner do qual o priority_queue construído será uma cópia.

right
O priority_queue do qual o conjunto criado é uma cópia.

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

last
A posição do primeiro elemento além do intervalo de elementos a serem copiados.

Comentários

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

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

Os últimos três construtores copiam o intervalo [first, last) de um contêiner e use os valores para inicializar um priority_queue vez mais explícito ao especificar o tipo de função de comparação da classe Traits econtainer_type.

Exemplo: usar contêineres 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 ser adicionado à parte superior do priority_queue.

Comentários

A parte superior do priority_queue contém o maior elemento no contêiner.

Exemplo: efetuar push de elementos e ler a parte superior

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

Retorna o número de elementos no priority_queue.

size_type size() const;

Valor de retorno

O comprimento atual do priority_queue.

Exemplo: obter 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 em um priority_queue.

typedef typename Container::size_type size_type;

Comentários

Esse tipo é um sinônimo do size_type contêiner base que o priority_queue adapta.

Exemplo: acessar o elemento superior

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

priority_queue::top

Retorna uma referência const ao maior elemento na parte superior de priority_queue.

const_reference top() const;

Valor de retorno

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

Comentários

Não priority_queue é necessário usar essa função de membro.

Exemplo: obter 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 um elemento em um priority_queue.

typedef typename Container::value_type value_type;

Comentários

Esse tipo é um sinônimo do value_type contêiner base que o priority_queue adapta.

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

Exemplo: usar um tipo de dados definido pelo usuário

Para usar priority_queue com elementos de tipo definidos pelo usuário, você deve fornecer uma maneira de comparar os elementos. Você pode definir operator< para seu tipo ou fornecer um objeto de função de comparação personalizado.

O exemplo a seguir demonstra um priority_queue que armazena Task objetos, ordenados por nível de prioridade. Tarefas com valores de prioridade mais altos estão na parte superior 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

Comentários

Se você quiser ordenação 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;

Confira também

Acesso Thread-Safe na Biblioteca Padrão C++
Referência da biblioteca padrão C++

  • Last updated on