使用pair作为键的unordered_map构建失败（C++）

Question

我看到可以使用 std::pair 作为 std::unordered_map 的键。在我的情况下，我需要在 pair 中使用 std::type_index。但是在构建时遇到了一些问题。我的代码如下：

template<class Base, class Result, bool Commutative>
struct Multimethod2
{
    using Args = std::pair<std::type_index, std::type_index>;
    using Method = std::function<bool(Base *, Base *)>;

    struct ArgsHash {
        std::size_t operator () (Args &p) const {
            std::size_t h1 = std::hash<std::type_index>()(p.first);
            std::size_t h2 = std::hash<std::type_index>()(p.second);
            return h1 ^ h2;
        }
    };

    struct KeyEqual
    {
        bool operator()(const Args &a1, const Args &a2) const
        {
            return (a1.first == a2.first && a1.second == a2.second) ||
                   (a1.first == a2.second && a1.second == a2.first);
        }
    };

    std::unordered_map<Args, Method, ArgsHash, KeyEqual> methods;
...
}

收到错误信息：

/usr/include/c++/7/bits/hashtable_policy.h:87: error: no match for call to ‘(const Multimethod2<Shape, bool, true>::ArgsHash) (const std::pair<std::type_index, std::type_index>&)’
  noexcept(declval<const _Hash&>()(declval<const _Key&>()))>
          ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

/usr/include/c++/7/bits/hashtable_policy.h:87: error: binding reference of type ‘Multimethod2<Shape, bool, true>::Args& {aka std::pair<std::type_index, std::type_index>&}’ to ‘const std::pair<std::type_index, std::type_index>’ discards qualifiers
  noexcept(declval<const _Hash&>()(declval<const _Key&>()))>
          ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

/usr/include/c++/7/type_traits:154: error: ‘value’ is not a member of ‘std::__and_<std::__is_fast_hash<Multimethod2<Shape, bool, true>::ArgsHash>, std::__detail::__is_noexcept_hash<std::pair<std::type_index, std::type_index>, Multimethod2<Shape, bool, true>::ArgsHash> >’
    : public integral_constant<bool, !_Pp::value>
                                      ^~~~

...

这里的语法有什么问题？

- Aleksey Kontsevich

---

ArgsHash::operator() 应该使用 const& 来接收 Args 参数。 - Massimiliano Janes

@MassimilianoJanes 这应该是一个答案，而不是一个评论。 - Angew is no longer proud of SO

@MassimilianoJanes，是的，我不小心清除了它，谢谢！ - Aleksey Kontsevich

@Angew 没错，我只是在等待原帖作者的回复；有时候这些问题只是打字错误而已... - Massimiliano Janes

Answer 1

根据哈希需求，`ArgsHash::operator()` 应该使用 `const&` 传递 `Args`。

顺便说一下，你的哈希函数可能不太好（如果有两个相同的 type_index 会发生什么？）。

组合哈希并不是一件简单的事情（这就是为什么没有 std::hash_combine 的原因）；不管怎样，你可以尝试使用 boost.hash_combine 来获得一个准备好的、更或多或少通用的解决方案。

- Massimiliano Janes

---

它并不是真的错了：它不会将相同的对象哈希为不同的值。它更多的是低效，因为它会导致很多不必要的冲突，但这更多的是“不好”而不是“错”。 - Angew is no longer proud of SO

@Angew，好的，但是标准提供了复杂度保证，这种哈希算法无法实现。对我来说，这听起来更像是“错误”而不是“糟糕”。 - Massimiliano Janes

我认为标准并不要求哈希完美无缺。您能否更精确地说明哪些复杂性保证受到影响？ - Angew is no longer proud of SO

这应该足够完成教育任务，但还要看情况。 - Aleksey Kontsevich

@Angew 当然，哈希不需要完美（通常也不可能完美），而且平均复杂度并不会因为哈希具有恒定的“对角线”而改变（因为对角线的测量趋近于零测量集）。尽管如此，这个哈希对于相当合理分布的输入来说会有最坏情况下的行为...无论如何，重新阅读后我同意“错误”可能听起来太强烈了...已编辑。 - Massimiliano Janes