std, boost o altra implementazione diffusa di un contenitore tabella hash con chiavi implicite

Question

Se ho capito bene, entrambe le chiavi std :: map e std :: unordered_map memorizzano esplicitamente (memorizzano coppie di chiavi/valori). Esiste un altro contenitore pronto per l'uso (std, boost o altra implementazione diffusa) che non memorizzerebbe la chiave, ma piuttosto consentirebbe di derivare la chiave dal valore memorizzato usando una funzione (vale a dire usare la chiave implicita?).

Answer 1

std::set o std::unordered_set, con funzioni di hash e/o confronto idonee per il tipo di valore memorizzato.

Tuttavia, la ricerca verrà eseguita dal tipo di valore memorizzato, non dalla chiave, quindi sarà necessario anche un modo per fabbricare un oggetto temporaneo da una chiave.

Answer 2

Tutti i contenitori ordinati nella libreria C++, ad es. std::set consentire meno confronto tratto tratto, passarlo come un secondo parametro modello (my_less nell'esempio seguente). . Se non lo fai, operator< verrà cercato tramite ADL e usato se trovato (errore di compilazione se non); dovrebbe essere appropriato per molti casi.

Il proprio tratto o operator< può essere utilizzato per definire l'ordine in base ai dati memorizzati in un set, cioè senza chiave. Nessun dato viene copiato per eseguire questo confronto, si prega di notare che ci vogliono riferimenti const.

Se non si desidera creare l'oggetto stack e preferisce utilizzare puntatori heap invece, ovviamente è possibile memorizzare boost::shared_ptr in container standard ordinata e scrivere il meno rispetto tratto di conseguenza. In questo caso si può anche considerare l'utilizzo di boost ptr containers

Esempio:

#include <boost/shared_ptr.hpp> 
#include <set> 
#include <iterator> 
#include <iostream> 

struct order_by_AB { int a; int b; int c; 
    order_by_AB(int a, int b, int c) : a(a), b(b), c(c) {} 
}; 

struct my_less 
{ 
    bool operator()(const boost::shared_ptr<order_by_AB>& lh, const boost::shared_ptr<order_by_AB>& rh) 
    { 
    if (lh->a == rh->a) 
     return lh->b < rh->b; 
    return lh->a < rh->a; 
    } 
}; 

std::ostream& operator<< (std::ostream& os, const boost::shared_ptr<order_by_AB>& rh) 
{ 
    os << "(" << rh->a << "," << rh->b << "," << rh->c << ")"; 
    return os; 
} 

int main() 
{ 
    std::set<boost::shared_ptr<order_by_AB>, my_less> data; 
    data.insert(boost::shared_ptr<order_by_AB>(new order_by_AB(0, 1, 2))); 
    data.insert(boost::shared_ptr<order_by_AB>(new order_by_AB(2, 3, 2))); 
    data.insert(boost::shared_ptr<order_by_AB>(new order_by_AB(0, 3, 2))); 
    data.insert(boost::shared_ptr<order_by_AB>(new order_by_AB(2, 1, 2))); 
    std::copy(data.begin(), data.end(), std::ostream_iterator<boost::shared_ptr<order_by_AB>>(std::cout, "\n")); 
    return 0; 
} 

A cura a dare esempio di funtore specificato dall'utente per il confronto. A cura aggiungere boost::shared_ptr in un contenitore

Answer 3

Si potrebbe essere alla ricerca di Boost.Intrusive. Spingi i contenitori intrusivi "agganciati" ai tuoi tipi di valore per fornire le caratteristiche di un determinato contenitore (ad es. Set, elenco, albero AVL, ecc.) Direttamente dagli oggetti.

Vedere Differences between intrusive and non-intrusive containers per una panoramica delle differenze tra contenitori STL e contenitori Boost Intrusive.