Comment utiliser c ++ priority_queue?

En C ++, une file d'attente est une structure de données de liste où le premier élément à placer dans la liste est le premier élément à être supprimé, lorsque la suppression doit avoir lieu. Une file d'attente prioritaire en C ++ est similaire, mais a une commande; C'est l'élément avec la plus grande valeur qui est supprimée en premier. La file d'attente prioritaire peut toujours être configurée de sorte que c'est l'élément avec la moindre valeur qui est supprimée en premier. Toute file d'attente doit avoir au moins le pousser() fonction et le populaire() fonction. Le pousser() La fonction ajoute un nouvel élément à l'arrière. Pour la file d'attente normale, le populaire() La fonction supprime le premier élément jamais poussé. Pour la file d'attente prioritaire, le populaire() La fonction supprime l'élément avec la priorité la plus élevée, qui pourrait être le plus grand ou le plus petit, selon le schéma de commande.

Afin d'utiliser le C ++ Priority_queue, le programme doit commencer par un code comme:

#inclure
#inclure
Utilisation de Namespace Std;

Il comprend la bibliothèque de file d'attente dans le programme.

Afin de continuer à lire, le lecteur aurait dû avoir une connaissance de base de C++.

Contenu de l'article

• Construction de base
• Fonctions des membres importants
• Autres fonctions de file d'attente prioritaires
• Données de chaîne
• Autres constructions de file d'attente prioritaires
• Conclusion

Construction de base

La structure de données doit être construite avant de pouvoir être utilisée. La construction ici signifie instanier un objet de la classe de file d'attente de la bibliothèque. L'objet de file d'attente doit alors avoir un nom donné par le programmeur. La syntaxe la plus simple pour créer une file d'attente prioritaire est:

File d'attente de priorité queuename;

Avec cette syntaxe, la plus grande valeur est supprimée en premier. Un exemple de l'instanciation est:

File d'attente de priorité PQ;

ou

File d'attente de priorité PQ;

Le vecteur et le deque sont deux structures de données en c++. Une priorité_queue peut être créée avec l'un ou l'autre. La syntaxe pour créer une file d'attente prioritaire à partir de la structure vectorielle est:

File d'attente de priorité, Comparez> pq;

Un exemple de cette instanciation est:

File d'attente de priorité, moins > pq;

Remarquez l'écart entre> et> à la fin de la déclaration. C'est pour empêcher la confusion avec >>. Le code de comparaison par défaut est «moins», ce qui signifie que le plus grand, et pas nécessairement la première valeur, serait supprimé en premier. Ainsi, la déclaration de création peut simplement être écrite comme:

File d'attente de priorité > pq;

Si la moindre valeur doit être supprimée en premier, l'instruction doit être:

File d'attente de priorité, plus grand > pq;

Fonctions des membres importants

La fonction push ()
Cette fonction pousse une valeur, qui est son argument, dans la priorité_queue. Il revient vide. Le code suivant illustre ceci:

File d'attente de priorité PQ;
pq.push (10);
pq.push (30);
pq.push (20);
pq.push (50);
pq.push (40);

Cette priorité_queue a reçu 5 valeurs entières dans l'ordre de 10, 30, 20, 50, 40. Si tous ces éléments doivent être sortis de la file d'attente prioritaire, alors ils sortiront dans l'ordre de 50, 40, 30, 20, 10.

La fonction pop ()
Cette fonction supprime de la priorité_queue la valeur avec la priorité la plus élevée. Si le code de comparaison est «plus grand», il supprimera l'élément avec la plus petite valeur. S'il est appelé à nouveau, il supprime l'élément suivant avec la plus petite valeur du reste; Appelé à nouveau, il supprime la plus petite valeur suivante, et ainsi de suite. Il revient vide. Le code suivant illustre ceci:

File d'attente de priorité, plus grand > pq;
pq.push ('a');
pq.push ('c');
pq.push ('b');
pq.push ('e');
pq.push ('d');

Notez que pour appeler une fonction membre, le nom de l'objet doit être suivi d'un point, puis de la fonction.

