hash_multiset, classe

Article
06/09/2015

Notes

Cette API est obsolète.L'alternative est unordered_multiset, classe.

Le hash_multiset de classe de conteneur est une extension de la Standard TEMPLATE Library (STL) et est utilisé pour le stockage et la récupération rapide des données d'une collection dans laquelle les valeurs des éléments contenus servent de clé et ne sont pas obligatoirement uniques.

template < 
   class Key,  
   class Traits=hash_compare<Key, less<Key> >,  
   class Allocator=allocator<Key>  
> 
class hash_multiset

Paramètres

Clé
Le type de données de l'élément à stocker dans le hash_multiset.
Traits
Le type qui inclut deux objets de fonction, un de comparaison de classe qui est un prédicat binaire capable de comparer deux valeurs d'élément comme des clés de tri pour déterminer leur ordre relatif, et une fonction de hachage qui est un prédicat donnant le mappage de valeurs clés des d'entiers non signés de size_t. Cet argument est facultatif, et la clé hash_compare*<,* moins*<clé> >* est la valeur par défaut.
Allocator
Le type qui représente l'objet d'allocation stocké qui contient des détails sur le l'allocation et la désallocation de mémoire du hash_multimap . Cet argument est facultatif et la valeur par défaut est allocator*<Key>.*

Notes

Le hash_multiset est :

Un conteneur associatif, qui est un conteneur de taille variable qui prend en charge la récupération efficace des valeurs d'élément selon une valeur de clé associée. De plus, il s'agit d'un conteneur associatif simple car ses valeurs d'élément sont ses valeurs clé.
Réversible, car il fournit un itérateur bidirectionnel pour accéder à ses éléments.
Haché, car ses éléments sont regroupés dans des compartiments selon la valeur d'une fonction de hachage appliquée aux valeurs des clés des éléments.
Unique dans le sens où chacun de ses éléments doit avoir une clé unique. Étant donné que le hash_multiset est également un conteneur associatif simple, les éléments sont également uniques.
Une classe de modèle, car la fonctionnalité qu'elle fournit est générique et donc indépendante du type de données spécifique contenu comme éléments ou clés. Les types de données utilisés pour des éléments et des clés sont eux spécifiés comme paramètres dans la classe modèle avec la fonction de comparaison et l'allocateur.

L'avantage principal du hachage sur le tri est une meilleure efficacité ; un hachage réussi exécute les insertions, les suppressions, et effectue des recherchess en une durée moyenne constante par rapport à une durée proportionnelle au logarithme du nombre d'éléments dans le conteneur pour les techniques de tri. La valeur d'un élément dans un jeu peut ne pas être modifiée directement. A la place, vous devez supprimer les anciennes valeurs et insérer des éléments avec des nouvelles valeurs.

Le choix du type de conteneur doit être basée en général sur le type de la recherche et de l'insertion requis par l'application. Les conteneurs associatifs hachés sont optimisées pour les opérations de recherche, d'insertion, et de suppression. Les fonctions membres qui prennent en charge explicitement ces opérations sont efficaces lorsqu'elles sont utilisées avec une fonction de hachage bien conçue, les exécutant en une durée constante qui ne dépend pas du nombre d'éléments dans le conteneur. Une fonction de hachage bien conçue produit une distribution uniforme de valeurs hachées et réduit le nombre de collisions. On dit qu'une collision se produit lorsque des valeurs de clés séparées sont mappées à la même valeur de hachage. Dans le pire des cas, avec la pire des fonctions de hachage, le nombre d'opérations est proportionnel au nombre d'éléments dans la séquence (temps linéaire).

Le hash_multimap doit être le conteneur associatif du choix lorsque les conditions associant les valeurs à leurs clés sont satisfaites par l'application. Les éléments d'un hash_multiset peuvent être différents et servir comme leurs propres clés de tri, les clés ne sont pas uniques. Un modèle pour ce type de structure est une liste triée de mots dans lesquels les mots peuvent apparaître plusieurs fois par exemple. Si les occurrences multiples de mots étaient non autorisées, un hash_set aurait été la structure appropriée du conteneur. Si des définitions uniques étaient jointes en tant que valeurs à la liste des mots clés uniques, une hash_map serait une structure appropriée pour contenir les données. Si à la place des définitions n'étaient pas uniques, un hash_multimap serait le conteneur de choix.

