Comment utiliser unordered_set avec des types personnalisés?

Est-il nécessaire que je crée ma propre fonction de hachage pour les types personnalisés? Y at-il des valeurs par défaut que je peux utiliser avec unordered_set?

La bibliothèque standard contient les spécialisations de std::hash pour les types fondamentaux, pour les pointeurs et pour std::ssortingng (ou plutôt pour toutes les spécialisations de std::basic_ssortingng ).

Malheureusement, la bibliothèque ne contient pas la fonction de combinaison essentielle nouvelle-ancienne-ancienne, qui fait cependant partie de Boost, et que vous devez copier dans votre code:

 template  inline void hash_combine(std::size_t & seed, const T & v) { std::hash hasher; seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2); } 

Avec cette fonction, vous pouvez hacher des paires, des n-uplets, des tableaux et tout type d’ éventail d’éléments eux-mêmes pouvant être hachés. Parcourez les sources Boost pour de nombreux exemples et implémentations utiles. Et évidemment, vous pouvez utiliser cette fonction pour créer une fonction de hachage pour vos propres types. Par exemple, voici un hachage d’une paire:

 template struct pair_hash> { inline std::size_t operator()(const std::pair & v) const { std::size_t seed = 0; hash_combine(seed, v.first); hash_combine(seed, v.second); return seed; } }; 

Sachez cependant que la combinaison de hachage ne produit pas de bonnes valeurs de hachage. Les résultats ont de très mauvaises qualités statistiques (par exemple, il est très facile de créer des collisions de hachage). Un bon hachage doit pouvoir voir tous les bits d’entrée bruts et ne peut pas être factorisé par des hachages partiels. (C’est pourquoi il n’y a pas de meilleure solution dans la bibliothèque standard actuelle; personne n’a été en mesure de proposer une conception satisfaisante.)

Oui, vous devrez écrire votre propre fonction de hachage. Ce n’est pas aussi grave que cela en a l’air: si votre classe a un membre hashable que vous savez raisonnablement unique, vous pouvez simplement retourner le hachage de ce membre.

Vous pouvez fournir ce hachage en spécialisant std::hash ou en transmettant explicitement la classe de hachage en tant que paramètre de modèle.