Partager via


priority_queue, classe

Une classe d'adaptateur au 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 plus haute priorité. De nouveaux éléments peuvent être ajoutés au priority_queue et l'élément du plus haut niveau de priority_queue peut être examiné ou supprimé.

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 la priority_queue.

  • Container
    Le type de conteneur sous-jacent utilisé pour implémenter la priority_queue.

  • Comparaison
    Type qui fournit un objet de fonction pouvant comparer deux valeurs d'éléments comme clés de tri afin de déterminer leur ordre relatif dans la 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 la classe Type stipulés dans le premier paramètre de modèle d'un objet de fin sont similaires à une value_type et doivent correspondre au type d'élément dans la classe de conteneur sous-jacent Container stipulé par le deuxième paramètre de modèle. Le Type doit être assignable, afin qu'il soit possible de copier des objets de ce type et d'affecter des valeurs aux variables de ce type.

La priority_queue trie la séquence qu'elle contrôle en appelant un objet de fonction stocké de classe Traits. En général, les éléments doivent être seulement moins que comparableq afin d'établir cet ordre : pour que, avec deux événements quelconques donnés, il soit possible de déterminer soit qu'ils soient équivalent (dans le sens où aucune n'est inférieur à l'autre), soit que l'un l'est moins que l'autre. Cela entraîne un classement entre les éléments non-équivalents. D'un point de vue plus technique, la fonction de comparaison est un prédicat binaire qui induit une commande faible stricte dans le sens mathématique standard.

Les classes de conteneur sous-jacentes appropriées pour le priority_queue incluent classe de deque et classe vectorielle par défaut ou tout autre conteneur de séquences qui prend en charge des opérations front, push_back, et pop_back et un itérateur d'accès aléatoire. La classe de conteneur sous-jacente est encapsulée dans l'adaptateur de conteneur, qui expose uniquement l'ensemble limité des fonctions membres du conteneur de séquences en tant qu'interface publique.

L'ajout et la suppression d'éléments dans une priority_queue ont une complexité logarithmique. L'accès aux éléments dans une priority_queue a une complexité constante.

Il existe trois types d'adaptateurs de conteneur définis par STL : pile, file d'attente, et priority_queue. Chacun limite la fonctionnalité d'une certaine classe de conteneurs sous-jacente pour fournir une interface contrôlée avec précision à une structure de données standard.

  • La classe de pile prend en charge une structure de données dernière-entrée et première-sortie (LIFO). Une bonne analogie à garder à l'esprit serait de la comparer à une pile d'assiettes. Les éléments (les assiettes) peuvent être insérés, inspectés, ou supprimés uniquement depuis le haut de la pile, qui est le dernier élément à la fin du conteneur de base. La raison pour laquelle vous utilisez une classe de pile est la restriction à accéder seulement à l'élément supérieur.

  • La classe de file d'attente prend en charge une structure de données premier-entré, premier-sorti (FIFO). Une bonne analogie à garder à l'esprit serait des personnes faisant la queue devant un guichet. Les éléments (les personnes) peuvent être ajoutés à la fin de la ligne et sont supprimés au début de la ligne. L'avant et l'arrière d'une ligne peuvent tous les deux être inspectés. La raison pour laquelle vous utilisez la classe de file d'attente est la restriction à accéder de cette manière uniquement aux éléments de début et de fin.

  • La classe de priority_queue classe ses éléments afin que le plus grand élément soit toujours au dessus. Il prend en charge l'insertion d'un élément, et l'inspection et la suppression de l'élément du dessus. Une bonne analogie à garder à l'esprit serait des personnes s'alignant de manière à être rangés par âge, par taille, ou suivant tout autre critère.

Constructeurs

priority_queue

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

Typedef

container_type

Type qui contient le conteneur de base devant être adapté par une priority_queue.

type_taille

Un type d'entier non signé qui peut représenter le nombre d'éléments dans une priority_queue.

type valeur

Un type qui représente le type d'objet stocké comme élément dans la priority_queue.

Fonctions membres

empty

Vérifie que la priority_queue est vide.

pop

Supprime le plus grand élément de la priority_queue depuis la position supérieure.

push

Ajoute un élément à la file d'attente à priorité déterminée en fonction de la priorité de l'élément de l'opérateur<.

taille

Retourne le nombre d'éléments figurant dans le priority_queue.

top

Retourne une référence const au plus grand élément en haut de la priority_queue.

Configuration requise

En-tête : <File d'attente>

Espace de noms : std

Voir aussi

Référence

Sécurité des threads dans la bibliothèque standard C++

Bibliothèque STL (Standard Template Library)