Функция хеширования unordered_map С++

Мне нужно определить 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. Каков правильный способ сделать это? Спасибо.

Ответы

Ответ 1

Это неудачное упущение в С++ 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;

Если вы хотите использовать свой хорватский хэш (который не имеет хороших статистических свойств), вы должны явно указать параметры шаблона:

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

Обратите внимание, что нет необходимости указывать копию хешерного объекта, поскольку по умолчанию используется значение по умолчанию - постройте один для вас.

Ответ 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;

Ответ 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) );
}

EDIT:
Вам не нужно определять равный предикат, поскольку operator== определен для std::pair, и он делает именно то, что я сделал в pairEquals. Вам потребуется только определение pairEquals, если вы ожидаете, что сравнение будет выполнено по-другому.