consulenza sulla struttura dati su C++

Question

Sto cercando la struttura dati in C++ e ho bisogno di un consiglio.

devo nodi, ogni nodo ha unique_id e group_id:

1 1.1.1.1 
2 1.1.1.2 
3 1.1.1.3 

4 1.1.2.1 
5 1.1.2.2 
6 1.1.2.3 

7 2.1.1.1 
8 2.1.1.2 

ho bisogno di una struttura di dati per rispondere a queste domande:

1. Qual è il group_id del nodo 4
2. dammi lista (probabilmente vettoriale) di unique_id appartenente al gruppo 1.1.1
3. dammi elenco (probabilmente vettoriale) di unique_id's che appartengono al gruppo 1.1
4. mi danno lista (probabilmente vettore) di Unique_ID di appartenenti al gruppo 1

Esiste una struttura di dati che può rispondere a queste domande (che cosa è il tempo della complessità di inserimento e di risposta)? o dovrei implementarlo?

Gradirei un esempio.

EDIT:

all'inizio, ho bisogno di costruire questa struttura dati. la maggior parte dell'azione sta leggendo dal gruppo id. l'inserimento avverrà ma meno che leggere.

la complessità temporale è più importante di spazio di memoria

Answer 1

non sono sicuro dei Ds perfetti per questo. Ma mi piacerebbe fare uso di una mappa. Ti darà O (1) efficienza per la domanda 1 e per inserimento O (logn) e cancellazione. Il problema riguarda la domanda 2,3,4 in cui l'efficienza sarà O (n) dove n è il numero di nodi.

Answer 2

Sembra che sia necessario un contenitore con due indici separati su unique_id e group_id. La domanda 1 sarà gestita dal primo indice, le domande 2-4 saranno gestite dal secondo.

Forse un'occhiata a Boost Multi-index Containers Library

Answer 3

Prima di tutto, se avete intenzione di avere solo un piccolo numero di nodi, allora sarebbe probabilmente un senso di non pasticciare con avanzate strutturazione dei dati. La ricerca lineare semplice potrebbe essere sufficiente.

Successivamente, sembra un buon lavoro per SQL. Quindi potrebbe essere una buona idea incorporare nella tua libreria SQLite dell'app. Ma anche se vuoi davvero farlo senza SQL è ancora un buon suggerimento: quello di cui hai bisogno sono due alberi indice per supportare la ricerca rapida attraverso l'array. La complessità (se si utilizzano alberi bilanciati) sarà logaritmica per tutte le operazioni.

Answer 4

Depends ...

Quanto spesso inserisci? O per lo più leggi? Con quale frequenza accedi a Id o GroupId?

Con un massimo di 500 nodi li inserirò in un semplice Vector dove l'ID è l'offset nell'array (se gli ID sono effettivamente come mostrato). La ricerca di gruppo può essere implementata iterando sull'array e confrontando gli id-gtroup parziali.

Se questo è troppo costoso e si accede veramente molto a strcuture e si richiedono prestazioni molto elevate, oppure si fanno molti inserti, implementerei uno tree con uno HashMap per gli Id.

Se i dati sono memorizzati in un database, è possibile utilizzare uno SELECT/ CONNECT BY se i sistemi lo supportano e interrogare le informazioni direttamente dal DB.

spiacenti per non aver fornito una risposta chiara, ma la soluzione dipende da troppi fattori ;-)

Answer 5

a me, dati gerarchici come il gruppo ID richiede una struttura ad albero. (Suppongo che per 500 elementi questo non sia realmente necessario, ma sembra naturale e si adatta bene.)

Ogni elemento nei primi due livelli dell'albero contiene solo vettori (se vengono ordinati) o mappe (se vengono non ordinati) di sotto-ID.

Il terzo livello nella gerarchia ad albero dovrebbe contenere puntatori alle foglie, sempre in un vettore o in una mappa, che contengono la quarta parte ID del gruppo e l'ID univoco.

Le domande 2-4 rispondono facilmente e rapidamente navigando l'albero.

Per la domanda 1 è necessaria una mappa aggiuntiva dagli ID univoci alle foglie nell'albero; ogni elemento inserito nell'albero ha anche un puntatore ad esso inserito nella mappa.