hash_map, classe

Article
06/09/2015

Notes

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

Stocke et récupère 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

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

Notes

Le mappage du code de hachage 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.
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.
Un conteneur paire-associatif, car ses valeurs d'éléments sont séparées de ses valeurs de clés.
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 mappage de code hachage, mais pas sa valeur de clé associée, peut être modifiée 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 doivent être associées avec les nouveaux éléments insérés.

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 mappage du code de hachage doit être le conteneur associatif du choix lorsque les conditions associant les valeurs à 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 se produisant une unique fois avec des valeurs de chaîne associées fournissant par exemple des définitions. Si, en revanche, les mots ont plusieurs définitions correcte, et donc que les clés n'ont pas été uniques, alors un multi-mappage du code de hachage sera le conteneur choisi. Si, en revanche, juste la liste de mots a été stockée, un set de hachage serait le conteneur approprié. Si de multiples occurrences des mots sont autorisées, alors un code de hachage multiset sera la structure appropriée du conteneur.

Le mappage du code de hachage classe la séquence qu'il contrôle en appelant un objet stocké de hachage Traits de la 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 la 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 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 une fonction objet qui a deux arguments objets x et y , et une valeur de retour de true ou de false. Une commande appliquée à un mappage de code de hachage 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 mappage de code de hachage est un itérateur bidirectionnel, mais les fonctions membres de classe insertion et mappage 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 ensemble 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 jeu 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_map

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

Typedef

allocator_type	Un type qui représente la classe allocator pour l'objet hash_map .
const_iterator	Un type qui fournit un itérateur bidirectionnel capable de lire un élément const dans hash_map.
const_pointer	Un type qui fournit un pointeur vers un élément const dans hash_map.
const_reference	Un type qui fournit une référence à un élément const stocké dans hash_map 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_map.
difference_type	Un type d'entier signé qui peut être utilisé pour représenter le nombre d'éléments d'une hash_map dans une plage entre les éléments indiqués par des itérateurs.
itérateur	Un type qui fournit un itérateur bidirectionnel capable de lire ou de modifier tout élément dans une hash_map.
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_map.
key_type	Un type décrit l'objet clé trié qui constitue chaque élément d'une hash_map.
mapped_type	Un type qui représente le type de données stocké dans une hash_map.
pointer	Un type qui fournit un pointeur à un élément dans une hash_map.
référence	Un type qui fournit une référence à un élément stocké dans une hash_map.
reverse_iterator	Un type qui fournit un itérateur bidirectionnel capable de lire ou modifier tout élément dans une hash_map inversée.
type_taille	Un type d'entier non signé qui peut représenter le nombre d'éléments dans une hash_map.
type valeur	Un type qui fournit une fonction objet qui peut comparer deux éléments comme des clés triées pour déterminer leur ordre relatif dans la hash_map.

Fonctions membres

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

Opérateurs

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