How can I use tuples as keys in unordered maps without writing a custom hash function?

Using Tuples in Unordered Maps Without Custom Hash Function

You might expect std::unordered_map to effortlessly work with tuple keys out of the box. However, it requires defining a hash function for tuples, as shown below:

template<> struct do_hash<tuple<int, int>> {
    size_t operator()(std::tuple<int, int> const& tt) const {...}
};

This process can become tedious, leading to the question of automating it for C 0x tuples without resorting to variadic templates.

The following approach allows all C 0x tuples containing standard hashable types to become part of unordered_map and unordered_set without additional effort:

#include <tuple>
namespace std {
    namespace {
        template <class T>
        inline void hash_combine(std::size_t& seed, T const& v) {
            // Modified from Boost
            seed ^= std::hash<T>()(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        }

        // Recursive template for hashing tuples
        template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
        struct HashValueImpl {
            static void apply(size_t& seed, Tuple const& tuple) {
                HashValueImpl<Tuple, Index - 1>::apply(seed, tuple);
                hash_combine(seed, std::get<Index>(tuple));
            }
        };

        template <class Tuple>
        struct HashValueImpl<Tuple, 0> {
            static void apply(size_t& seed, Tuple const& tuple) {
                hash_combine(seed, std::get<0>(tuple));
            }
        };
    }

    template <typename... TT>
    struct hash<std::tuple<TT...>> {
        size_t
        operator()(std::tuple<TT...> const& tt) const {
            size_t seed = 0;
            HashValueImpl<std::tuple<TT...>>::apply(seed, tt);
            return seed;
        }
    };
}

By placing the function in the std namespace, it is accessible via argument-dependent name lookup (ADL).

Standard Conformant Code

Specializing objects in the std namespace is undefined behavior. Hence, for a standards-compliant solution, move the code into a separate namespace and forgo the convenience of ADL:

namespace hash_tuple {

// Forward non-tuple types to std::hash
template <class TT>
struct hash {
    size_t
    operator()(TT const& tt) const {
        return std::hash<TT>()(tt);
    }
};

// Hash function combining values in a tuple
template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
struct HashValueImpl {
    static void apply(size_t& seed, Tuple const& tuple) {
        HashValueImpl<Tuple, Index - 1>::apply(seed, tuple);
        hash_combine(seed, std::get<Index>(tuple));
    }
};

template <class Tuple>
struct HashValueImpl<Tuple, 0> {
    static void apply(size_t& seed, Tuple const& tuple) {
        hash_combine(seed, std::get<0>(tuple));
    }
};

// Hash function for tuples
template <typename... TT>
struct hash<std::tuple<TT...>> {
    size_t
    operator()(std::tuple<TT...> const& tt) const {
        size_t seed = 0;
        HashValueImpl<std::tuple<TT...>>::apply(seed, tt);
        return seed;
    }
};
} // namespace hash_tuple

Declare a hash implementation within the hash_tuple namespace to forward all non-tuple types to std::hash and modify hash_combine to use hash_tuple::hash instead of std::hash. Place the remaining code inside the hash_tuple namespace.

To use this solution, you must include the following code, which gives up on the convenience of ADL:

unordered_set<tuple<double, int>, hash_tuple::hash<tuple<double, int>>> test2;

The above is the detailed content of How can I use tuples as keys in unordered maps without writing a custom hash function?. For more information, please follow other related articles on the PHP Chinese website!