Come usare stdext :: hash_map dove la chiave è un oggetto personalizzato?

Question

Utilizzando l'++ hash_map STL C ...

class MyKeyObject 
{ 
    std::string str1; 
    std::string str2; 

    bool operator==(...) { this.str1 == that.str1 ... } 
}; 

class MyData 
{ 
    std::string data1; 
    int data2; 
    std::string etcetc; 
}; 

come questo ...

MyKeyObject a = MyKeyObject(...); 
MyData b = MyData(...); 

stdext::hash_map <MyKeyObject, MyData> _myDataHashMap; 
_myDataHashMap[ a ] = b; 

ottengo un intero carico di errori. Qui ci sono i primi tre ...

Errore 1 Errore C2784: 'bool std :: operator < (const std :: _ Albero < _Traits> &, const std :: _ Albero < _Traits> &) ': non potevano dedurre modello argomento per 'const std :: _ Albero < _Traits> &' da 'const MyKeyObject' c: \ programmi \ Microsoft visual Studio 8 \ VC \ include \ funzionale 143

01.235.

errore 2 Errore C2784: 'bool std :: operator < (const std :: basic_string < _Elem, _Traits, _Alloc> &, const _Elem *)': non poteva dedurre modello argomento per ' std const: : basic_string < _Elem, _Traits, _Alloc> & 'da 'const Tasking :: MyKeyObject' C: \ programmi \ Microsoft visual studio 8 \ VC \ include \ funzionale 143

errore 3 errore C2784:' bool std :: operator < (Const _Elem *, const std :: basic_string < _Elem, _Traits, _Alloc> &)': non poteva dedurre modello argomento per 'const _Elem *' dal 'const MyDataObject' C: \ Programmi \ Microsoft Visual Studio 8 \ VC \ include \ funzionale 143

...

Se ho impostato la chiave per qualcosa di semplice come un int tutto va bene.

Cosa sto sbagliando ?! Forse ho bisogno di fare qualcosa con i modelli?

C'è un modo migliore (più veloce?) Di accedere ai dati utilizzando un oggetto chiave personalizzato come questo?

Answer 1

Provate il seguente, ha lavorato per me in VS 2005. Si tratta di una soluzione per entrambi VS2005 tipo built-in hash_map nel namespace stdext così come il boost unordered_map (preferito). Elimina quello che non usi.

#include <boost/unordered_map.hpp> 
#include <hash_map> 

class HashKey 
{ 
public: 
    HashKey(const std::string& key) 
    { 
     _key=key; 
    } 
    HashKey(const char* key) 
    { 
     _key=key; 
    } 

    // for boost and stdext 
    size_t hash() const 
    { 
     // your own hash function here 
     size_t h = 0; 
     std::string::const_iterator p, p_end; 
     for(p = _key.begin(), p_end = _key.end(); p != p_end; ++p) 
     { 
      h = 31 * h + (*p); 
     } 
     return h; 
    } 
    // for boost 
    bool operator==(const HashKey& other) const 
    { 
     return _key == other._key; 
    } 

    std::string _key; 
}; 

// for boost 
namespace boost 
{ 
    template<> 
    class hash<HashKey> 
    { 
    public : 
     std::size_t operator()(const HashKey &mc) const 
     { 
      return mc.hash(); 
     } 
    }; 
} 

// for stdext 
namespace stdext 
{ 
    template<> 
    class hash_compare<HashKey> 
    { 
    public : 
     static const size_t bucket_size = 4; 
     static const size_t min_buckets = 8; 

     size_t operator()(const HashKey &mc) const 
     { 
      return mc.hash(); 
     } 

     bool operator()(const HashKey &mc1, const HashKey &mc2) const 
     { 
      return (mc1._key < mc2._key); 
     } 
    }; 
} 

int _tmain(int argc, _TCHAR* argv[]) 
{ 
    { 
     stdext::hash_map<HashKey, int> test; 
     test["one"] = 1; 
     test["two"] = 2; 
    } 

    { 
     boost::unordered_map<HashKey, int> test(8); // optional default initial bucket count 8 
     test["one"] = 1; 
     test["two"] = 2; 
    } 

    return 0; 
} 

Answer 2

Per utilizzare una tabella di hash, è necessario specificare una funzione di hash. È necessario creare un oggetto funzione che rappresenta una funzione che accetta un oggetto MyKeyObject e restituisce un valore size_t. Poi si passa il funtore come secondo argomento dopo la dimensione iniziale:

hash_map <MyKeyObject, MyData> _myDataHashMap(initial_size, YourHashFunctor()); 

In alternativa, è possibile scrivere la funzione di hash come modello di specializzazione del hash<T> funtore per il tipo; in questo modo non è necessario passare in una funzione hash personalizzata.

