C ++ unordered_map utilisant un type de classe personnalisé comme clé

286

J'essaie d'utiliser une classe personnalisée comme clé pour un unordered_map, comme suit:

#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

class node;
class Solution;

class Node {
public:
    int a;
    int b; 
    int c;
    Node(){}
    Node(vector<int> v) {
        sort(v.begin(), v.end());
        a = v[0];       
        b = v[1];       
        c = v[2];       
    }

    bool operator==(Node i) {
        if ( i.a==this->a && i.b==this->b &&i.c==this->c ) {
            return true;
        } else {
            return false;
        }
    }
};

int main() {
    unordered_map<Node, int> m;    

    vector<int> v;
    v.push_back(3);
    v.push_back(8);
    v.push_back(9);
    Node n(v);

    m[n] = 0;

    return 0;
}

Cependant, g ++ me donne l'erreur suivante:

In file included from /usr/include/c++/4.6/string:50:0,
                 from /usr/include/c++/4.6/bits/locale_classes.h:42,
                 from /usr/include/c++/4.6/bits/ios_base.h:43,
                 from /usr/include/c++/4.6/ios:43,
                 from /usr/include/c++/4.6/ostream:40,
                 from /usr/include/c++/4.6/iostream:40,
                 from 3sum.cpp:4:
/usr/include/c++/4.6/bits/stl_function.h: In member function bool std::equal_to<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = Node]’:
/usr/include/c++/4.6/bits/hashtable_policy.h:768:48:   instantiated from bool std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, std::__detail::_Default_ranged_hash, false>::_M_compare(const _Key&, std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, std::__detail::_Default_ranged_hash, false>::_Hash_code_type, std::__detail::_Hash_node<_Value, false>*) const [with _Key = Node, _Value = std::pair<const Node, int>, _ExtractKey = std::_Select1st<std::pair<const Node, int> >, _Equal = std::equal_to<Node>, _H1 = std::hash<Node>, _H2 = std::__detail::_Mod_range_hashing, std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, std::__detail::_Default_ranged_hash, false>::_Hash_code_type = long unsigned int]’
/usr/include/c++/4.6/bits/hashtable.h:897:2:   instantiated from std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Node* std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_M_find_node(std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Node*, const key_type&, typename std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Hash_code_type) const [with _Key = Node, _Value = std::pair<const Node, int>, _Allocator = std::allocator<std::pair<const Node, int> >, _ExtractKey = std::_Select1st<std::pair<const Node, int> >, _Equal = std::equal_to<Node>, _H1 = std::hash<Node>, _H2 = std::__detail::_Mod_range_hashing, _Hash = std::__detail::_Default_ranged_hash, _RehashPolicy = std::__detail::_Prime_rehash_policy, bool __cache_hash_code = false, bool __constant_iterators = false, bool __unique_keys = true, std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Node = std::__detail::_Hash_node<std::pair<const Node, int>, false>, std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::key_type = Node, typename std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Hash_code_type = long unsigned int]’
/usr/include/c++/4.6/bits/hashtable_policy.h:546:53:   instantiated from std::__detail::_Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::mapped_type& std::__detail::_Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::operator[](const _Key&) [with _Key = Node, _Pair = std::pair<const Node, int>, _Hashtable = std::_Hashtable<Node, std::pair<const Node, int>, std::allocator<std::pair<const Node, int> >, std::_Select1st<std::pair<const Node, int> >, std::equal_to<Node>, std::hash<Node>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, false, false, true>, std::__detail::_Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::mapped_type = int]’
3sum.cpp:149:5:   instantiated from here
/usr/include/c++/4.6/bits/stl_function.h:209:23: error: passing const Node as this argument of bool Node::operator==(Node)’ discards qualifiers [-fpermissive]
make: *** [threeSum] Error 1

Je suppose que j'ai besoin de dire à C ++ comment hacher la classe Node, cependant, je ne sais pas trop comment le faire. Comment puis-je accomplir ces tâches?

Alfred Zhong
la source
2
Le troisième argument de modèle est la fonction de hachage que vous devez fournir.
chrisaycock
4
cppreference a un exemple simple et pratique de la façon de procéder: en.cppreference.com/w/cpp/container/unordered_map/unordered_map
jogojapan

Réponses:

488

Pour pouvoir utiliser std::unordered_map(ou l'un des autres conteneurs associatifs non ordonnés) avec un type de clé défini par l'utilisateur, vous devez définir deux choses:

  1. Une fonction de hachage ; il doit s'agir d'une classe qui remplace operator()et calcule la valeur de hachage en fonction d'un objet de type clé. Une façon particulièrement simple de procéder consiste à spécialiser le std::hashmodèle pour votre type de clé.

  2. Une fonction de comparaison pour l'égalité ; cela est nécessaire car le hachage ne peut pas compter sur le fait que la fonction de hachage fournira toujours une valeur de hachage unique pour chaque clé distincte (c'est-à-dire qu'elle doit pouvoir gérer les collisions), elle a donc besoin d'un moyen de comparer deux clés données pour une correspondance exacte. Vous pouvez l'implémenter soit en tant que classe qui remplace operator(), soit en tant que spécialisation std::equal, ou - le plus simple de tous - en surchargeant operator==()votre type de clé (comme vous l'avez déjà fait).

