Partage via

Classe priority_queue

Adaptateur de conteneur qui gère une collection d’éléments où l’élément le plus grand (ou priorité la plus élevée) est toujours accessible en haut. Vous pouvez ajouter de nouveaux éléments et supprimer ou examiner l’élément supérieur, mais vous ne pouvez pas accéder directement aux éléments au milieu de la collection.

Syntaxe

template <class Type, class Container= vector <Type>, class Compare= less <typename Container ::value_type>>
class priority_queue

Paramètres

Type
Type de données d’élément à stocker dans le priority_queue.

Container
Type du conteneur sous-jacent qui stocke les éléments pour le priority_queue.

Compare
Type qui fournit un objet de fonction qui compare deux valeurs d’élément en tant que clés de tri pour déterminer leur ordre relatif dans le priority_queue. Cet argument est facultatif. Le prédicat less<typename Container::value_type> binaire est la valeur par défaut.

Notes

Les éléments de classe Type spécifiés dans le premier paramètre de modèle d’un priority_queue objet sont équivalents value_type et doivent correspondre au type d’élément dans la classe Container de conteneur sous-jacente spécifiée par le deuxième paramètre de modèle. Il Type doit être assignable, ce qui signifie que vous pouvez copier des objets de ce type et affecter des valeurs à des variables de ce type.

Utilise priority_queue une fonction de comparaison pour déterminer quels éléments ont une priorité plus élevée. Cette fonction de comparaison est un objet de fonction de classe Traits. Pour travailler avec priority_queue, vos éléments doivent uniquement prendre en charge la comparaison à l’aide de l’opérateur inférieur à (<) afin qu’il puisse organiser les éléments dans l’ordre.

Vous pouvez modifier le type de conteneur sous-jacent utilisé par le priority_queue. Vous pouvez le faire pour des raisons de performances. La valeur par défaut est vectorgénéralement la meilleure pour la localité du cache, car les éléments sont stockés dans un stockage contigu et effectue moins d’allocations au fur et à mesure qu’il augmente. Mais peut-être pensez-vous deque que si vous avez des files d’attente très volumineuses ou non liées et que les éléments mobiles sont coûteux. Pour plus d’informations sur les classes de conteneur sous-jacentes appropriées, consultez container_type.

L’ajout et la suppression d’éléments d’une priority_queue complexité logarithmique sont tous deux complexes. L’accès aux éléments dans une classe priority_queue présente une complexité constante.

La bibliothèque standard C++ définit d’autres adaptateurs de conteneur que vous pouvez utiliser pour stocker les éléments dans vos priority_queueéléments : stack, queueet priority_queue:

  • La stack classe prend en charge une structure de données liFO (last-in, first-out). Considérez une pile de plaques : vous pouvez insérer, inspecter ou supprimer des éléments (plaques) uniquement du haut de la pile, qui est le dernier élément à la fin du conteneur de base.
  • La queue classe prend en charge une structure de données fiFO (first-out) de première entrée. Considérez les gens dans une ligne. Vous ajoutez des éléments (personnes) à l’arrière de la ligne et supprimez-les de l’avant de la ligne. L’avant et l’arrière d’une ligne peuvent être inspectés.
  • La priority_queue classe trie ses éléments afin que le plus grand élément soit toujours en haut. Elle prend en charge l'insertion d'un élément, et l'inspection et la suppression de l'élément du haut.

Examples

Constructeurs

Constructeur Description
priority_queue Construit un priority_queue qui est vide ou qui est une copie d’une plage d’un objet conteneur de base ou d’un autre priority_queue.

Typedefs

Nom de type Description
container_type Type qui fournit le conteneur de base adapté priority_queue .
size_type Type entier non signé qui peut représenter le nombre d'éléments dans un priority_queue.
value_type Type qui représente le type d'objet stocké en tant qu'élément dans un objet priority_queue.

Fonctions Membre

Fonction membre Description
empty Vérifie si l'objet priority_queue est vide.
pop Supprime l’élément le plus grand en haut du priority_queue.
push Ajoute un élément à la file d’attente de priorité en fonction de la priorité de l’élément de operator<.
size Retourne le nombre d'éléments d'un priority_queue.
top Retourne une référence const à l’élément le plus grand en haut du priority_queue.

