Функция хеширования для вложенной структуры в структуре при использовании unordered_set - PullRequest
Новая
       41

Функция хеширования для вложенной структуры в структуре при использовании unordered_set

2 голосов
/ 30 ноября 2011

Я пытаюсь использовать unordered_set для поддержки уникального списка структур. Я определил хеш-функцию для структуры Name, однако я получаю ошибки компиляции, когда расширяю структуру Name, чтобы она содержала другой член структуры, Address. Я знаю, что мне нужно указать, как хешируется структура Address, но я не могу понять, где и как. 

#include <unordered_set>
#include <string>

using namespace std;

struct Address
{
    int num;
};

struct Name
{
    string first;
    string second;
    Address address;
};


struct hashing_fn {

    size_t operator()(const Address &a ) const
    {
        return  hash<int>()(a.num);
    }

    size_t operator()(const Name &name ) const
    {
        return hash<string>()(name.first) ^ hash<string>()(name.second) ^ hash<Address>()(name.address);
    }
};

int main(int argc, char* argv[])
{
    unordered_set<Name,hashing_fn> ids;
    return 0;
}

Обновление

Только для завершения, это было исправлением: 

template<>
struct hash<typename Address> {
    size_t operator()(const Address &a ) const
    {
        return  hash<int>()(a.num);
    }
};

1 Ответ

2 голосов
/ 30 ноября 2011

Вы никогда не определили hash<Address>! Вместо этого вы должны использовать свою собственную функцию operator()(name.address).

Простое XORing, возможно, не лучшее решение. Я настоятельно рекомендую вам скопировать Boost's hash_combine() и поместить всю нагрузку в namespace std: 

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 <> struct hash<Address>
  {
    inline size_t operator()(const Address & a) const
    {
      return hash<int>()(a.num);
    }
  };

  template <> struct hash<Name>
  {
    inline size_t operator()(const Name & a) const
    {
      size_t seed = 0;
      hash_combine(seed, name.first);
      hash_combine(seed, name.second);
      hash_combine(seed, name.address);
      return seed;
    }
  };
}

Теперь вы можете использовать типы напрямую (при условии реализации компаратора равенства): std::unordered_set<Name> s;

...