相关疑难解决方法(0)

我试图定义一个像这样的unordered_set:

unordered_set<Point> m_Points;

当我编译它时,我收到以下错误:

C++标准不为此类型提供哈希.

课程Point:

class Point{
    private:
        int x, y;
    public:
        Point(int a_x, int a_y)
            : x(a_x), y(a_y)
        {}
        ~Point(){}

        int getX()const { return x; }
        int getY()const { return y; }

        bool operator == (const Point& rhs) const{
            return x == rhs.x && y == rhs.y;
        }

        bool operator != (const Point& rhs) const{
            return !(*this == rhs);
        }
};

• 如何/在哪里为Point定义哈希函数？
• 什么是2D点的好哈希函数？

如何允许STL实现获取我的自定义类型？在MSVC上,有一个类std::tr1::hash,我可以通过使用来部分专门化

namespace std 
{
    namespace tr1 
    { 
        template <> 
        struct hash<MyType> 
        { ... };
    } 
}

但这是推荐的方式吗？此外,这是否也适用于GCC的实施？因为boost::hash,它足以提供免费功能size_t hash_value (const MyType&),是否有类似的TR1实现？

我想要有类似的东西

 unordered_set<vector<pair<int,int>>> us;

但即使没有配对:

#include <vector>
#include <unordered_set>
using namespace std;

int main() {
    unordered_set<vector<int>> um;
}

它失败:

In file included from /usr/include/c++/4.8/bits/hashtable.h:35:0,
                 from /usr/include/c++/4.8/unordered_set:47,
                 from prog.cpp:2:
/usr/include/c++/4.8/bits/hashtable_policy.h: In instantiation of ‘struct std::__detail::_Hash_code_base<std::vector<int>, std::vector<int>, std::__detail::_Identity, std::hash<std::vector<int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, true>’:
/usr/include/c++/4.8/bits/hashtable_policy.h:1402:10:   required from ‘struct std::__detail::_Hashtable_base<std::vector<int>, std::vector<int>, std::__detail::_Identity, std::equal_to<std::vector<int> >, std::hash<std::vector<int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits<true, true, true> >’
/usr/include/c++/4.8/bits/hashtable.h:174:11:   required from ‘class std::_Hashtable<std::vector<int>, std::vector<int>, std::allocator<std::vector<int> >, std::__detail::_Identity, std::equal_to<std::vector<int> >, std::hash<std::vector<int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits<true, true, true> >’
/usr/include/c++/4.8/bits/unordered_set.h:96:18:   required from …

问题

对于用户定义类型的std :: unordered_map或std :: unordered_set的第三个模板参数,std :: hash有什么好的特殊性,所有成员数据类型都已经具有良好的std :: hash特性？

对于这个问题,我将"好"定义为易于实现和理解,合理有效,并且不太可能产生哈希表冲突.商品的定义不包括任何有关安全性的陈述.

什么是谷歌的状态

目前,两个StackOverflow问题是Google搜索"std hash specialization"的第一个问题.

第一个,如何在无序容器中为用户定义的类型专门化std :: hash :: operator()？,解决了打开std命名空间和添加模板特化是否合法的问题.

第二个,如何专门化来自其他库的类型的std :: hash,基本上解决了同样的问题.

这留下了当前的问题.鉴于C++标准库的实现为标准库中的基本类型和类型定义了散列函数,为用户定义的类型专门化std :: hash的简单有效方法是什么？有没有一种很好的方法来组合标准库实现提供的哈希函数？

(编辑感谢dyp.)StackOverflow的另一个问题是如何组合一对哈希函数.

谷歌的其他结果没有任何帮助.

这篇 Dobbs博士的文章指出,两个令人满意的哈希的XOR将产生一个新的令人满意的哈希值.

这篇文章似乎是从知识中说出并暗示了很多东西,但却注重细节.它与第一个例子中的简短评论中的Dr. Dobbs文章相矛盾,称使用XOR组合散列函数会产生一个弱的结果散列函数.