Non so perché stiate ottenendo quegli errori in modo specifico. Forse sta cercando di usare il tuo oggetto come codice hash o qualcosa del genere?In ogni caso non dovrebbe funzionare senza una funzione hash. Le funzioni hash sono predefinite per i tipi interi e le stringhe.

Answer 3

< collegamento rimosso> spiega chiaramente come utilizzare hash_map e creare la propria funzione di hash.

(edit:. Collegamento rimosso punti alla pagina di spam ora)

Answer 4

Lo sto usando per mappare la struttura dei dati dei vertici.

#include <stdio.h> 
#include <stdlib.h> 
#include <string> 
#include <boost/unordered_map.hpp> 



struct VERTEX 
{ 
float x,y,z; 
}; 

typedef boost::unordered_map<std::string, unsigned int> map; 

int main() 
{ 
VERTEX v1,v2,v3; 

v1.x = 5.0; v1.y = 2.0; v1.z = 2.33333336; 
v2.x = 5.0; v2.y = 2.0; v2.z = 2.32333336; 
v3.x = 5.0; v3.y = 2.0; v3.z = 2.33333336; 

unsigned int vertexSize = sizeof(VERTEX); 
char * v1c = new char[vertexSize]; 
char * v2c = new char[vertexSize]; 
char * v3c = new char[vertexSize]; 

memcpy(v1c, &v1, vertexSize);memcpy(v2c, &v2, vertexSize);memcpy(v3c, &v3, vertexSize); 
map mymap; 

std::string aaa(v1c, vertexSize); 
std::string bbb(v2c, vertexSize); 
std::string ccc(v3c, vertexSize); 

mymap[ aaa ] = 1; 
mymap[ bbb ] = 2; 

unsigned int a = mymap[ aaa ]; 
unsigned int b = mymap[ bbb ]; 
unsigned int c = mymap[ ccc ]; 


return 0; 
} 

Questo è solo un piccolo esempio, di come sto usando tipi personalizzati. Copio solo parte della memoria di struct in char * e quindi creo una stringa con il secondo param, che è una dimensione, la dimensione è importante in quanto i dati di memoria possono contenere caratteri nulli. Non ho bisogno di ulteriori comparazioni, funzioni di hashing ...

Answer 5

Mi sono imbattuto in questa vecchia domanda mentre cercavo di trovare la stessa risposta e trovavo le risposte esistenti non molto utili. Al giorno d'oggi usiamo unordered_map se vogliamo una mappa hash e il modo migliore per rendere la vostra classe MyKeyObject utilizzabile come chiave in un hash_map in generale è definire una funzione di hash per la classe e dire alla libreria standard di usare questa funzione di hash per mappe. Ciò significa che è possibile creare un'istanza del modello di mappa senza fornire sempre una funzione di hash.

Il wikipedia page su "Contenitori associativi non ordinati in C++" fornisce un esempio facile da seguire, l'ho ridotto un po 'e l'ho applicato al caso. Prima definiamo una semplice funzione hash come metodo membro:

#include <functional> 
class MyKeyObject { 
private: 
    std::string str1; 
    std::string str2; 

public: 
    inline size_t hash() const { 
     return std::hash<std::string>()(str1)^std::hash<std::string>()(str2); 
    } 

    inline bool operator==(const MyKeyObject& other) const { 
     return str1 == other.str1 && str2 == other.str2; 
    } 
}; 

Al fine di rendere la funzione hash, abbiamo XOR gli hash di tutte contenute oggetti insieme. Questo viene fatto usando std::hash, un modello che deve essere istanziato con il tipo di bambino. Nota che non possiamo usare questo come il terzo parametro del template su unordered_map. Notare anche l'operatore const-equals.

Ora dobbiamo dire la libreria standard che questa è la funzione hash da utilizzare per MyKeyObject valori:

namespace std { 
    template <> 
    class hash<MyKeyObject> { 
    public: 
     size_t operator()(const MyKeyObject &aMyKeyObject) const { 
      return aMyKeyObject.hash(); 
     } 
    }; 
} 

Questo aggiunge un modello di specializzazione alla classe std::hash modello, fornendo all'operatore hash per l'MyKeyObject classe. Nell'esempio la pagina wikipedia non definisce direttamente l'hash qui, piuttosto che chiamare una funzione hash che è un membro dell'oggetto, ma se la funzione hash deve accedere ai membri privati, ciò non funzionerà.

Ora si dovrebbe essere in grado di utilizzare MyKeyObject in un unordered_map in questo modo:

std::unordered_map<MyKeyObject, MyData> _myDataHashMap; 

(testato con clangore/Xcode)