Le hash_multimap classe la séquence qu'il contrôle en appelant un objet stocké de hachage de type value_compare. Cet objet stocké est accessible en appelant la fonction membre key_comp. Un tel objet de fonction doit se comporter de la même manière qu'un objet de la classe hash_compare*<Key,* less*<Key> >.* En particulier, pour toutes les clés de valeurs de type Clé, l'appel Trait(clé) génère une distribution des valeurs de type size_t.

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. Un prédicat binaire f (x,*y)*est un objet fonction qui a deux objets arguments X et Y et une valeur de retour true ou false. Une commande appliquée à un hash_multiset est une commande faible stricte si le prédicat binaire est irréflexif, antisymétrique, et transitif et si l'équivalence est transitive. Deux objets x et y sont définis comme équivalents lorsque les deux f(x,y) et f(y,x) sont faux Si la condition d'égalité la plus élevée entre les clés remplace celle de l'équivalence, alors la commande devient totale (dans le sens où tous les éléments sont classés les uns par rapport aux autres), et les clés correspondantes seront alors impossibles à différencier les unes des autres.

L'ordre actuel des éléments dans la séquence contrôlée dépend de la fonction de hachage, de la fonction de commande, et de la taille actuelle de la table de hachage stockée dans le conteneur de l'objet. Vous ne pouvez pas déterminer la taille actuelle de la table de hachage, vous ne pouvez généralement pas prédire l'ordre des éléments dans la séquence contrôlée. L'Insertion d'éléments n'invalide aucun itérateur, et la suppression d'éléments invalide uniquement les itérateurs qui pointaient spécifiquement vers les éléments supprimés.

L'itérateur fourni par la classe de hash_multiset est un itérateur bidirectionnel, mais les fonctions membres de classe insertion et hash_multiset ont des versions qui prennent comme paramètres de modèle un itérateur d'entrée plus faible, dont les spécifications des fonctionnalités sont plus minimales que celles garanties par la classe des itérateurs bidirectionnels. Les différents concepts d'itérateurs forment une famille liée par les améliorations de leurs fonctionnalités. Chaque concept d'itérateur possède son propre hash_multiset de spécifications, et les algorithmes qui fonctionnent avec eux doivent limiter leurs hypothèses aux spécifications fournies par ce type d'itérateur. On peut considérer qu'un itérateur d'entrée peut être déréférencé pour faire référence à un objet et qu'il peut être incrémenté à l'itérateur suivant dans la séquence. Ceci est un hash_multiset minimal de fonctionnalités, mais c'est assez pour pouvoir parler clairement d'une portée d'itérateurs (_First, _Last) dans le contexte des fonctions membres de classe.

Dans Visual C++ .NET 2003, les membres des fichiers d'en-tête <hash_map> et de <hash_set> ne sont plus dans l'espace de noms standard, mais ont été plutôt déplacés dans l'espace de noms de stdext. Pour plus d'informations, consultez The stdext Namespace.

Constructeurs

hash_multiset

Construisez un hash_multiset qui est vide ou qui est une copie de l'ensemble ou d'une partie d'un autre hash_multiset.

Typedef

