unordered_map con coppia come chiave - non compilato

Question

Sto provando a creare un unordered_map per mappare le coppie con numeri interi.

#include <unordered_map> 

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

Ho una classe in cui ho dichiarato Unordered_map come membro privato.

Tuttavia, sto ottenendo questo errore quando provo a compilare:

/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> > >' 

non sto ottenendo questo errore se uso una mappa regolare come map<pair<string, string>, int> invece di un unordered_map.

Non è possibile utilizzare pair come chiave nelle mappe non ordinate?

Answer 1

è necessario fornire un funzione hash adatta per il tuo tipo di chiave. Un semplice esempio:

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

Questo funzionerà, ma non avere i migliori hash-properties ^†. Si consiglia di dare un'occhiata a qualcosa come boost.hash_combine per risultati di alta qualità quando si combinano gli hash.

Per uso mondo reale: Boost fornisce anche la funzione impostata hash_value che fornisce già una funzione di hash per std::pair, così come std::tuple e più standard contenitori.

---

^† Più precisamente, esso produrrà troppe collisioni. Ad esempio, ogni coppia simmetrica avrà hash a 0 e le coppie che differiscono solo per la permutazione avranno lo stesso hash. Questo probabilmente va bene per il tuo esercizio di programmazione, ma potrebbe seriamente danneggiare le prestazioni del codice del mondo reale.

Answer 2

Come indica l'errore di compilazione, non esiste un'istanza valida di std::hash<std::pair<std::string, std::string>> nel proprio spazio dei nomi std.

Secondo il mio compilatore:

Errore C2338 Il C++ standard non fornisce un hash per questo tipo . c: \ program files (x86) \ Microsoft Visual Studio 14.0 \ VC \ include \ xstddef 381

è possibile fornire la propria specializzazione per std::hash<Vote> come segue:

#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

Il mio modo preferito di risolvere questo problema è definire una funzione key che trasforma la coppia in un numero intero univoco (o qualsiasi tipo di dati lavabile). Questa chiave non è la chiave hash. È l'ID univoco della coppia di dati che verrà quindi sostituita in modo ottimale dallo unordered_map. Ad esempio, si vuole definire un unordered_map del tipo

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

E che si desidera utilizzare o Map[make_pair(i,j)]=valueMap.find(make_pair(i,j)) per operare sulla mappa. Quindi dovrai dire al sistema come hash un paio di interi make_pair(i,j).Invece di questo, possiamo definire

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

e quindi modificare il tipo di mappa per

unordered_map<size_t,double> Map; 

Ora possiamo usare Map[key(i,j)]=value o Map.find(key(i,j)) di operare sulla mappa. Ogni make_pair ora chiama la funzione in linea key.

Questo metodo garantisce che la chiave sarà ottimale hash, perché ora la parte di hashing viene fatto dal sistema, che sarà sempre scegliere la dimensione interna tabella hash per essere primo per assicurarsi che ogni secchio è altrettanto probabile. Ma devi essere sicuro al 100% che lo key sia univoco per ogni coppia, vale a dire che non esistono due coppie distinte che possono avere la stessa chiave, oppure che ci possono essere bug molto difficili da trovare.

Answer 4

Per coppia di chiavi, possiamo usare la funzione Boost coppia di hash:

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

Allo stesso modo possiamo usare hash spinta per i vettori,

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