C++ unordered_map mit einer benutzerdefinierten Klassentyp als Schlüssel

Question

Ich versuche, eine benutzerdefinierte Klasse als Schlüssel für eine unordered_map zu verwenden, wie folgt:

#include 
#include 
#include 

using namespace std;

class node;
class Solution;

class Node {
public:
    int a;
    int b; 
    int c;
    Node(){}
    Node(vector 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 m;    

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

    m[n] = 0;

    return 0;
}

Allerdings bekomme ich von g++ den folgenden Fehler:

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, _ExtractKey = std::_Select1st >, _Equal = std::equal_to, _H1 = std::hash, _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, _Allocator = std::allocator >, _ExtractKey = std::_Select1st >, _Equal = std::equal_to, _H1 = std::hash, _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, false>, std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey...
/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, _Hashtable = std::_Hashtable, std::allocator >, std::_Select1st >, std::equal_to, std::hash, 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

Ich vermute, dass ich C++ sagen muss, wie die Klasse Node gehasht werden soll, bin mir jedoch nicht ganz sicher, wie ich das machen soll. Wie kann ich diese Aufgabe erfüllen?

Answer 1

Um std::unordered_map (oder einen der anderen ungeordneten assoziativen Container) mit einem benutzerdefinierten Schlüsseltyp verwenden zu können, müssen Sie zwei Dinge definieren:

1. Eine Hashfunktion; dies muss eine Klasse sein, die operator() überschreibt und den Hashwert für ein Objekt des Schlüsseltyps berechnet. Eine besonders einfache Möglichkeit, dies zu tun, besteht darin, die Vorlage std::hash für Ihren Schlüsseltyp zu spezialisieren.

2. Eine Vergleichsfunktion für die Gleichheit; diese ist erforderlich, da der Hash nicht darauf vertrauen kann, dass die Hashfunktion immer einen eindeutigen Hashwert für jeden unterschiedlichen Schlüssel liefert (d. h., er muss mit Kollisionen umgehen können), sodass er eine Möglichkeit benötigt, um zwei gegebene Schlüssel auf eine genaue Übereinstimmung zu vergleichen. Sie können dies entweder als eine Klasse implementieren, die operator() überschreibt, oder als Spezialisierung von std::equal, oder - am einfachsten von allen - durch das Überladen von operator==() für Ihren Schlüsseltyp (wie Sie es bereits getan haben).

Die Schwierigkeit bei der Hashfunktion besteht darin, dass, wenn Ihr Schlüsseltyp aus mehreren Elementen besteht, die Hashfunktion in der Regel Hashwerte für die einzelnen Elemente berechnet und diese dann auf irgendeine Weise zu einem Hashwert für das gesamte Objekt kombiniert. Für eine gute Leistung (d. h. wenige Kollisionen) sollten Sie sorgfältig darüber nachdenken, wie Sie die einzelnen Hashwerte kombinieren, um sicherzustellen, dass Sie nicht zu oft dasselbe Ergebnis für verschiedene Objekte erhalten.

Ein ziemlich guter Ausgangspunkt für eine Hashfunktion ist eine, die Bitverschiebungen und Bitweises XOR zum Kombinieren der einzelnen Hashwerte verwendet. Angenommen, Sie haben einen Schlüsseltyp wie diesen:

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 Hashfunktion (angepasst von der, die im cppreference-Beispiel für benutzerdefinierte Hashfunktionen verwendet wird):

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

    // Berechnen Sie einzelne Hashwerte für first,
    // second und third und kombinieren Sie diese unter Verwendung von XOR
    // und Bitverschiebung:

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

Mit diesem können Sie eine std::unordered_map für den Schlüsseltyp instanziieren:

int main()
{
  std::unordered_map m6 = {
    { {"John", "Doe", 12}, "Beispiel"},
    { {"Mary", "Sue", 21}, "ein weiteres"}
  };
}

Es wird automatisch std::hash für die Hashwertberechnungen verwendet, wie oben definiert, und der als Elementfunktion von Key definierte operator== für Gleichheitsprüfungen.

Wenn Sie die Vorlage im std-Namespace nicht spezialisieren möchten (obwohl dies in diesem Fall vollkommen legal ist), können Sie die Hashfunktion als separate Klasse definieren und sie der Vorlagenargumentliste für die Map hinzufügen:

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

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

int main()
{
  std::unordered_map m6 = {
    { {"John", "Doe", 12}, "Beispiel"},
    { {"Mary", "Sue", 21}, "ein weiteres"}
  };
}

Wie definiert man eine bessere Hashfunktion? Wie bereits erwähnt, ist es wichtig, eine gute Hashfunktion zu definieren, um Kollisionen zu vermeiden und eine gute Leistung zu erzielen. Für eine wirklich gute benötigen Sie eine Hashfunktion, die die Verteilung der möglichen Werte aller Felder berücksichtigt und eine Hashfunktion definiert, die diese Verteilung in einen Raum möglicher Ergebnisse projiziert, der so breit und gleichmäßig wie möglich ist.

Dies kann schwierig sein; Die oben genannte XOR-/Bitverschiebungsmethode ist wahrscheinlich kein schlechter Anfang. Für einen etwas besseren Ansatz können Sie die Funktionenvorlagen hash_value und hash_combine aus der Boost-Bibliothek verwenden. Die erste verhält sich ähnlich wie std::hash für Standardtypen (vor kurzem auch für Tupel und andere nützliche Standardtypen); die letzte hilft Ihnen dabei, einzelne Hashwerte zu kombinieren. Hier ist eine Neufassung der Hashfunktion, die die Hilfsfunktionen von Boost verwendet:

#include 

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

