Comment combiner les valeurs de hachage en C ++ 0x?

C ++ 0x ajoute hash<...>(...).

Je n'ai pas trouvé de hash_combinefonction cependant, comme présenté en boost . Quelle est la manière la plus propre de mettre en œuvre quelque chose comme ça? Peut-être, en utilisant C ++ 0x xor_combine?

Eh bien, faites-le comme les gars du boost l'ont fait:

template <class T>
inline void hash_combine(std::size_t& seed, const T& v)
{
    std::hash<T> hasher;
    seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}

Je vais le partager ici car il peut être utile à d'autres personnes à la recherche de cette solution: à partir de la réponse @KarlvonMoor , voici une version de modèle variadique, qui est plus courte dans son utilisation si vous devez combiner plusieurs valeurs ensemble:

inline void hash_combine(std::size_t& seed) { }

template <typename T, typename... Rest>
inline void hash_combine(std::size_t& seed, const T& v, Rest... rest) {
    std::hash<T> hasher;
    seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
    hash_combine(seed, rest...);
}

Usage:

std::size_t h=0;
hash_combine(h, obj1, obj2, obj3);

Cela a été écrit à l'origine pour implémenter une macro variadique afin de rendre facilement les types personnalisés hachables (ce qui, je pense, est l'un des principaux usages d'une hash_combinefonction):

#define MAKE_HASHABLE(type, ...) \
    namespace std {\
        template<> struct hash<type> {\
            std::size_t operator()(const type &t) const {\
                std::size_t ret = 0;\
                hash_combine(ret, __VA_ARGS__);\
                return ret;\
            }\
        };\
    }

Usage:

struct SomeHashKey {
    std::string key1;
    std::string key2;
    bool key3;
};

MAKE_HASHABLE(SomeHashKey, t.key1, t.key2, t.key3)
// now you can use SomeHashKey as key of an std::unordered_map

Cela pourrait également être résolu en utilisant un modèle variadique comme suit:

#include <functional>

template <typename...> struct hash;

template<typename T> 
struct hash<T> 
    : public std::hash<T>
{
    using std::hash<T>::hash;
};


template <typename T, typename... Rest>
struct hash<T, Rest...>
{
    inline std::size_t operator()(const T& v, const Rest&... rest) {
        std::size_t seed = hash<Rest...>{}(rest...);
        seed ^= hash<T>{}(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        return seed;
    }
};

Usage:

#include <string>

int main(int,char**)
{
    hash<int, float, double, std::string> hasher;
    std::size_t h = hasher(1, 0.2f, 2.0, "Hello World!");
}

On pourrait certainement créer une fonction de modèle, mais cela pourrait entraîner une déduction de type désagréable, par exemple hash("Hallo World!")calculera une valeur de hachage sur le pointeur plutôt que sur la chaîne. C'est probablement la raison pour laquelle le standard utilise un struct.

Il y a quelques jours, j'ai proposé une version légèrement améliorée de cette réponse (le support C ++ 17 est requis):

template <typename T, typename... Rest>
void hashCombine(uint& seed, const T& v, Rest... rest)
{
    seed ^= ::qHash(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    (hashCombine(seed, rest), ...);
}

Le code ci-dessus est meilleur en termes de génération de code. J'ai utilisé la fonction qHash de Qt dans mon code, mais il est également possible d'utiliser d'autres hachages.

J'aime vraiment l'approche C ++ 17 du réponse de vt4a2h , mais elle souffre d'un problème:Rest est passé par valeur alors qu'il serait plus souhaitable de les transmettre par des références const (ce qui est un must s'il doit être utilisable avec les types de déplacement uniquement).

Voici la version adaptée qui utilise toujours une expression de pli (qui est la raison pour laquelle elle nécessite C ++ 17 ou supérieur) et utilise std::hash(au lieu de la fonction de hachage Qt):

template <typename T, typename... Rest>
void hash_combine(std::size_t& seed, const T& v, const Rest&... rest)
{
    seed ^= std::hash<T>{}(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    (hash_combine(seed, rest), ...);
}

Par souci d'exhaustivité: tous les types utilisables avec cette version de hash_combinedoivent avoir un spécialisation de modèle pour être hashinjectés dans lestd espace de noms.

Exemple:

namespace std // Inject hash for B into std::
{
    template<> struct hash<B>
    {
        std::size_t operator()(B const& b) const noexcept
        {
            std::size_t h = 0;
            cgb::hash_combine(h, b.firstMember, b.secondMember, b.andSoOn);
            return h;
        }
    };
}

Donc, ce type Bdans l'exemple ci-dessus est également utilisable dans un autre type A, comme le montre l'exemple d'utilisation suivant:

struct A
{
    std::string mString;
    int mInt;
    B mB;
    B* mPointer;
}

namespace std // Inject hash for A into std::
{
    template<> struct hash<A>
    {
        std::size_t operator()(A const& a) const noexcept
        {
            std::size_t h = 0;
            cgb::hash_combine(h,
                a.mString,
                a.mInt,
                a.mB, // calls the template specialization from above for B
                a.mPointer // does not call the template specialization but one for pointers from the standard template library
            );
            return h;
        }
    };
}

La réponse de vt4a2h est certainement agréable mais utilise l'expression C ++ 17 fold et tout le monde n'est pas capable de passer facilement à une nouvelle chaîne d'outils. La version ci-dessous utilise l'astuce de l'expandeur pour émuler une expression fold et fonctionne en C ++ 11 et C ++ 14 .

De plus, j'ai marqué la fonction inlineet j'utilise une transmission parfaite pour les arguments du modèle variadique.

template <typename T, typename... Rest>
inline void hashCombine(std::size_t &seed, T const &v, Rest &&... rest) {
    std::hash<T> hasher;
    seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
    (int[]){0, (hashCombine(seed, std::forward<Rest>(rest)), 0)...};
}

Exemple en direct sur l'Explorateur de compilateurs