Spécifications

En-tête :<queue>

Espace de noms : std

priority_queue::container_type

Type qui fournit le conteneur de base à adapter.

typedef Container container_type;

Notes

Le type est un synonyme du paramètre de modèle Container.

Classes de conteneur sous-jacentes appropriées pour priority_queue inclure deque la classe, la classe par défaut vectorou tout autre conteneur de séquence qui prend en charge les opérations de front, push_backet pop_back un itérateur d’accès aléatoire. L’adaptateur de conteneur encapsule la classe de conteneur sous-jacente et expose uniquement un ensemble limité de fonctions membres de conteneur de séquence en tant qu’interface publique.

Pour obtenir un exemple de déclaration et d’utilisation container_type, consultez Utiliser des conteneurs et comparateurs personnalisés

priority_queue::empty

Vérifie si un priority_queue est vide.

bool empty() const;

Valeur de retour

true si la priority_queue valeur est vide ; false si elle priority_queue n’est pas vide.

Exemple : vérifier si l’objet priority_queue est vide

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;

   // Declares priority_queues with default deque base container
   priority_queue <int> q1, s2;

   q1.push(1);

   if (q1.empty())
      cout << "The priority_queue q1 is empty." << endl;
   else
      cout << "The priority_queue q1 is not empty." << endl;

   if (s2.empty())
      cout << "The priority_queue s2 is empty." << endl;
   else
      cout << "The priority_queue s2 is not empty." << endl;
}

The priority_queue q1 is not empty.
The priority_queue s2 is empty.

priority_queue::pop

Supprime l’élément le plus grand en haut du priority_queue.

void pop();

Notes

Il priority_queue doit être vide pour utiliser cette fonction membre. Le haut du priority_queue conteneur contient toujours le plus grand élément dans le conteneur.

Exemple : Éléments pop et taille de vérification

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;
   priority_queue <int> q1, s2;

   q1.push(10);
   q1.push(20);
   q1.push(30);

   priority_queue <int>::size_type i, iii;
   i = q1.size();
   cout << "The priority_queue length is " << i << "." << endl;

   const int& ii = q1.top();
   cout << "The element at the top of the priority_queue is " << ii << "." << endl;

   q1.pop();

   iii = q1.size();
   cout << "After a pop, the priority_queue length is " << iii << "." << endl;

   const int& iv = q1.top();
   cout << "After a pop, the element at the top of the " << "priority_queue is " << iv << "." << endl;
}

The priority_queue length is 3.
The element at the top of the priority_queue is 30.
After a pop, the priority_queue length is 2.
After a pop, the element at the top of the priority_queue is 20.

priority_queue::priority_queue

Crée un priority_queue objet vide ou qui copie une plage à partir d’un objet conteneur de base ou d’un autre priority_queue.

priority_queue();

explicit priority_queue(const Traits& _comp);

priority_queue(const Traits& _comp, const container_type& _Cont);

priority_queue(const priority_queue& right);

template <class InputIterator>
priority_queue(InputIterator first, InputIterator last);

template <class InputIterator>
priority_queue(InputIterator first, InputIterator last, const Traits& _comp);

template <class InputIterator>
priority_queue(InputIterator first, InputIterator last, const Traits& _comp, const container_type& _Cont);

Paramètres

_comp
Fonction de comparaison de type constTraits utilisée pour classer les éléments dans le priority_queue, qui par défaut compare la fonction du conteneur de base.

_Cont
Conteneur de base dont la construction priority_queue doit être une copie.

right
Dont priority_queue l’ensemble construit doit être une copie.

first
Position du premier élément de la plage d'éléments à copier.

last
Position du premier élément au-delà de la plage d'éléments à copier.

Notes

Chacun des trois premiers constructeurs spécifie un initial priority_queuevide, le second spécifiant également le type de fonction de comparaison (comp) à utiliser pour établir l’ordre des éléments et le troisième spécifiant explicitement le container_type (_Cont) à utiliser. Le mot clé explicit supprime certains genres de conversions de type automatiques.

Le quatrième constructeur spécifie une copie du priority_queue right.

