Use a fila de prioridade STL em C++

1. Use std::priority_queue para declarar uma fila prioritária em C++
2. Use o argumento do modelo para especificar a função de pedido em C++
3. Use o comparador personalizado para especificar a ordem dos elementos em C++

Este artigo demonstrará vários métodos sobre como usar a fila de prioridade STL em C++.

Use std::priority_queue para declarar uma fila prioritária em C++

A classe std::priority_queue é um adaptador de contêiner que implementa uma fila da qual os elementos são lidos de acordo com sua prioridade. Observe que priority_queue pode utilizar qualquer contêiner de sequência internamente para elementos, e o usuário pode passar o preferido como o segundo parâmetro do modelo. Se o último parâmetro não for especificado, o contêiner vetor é usado por padrão.

Os elementos de priority_queue são manipulados usando as mesmas funções do contêiner queue. A função de membro push insere um novo elemento na fila e a função top para acessar o elemento superior. Essas duas funções são utilizadas na função printQueue para enviar elementos para o fluxo cout.

#include <iostream>
#include <queue>

using std::cout;
using std::endl;
using std::priority_queue;
using std::string;
using std::vector;

template <typename Queue>
void printQueue(Queue& q) {
  while (!q.empty()) {
    cout << q.top() << ", ";
    q.pop();
  }
  cout << endl;
}

int main() {
  std::priority_queue<int> q1;
  vector vec1 = {1, 8, 5, 6, 3, 7};

  for (int n : vec1) q1.push(n);

  printQueue(q1);

  return EXIT_SUCCESS;
}

Resultado:

8, 7, 6, 5, 3, 1,

Use o argumento do modelo para especificar a função de pedido em C++

A prioridade de cada elemento é determinada usando a função de comparação que o usuário pode especificar opcionalmente. Caso contrário, a ordem decrescente é escolhida por padrão. Podemos construir a priority_queue a partir do código de exemplo anterior em ordem reversa usando o objeto de função std::greater como o terceiro parâmetro do modelo. Observe que um novo contêiner de fila é inicializado usando o construtor baseado em intervalo.

#include <iostream>
#include <queue>

using std::cout;
using std::endl;
using std::priority_queue;
using std::string;
using std::vector;

template <typename Queue>
void printQueue(Queue& q) {
  while (!q.empty()) {
    cout << q.top() << ", ";
    q.pop();
  }
  cout << endl;
}

int main() {
  std::priority_queue<int> q1;
  vector vec1 = {1, 8, 5, 6, 3, 7};

  std::priority_queue<int, vector<int>, std::greater<>> q2(vec1.begin(),
                                                           vec1.end());
  printQueue(q2);

  return EXIT_SUCCESS;
}

Resultado:

1, 3, 5, 6, 7, 8,

Use o comparador personalizado para especificar a ordem dos elementos em C++

Em primeiro lugar, definimos um vector de strings usadas para inicializar uma priority_queue. A seguir, uma expressão lambda é definida para formar a função comparadora. O último compara duas cordas por comprimento. Agora, podemos declarar um objeto priority_queue com três parâmetros de modelo especificando o tipo de elemento, o tipo de contêiner subjacente e a função de comparação, respectivamente. O construtor baseado em intervalo é utilizado para inicializar o conteúdo da fila.

#include <iostream>
#include <queue>

using std::cout;
using std::endl;
using std::priority_queue;
using std::string;
using std::vector;

template <typename Queue>
void printQueue(Queue& q) {
  while (!q.empty()) {
    cout << q.top() << ", ";
    q.pop();
  }
  cout << endl;
}

int main() {
  vector vec2 = {"porro", "quisquam", "est", "qui", "dolorem", "ipsum", "quia"};
  auto compFunc = [](const string& s1, const string& s2) {
    return s1.length() < s2.length();
  };

  std::priority_queue<string, vector<string>, decltype(compFunc)> q3(
      vec2.begin(), vec2.end(), compFunc);

  printQueue(q3);

  return EXIT_SUCCESS;
}

Resultado:

quisquam, dolorem, ipsum, porro, quia, qui, est,