Namespaces
Variants

std:: priority_queue

From cppreference.net
C++
Containers library
std::priority_queue
Défini dans l'en-tête <queue>
template <

class T,
class Container = std:: vector < T > ,
class Compare = std:: less < typename Container :: value_type >

> class priority_queue ;

La file de priorité est un adaptateur de conteneur qui fournit une recherche en temps constant du plus grand élément (par défaut), au prix d'une insertion et d'une extraction logarithmiques.

Un Compare fourni par l'utilisateur peut être fourni pour modifier l'ordre, par exemple en utilisant std:: greater < T > ferait apparaître le plus petit élément comme le top() .

Travailler avec une priority_queue est similaire à la gestion d'un heap dans un conteneur à accès aléatoire, avec l'avantage de ne pas pouvoir invalider accidentellement le heap.

Toutes les fonctions membres de std::priority_queue sont constexpr : il est possible de créer et d'utiliser des objets std::priority_queue lors de l'évaluation d'une expression constante.

Cependant, les objets std::priority_queue ne peuvent généralement pas être constexpr , car tout stockage alloué dynamiquement doit être libéré lors de la même évaluation d'expression constante.

(depuis C++26)

Table des matières

Paramètres du modèle

T - Le type des éléments stockés. Le programme est mal formé si T n'est pas le même type que Container::value_type .
Container - Le type du conteneur sous-jacent utilisé pour stocker les éléments. Le conteneur doit satisfaire aux exigences de SequenceContainer , et ses itérateurs doivent satisfaire aux exigences de LegacyRandomAccessIterator . De plus, il doit fournir les fonctions suivantes avec la sémantique habituelle :

Les conteneurs standards std::vector (à l'exclusion de std::vector<bool> ) et std::deque satisfont à ces exigences.

Compare - Un type Compare fournissant un ordre strict faible.

Notez que le paramètre Compare est défini de telle sorte qu'il retourne true si son premier argument vient avant son second argument dans un ordre faible. Mais comme la file de priorité sort les plus grands éléments en premier, les éléments qui "viennent avant" sont en réalité sortis en dernier. C'est-à-dire que l'avant de la file contient le "dernier" élément selon l'ordre faible imposé par Compare .

Types membres

Type de membre Définition
container_type Container
value_compare Compare
value_type Container::value_type
size_type Container :: size_type
reference Container::reference
const_reference Container::const_reference

Objets membres

Nom du membre Définition
Container c
le conteneur sous-jacent
(objet membre protégé)
Compare comp
l'objet fonction de comparaison
(objet membre protégé)

Fonctions membres

construit la priority_queue
(fonction membre publique)
détruit la priority_queue
(fonction membre publique)
assigne des valeurs à l'adaptateur de conteneur
(fonction membre publique)
Accès aux éléments
accède à l'élément supérieur
(fonction membre publique)
Capacité
vérifie si l'adaptateur de conteneur est vide
(fonction membre publique)
renvoie le nombre d'éléments
(fonction membre publique)
Modificateurs
insère un élément et trie le conteneur sous-jacent
(fonction membre publique)
(C++23)
insère une plage d'éléments et trie le conteneur sous-jacent
(fonction membre publique)
(C++11)
construit un élément en place et trie le conteneur sous-jacent
(fonction membre publique)
supprime l'élément supérieur
(fonction membre publique)
(C++11)
échange le contenu
(fonction membre publique)

Fonctions non membres

(C++11)
spécialise l'algorithme std::swap
(modèle de fonction)

Classes d'assistance

(C++11)
spécialise le std::uses_allocator trait de type
(spécialisation de modèle de classe)
(C++23)
support de formatage pour std::priority_queue
(spécialisation de modèle de classe)

Guides de déduction

(depuis C++17)

Notes

Macro de test de fonctionnalité Valeur Std Fonctionnalité
__cpp_lib_containers_ranges 202202L (C++23) Construction et insertion compatibles avec les gammes pour les conteneurs
__cpp_lib_constexpr_queue 202502L (C++26) constexpr std::priority_queue

Exemple

Exécuter ce code 
#include <functional>
#include <iostream>
#include <queue>
#include <string_view>
#include <vector>
template<typename T>
void pop_println(std::string_view rem, T& pq)
{
    std::cout << rem << ": ";
    for (; !pq.empty(); pq.pop())
        std::cout << pq.top() << ' ';
    std::cout << '\n';
}
template<typename T>
void println(std::string_view rem, const T& v)
{
    std::cout << rem << ": ";
    for (const auto& e : v)
        std::cout << e << ' ';
    std::cout << '\n';
}
int main()
{
    const auto data = {1, 8, 5, 6, 3, 4, 0, 9, 7, 2};
    println("data", data);
    std::priority_queue<int> max_priority_queue;
    // Remplir la file de priorité.
    for (int n : data)
        max_priority_queue.push(n);
    pop_println("max_priority_queue", max_priority_queue);
    // std::greater<int> fait agir la file de priorité max comme une file de priorité min.
    std::priority_queue<int, std::vector<int>, std::greater<int>>
        min_priority_queue1(data.begin(), data.end());
    pop_println("min_priority_queue1", min_priority_queue1);
    // Deuxième façon de définir une file de priorité min.
    std::priority_queue min_priority_queue2(data.begin(), data.end(), std::greater<int>());
    pop_println("min_priority_queue2", min_priority_queue2);
    // Utilisation d'un objet fonction personnalisé pour comparer les éléments.
    struct
    {
        bool operator()(const int l, const int r) const { return l > r; }
    } customLess;
    std::priority_queue custom_priority_queue(data.begin(), data.end(), customLess);
    pop_println("custom_priority_queue", custom_priority_queue);
    // Utilisation d'une lambda pour comparer les éléments.
    auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1); };
    std::priority_queue<int, std::vector<int>, decltype(cmp)> lambda_priority_queue(cmp);
    for (int n : data)
        lambda_priority_queue.push(n);
    pop_println("lambda_priority_queue", lambda_priority_queue);
}

Sortie : 

data: 1 8 5 6 3 4 0 9 7 2
max_priority_queue: 9 8 7 6 5 4 3 2 1 0
min_priority_queue1: 0 1 2 3 4 5 6 7 8 9
min_priority_queue2: 0 1 2 3 4 5 6 7 8 9
custom_priority_queue: 0 1 2 3 4 5 6 7 8 9
lambda_priority_queue: 8 9 6 7 4 5 2 3 0 1

Rapports de défauts

Les rapports de défauts modifiant le comportement suivants ont été appliqués rétroactivement aux normes C++ précédemment publiées.

DR Appliqué à Comportement publié Comportement corrigé
LWG 307 C++98 Container ne pouvait pas être std::vector<bool> autorisé
LWG 2566 C++98 Absence de l'exigence pour Container::value_type mal formé si T n'est pas du même type que Container::value_type
LWG 2684 C++98 priority_queue prend un comparateur
mais manquait le typedef membre correspondant 		ajouté

Voir aussi

tableau contigu redimensionnable
(modèle de classe)
ensemble de bits dynamique économe en espace
(spécialisation de modèle de classe)
file double face
(modèle de classe)