Conteneurs de séquence - priority_queue

priority_queue

Il s’agit cette fois de files d’attente à priorité. Elles fonctionnent comme une file normale, mais leurs éléments sont automatiquement rangés par ordre de priorité. C’est l’utilisateur de la classe qui définit son opérateur de comparaison pour établir la priorité des éléments.
Pour implémenter une file d’attente à priorité, vous devez inclure le fichier en-tête <queue> au début du programme et travailler dans l’espace de noms std.

À savoir

Dans ce type de file, vous pouvez mettre des int, des double, ou des données d’un type personnalisé. Dans le cas des int et double, l’ordinateur saura comparer tout seul et savoir lequel est le plus grand.
Dans le cas des types personnalisés, il FAUT préciser à l’ordinateur comment déterminer la plus grande entre deux instances de classe stockées dans la file.
Pour cela, deux méthodes :
Vous surchargez l’opérateur <.
Vous utilisez un foncteur.

La classe modèle priority_queue reçoit trois arguments : le type des données à stocker dans la pile, un type de conteneur de séquence qui doit fournir au minimum les fonctions front(), push_back et pop_back et le type d’un prédicat binaire pour comparer les éléments. Vous pouvez donc utiliser un vector ou un deque. Si vous ne fournissez pas cet argument, le conteneur vector est sélectionné par défaut. C’est l’opérateur « inférieur à » < du type d’élément stocké qui est utilisé par défaut.

Le code 8.12 illustre l’utilisation d’une file d’attente à priorité. La classe priority_queue fournit la fonction top() pour accéder à l’élément de plus forte priorité et les fonctions push() et pop() pour ajouter un élément à la file et supprimer l’élément de plus forte priorité respectivement.

Code 8.12 : utilisation d’une file d’attente à priorité

#include <iostream>  
#include <queue>  

using namespace std;  

// Type des objets stockés dans la file :  
class A  
{  
public:  
    int p;         // Priorité  
    const char *t; // Valeur chaîne de caractères  

    A() : p(0), t(0) {}  
    A(int p, const char *t) : p(p), t(t) {}  

// fonction de comparaison :   
    bool operator()(const A &a1, const A &a2)  
    {   
//On renvoie 0 ou 1 selon que la comparaison est  
//vraie ou fausse  
        return a1.p < a2.p ;  
    }  

};  

int main(void)  
{  
  //On crée quelques objets :  
   A a1(1, "Priorité faible");  
   A a2(2, "Priorité moyenne 1");  
   A a3(2, "Priorité moyenne 2");  
   A a4(3, "Forte priorité");  
 //On crée la file d'attente à priorité :  
   priority_queue<A, vector<A>, A> ma_file; /*attention, il faut insérer  
     un espace entre les 2 > > pour ne pas confondre avec   
     l'opérateur >> de cin*/  
 //On ajoute les éléments :  
   ma_file.push(a3);  
   ma_file.push(a1);  
   ma_file.push(a2);  
   ma_file.push(a4);  
 //On récupère les éléments par ordre de priorité :  
   while (!ma_file.empty()) //tant que la file n’est pas vide  
   {  
   //on affiche l’élément de plus forte priorité :  
   cout << ma_file.top().t << endl;  
        ma_file.pop();  //puis on le supprime  
    }  
}

L’exécution de ce programme donne le résultat suivant :

Forte priorité  
Priorité moyenne 1  
Priorité moyenne 2  
Priorité faible

Le texte original de cette fiche pratique est extrait de
«Tout sur le C++» (Christine EBERHARDT, Collection
CommentCaMarche.net, Dunod, 2009)