Fast hash for std::set<int> of two values?

I am using a std::set<int> for the key of a std map (std::unordered_map<std::Set<int>,float>). I need a hash for this set.

The set will always be only two integ开发者_C百科ers, whose values could be up to 2 million.

Any ideas on a good and fast hash for such a key as performance is critical?

You could use boost::hash_combine() : http://www.boost.org/doc/libs/1_44_0/doc/html/hash/combine.html

You didn't exactly state what the purpose of your lookup is, but maybe you should (or shouldn't):

• simply use a struct { int a, b; } as a key - you control the insertion of the members (make sure a <= b)

• use a Sparse Matrix implementation

Regards

rbo

I'd ditch the set idea (it is a waste of both memory and time to store two integers in a std::set) and go with the pair. Then define

template <class A>
struct unordered_pair_hash
{
  std::size_t operator()(const std::pair<A, A>& p) const { 
    using std::min;
    using std::max;
    return std::hash<A>()(min(p.first, p.second))+
        17*std::hash<A>()(max(p.first, p.second));
  }
};

template <class A>
struct unordered_pair_eq
{
  bool operator()(const std::pair<A, A>& p1, const std::pair<A, A>& p2) const {
    using std::min;
    using std::max;
    return min(p1.first, p1.second)==min(p2.first, p2.second) &&
           max(p1.first, p1.second)==max(p2.first, p2.second);
  }
};

and then declare the map with a custom hash and equality.

std::unordered_map<std::pair<int, int>, float, unordered_pair_hash<int>, unordered_pair_eq<int> > ...