Funzione hash di unordered_set

Question

Sto utilizzando un std::unordered_set per la prima volta e ho una domanda sulla funzione hash. Per quanto ho capito, se non si specifica una funzione di hash, verrà automaticamente impostato su std :: hash.

Ho un membro MySet in una delle mie classi:

typedef std::unordered_set<MyClass> USetType; 
USetType mySet; 

Quando provo a costruire, ottengo un errore:

error C2440: 'type cast' : cannot convert from 'const MyClass' to 'size_t' 

E 'necessario definire una funzione di conversione (a size_t) se vuoi usare unordered_set con una classe personalizzata? C'è un modo per evitare di scrivere la tua funzione di hash e solo usando l'impostazione predefinita?

Answer 1

Se non si specifica il proprio hash functor come argomento del modello, per impostazione predefinita sarà std::hash<MyClass>, che non esiste se non lo si definisce.

meglio definiscono la propria specializzazione delle std::hash all'interno dello spazio dei nomi std:

namespace std { 
    template <> 
    struct hash<MyClass> 
    { 
    typedef MyClass  argument_type; 
    typedef std::size_t result_type; 

    result_type operator()(const MyClass & t) const 
    { 
     /* ..calculate hash value for t */ 
    } 
    }; 
} 

e assicurarsi di includere questo codice prima la dichiarazione del hash. In questo modo è possibile dichiarare l'hash semplicemente come std::unordered_set<MyClass> senza ulteriori argomenti del modello.

Non è stato specificato cosa sia l'interno di MyClass, ma una situazione tipica è che il tipo definito dall'utente consiste semplicemente in diversi membri di tipo semplice, per i quali esiste una funzione di hash predefinita. In questo caso, probabilmente vorrai combinare i valori hash per i singoli tipi con un valore hash per l'intera combinazione. La libreria Boost fornisce una funzione chiamata hash_combine per questo scopo. Ovviamente, non vi è alcuna garanzia che funzionerà bene nel vostro caso particolare (dipende dalla distribuzione dei valori dei dati e dalla probabilità di collisioni), ma fornisce un punto di partenza valido e di facile utilizzo.

Ecco un esempio di come usarlo, assumendo MyClass è costituito da due componenti: stringa

#include <unordered_set> 
#include <boost/functional/hash.hpp> 

struct MyClass 
{ 
    std::string _s1; 
    std::string _s2; 
}; 

namespace std { 
    template <> 
    struct hash<MyClass> 
    { 
    typedef MyClass  argument_type; 
    typedef std::size_t result_type; 

    result_type operator()(const MyClass & t) const 
    { 
     std::size_t val { 0 }; 
     boost::hash_combine(val,t._s1); 
     boost::hash_combine(val,t._s2); 
     return val; 
    } 
    }; 
} 

int main() 
{ 
    std::unordered_set<MyClass> s; 
    /* ... */ 
    return 0; 
}