Jak połączyć wartości skrótu w C ++ 0x?

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

Nie mogłem jednak znaleźć hash_combinefunkcji, jak przedstawiono w boost . Jaki jest najczystszy sposób na wdrożenie czegoś takiego? Być może używając C ++ 0x xor_combine?

Cóż, po prostu zrób to tak, jak zrobili to faceci doładowania:

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

Podzielę się tym tutaj, ponieważ może być przydatne dla innych, którzy szukają tego rozwiązania: zaczynając od odpowiedzi @KarlvonMoor , oto wariadyczna wersja szablonu, która jest bardziej zwięzła w użyciu, jeśli musisz połączyć kilka wartości razem:

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

Stosowanie:

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

Zostało to pierwotnie napisane w celu zaimplementowania wariadycznego makra, aby łatwo umożliwić hashowanie typów niestandardowych (co moim zdaniem jest jednym z podstawowych zastosowań hash_combinefunkcji):

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

Stosowanie:

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

Można to również rozwiązać za pomocą szablonu wariadycznego w następujący sposób:

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

Stosowanie:

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

Z pewnością można by utworzyć funkcję szablonu, ale mogłoby to spowodować jakieś paskudne odliczenie typu, np. hash("Hallo World!")Obliczy wartość skrótu na wskaźniku zamiast na łańcuchu. Jest to prawdopodobnie powód, dla którego standard używa struktury.

Kilka dni temu wymyśliłem nieco poprawioną wersję tej odpowiedzi (wymagana obsługa 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), ...);
}

Powyższy kod jest lepszy pod względem generowania kodu. Użyłem funkcji qHash z Qt w moim kodzie, ale można też użyć innych skrótów.

Bardzo podoba mi się podejście C ++ 17 z odpowiedzi vt4a2h , jednak występuje problem: Restjest przekazywana przez wartość, podczas gdy byłoby bardziej pożądane, aby przekazać je przez odwołania do stałych (co jest koniecznością, jeśli ma być nadające się do użytku z typami tylko do przenoszenia).

Oto dostosowana wersja, która nadal używa wyrażenia fold (co jest powodem, dla którego wymaga C ++ 17 lub nowszego) i używa std::hash(zamiast funkcji skrótu 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), ...);
}

Ze względu na kompletność: wszystkie typy, które mają być używane w tej wersji, hash_combinemuszą mieć specjalizację szablonu do hashwstrzyknięcia do stdprzestrzeni nazw.

Przykład:

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

Tak więc ten typ Bw powyższym przykładzie jest również użyteczny w innym typie A, jak pokazano w poniższym przykładzie użycia:

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

Odpowiedź przez vt4a2h pewnością jest miły, ale używa C ++ 17-krotny ekspresji i nie każdy jest w stanie przejść do nowszej toolchain łatwo. Poniższa wersja wykorzystuje sztuczkę ekspandera do emulacji wyrażenia fold i działa również w C ++ 11 i C ++ 14 .

Dodatkowo zaznaczyłem funkcję inlinei użyłem idealnego przekazywania dla zmiennych argumentów szablonu.

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

Przykład na żywo w Eksploratorze kompilatora