CODEWITHSUNDEEP
c++
icedtrees
icedtrees

Reputation: 6466

Defining hash function as part of a struct

I know that it's possible to define a hash function for a struct X by defining a separate hash function struct:

struct hash_X {
    size_t operator()(const X &x) const {}
    bool operator()(const X &a, const X &b) const {}
};
int main() {
    unordered_set<X, hash_X, hash_X> s;
}

But I'm looking for something like operator<, which can be attached to struct X itself, e.g. with set:

struct X {
    bool operator<(const X &other) const {}
};
int main() {
    set<X> s;
}

The end goal is something like:

struct X {
    size_t operator()(void) const {}
    bool operator()(const X &other) const {}
};

int main() {
    unordered_set<X> s;
}

Is this possible in C++?

Upvotes: 12

Views: 11439

Answers (4)

Rubens
Rubens

Reputation: 14778

std::unordered_set is defined within std namespace. And it uses std::hash structures to hash many different types. If you want to be able to use std::unordered_set<X> (without adding much info to the declaration), you must create another overload of the std::hash template, so as to make it hash your structure.

You should be able to get it working by doing the following:

# include <unordered_set>
struct X {
    size_t operator()(void) const {}
    bool operator()(const X &other) const {}
};

namespace std {
    template<>
    struct hash<X> {
        inline size_t operator()(const X& x) const {
            // size_t value = your hash computations over x
            return value;
        }
    };
}

int main() {
    std::unordered_set<X> s;
}

Andalso, you must provide either an overload to std::equal_to, or a comparison operator (operator==()) for your structure. You should add one of the following:

struct X {
    ...
    inline bool operator==(const X& other) const {
        // bool comparison = result of comparing 'this' to 'other'
        return comparison;
    }

};

Or:

template <>
struct equal_to<X> {
    inline bool operator()(const X& a, const X& b) const {
        // bool comparison = result of comparing 'a' to 'b'
        return comparison;
    }
};

Upvotes: 8

Yakk - Adam Nevraumont
Yakk - Adam Nevraumont

Reputation: 275565

namespace hashing {
  template<class T>
  std::size_t hash(T const&t)->
  std::result_of_t<std::hash<T>(T const&)>
  {
    return std::hash<T>{}(t);
  }
  struch hasher {
    template<class T>
    std::size_t operator()(T const&t)const{
      return hash(t);
    }
  };
}

the above is some boilerplate that sets up an adl-based hash system.

template<class T>
using un_set=std::unordered_set<T,hashing::hasher>;
template<class K, class V>
using un_map=std::unordered_map<K,V,hashing::hasher>;

now creates two container aliases where you do not have to specify the hasher.

To add a new hashable:

struct Foo {
  std::string s;
  friend size_t hash(Foo const&f){
    return hashing::hasher{}(s);
  }
};

and Foo works in un_set and un_map.

I would add support for std containers and tuples into hashing namespace (override the function hash for them), and magically those will work too.

Upvotes: 2

Christophe
Christophe

Reputation: 73406

I'd recommend to consider a more general hash class. You could define for this class all the common hash manipulation operations that you could need: 

struct ghash {
     // all the values and operations you need here 
};

Then in any class where you want to compute a hash, you could define a conversion operator 

struct X { 
    operator ghash () {  // conversion operator 
        ghash rh; 
        // compute the hash
        return rh; 
    }
};

You can then easily calculate the hash: 

 X x; 
 ghash hx = x;   // convert x to a hash 
 hx = (ghash)x;  // or if you prefer to make it visible

This will make it easier to extend the use of your hash structure without reinventing the common ground for any other struct X, Y,Z that may need a hash in the future.

Live demo here

Upvotes: 1

Daniel Frey
Daniel Frey

Reputation: 56863

There is no hash operator, but you could hide the hash struct inside of your X:

struct X
{
    std::string name;

    struct hash
    {
        auto operator()( const X& x ) const
        { return std::hash< std::string >()( x.name ); }
    };
};

You could even make it a friend and make name private, etc.

Live example

Upvotes: 4

Related Questions