c++ - 我们什么时候应该为 `std::unordered_set` 提供我们自己的哈希函数

Question

当我编译下面的代码时，我看到了与 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: 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_hash_code(std::vector > const&) const': /usr/include/c++/4.6/bits/hashtable_policy.h:753: undefined reference to 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 returned 1 exit status

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

问题 1> 我们什么时候应该为 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; 
}

warning: base class ‘struct std::unary_function, unsigned int>’ has a non-virtual destructor [-Weffc++]

问题 2> 为什么 g++ 会提示 struct HashVector 并出现上述警告？

谢谢

Answer 1

When should we provide our own Hash for std::unordered_set?

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

Why the g++ complain about the struct HashVector with the above warning?

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

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