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

Question

我查了很多页，我想我已经知道怎么写std::hash了。但是我不知道放在哪里。

此处提供了一个示例 http://en.cppreference.com/w/cpp/utility/hash .

但是，我在文件 instance_management.h 的命名空间 ca 中定义了我的类型 Instance。我想在另一个 class 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

Answer 1

不要专门化 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;
}

相关帖子是，例如：

• Inserting in unordered_set using custom hash function

Answer 2

有几种方法。

专精std::hash

在您的代码中，确保您的 std::hash<Instance> 专业化紧跟在 Instance class 定义之后，然后是使用 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);
    }
};

用户定义的 class 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 的演讲（slides, video). Full source code by both the author and Bloomberg 可用。

Answer 3

谢谢大家。

我找到了原因并以某种方式解决了问题：visual studio 在定义 instances_ 时接受了 InstanceHash。由于我将 set 的使用更改为 unordered_set，我在尝试获取 const_iterator 时忘记指定 InstanceHash，所以这次编译器尝试使用 std::hash<>事情又失败了。但是编译器没有定位到使用const_iterator的行，所以我在定义instances_.

的时候误以为它没有接受InstanceHash

我还尝试将 std::hash<> 专门化为 class 实例。但是，这个特化至少需要声明class ca::Instance 和它的一些成员函数来计算散列值。特化后classca::InstanceManage的定义会用到

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