Usar la cola de prioridad STL en C++

Jinku Hu 12 octubre 2023
  1. Utilice std::priority_queue para declarar una cola de prioridad en C++
  2. Utilice el argumento de plantilla para especificar la función de ordenación en C++
  3. Utilice el comparador personalizado para especificar el orden de los elementos en C++
Usar la cola de prioridad STL en C++

Este artículo mostrará varios métodos sobre cómo utilizar la cola de prioridad STL en C++.

Utilice std::priority_queue para declarar una cola de prioridad en C++

La clase std::priority_queue es un adaptador de contenedor que implementa una cola desde la que se leen los elementos según su prioridad. Tenga en cuenta que priority_queue puede utilizar cualquier contenedor de secuencia internamente para los elementos, y el usuario puede pasar el preferido como segundo parámetro de plantilla. Si no se especifica este último parámetro, el contenedor vector se utiliza por defecto.

Los elementos de priority_queue se manipulan utilizando las mismas funciones que el contenedor queue. La función miembro push inserta un nuevo elemento en la cola y la función top para acceder al elemento superior. Estas dos funciones se utilizan en la función printQueue para enviar elementos al flujo 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;
}

Producción :

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

Utilice el argumento de plantilla para especificar la función de ordenación en C++

La prioridad de cada elemento se determina mediante la función de comparación que el usuario puede especificar opcionalmente. De lo contrario, se elige el orden descendente de forma predeterminada. Podemos construir el priority_queue a partir del código de ejemplo anterior en orden inverso usando el objeto de función std::greater como tercer parámetro de plantilla. Observe que se inicializa un nuevo contenedor de cola mediante el constructor basado en rangos.

#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;
}

Producción :

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

Utilice el comparador personalizado para especificar el orden de los elementos en C++

Al principio, definimos un vector de cadenas que se utilizan para inicializar una priority_queue. A continuación, se define una expresión lambda para formar la función comparadora. Este último compara dos cadenas por longitud. Ahora, podemos declarar un objeto priority_queue con tres parámetros de plantilla que especifican el tipo de elemento, el tipo de contenedor subyacente y la función de comparación, respectivamente. El constructor basado en rango se utiliza para inicializar el contenido de la cola.

#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;
}

Producción :

quisquam, dolorem, ipsum, porro, quia, qui, est,
Autor: Jinku Hu
Jinku Hu avatar Jinku Hu avatar

Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.

LinkedIn Facebook

Artículo relacionado - C++ Queue