La difficulté avec la fonction de hachage est que si votre type de clé se compose de plusieurs membres, vous aurez généralement la fonction de hachage calculer les valeurs de hachage pour les membres individuels, puis les combiner en quelque sorte en une seule valeur de hachage pour l'objet entier. Pour de bonnes performances (c.-à-d. Peu de collisions), vous devez réfléchir soigneusement à la façon de combiner les valeurs de hachage individuelles pour vous assurer d’éviter d’obtenir trop souvent la même sortie pour différents objets.

Un assez bon point de départ pour une fonction de hachage est celui qui utilise le décalage de bits et XOR au niveau du bit pour combiner les valeurs de hachage individuelles. Par exemple, en supposant un type de clé comme celui-ci:

struct Key
{
  std::string first;
  std::string second;
  int         third;

  bool operator==(const Key &other) const
  { return (first == other.first
            && second == other.second
            && third == other.third);
  }
};

Voici une fonction de hachage simple (adaptée de celle utilisée dans l' exemple cppreference pour les fonctions de hachage définies par l'utilisateur ):

namespace std {

  template <>
  struct hash<Key>
  {
    std::size_t operator()(const Key& k) const
    {
      using std::size_t;
      using std::hash;
      using std::string;

      // Compute individual hash values for first,
      // second and third and combine them using XOR
      // and bit shifting:

      return ((hash<string>()(k.first)
               ^ (hash<string>()(k.second) << 1)) >> 1)
               ^ (hash<int>()(k.third) << 1);
    }
  };

}

Avec cela en place, vous pouvez instancier un std::unordered_mappour le type de clé:

int main()
{
  std::unordered_map<Key,std::string> m6 = {
    { {"John", "Doe", 12}, "example"},
    { {"Mary", "Sue", 21}, "another"}
  };
}

Il sera automatiquement utilisé std::hash<Key>comme défini ci-dessus pour les calculs de valeur de hachage, et operator==défini comme fonction membre de Keypour les contrôles d'égalité.

Si vous ne souhaitez pas spécialiser le modèle dans l' stdespace de noms (bien que cela soit parfaitement légal dans ce cas), vous pouvez définir la fonction de hachage en tant que classe distincte et l'ajouter à la liste des arguments de modèle pour la carte:

struct KeyHasher
{
  std::size_t operator()(const Key& k) const
  {
    using std::size_t;
    using std::hash;
    using std::string;

    return ((hash<string>()(k.first)
             ^ (hash<string>()(k.second) << 1)) >> 1)
             ^ (hash<int>()(k.third) << 1);
  }
};

int main()
{
  std::unordered_map<Key,std::string,KeyHasher> m6 = {
    { {"John", "Doe", 12}, "example"},
    { {"Mary", "Sue", 21}, "another"}
  };
}

Comment définir une meilleure fonction de hachage? Comme indiqué ci-dessus, la définition d'une bonne fonction de hachage est importante pour éviter les collisions et obtenir de bonnes performances. Pour un bien réel, vous devez prendre en compte la distribution des valeurs possibles de tous les champs et définir une fonction de hachage qui projette cette distribution dans un espace de résultats possibles aussi large et uniformément distribué que possible.

Cela peut être difficile; la méthode XOR / bit-shifting ci-dessus n'est probablement pas un mauvais début. Pour un démarrage légèrement meilleur, vous pouvez utiliser le modèle de fonction hash_valueet hash_combinede la bibliothèque Boost. Le premier agit de la même manière que std::hashpour les types standard (récemment, il inclut également des tuples et d'autres types standard utiles); ce dernier vous aide à combiner des valeurs de hachage individuelles en une seule. Voici une réécriture de la fonction de hachage qui utilise les fonctions d'assistance Boost:

#include <boost/functional/hash.hpp>

struct KeyHasher
{
  std::size_t operator()(const Key& k) const
  {
      using boost::hash_value;
      using boost::hash_combine;

      // Start with a hash value of 0    .
      std::size_t seed = 0;

      // Modify 'seed' by XORing and bit-shifting in
      // one member of 'Key' after the other:
      hash_combine(seed,hash_value(k.first));
      hash_combine(seed,hash_value(k.second));
      hash_combine(seed,hash_value(k.third));

      // Return the result.
      return seed;
  }
};

