funzione hash Definire come parte di una struttura

Question

So che è possibile definire una funzione hash per un struct X definendo una funzione di hash separata struct:

struct hash_X { 
    size_t operator()(const X &x) const {} 
    bool operator()(const X &a, const X &b) const {} 
}; 
int main() { 
    unordered_set<X, hash_X, hash_X> s; 
} 

Ma io sto cercando qualcosa di simile operator<, che può essere collegato a struct X stesso, ad es con set:

struct X { 
    bool operator<(const X &other) const {} 
}; 
int main() { 
    set<X> s; 
} 

L'obiettivo finale è qualcosa di simile:

struct X { 
    size_t operator()(void) const {} 
    bool operator()(const X &other) const {} 
}; 

int main() { 
    unordered_set<X> s; 
} 

Questo è possibile in C++?

Answer 1

std::unordered_set è definito all'interno dello spazio dei nomi std. E usa le strutture std::hash per hash molti tipi diversi.Se si desidera essere in grado di utilizzare std::unordered_set<X> (senza aggiungere molte informazioni alla dichiarazione), è necessario creare un altro sovraccarico del modello std::hash, in modo da renderlo hash la propria struttura.

Si dovrebbe essere in grado di farlo funzionare nel modo seguente:

# include <unordered_set> 
struct X { 
    size_t operator()(void) const {} 
    bool operator()(const X &other) const {} 
}; 

namespace std { 
    template<> 
    struct hash<X> { 
     inline size_t operator()(const X& x) const { 
      // size_t value = your hash computations over x 
      return value; 
     } 
    }; 
} 

int main() { 
    std::unordered_set<X> s; 
} 

---

AndAlso, è necessario fornire sia un sovraccarico per std::equal_to, o di un operatore di confronto (operator==()) per la vostra struttura. Si dovrebbe aggiungere uno dei seguenti modi:

struct X { 
    ... 
    inline bool operator==(const X& other) const { 
     // bool comparison = result of comparing 'this' to 'other' 
     return comparison; 
    } 

}; 

Oppure:

template <> 
struct equal_to<X> { 
    inline bool operator()(const X& a, const X& b) const { 
     // bool comparison = result of comparing 'a' to 'b' 
     return comparison; 
    } 
}; 

Answer 2

Non c'è nessun operatore hash, ma si potrebbe nascondere il hash struct all'interno della vostra X:

struct X 
{ 
    std::string name; 

    struct hash 
    { 
     auto operator()(const X& x) const 
     { return std::hash<std::string>()(x.name); } 
    }; 
}; 

Si potrebbe anche fare un amico e fare name privato, ecc

Live example

Answer 3

Suggerirei di prendere in considerazione una classe hash più generale. Si potrebbe definire per questa classe tutte le operazioni di manipolazione comuni hash che potreste avere bisogno:

struct ghash { 
    // all the values and operations you need here 
}; 

Poi in tutte le fasce in cui si desidera calcolare un hash, si potrebbe definire un operatore di conversione

struct X { 
    operator ghash() { // conversion operator 
     ghash rh; 
     // compute the hash 
     return rh; 
    } 
}; 

È possono poi facilmente calcolare l'hash:

X x; 
ghash hx = x; // convert x to a hash 
hx = (ghash)x; // or if you prefer to make it visible 

questo modo sarà più facile per estendere l'uso della vostra struttura hash senza reinventare il terreno comune per qualsiasi altro struct X , Y, Z che potrebbe richiedere un hash in futuro.

Live demo here

Answer 4

namespace hashing { 
    template<class T> 
    std::size_t hash(T const&t)-> 
    std::result_of_t<std::hash<T>(T const&)> 
    { 
    return std::hash<T>{}(t); 
    } 
    struch hasher { 
    template<class T> 
    std::size_t operator()(T const&t)const{ 
     return hash(t); 
    } 
    }; 
} 

quanto sopra è qualche boilerplate che imposta un sistema ADL basato hash.

template<class T> 
using un_set=std::unordered_set<T,hashing::hasher>; 
template<class K, class V> 
using un_map=std::unordered_map<K,V,hashing::hasher>; 

ora crea due alias di contenitore in cui non è necessario specificare l'hasher.

Per aggiungere un nuovo hashable:

struct Foo { 
    std::string s; 
    friend size_t hash(Foo const&f){ 
    return hashing::hasher{}(s); 
    } 
}; 

e Foo opere in un_set e un_map.

Vorrei aggiungere il supporto per std contenitori e tuple nello spazio dei nomi hashing (ignorare la funzione hash per loro) e magicamente anche quelli funzioneranno.