Comment puis-je utiliser des tuples comme clés dans des cartes non ordonnées sans écrire de fonction de hachage personnalisée ?

Utilisation de tuples dans des cartes non ordonnées sans fonction de hachage personnalisée

Vous pouvez vous attendre à ce que std::unordered_map fonctionne sans effort avec les clés de tuple prêtes à l'emploi. Cependant, cela nécessite de définir une fonction de hachage pour les tuples, comme indiqué ci-dessous :

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

Ce processus peut devenir fastidieux, ce qui pose la question de son automatisation pour les tuples C 0x sans recourir à des modèles variadiques.

L'approche suivante permet à tous les tuples C 0x contenant des types hachables standard de faire partie de unordered_map et unordered_set sans frais supplémentaires 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;
        }
    };
}

En plaçant la fonction dans l'espace de noms std, elle est accessible via la recherche de nom dépendante de l'argument (ADL).

Code conforme au standard

Objets spécialisés dans l'espace de noms std, le comportement n'est pas défini. Par conséquent, pour une solution conforme aux normes, déplacez le code dans un espace de noms distinct et renoncez à la commodité d'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

Déclarez une implémentation de hachage dans l'espace de noms hash_tuple pour transférer tous les types non-tuples vers std : :hash et modifiez hash_combine pour utiliser hash_tuple::hash au lieu de std::hash. Placez le code restant dans l'espace de noms hash_tuple.

Pour utiliser cette solution, vous devez inclure le code suivant, qui renonce à la commodité d'ADL :

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!