在哪里放置用户定义类型的专用std::hash？

Question

我搜索了很多页面，我认为我已经知道如何编写std :: hash。但我不知道该把它放在哪里。

这里提供了一个示例 http://en.cppreference.com/w/cpp/utility/hash。

然而，在文件instance_management.h的命名空间ca中定义了我的类型Instance。我想在同一文件中的另一个类InstanceManager中使用unordered_set<Instance>。所以我写了以下代码：

namespace std
{
    template <> struct hash<ca::Instance>
    {
        size_t operator()(const ca::Instance & instance) const
        {
            std::size_t seed = 0;
            // Some hash value calculation here.
            return seed;
        }
    };
} // namespace std

但是我应该把它放在哪里呢？我尝试了很多地方，但都失败了。

我正在使用Visual Studio 2013。我尝试将先前的代码放在一些位置，但都无法编译它。

// location 1

namespace ca
{
    class Instance {...}
    class InstanceManager
    {
        // ... some other things.
        private unordered_set<Instance>;
    }
}

// location 2

- John Smith

---

把它放在 instance_management.h 有什么问题吗？ - vsoftco

Answer 1

有几种方法。

专门化std :: hash

在您的代码中，确保您的std :: hash <Instance> 专门化紧跟着 Instance 类定义之后，并且在使用它的 unordered_set 容器之前。

namespace ca
{
    class Instance {...};

}

namespaces std {

    template<> hash<Instance> { ... };

}

namespace ca {

    class InstanceManager
    {
        // ... some other things.
        private unordered_set<Instance>;
    }
}

一个缺点是当你将 std::hash<ca::Instance> 传递给其他函数时，可能会出现有趣的名称查找干扰。原因是 std::hash 的所有模板参数的相关命名空间（ca）可以在名称查找（ADL）期间使用。这样的错误有点罕见，但如果发生了，调试可能很困难。

有关更多详细信息，请参见 this Q&A。

将您的哈希传递给 unordered_set

struct MyInstanceHash { ... };

using MyUnorderedSet = std:unordered_set<Instance, MyInstanceHash>;

在这里，你只需将自己的哈希函数传递给容器即可完成。缺点是必须显式地输入自己的容器类型。

使用hash_append

然而，请注意，目前正在等待审核的N3980标准提案。该提案具有更优秀的设计，使用了一个通用哈希函数，可以通过其模板参数（实际哈希算法）对任意字节流进行哈希处理。

template <class HashAlgorithm>
struct uhash
{
    using result_type = typename HashAlgorithm::result_type;

    template <class T>
    result_type
    operator()(T const& t) const noexcept
    {
        HashAlgorithm h;
        using std::hash_append;
        hash_append(h, t);
        return static_cast<result_type>(h);
    }
};

用户定义的类X需要通过提供适当的hash_append方法来呈现自身为字节流，以便可以被通用哈希函数进行哈希处理。

class X
{
    std::tuple<short, unsigned char, unsigned char> date_;
    std::vector<std::pair<int, int>>                data_;

public:
    // ...
    friend bool operator==(X const& x, X const& y)
    {
        return std::tie(x.date_, x.data_) == std::tie(y.date_, y.data_);
    }

    // Hook into the system like this
    template <class HashAlgorithm>
    friend void hash_append(HashAlgorithm& h, X const& x) noexcept
    {
        using std::hash_append;
        hash_append(h, x.date_);
        hash_append(h, x.data_);
    }
}

更多细节请参见作者@HowardHinnant在CppCon14的演示(幻灯片, 视频)。作者和Bloomberg均提供完整的源代码。

- TemplateRex

---

我会点赞 +10，因为这很棒，但它并没有真正回答 OP 的问题，不是吗？ - Jonathan H

@Sh3ljohn，有一份可行的代码实现了这个功能，并完全避免了使用std::hash。在你的回答中，“H(e.src) ^ H(e.dst)”这个语句是薄弱环节。它可能会破坏你的哈希函数的所有良好属性。 - TemplateRex

@TemplateRex 实际上，我不知道“标准提案”是什么意思。它是否表示该提案将在未来成为C++标准？编译器支持如何呢？VC++会支持吗？ - John Smith

