hash_multiset Class

Article
03/26/2013

[!REMARQUE]

Cette API est obsolète.l'alternative est unordered_multiset Class.

Le hash_multiset de classe de conteneur est une extension du Standard Template Library) et est utilisé pour le stockage et la recherche rapide des données d'une collection dans laquelle les valeurs des éléments contenus servent de valeurs de clés et n'est pas requis pour être unique.

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 d'élément à stocker dans le hash_multiset.
Traits
Le type qui inclut deux objets de fonction, un de classe comparaison qui est un attribut binaire capable de comparer deux valeurs d'élément comme clés de tri pour déterminer leur commande relative et une fonction de hachage qui a les valeurs de clés unaires d'un mappage d'attribut des éléments aux entiers non signés de type size_t.Cet argument est facultatif, et le hash_compare*<Key,less<Key> >* est la valeur par défaut.
Allocator
Le type qui représente l'objet d'allocation stocké qui encapsule des informations sur l'allocation et la libération des hash_multiset de la mémoire.Cet argument est facultatif, et la valeur par défaut est allocator*<Key>.*

Notes

Le hash_multiset est :

Un conteneur associatif, qui un conteneur variable de taille qui prend en charge la recherche 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 de clés.
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 de clés des éléments.
Unique dans le sens que chacun de ses éléments doit avoir une clé unique.Étant donné que le hash_multiset est également un conteneur associatif simple, ses éléments sont également uniques.
Une classe de modèle car les fonctionnalités qu'elle fournit est générique et par conséquent indépendant du type de données spécifique contenu comme éléments ou clés.Les types de données à utiliser pour les éléments et les clés correspondent à la place spécifiés comme paramètres dans le modèle de classe avec la fonction de comparaison et l'allocateur.

L'avantage principal du hachage sur le tri est une efficacité supérieure : un hachage réussi exécute les insertions, les suppressions et les recherches, dans la durée moyenne constante par rapport à un moment proportionnel au logarithme du nombre d'éléments dans le conteneur pour les techniques de tri.La valeur d'un élément dans un jeu ne peut être modifié directement.À la place, vous devez supprimer les anciennes valeurs et des éléments d'insertion avec de nouvelles valeurs.

Le choix du type de conteneur doit être basé généralement sur le type de rechercher et d'insérer requis par l'application.Les conteneurs associatifs sont hachés optimisés pour les opérations de recherche, de l'insertion et de suppression.Les fonctions membres qui prennent en charge explicitement ces opérations sont efficaces lorsqu'elles avec une fonction de hachage bien conçue, les exécutant dans une heure qui est sur la constante moyenne et non en fonction de le nombre d'éléments dans le conteneur.Une fonction de hachage bien conçue produit une distribution uniforme des valeurs hachées et réduit le nombre de conflits, où est réputé un conflit se produit lorsque les valeurs de clés séparées sont mappées vers la même valeur hachée.Dans le pire des cas, la version incorrecte possible fonction de hachage, le nombre d'opérations est proportionnel au nombre d'éléments dans la séquence (temps linéaire).

Le hash_multiset doit être le conteneur du tableau associatif lorsque les conditions associant les valeurs avec leurs clés sont contenu par l'application.Les éléments d'un hash_multiset peuvent être plusieurs et le sert de leurs propres clés de tri, de clés ne sont pas unique.Un modèle pour ce type de structure est une liste triée par exemple des mots dans les mots peuvent se produire plusieurs fois.Plusieurs occurrences des mots n'avaient pas été autorisées, puis un hash_set aurait été la structure appropriée du conteneur.Si seules de définitions étaient liées comme valeurs à la liste de mots clés uniques, un hash_map est une structure appropriée pour contenir les données.Si à la place les définitions n'étaient pas uniques, un hash_multimap est le conteneur du tableau.

Le hash_multiset classe la séquence qu'il contrôle en appelant un objet Ctraits 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 objethash_compare*<Key de classe,* less*<Key> >.* Spécifiquement, car toute la clé de valeurs de type Key, l'appel Trait(clés) donne une distribution des valeurs de type size_t.

En général les éléments doivent être simplement moins que comparables pour générer cette commande : afin que, avec deux éléments quelconques, il puisse déterminer l'un ou l'autre qu'ils sont équivalents (dans le sens que ni l'un ni l'autre n'est inférieure à l'autre) ou qu'il est inférieure à l'autre.Cela provoque le classement entre les éléments d'inégalité.En plus de la note technique, la fonction de comparaison est un attribut binaire qui induit le classement faible strict dans le sens mathématiques standard.Un attribut fbinaire (x,*y)*est un objet de fonction qui a deux objets d'argument coordonnées et une valeur de retour de la valeur true ou false.Le classement imposé à un hash_multiset est faible l'ordre strict si l'attribut binaire est irréflexif, antisymétrique, et transitif et si l'équivalence est transitive, où deux objets X et y sont définis pour être équivalents lorsque les deux f(x,*y)*et f(x,y) sont fictifs.Si l'état plus fort de l'égalité entre les clés remplace celui de l'équivalence, le classement est total (dans le sens que tous les éléments sont triés par rapport à l'autre) et les clés correspondance seront imperceptibles entre eux.

La commande réelle d'éléments dans l'ordre d'exécution des instructions dépend de la fonction de hachage, de la fonction classante, et la taille actuelle de la table de hachage stockée dans l'objet conteneur.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 l'ordre d'exécution des instructions.Insertion des éléments n'invalide pas d'itérateur, et supprime des éléments invalide uniquement les itérateurs qui avaient spécifiquement pointe vers des éléments supprimés.

