¿Cómo combino valores hash en C ++ 0x?

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

Sin embargo, no pude encontrar una hash_combinefunción, como se presenta en boost . ¿Cuál es la forma más limpia de implementar algo como esto? ¿Quizás, usando C ++ 0x xor_combine?

Bueno, hazlo como lo hicieron los chicos de impulso:

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

Lo compartiré aquí, ya que puede ser útil para otras personas que buscan esta solución: a partir de la respuesta de @KarlvonMoor , aquí hay una versión de plantilla variada, que es más tersa en su uso si tiene que combinar varios valores:

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

Esto se escribió originalmente para implementar una macro variadic para hacer fácilmente los tipos personalizados hash (que creo que es uno de los usos principales de una hash_combinefunción):

#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

Esto también podría resolverse utilizando una plantilla variada de la siguiente manera:

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

Ciertamente se podría hacer una función de plantilla, pero esto podría causar alguna deducción de tipo desagradable, por ejemplo hash("Hallo World!"), calculará un valor hash en el puntero en lugar de en la cadena. Esta es probablemente la razón por la que el estándar usa una estructura.

Hace unos días se me ocurrió una versión ligeramente mejorada de esta respuesta (se requiere compatibilidad con C ++ 17):

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

El código anterior es mejor en términos de generación de código. Usé la función qHash de Qt en mi código, pero también es posible usar cualquier otro hash.

Realmente me gusta el enfoque de C ++ 17 de la respuesta de vt4a2h , sin embargo, tiene un problema: Restse transmite por valor, mientras que sería más deseable transmitirlos mediante referencias constantes (que es imprescindible si debe ser utilizable con tipos de solo movimiento).

Aquí está la versión adaptada que todavía usa una expresión de plegado (que es la razón por la que requiere C ++ 17 o superior) y usa std::hash(en lugar de la función 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), ...);
}

En aras de la integridad: todos los tipos que se podrán utilizar con esta versión de hash_combinedeben tener una especialización de plantilla para hashinyectarse en el stdespacio de nombres.

Ejemplo:

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

Entonces, ese tipo Ben el ejemplo anterior también se puede usar dentro de otro tipo A, como muestra el siguiente ejemplo 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;
        }
    };
}

La respuesta de vt4a2h es ciertamente agradable, pero usa la expresión C ++ 17 veces y no todos pueden cambiar fácilmente a una cadena de herramientas más nueva. La siguiente versión utiliza el truco de expansión para emular una expresión de plegado y también funciona en C ++ 11 y C ++ 14 .

Además, inlinemarqué la función y utilicé el reenvío perfecto para los argumentos de la plantilla 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)...};
}

Ejemplo en vivo en Compiler Explorer