标准容器没有std::hash的专门化吗？

Question

我 刚刚 发现自己有点惊讶，无法简单地使用一个

std::unordered_set<std::array<int, 16> > test;

因为似乎没有针对std::array的std::hash专门化。为什么会这样？还是我没有找到它？如果确实没有，下面的实现尝试是否可以简化？

namespace std
{
    template<typename T, size_t N>
    struct hash<array<T, N> >
    {
        typedef array<T, N> argument_type;
        typedef size_t result_type;

        result_type operator()(const argument_type& a) const
        {
            hash<T> hasher;
            result_type h = 0;
            for (result_type i = 0; i < N; ++i)
            {
                h = h * 31 + hasher(a[i]);
            }
            return h;
        }
    };
}

我真的认为这应该是标准库的一部分。

- fredoverflow

---

实际上并没有这样的特权，只有std::string和相关类型才拥有。如果我说这是因为C++试图使其标准数据结构达到当前技术水平所做的努力还没有完成整个工作，那么我会不会很不受欢迎？实际上，并没有任何需要模板的"hash"特化（这反过来又需要它们的模板参数具有可哈希性）。唯一需要特化的是内置类型和四个具体的字符串类。因此，我怀疑在这里已经划了一个界限。 - Steve Jessop

string、u16string、u32string、wstring（在C++11中为21.6）。我认为pair和tuple应该是下一个最重要的目标，其次是标准容器，再其次是任何由可哈希成员组成的聚合类型的默认哈希。 - Steve Jessop

显然，string哈希器需要一个内部函数来对一块内存进行哈希。我想知道为什么它们没有要求实现直接公开它？ - Nemo

@nemo 没有人将其写成委员会的论文。只有当有人足够关心时，事情才会成为标准。 - Alan Stokes

boost::hash_combine 使用 seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);，如果有人感兴趣的话。这看起来更加健壮一些。 - Rag

Answer 1

虽然不是答案，但这里有一些有用的信息。C++11标准的2月份草案规定了以下类型的std::hash特化：

• error_code § 19.5.5
• bitset<N> § 20.5.3
• unique_ptr<T, D> § 20.7.2.36
• shared_ptr<T, D> § 20.7.2.36
• type_index § 20.13.4
• string § 21.6
• u16string § 21.6
• u32string § 21.6
• wstring § 21.6
• vector<bool, Allocator> § 23.3.8
• thread::id § 30.3.1.1

以及所有这些类型：§ 20.8.12

template <> struct hash<bool>;
template <> struct hash<char>;
template <> struct hash<signed char>;
template <> struct hash<unsigned char>;
template <> struct hash<char16_t>;
template <> struct hash<char32_t>;
template <> struct hash<wchar_t>;
template <> struct hash<short>;
template <> struct hash<unsigned short>;
template <> struct hash<int>;
template <> struct hash<unsigned int>;
template <> struct hash<long>;
template <> struct hash<long long>;
template <> struct hash<unsigned long>;
template <> struct hash<unsigned long long>;
template <> struct hash<float>;
template <> struct hash<double>;
template <> struct hash<long double>;
template<class T> struct hash<T*>;

- Mooing Duck

Answer 2

我不确定为什么标准库没有包含这个功能，但Boost针对可以从可哈希类型制作的所有内容都提供了哈希函数。其中关键函数是hash_combine，你可以从boost/functional/hash/hash.hpp中复制它。

使用hash_combine，Boost可以派生出range_hash（只需结合范围内每个元素的哈希值），以及用于对pair和tuple进行哈希的工具。range_hash可以进而用于哈希任何可迭代容器。

- Kerrek SB

---

是的，“range_hash”听起来应该是标准中的一部分。 - fredoverflow