L'itérateur fourni par la classe de hash_multiset est un itérateur bidirectionnel, mais le membre de classe s'exécute insertion et hash_multiset ont des versions qui prennent comme paramètre de modèle un itérateur d'entrée plus faible, dont les spécifications de fonctionnalités sont plus minimales que celles garanties par la classe les itérateurs bidirectionnelles.Les différents concepts d'itérateur forment une famille associée par des améliorations dans leurs fonctionnalités.Chaque concept d'itérateur a son propre hash_multiset des spécifications, et les algorithmes qui fonctionnent avec elles la limite de nécessité les hypothèses aux spécifications fournies par ce type d'itérateur.Il peut supposer 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 dans la séquence.Il s'agit d'un hash_multiset minimal de fonctionnalité, mais il est asse'à pouvoir parler clairement à propos d'une plage des 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 de <hash_map> et de <hash_set> ne sont plus dans l'espace de noms de DST, mais plutôt ont été déplacés dans l'espace de noms de stdext.Pour plus d'informations, consultez The stdext Namespace.

Constructeurs

hash_multiset

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

Typedef

allocator_type	Un type qui représente la classe d' allocator pour l'objet d' hash_multiset .
const_iterator	Un type qui fournit un itérateur bidirectionnel qui peut lire un élément d' const dans hash_multiset.
const_pointer	Un type qui fournit un pointeur vers un élément de const dans hash_multiset.
const_reference	Un type qui fournit une référence à un élément d' const stocker dans hash_multiset pour lire et effectuer des opérations d' const .
const_reverse_iterator	Un type qui fournit un itérateur bidirectionnel qui peut lire un élément d' const dans hash_multiset.
difference_type	Un type d'entier signé qui fournit la différence entre deux itérateurs qui répondent à des éléments dans le même hash_multiset.
itérateur	Un type qui fournit un itérateur bidirectionnel qui peut lire ou modifier un élément dans hash_multiset.
key_compare	Un type qui fournit un objet de fonction qui peut comparer deux clés de tri pour déterminer la commande relative de deux éléments dans hash_multiset.
key_type	Un type qui décrit un objet stocké comme un élément d' hash_set dans sa qualité de clé de tri.
pointer	Un type qui fournit un pointeur vers un élément dans hash_multiset.
référence	Un type qui fournit une référence à un élément stocker dans hash_multiset.
reverse_iterator	Un type qui fournit un itérateur bidirectionnel qui peut lire ou modifier un élément dans hash_multisetinversé.
size_type	Un type d'entier non signé qui peut représenter le nombre d'éléments dans hash_multiset.
value_compare	Un type qui fournit deux objets de fonction, un attribut binaire de classe comparaison qui peut comparer deux valeurs d'élément d' hash_multiset pour déterminer leur commande relative et un attribut qui unaire hache les éléments.
value_type	Un type qui décrit un objet stocké comme un élément d' hash_multiset dans sa qualité de valeur.

Fonctions membres

begin	Retourne un itérateur qui traite le premier élément de hash_multiset.
hash_multiset::cbegin	Retourne un itérateur const adressant le premier élément de hash_multiset.
hash_multiset::cend	Retourne un itérateur const qui traite l'emplacement réussissant le dernier élément de hash_multiset.
clear	Efface tous les éléments d' hash_multiset.
count	Retourne le nombre d'éléments dans hash_multiset dont la clé correspond à une clé spécifiée paramètre-
hash_multiset::crbegin	Retourne un itérateur const adressant le premier élément de hash_multisetinversé.
hash_multiset::crend	Retourne un itérateur const qui traite l'emplacement réussissant le dernier élément de hash_multisetinversé.
hash_multiset::emplace	Insère un élément construit en place dans hash_multiset.
hash_multiset::emplace_hint	Insère un élément construit en place dans hash_multiset, avec un indicateur de positionnement.
empty	Teste si hash_multiset est vide.
end	Retourne un itérateur qui traite l'emplacement réussissant le dernier élément de hash_multiset.
equal_range	Retourne une paire d'itérateurs respectivement au premier élément de hash_multiset avec une clé qui est supérieure à une clé spécifiée et au premier élément de hash_multiset avec une clé à laquelle est égal ou supérieur à la clé.
effacement	Supprime un élément ou une plage d'éléments dans hash_multiset des positions spécifiées ou supprime des éléments qui correspondent à une clé spécifiée.
find	Retourne un itérateur adressant l'emplacement d'un élément dans hash_multiset qui a une clé équivalente à une clé spécifiée.
get_allocator	Retourne une copie de l'objet d' allocator utilisé pour construire hash_multiset.
insertion	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é à des clés de commande dans hash_multiset.
lower_bound	Retourne un itérateur au premier élément de hash_multiset avec une clé à laquelle est égal ou supérieur une clé spécifiée.
max_size	Retourne la longueur maximale d' hash_multiset.
rbegin	Retourne un itérateur adressant le premier élément de hash_multisetinversé.
rend	Retourne un itérateur qui traite l'emplacement réussissant le dernier élément de hash_multisetinversé.
taille	Retourne le nombre d'éléments dans hash_multiset.
échange	Permute les éléments de deux hash_multisetS.
upper_bound	Retourne un itérateur au premier élément de hash_multiset qui avec une clé à laquelle est égal ou supérieur une clé spécifiée.
value_comp	Extrait une copie de l'objet Ctraits de hachage utilisé pour hacher et classer les valeurs de clés d'élément dans hash_multiset.