hash_multimap Class

Article
03/26/2013

[!REMARQUE]

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

Le hash_multimap 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 chaque élément est une paire qui a une clé de tri dont la valeur n'a pas besoin d'être unique et une valeur de données associée.

template <
   class Key, 
   class Type, 
   class Traits=hash_compare<Key, less<Key> >, 
   class Allocator=allocator<pair <const Key, Type> > 
>
class hash_multimap

Paramètres

Clé
Le type de données clés à stocker dans le hash_multimap.
Tapez
Le type de données d'élément à stocker dans le hash_multimap.
Traits
Le type qui inclut deux objets de fonction, un de classe Traits qui peut 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 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_multimap de la mémoire.Cet argument est facultatif, et la valeur par défaut est allocator*<*pair *<*const clé , Type> >.

Notes

Le hash_multimap 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.
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.
Multiple, car ses éléments n'ont pas besoin d'avoir des clés uniques, afin qu'une valeur de clé peut avoir plusieurs valeurs de données d'élément qui lui est associée.
Un conteneur associatif de paires, car ses valeurs d'élément sont séparées de ses valeurs de clés.
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 hash_multimap, mais pas sa valeur de clé associée, peut être modifié directement.À la place, les valeurs de clés associées aux éléments anciens doivent être supprimées et de nouvelles valeurs de clés être associées à de nouveaux éléments insérés.

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_multimap doit être le conteneur du tableau associatif lorsque les conditions associant les valeurs avec leurs clés sont satisfaites par l'application.Un modèle pour ce type de structure est une liste triée de mots clés avec des valeurs de chaîne associées fournissant par exemple des définitions, où les mots toujours n'ont pas été définis uniquement.Si, au lieu de cela, les mots clés ont été définis uniquement afin que les clés aient été uniques, un hash_map est le conteneur du tableau.Si, en revanche, juste la liste de mots ont été stockées, un hash_set est le conteneur approprié.Si vous permettait de plusieurs occurrences des mots, un hash_multiset est la structure appropriée du conteneur.

Le hash_multimap 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 objet de classehash_compare<Key, less*<Key> >.Spécifiquement, pour toutes les valeurs _Key de type Key, l'appel Traits(_Key)* 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_multimap 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_multimap est un itérateur bidirectionnel, mais le membre de classe s'exécute insertion et hash_multimap 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_multimap 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_multimap 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.

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_multimap

Construit une liste d'une taille particulière ou avec des éléments d'une valeur spécifique ou à allocator spécifique ou en tant que copie d'un autre hash_multimap.

Typedef

allocator_type	Un type qui représente la classe d' allocator pour l'objet d' hash_multimap .
const_iterator	Un type qui fournit un itérateur bidirectionnel qui peut lire un élément d' const dans hash_multimap.
const_pointer	Un type qui fournit un pointeur vers un élément de const dans hash_multimap.
const_reference	Un type qui fournit une référence à un élément d' const stocker dans hash_multimap 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_multimap.
difference_type	Un type d'entier signé qui peut être utilisé pour représenter le nombre d'éléments d' hash_multimap dans une plage entre les éléments a globale pointe vers les itérateurs.
itérateur	Un type qui fournit un itérateur bidirectionnel qui peut lire ou modifier un élément dans hash_multimap.
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_multimap.
key_type	Un type qui décrit l'objet clé de tri qui constitue chaque élément d' hash_multimap.
mapped_type	Un type qui représente le type de données stockées dans hash_multimap.
pointer	Un type qui fournit un pointeur vers un élément dans hash_multimap.
référence	Un type qui fournit une référence à un élément stocker dans hash_multimap.
reverse_iterator	Un type qui fournit un itérateur bidirectionnel qui peut lire ou modifier un élément dans hash_multimapinversé.
size_type	Un type d'entier non signé qui peut représenter le nombre d'éléments dans hash_multimap.
value_type	Un type qui fournit un objet de fonction qui peut comparer deux éléments comme clés de tri pour déterminer leur commande relative dans hash_multimap.

Fonctions membres

begin	Retourne un itérateur adressant le premier élément de hash_multimap.
hash_multimap::cbegin	Retourne un itérateur const adressant le premier élément de hash_multimap.
hash_multimap::cend	Retourne un itérateur const qui traite l'emplacement réussissant le dernier élément de hash_multimap.
clear	Efface tous les éléments d' hash_multimap.
count	Retourne le nombre d'éléments dans hash_multimap dont la clé correspond à une clé paramètre- spécifiée.
hash_multimap::crbegin	Retourne un itérateur const adressant le premier élément de hash_multimapinversé.
hash_multimap::crend	Retourne un itérateur const qui traite l'emplacement réussissant le dernier élément de hash_multimapinversé.
hash_multimap::emplace	Insère un élément construit en place dans hash_multimap.
hash_multimap::emplace_hint	Insère un élément construit en place dans hash_multimap, avec un indicateur de positionnement.
empty	Teste si hash_multimap est vide.
end	Retourne un itérateur qui traite l'emplacement réussissant le dernier élément de hash_multimap.
equal_range	Retourne un itérateur qui traite l'emplacement réussissant le dernier élément de hash_multimap.
effacement	Supprime un élément ou une plage d'éléments dans hash_multimap des positions spécifiées
find	Retourne un itérateur adressant l'emplacement d'un élément dans hash_multimap qui a une clé équivalente à une clé spécifiée.
get_allocator	Retourne une copie de l'objet d' allocator utilisé pour construire hash_multimap.
insertion	Insère un élément ou une plage d'éléments dans hash_multimap à une position spécifiée.
key_comp	Extrait une copie de l'objet de comparaison utilisé à des clés de commande dans hash_multimap.
lower_bound	Retourne un itérateur au premier élément de hash_multimap qui avec une valeur de clé à laquelle est égal ou supérieur à celui d'une clé spécifiée.
max_size	Retourne la longueur maximale d' hash_multimap.
rbegin	Retourne un itérateur adressant le premier élément de hash_multimapinversé.
rend	Retourne un itérateur qui traite l'emplacement réussissant le dernier élément de hash_multimapinversé.
taille	Spécifie une nouvelle taille pour hash_multimap.
échange	Permute les éléments de deux hash_multimapS.
upper_bound	Retourne un itérateur au premier élément de hash_multimap qui avec une valeur de clé supérieure à celle d'une clé spécifiée.
value_comp	Extrait une copie de l'objet de comparaison utilisé aux valeurs des éléments commandés dans hash_multimap.