hash_map Class

Article
03/26/2013

[!REMARQUE]

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

Stocker et de récupérer des données rapidement d'une collection dans laquelle chaque élément est une paire qui a une clé de tri dont la valeur est 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_map

Paramètres

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

Notes

Le hash_map 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.
Unique dans le sens que chacun de ses éléments doit avoir une clé unique.
Un conteneur associatif de paires, car ses valeurs de données 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_map, 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_map 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 se produire uniquement des mots clés avec des valeurs de chaîne associées fournissant par exemple des définitions.Si, au lieu de cela, les mots avaient plusieurs définitions correcte, afin que les clés n'ont pas été uniques, un hash_multimap 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_map classe la séquence qu'il contrôle en appelant un objet Ctraits stocké de hachage de classe 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 classe hash_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 true ou de false.Le classement imposé à un hash_map 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_map est un itérateur bidirectionnel, mais le membre de classe s'exécute insertion et hash_map 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 possède son propre ensemble de 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.C'est un jeu 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_map

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

Typedef

allocator_type	Un type qui représente la classe d' allocator pour l'objet d' hash_map .
const_iterator	Un type qui fournit un itérateur bidirectionnel qui peut lire un élément d' const dans hash_map.
const_pointer	Un type qui fournit un pointeur vers un élément de const dans hash_map.
const_reference	Un type qui fournit une référence à un élément d' const stocker dans hash_map 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_map.
difference_type	Un type d'entier signé qui peut être utilisé pour représenter le nombre d'éléments d' hash_map 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_map.
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_map.
key_type	Un type décrit l'objet clé de tri qui constitue chaque élément d' hash_map.
mapped_type	Un type qui représente le type de données stockées dans hash_map.
pointer	Un type qui fournit un pointeur vers un élément dans hash_map.
référence	Un type qui fournit une référence à un élément stocker dans hash_map.
reverse_iterator	Un type qui fournit un itérateur bidirectionnel qui peut lire ou modifier un élément dans hash_mapinversé.
size_type	Un type d'entier non signé qui peut représenter le nombre d'éléments dans hash_map.
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_map.

Fonctions membres

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

Opérateurs

operator[]	Insère un élément dans hash_map avec une valeur de clé spécifiée.
hash_map::operator=	Remplace les éléments d' hash_map par une copie d'un autre hash_map.