Les trois derniers constructeurs copient la plage [first, last) de certains conteneurs et utilisent les valeurs pour initialiser un avec une priority_queue précision croissante dans la spécification du type de fonction de comparaison de classe Traits et container_type.

Exemple : Utiliser des conteneurs et comparateurs personnalisés

// compile with: /EHsc
#include <queue>
#include <vector>
#include <deque>
#include <list>
#include <iostream>

int main()
{
   using namespace std;

   // Declares a priority_queue with a default vector base container
   priority_queue <int> q1;
   cout << "q1 = ( ";
   while (!q1.empty())
   {
      cout << q1.top() << " ";
      q1.pop();
   }
   cout << ")" << endl;

   // Declares a priority_queue with nondefault deque base container
   priority_queue <int, deque <int>> q2;
   q2.push(5);
   q2.push(15);
   q2.push(10);
   cout << "q2 = ( ";
   while (!q2.empty())
   {
      cout << q2.top() << " ";
      q2.pop();
   }
   cout << ")" << endl;
   cout << "After printing, q2 has " << q2.size() << " elements." << endl;

   // Declares a priority_queue with a vector base container and specifies that
   // the comparison function greater is to be used for ordering elements
   priority_queue <int, vector<int>, greater<int>> q3;
   q3.push(2);
   q3.push(1);
   q3.push(3);
   cout << "q3 = ( ";
   
   while (!q3.empty())
   {
      cout << q3.top() << " ";
      q3.pop();
   }
   cout << ")" << endl;

   // Declares a priority_queue and initializes it with elements copied from another
   // container by first inserting elements into q1 and then copying q1 elements into q4
   q1.push(100);
   q1.push(200);
   priority_queue <int> q4(q1);
   cout << "q4 = ( ";
   while (!q4.empty())
   {
      cout << q4.top() << " ";
      q4.pop();
   }
   cout << ")" << endl;

   // Creates an auxiliary vector object v5 to be used to initialize q5
   vector <int> v5;
   vector <int>::iterator v5_Iter;
   v5.push_back(10);
   v5.push_back(30);
   v5.push_back(20);
   cout << "v5 = ( " ;
   for (v5_Iter = v5.begin() ; v5_Iter != v5.end() ; v5_Iter++)
   {
      cout << *v5_Iter << " ";
   }
   cout << ")" << endl;

   // Declares and initializes a priority_queue q5 by copying the
   // range v5[ first,  last) from vector v5
   priority_queue <int> q5(v5.begin(), v5.begin() + 2);
   cout << "q5 = ( ";
   while (!q5.empty())
   {
      cout << q5.top() << " ";
      q5.pop();
   }
   cout << ")" << endl;

   // Declares a priority_queue q6 with a comparison function greater and
   // initializes q6 by copying the range v5[ first,  last) from vector v5
   priority_queue <int, vector<int>, greater<int>> q6(v5.begin(), v5.begin() + 2);
   cout << "q6 = ( ";
   while (!q6.empty())
   {
      cout << q6.top() << " ";
      q6.pop();
   }
   cout << ")" << endl;
}

priority_queue::push

Ajoute un élément à la file d’attente de priorité en fonction de la priorité de l’élément de operator<.

void push(const Type& val);

Paramètres

val
Élément à ajouter en haut du priority_queue.

Notes

Le haut du priority_queue conteneur contient le plus grand élément du conteneur.

Exemple : Envoyer des éléments et lire le haut

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;
   priority_queue<int> q1;

   q1.push(10);
   q1.push(30);
   q1.push(20);

   priority_queue<int>::size_type i;
   i = q1.size();
   cout << "The priority_queue length is " << i << "." << endl;

   const int& ii = q1.top();
   cout << "The element at the top of the priority_queue is " << ii << "." << endl;
}

The priority_queue length is 3.
The element at the top of the priority_queue is 30.

priority_queue::size

Retourne le nombre d'éléments d'un priority_queue.

size_type size() const;

Valeur de retour

Longueur actuelle du priority_queue.

