wake-up-neo.com

Wie kombiniere ich Hashwerte in C++ 0x?

C++ 0x fügt hash<...>(...) hinzu.

Ich konnte jedoch keine hash_combine-Funktion finden, wie in boost dargestellt. Was ist der sauberste Weg, um so etwas zu implementieren? Vielleicht mit C++ 0x xor_combine?

70
Neil G

Tut es einfach so, wie es die Jungs gemacht haben:

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);
}
77
Karl von Moor

Ich werde es hier teilen, da es für andere nützlich sein kann, die nach dieser Lösung suchen: Ausgehend von @KarlvonMoor answer, hier ist eine variadische Template-Version, die in ihrer Verwendung etwas terser ist, wenn Sie mehrere Werte miteinander kombinieren müssen:

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

Verwendungszweck:

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

Dies wurde ursprünglich geschrieben, um ein variadisches Makro zu implementieren, um benutzerdefinierte Typen leicht hashierbar zu machen (was meiner Meinung nach eine der primären Verwendungen einer hash_combine-Funktion ist):

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

Verwendungszweck:

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
25
Matteo Italia

Dies könnte auch durch die Verwendung einer variadischen Vorlage wie folgt gelöst werden:

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

Verwendungszweck:

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

Man könnte sicherlich eine Schablonenfunktion erstellen, aber dies könnte zu einer unangenehmen Typabzug führen, z. B. hash("Hallo World!") berechnet einen Hashwert im Zeiger und nicht im String. Dies ist wahrscheinlich der Grund, warum der Standard eine struct verwendet.

3
kiloalphaindia

Ich mag den C++ 17-Ansatz von answer by vt4a2h sehr, aber er hat ein Problem: Das Rest wird nach Wert weitergegeben, wohingegen es wünschenswerter wäre, sie weiterzugeben durch const-Referenzen (was ein Muss ist, wenn es mit Nur-Verschieben-Typen verwendet werden soll).

Hier ist die angepasste Version, die immer noch einen Fold-Ausdruck (aus diesem Grund ist C++ 17 oder höher erforderlich) und std::hash (anstelle der Qt-Hash-Funktion) verwendet:

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

Der Vollständigkeit halber: Alle Typen, die mit dieser Version von hash_combine verwendbar sein sollen, müssen ein Template-Spezialisierung für hash aufweisen, das in den std-Namespace eingefügt wird.

Beispiel:

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

Dieser Typ B im obigen Beispiel kann auch in einem anderen Typ A verwendet werden, wie das folgende Verwendungsbeispiel zeigt:

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

Vor ein paar Tagen habe ich eine etwas verbesserte Version von this answer gefunden (C++ 17-Unterstützung ist erforderlich):

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

Der obige Code ist in Bezug auf die Codegenerierung besser. Ich habe die qHash-Funktion von Qt in meinem Code verwendet, es ist jedoch auch möglich, andere Hasher zu verwenden.

0
vt4a2h