Ben L Ben L - 8 days ago 5
C++ Question

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

Using the 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 a whole load of errors. Here are the first three...


Error 1 error C2784: 'bool
std::operator <(const
std::_Tree<_Traits> &,const
std::_Tree<_Traits> &)' : could not
deduce template argument for 'const
std::_Tree<_Traits> &' from 'const
MyKeyObject' c:\program files\microsoft
visual studio
8\vc\include\functional 143

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

Error 3 error C2784: 'bool
std::operator <(const _Elem *,const
std::basic_string<_Elem,_Traits,_Alloc>
&)' : could not deduce 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 simple like an int all is well.

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

Is there a better (quicker?) way of accessing data using a custom key object like this?

Answer

Try the following, worked for me in VS 2005. This is a solution for both VS2005 built-in hash_map type in stdext namespace as well as the boost unordered_map (preferred). Delete whichever you don't use.

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