Mapplet Mapplet - 2 months ago 29
C++ Question

C++ unordered_map with pair as key - not compiling

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 this error when I try to compile:

/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::pair<std::__1::basic_string<char>, std::__1::basic_string<char> > >'


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

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 namespace std;
using Vote = pair<string, string>;
using Unordered_map = 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.

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.

Comments