|
|
|
Definiremo la classe vector. |
|
La classe rappresenta un vettore dimensionabile
dinamicamente. |
|
Ha un parametro template che definisce il tipo
di dato contenuto nel vettore. |
|
L’implementazione proposta e’ volutamente rozza. |
|
Vedremo come la stessa classe sia implementanta
nella Standard Template Library. |
|
|
|
|
La classe vector e’ definita da tre valori: |
|
Size: la dimensione corrente del vettore, ovvero
il numero dei suoi elementi. |
|
Memo: il numero di elementi allocati realmente,
che deve essere maggiore o uguale a size. |
|
Data: la memoria allocata vera e propria. |
|
|
|
La classe e’ parametrizzata secondo il tipo T,
che rappresenta il tipo degli elementi contenuti nel vettore. |
|
|
|
|
template<class T> // Parametro template |
|
class vector |
|
{ |
|
private: // Dati privati |
|
T * data; // Memoria allocata |
|
int size; // Dimensione corrente |
|
int memo; // Dim. memoria allocata |
|
}; |
|
|
|
Data contiene il vettore vero e proprio, size
memorizza la dimensione reale del vettore, memo la memoria allocata (>=
size). |
|
|
|
|
inline vector() |
|
{ |
|
data = 0; // Inizializzazione variabili |
|
size = 0; |
|
memo = 0; |
|
} |
|
|
|
Il costruttore di default definisce un vettore
con zero elementi e zero posizioni allocate. |
|
|
|
|
Inline vector( int s ) |
|
{ |
|
assert(s>0); |
|
data = new T[s]; // Allocazione memoria |
|
assert(data!=0); |
|
size = s; // Definizione di size |
|
memo = s; // Definizione di memo |
|
} |
|
|
|
Costruttore con allocazione iniziale della
dimensione; lo spazio allocato coincide con la dimensione attuale. |
|
|
|
|
inline void clear() |
|
{ |
|
if(data) delete[] data; // Disallocazione |
|
data = 0; |
|
size = memo = 0; |
|
} |
|
inline ~vector() |
|
{ |
|
clear(); |
|
} |
|
E’ importante dichiarare il distruttore della
classe; il distruttore si occupa di disallocare la memoria dei dati. |
|
|
|
|
inline T & operator[] ( const int i ) |
|
{ |
|
assert(i>=0 && i<size); |
|
return data[i]; |
|
} |
|
inline const T & operator[] ( int i ) const |
|
{ |
|
assert(i>=0 && i<size); |
|
return data[i]; |
|
} |
|
Operatore[]: accesso agli elementi del vettore,
come al solito di definisce anche la versione costante. |
|
|
|
|
inline void reserve( int m ) |
|
{ |
|
if(m>memo) |
|
{ |
|
T * tmp = new T[m]; // Alloc. nuovo vettore |
|
for(int i=0;i<size;++i) // Copia dati |
|
tmp[i] = data[i]; |
|
if(data) delete[] data;// Disalloc. memoria |
|
data = tmp; |
|
memo = s; |
|
} } |
|
Questo metodo ridimensiona la memoria allocata
senza modificare il vettore. |
|
|
|
|
inline void resize( int s ) |
|
{ |
|
reserve(s); |
|
size = s; // Assegnamento dimensione |
|
} |
|
|
|
Questo metodo espande (o riduce) il numero di
elementi del vettore, la chiamata a reserve assicura che la memoria
allocata sia sufficiente. |
|
|
|
|
inline void push_back( const T & e ) |
|
{ |
|
reserve(size+1); |
|
data[size++] = e; |
|
} |
|
|
|
Il metodo aggiunge un elemento in coda al
vettore; tuttavia, in caso di aggiunta di molti elementi, l’implementazione
risulta eccessivamente inefficiente: si esegua una riallocazione (con
copiatura dei dati) per ogni elemento aggiunto. |
|
|
|
|
inline void push_back( const T & e ) |
|
{ |
|
if(size==memo) // Necessaria riallocazione |
|
{ |
|
if(memo==0) reserve(256); |
|
else reserve(memo*2); |
|
} |
|
data[size++] = e; |
|
} |
|
Con questa implementazione, per ogni n
inserzioni nel vettore, si eseguono al piu’ log(n) espansioni (perche?). |
|
|
|
|
inline bool is_empty() const |
|
{ |
|
return size==0; |
|
} |
|
inline int size() const |
|
{ |
|
return size; |
|
} |
|
|
|
Il metodo is_empty constrolla se il vettore e’
vuoto. Il metodo size ritorna il numero di elementi del vettore. |
|
|
|
|
La funzione di assegnamento di default, copia i
dati propri della classe nel seguente modo: |
|
Inline vector & operator= ( const vector
& v ) |
|
{ |
|
data = v.data; |
|
size = v.size; |
|
memo = v.memo; |
|
return *this; |
|
} |
|
|
|
Il funzionamento risulta errato. |
|
|
|
|
|
inline vector & operator= ( const vector
& v ) |
|
{ |
|
if(v.size>memo) // Memoria insuff. |
|
{ |
|
if(data) delete[] data; // Riallocazione |
|
memo = v.size; |
|
data = new T[memo]; |
|
} |
|
for(int i=0;i<v.size;++i) // Copia elementi |
|
data[i] = v.data[i]; |
|
size = v.size; // Aggiorn. dimensione |
|
} |
|
|
|
|
… |
|
vector<char> v(10); // vettore di 10 char |
|
V[3] = ‘x’; // Assegnamento elemento |
|
v.push_back(‘y’); // Aggiunta in coda |
|
cout << v.size(); // stampa: 11 |
|
vector<char> w; // Dichiarazione |
|
w = v; // assegnamento vettori |
|
|
|
Vector<char> k[10]; // ATTENZIONE: si e’ |
|
//
dichiarato 10 vettori |
|
|
|
|
char v[100]; |
|
|
|
for(int i=0;i<100;++i) // (1)Iterazione con
indice |
|
operazione(v[i]); |
|
|
|
for(char* j=v;j<v+100;++j) // (2)Iteraz. con
puntatore |
|
operazione(*j); |
|
|
|
L’iterazione degli elementi di un vettore si
effettua di solito tramite indici (caso 1) o tramite puntatori (caso 2). Di
solito il secondo metodo e’ piu’ efficiente, non richiede infatti il
calcolo dell’indirizzo dell’elemento. Come si procede nel caso della classe
vector? |
|
|
|
|
typedef T * iterator; |
|
inline iterator begin() |
|
{ |
|
return data; |
|
} |
|
inline iterator end() |
|
{ |
|
return data+size; |
|
} |
|
|
|
Definiamo il tipo di dato iterator, che e’ un
estensione del puntatore. Definiamo inoltre i metodi begin e end che
ritornano gli iteratori all’inizio e alla fine del vettore. |
|
|
|
|
vector<char> v(100); |
|
|
|
vector<char>::iterator i; |
|
|
|
for(i=v.begin();v!=v.end();++i) |
|
operazione(*i); |
|
|
|
L’iteratore si utilizza in modo del tutto
analogo al puntatore. |
|
|
|
|
Abbiamo visto un’implementazione veramente rozza
della classe vector. |
|
In realta’ la classe vector e’ gia’ implementata
in maniera piu’ efficiente nella libreria standard del C++. |
|
Tale implementazione ha le stesse funzionalita’
da noi implementate piu’ altre aggiuntive. |
|
La classe vector della libreria standard ha un
secondo parametro template, che specifica la politica di riallocazione
della memoria. |
|
|
|
|
Per quanto riguarda la classe vector: |
|
Definire i metodi front() e back() che ritornano
il riferimento al primo e all’ultimo elemento del vettore. |
|
Definire il metodo pop_back() che elimina
l’ultimo elemento del vettore. |
|
Definire il metodo erase( iterator p ) che
elimina dal vettore l’elemento indicato da p e ricompatta gli altri valori
(*). |
|
|
|
(*) esercizio piu’ impegnativo. |
|
|
|
|
Claudio Rocchini |
|
|
|
email: rocchini@iei.pi.cnr.it |
|
web
: http://vcg.iei.pi.cnr.it/~rocchini |
|
tel. : 050-3152926 |
|
|
|
Ufficio: Istituto Elaborazione Informazione,
CNR, Area della ricerca di Pisa, S. Cataldo Pisa. |
|
|
|