Sto cercando una classe contenitore C++ indicizzata come std::vector, ma con inserimenti, eliminazioni e indicizzazione rapidi. Ad esempio, un'interfaccia vector implementata con un albero di bilanciamento sottostante avrebbe le inserzioni/eliminazioni O (logN) e l'indicizzazione O (logN).Contenitore con inserti e indici rapidi?
Per essere chiari: non sto cercando std::map<int, T>. L'inserimento di un elemento nell'indice N dovrebbe incrementare gli indici di tutti gli elementi successivi nell'array, cosa che non sarebbe il caso di std::map<int, T>.
Ho trovato AVL Array che fa esattamente quello che sto cercando. Ha l'interfaccia giusta, ma mi piacerebbe vedere se ci sono altre opzioni.
Conosci altre implementazioni (di qualità di produzione)? Forse qualcosa di più popolare (la spinta ha qualcosa del genere?). Qualcosa con un minor ingombro di memoria? (Un nodo che contiene un puntatore nell'array AVL è 64 byte sulla mia macchina.)
si può approfondire il motivo per cui si richiede l'accesso casuale? – BeyelerStudios
Questo sembra essere off-topic - alla ricerca di raccomandazioni software/libreria. –
Non penso che ci sia una cosa più semplice (in termini di struttura dei dati) che fa quello che vuoi, quindi richiede 2 ptr per next/prev e 3 ptrs per parent/left/right più il puntatore originale. In totale, 6 puntatori = 48 byte per ambienti a 64 bit. Questo è il minimo che puoi ottenere in termini di impronta di memoria (credo). – mostruash