Création d’unordered_set of unordered_set

J’ajoute encore une autre réponse à cette question car personne n’a encore abordé un point clé.

Tout le monde vous dit que vous devez créer une fonction de hachage pour unordered_set , ce qui est correct. Vous pouvez le faire en spécialisant std::hash> , ou vous pouvez créer votre propre foncteur et l’utiliser comme ceci:

 unordered_set, my_unordered_set_hash_functor> s; 

De toute façon, c’est bien. Cependant, il y a un gros problème que vous devez surveiller:

Pour tout deux unordered_set qui se comparent égaux ( x == y ), ils doivent utiliser un hachage identique: hash(x) == hash(y) . Si vous ne respectez pas cette règle, vous obtiendrez des erreurs d’exécution. Notez également que les deux éléments unordered_set suivants se comparent égaux (en utilisant le pseudo-code ici pour plus de clarté):

 {1, 2, 3} == {3, 2, 1} 

Par conséquent, hash({1, 2, 3}) doit être égal à hash({3, 2, 1}) . Autrement dit, les conteneurs non ordonnés ont un opérateur d’égalité où l’ordre n’a pas d’importance. Donc, quelle que soit la structure de votre fonction de hachage, son résultat doit être indépendant de l’ordre des éléments dans le conteneur.

Sinon, vous pouvez remplacer le prédicat d’égalité utilisé dans le unordered_set sorte qu’il respecte l’ordre:

 unordered_set, my_unordered_set_hash_functor, my_unordered_equal> s; 

Le fardeau d’obtenir tout cela correctement fait:

 unodered_set, my_set_hash_functor> 

l’air assez attrayant. Vous devez toujours créer un foncteur de hachage pour l’ set , mais vous n’avez maintenant plus à vous soucier d’obtenir le même code de hachage pour {1, 2, 3} et {3, 2, 1} . Au lieu de cela, vous devez vous assurer que ces codes de hachage sont différents.

Je remarque que la réponse de Walter donne un foncteur de hachage qui a le bon comportement: il ignore l’ordre dans le calcul du code de hachage. Mais alors sa réponse (actuellement) vous dit que ce n’est pas une bonne solution. 🙂 C’est en fait une bonne solution pour les conteneurs non ordonnés. Une solution encore meilleure serait de renvoyer la sum des hachages individuels au lieu de hacher la sum des éléments.

Vous pouvez le faire, mais comme tous unsorted_set/map types unsorted_set/map , le unsorted_set interne a maintenant besoin de définir une fonction de hachage. Il n’en a pas par défaut mais vous pouvez en écrire un vous-même.

Ce que vous devez faire est de définir un hachage approprié pour les clés de type std::unordered_set (puisque l’ operator== est déjà défini pour cette clé, vous n’avez pas besoin de fournir également le paramètre de modèle EqualKey pour std::unordered_set, Hash, EqualKey> .

Une option simple (bien qu’inefficace) consiste à hacher la sum totale de tous les éléments de l’ensemble. Cela ressemblerait à ceci:

 template struct hash_on_sum : private std::hash { typedef T::element_type count_type; typedef std::hash base; std::size_t operator()(T const&obj) const { return base::operator()(std::accumulate(obj.begin(),obj.end(),count_type())); } }; typedef std::unordered_set inner_type; typedef std::unordered_set> set_of_unique_sets; 

Cependant, bien que simple, ce n’est pas bon, car cela ne garantit pas l’exigence suivante. Pour deux parameters différents k1 et k2 qui ne sont pas égaux, la probabilité que std::hash()(k1) == std::hash()(k2) soit très faible, approche 1.0/std::numeric_limits::max() .

std::unordered_set> ne remplit pas l’exigence d’être un élément d’un std::unordered_set car il n’y a pas de fonction de hachage par défaut (ie, std::hash<> n’est pas spécialisé pour std::unordered_set> ).

vous pouvez en fournir un (il doit être rapide et éviter autant que possible les collisions):

 class MyHash { public: std::size_t operator()(const std::unordered_set& s) const { return ... // return some meaningful hash of the et elements } }; int main() { std::unordered_set, MyHash> u; } 

Vous pouvez voir de très bons exemples de fonctions de hachage dans cette réponse .

Vous devez vraiment fournir à la fois un hachage et une fonction d’égalité répondant à l’exigence standard d’un conteneur associatif non ordonné.

Hash () la fonction par défaut pour créer des hachages des éléments de votre ensemble ne sait pas comment traiter un ensemble entier en tant qu’élément. Créez une fonction de hachage qui crée une valeur unique pour chaque ensemble unique et vous êtes prêt à partir.

C’est le constructeur d’un unordered_set

explicit unordered_set( size_type bucket_count = /*implementation-defined*/, const Hash& hash = Hash(), const KeyEqual& equal = KeyEqual(), const Allocator& alloc = Allocator() ); http://en.cppreference.com/w/cpp/container/unordered_set/unordered_set

La chose la plus simple à faire est peut-être de créer une fonction de hachage pour votre unordered_set

 unsigned int my_hash(std::unordered_set& element) { for( e : element ) { some sort of math to create a unique hash for every unique set } } 

edit: comme vu dans une autre réponse, que j’ai complètement oubliée, la fonction de hachage doit être dans un object Hash. Au moins selon le constructeur que j’ai collé dans ma réponse.

Il y a une raison pour laquelle il n’y a pas de hachage à unordered_set . unordered_set est une séquence mutable par défaut. Un hachage doit conserver la même valeur tant que l’object est dans le unordered_set . Ainsi, vos éléments doivent être immuables. Cela n’est pas garanti en utilisant le modificateur const& , car il garantit uniquement que seul le unordered_set principal et ses méthodes ne modifieront pas le sous- unordered_set . Ne pas utiliser de référence pourrait être une solution sûre (vous devez toujours écrire la fonction de hachage), mais voulez-vous vraiment la surcharge de déplacer / copier des unordered_set s?

Vous pourriez plutôt utiliser une sorte de pointeur. C’est bon; un pointeur est uniquement une adresse mémoire et votre unordered_set lui-même ne se déplace pas (il peut réaffecter son pool d’éléments, mais qui s’en soucie?). Par conséquent, votre pointeur est constant et il peut conserver le même hachage pour sa durée de vie dans le unordered_set . ( EDIT : comme Howard l’a fait remarquer, vous devez vous assurer que tous les ordres que vous élémentez sont stockés pour votre ensemble. Si deux ensembles ont les mêmes éléments, ils sont considérés comme égaux. les ensembles correspondent à deux vecteurs égaux.)

En prime, vous pouvez maintenant utiliser un pointeur intelligent dans l’ensemble principal lui-même pour gérer la mémoire de sub- unordered_set si vous les avez alloués sur le tas.

Notez que ce n’est toujours pas votre implémentation la plus efficace pour obtenir une collection d’ensembles d’int. Pour créer des sous-ensembles, vous pouvez écrire un wrapper rapide autour de std::vector qui stocke l’int, classés par valeur. int int sont petits et peu coûteux à comparer, et l’utilisation d’une recherche dichotomique n’a qu’une complexité de O(log n) . Un std::unordered_set est une structure lourde et ce que vous perdez en passant de O(1) à O(log n) , vous le récupérez en disposant d’une mémoire compacte pour chaque ensemble. Cela ne devrait pas être trop difficile à mettre en œuvre, mais il est presque certain que les performances seront meilleures.

Une solution plus difficile à mettre en œuvre impliquerait un sortinge .