unordered_map哈希函数c ++

Question

我需要像这样定义一个unordered_map unordered_map<pair<int, int>, *Foo>,定义和传递一个hash和equal函数到这个地图的语法是什么？

我试过传递给它这个对象:

class pairHash{
public:
    long operator()(const pair<int, int> &k) const{
        return k.first * 100 + k.second;
    }
};

没有运气:

unordered_map<pair<int, int>, int> map = unordered_map<pair<int, int>, int>(1,
*(new pairHash()));

我不知道是什么size_type_Buskets意思所以我给了它1.做正确的方法是什么？谢谢.

Answer 1

这是C++ 11中遗漏的一个遗漏; Boost有答案hash_combine.随意粘贴它们!这是我如何散列对:

template <class T>
inline void hash_combine(std::size_t & seed, const T & v)
{
  std::hash<T> hasher;
  seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

namespace std
{
  template<typename S, typename T> struct hash<pair<S, T>>
  {
    inline size_t operator()(const pair<S, T> & v) const
    {
      size_t seed = 0;
      ::hash_combine(seed, v.first);
      ::hash_combine(seed, v.second);
      return seed;
    }
  };
}

您可以将hash_combine其用作许多其他内容的基础,例如元组和范围,因此您可以散列整个(有序)容器,例如,只要每个成员都是可单独清洗的.

现在您可以声明一个新地图:

std::unordered_map<std::pair<int, int>, my_mapped_type> mymap;

如果要使用自制的hasher(没有良好的统计属性),则必须明确指定模板参数:

std::unordered_map<std::pair<int,int>, int, pairHash> yourmap;

请注意,不需要指定hasher对象的副本,因为默认情况下是为您构造一个.

Answer 2

如果你使用Boost就可以了,一个更干净的解决方案就是依靠Boost对对的哈希函数的实现(实际上这正是kerrek-sb在他的答案中解释的).因此,您所要做的就是:

#include <unordered_map>
#include <boost/functional/hash.hpp>

using namespace std;
using namespace boost;

unordered_map<pair<int, int>, int, hash<pair<int, int>>> table;

Answer 3

哈希函数的返回类型应该是size_t,不long(虽然这不是错误的原因).您为提供自定义哈希函数而显示的语法不正确.

您还需要提供一个相等的谓词来使上述工作正常进行.

#include <unordered_map>
#include <utility>

using namespace std;

class pairHash{
public:
    size_t operator()(const pair<int, int> &k) const{
        return k.first * 100 + k.second;
    }
};

struct pairEquals : binary_function<const pair<int,int>&, const pair<int,int>&, bool> {
  result_type operator()( first_argument_type lhs, second_argument_type rhs ) const
  {
    return (lhs.first == rhs.first) && (lhs.second == rhs.second);
  }
};     

int main()
{
  unordered_map<pair<int, int>, int, pairHash, pairEquals> myMap;

  myMap[make_pair(10,20)] = 100;
  myMap.insert( make_pair(make_pair(100,200), 1000) );
}

编辑:
你不需要定义相同的谓词,因为它operator==是定义的std::pair,它完全正是我所做的pairEquals.pairEquals如果您希望以不同方式进行比较,则只需要定义.