CKTIS / C++
std::priority_queue — file de priorité
std::priority_queue donne accès à l’élément de priorité la plus élevée, et non au premier élément inséré. Par défaut, la plus grande valeur se trouve au sommet ; std::greater<T> inverse l’ordre.
Version : C++23; repository compiler flag, production runtime not attested
Syntaxe
#include <functional>
#include <queue>
#include <vector>
std::priority_queue<T> q;
std::priority_queue<T, std::vector<T>, std::greater<T>> min_q;std::priority_queue de <queue> est un adaptateur de conteneur qui maintient un tas, et non une file FIFO. Par défaut, il utilise std::vector<T> et std::less<T>, donc top() désigne la plus grande valeur. La variante utilisant std::greater<T> désigne la plus petite ; elle nécessite <functional>.
push() insère une valeur, tandis que emplace() construit un élément dans le conteneur et rétablit la propriété de tas. top() fournit un accès en lecture seule. pop() retire le sommet et renvoie void : copiez toute valeur nécessaire avant son retrait. Vérifiez empty() avant top() et pop() ; ces deux opérations exigent une file non vide.
Le comparateur doit définir un ordre faible strict. Compare(a, b) == true signifie que a précède b dans cet ordre et a donc une priorité d’extraction plus faible. L’adaptateur ne fournit ni itérateurs ni opération permettant de modifier la priorité d’un élément arbitraire.
top() a un coût constant. Le rétablissement du tas pendant push(), emplace() et pop() nécessite O(log n) comparaisons. L’insertion inclut aussi le coût du conteneur sous-jacent : la réallocation du std::vector<T> par défaut peut rendre une insertion individuelle linéaire.
L’exemple affiche les mêmes données dans l’ordre décroissant puis croissant, en vidant les deux files. Cette entrée concerne C++23 ; le projet de travail lié est plus récent et ne constitue pas un texte C++23 figé.
Exemples
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
int main() {
std::priority_queue<int> max_q;
std::priority_queue<int, std::vector<int>, std::greater<int>> min_q;
for (int value : {4, 1, 7, 1}) {
max_q.push(value);
min_q.push(value);
}
while (!max_q.empty()) {
std::cout << max_q.top();
max_q.pop();
std::cout << (max_q.empty() ? '\n' : ' ');
}
while (!min_q.empty()) {
std::cout << min_q.top();
min_q.pop();
std::cout << (min_q.empty() ? '\n' : ' ');
}
}
Résultat
7 4 1 1 1 1 4 7
Le code affiché et le résultat déclaré ont été vérifiés dans un environnement isolé selon la méthode consignée dans la preuve de vérification de cette version exacte.