La classe `priority_queue`

Article
10/12/2023

Classe d’adaptateur de conteneur de modèle qui fournit une restriction de fonctionnalité limitant l’accès à l’élément supérieur d’un certain type de conteneur sous-jacent, qui est toujours le plus grand ou de la priorité la plus élevée. De nouveaux éléments peuvent être ajoutés à l’élément priority_queue supérieur de celui-ci priority_queue ou être inspectés ou supprimés.

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 utilisé pour implémenter le priority_queue.

Compare
Type qui fournit un objet de fonction qui peut comparer 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 et le prédicat binaire less<typename Container::value_type> est la valeur par défaut.

Notes

Les éléments de classe Type stipulés dans le premier paramètre de modèle d’un objet file d’attente sont synonymes value_type et doivent correspondre au type d’élément dans la classe Container de conteneur sous-jacente stipulée par le deuxième paramètre de modèle. Il Type doit être assignable, afin qu’il soit possible de copier des objets de ce type et d’affecter des valeurs à des variables de ce type.

Commande priority_queue la séquence qu’il contrôle en appelant un objet de fonction stockée de classe Traits. En général, les éléments doivent être simplement moins que comparables pour établir cet ordre : pour que, compte tenu de deux éléments, il peut être déterminé qu’ils sont équivalents (dans le sens où aucun n’est inférieur à l’autre) ou qu’un élément est inférieur à l’autre. Cela entraîne le tri des éléments non équivalents. D’un point de vue plus technique, la fonction de comparaison est un prédicat binaire qui induit un ordre faible strict au sens mathématique du terme.

Classes de conteneur sous-jacentes appropriées pour priority_queue inclure deque la classe et la classe par défautvectorou 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. La classe de conteneur sous-jacent est encapsulée dans l'adaptateur de conteneur, qui expose seulement l'ensemble limité de fonctions membres du conteneur de séquence comme une interface publique.

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

Il existe trois types d’adaptateurs de conteneur définis par la bibliothèque standard C++ : stack, queueet priority_queue. Chaque type limite les fonctionnalités d’une classe de conteneur sous-jacent pour fournir une interface contrôlée de façon précise à une structure de données standard.

La stack classe prend en charge une structure de données liFO (last-in, first-out). Une bonne analogie à avoir à l'esprit est celle d'une pile d'assiettes. Les éléments (les assiettes) peuvent être insérés, inspectés ou supprimés seulement à partir du haut de la pile, qui est le dernier élément à la fin du conteneur de base. La restriction d’accès uniquement à l’élément supérieur est la raison d’utiliser la stack classe.
La queue classe prend en charge une structure de données fiFO (first-out) de première entrée. Une bonne analogie à avoir à l'esprit est celle de personnes faisant la file pour un employé de banque. Les éléments (les personnes) peuvent être ajoutés à l'arrière de la file et ils sont supprimés de l'avant de la file. Le début et la fin d'une file peuvent être inspectés. La restriction d’accès uniquement aux éléments front et back de cette façon est la raison de l’utilisation de la queue classe.
La priority_queue classe trie ses éléments afin que le plus grand élément soit toujours à la position supérieure. Elle prend en charge l'insertion d'un élément, et l'inspection et la suppression de l'élément du haut. Un bon analogue à garder à l’esprit serait les gens qui s’alignent là où ils sont disposés par âge, hauteur ou un autre critère.

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 à adapter par un objet `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. La classe deque de conteneur de séquence de bibliothèque standard C++ et la classe vector par défaut répondent aux exigences à utiliser comme conteneur de base pour un priority_queue objet. Les types définis par l’utilisateur peuvent également être utilisés s’ils remplissent les conditions.

Pour plus d’informations sur Container, consultez la section Remarques de la priority_queue rubrique Classe .

Exemple

Consultez l’exemple pour priority_queue obtenir un exemple de déclaration et d’utilisation container_type.

`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

// pqueue_empty.cpp
// 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 appliquer la fonction membre. Le haut du conteneur priority_queue est toujours occupé par le plus grand élément du conteneur.

Exemple

// pqueue_pop.cpp
// 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`

Construit un priority_queue objet vide ou qui est une copie d’une plage 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

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

int main( )
{
   using namespace std;

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

   // Explicitly 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;

   // This method of printing out the elements of a priority_queue
   // removes the elements from the priority queue, leaving it empty
   cout << "After printing, q2 has " << q2.size( ) << " elements." << endl;

   // The third member function 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;

   // The fourth member function declares a priority_queue and
   // initializes it with elements copied from another container:
   // first, inserting elements into q1, 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;

   // The fifth member function 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;

   // The sixth member function 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 ajouté en haut du priority_queue.

Notes

La partie supérieure est priority_queue la position occupée par le plus grand élément du conteneur.

Exemple

// pqueue_push.cpp
// 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

// pqueue_size.cpp
// 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 peut représenter le nombre d'éléments dans un priority_queue.

typedef typename Container::size_type size_type;

Notes

Le type est un synonyme du size_type conteneur de base adapté par le priority_queue.

Exemple

Consultez l’exemple pour size obtenir un exemple de déclaration et d’utilisation size_type.

`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 appliquer la fonction membre.

Exemple

// pqueue_top.cpp
// 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

Le type est un synonyme du value_type conteneur de base adapté par le priority_queue.

Exemple

// pqueue_value_type.cpp
// 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.

Voir aussi

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

Partager via

La classe priority_queue

Syntaxe

Paramètres

Notes

Constructeurs

Typedefs

Fonctions Membre

Spécifications

priority_queue::container_type

Notes

Exemple

priority_queue::empty

Valeur de retour

Exemple

priority_queue::pop

Notes

Exemple

priority_queue::priority_queue

Paramètres

Notes

Exemple

priority_queue::push

Paramètres

Notes

Exemple

priority_queue::size

Valeur de retour

Exemple

priority_queue::size_type

Notes

Exemple

priority_queue::top

Valeur de retour

Notes

Exemple

priority_queue::value_type

Notes

Exemple

Voir aussi

Commentaires

Commentaires

Ressources supplémentaires

La classe `priority_queue`

`priority_queue::container_type`

`priority_queue::empty`

`priority_queue::pop`

`priority_queue::priority_queue`

`priority_queue::push`

`priority_queue::size`

`priority_queue::size_type`

`priority_queue::top`

`priority_queue::value_type`