Et voici une réécriture qui n'utilise pas de boost, mais utilise une bonne méthode de combinaison des hachages:

namespace std
{
    template <>
    struct hash<Key>
    {
        size_t operator()( const Key& k ) const
        {
            // Compute individual hash values for first, second and third
            // http://stackoverflow.com/a/1646913/126995
            size_t res = 17;
            res = res * 31 + hash<string>()( k.first );
            res = res * 31 + hash<string>()( k.second );
            res = res * 31 + hash<int>()( k.third );
            return res;
        }
    };
}
jogojapan
la source
11
Pouvez-vous expliquer pourquoi il est nécessaire de déplacer les bits KeyHasher?
Chani
46
Si vous ne décaliez pas les bits et que deux chaînes étaient identiques, le xor les ferait s'annuler. Ainsi, le hachage ("a", "a", 1) serait le même que le hachage ("b", "b", 1). L'ordre n'aurait pas d'importance, donc le hachage ("a", "b", 1) serait le même que le hachage ("b", "a", 1).
Buge
1
J'apprends juste le C ++ et une chose avec laquelle je lutte toujours est: Où mettre le code? J'ai écrit une std::hashméthode spécialisée pour ma clé comme vous l'avez fait. Je mets cela au fond de mon dossier Key.cpp mais je reçois l'erreur suivante: Error 57 error C2440: 'type cast' : cannot convert from 'const Key' to 'size_t' c:\program files (x86)\microsoft visual studio 10.0\vc\include\xfunctional. Je suppose que le compilateur ne trouve pas ma méthode de hachage? Dois-je ajouter quelque chose à mon fichier Key.h?
Ben
4
@Ben Le placer dans le fichier .h est correct. std::hashn'est pas en fait une structure, mais un modèle (spécialisation) pour une structure . Ce n'est donc pas une implémentation - elle sera transformée en implémentation lorsque le compilateur en aura besoin. Les modèles doivent toujours aller dans les fichiers d'en-tête. Voir aussi stackoverflow.com/questions/495021/…
jogojapan
3
@nightfury find()renvoie un itérateur, et cet itérateur pointe vers une "entrée" de la carte. Une entrée est std::pairconstituée d'une clé et d'une valeur. Donc, si vous le faites auto iter = m6.find({"John","Doe",12});, vous obtiendrez la clé iter->firstet la valeur (c'est-à-dire la chaîne "example") iter->second. Si vous voulez directement la chaîne, vous pouvez utiliser m6.at({"John","Doe",12})(qui lèvera une exception si la clé ne se termine pas), ou m6[{"John","Doe",12}](cela créera une valeur vide si la clé n'existe pas).
jogojapan
16

Je pense que le jogojapan a donné une très bonne et exhaustive réponse . Vous devriez définitivement y jeter un œil avant de lire mon article. Cependant, je voudrais ajouter ce qui suit:

  1. Vous pouvez définir une fonction de comparaison pour un unordered_mapséparément, au lieu d'utiliser l'opérateur de comparaison d'égalité ( operator==). Cela peut être utile, par exemple, si vous souhaitez utiliser ce dernier pour comparer tous les membres de deux Nodeobjets les uns aux autres, mais uniquement certains membres spécifiques comme clé d'un unordered_map.
  2. Vous pouvez également utiliser des expressions lambda au lieu de définir les fonctions de hachage et de comparaison.

Dans l'ensemble, pour votre Nodeclasse, le code pourrait être écrit comme suit:

using h = std::hash<int>;
auto hash = [](const Node& n){return ((17 * 31 + h()(n.a)) * 31 + h()(n.b)) * 31 + h()(n.c);};
auto equal = [](const Node& l, const Node& r){return l.a == r.a && l.b == r.b && l.c == r.c;};
std::unordered_map<Node, int, decltype(hash), decltype(equal)> m(8, hash, equal);

Remarques:

  • Je viens de réutiliser la méthode de hachage à la fin de la réponse de jogojapan, mais vous pouvez trouver l'idée d'une solution plus générale ici (si vous ne voulez pas utiliser Boost).
  • Mon code est peut-être un peu trop réduit. Pour une version légèrement plus lisible, veuillez consulter ce code sur Ideone .
klaxonner
la source
d'où viennent les 8 et qu'est-ce que cela signifie?
AndiChin
@WhalalalalalalaCHen: Veuillez consulter la documentation du unordered_mapconstructeur . Le 8représente le soi-disant "nombre de compartiments". Un compartiment est un emplacement dans la table de hachage interne du conteneur, voir par exemple unordered_map::bucket_countpour plus d'informations.
klaxonner le
@WhalalalalalalaCHen: J'ai choisi 8au hasard. Selon le contenu que vous souhaitez stocker dans votre unordered_map, le nombre de compartiments peut affecter les performances du conteneur.
klaxonner le