Tipo di dati per la tabella di ricerca/indice nell'array

Question

Si supponga di avere una classe "Widget". Nella mia applicazione, creo molti widget che (per località cache e altri motivi) mantengo un vettore.

Per ricerche efficienti vorrei implementare un indice di dati. Per il gusto della domanda, supponiamo che sia una semplice tabella di ricerca dagli indici int agli elementi Widget nel vettore sopra menzionato. La mia domanda è: quale dovrebbe essere il contenuto della tabella di ricerca. In altre parole, con quale tipo dovrei sostituire il punto interrogativo in

using LookupTable = std::vector<?> 

vedo le seguenti opzioni:

• Riferimenti (Widget &, o meglio come deve essere assegnabili: reference_wrapper <widget>)
• puntatori (widget *)
• indici nel vettore widget (size_t)
• oggetti iteratore che punta nel vettore Widget (std :: vector <Widget> :: iterator)

Tra queste opzioni, indici sembrano essere l'unica opzione che non vengono invalidato da un ridimensionamento vettoriale. Potrei essere in grado di evitare le ridimensionazioni, tuttavia, implementare la tabella di ricerca in questo modo significa fare supposizioni sull'implementazione del vettore che sembra irragionevole da un punto di vista del "design disaccoppiato".

Gli indici OTOH non sono typesafe: se la cosa che ottengo dalla tabella di ricerca era un riferimento, potevo utilizzarla solo per accedere al widget corrispondente. L'utilizzo di valori size_t posso fare operazioni senza senso come moltiplicando il risultato per 3. Considera anche i seguenti due firme:

void doSomethingWithLookupResult(Widget& lookupResult); 
void doSomethingWithLookupResult(size_t lookupResult); 

Il primo è molto più descrittivo.

In breve: quale tipo di dati posso utilizzare per la mia tabella di ricerca per ottenere sia un disaccoppiamento dall'implementazione del vettore che la sicurezza del tipo?

Answer 1

È possibile creare una classe che rappresenta un indice che contiene anche informazioni di tipo (in fase di compilazione).

#include <vector> 

template <class T> 
struct typed_index { 
    typed_index(int i) : i(i) {} 

    template <class CONTAINER> 
    T &operator[](CONTAINER &c) { return c[i]; } 
    template <class CONTAINER> 
    const T &operator[](const CONTAINER &c) { return c[i]; } 

    int i; 
}; 

int main() { 
    std::vector<int> v1 = {0}; 
    std::vector<const char *> v2 = {"asd"}; 
    typed_index<int> i = 3; 
    int z = i[v1]; 
    const char *s = i[v2]; // will fail 
} 

Answer 2

Utilizzare std :: vector :: size_type (not size_t). std :: vector :: size_type può essere size_t nella maggior parte delle implementazioni, ma per la portabilità e il futuro a prova di effetto, lo faremo bene.

Vai avanti e digitare typedef: utilizzando WidgetIndex = std :: vector :: size_type;

in modo che questo sembra ragionevole:

vuoto doSomethingWithLookupResult (WidgetIndex lookupResult);

Questo evita il problema del ridimensionamento del vettore che, mentre lo si interrompe, nella tua domanda, tornerà a morderti.

Non giocare con un tipo definito dall'utente, come ad esempio tohava (molto intelligente), a meno che non si preveda di usare questo idioma molto nel codice base.Ecco perché non:

• Il problema che si sta affrontando (tipo-sicurezza) è reale e ci piacerebbe una soluzione ad esso se è "libero", ma rispetto ad altre opportunità programmatori C++ hanno a sparare loro stessi in piedi, questo non è un grosso problema.
• Perderai tempo. Il tuo tempo per progettare la classe e quindi il tempo di ogni utente della tua base di codice (incluso te stesso dopo aver dimenticato l'implementazione in pochi mesi) che fisserà quel codice e dovrà risolvere il problema.
• A un certo punto, in futuro, inciamperete su quel caso d'angolo "interessante" che nessuno di noi può vedere ora fissando questo codice.

Detto questo, se hai intenzione di usare questo idioma spesso nella tua base di codice (hai molte classi che sono memorizzate in vettori o array molto statici), allora potrebbe essere sensato fare questo investimento. In tal caso l'onere di manutenzione si estende su più codice e la possibilità di utilizzare il tipo di indice sbagliato con il contenitore sbagliato è maggiore.