因为XOR应用于任何两个相等的值导致0,我可以看出为什么XOR本身很弱.

元问题

一个很好的理由回答解释为什么这个问题无效且一般无法回答也是受欢迎的.

我不清楚C++ 11标准中hash<T>应该定义用户定义的仿函数.

例如,在23.5.2 Header中<unordered_map>,它显示:

template <class Key,
        class T,
        class Hash = hash<Key>,
        class Pred = std::equal_to<Key>,
        class Alloc = std::allocator<std::pair<const Key, T> > >
    class unordered_map;

这表明,默认情况下,hash<T>在全局命名空间equal_to<>中搜索,而在std命名空间中搜索.

为什么名称空间hash<>与equal_to<>？之间存在差异？

(实际上,在http://www.cplusplus.com/reference/unordered_map/unordered_map/的描述中,都没有指定std命名空间.)

因此,在hash<>为用户类型定义仿函数时,是应该将它包含在namespace std { }块中,还是可以保留在当前命名空间中？

如果代码没有using namespace std;,那么STL容器如何unordered_map知道在std命名空间中查找hash<>与基元类型相关联的预定义仿函数？看起来默认Hash = hash<Key>会找不到这些.

对不起,如果这些都是愚蠢的问题..

如何在一个类中存储类的对象unordered_set？我的程序需要经常检查对象是否存在,如果存在unordered_set,则对该对象进行一些更新.

我已经在线查看了如何使用unordered_set,但遗憾的是大多数教程都是关于使用它int或string类型.但是我如何在课堂上使用它呢？我怎样才能定义一个哈希函数来使node_id下面的例子成为关键的unordered_set？

#include <iostream>
#include <unordered_set>

using namespace std;

// How can I define a hash function that makes 'node' use 'node_id' as key?    
struct node
{
    string node_id;
    double value;
    node(string id, double val) : node_id(id), value(val) {}
};

int main()
{
    unordered_set<node> set;
    set.insert(node("1001", 100));
    if(set.find("1001") != set.end()) cout << "1001 found" << endl;
}

我想存储一对无序整数的浮点值.我无法找到任何易于理解的教程.例如,对于无序对,{i,j}我想存储浮点值f.如何插入,存储和检索这样的值？

我可以std::hash用我自己std::hash在C++ 11中的定义替换实际的实现吗？

我的意思是从我的代码库,而不是触及标准库.

在这种情况下,我看不出任何虚函数/多态的用法,所以我想我无法改变std :: hash的定义？

根据对此问题的接受答案,可以使用专门化为std用户定义的类型提供哈希函数.

#include <unordered_set>
#include <stdint.h>


struct FooBar {
    int i; 
};
namespace std {
    template <> struct hash<FooBar>
    {
        size_t operator()(const FooBar & x) const
        {
            return x.i;
        }
    };
}

int main(){
    std::unordered_set<FooBar> foo(0);
}

但是,文档似乎暗示自定义散列函数也可以显式传递给构造函数,我想为这个散列函数使用一个命名函数.

但是,我当前的尝试遭受编译错误.

#include <unordered_set>
#include <stdint.h>

struct FooBar {
    int i; 
};

const size_t hashFooBar(const FooBar& foo) {
    return foo.i;
}

int main(){
    std::unordered_set<FooBar> foo(0, hashFooBar);
}

什么是正确的模板魔术和方法签名才能使其工作？

所以我使用的库有一个枚举(说它的名字LibEnum).我需要有一个std::unordered_set的LibEnum,但我得到的编译错误是没有专门std::hash为它.我可以很容易地写它并且只返回值的数量(第一个元素是0,第二个1等),但是我应该把它放在哪个专门化以及它应该是什么样子？我无法修改库源.

  enum LibEnum { A, B, C, D};
  std::unordered_set <LibEnum> mySet;
  //need std::hash for LibEnum
  //how should it look like?