Jak używać stdext :: hash_map, gdzie klucz jest obiektem niestandardowym?

Question

Korzystanie z STL C++ hash_map ...

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

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

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

tak ...

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

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

dostaję cały ciężar błędów. Oto trzy pierwsze ...

Error 1 error C2784: „bool std :: operator < (const std :: _ Drzewo < _Traits> &, const std :: _ drzewa < _Traits> &) 'nie może wydedukować szablonu argument 'const std :: _ drzewa < _Traits> &' z 'const MyKeyObject' C: \ Program Files \ Microsoft visual studio 8 \ VC \ include \ funkcjonalną 143

Błąd 2 error C2784: 'bool std :: operator < (const std :: basic_string < _Elem, _Traits, _Alloc> &, const _Elem *)': nie mogła wywnioskować szablonu argument „const std : basic_string < _Elem, _Traits, _Alloc> & 'od 'const wielozadaniowych :: MyKeyObject' C: \ Program Files \ Microsoft visual studio 8 \ VC \ include \ funkcjonalną 143

błąd 3 błędu C2784:' bool std :: operator < (Const _Elem *, const std :: basic_string < _Elem, _Traits, _Alloc> &)”: nie można wywnioskować szablon argumentem dla 'const _Elem *' od 'const MyDataObject' C: \ Program Files \ Microsoft wizualny studio 8 \ VC \ include \ funkcjonalny 143

...

Jeżeli ustawić klucz do czegoś prostego jak int wszystko jest dobrze.

Co robię źle ?! Może muszę coś zrobić z szablonami?

Czy istnieje lepszy (szybszy?) Sposób dostępu do danych przy użyciu niestandardowego obiektu klucza, takiego jak ten?

Answer 1

spróbuj wykonać następujące czynności, pracował dla mnie w VS 2005. Jest to rozwiązanie zarówno dla VS2005 wbudowany typ hash_map w przestrzeni nazw stdext jak również boost unordered_map (preferowane). Usuń to, czego nie używasz.

#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

Aby użyć tabeli skrótów, musisz podać funkcję skrótu. Musisz utworzyć obiekt funkcji, który reprezentuje funkcję, która pobiera obiekt MyKeyObject i zwraca wartość size_t. Następnie mijamy funktor jako drugi argument po początkowym rozmiarze:

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

Alternatywnie, można napisać funkcję skrótu jako specjalizacji szablonu z hash<T> funktora dla danego typu; w ten sposób nie musisz przekazywać niestandardowej funkcji skrótu.

Nie wiem, dlaczego otrzymujesz te błędy. Być może próbuje użyć twojego obiektu jako kodu skrótu lub czegoś podobnego?W każdym razie nie powinno działać bez funkcji skrótu. Funkcje skrótu są wstępnie zdefiniowane dla typów całkowitych i łańcuchów.

Answer 3

< usunięty link> wyjaśnia wyraźnie, w jaki sposób używać hash_map i utworzyć własną funkcję skrótu.

(edit:. Usunięto link do strony punktów spamu teraz)

Answer 4

Używam go do mapowania struktury danych wierzchołków.

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

To tylko mały przykład, jak używam typów niestandardowych. Po prostu kopiuję część pamięci struct na char *, a następnie tworzę ciąg z drugim parametrem, który jest wielkością, a rozmiar jest ważny, ponieważ dane pamięci mogą zawierać puste znaki. Nie potrzebuję żadnych dodatkowych funkcji porównywania, mieszania ...

Answer 5

Natknąłem się na to bardzo stare pytanie, próbując znaleźć tę samą odpowiedź i uważam, że istniejące odpowiedzi nie są naprawdę pomocne. Obecnie używamy unordered_map, jeśli chcemy mieć mapę haszującą, a najlepszym sposobem na uczynienie klasy MyKeyObject użyteczną jako klucz w hash_map w ogólności jest zdefiniowanie funkcji skrótu dla klasy i powiedzenie standardowej bibliotece, aby użyła tej funkcji skrótu dla mapy. Oznacza to, że możemy utworzyć szablon mapy bez podawania funkcji mieszania.

Na wikipedia page w "Nieuporządkowanych pojemnikach asocjacyjnych w C++" znajduje się prosty przykład, który został nieco uproszczony i zastosowałem go do twojej sprawy. Najpierw będziemy definiować prostą funkcję skrótu jako metoda członkiem:

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

Aby funkcję skrótu, mamy XOR hashe wszystkich zawartych przedmiotów razem. Odbywa się to za pomocą std::hash, szablonu, który należy utworzyć instancją z typem podrzędnym. Zauważ, że nie możemy użyć tego jako trzeciego parametru szablonu do nieuporządkowanej_mapy. Zwróć także uwagę na operatora const-equals.

Teraz musimy powiedzieć biblioteki standardowej, że jest to funkcja hash być wykorzystywane do MyKeyObject wartości:

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

Dodaje specjalizację szablonu do klasy std::hash szablonu, zapewniając operatorowi hash dla MyKeyObject klasa. W przykładzie nie strona wikipedia bezpośrednio określa skrót, zamiast wywoływać funkcję skrótu, która jest członkiem obiektu - ale jeśli funkcja hash ma dostęp do prywatnych członków, to nie zadziała.

Teraz powinieneś być w stanie korzystać MyKeyObject w unordered_map tak:

std::unordered_map<MyKeyObject, MyData> _myDataHashMap; 

(testowane z brzękiem/Xcode)