C++ unordered_map einer benutzerdefinierten Klassentyp als Schlüssel

Question

ich mit einer benutzerdefinierten Klasse als Schlüssel für unordered_map zu verwenden, ich versuche, wie die folgenden,

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

Ich glaube, ich das tell C benötigen ++ wie Klasse Knoten Hash, Ich bin mir jedoch nicht ganz sicher, wie ich das machen soll. Gibt es ein Beispiel für diese Art von Aufgaben?

Im folgenden wird der Fehler aus 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

der Lage sein zu verwenden std::unordered_map (oder einer der anderen ungeordneten assoziativen Container) mit einer benutzerdefinierten Schlüsseltyp, sie müssen zwei Dinge definieren, :

1. A Hashfunktion; Dies muss eine Klasse sein, die operator() überschreibt und den Hash-Wert für ein Objekt des Schlüsseltyps berechnet. Ein besonders einfacher Weg, dies zu tun, ist die std::hash Vorlage für Ihren Schlüsseltyp zu spezialisieren.

2. A Vergleichsfunktion für Gleichheit; Dies ist erforderlich, da sich der Hash nicht auf die Tatsache verlassen kann, dass die Hash-Funktion immer einen eindeutigen Hash-Wert für jeden einzelnen Schlüssel bereitstellt (dh er muss mit Kollisionen umgehen können), so dass er zwei gegebene Schlüssel vergleichen kann für eine genaue Übereinstimmung. Sie können dies entweder als eine Klasse implementieren, die operator() überschreibt, oder als Spezialisierung std::equal oder – am einfachsten – durch Überladen operator==() für Ihren Schlüsseltyp (wie Sie bereits getan haben).

Die Schwierigkeit bei der Hash-Funktion ist, dass, wenn Ihr Schlüsseltyp aus mehreren Mitgliedern besteht, werden Sie in der Regel die Hash-Funktion berechnet Hash-Werte für die einzelne Mitglieder haben, und sie dann irgendwie für die in einen Hash-Wert kombinieren gesamtes Objekt. Für eine gute Leistung (d. H. Wenige Kollisionen) sollten Sie sorgfältig darüber nachdenken, wie Sie die einzelnen Hash-Werte kombinieren, um sicherzustellen, dass Sie nicht zu oft die gleiche Ausgabe für verschiedene Objekte erhalten.

Ein ziemlich guter Ausgangspunkt für eine Hash-Funktion ist eine, die bit-shifting und bitweise XOR verwendet, um die einzelnen Hash-Werte zu kombinieren. Um zum Beispiel einen Schlüsseltyp wie dies unter der Annahme:

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

Hier ist eine einfache Hash-Funktion (von dem in der cppreference example for user-defined hash functions verwendet angepasst):

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

} 

In diesem Ort können Sie instanziiert ein std::unordered_map für den Schlüsseltyp:

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

Es wird std::hash<Key> automatisch verwendet, wie oben für die Hash-Wert-Berechnungen definiert, und die operator== definiert als Elementfunktion von Key für Gleichheitsprüfungen.

Wenn Sie keine Vorlage innerhalb des std Namespace spezialisieren wollen (obwohl es in diesem Fall vollkommen legal ist), können Sie die Hash-Funktion als eine separate Klasse definieren und an die für die Karte Template-Argument Liste hinzu:

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

Wie definiert man eine bessere Hash-Funktion? Wie oben gesagt, ist das Definieren einer guten Hash-Funktion wichtig, um Kollisionen zu vermeiden und eine gute Leistung zu erhalten. Für einen wirklich guten Wert müssen Sie die Verteilung der möglichen Werte aller Felder berücksichtigen und eine Hash-Funktion definieren, die diese Verteilung auf einen Raum mit möglichen Ergebnissen so weit und gleichmäßig verteilt wie möglich projiziert.

Dies kann schwierig sein; Die obige XOR/Bit-Shifting-Methode ist wahrscheinlich kein schlechter Start. Für einen etwas besseren Start können Sie die Funktionsschablone hash_value und hash_combine aus der Boost-Bibliothek verwenden. Ersteres verhält sich ähnlich wie std::hash für Standardtypen (neuerdings auch Tupel und andere nützliche Standardtypen); Letzteres hilft Ihnen, einzelne Hash-Werte zu einem zu kombinieren. Hier ist ein Umschreiben der Hash-Funktion, die die Boost-Helferfunktionen verwendet:

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

Und hier ist ein Umschreiben, die nicht boost nicht verwendet, verwendet noch gute Methode der Kombination den Hashes:

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