hash_set, classe

Article
06/09/2015

Notes

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

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

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 de l'élément à stocker dans le hash_set.
Traits
Type qui contient deux objets de fonction, un de la classe et qui est un attribut binaire peut comparer deux valeurs de l'élément comme clés de tri pour déterminer leur ordre relatif et une fonction de hachage qui est valeur de clé unaire d'un mappage de l'attribut des éléments des entiers non signés de type size_t. Cet argument est facultatif, et lahash_compare*<clé,* less*<clé>>* est la valeur par défaut.
Allocator
Type qui représente l'objet d'allocation stockée qui encapsule les informations sur l'allocation et la désallocation de hash_set de la mémoire. Cet argument est facultatif ; la valeur par défaut est laallocator*<clé>.*

Notes

Le hash_set 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. De plus, il s'agit d'un conteneur associatif simple car ses valeurs d'élément sont la valeur de clé.
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. Étant donné que le hash_set est également un conteneur associatif simple, les éléments sont également uniques.
Une classe de modèle car la fonctionnalité elle fournit est générique et donc indépendantes du type de données spécifique contenu en tant qu'é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 jeu ne peut être modifiée directement. Au lieu de cela, vous devez supprimer les anciennes valeurs et les éléments d'insertion avec les nouvelles valeurs.

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 hash_set doit être le conteneur du tableau associatif si les conditions associant les valeurs avec leurs clés sont de contenu par l'application. Les éléments d'un hash_set sont uniques et servir 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 lesquels les mots peuvent se produire une seule fois. Si de multiples occurrences des mots sont autorisées, alors un code de hachage multiset sera 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 les clés ne sont pas uniques, un hash_multimap est le conteneur du tableau.

La classe hash_set la séquence qu'il contrôle en appelant un objet stockées de Caractéristiques de hachage de type value_compare. Cet objet stocké est accessible en appelant la fonction membre key_comp. Ce objet de la fonction doit se comporte de la même manière qu'un objet de hash_compareKey de la classe<, less<Key>>. En particulier, car toutes les valeurs _Key de type, la caractéristique d'appel (_Key ) génère une distribution des valeurs de size_t de type.

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 attribut fbinaire (x,*y)*est un objet de la fonction qui a deux objets d'argument X et y et une valeur de retour de la valeur true ou false. Classement appliqué à un hash_set est faible ordre strict si l'attribut est irréflexif binaire, antisymétrique, et transitif et si l'équivalence est transitive, où deux objets X et y sont définis pour être identiques lorsque les deux f(x,y) et f(y,x) est false. 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 hash_set est un itérateur bidirectionnelle, mais le membre de la classe fonctionne insertion et hash_set ont des versions prenant comme paramètres du modèle à un itérateur d'entrée plus faible, dont les spécifications des fonctionnalités sont plus faibles que celles garanties par la classe les 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. Il s'agit d'un ensemble minimal des fonctionnalités, mais il est asse'à pouvoir communiquer clairement sur une plage des itérateurs [_First, _Last) dans le contexte des fonctions de membre de la 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_set

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

Typedef

allocator_type	Un type qui représente la classe allocator pour l'objet hash_set .
const_iterator	Un type qui fournit un itérateur bidirectionnel capable de lire un élément const dans hash_set.
const_pointer	Un type qui fournit un pointeur vers un élément const dans hash_set.
const_reference	Un type qui fournit une référence à un élément const stocké dans hash_set 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_set.
difference_type	Un type d'entier signé qui peut être utilisé pour représenter le nombre d'éléments d'une hash_set 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_set.
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_set.
key_type	Type qui décrit un objet stocké en tant qu'élément d'hash_set dans sa qualité de clé de tri.
pointer	Un type qui fournit un pointeur à un élément dans une hash_set.
référence	Un type qui fournit une référence à un élément stocké dans une hash_set.
reverse_iterator	Un type qui fournit un itérateur bidirectionnel capable de lire ou modifier tout élément dans une hash_set inversée.
type_taille	Un type d'entier non signé qui peut représenter le nombre d'éléments dans une hash_set.
value_compare	Type qui fournit deux objets de fonction, un attribut binaire de la classe et qui peut comparer deux valeurs d'élément d'hash_set déterminer leur ordre relatif et un attribut unaire qui hache les éléments.
type valeur	Type qui décrit un objet stocké en tant qu'élément d'hash_set dans sa qualité de valeur.

Fonctions membres

begin	Retourne un itérateur qui répond le premier élément dans hash_set.
hash_set::cbegin	Retourne un itérateur constant adressant le premier élément dans la hash_set.
hash_set::cend	Retourne un itérateur constant qui adresse l'emplacement succédant au dernier élément dans une hash_set.
clear	Efface tous les éléments d'une hash_set.
count	Retourne le nombre d'éléments dans une hash_set dont la clé correspond à une clé à paramètre spécifié.
hash_set::crbegin	Retourne un itérateur const adressant le premier élément dans une hash_set inversée.
hash_set::crend	Retourne un itérateur const qui s'adresse à l'emplacement suivant le dernier élément dans une hash_set inversée.
hash_set::emplace	Insère un élément construit sur place dans une hash_set.
hash_set::emplace_hint	Insère un élément construit sur place dans une hash_set, avec un indicateur de positionnement.
empty	Teste si une hash_set est vide.
end	Retourne un itérateur qui s'adresse à l'emplacement suivant le dernier élément dans une hash_set.
equal_range	Retourne une paire d'itérateurs respectivement au premier élément dans hash_set avec une clé qui est supérieure à la clé spécifiée et le premier élément dans hash_set avec une clé à laquelle est égal ou supérieur à la clé.
effacer	Supprime un élément ou une plage des éléments dans hash_set les positions spécifiées ou supprimer les éléments qui correspondent à la clé spécifiée.
find	Retourne un itérateur adressant l'emplacement d'un élément dans une hash_set qui a une clé équivalente à une clé spécifiée.
get_allocator	Retourne une copie de l'objet allocator utilisé pour construire la hash_set.
insérer	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é pour mettre en ordre les clés dans une hash_set.
lower_bound	Retourne un itérateur au premier élément dans hash_set avec une clé à laquelle est supérieur ou égal à la clé spécifiée.
max_size	Retourne la longueur maximale de la hash_set.
rbegin	Retourne un itérateur s'adressant au premier élément d'une hash_set inversée.
rend	Retourne un itérateur qui adresse l'emplacement suivant le dernier élément d'une hash_set inversée.
taille	Retourne le nombre d'éléments figurant dans le hash_set.
échange	Échange les éléments de deux hash_set.
upper_bound	Retourne un itérateur au premier élément dans hash_set ayant une clé à laquelle est supérieur ou égal à la clé spécifiée.
value_comp	Extrait une copie de l'objet Ctraits de hachage utilisé pour hacher et signaler la valeur de clé de l'élément dans hash_set.