La fonction supérieure ()
Le populaire() La fonction supprime la valeur suivante de la priorité la plus élevée, mais ne le renvoie pas, comme populaire() est une fonction vide. Utilisez le haut() fonction afin de connaître la valeur de la plus haute priorité qui doit être supprimée ensuite. Le haut() La fonction renvoie une copie de la valeur de la plus haute priorité dans la priorité_queue. Le code suivant, où la prochaine valeur de la priorité la plus élevée est la moindre valeur, illustre cela

File d'attente de priorité, plus grand > pq;
pq.push ('a'); pq.push ('c'); pq.push ('b'); pq.push ('e'); pq.push ('d');
char ch1 = pq.haut(); pq.populaire();
char ch2 = pq.haut(); pq.populaire();
char ch3 = pq.haut(); pq.populaire();
char ch4 = pq.haut(); pq.populaire();
char ch5 = pq.haut(); pq.populaire();
couter<

La sortie est 'a "b" c "d" e'.

La fonction vide ()
Si un programmeur utilise le haut() Fonction sur une priorité vide_queue, après la compilation réussie, il recevrait un message d'erreur tel que:

Segmentation fault (core dumped)

Donc, vérifiez toujours si la file d'attente prioritaire n'est pas vide avant d'utiliser haut() fonction. Le vide() La fonction membre renvoie un bool, vrai, si la file d'attente est vide et fausse si la file d'attente n'est pas vide. Le code suivant illustre ceci:

File d'attente de priorité PQ;
int i1 = 10; int i2 = 30; int i3 = 20; int i4 = 50; int i5 = 40;
pq.push (i1); pq.push (I2); pq.push (i3); pq.push (i4); pq.push (i5);
alors que(!pq.vide())

couter << pq.top() << ";
pq.populaire();

couter << '\n';

Autres fonctions de file d'attente prioritaires

La fonction size ()
Cette fonction renvoie la longueur de la file d'attente prioritaire, car le code suivant illustre:

File d'attente de priorité PQ;
int i1 = 10; int i2 = 30; int i3 = 20; int i4 = 50; int i5 = 40;
pq.push (i1); pq.push (I2); pq.push (i3); pq.push (i4); pq.push (i5);
int len ​​= pq.taille();
couter << len << '\n';

La sortie est 5.

La fonction swap ()
Si deux Priority_queues sont du même type et de la même taille, ils peuvent être échangés par cette fonction, comme le montre le code suivant:

File d'attente de priorité PQ1;
int i1 = 10; int i2 = 30; int i3 = 20; int i4 = 50; int i5 = 40;
PQ1.push (i1); PQ1.push (I2); PQ1.push (i3); PQ1.push (i4); PQ1.push (i5);
File d'attente de priorité PQA;
int it1 = 1; int it2 = 3; int it3 = 2; int it4 = 5; int it5 = 4;
PQA.push (it1); PQA.push (it2); PQA.push (it3); PQA.push (it4); PQA.push (it5);
PQ1.échange (PQA);
alors que(!PQ1.vide())

couter << pq1.top() << ";
PQ1.populaire();
cout<<'\n';
alors que(!PQA.vide())

couter << pqA.top() << ";
PQA.populaire();
cout<<'\n';

La sortie est:

5 4 3 2 1
50 40 30 20 10

L'EMPlace ()
Le EMPlace () La fonction est similaire à la fonction push. Le code suivant illustre ceci:

File d'attente de priorité PQ1;
int i1 = 10; int i2 = 30; int i3 = 20; int i4 = 50; int i5 = 40;
PQ1.EMPLACE (I1);
PQ1.EMPLACE (I2);
PQ1.EMPLACE (I3);
PQ1.EMPLACE (I4);
PQ1.EMPLACE (I5);
alors que(!PQ1.vide())

couter << pq1.top() << ";
PQ1.populaire();
cout<<'\n';

La sortie est:

50 40 30 20 10

Données de chaîne

Lors de la comparaison des chaînes, la classe de chaînes doit être utilisée et non l'utilisation directe des littéraux de chaîne car il comparait les pointeurs et non les chaînes réelles. Le code suivant montre comment la classe de chaîne est utilisée:

