首页 文章

我们什么时候应该为`std :: unordered_set`提供我们自己的Hash函数

提问于
浏览
5

当我编译以下代码时,我看到了与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:对std的未定义引用:: hash> :: operator()(std :: vector>)const'colle2:ld返回1退出状态

然后,我介绍以下自己的Hash,问题解决了 .

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

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

Question 2 >为什么g抱怨带有上述警告的结构HashVector?

谢谢

2 回答

  • 6

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

    当您're using a type that doesn'具有标准库提供的哈希时 . 例如,它不为标准容器提供哈希函数,包括 vector<int> .

    为什么g抱怨带有上述警告的结构HashVector?

    因为你曾经使用 -Weffc++ 来请求(略微过度热心)警告,告诉你何时从没有虚拟析构函数的类继承 . 对于大多数继承用途(即多态性),您不希望这样做 . 但是,在这种情况下,继承只是使用(或者,有些人可能会说,滥用)将一些定义注入类中,因此警告并不表示存在问题 .

    std::unary_function 这样的类已被弃用,因此最好的解决方案是不要继承它 .

  • 5

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

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

    此外,提供自己的哈希函数的另一个原因是,当您对 unordered_set 中的值分布有一些额外的专业知识时 . 散列表的性能对散列函数相对于存储在表中的值的分布的适当性非常敏感 . Here 's a more complete explanation. The standard defaults are just a one-size-fits-all solution, meaning it'简单方便,但几乎总是次优 .

    为什么g抱怨带有上述警告的结构HashVector?

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

    另请注意, std::unary_function (及其亲属)已在最新标准(C 11)中弃用 . 这是因为最新标准提供的类型内省的增强功能(使用 <type_traits>decltype 和类型推断) .

相关问题