Como faço para combinar valores de hash em C ++ 0x?

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

No hash_combineentanto, não consegui encontrar uma função, conforme apresentado no boost . Qual é a maneira mais limpa de implementar algo assim? Talvez, usando C ++ 0x xor_combine?

Bem, apenas faça como os caras do impulso fizeram:

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);
}

Vou compartilhá-lo aqui, pois pode ser útil para outras pessoas que procuram esta solução: começando com a resposta de @KarlvonMoor , aqui está uma versão de modelo variável, que é mais tersa em seu uso se você tiver que combinar vários valores juntos:

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...);
}

Uso:

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

Isso foi escrito originalmente para implementar uma macro variável para facilmente tornar os tipos personalizados em hash (que eu acho que é um dos principais usos de uma hash_combinefunção):

#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;\
            }\
        };\
    }

Uso:

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

Isso também pode ser resolvido usando um modelo variável da seguinte maneira:

#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;
    }
};

Uso:

#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!");
}

Certamente, alguém poderia fazer uma função de modelo, mas isso poderia causar alguma dedução de tipo desagradável, por exemplo hash("Hallo World!"), calculará um valor de hash no ponteiro em vez de na string. Este é provavelmente o motivo pelo qual o padrão usa uma estrutura.

Alguns dias atrás, eu vim com uma versão ligeiramente melhorada desta resposta (suporte C ++ 17 é necessário):

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), ...);
}

O código acima é melhor em termos de geração de código. Usei a função qHash do Qt no meu código, mas também é possível usar qualquer outro hasher.

Eu realmente gosto da abordagem C ++ 17 da resposta de vt4a2h , no entanto, ela sofre de um problema: O Resté transmitido por valor, ao passo que seria mais desejável transmiti-los por referências const (o que é uma obrigação, se assim for utilizável com tipos de movimento).

Aqui está a versão adaptada que ainda usa uma expressão de dobra (que é a razão pela qual requer C ++ 17 ou superior) e usa std::hash(em vez da função hash 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), ...);
}

Para completar: Todos os tipos que podem ser usados ​​com esta versão do hash_combinedevem ter uma especialização de modelo para hashinjetada no stdnamespace.

Exemplo:

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;
        }
    };
}

Portanto, esse tipo Bno exemplo acima também pode ser usado em outro tipo A, como mostra o seguinte exemplo de uso:

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;
        }
    };
}

A resposta de vt4a2h é certamente boa, mas usa a expressão C ++ 17 fold e nem todos são capazes de mudar para um conjunto de ferramentas mais recente facilmente. A versão abaixo usa o truque do expansor para emular uma expressão de dobra e funciona em C ++ 11 e C ++ 14 também.

Além disso, marquei a função inlinee uso o encaminhamento perfeito para os argumentos do modelo variadic.

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)...};
}

Exemplo ao vivo no Compiler Explorer