Namespaces
Variants

    std:: priority_queue

    From fr.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)

    Contenu

    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 de membres

    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

    Membre Description
    Conteneur c
    		 le conteneur sous-jacent
    (objet membre protégé)
    Comparateur 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)