Hashing function for nested struct in struct when using an unordered_set

Question

I'm trying to use an unordered_set to maintain an unique list of structs. I've defined the hash function for the struct, Name, however I receive compile errors when I extend the Name struct to contain another struct member, Address. I know I need to specify how the Address struct must be hashed, but I can't seem to figure out where/how.

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

Update

Just for completion, this was the fix:

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

error C2440: 'type cast' : cannot convert from 'const Address' to 'size_t' — mrantifreeze
– mrantifreeze, Commented Nov 30, 2011 at 1:09

Kerrek SB · Accepted Answer · 2011-11-30 01:19:16Z

2

You never defined hash<Address>! Instead, you have to use your own function operator()(name.address).

Simple XORing is maybe not the best solution. I strongly recommend you copy over Boost's hash_combine(), and put the whole load into 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;
    }
  };
}

Now you can use the types directly (subject to implementing an equality comparator): std::unordered_set<Name> s;

edited Nov 30, 2011 at 1:19

answered Nov 30, 2011 at 1:13

Kerrek SB

481k96 gold badges904 silver badges1.1k bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

mrantifreeze Over a year ago

Thank you! Complete oversight on my part.

Kerrek SB Over a year ago

Yes. I strongly advice also to never say using namespace std;, especially never in a header file. That said, defining those specializations of std::hash makes it easy to build up other hashable types by composition, so I like this approach a lot. (Note that hash_combine depends on having a std::hash-able argument.)

mrantifreeze Over a year ago

I fully agree. This is simple scratchpad code, far away from anything in production. Simply for stochastic experimentation. The code will be thrown away, but the lesson has been learned ;)

Collectives™ on Stack Overflow

Hashing function for nested struct in struct when using an unordered_set

Update

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Update

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related