Allocazione dinamica della memoria

     

In un programma non sempre è possibile stabilire prima dell'esecuzione la dimensione delle variabili aggregate (vettori, strutture ecc.) destinate a contenere i dati.
Per questi casi il C++ prevede la possibilità di gestire la memoria dinamicamente, vale a dire durante il runtime.
La memoria allocata in questo modo non fa parte dello stack, in cui sono memorizzate le variabili locali, ma di un altro segmento, denominato heap o free store.
L'accesso alle locazioni di memoria di quest'area avviene indirettamente, dereferenziando dei puntatori.
L'allocazione dinamica consente di utilizzare solo la memoria strettamente necessaria e di creare particolari strutture (liste, alberi ecc.) la cui dimensione varia dinamicamente in funzione della quantità dei dati da memorizzare.

Operatore new

     

Definizione:

Per allocare nuova memoria nello heap s'impiega l'operatore new, la cui sintassi è:

new tipo
new tipo[dimensione] (per i vettori)

new alloca un'area di memoria adatta a contenere un oggetto del tipo specificato. Se l'operazione va a buon fine, il valore dell'espressione è l'indirizzo di memoria dell'area allocata.

esempio:

int *p;
p=new int;
char *s=new char[40];

Operatore delete

     

Quando la memoria allocata dinamicamente non è più necessaria, è bene restituirla al sistema operativo cancellandola dallo heap. L'operatore delete dealloca l'area di memoria puntata dal suo operando.

sintassi:

delete puntatore;
delete[] puntatore;// per i vettori

esempio:

se p ed s sono i puntatori dell'esempio relativo all'operatore new:

delete p;
delete[] s;

Memory leak

     

Quando un puntatore a un'area di memoria dinamica esce dal proprio ambito di visibilità, viene automaticamente deallocato. Lo stesso non accade all'area di memoria cui punta che sebbene, continui a impegnare risorse, rimane inaccessibile.
Questa circostanza, se perpetuata, può portare all'esaurimento della memoria disponibile (memory leak), all'interruzione improvvisa del programma o addirittura al crash del sistema operativo.
Per evitare questi problemi è bene prestare attenzione a deallocare con delete la memoria non necessaria prima che il corrispondente puntatore termini il proprio periodo di vita.
In alternativa è possibile impiegare i puntatori automatici, auto_ptr, che prima di essere eliminati deallocano automaticamente il blocco di memoria cui puntano.

Vettori dinamici

     

Grazie al meccanismo di allocazione dinamica della memoria è possibile creare dei vettori dinamici, ossia che variano la propria dimensione in funzione della quantità di dati da memorizzare.

esempio:

int vett[], n;
cout << "Quanti valori? ";
cin >> n;
vett = new int[n]; // allocazione
for(int i=0; i<n; i++){
  cout<<i+1<<":";
  cin >> vett[i];
}
delete[] vett; // deallocazione

....

Controllo della corretta allocazione

     

Non sempre è possibile allocare un oggetto nello heap (per esempio nel caso di memoria insufficiente).
In questi casi lo Standard prevede che il programma sollevi un'eccezione che, se non viene opportunamente intercettata, porta all'interruzione immediata del programma stesso. Questo comportamento predefinito può essere modificato in due modi.
Il primo, molto semplice, prevede l'uso di nothrow insieme a new:

vett = new(nothrow) int[n];
if(!vett) cerr << "Errore di allocazione!";

Se l'allocazione non riesce, il valore dell'espressione con new diventa 0 (puntatore null).
La seconda modalità di verifica, più complessa, prevede il dirottamento del controllo del programma a una specifica funzione definita dall'utente.
Questa operazione va effettuata mediante la funzione della Libreria Standard set_new_handler() (header file <new>).

Strutture di dati dinamiche

     

Grazie alla facoltà di allocare dinamicamente la memoria è possibile creare strutture dati molto efficienti, in grado di ottimizzare sia lo spazio che occupano sia la velocità di accesso ai singoli elementi. Le più diffuse strutture di questo tipo sono le liste, gli alberi binari e i grafi.

Liste a legame unico

     

Nella sua forma più semplice (single linked list) una lista è una struttura dati formata da elementi dello stesso tipo collegati in catena la cui lunghezza varia dinamicamente. Ogni elemento è costituito da uno o più campi contenenti le informazioni utili e da un campo che punta all'elemento successivo.

Il primo elemento è indirizzato da un puntatore alla lista, l'ultimo non punta a nulla.

Liste a doppio legame

     

Aggiungendo un altro puntatore a ogni elemento di una lista a legame unico si ottiene una lista a doppio legame (doubly linked list).
In questa struttura ogni elemento punta sia al precedente che al successivo, con la conseguente possibilità di scorrere la lista nei due sensi:

Il puntatore all'elemento precedente del primo dato e quello all'elemento successivo dell'ultimo sono nulli.

Stack e code

     

Diversamente dalle liste, dove generalmente gli elementi possono essere aggiunti ed eliminati in qualsiasi punto, gli stack e le code si distinguono per consentire queste operazioni solo dagli estremi della catena. In particolare, negli stack l'inserimento e l'accesso a un elemento avviene sempre dalla testa (top), l'ultimo elemento inserito è anche il primo a essere estratto (LIFO).
Nelle code, invece, gli elementi sono inseriti dalla testa ed estratti dalla coda.
Il primo elemento immesso è quindi anche il primo a uscire dalla struttura (FIFO).

Esempio

Se A, B e C sono tre elementi inseriti in queste strutture, nello stack l'ordine di estrazione è C, B, A, mentre nella coda è ancora A,B,C.

Alberi binari

     

Come nelle liste a doppio legame, un albero binario è caratterizzato da elementi che contengono uno o più campi per le informazioni e due campi puntatore. In questo caso, però, puntano rispettivamente all'elemento sul ramo sinistro e a quello sul ramo destro:

Se gli elementi vengono disposti nei rami secondo un criterio prestabilito (per esempio il minore a sinistra e il maggiore a destra), l'albero, per la sua stessa natura ricorsiva, mantiene gli elementi automaticamente ordinati.

Grafi

     

I grafi sono costituiti da elementi che possono avere più predecessori e più successori.
Sono caratterizzati dal fatto che il percorso per accedere a un elemento spesso non è univoco:

Per questa peculiarità, i grafi sono spesso impiegati in campo informatico per individuare percorsi ottimali, da quelli nelle reti di computer a quelli stradali, o per rappresentare organizzazioni complesse di dati.