Why can't I compile an unordered_map with a pair as key?

Question

I am trying to create an unordered_map to map pairs with integers:

#include <unordered_map>  using namespace std; using Vote = pair<string, string>; using Unordered_map = unordered_map<Vote, int>; 

I have a class where I have declared an Unordered_map as a private member.

However, I am getting the following error when I try to compile it:

/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/type_traits:948:38: Implicit instantiation of undefined template 'std::__1::hash, std::__1::basic_string > >'

I am not getting this error if I use a regular map like map<pair<string, string>, int> instead of an unordered_map.

Is it not possible to use pair as key in unordered maps?

Answer 1

You need to provide a suitable hash function for your key type. A simple example:

#include <unordered_map> #include <functional> #include <string> #include <utility>  // Only for pairs of std::hash-able types for simplicity. // You can of course template this struct to allow other hash functions struct pair_hash {     template <class T1, class T2>     std::size_t operator () (const std::pair<T1,T2> &p) const {         auto h1 = std::hash<T1>{}(p.first);         auto h2 = std::hash<T2>{}(p.second);          // Mainly for demonstration purposes, i.e. works but is overly simple         // In the real world, use sth. like boost.hash_combine         return h1 ^ h2;       } };  using Vote = std::pair<std::string, std::string>; using Unordered_map = std::unordered_map<Vote, int, pair_hash>;  int main() {     Unordered_map um; } 

This will work, but not have the best hash-properties^†. You might want to have a look at something like boost.hash_combine for higher quality results when combining the hashes. This is also discussed in greater detail – including the aforementioned solution from boost – in this answer.

For real world use: Boost also provides the function set hash_value which already provides a hash function for std::pair, as well as std::tuple and most standard containers.

---

^†More precisely, it will produce too many collisions. E.g., every symmetric pair will hash to 0 and pairs that differ only by permutation will have the same hash. This is probably fine for your programming exercise, but might seriously hurt performance of real world code.