C++ unordered_map utilizzando un tipo di classe personalizzata come la chiave

Question

Sto cercando di usare una classe personalizzata come la chiave per unordered_map, come il seguente,

#include <iostream> 
#include <algorithm> 
#include <unordered_map> 
//#include <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; 
} 

Credo che ho bisogno tell C++ come hash classe Node, tuttavia, non sono abbastanza sicuro di come farlo. C'è qualche esempio per questo tipo di attività?

È il seguente errore da g ++:

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 

Answer 1

Per poter utilizzare std::unordered_map (o uno degli altri contenitori associativi non ordinata) con una chiave di tipo definito dall'utente, è necessario definire due cose :

1. Un hash funzione; questa deve essere una classe che sostituisce operator() e calcola il valore hash assegnato a un oggetto del tipo di chiave. Un modo particolarmente semplice per farlo è quello di specializzare il modello std::hash per il tipo di chiave.

2. A funzione di confronto per l'uguaglianza; questo è richiesto perché l'hash non può fare affidamento sul fatto che la funzione di hash fornirà sempre un valore hash univoco per ogni chiave distinta (cioè, deve essere in grado di gestire le collisioni), quindi ha bisogno di un modo per confrontare due chiavi date per una corrispondenza esatta. È possibile implementarlo come classe che sostituisce operator() o come specializzazione di std::equal o – più semplice di tutti – sovraccaricando operator==() per il tipo di chiave (come già fatto).

La difficoltà con la funzione di hash è che se il vostro tipo di chiave è composta da diversi membri, di solito hanno i valori funzione hash calcolare hash per i singoli membri, e quindi in qualche modo combinarle in un unico valore hash per la intero oggetto. Per ottenere buone prestazioni (ad esempio, poche collisioni) è necessario riflettere attentamente su come combinare i singoli valori hash per evitare di ottenere lo stesso risultato per oggetti diversi troppo spesso.

Un punto di partenza abbastanza buono per una funzione di hash è uno che utilizza lo spostamento bit e XOR bit a bit per combinare i singoli valori hash. Ad esempio, ipotizzando un tipo chiave simili:

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); 
    } 
}; 

Ecco una semplice funzione hash (adattato da quello usato nella cppreference example for user-defined hash functions):

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); 
    } 
    }; 

} 

Con questo in luogo, è possibile creare un'istanza un std::unordered_map per il tipo chiave:

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

Si utilizzerà automaticamente std::hash<Key> come sopra definito per il calcolo del valore hash, e la operator== definito come funzione membro di Key per i controlli di uguaglianza.

Se non si desidera specializzarsi modello all'interno del std namespace (anche se è perfettamente legale in questo caso), è possibile definire la funzione hash come una classe separata e aggiungerlo alla lista di argomenti modello per la mappa:

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"} 
    }; 
} 

Come definire una funzione di hash migliore? Come detto sopra, definire una buona funzione di hash è importante per evitare collisioni e ottenere buone prestazioni. Per fare un buon esempio è necessario prendere in considerazione la distribuzione dei possibili valori di tutti i campi e definire una funzione hash che proietta tale distribuzione in uno spazio di risultati possibili nel modo più ampio ed equamente distribuito possibile.

Questo può essere difficile; il metodo di spostamento XOR/bit di cui sopra non è probabilmente un brutto inizio. Per un avvio leggermente migliore, è possibile utilizzare il modello di funzione hash_value e hash_combine dalla libreria Boost. Il primo funziona in modo simile a std::hash per i tipi standard (recentemente include anche tuple e altri tipi standard utili); quest'ultimo ti aiuta a combinare singoli valori hash in uno. Qui è una riscrittura della funzione di hash che utilizza le funzioni Boost helper:

#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; 
    } 
}; 

Ed ecco una riscrittura che non utilizza spinta, ma usa buon metodo di combinare le hash:

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; 
     } 
    }; 
}