Usa la coda di priorità STL in C++

1. Usa std::priority_queue per dichiarare una coda prioritaria in C++
2. Usa l’argomento del modello per specificare la funzione di ordinamento in C++
3. Usa il comparatore personalizzato per specificare l’ordinamento degli elementi in C++

Questo articolo dimostrerà più metodi su come utilizzare la coda di priorità STL in C++.

Usa std::priority_queue per dichiarare una coda prioritaria in C++

La classe std::priority_queue è un adattatore contenitore che implementa una coda da cui vengono letti gli elementi in base alla loro priorità. Nota che priority_queue può utilizzare qualsiasi contenitore di sequenza internamente per gli elementi e l’utente può passare quello preferito come secondo parametro del modello. Se quest’ultimo parametro non è specificato, per impostazione predefinita viene utilizzato il contenitore vector.

Gli elementi di priority_queue vengono manipolati utilizzando le stesse funzioni del contenitore queue. La funzione membro push inserisce un nuovo elemento nella coda e la funzione top per accedere all’elemento superiore. Queste due funzioni sono utilizzate nella funzione printQueue per inviare elementi al flusso 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;
}

Produzione:

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

Usa l’argomento del modello per specificare la funzione di ordinamento in C++

La priorità per ogni elemento è determinata utilizzando la funzione di confronto che l’utente può specificare facoltativamente. In caso contrario, per impostazione predefinita viene scelto l’ordine decrescente. Possiamo costruire la priority_queue dal codice di esempio precedente in ordine inverso utilizzando l’oggetto funzione std::greater come terzo parametro del modello. Si noti che un nuovo contenitore di coda viene inizializzato utilizzando il costruttore basato sull’intervallo.

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

Produzione:

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

Usa il comparatore personalizzato per specificare l’ordinamento degli elementi in C++

Per prima cosa, definiamo un vettore di stringhe utilizzato per inizializzare una priority_queue. Successivamente, viene definita un’espressione lambda per formare la funzione comparatore. Quest’ultimo confronta due stringhe in base alla lunghezza. Ora possiamo dichiarare un oggetto priority_queue con tre parametri di template che specificano rispettivamente il tipo di elemento, il tipo di contenitore sottostante e la funzione comparatore. Il costruttore basato sull’intervallo viene utilizzato per inizializzare il contenuto della coda.

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

Produzione:

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