View Full Version : [C++] stack dinamico con i template
Buonasera a tutti.
Avendo bisogno di creare un array multidimensionale dinamico e volendo sperimentare con i template, ho deciso di cogliere questi due piccioni :D e ho steso qualcosa. Da quanto ho capito, posso poi dichiarare uno stack di stack in modo molto semplice, in altre parole l'array multidimensionale di cui sopra.
template <class T> class gVector {
public:
// proprietà
uint32_t size;
T *stack;
// metodi
void init() {
size = 0;
stack = NULL;
}
void add(T &item) {
stack = (T*) realloc(stack, (size+1)*sizeof(T));
size += 1;
stack[size-1] = item;
}
void clear() {
if (stack != NULL) {
free(stack);
stack = NULL;
size = 0;
}
}
T at(uint32_t p) {
return stack[p];
}
};
Considerando che manca completamente la gestione degli errori e i metodi di cancellazione elementi, mi piacerebbe avere un parere da voi. Sono aperto ad ogni suggerimento/critica.
Non siate troppo cattivi :oink:
tomminno
18-02-2011, 23:50
La prima critica da sollevare è che uno stack non è un array. Vuoi uno stack o un array?
Quella che hai fatto te sarebbe una "brutta copia", scusami il termine, della classe std::vector, oltre tutto la tua ha un sacco di problemi.
Il primo che mi viene in mente è: prova ad usare il tuo codice con una classe con un campo int e uno std::string, avrai delle spiacevolissime sorprese.
Realloc così come tutte le funzioni di allocazione del C non chiamano il costruttore della classe, ma lavorano a basso livello riservando un'area di memoria.
Quando il codice proverà a copiare la stringa di item sul tuo oggetto allocato con realloc si troverà a copiare i valori su un puntatore non inizializzato, perchè non è stato chiamato il costruttore della classe string.
Quando in C++ si arriva ad usare le funzioni di allocazione del C, secondo il mio parere, si sta sbagliando qualcosa.
Ma hai proprio la necessità di reimplementare funzionalità già presenti nella libreria standard? Vuoi un array dinamico? Usa std::vector. Vuoi uno stack dinamico? usa std::stack.
Ciao tomminno, grazie degli spunti!
Allora, parto dal fondo: il mio è assolutamente un esercizio per capire l'uso dei template, non avrei il coraggio di introdurre codice del genere in un programma "serio" :)
Per lo stack vs. array... hai ragione, visto che fornisco il metodo at() direi che si tratta di array.
Per quanto riguarda realloc, comprendo la bassezza del mix C e C++ ma mi chiedo: dato che il mio template non ha costruttore e si affida a quello di default (che non fa nulla), dovrei comunque chiamare init() in ogni caso per inizializzare le proprietà; il problema sorge quando creo gVector di classi, il cui costruttore non verrebbe chiamato. Dico bene?
tomminno
19-02-2011, 10:03
Per quanto riguarda realloc, comprendo la bassezza del mix C e C++ ma mi chiedo: dato che il mio template non ha costruttore e si affida a quello di default (che non fa nulla), dovrei comunque chiamare init() in ogni caso per inizializzare le proprietà;
Il tuo init in realtà dovrebbe essere il costruttore di gVector.
il problema sorge quando creo gVector di classi, il cui costruttore non verrebbe chiamato. Dico bene?
Si il problema nasce proprio in caso di utilizzo del tuo vettore con le classi le quali, senza la chiamata al costruttore, potrebbero risentirsene, specialmente se eseguono allocazioni dinamiche sul costruttore come per l'appunto std::string. E ovviamente no costruttore => no distruttore, che potrebbe essere anche peggio, in quanto potrebbero non essere liberate risorse magari non allocate sul costruttore.
Si il problema nasce proprio in caso di utilizzo del tuo vettore con le classi le quali, senza la chiamata al costruttore, potrebbero risentirsene, specialmente se eseguono allocazioni dinamiche sul costruttore come per l'appunto std::string. E ovviamente no costruttore => no distruttore, che potrebbe essere anche peggio, in quanto potrebbero non essere liberate risorse magari non allocate sul costruttore.
Ora è tutto molto più chiaro!
Mediterò su queste informazioni, nel frattempo ti ringrazio molto. :)
Per ulteriori sviluppi riutilizzerò questo post.
Ritorno con gli sviluppi. Ho corretto il mio template come segue:
template <class T> class gVector {
public:
// proprietà
uint32_t size;
T *stack;
// metodi
gVector() : size(0), stack(NULL) {}
~gVector() { clear(); }
void add(T &item) {
T *tmp = new T[size+1];
for (uint32_t i=0; i<size; i++)
tmp[i] = stack[i];
tmp[size] = item;
delete [] stack;
stack = tmp;
size += 1;
}
void clear() {
if (size > 0) {
delete [] stack;
stack = NULL;
size = 0;
}
}
T at(uint32_t p) {
return stack[p];
}
};
Ho notato che questo sistema si comporta male quando si creano array di array, ad esempio:
gVector< gVector<int> > mtx;
Quando, dopo aver riempito a dovere, provo ad accedere ad un elemento del sotto-array con
mtx.at(x).at(y);
ottengo valori incoerenti con la realtà.
Sbaglio a pensare sia dovuto al copy constructor di default che copia "male" i valori di stack?
(ribadisco che il mio non è un voler reinventare la ruota, sto cercando di imparare i template e i dinamismi dei costruttori :) )
Grazie in anticipo!
Supdario
20-02-2011, 22:04
1) Il tuo metodo per il ridimensionamento è giusto (anche se potresti copiare l'array in modo più efficiente usando la funzione "memcpy"), però si può capire facilmente che estendendo l'array solo di 1, il tutto diventa molto lento.
In questo caso i usano i cosiddetti chunks, cioè l'array non viene ridimensionato di 1, ma viene ridimensionato in abbondanza (tipo raddoppiando i blocchi o estendendoli di un numero fisso tipo 64), ed ogni volta che il vettore si riempie, viene allocata altra memoria in abbondanza.
2) Se ci hai fatto caso, nella prima chiamata alla funzione add il vettore "stack" non è ancora stato inizializzato (ovviamente), ma il delete [] viene richiamato ugualmente. Questo potrebbe dare risultati inaspettati, quindi ti consiglio di impostare il puntatore "stack" a NULL nel costruttore della classe.
Ciao Supdario e grazie per le risposte.
1) Il tuo metodo per il ridimensionamento è giusto (anche se potresti copiare l'array in modo più efficiente usando la funzione "memcpy"), però si può capire facilmente che estendendo l'array solo di 1, il tutto diventa molto lento.
In questo caso i usano i cosiddetti chunks, cioè l'array non viene ridimensionato di 1, ma viene ridimensionato in abbondanza (tipo raddoppiando i blocchi o estendendoli di un numero fisso tipo 64), ed ogni volta che il vettore si riempie, viene allocata altra memoria in abbondanza.
Questa tecnica è molto interessante e l'avevo letta in merito ai meccanismi del "famoso" std::vector. Memcpy però non rischia di andare in conflitto con ciò che è stato allocato da new?
2) Se ci hai fatto caso, nella prima chiamata alla funzione add il vettore "stack" non è ancora stato inizializzato (ovviamente), ma il delete [] viene richiamato ugualmente. Questo potrebbe dare risultati inaspettati, quindi ti consiglio di impostare il puntatore "stack" a NULL nel costruttore della classe.
Mea culpa, ho cannato nel copia-incolla. Nel costruttore già imposto stack(NULL), ma nello snippet sopra compare s(NULL). Ho corretto :)
Supdario
20-02-2011, 22:43
Ciao Supdario e grazie per le risposte.
Questa tecnica è molto interessante e l'avevo letta in merito ai meccanismi del "famoso" std::vector. Memcpy però non rischia di andare in conflitto con ciò che è stato allocato da new?
Il problema che si poneva prima era quello di allocare la memoria, ed eseguendo realloc, non viene chiamato il costruttore della classe di cui vuoi allocare il vettore.
In questo caso, invece, si tratta semplicemente di eseguire la copia binaria di un vettore, cioè copiarlo esattamente com'è da una locazione di memoria ad un'altra. Per sicurezza, assicurati di usare std::memcpy (e non il memcpy del C), anche se ad occhio non dovrebbe cambiare niente.
...
Davvero, c'è sempre da imparare, ero completamente all'oscuro del memcpy in std! Ah l'autodidattarianesimo... :)
Che ne pensi/pensate invece del problema della matrice, o gVector< gVector<...> >?
malocchio
22-02-2011, 15:04
Quel tuo gVector utilizza memoria dinamica... è consigliabile definire un costruttore di copia e un operatore di assegnamento ;) e, se fanno le cose come si deve, l'ultimo problema dovrebbe sparire.
Cerca di capire tu perché.
Quel tuo gVector utilizza memoria dinamica... è consigliabile definire un costruttore di copia e un operatore di assegnamento ;) e, se fanno le cose come si deve, l'ultimo problema dovrebbe sparire.
Cerca di capire tu perché.
Grazie anche a te per la collaborazione! ;)
Quello che io pensavo di implementare (pseudocodice):
gVector (const gVector &other) {
std::memcpy(...da other.stack a this.stack)
}
Anche se ho un dubbio concettuale: così facendo mi pare si crei e poi si distrugga (alloca e poi dealloca) un bel po' di roba, in casi tipo:
mtx.at(x).at(y);
E' una situazione tipica e corretta per il c++?
malocchio
22-02-2011, 21:50
Grazie anche a te per la collaborazione! ;)
Quello che io pensavo di implementare (pseudocodice):
gVector (const gVector &other) {
std::memcpy(...da other.stack a this.stack)
}
Anche se ho un dubbio concettuale: così facendo mi pare si crei e poi si distrugga (alloca e poi dealloca) un bel po' di roba, in casi tipo:
mtx.at(x).at(y);
E' una situazione tipica e corretta per il c++?
Esattamente: le allocazioni e deallocazioni sono molto numerose.
Corretto è corretto...
che poi faccia schifo per le performance (anche se con quantità di dati piccole la differenza potrebbe essere impercettibile) è tutto un altro paio di maniche :)
Sempre meglio di un segfault...
Vabbè, voglio sbilanciarmi: diciamo che potresti prendere in considerazione l'idea di modificare il metodo at() in modo che restituisca un reference...
Sempre meglio di un segfault...
Non ci sono dubbi...
Vabbè, voglio sbilanciarmi: diciamo che potresti prendere in considerazione l'idea di modificare il metodo at() in modo che restituisca un reference...
Questa chicca permette di evitare la copia, un po' in stile "passing by reference"? In ogni caso adesso me la studio. Ti ringrazio ancora!
malocchio
22-02-2011, 22:44
Questa chicca permette di evitare la copia, un po' in stile "passing by reference"? In ogni caso adesso me la studio. Ti ringrazio ancora!
Ehm sì... i reference si usano spesso per risparmiare sulle allocazioni "inutili". Attento che però è un'importante scelta di design della classe: prima di metterla giù in codice ci penserei due volte.
In ogni caso se la usi così:
gVector< gVector<int> > gv;
...
...
gv.at(0).at(1);dovrebbe funzionare e anche molto velocemente.
Occhio che però con i reference diventa possibile fare anche cose come
gVector< gVector<int> > gv;
...
...
gv.at(0).at(1) = 1234567;
gv.at(0).at(1)++;
gv.at(1) = gv.at(2);e altre porcate molto molto arrapanti.
tomminno
23-02-2011, 08:12
Occhio che però con i reference diventa possibile fare anche cose come
gVector< gVector<int> > gv;
...
...
gv.at(0).at(1) = 1234567;
gv.at(0).at(1)++;
gv.at(1) = gv.at(2);e altre porcate molto molto arrapanti.
Per questo esistono i const reference :D
Se per scelta i dati devono essere modificabili dall'esterno quelle non sono porcate ma funzionalità previste, altrimenti meglio usare i const reference e passa la paura. :)
malocchio
23-02-2011, 12:18
Per questo esistono i const reference :D
Se per scelta i dati devono essere modificabili dall'esterno quelle non sono porcate ma funzionalità previste, altrimenti meglio usare i const reference e passa la paura. :)
Hai perfettamente ragione e mi sorprendo di non aver sollevato io l'argomento visto che sono un "amante" del const.
Però c'è da dire che il const funziona bene se messo in tutti i posti dove va messo, altrimenti perde un po' la sua comodità...
Volendo esser pignoli quindi andrebbe messo come attributo
template <class T> class gVector {
public:
// proprietà
uint32_t size;
T *stack;
// metodi
gVector() : size(0), stack(NULL) {}
~gVector() { clear(); }
void add(T const& item) {
T *tmp = new T[size+1];
for (uint32_t i=0; i<size; i++)
tmp[i] = stack[i];
tmp[size] = item;
delete [] stack;
stack = tmp;
size += 1;
}
void clear() {
if (size > 0) {
delete [] stack;
stack = NULL;
size = 0;
}
}
T const& at(const uint32_t p) const {
return stack[p];
}
};ho usato la sintassi più moderna, che piace di più al mio occhio...
Per dubbi consiglio http://www.parashift.com/c++-faq-lite/const-correctness.html#faq-18.6, punti 18.6 e 18.8
non sono sicuro della correttezza dell'intestazione dell'ultimo metodo... bisognerebbe provare a compilarlo...
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.