Why can't I use pair as key of unordered_set / unordered_map? [duplicate]

Question

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.

Truce

Answer 1

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

Cardio

would S.emplace(... also work, and if not, what would you change? – Nursling

@Cardio can p.first ^ p.second get the same value for different pairs like p_a and p_b? – Mule

@Mule 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. – Cardio

Answer 2

You need to provide a hash function for pair.

Geoponic