allocator_type	Un type qui représente la classe allocator pour l'objet hash_multiset .
const_iterator	Un type qui fournit un itérateur bidirectionnel capable de lire un élément const dans hash_multiset.
const_pointer	Un type qui fournit un pointeur vers un élément const dans hash_multiset.
const_reference	Un type qui fournit une référence à un élément const stocké dans hash_multiset pour la lecture et l'exécution des opérations const .
const_reverse_iterator	Un type qui fournit un itérateur bidirectionnel capable de lire n'importe quel élément const dans hash_multiset.
difference_type	Un type d'entier signé qui fournit la différence entre deux itérateurs qui s'adressent à des éléments dans le même hash_multiset.
itérateur	Un type qui fournit un itérateur bidirectionnel capable de lire ou de modifier tout élément dans une hash_multiset.
key_compare	Un type qui fournit une fonction objet qui peut comparer deux clés triées pour déterminer l'ordre relatif de deux éléments dans une hash_multiset.
key_type	Type qui décrit un objet stocké en tant qu'élément d'un hash_set dans sa capacité comme clé de tri.
pointer	Un type qui fournit un pointeur à un élément dans une hash_multiset.
référence	Un type qui fournit une référence à un élément stocké dans une hash_multiset.
reverse_iterator	Un type qui fournit un itérateur bidirectionnel capable de lire ou modifier tout élément dans une hash_multiset inversée.
type_taille	Un type d'entier non signé qui peut représenter le nombre d'éléments dans une hash_multiset.
value_compare	Type qui fournit deux objets de fonction, un attribut binaire de comparaison de classe et qui peut comparer deux valeurs d'élément d'un hash_multiset pour déterminer leur ordre relatif et un attribut unaire qui hache les éléments.
type valeur	Un type qui décrit un objet enregistré comme élément d'un hash_multiset avec sa capacité comme valeur.

Fonctions membres

begin	Retourne un itérateur traitant le premier élément du hash_multiset.
hash_multiset::cbegin	Retourne un itérateur constant adressant le premier élément dans la hash_multiset.
hash_multiset::cend	Retourne un itérateur constant qui adresse l'emplacement succédant au dernier élément dans une hash_multiset.
clear	Efface tous les éléments d'une hash_multiset.
count	Retourne le nombre d'éléments dans une hash_multiset dont la clé correspond à une clé à paramètre spécifié.
hash_multiset::crbegin	Retourne un itérateur const adressant le premier élément dans une hash_multiset inversée.
hash_multiset::crend	Retourne un itérateur const qui s'adresse à l'emplacement suivant le dernier élément dans une hash_multiset inversée.
hash_multiset::emplace	Insère un élément construit sur place dans une hash_multiset.
hash_multiset::emplace_hint	Insère un élément construit sur place dans une hash_multiset, avec un indicateur de positionnement.
empty	Teste si une hash_multiset est vide.
end	Retourne un itérateur qui s'adresse à l'emplacement suivant le dernier élément dans une hash_multiset.
equal_range	Retourne une paire d'itérateurs, respectivement, au premier élément d'une hash_multiset avec une clé qui est supérieure à une clé spécifiée et au premier élément d'une hash_multiset avec une clé qui est égale ou supérieure à la clé.
effacer	Supprime un élément ou une plage d'éléments dans un hash_multiset depuis des emplacements spécifiés ou supprime les éléments qui correspondent à une clé spécifiée.
find	Retourne un itérateur adressant l'emplacement d'un élément dans une hash_multiset qui a une clé équivalente à une clé spécifiée.
get_allocator	Retourne une copie de l'objet allocator utilisé pour construire la hash_multiset.
insérer	Insère un élément ou une plage d'éléments dans hash_multiset.
key_comp	Extrait une copie de l'objet de comparaison utilisé pour mettre en ordre les clés dans une hash_multiset.
lower_bound	Retourne un itérateur au premier élément dans une hash_multiset avec clé qui est égale ou supérieure à une clé spécifiée.
max_size	Retourne la longueur maximale de la hash_multiset.
rbegin	Retourne un itérateur s'adressant au premier élément d'une hash_multiset inversée.
rend	Retourne un itérateur qui adresse l'emplacement suivant le dernier élément d'une hash_multiset inversée.
taille	Retourne le nombre d'éléments figurant dans le hash_multiset.
échange	Échange les éléments de deux hash_multiset.
upper_bound	Retourne un itérateur au premier élément dans un hash_multiset avec clé qui est égale ou supérieure à une clé spécifiée.
value_comp	Extrait une copie de l'objet traits de hachage utilisé pour hacher et signaler la valeur de clé de l'élément dans un hash_multiset.