@TemplateRex，你为什么说xor是弱点呢？我欣赏你的解决方案既优美又简洁，但它本质上与在单独的函数对象中手动哈希实例内容没有区别。它不是目前的标准，肯定更加复杂，而且绝对不兼容c++11或VS2013，这是OP正在使用的。我仍然喜欢你的文章，但它超出了范围，也不兼容OP明显的编程技能。 - Jonathan H

@Sh3ljohn 我建议你阅读N3980。它解决了合并不同子对象哈希的问题。即使您拥有完美和出色的哈希函数（具有经过验证的分布属性），仅仅执行h(x) ^ h(y)也会破坏这些良好的特性。相反，您希望能够将主题的字节流连接到（可能是有状态的）哈希算法中。顺便说一句，SO答案不仅针对OP，而且还针对广大C++程序员。从GitHub使用hash_append.h并不需要那么多技巧。 - TemplateRex

Answer 2

不要专门化 std::hash，相反地，编写自己的哈希函数对象（参见下面的 Edge_Hash），并使用两个模板参数声明你的 unordered_set。

#include <unordered_set>
#include <functional>

namespace foo
{
    // an edge is a link between two nodes
    struct Edge
    {
        size_t src, dst;
    };

    // this is an example of symmetric hash (suitable for undirected graphs)
    struct Edge_Hash
    {
        inline size_t operator() ( const Edge& e ) const
        {
            static std::hash<size_t> H;
            return H(e.src) ^ H(e.dst);
        }
    };

    // this keeps all edges in a set based on their hash value
    struct Edge_Set
    {
        // I think this is what you're trying to do?
        std::unordered_set<Edge,Edge_Hash> edges;
    };
}

int main()
{
    foo::Edge_Set e;
}

相关文章包括：

• 使用自定义哈希函数插入unordered_set
• 创建自定义哈希函数unordered_map时遇到的问题

- Jonathan H

---

我正在开发一个C++库代码。因此，在instance_management.h文件中没有main()函数。我必须尝试将所有内容都放在命名空间中，包括使用unordered_set<Instance>的类Instance和InstanceManager。然而，许多页面上都说鼓励将用户定义类型的专用std::hash<>放在std命名空间中。我编写了代码片段，并尝试将其放在同一文件中的某个位置，但无法成功编译instance_management.h文件。 - John Smith

当我将您的代码放入单独的.h文件中时，Visual Studio成功编译了它。然而，当我对我的代码采用同样的方式并使用private: unordered_set<Instance, InstanceHash> instances_;时，我会遇到错误。 - John Smith

类似这样的编程错误：error C2338: The C++ Standard doesn't provide a hash for this type.和see reference to class template instantiation 'std::hash<_Kty>' being compiled with [_Kty=ca::Instance]。看起来编译器没有接受我指定的InstanceHash。 - John Smith

Answer 3

谢谢大家。

我找到了原因并以某种方式解决了问题：在定义instances_时，Visual Studio接受了InstanceHash。由于我将set的使用更改为unordered_set，当我尝试获取const_iterator时，我忘记指定InstanceHash，所以这次编译器尝试使用std::hash<>的东西并失败了。但是编译器没有定位使用const_iterator的那一行，所以我错误地认为在定义instances_时它不接受InstanceHash。

我还尝试为类Instance专门化std::hash<>。然而，这个专门化至少需要声明类ca::Instance和一些成员函数来计算哈希值。在这个专门化之后，类ca::InstanceManage的定义将使用它。

现在我通常将几乎所有类和成员函数的声明和实现放在一起。因此，我需要做的事情可能是将ca命名空间范围分为2个部分，并将std{ template <> struct hash<ca::Instance>{...}}放在中间。

- John Smith

---

@Sh3ljohn，将模板特化放入std命名空间的提议来自于这里：https://dev59.com/CWsz5IYBdhLWcg3wBzfi。此外，如果我不将特化放入std命名空间，每次尝试获取迭代器时都需要指定“InstanceHash”。 - John Smith

我想知道哪种编程实践更好：将模板特化放在std中还是不放。例如：“unordered_set<Instance, InstanceHash>::const_iterator iterator = instances_.find(...)"。请仅返回翻译后的文本。 - John Smith

这就是为什么类通常从使用typedef定义一堆类型开始。更好的编程实践绝对不是将其放在std命名空间中。 - Jonathan H