[C++] Strutture dati

[bianchis78]

Salve,

sono un principiante della programmazione, in un mio progetto ho la necessità di utilizzare un vettore di puntatori verso vettori.

E' possibile utilizzare i vector delle STL? :help:

[tomminno]

Salve,

sono un principiante della programmazione, in un mio progetto ho la necessità di utilizzare un vettore di puntatori verso vettori.

E' possibile utilizzare i vector delle STL? :help:

Dovresti dettagliare meglio, comunque puoi usare:


vector< vector<Tipo1>* > vettore_di_puntatori_a_vettori_di_tipo1

[bianchis78]

Ho degli oggetti cosi composti:
Obj[ int ID, doble Time, float A, float B]

A priori non conosco il numero e la composizione degli oggetti;
posso avere oggetti con lo stesso ID ma le altre componenti diverse.

Posto che ipotizzo che ID inizi da 0 per poi crescere,
volevo sfruttare l'indice del vector per individuare con
un singolo accesso l'ID dell'oggetto a cui era associato
un puntatore che mi puntava ad un vector
contenente una serie di elementi del tipo [double Time, float A, float B].

Per evitare incomprensioni ho allegato una semplice immagine

[tomminno]

Ho degli oggetti cosi composti:
Obj[ int ID, doble Time, float A, float B]

A priori non conosco il numero e la composizione degli oggetti;
posso avere oggetti con lo stesso ID ma le altre componenti diverse.

Posto che ipotizzo che ID inizi da 0 per poi crescere,
volevo sfruttare l'indice del vector per individuare con
un singolo accesso l'ID dell'oggetto a cui era associato
un puntatore che mi puntava ad un vector
contenente una serie di elementi del tipo [double Time, float A, float B].

Per evitare incomprensioni ho allegato una semplice immagine

Da quello che ho capito ti serve indicizzare i dati rispetto al campo ID numerico con collisioni, quindi il vettore di vettori non serve, devi usare una map o una hash_map che ad un ID fa corrispondere un vettore di dati di tipo Obj, sul quale scorri in caso di collisione del valore ID.

[bianchis78]

preferivo utilizzare i vector perchè:

1) a differenza delle map ho già utilizzato i vector, anche se credo che
anche le map siano semplici da utilizzare.
2) in seguito volevo fare la seguente modifica:fare una specie di caching inserendo nel vettore dei puntatore anche l'ultimo elemento [time,A,B] cercato, per poi confrontare le prestazioni con il caso precedente.
(Vedi altra immagine che vale più di 1000 parole).

[tomminno]

1) a differenza delle map ho già utilizzato i vector, anche se credo che
anche le map siano semplici da utilizzare.


Usando i vector e volendo far corrispondere una posizione del vector con l'ID nascono dei problemi nel caso in cui gli ID non siano consecutivi.
Supponi di avere come ID: 0,1,2,3,5 a questo punto vector.at(5) (dato che vuoi accedere con una sola operazione) ti solleva l'eccezione out_of_range.
E se sei nella condizione ID: 0,1,2,3,5,6 vector.at(5) ti restituisce un riferimento sbagliato.


2) in seguito volevo fare la seguente modifica:fare una specie di caching inserendo nel vettore dei puntatore anche l'ultimo elemento [time,A,B] cercato, per poi confrontare le prestazioni con il caso precedente.
(Vedi altra immagine che vale più di 1000 parole).

Perchè mai dovresti inserirlo in un oggetto che usi per fare tutt'altro?
In quale posizione vorresti inserirlo?
Il chaching è più corretto farlo usando un'altra variabile di tipo Obj o int a seconda di quello che ti interessa.

[bianchis78]

L'idea per ovviare al problema degli ID non consecutivi era quella di tenere una tabella di conversione ID_Reale/ID_Fittizio dove l'ID fittizio lo assegnavo partendo da 0 ed incrementandolo di volta in volta.
... però mi sa che a questo punto sarebbe meglio utlizzare direttamente una map.

come ho detto non ho mai utilizzato una map, dovrebbe essere una cosa del genere?

_________________________________________________________

map <int, vector<ObjValue>> MapObj; //dichiarazione della map

- Quando inserisco un elemento nuovo [ID_X, ObjValue_X] dovrei:

vector <ObjValue> vec; //dichiararo un vector.

vec.push_back(ObjValue_X); //inserire l'ObjValue nel vettore.

vector<ObjValue>* p; //dichiararo un puntatore al vettore.

p= &vec; //faccio puntare p al vettore dichiarato prima.

MapObj[ID_X]=p; //associo tale puntatore alla chiave ID_X.

- Se invece è gia presente l' ID_X

vector<ObjValue>* tmp=MapObj.find(ID_X);

*tmp.push_back(ObjValue_X);

- Mentre per estrarre un oggetto ObjValue_Y:

vector<ObjValue> temp;

vector<ObjValue>* tmp=MapObj.find(ID_Y);

temp = *tmp.pop_back(ObjValue_Y);

______________________________________________________

Ho scritto un mare di stronzate, vero? :cry:

[tomminno]

L'idea per ovviare al problema degli ID non consecutivi era quella di tenere una tabella di conversione ID_Reale/ID_Fittizio dove l'ID fittizio lo assegnavo partendo da 0 ed incrementandolo di volta in volta.
... però mi sa che a questo punto sarebbe meglio utlizzare direttamente una map.


Infatti...


come ho detto non ho mai utilizzato una map, dovrebbe essere una cosa del genere?

_________________________________________________________

map <int, vector<ObjValue>> MapObj; //dichiarazione della map

- Quando inserisco un elemento nuovo [ID_X, ObjValue_X] dovrei:

vector <ObjValue> vec; //dichiararo un vector.

vec.push_back(ObjValue_X); //inserire l'ObjValue nel vettore.

vector<ObjValue>* p; //dichiararo un puntatore al vettore.

p= &vec; //faccio puntare p al vettore dichiarato prima.

MapObj[ID_X]=p; //associo tale puntatore alla chiave ID_X.


Qui c'è un errore (ripetuto anche in seguito) in quanto hai dichiarato MapObj che mappa int in vector<ObjValue> mentre te stai assegnando vector<ObjValue>*.
Inoltre il metodo find restituisce un iteratore non l'oggetto mappato.


- Se invece è gia presente l' ID_X

vector<ObjValue>* tmp=MapObj.find(ID_X);

*tmp.push_back(ObjValue_X);

- Mentre per estrarre un oggetto ObjValue_Y:

vector<ObjValue> temp;

vector<ObjValue>* tmp=MapObj.find(ID_Y);

temp = *tmp.pop_back(ObjValue_Y);

______________________________________________________

Ho scritto un mare di stronzate, vero? :cry:

Qualcuna ;)

io farei qualcosa del tipo:


typedef map<int, vector<ObjValue>*> Map;
//Ricodarsi di fare delete sugli elementi vector<ObjValue>*
Map MapObj;

//Per l'inserimento
void Insert(ObjValue & obj)
{
Map::iterator it;
if ((it = MapObj.find(obj.ID_X())) == MapObj.end())
{
vector<ObjValue> * vec = new vector<ObjValue>;
vec->push_back(obj);
MapObj[obj.ID_X()] = vec;
}
else
it->second->push_back(obj);
}

ObjValue * Get(int id_x, int id_y)
{
Map::iterator it;
if ((it = MapObj.find(id_x)) != MapObj.end())
{
//Anche qui vedere se non merita usare map
return &it->second->at(id_y);
}
else
return NULL;
}