Relation between hasher and key_equal in std::unordered_set

Question

I would say, that there must be a relation between hasher and key_equal. If two elements are the same (calling equal returns true) they must have the same hash, otherwise wrong bucket would be searched for element.

But there is no such thing written either at http://www.cplusplus.com/reference/unordered_set/unordered_set/ or http://en.cppreference.com/w/cpp/container/unordered_set

But it is obviously not working correctly. See example, when I try to filter pairs independent on order of elements ( 1,2 == 2,1)

#include <iostream>
#include <functional>
#include <unordered_set>

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

int main() 
{
   typedef std::pair<int, int> Pair;
    Pair pa = std::make_pair(7,5);
    Pair pb = std::make_pair(5,7);
    Pair pc = std::make_pair(5,1);
    Pair pd = std::make_pair(4,3);
    Pair pe = std::make_pair(5,7);

    struct PairEq
    {
        inline bool operator()(const Pair & p1, const Pair & p2) const
        {
            return (p1.first == p2.first && p1.second == p2.second)
                || (p1.first == p2.second && p1.second == p2.first);
        }
    };

    std::unordered_set<Pair, std::hash<Pair>> h;

    h.insert(pa);
    h.insert(pb);
    h.insert(pc);
    h.insert(pd);
    h.insert(pe);

   for(auto & p : h)
   {
      std::cout << p.first << " " << p.second << "\n";
   }

   // note 5,7 AND 7,5 is outputted
}

Is it safe to assume the usual hash properties : If two elements are equal, they have the same hash. Two same hashes doesn't mean the same elements?

quantdev quantdev · Accepted Answer · 2014-08-28T19:42:34

Yes, this relationship is required, as per the C++ Standard, section § 23.2.5 / 5 [unord.req] - (Unordered associative containers, emphasis mine)

The container’s object of type Hash — denoted by hash — is called the hash function of the container. The container’s object of type Pred — denoted by pred — is called the key equality predicate of the container.

Two values k1 and k2 of type Key are considered equivalent if the container’s key equality predicate returns true when passed those values. If k1 and k2 are equivalent, the container’s hash function shall return the same value for both.

Note that this requirement stands for all unordered associative containers, not just std::unordered_set.

Relation between hasher and key_equal in std::unordered_set

1 Answers