Exemple : Obtenir le nombre d’éléments dans le priority_queue

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;
   priority_queue <int> q1, q2;
   priority_queue <int>::size_type i;

   q1.push(1);
   i = q1.size();
   cout << "The priority_queue length is " << i << "." << endl;

   q1.push(2);
   i = q1.size();
   cout << "The priority_queue length is now " << i << "." << endl;
}

The priority_queue length is 1.
The priority_queue length is now 2.

priority_queue::size_type

Type entier non signé qui représente le nombre d’éléments d’un priority_queue.

typedef typename Container::size_type size_type;

Notes

Ce type est un synonyme size_type du conteneur de base adapté priority_queue .

Exemple : Accéder à l’élément supérieur

Pour obtenir un exemple de déclaration et d’utilisation size_type, consultez Obtenir le nombre d’éléments

priority_queue::top

Retourne une référence const à l’élément le plus grand en haut du priority_queue.

const_reference top() const;

Valeur de retour

Référence au plus grand élément, tel que déterminé par la Traits fonction, objet du priority_queue.

Notes

Il priority_queue doit être vide pour utiliser cette fonction membre.

Exemple : Obtenir l’élément supérieur de l’élément priority_queue

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;
   priority_queue<int> q1;

   q1.push(10);
   q1.push(30);
   q1.push(20);

   priority_queue<int>::size_type i;
   i = q1.size();
   cout << "The priority_queue length is " << i << "." << endl;

   const int& ii = q1.top();
   cout << "The element at the top of the priority_queue is " << ii << "." << endl;
}

The priority_queue length is 3.
The element at the top of the priority_queue is 30.

priority_queue::value_type

Type qui représente le type d'objet stocké en tant qu'élément dans un objet priority_queue.

typedef typename Container::value_type value_type;

Notes

Ce type est un synonyme value_type du conteneur de base adapté priority_queue .

Exemple : Utiliser l’alias priority_queue value_type

// compile with: /EHsc
#include <queue>
#include <iostream>

int main()
{
   using namespace std;

   // Declares priority_queues with default deque base container
   priority_queue<int>::value_type AnInt;

   AnInt = 69;
   cout << "The value_type is AnInt = " << AnInt << endl;

   priority_queue<int> q1;
   q1.push(AnInt);
   cout << "The element at the top of the priority_queue is " << q1.top() << "." << endl;
}

The value_type is AnInt = 69
The element at the top of the priority_queue is 69.

Exemple : Utiliser un type de données défini par l’utilisateur

Pour utiliser priority_queue des éléments de type définis par l’utilisateur, vous devez fournir un moyen de comparer les éléments. Vous pouvez définir operator< pour votre type ou fournir un objet de fonction de comparaison personnalisé.

L’exemple suivant montre un priority_queue objet qui stocke les Task objets, classés par niveau de priorité. Les tâches avec des valeurs de priorité supérieure sont en haut de la file d’attente.

// compile with: /EHsc
#include <queue>
#include <iostream>
#include <string>

struct Task
{
    int priority;
    std::string name;

    // Define operator< for priority_queue ordering
    // Returns true if this task has LOWER priority than other
    // (priority_queue puts the "largest" element at the top)
    bool operator<(const Task& other) const
    {
        return priority < other.priority;
    }
};

int main()
{
    std::priority_queue<Task> tasks;

    tasks.push({3, "Low priority task"});
    tasks.push({10, "High priority task"});
    tasks.push({5, "Medium priority task"});

    std::cout << "Processing tasks by priority:\n";
    while (!tasks.empty())
    {
        const Task& t = tasks.top();
        std::cout << "  Priority " << t.priority << ": " << t.name << "\n";
        tasks.pop();
    }
}

Processing tasks by priority:
  Priority 10: High priority task
  Priority 5: Medium priority task
  Priority 3: Low priority task

Notes

Si vous souhaitez un classement différent (par exemple, des valeurs inférieures en premier), fournissez un comparateur personnalisé :

struct ComparePriority
{
    bool operator()(const Task& a, const Task& b)
    {
        return a.priority > b.priority; // Lower priority value means higher priority
    }
};

std::priority_queue<Task, std::vector<Task>, ComparePriority> minQueue;

Voir aussi

Sécurité des threads dans la bibliothèque C++ Standard
Informations de référence sur la bibliothèque standard C++

  • Last updated on