Note
Struttura
Vettori dinamici
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.
Vector: implementazione
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.
Vector: Intestazione
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).
Vector: costruttore 1
inline vector()
{
data = 0; // Inizializzazione variabili
  size = 0;
  memo = 0;
}
Il costruttore di default definisce un vettore con zero elementi e zero posizioni allocate.
Vector: costruttore 2
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.
Vector: distruttore
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.
Vector: accesso agli elementi
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.
Vector: espansione
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.
Vector: ridimensionamento
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.
Vector: aggiunta di 1 elemento
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.
Vector: aggiunta efficiente
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?).
Vector: controlli
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.
Vector: assegnamento errato
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.
Vector: assegnamento errato(2)
Vector: assegnamento corretto
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: esempio di utilizzo
…
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
Vector: introduzione agli iteratori
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?
Vector: iteratori
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: utilizzo degli iteratori
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.
Vector: un’altra implementazione
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.
Esercizi
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.
Contatti
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.