How to use stdext :: hash_map where the key is a custom object?

Question

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

like this...

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

I get all the error. Here are the first three ...

Error 1 error C2784: 'bool std :: operator <(const std :: _ Tree <_Traits> &, const std :: _ Tree <_Traits> &)': failed to print the template argument for 'const std :: _ Tree <_Traits> & 'by' const MyKeyObject 'c: \ program files \ microsoft visual studio 8 \ vc \ include \ functional 143

Error 2 of error C2784: 'bool std :: operator <(const std :: basic_string <_Elem, _Traits, _Alloc> &, const _Elem *)': the template argument for 'const std :: basic_string <_Elem, _Traits, failed _Alloc> & amp; "from 'const Task :: MyKeyObject' c: \ program files \ microsoft visual studio 8 \ vc \ include \ functional 143

Error 3 of error C2784: 'bool std :: operator <(const _Elem *, const std :: basic_string <_Elem, _Traits, _Alloc> &)': could not derive the template argument for 'const _Elem *' from 'const MyDataObject' c : \ program files \ microsoft visual studio 8 \ vc \ include \ functional 143

...

If I set the key to something as simple as int, everything is fine.

What am I doing wrong?! Maybe I need to do something with templates?

Is there a better (faster?) Way to access data using a custom key object like this?

Answer 1

Try the following, working for me in VS 2005. This is a solution for both the VS2005 built-in hash_map type in the stdext namespace and boost unordered_map (preferred). Remove what you are not using.

 #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

To use a hash table, you need to specify a hash function. You need to create a function object that represents a function that takes a MyKeyObject and returns size_t . Then you pass the functor as the second argument after the initial size:

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

Alternatively, you can write your hash function as a specialized specialization of the hash<T> functor for your type; this way you do not need to pass a custom hash function.

I do not know why you are getting these errors. Perhaps he is trying to use your object as a hash code or something else? In any case, it should not work without a hash function. Hash functions are predefined for integer types and strings.

Answer 3

<link removed> explains how to use hash_map and create your own hash function.

(edit: link removed. points to spam page)

Answer 4

I use it to display the vertex data structure.

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

This is just a small example of how I use custom types. I just copy part of the structure’s memory to char *, and then create a line with a second parameter, the size of which is important, since the data in the memory can contain null characters. I don't need additional comparisons, hashing functions ...

Answer 5

I came across this very old question, trying to find the same answer, and finding existing answers is not very useful. We are currently using unordered_map if we want a hash map, and the best way to make your MyKeyObject class useful as a key in hash_map in general is to define a hash function for the class and tell the standard library this hash function for mappings. This means that we can create a template template without providing a hash function.

in the "Unordered Associative Containers in C ++" section gives a simple example, I disabled it a bit and applied it to your case. First, we define a simple hash function as a member method:

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

To make a hash function, we xor the hashes of all the contained objects together. This is done using std::hash , a template that must be created using a child type. Please note: we cannot use this as the third template parameter for unordered_map. Note also the const-equals operator.

Now we need to tell the standard library that this is a hash function that will be used for MyKeyObject values:

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

This adds the template specialization to the std::hash template std::hash , providing a hash statement for the MyKeyObject class. In the example, there is no wikipedia page that directly defines the hash here, and does not call a hash function that is a member of the object, but if the hash function needs to access private members, this will not work.

Now you can use MyKeyObject in unordered_map like this:

  std::unordered_map<MyKeyObject, MyData> _myDataHashMap; 

(verified with clang / xcode)