Use pair as a key in std::unordered_set in C++

This post will discuss how to use std::pair as a key in std::unordered_set in C++.

In the previous post, we have seen that the default value for the second template parameter of std::set is std::less, which will delegate to operator<. Since operator< is defined for pairs, std::set performs a lexicographical comparison on two pair objects to define order. This is the reason the following declaration works in C++:

1	std::set<std::pair<int, int>> s;

On the other hand, std::unordered_set throws a compilation error when std::pair is used as a key.

1	std::unordered_set<std::pair<int, int>> s;

This is because unordered containers like std::unordered_set and std::unordered_map uses std::hash for computing hash value for its keys and there is no standard specialization of std::hash for std::pair in the C++ library.

To use pair as a key in a std::unordered_set, we can follow any of the following approaches:

1. Using `std::hash` function

We can define the specialization for std::hash that works with std::pair.

#include <iostream>

#include <unordered_set>

#include <utility>

struct pair_hash

{

template <class T1, class T2>

std::size_t operator () (std::pair<T1, T2> const &pair) const

{

std::size_t h1 = std::hash<T1>()(pair.first);

std::size_t h2 = std::hash<T2>()(pair.second);

return h1 ^ h2;

}

};

int main()

{

std::unordered_set<std::pair<std::string, int>, pair_hash> set = {

{"two", 2}, {"one", 1}, {"four", 4}, {"three", 3}

};

for (auto const &p: set) {

std::cout << p.first << ": " << p.second << std::endl;

}

return 0;

}

Download Run Code

Output:

four: 4
one: 1
three: 3
two: 2

The above code uses XOR as a hash combination function for simplicity. XOR should be avoided as XOR is symmetric (x ^ y == y ^ x) and maps identical values to zero (x ^ x == y ^ y == 0). This would end up with far too many collisions in the real world. For production code, we should shift/rotate one of the hashes before XORing.

2. Using boost Library

Since there is no specialization of std::hash for std::pair in the standard library, a good alternative is to use the boost::hash from Boost.Functional. We can use it to hash integers, floats, pointers, strings, arrays, pairs, and standard containers.

#include <iostream>

#include <unordered_set>

#include <utility>

#include <boost/functional/hash.hpp>

typedef std::pair<std::string, int> Pair;

int main()

{

std::unordered_set<Pair, boost::hash<Pair>> set = {

{"two", 2}, {"one", 1}, {"four", 4}, {"three", 3}

};

for (auto const &p: set) {

std::cout << p.first << ": " << p.second << std::endl;

}

return 0;

}

Download Code

Output:

three: 3
four: 4
one: 1
two: 2

That’s all about using pair as a key in std::unordered_set in C++.

Use pair as a key in std::unordered_set in C++

1. Using std::hash function

2. Using boost Library

Share this:

1. Using `std::hash` function