Utiliser la file d'attente de priorité STL en C++

1. Utilisez std::priority_queue pour déclarer une file d’attente prioritaire en C++
2. Utiliser l’argument de modèle pour spécifier la fonction de tri en C++
3. Utilisez le comparateur personnalisé pour spécifier l’ordre des éléments en C++

Cet article présente plusieurs méthodes sur l’utilisation de la file d’attente prioritaire STL en C++.

Utilisez std::priority_queue pour déclarer une file d’attente prioritaire en C++

La classe std::priority_queue est un adaptateur de conteneur qui implémente une file d’attente à partir de laquelle les éléments sont lus en fonction de leur priorité. Notez que priority_queue peut utiliser n’importe quel conteneur de séquence en interne pour les éléments, et l’utilisateur peut passer celui qu’il préfère comme deuxième paramètre de modèle. Si ce dernier paramètre n’est pas précisé, le conteneur vector est utilisé par défaut.

Les éléments de priority_queue sont manipulés en utilisant les mêmes fonctions que le conteneur queue. La fonction membre push insère un nouvel élément dans la file d’attente et la fonction top pour accéder à l’élément supérieur. Ces deux fonctions sont utilisées dans la fonction printQueue pour sortir des éléments vers le flux 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;
}

Production:

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

Utiliser l’argument de modèle pour spécifier la fonction de tri en C++

La priorité de chaque élément est déterminée à l’aide de la fonction de comparaison que l’utilisateur peut éventuellement spécifier. Sinon, l’ordre décroissant est choisi par défaut. Nous pouvons construire le priority_queue à partir de l’exemple de code précédent dans l’ordre inverse en utilisant l’objet de fonction std::greater comme troisième paramètre de modèle. Notez qu’un nouveau conteneur de file d’attente est initialisé à l’aide du constructeur basé sur la plage.

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

Production:

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

Utilisez le comparateur personnalisé pour spécifier l’ordre des éléments en C++

Dans un premier temps, nous définissons un vector de chaînes utilisé pour initialiser une priority_queue. Ensuite, une expression lambda est définie pour former la fonction de comparaison. Ce dernier compare deux chaînes par longueur. Maintenant, nous pouvons déclarer un objet priority_queue avec trois paramètres de modèle spécifiant respectivement le type d’élément, le type de conteneur sous-jacent et la fonction de comparaison. Le constructeur basé sur la plage est utilisé pour initialiser le contenu de la file d’attente.

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

Production:

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