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

Überprüfen Sie den folgenden Link https://www.geeksforgeeks.org/how-to-create-an-unordered_map-of-user-defined-class-in-cpp/ für weitere Details.

• Die benutzerdefinierte Klasse muss den == Operator implementieren
• Muss eine Hash-Funktion für die Klasse erstellen (für primitive Typen wie int und auch für Typen wie string ist die Hash-Funktion vordefiniert)

Answer 2

Die Antworten hier waren ziemlich hilfreich, aber ich hatte immer noch große Schwierigkeiten, das herauszufinden, also werden meine gewonnenen Erkenntnisse vielleicht nützlich sein. Ich hatte eine etwas einzigartige Situation im Vergleich zum OP; mein key war eine benutzerdefinierte UUID-Klasse die mir nicht gehörte. In dem, was ich als Bug/Fehlernutzung betrachte, definierte diese Klasse keine Hash-Funktion oder Überladung für operator() (sie definierte das operator==, also war ich dort gesetzt). Ja, ich hatte den Quellcode, aber er wurde weit verbreitet verteilt und kontrolliert, also war das Ändern davon kein Ausgangspunkt. Ich wollte diese UUID als Schlüssel in einem std::unordered_map Member verwenden, wie

std::unordered_map mapOfObjs_;

In Visual Studio habe ich schließlich auf diese Lösung geeinigt:

// Datei MyClass.h

namespace myNamespace
{
   static auto staticUuidHashFunc = [](const UUID& n)
   {
      // XOR der meisten und der am wenigsten signifikanten Bits, nicht wichtig
   }
   ... 
   class MyClass
   {
      ...
   private:
      std::unordered_map, decltype(staticUuidHashFunc)> mapOfObjs_;
   };
}

Dies hat in Windows großartig funktioniert. Allerdings habe ich, als ich meinen Code schließlich nach gcc in Linux gebracht habe, die Warnung erhalten (sinngemäß)

'MyClass' hat ein Feld 'mapOfObjs_', dessen Typ den anonymen Namespace verwendet

Ich habe diese Warnung sogar mit allen deaktivierten Warnungen erhalten, also muss gcc das als ziemlich ernsthaft betrachten. Ich habe im Internet recherchiert und diese Antwort gefunden, die vorgeschlagen hat, dass ich den Hash-Funktionscode in die .cpp-Datei verschieben muss.

In diesem Stadium habe ich auch versucht, von der UUID-Klasse abzuleiten:

// Datei MyClass.h

namespace myNamespace
{
   struct myUuid : public UUID
   {
      // Überladung des Operator()
   };
   ...
   // und ändere meine Map, um diesen Typ zu verwenden
   std::unordered_map> mapOfObjs_;
}

Dies brachte jedoch seine eigenen Probleme mit sich. Nämlich waren alle Teile des Codes, die die (jetzt übergeordnete) UUID-Klasse verwendeten, mit meiner Map nicht kompatibel, wie zum Beispiel:

void MyClass::FindUuid(const UUID& id)
{
   // funktioniert nicht, kann `id` nicht in einen `myUuid`-Typ umwandeln
   auto it = mapOfObjs_.find(id);
   ...
}

war jetzt kaputt. Ich wollte nicht den ganzen Code ändern, also habe ich das aufgeschoben und war wieder bei der "den Code in die .cpp-Datei setzen"-Lösung. Trotzdem habe ich hartnäckig ein paar Dinge ausprobiert, um die Hash-Funktion in der .h-Datei zu lassen. Mir ging es wirklich darum, das auto aus der Hash-Funktionsdefinition nicht zu entfernen, da ich den Typ nicht kannte und nicht herausfinden wollte, was er war. Also habe ich versucht:

class MyClass
{
   ...
private:
   static auto staticUuidHashFunc = [](const UUID& n)
   {
      // meine Hash-Funktion
   }
};

Aber das (oder Variationen davon) kam mit Fehlern zurück, wie "kann keine statischen Initialisierer in einer Klasse haben", "kann hier kein auto verwenden", etc. (Ich hatte eine harte C++11-Anforderung). Also habe ich schließlich akzeptiert, dass ich dies wie eine static-Variable behandeln musste, sie in der Header-Datei deklarieren und in der .cpp-Datei initialisieren. Sobald ich ihren Typ herausgefunden hatte, war es einfach:

// MyClass.h
namespace myNamespace
{
   class MyClass
   {
      ...
   private:
      static std::function staticUuidHashFunc;

      std::unordered_map, decltype(staticUuidHashFunc)> mapOfObjs_;
   };
}

Und schließlich in der .cpp-Datei:

// MyClass.cpp

namespace myNamespace
{
   std::function MyClass::staticUuidHashFunc = [](const UUID& n)
    {
        // die Hash-Funktion
    };

    MyClass::MyClass()
       : mapOfObjs_{ std::unordered_map, decltype(staticUuidHashFunc)> (MyClass::NUMBER_OF_MAP_BUCKETS, staticUuidHashFunc)}
    {  }

   ...
}

Das Definieren der statischen Hash-Funktion in der .cpp-Datei war der Schlüssel. Danach waren sowohl Visual Studio als auch gcc zufrieden.