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?

You should stat that clearly in the body of the question. Anyway, there's a duplicate. — juanchopanza, Feb 15 '16 at 11:51
I think question is not fully duplicate. Most people will not find that question with their keywords. — oklas, Feb 15 '16 at 12:27
@juanchopanza 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. — phant0m, Jun 28 '16 at 09:59
@phant0m Everything is a special case. The question is still a duplicate. — juanchopanza, Jun 28 '16 at 10:37
@juanchopanza Does the question you linked explain how to implement a hash function for CString? — phant0m, Jun 28 '16 at 11:36
@phant0m 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. — juanchopanza, Jun 28 '16 at 11:37
@juanchopanza It's what it should have asked and does now, since my edit, that is :) — phant0m, Jun 28 '16 at 11:38

MrTux · Accepted Answer · 2023-06-07T13:32:22.363

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

oklas · Answer 2 · 2016-02-17T06:27:34.230

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.

edited Feb 17 '16 at 06:27

answered Feb 15 '16 at 11:40

oklas

7,935
2
26
42

1

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. – oklas Jun 28 '16 at 06:19
@oklas is it possible to use the move constructor to get rid of that performance issue ? – Aminos Jul 21 '16 at 17:29
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. – oklas Jul 21 '16 at 23:00

score 1 · Answer 3 · answered Jun 02 '22 at 16:56

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()));
    }
};
}

@MrTux 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. — Oliver Old, Jun 05 '23 at 14:04

xitong · Answer 4 · 2023-03-18T13:41:14.603

0

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;

edited Mar 18 '23 at 13:41

answered Mar 15 '23 at 03:14

xitong

352
2
9

This answer is not optimal as all `CString`s have to be converted to a `std::string` before... – MrTux Jun 05 '23 at 02:44

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

4 Answers4

Linked

Related