如何实现一个用于 std::unordered_map 的 CString 哈希函数？

Question

我想声明：

std::unordered_map<CString, CString> m_mapMyMap;

当我进行构建时，会出现错误提示，告诉我标准的C++不为CString提供哈希函数，而CString有(LPCSTR)运算符。

我应该如何正确实现一个适用于CString的哈希函数？

- Aminos

---

你有什么问题？ - juanchopanza

如何使其编译通过。 - Aminos

你应该在问题正文中清楚地表明。无论如何，这是一个重复的问题。 - juanchopanza

我认为这个问题不完全是重复的。大多数人使用他们的关键词无法找到那个问题。 - oklas

@juanchopanza，你链接的问题是否解释了如何为CString实现哈希函数？ - phant0m

Answer 1

基于MS STL实现的std::string，我创建了以下方法，可以用于std::unordered_set和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;

如果您想指定一个哈希函数（而不是将自己的代码放入std命名空间），请使用以下代码：

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;

---

旧答案适用于C++11之前的版本（在C++17中删除了unary_function和std::_HashSeq）。

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

甚至更加通用：

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

- MrTux

Answer 2

std::unordered_map使用std::hash<>而不使用(LPCSTR)运算符。

您需要重新定义哈希函数：

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;

但为了更好的性能，请使用std::string而不是CString作为键。

- oklas

---

这里发生了将CString转换为const TCHAR ptr的强制类型转换，然后出现了匿名std :: string对象的构造。无法保证const TCHAR ptr指向的内存不会被释放或重写，因此std :: string无法使用该内存。std :: string从该内存中复制字符串。因此，这个简单的解决方案存在性能问题，需要进行不必要的内存复制。没有std api可以从“C”字符串的char ptr中获取哈希值。因此，在简单情况下，可以使用此解决方案，并且为了获得最佳性能，需要使用std :: string或编写特殊的哈希函数。 - oklas

@oklas，使用移动构造函数来解决性能问题是否可行？ - Aminos

对于问题中描述的情况，这是不可能且不适用的。有趣的数据是由const指针保留的内存区域。在某些情况下，可以为CString类型的对象使用复制构造函数。但无论如何，内存区域都需要从另一个被复制的CString对象进行复制。 - oklas

Answer 3

在尝试了MrTux的建议之后，我不得不说这已经不再起作用了。std::_HashSeq在C++17中被移除，std::unary_function也被移除了。

最终，我采用了另一种解决方案，结合了Microsoft关于哈希实现的建议，使用了std::basic_string_view的哈希函数：

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

- Oliver Old

---

请查看我的答案，它不修改std命名空间。 - MrTux

@MrTux 这种做法也是可行的，但是将哈希函数添加到std命名空间中是完全合法的。在我看来，要求额外的模板参数有点奇怪。 - Oliver Old

@MrTux 这种做法也是可行的，但是将哈希函数添加到std命名空间中是完全合法的。在我看来，要求额外的模板参数有些奇怪。 - undefined

Answer 4

首先定义这个：

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

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

然后将其用作哈希函数

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

- xitong

---

这个答案并不是最佳的，因为所有的 CString 都必须在转换成 std::string 之前... - MrTux

这个答案并不理想，因为所有的 CString 都必须在...之前转换为 std::string。 - undefined