C++ unordered_map wo Schlüssel ist auch ungeordnete_map

Question

Ich versuche eine ungeordnete_map mit einer anderen ungeordneten_map als Schlüssel (benutzerdefinierte Hash-Funktion) zu verwenden. Ich habe auch eine benutzerdefinierte gleich Funktion hinzugefügt, obwohl es wahrscheinlich nicht benötigt wird.

Der Code tut nicht, was ich erwarte, aber ich kann nicht Kopf oder Zahl davon machen, was vor sich geht. Aus irgendeinem Grund wird die gleiche Funktion nicht aufgerufen, wenn find() ausgeführt wird, was ich erwarte.

unsigned long hashing_func(const unordered_map<char,int>& m) { 
    string str; 
    for (auto& e : m) 
     str += e.first; 
    return hash<string>()(str); 
} 
bool equal_func(const unordered_map<char,int>& m1, const unordered_map<char,int>& m2) { 
    return m1 == m2; 
} 

int main() { 

    unordered_map< 
     unordered_map<char,int>, 
     string, 
     function<unsigned long(const unordered_map<char,int>&)>, 
     function<bool(const unordered_map<char,int>&, const unordered_map<char,int>&)> 
     > mapResults(10, hashing_func, equal_func); 

    unordered_map<char,int> t1 = getMap(str1); 
    unordered_map<char,int> t2 = getMap(str2); 

    cout<<(t1 == t2)<<endl; // returns TRUE 
    mapResults[t1] = "asd"; 
    cout<<(mapResults.find(t2) != mapResults.end()); // returns FALSE 

    return 0; 
} 

Answer 1

Zunächst einmal ist der Gleichheitsoperator sicherlich erforderlich, so dass Sie es halten sollte.

Schauen wir uns Ihre ungeordnete Karte der Hash-Funktion:

string str; 
for (auto& e : m) 
    str += e.first; 
return hash<string>()(str); 

Da es sich um eine ungeordnete Karte ist per definitionem kann der Iterator über die in beliebiger Reihenfolge Schlüssel des ungeordneten Karte iterieren. Da jedoch die Hash-Funktion denselben Hash-Wert für den gleichen Schlüssel erzeugen muss, wird diese Hash-Funktion in dieser Hinsicht offensichtlich fehlschlagen.

Zusätzlich würde ich auch erwarten, dass die Hash-Funktion zusätzlich zu den Schlüsseln auch die Werte des nicht erteilten Kartenschlüssels enthält. Ich nehme an, dass Sie es vielleicht so machen wollen - für zwei ungeordnete Karten, die als derselbe Schlüssel angesehen werden, solange ihre Schlüssel gleich sind und ihre Werte ignorieren. Es ist nicht klar aus der Frage, was Ihre Erwartung ist, aber Sie möchten vielleicht darüber nachdenken.

Answer 2

Vergleich zweier std::unordered_map Objekte mit == vergleicht, ob die Karten mit den gleichen Schlüssel enthalten. Es tut nichts zu sagen, ob sie sie in der gleichen Reihenfolge enthalten (es ist schließlich eine ungeordnete Karte). Ihre hashing_func hängt jedoch von der Reihenfolge der Elemente in der Karte ab: hash<string>()("ab") unterscheidet sich im Allgemeinen von hash<string>()("ba").

Answer 3

Ein guter Ausgangspunkt ist, was hashing_func für jede Map zurückgibt, oder einfacher, was die String-Konstruktion in hashing_func erzeugt.

Eine offenbar richtige Hash-Funktion für eine solche Art könnte sein:

unsigned long hashing_func(const unordered_map<char,int>& m) { 
    unsigned long res = 0; 
    for (auto& e : m) 
     res^hash<char>()(e.first)^hash<int>()(e.second); 
    return res; 
}