Posso usare una variabile membro come chiave per un hash_set/hash_map?

Question

Ho una classe come questa:

class Foo 
{ 
    long long Id; 
    string x; 
    string y; 
    // other member variables and functions 
}; 

mi piacerebbe conservare questo in un hash_set (o hash_map), ma utilizzare la variabile membro Id come la chiave per l'inserimento e la ricerca. Non sono sicuro di come posso farlo. Ho pensato ai seguenti modi, ma nessuno di questi è veramente buono:

1) Posso scrivere una funzione di hash personalizzata che cancellerà l'oggetto usando l'Id, ma non posso usare il metodo find() su hash_set su cercare l'oggetto con ID (long long) poiché richiede l'inserimento di un oggetto Foo.

2) posso duplicare il Id e creare un hash_map<long long, Foo> invece di un hash_set<long long, Foo> ma ho 100 milioni di istanze di questi oggetti così preferisco non duplicare il campo ID.

3) posso spostare il campo Id esterno del Foo e poi fare hash_map<long long, Foo>, ma sarebbe sorta di disordinato poiché l'ID viene utilizzato internamente dalla classe e sarebbe meglio tenerlo con Foo.

Qualche idea? Quello che sto cercando è un modo per memorizzare gli oggetti ma essere in grado di cercarli nello hash_set utilizzando un long long (da Id).

Grazie!

Answer 1

Questo non può essere una particolare soluzione elegante, ma funziona: definire un operator < (e operator == così, come suggerito CashCow) per la classe che ordina gli oggetti in base al campo Id, poi, quando si vuole fare un find , passa in un oggetto fittizio che contiene lo Id che stai cercando.

Answer 2

1) posso scrivere una funzione di hash personalizzato che hash l'oggetto utilizzando il Id, ma d'altra parte non posso usare il find() metodo su hash_set di ricercare la voce da Id (lunga lungo) poiché sarà necessario che richieda un oggetto Foo.

Questo è un problema comune con la mappa standard e impostare i contenitori. Aggiungi un costruttore o membro statico che crea un oggetto di confronto, un oggetto con solo il membro chiave valido.

Answer 3

L'opzione 2 è la soluzione migliore tra le tre che hai dato. Se sei all'altezza, puoi scrivere un hash_set personalizzato (anche solo un wrapper attorno a quello normale) per fornire ciò che desideri. In tal caso, preferirei l'opzione 1. Potresti facilmente aggiungere una funzione di ricerca che prende solo il valore chiave e la adatta per utilizzare correttamente la funzione di ricerca interna, offrendo tutti i vantaggi.

Answer 4

non ho molta esperienza con esso, ma boost :: multiindex è costruito sulla base di boost :: hash per default, e ha il supporto esplicito per la ricerca di un oggetto in un hash utilizzando solo una chiave trovata nel oggetto.

Answer 5

Se non si trova una soluzione reale per i contenitori hash_set/hash_map, è possibile prendere in considerazione l'utilizzo dell'implementazione della tabella hash uthash, che supporta direttamente il caso d'uso. È C e si basa su macro, ma è una delle più popolari implementazioni di hash table esistenti.