Bagaimana cara menggabungkan nilai hash di C ++ 0x?

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

Saya tidak dapat menemukan hash_combinefungsi, seperti yang disajikan dalam boost . Apa cara terbersih untuk menerapkan sesuatu seperti ini? Mungkin, menggunakan C ++ 0xxor_combine ?

Nah, lakukan saja seperti yang dilakukan orang-orang pendorong:

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

Saya akan membagikannya di sini karena dapat bermanfaat bagi orang lain yang mencari solusi ini: mulai dari jawaban @KarlvonMoor , berikut adalah versi template variadic, yang penggunaannya lebih singkat jika Anda harus menggabungkan beberapa nilai bersama:

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

Pemakaian:

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

Ini awalnya ditulis untuk mengimplementasikan makro variadic agar dengan mudah membuat jenis kustom dapat di-hash (yang menurut saya adalah salah satu penggunaan utama suatu hash_combinefungsi):

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

Pemakaian:

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

Ini juga bisa diselesaikan dengan menggunakan template variadic sebagai berikut:

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

Pemakaian:

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

Seseorang pasti bisa membuat fungsi templat, tapi ini bisa menyebabkan beberapa jenis pengurangan yang buruk misalnya hash("Hallo World!")akan menghitung nilai hash pada pointer daripada pada string. Ini mungkin alasan mengapa standar menggunakan struct.

Beberapa hari yang lalu saya datang dengan versi yang sedikit lebih baik dari jawaban ini (dukungan C ++ 17 diperlukan):

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

Kode di atas lebih baik dalam hal pembuatan kode. Saya menggunakan fungsi qHash dari Qt dalam kode saya, tetapi juga memungkinkan untuk menggunakan hasher lainnya.

Saya sangat suka pendekatan C ++ 17 dari jawaban oleh vt4a2h , namun mengalami masalah: The Restditeruskan oleh nilai sedangkan akan lebih diinginkan untuk meneruskannya dengan referensi const (yang merupakan suatu keharusan jika harus dapat digunakan dengan tipe hanya bergerak).

Berikut adalah versi adaptasi yang masih menggunakan ekspresi lipat (itulah alasan mengapa ia membutuhkan C ++ 17 atau lebih tinggi) dan menggunakan std::hash(bukan fungsi 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), ...);
}

Demi kelengkapan: Semua tipe yang dapat digunakan dengan versi ini hash_combineharus memiliki spesialisasi template untuk hashdimasukkan ke dalam stdnamespace.

Contoh:

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

Jadi tipe Bdalam contoh di atas juga dapat digunakan dalam tipe lain A, seperti yang ditunjukkan contoh penggunaan berikut:

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

The jawaban dengan vt4a2h tentu bagus tapi menggunakan C ++ 17 ekspresi kali lipat dan tidak semua orang mampu untuk beralih ke toolchain baru dengan mudah. Versi di bawah ini menggunakan trik expander untuk meniru ekspresi lipatan dan juga berfungsi di C ++ 11 dan C ++ 14 .

Selain itu, saya menandai fungsi tersebut inlinedan menggunakan penerusan sempurna untuk argumen template 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)...};
}

Contoh langsung di Compiler Explorer