Come vengono memorizzati gli oggetti in unordered_sets?

Un unordered_set è specificato un po 'più "strettamente" di quanto la maggior parte delle persone sembra realizzare, quindi è difficile (se possibile del tutto) implementarlo come qualsiasi cosa eccetto una tabella hash che risolve le collisioni hash concatenando.

In particolare, lo standard richiede che la tabella hash sia composta da bucket, che ogni bucket contenga elementi che hanno hash sullo stesso valore, che la dimensione di un bucket sia ottenibile con una complessità costante e che attraversando gli elementi in un bucket sia possibile con complessità lineare.

Questi requisiti sono banali da soddisfare se usi il concatenamento di collisioni e difficile o impossibile incontrarli diversamente.

Come tale, la struttura dei dati di base di solito assomiglia a qualcosa di simile (ignorando alcuni parametri extra del modello di cui non ci importa adesso):

template <class T>
class unordered_set {
    std::vector<std::vector<T> > data;

    // ...

Il membro insert potrebbe apparire vagamente simile a questo:

pair<iterator, bool>
insert(T t) { 
    auto raw_pos = hash(t); // hash the input
    auto pos = raw_pos % data.size(); // reduce the range to that of the table

    auto &bucket = data[pos];

    // try to find existing item:
    auto existing = std::find(bucket.begin(), bucket.end(), t);

    // if there was no existing item, add the new one
    if (existing == bucket.end()) {
        bucket.push_back(t);
        return {bucket.back(), true};
    }
    // if there was an existing item, return iterator and false to indicate we didn't add
    return {existing, false};
}

Si noti che questo non è sicuramente un tentativo di qualcosa di simile al codice di produzione - solo uno schema generale della logica di base. E quando dico "base", intendo, una vera implementazione richiede molta più logica, come ad esempio ridimensionare la tabella nel caso in cui la nuova aggiunta aumenti il fattore di carico oltre il limite specificato. In effetti, parte del codice non è solo semplificata, è tecnicamente sbagliata come è adesso (ma risolverlo renderebbe il codice più complesso senza aggiungere molto).