      // Beginnen Sie mit einem Hashwert von 0.
      std::size_t seed = 0;

      // Modifizieren Sie 'seed', indem Sie unter Verwendung von XOR und Bitverschiebung nacheinander ein Element von 'Key' ändern:
      hash_combine(seed,hash_value(k.first));
      hash_combine(seed,hash_value(k.second));
      hash_combine(seed,hash_value(k.third));

      // Gehen Sie das Ergebnis zurück.
      return seed;
  }
};

Und hier ist eine Version, die Boost nicht verwendet, sondern eine gute Methode zur Kombination der Hashes verwendet:

template <>
struct std::hash
{
    std::size_t operator()( const Key& k ) const
    {
        // Berechnen Sie einzelne Hashwerte für first, second und third
        // http://stackoverflow.com/a/1646913/126995
        std::size_t res = 17;
        res = res * 31 + hash()( k.first );
        res = res * 31 + hash()( k.second );
        res = res * 31 + hash()( k.third );
        return res;
    }
};

Answer 2

Ich denke, dass jogojapan eine sehr gute und ausführliche Antwort gegeben hat. Sie sollten sie definitiv anschauen, bevor Sie meinen Beitrag lesen. Trotzdem möchte ich Folgendes hinzufügen:

1. Sie können eine Vergleichsfunktion für ein unordered_map separat definieren, anstatt den Gleichheitsvergleichsoperator (operator==) zu verwenden. Dies kann beispielsweise hilfreich sein, wenn Sie letzteres verwenden möchten, um alle Elemente zweier Node-Objekte miteinander zu vergleichen, aber nur einige spezifische Elemente als Schlüssel eines unordered_map zu verwenden.
2. Sie können auch Lambda-Ausdrücke anstelle der Definition der Hash- und Vergleichsfunktionen verwenden.

Alles in allem könnte der Code für Ihre Node-Klasse wie folgt aussehen:

using h = std::hash;
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 m(8, hash, equal);

Notizen:

• Ich habe einfach die Hashing-Methode am Ende von jogojapans Antwort wiederverwendet, aber Sie können die Idee für eine allgemeinere Lösung hier finden (wenn Sie Boost nicht verwenden möchten).
• Mein Code ist vielleicht etwas zu minifiziert. Für eine etwas lesbarere Version sehen Sie bitte diesen Code auf Ideone.

Answer 3

Der einfachste mögliche vollständige ausführbare Beispiel für das Verwenden einer benutzerdefinierten Klasse als Schlüssel für eine unordered_map (Grundimplementierung einer dünnen Matrix):

// UnorderedMapObjectAsKey.cpp

#include 
#include 
#include 

struct Pos
{
  int row;
  int col;

  Pos() { }
  Pos(int row, int col)
  {
    this->row = row;
    this->col = col;
  }

  bool operator==(const Pos& otherPos) const
  {
    if (this->row == otherPos.row && this->col == otherPos.col) return true;
    else return false;
  }

  struct HashFunction
  {
    size_t operator()(const Pos& pos) const
    {
      size_t rowHash = std::hash()(pos.row);
      size_t colHash = std::hash()(pos.col) << 1;
      return rowHash ^ colHash;
    }
  };
};

int main(void)
{
  std::unordered_map umap;

  // an Position 1, 2, Wert auf 5 setzen
  umap[Pos(1, 2)] = 5;

  // an Position 3, 4, Wert auf 10 setzen
  umap[Pos(3, 4)] = 10;

  // die umap ausgeben
  std::cout << "\n";
  for (auto& element : umap)
  {
    std::cout << "( " << element.first.row << ", " << element.first.col << " ) = " << element.second << "\n";
  }
  std::cout << "\n";

  return 0;
}

Answer 4

Für den Enum-Typ denke ich, dass dies ein geeigneter Weg ist, und der Unterschied zu Klassen besteht darin, wie der Hash-Wert berechnet wird.

template 
struct EnumTypeHash {
  std::size_t operator()(const T& type) const {
    return static_cast(type);
  }
};

enum MyEnum {};
class MyValue {};

std::unordered_map> map_;

Answer 5

STL bietet keine Hash-Funktionen für Paare an. Sie müssen sie selbst implementieren und entweder als Vorlagenparameter angeben oder in den Namespace std einfügen, von wo aus sie automatisch übernommen werden. Folgender https://github.com/HowardHinnant/hash_append/blob/master/n3876.h ist sehr nützlich für die Implementierung benutzerdefinierter Hash-Funktionen für Strukturen. Weitere Details werden in den anderen Antworten auf diese Frage gut erklärt, daher werde ich das nicht wiederholen. Im Boost gibt es auch etwas ähnliches (hash_combine).