什么时候我们应该为' std::unordered_set '提供我们自己的散列函数

Question

当我编译以下代码时，我看到了与哈希相关的错误。

int F_no_meaningA(unordered_set<vector<int>>& setVec, vector<int>& vec) 
{
    setVec.insert(vec);
    return 1;
}

int main()
{
  vector<int> W{2, 3, 7}; 
  unordered_set<vector<int>> setVec; 
}

$ g++ --version
g++ (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3

$ g++ $1.cpp -o $1 -g -Wall -Weffc++ -pedantic -std=c++0x

/tmp/ccCQFQ4N.o： 在函数“标准：：__detail：：_Hash_code_base

，标准：：矢量

然后，我介绍了下面自己的Hash，问题就解决了。

问题 1

struct HashVector : unary_function<vector<int>, vector<int>::size_type> {
  vector<int>::size_type operator()(const vector<int>& vec) const {
    vector<int>::size_type sum = 0;
    for(int i : vec) {
      sum = sum*37 + hash<int>()(i);
    }
    return sum;
  }
};

int F_no_meaningB(unordered_set<vector<int>, HashVector>& setVec, vector<int>& vec) 
{
    setVec.insert(vec);
    return 1;
}

int main()
{
  vector<int> W{2, 3, 7}; 
  unordered_set<vector<int>, HashVector> setVec; 
}

警告：基类“结构”std：：unary_function，无符号整型

问题2

非常感谢。

Answer 1

什么时候应该为std::unordered_set提供自己的Hash？

该标准只需要有限数量的专门化，主要用于基元类型。这是因为这些基本类型具有实现可以提供的一些合理的默认“一刀切”哈希函数。更复杂的类型，例如自定义类型或容器，没有明显甚至合理的默认哈希，因此，您需要提供自己的哈希。如果不支持您的值类型，则必须为其提供哈希函数实现。

此外，提供自己的哈希函数的另一个原因是，您对unordered_set中值的分布有一些额外的专业知识。哈希表的性能对于哈希函数相对于表中存储的值的分布的适用性非常敏感。这是一个更完整的解释。标准默认值只是一种一刀切的解决方案，这意味着它既简单又方便，但几乎总是次优。

为什么g抱怨带有上述警告的struct HashVector？

这主要是应用与经典面向对象编程最相关的警告(使用基类作为派生类的动态多态接口)。在这种情况下，不将析构函数定义为虚拟的是一个非常严重的错误(这允许从基类实例中正确地析构派生类(例如，< code > delete base _ ptr)。正如Mike所建议的，这是因为启用了< code>-Weffc (它主要应用新手级别的经典OOP风格的警告消息)。然而，在您的代码中，继承是在泛型编程的上下文中使用的，在泛型编程中，继承以非常不同的方式使用(主要是用一些基础的属性和特征来灌输一个类)。在这种情况下，基类没有虚析构函数不是问题，因为它不打算用于动态多态设置，而是用于静态多态设置。

另请注意，std::unary_function（及其亲属）在最新标准（C 11）中已被弃用。这是因为最新标准提供了对类型自省的增强（使用

Answer 2

何时应该为std:：unordered_set提供自己的Hash？

当你使用的类型没有标准库提供的散列时。例如，它没有为标准容器提供散列函数，包括< code>vector

为什么g抱怨带有上述警告的struct HashVector？

因为您已经使用了-Weffc来请求一个（稍微过于热情）警告，以便在您从没有虚拟析构函数的类继承时告诉您。对于继承的大多数用途（即多态性），您不希望这样做。然而，在这种情况下，继承只是被用来（或者，有人可能会说，被滥用了）向类中注入一些定义，因此警告并不表示有问题。

不推荐使用std:：unary_function之类的类，因此最好的解决方案是根本不从中继承。