Come scrivere qHash per un contenitore QSet <SomeClass*>?

Question

Ho bisogno di implementare un set di set nella mia applicazione. L'utilizzo di QSet con una classe personalizzata richiede la fornitura di una funzione qHash() e una operator==.

Il codice è il seguente:

class Custom{ 
     int x; 
     int y; 
     //some other irrelevant here 
    } 
    inline uint qHash(Custom* c){ 
     return (qHash(c->x)^qHash(c->y)); 
    } 
    bool operator==(Custom &c1, Custom &c2){ 
     return ((c1.x==c2.x) && (c1.y == c2.y)); 
    } 

    //now I can use: QSet<Custom*> 

Come posso implementare qHash(QSet<Custom*>), per essere in grado di utilizzare QSet< QSet<SomeClass*> >?

Edit:

domanda supplementare: Nella mia applicazione del "set di set" può contenere fino a 15000 set. Ogni sottoinsieme fino a 25 puntatori di classe personalizzati. Come garantire che qHash(QSet<Custom*>) sarà abbastanza unico?

Answer 1

Un modo comune per i contenitori di hash consiste nel combinare gli hash di tutti gli elementi. Boost fornisce hash_combine and hash_range per questo scopo. Questo dovrebbe darti un'idea su come implementarlo per i risultati del tuo qHash.

Quindi, dato il tuo qHash per Custom:

uint qHash(const QSet<Custom*>& c) { 
    uint seed = 0; 

    for(auto x : c) { 
    seed ^= qHash(x) + 0x9e3779b9 + (seed << 6) + (seed >> 2); 
    } 

    return seed; 
} 

Answer 2

Non si può implementare qHash con boost::hash_range/boost::hash_combine (che è ciò che la risposta di PMR fa, in modo efficace), perché QSet è l'equivalente Qt di std::unordered_set, e, come il nome STL suggerisce, questi contenitori sono non ordinati, mentre lo Boost Documentation indica che hash_combine dipende dall'ordine, ad es. permetteranno le hash per diversi valori di hash.

Questo è un problema perché se si ingenuamente hash combinare gli elementi in ordine memorizzato non è possibile garantire che due serie che mettono a confronto pari sono, infatti, uguale, che è uno dei requisiti di una funzione di hash:

For all x, y: x == y => qHash(x) == qHash(y) 

Quindi, se la funzione di combinazione hash deve produrre lo stesso output per qualsiasi permutazione dei valori di input, è necessario commutativo. Fortunatamente, entrambi (non firmato) addizione e l'operazione XOR solo misura la fattura:

template <typename T> 
inline uint qHash(const QSet<T> &set, uint seed=0) { 
    return std::accumulate(set.begin(), set.end(), seed, 
          [](uint seed, const T&value) { 
           return seed + qHash(value); // or^
          }); 
}