#inclure
File d'attente de priorité PQ1;
String S1 = String ("Pen"),
s2 = string ("crayon"),
S3 = String ("Exercice Book"),
s4 = string ("manuel"),
S5 = String ("Règle");
PQ1.push (s1);
PQ1.push (s2);
PQ1.push (s3);
PQ1.push (s4);
PQ1.push (s5);
alors que(!PQ1.vide())

couter << pq1.top() << " ";
PQ1.populaire();
cout<<'\n';

La sortie est:

livre de texte souverain crayon stylo exercice

Autres constructions de file d'attente prioritaires

Création explicite à partir d'un vecteur
Une file d'attente prioritaire peut être créée explicitement à partir d'un vecteur comme le montre le code suivant:

#inclure
vecteur vtr = 10, 30, 20, 50, 40;
File d'attente de priorité pq (vtr.begin (), vtr.fin());
alors que(!pq.vide())

couter << pq.top() << ";
pq.populaire();
cout<<'\n';

La sortie est: 50 40 30 20 10. Cette fois, l'en-tête vectoriel doit également être inclus. Les arguments pour la fonction du constructeur prennent les pointeurs de départ et de fin du vecteur. Le type de données pour le vecteur et le type de données pour la priority_queue doivent être les mêmes.

Afin de faire la moindre valeur la priorité, la déclaration du constructeur serait:

File d'attente de priorité, plus grand> int >> pq (vtr.begin (), vtr.fin());

Création explicite à partir d'un tableau
Une file d'attente prioritaire peut être créée explicitement à partir d'un tableau comme le montre le code suivant:

int arr [] = 10, 30, 20, 50, 40;
File d'attente de priorité pq (arr, arr + 5);
alors que(!pq.vide())

couter << pq.top() << ";
pq.populaire();
cout<<'\n';

La sortie est: 50 40 30 20 10. Les arguments pour la fonction du constructeur prennent les pointeurs de départ et de fin du tableau. ARR renvoie le pointeur de démarrage, «ARR + 5» renvoie le pointeur juste après le tableau, et 5 est la taille du tableau. Le type de données pour le tableau et le type de données pour la priority_queue doivent être les mêmes.

Afin de faire la moindre valeur la priorité, la déclaration du constructeur serait:

File d'attente de priorité, plus grand > pq (arr, arr + 5);

Remarque: En C ++, la priority_queue est en fait appelée adaptateur, pas seulement un conteneur.

Code de comparaison personnalisé

Avoir toutes les valeurs dans la file d'attente prioritaire ascendante ou toutes les descendant n'est pas la seule option pour la file d'attente prioritaire. Par exemple, une liste de 11 entiers pour un tas maximum est:

88, 86, 87, 84, 82, 79,74, 80, 81 ,,, 64, 69

La valeur la plus élevée est de 88. Ceci est suivi de deux nombres: 86 et 87, qui sont inférieurs à 88. Le reste des chiffres est inférieur à ces trois nombres, mais pas vraiment dans l'ordre. Il y a deux cellules vides dans la liste. Les chiffres 84 et 82 sont inférieurs à 86. Les chiffres 79 et 74 sont inférieurs à 87. Les nombres 80 et 81 sont inférieurs à 84. Les nombres 64 et 69 sont inférieurs à 79.

Le placement des nombres suit les critères maximaux - voir plus tard. Afin de fournir un tel schéma pour la priority_queue, le programmeur doit fournir son propre code de comparaison - voir plus tard.

Conclusion

Un C ++ Priority_Queue est une file d'attente de premier entrée. La fonction membre, pousser(), ajoute une nouvelle valeur dans la file d'attente. La fonction membre, haut(), lit la valeur maximale dans la file d'attente. La fonction membre, populaire(), Supprime sans renvoyer la valeur supérieure de la file d'attente. La fonction membre, vide(), vérifie si la file d'attente est vide. Cependant, la priorité_queue diffère de la file d'attente, en ce que, il suit un algorithme de priorité. Cela peut être le plus grand, du premier au dernier, ou du moins, du premier au dernier. Les critères (algorithme) peuvent également être définis par le programmeur.