7

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?

8
  • how to make it compile.
    – Aminos
    Feb 15, 2016 at 11:48
  • You should stat that clearly in the body of the question. Anyway, there's a duplicate. Feb 15, 2016 at 11:51
  • 2
    I think question is not fully duplicate. Most people will not find that question with their keywords.
    – oklas
    Feb 15, 2016 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, 2016 at 9:59
  • @phant0m Everything is a special case. The question is still a duplicate. Jun 28, 2016 at 10:37

4 Answers 4

4

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

3
  • 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, 2016 at 6:19
  • @oklas is it possible to use the move constructor to get rid of that performance issue ?
    – Aminos
    Jul 21, 2016 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, 2016 at 23:00
1

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()));
    }
};
}
2
  • See my answer which does not modify the std namespace.
    – MrTux
    Jun 5 at 2:50
  • @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 5 at 14:04
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;
1
  • This answer is not optimal as all CStrings have to be converted to a std::string before...
    – MrTux
    Jun 5 at 2:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.