hash_set Class

Article
03/26/2013

[!REMARQUE]

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

Le hash_set de classe de conteneur est une extension du Standard Template Library (STL) et est utilisé pour le stockage et la recherche rapide des données d'une collection dans laquelle les valeurs des éléments contenus sont uniques et sert de valeurs clés.

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

Paramètres

Key
Le type de données d'élément à stocker dans le hash_set.
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_set de la mémoire.Cet argument est facultatif, et la valeur par défaut est allocator*<Key>.*

Notes

Le hash_set 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_set 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_set doit être le conteneur du tableau associatif lorsque les conditions associant les valeurs avec leurs clés sont satisfaites par l'application.Les éléments d'un hash_set sont uniques et sert de leurs propres clés de tri.Un modèle pour ce type de structure est une liste triée par exemple des mots dans les mots peuvent se produire une seule fois.Si vous permettait de plusieurs occurrences des mots, un hash_multiset est la structure appropriée du conteneur.Si les valeurs doivent être jointes à une liste de mots clés de clé unique, un hash_map est une structure appropriée pour contenir les données.Si à la place des clés ne sont pas uniques, un hash_multimap est le conteneur du tableau.

Le hash_set 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, car toutes les valeurs _Key de type clé, la fonctionnalité d'appel (_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_set 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_set est un itérateur bidirectionnel, mais le membre de classe s'exécute insertion et hash_set 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_set

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

Typedef

allocator_type	Un type qui représente la classe d' allocator pour l'objet d' hash_set .
const_iterator	Un type qui fournit un itérateur bidirectionnel qui peut lire un élément d' const dans hash_set.
const_pointer	Un type qui fournit un pointeur vers un élément de const dans hash_set.
const_reference	Un type qui fournit une référence à un élément d' const stocker dans hash_set 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_set.
difference_type	Un type d'entier signé qui peut être utilisé pour représenter le nombre d'éléments d' hash_set 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_set.
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_set.
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_set.
référence	Un type qui fournit une référence à un élément stocker dans hash_set.
reverse_iterator	Un type qui fournit un itérateur bidirectionnel qui peut lire ou modifier un élément dans hash_setinversé.
size_type	Un type d'entier non signé qui peut représenter le nombre d'éléments dans hash_set.
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_set 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_set dans sa qualité de valeur.

Fonctions membres

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