6

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

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：在函数`std::__detail::_Hash_code_base

, std::vector >, std::_Identity > >, std::equal_to > >, std::hash > >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, false>::_M_hash_code( std::vector > const&) const': /usr/include/c++/4.6/bits/hashtable_policy.h:753: 未定义引用std::hash<std::vector<int, std::allocator<int> > ::operator()(std::vector<int, std::allocator<int> >) const' /tmp/ccCQFQ4N.o: In function std::__detail::_Hash_code_base , std::vector >, std::_Identity > , std::equal_to > >, std::hash > >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, false>::_M_bucket_index(std::__detail::_Hash_node >, false> const* , unsigned int) const': /usr/include/c++/4.6/bits/hashtable_policy.h:763: undefined reference to `std::hash > ::operator()(std::vector >) const' collect2: ld返回 1 个退出状态

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

问题 1 > 我们应该什么时候提供我们自己的 Hash std::unordered_set？我们什么时候应该为 提供我们自己的等效函数std::unordered_set？

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; 
}

警告：基类 'struct std::unary_function, unsigned int>' 有一个非虚拟析构函数 [-Weffc++]

问题 2 > 为什么 g++ 用上述警告抱怨 struct HashVector？

谢谢

4

2 回答 2

6

我们什么时候应该提供我们自己的哈希std::unordered_set？

当您使用的类型没有标准库提供的散列时。例如，它不为标准容器提供哈希函数，包括vector<int>.

为什么 g++ 用上述警告抱怨 struct HashVector？

因为你曾经-Weffc++请求过一个（有点过分热心的）警告来告诉你，无论何时你从一个没有虚拟析构函数的类继承。对于继承的大多数用途（即多态性），您不想这样做。但是，在这种情况下，继承只是用于（或者，有些人可能会说，被滥用）将一些定义注入到类中，因此警告并不表示存在问题。

类似的类std::unary_function已被弃用，因此最好的解决方案是根本不继承它。

于 2013-07-17T16:42:55.090 回答
5

我们什么时候应该为 std::unordered_set 提供我们自己的哈希？

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

此外，提供您自己的哈希函数的另一个原因是当您对unordered_set. 哈希表的性能对于哈希函数对于存储在表中的值的分布的适用程度非常敏感。这里有一个更完整的解释。标准默认值只是一种万能的解决方案，这意味着它简单方便，但几乎总是次优的。

为什么 g++ 用上述警告抱怨 struct HashVector？

这主要是应用与经典面向对象编程最相关的警告（使用基类作为派生类的动态多态接口）的问题。在这种情况下，不将析构函数定义为虚拟是一个非常严重的错误（这允许从基类实例（例如delete base_ptr;）正确销毁派生类。正如 Mike 所建议的那样，这是因为-Weffc++已启用（主要应用新手级别的经典 OOP 样式警告消息）。但是，在您的代码中，继承是在通用编程的上下文中使用的，其中继承以非常不同的方式使用（主要是为类注入一些基础属性和特征）。在这种情况下，基类没有虚拟析构函数不是问题，因为它不打算在动态多态设置中使用，而是在静态多态设置中使用。

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

于 2013-07-17T16:57:36.997 回答