unordered_map mit Paar als Schlüssel - nicht kompilieren

Question

Ich versuche, eine ungeordnete_map zu erstellen, um Paare mit Ganzzahlen abzubilden.

#include <unordered_map> 

using namespace std; 
using Vote = pair<string, string>; 
using Unordered_map = unordered_map<Vote, int>; 

Ich habe eine Klasse, wo ich eine Unordered_map als ein privates Mitglied deklariert habe.

Allerdings bin ich immer diese Fehlermeldung, wenn ich zu kompilieren versuchen:

/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/type_traits:948:38: Implicit instantiation of undefined template 'std::__1::hash<std::__1::pair<std::__1::basic_string<char>, std::__1::basic_string<char> > >' 

Ich bin nicht diesen Fehler, wenn ich eine reguläre Karte wie map<pair<string, string>, int> anstelle eines unordered_map verwenden.

Ist es nicht möglich, pair als Schlüssel in ungeordneten Karten zu verwenden?

Answer 1

Sie müssen zur Verfügung zu stellen geeignete Hash-Funktion für Ihren Schlüsseltyp. Ein einfaches Beispiel:

#include <unordered_map> 
#include <functional> 
#include <string> 
#include <utility> 

// Only for pairs of std::hash-able types for simplicity. 
// You can of course template this struct to allow other hash functions 
struct pair_hash { 
    template <class T1, class T2> 
    std::size_t operator() (const std::pair<T1,T2> &p) const { 
     auto h1 = std::hash<T1>{}(p.first); 
     auto h2 = std::hash<T2>{}(p.second); 

     // Mainly for demonstration purposes, i.e. works but is overly simple 
     // In the real world, use sth. like boost.hash_combine 
     return h1^h2; 
    } 
}; 

using namespace std; 
using Vote = pair<string, string>; 
using Unordered_map = unordered_map<Vote, int, pair_hash>; 

int main() { 
    Unordered_map um; 
} 

Dies funktioniert, aber nicht haben die besten Hash-Eigenschaften ^†. Vielleicht möchten Sie sich etwas wie boost.hash_combine ansehen, um Ergebnisse von höherer Qualität zu erhalten, wenn Sie die Hashes kombinieren.

Für reale Nutzung: Boost bietet auch die Funktion hash_value eingestellt, die bereits eine Hash-Funktion für std::pair bietet, sowie std::tuple und die meisten Standard-Container.

---

^† Genauer gesagt, wird es zu viele Kollisionen erzeugen. Z.B. wird jedes symmetrische Paar auf 0 hashen und Paare, die sich nur durch Permutation unterscheiden, haben denselben Hash. Dies ist wahrscheinlich gut für Ihre Programmierübung, könnte aber die Leistung von Real-World-Code ernsthaft beeinträchtigen.

Answer 2

Da Ihr Kompilierungsfehler anzeigt, gibt es keine gültige Instanziierung von std::hash<std::pair<std::string, std::string>> in Ihrem Std-Namespace.

Nach meinem Compiler:

Fehler C2338 der C++ Standard bietet keine Hash für diesen Typen. c: \ Programme (x86) \ Microsoft Visual Studio 14.0 \ vc \ include \ xstddef 381

Sie können Ihre eigene Spezialisierung für std::hash<Vote> lauten wie folgt:

#include <string> 
#include <unordered_map> 
#include <functional> 

using namespace std; 
using Vote = pair<string, string>; 
using Unordered_map = unordered_map<Vote, int>; 

namespace std 
{ 
    template<> 
    struct hash<Vote> 
    { 
     size_t operator()(Vote const& v) const 
     { 
      // ... hash function here ... 
     } 
    }; 
} 

int main() 
{ 
    Unordered_map m; 
} 

Answer 3

Meine bevorzugte Lösung dieses Problems besteht darin, eine key-Funktion zu definieren, die Ihr Paar in eine eindeutige ganze Zahl (oder einen anderen beliebigen Datentyp) umwandelt. Dieser Schlüssel ist nicht der Hash-Schlüssel. Es ist die eindeutige ID des Datenpaars, die dann optimal von der unordered_map gehasht wird. Zum Beispiel, Sie wollten ein unordered_map des Typs

unordered_map<pair<int,int>,double> Map; 

Und Sie wollen definieren Map[make_pair(i,j)]=value oder Map.find(make_pair(i,j)) verwenden, um auf der Karte zu betreiben. Dann müssen Sie dem System mitteilen, wie ein Paar Ganzzahlen zu hasen make_pair(i,j).Statt dessen können wir

inline size_t key(int i,int j) {return (size_t) i << 32 | (unsigned int) j;} 

definieren und dann den Typ der Karte ändern

unordered_map<size_t,double> Map; 

Wir haben jetzt Map[key(i,j)]=value oder Map.find(key(i,j)) verwenden können, um auf der Karte zu betreiben. Jede make_pair ruft jetzt die Inline-Funktion key auf.

Diese Methode garantiert, dass der Schlüssel optimal gehashed wird, da der Hashing-Teil jetzt vom System ausgeführt wird, das immer die interne Hashtabellengröße als Primzahl wählt, um sicherzustellen, dass jeder Bucket gleich wahrscheinlich ist. Aber Sie müssen sich 100% ig sicher sein, dass die key für jedes Paar einzigartig ist, d. H., Keine zwei verschiedenen Paare können den gleichen Schlüssel haben, oder es können sehr schwierige Fehler gefunden werden.

Answer 4

Für Paar Schlüssel, können wir boost Paar Hash-Funktion verwenden:

#include <iostream> 
#include <boost/functional/hash.hpp> 
#include <unordered_map> 
using namespace std; 

int main() { 
    unordered_map<pair<string, string>, int, boost::hash<pair<string, string>>> m; 

    m[make_pair("123", "456")] = 1; 
    cout << m[make_pair("123", "456")] << endl; 
    return 0; 
} 

Ebenso können wir für Vektoren verwenden Boost-Hash,

#include <iostream> 
#include <boost/functional/hash.hpp> 
#include <unordered_map> 
#include <vector> 
using namespace std; 

int main() { 
    unordered_map<vector<string>, int, boost::hash<vector<string>>> m; 
    vector<string> a({"123", "456"}); 

    m[a] = 1; 
    cout << m[a] << endl; 
    return 0; 
}