How do I implement a CString hash function for use with std::unordered_map?

Question

I want to declare :

std::unordered_map<CString, CString> m_mapMyMap;

But when I build I got an error telling me that the standard C++ doesn't provide a hash function for CString, while CString have the (LPCSTR) operator.

How do I properly implement a hash function for CString?

Shred

how to make it compile. – Shred

You should stat that clearly in the body of the question. Anyway, there's a duplicate. – Maureen

I think question is not fully duplicate. Most people will not find that question with their keywords. – Pintsize

@Maureen This is not a duplicate. It's a special case of the duplicate you linked and in order to know how to apply the question you linked, you need to know how to implement the hash function here, which this question should have been about, I've changed it accordingly. – Chainsmoke

@Chainsmoke Everything is a special case. The question is still a duplicate. – Maureen

@Maureen Does the question you linked explain how to implement a hash function for CString? – Chainsmoke

@Chainsmoke No, and this question doesn't ask that. The question linked tells you what needs to be done to use a user defined type as a key, and it isn't a huge step to look up how to create a hash and equality for a CString. – Maureen

@Maureen It's what it should have asked and does now, since my edit, that is :) – Chainsmoke

Answer 1

Based on the MS STL implementation for std::string I created the following methods which can be used for std::unordered_set and std::unordered_map:

namespace std
{
template <typename BaseType, class StringTraits>
struct hash<CStringT<BaseType, StringTraits>>
{ // hash functor for CStringT<BaseType, StringTraits>
    size_t operator()(const CStringT<BaseType, StringTraits>& _Keyval) const noexcept
    { // hash _Keyval to size_t value by pseudorandomizing transform
        return (_Hash_array_representation(_Keyval.GetString(), _Keyval.GetLength()));
    }
};
} // namespace std

// Usage:
std::unordered_set<CString> set1;
std::unordered_map<CString, CString> map1;
std::unordered_set<CStringA> set2;
std::unordered_map<CStringA, CStringA> map2;

Or use the following code if you want to specify a hasher (without putting your own code into the std namespace):

struct CStringHasher
{
    template <typename BaseType, class StringTraits>
    size_t operator()(const CStringT<BaseType, StringTraits>& _Keyval) const noexcept
    { // hash _Keyval to size_t value by pseudorandomizing transform
        return std::_Hash_array_representation(_Keyval.GetString(), _Keyval.GetLength());
    }
};

// Usage:
std::unordered_set<CString, CStringHasher> set1;
std::unordered_map<CString, CString, CStringHasher> map1;
std::unordered_set<CStringA, CStringHasher> set2;
std::unordered_map<CStringA, CStringA, CStringHasher> map2;

---

Old answer which works up to C++11 (unary_function and std::_HashSeq were removed in C++17):

namespace std {
    template <>
    struct hash<CString>
    {   // hash functor for CString
        size_t operator()(const CString& _Keyval) const
        {   // hash _Keyval to size_t value by pseudorandomizing transform
            return (_Hash_seq((const unsigned char*)(LPCWSTR)_Keyval, _Keyval.GetLength() * sizeof(wchar_t)));
        }
    };

    template <>
    struct hash<CStringA>
    {   // hash functor for CStringA
        size_t operator()(const CStringA& _Keyval) const
        {   // hash _Keyval to size_t value by pseudorandomizing transform
            return (_Hash_seq((const unsigned char*)(LPCSTR)_Keyval, _Keyval.GetLength() * sizeof(char)));
        }
    };
}

Or even more generic:

namespace std {
    template<typename BaseType, class StringTraits>
    struct hash<CStringT<BaseType, StringTraits>> : public unary_function<CStringT<BaseType, StringTraits>, size_t>
    {   // hash functor for CStringT<BaseType, StringTraits>
        typedef CStringT<BaseType, StringTraits> _Kty;

        size_t operator()(const _Kty& _Keyval) const
        {   // hash _Keyval to size_t value by pseudorandomizing transform
            return (_Hash_seq((const unsigned char*)(StringTraits::PCXSTR)_Keyval,
                _Keyval.GetLength() * sizeof(BaseType)));
        }
    };
}

Alphonsa

Answer 2

std::unordered_map use std::hash<> that does not use (LPCSTR) operator.

You need to redefine hash function:

template<class T> class MyHash;

template<>
class MyHash<CString> {
public:
    size_t operator()(const CString &s) const
    {
        return std::hash<std::string>()( (LPCSTR)s );
    }
};

std::unordered_map<CString,CString,MyHash> m_mapMyMap;

But for better performance use std::string instead CString for key.

Pintsize

There casting CString to const TCHAR ptr take place here and than construct anonimous std::string object is apears. There is no way to provide guarantee that memory pointed by const TCHAR ptr will not be released or rewrited, so std::string can not use that memory. The std::string make copy string from that memory. So this simple solution is have perfomance problem with needless memory coping. There is no std api to take hash from char ptr with "C" strings. So at simple cases it is possible to use this solution and for best performance need to use std::string or write special hash function. – Pintsize

@Pintsize is it possible to use the move constructor to get rid of that performance issue ? – Shred

For situation described in question it is not possible and not applicable. Interesting data is memory region retained by const ptr. Copy constuctor may applied for objects of CString type in some cases. But memory region need to copy anyway although from another copyed CString object. – Pintsize

Answer 3

After trying out MrTux's suggestion, I have to say that this doesn't work anymore. std::_HashSeq was removed and std::unary_function was also removed in C++17.

I ended up with another solution that incorporates Microsoft's advice for hash implementations to use std::basic_string_view's hasher:

namespace std
{
template<typename BaseType, class StringTraits>
struct hash<ATL::CStringT<BaseType, StringTraits>>
{
    size_t operator()(const ATL::CStringT<BaseType, StringTraits>& key) const noexcept
    {
        return hash<basic_string_view<BaseType>>()(
            basic_string_view<BaseType>(
                key.GetString(),
                key.GetLength()));
    }
};
}

Purveyor

See my answer which does not modify the std namespace. – Alphonsa

@Alphonsa It's also possible to do it that way, but it's perfectly legal to add the hasher to the std namespace. Requiring the additional template parameter is odd IMO. – Purveyor

Answer 4

Define this first:

struct KeyHasher
{
    std::size_t operator()(const CString& k) const
    {
        using std::hash;
        using std::string;

        return hash<string>()(string(CT2CA(k)));
    }
};

Then use it as the hash function

std::unordered_map<CString, CString, KeyHasher> umap;

Noncooperation

This answer is not optimal as all CStrings have to be converted to a std::string before... – Alphonsa