12

Both std::set<> and std::map<> can use a std::pair as a key, but why can't std::unordered_set<> and std::unordered_map<>?

For example:

unordered_set<pair<int,int> > S;
S.insert(make_pair(0, 1));

Does not compile.

Barry
  • 286,269
  • 29
  • 621
  • 977
Rafer
  • 1,170
  • 2
  • 10
  • 15

2 Answers2

21

The unordered_* containers need a hash function. By default, they use std::hash but there is no specialization of std::hash for std::pair<T1,T2> provided in the standard library. On the other hand, the ordered containers rely on std::less (by default) and std::pair does have operator< provided. That's why it just works.

In order to have an unordered container with a pair, you will have to provide a hash functor yourself. For example:

struct SimpleHash {
    size_t operator()(const std::pair<int, int>& p) const {
        return p.first ^ p.second;
    }
};

std::unordered_set<std::pair<int, int>, SimpleHash> S;
S.insert(std::make_pair(0, 1));
Barry
  • 286,269
  • 29
  • 621
  • 977
  • would S.emplace(... also work, and if not, what would you change? – HeinrichStack Dec 30 '16 at 07:36
  • 1
    @Barry can p.first ^ p.second get the same value for different pairs like p_a and p_b? – olivia Apr 13 '17 at 13:07
  • 1
    @olivia Of course. It'll definitely give you the same value for `(a,b)` and `(b,a)`. It's not intended to be a perfect hash function, just a simple example. – Barry Apr 13 '17 at 14:34
0

You need to provide a hash function for pair.

Xiaotian Pei
  • 3,210
  • 21
  • 40