Conceptul de alocare dinamică

Un program aflat în execuție primește de la sistemul de operare o zonă din memoria internă. În această zonă se păstrează instrucțiunile programului și datele pe care le prelucrează. Locul în care stă o dată și momentul în care i se rezervă memorie depind de felul în care a fost declarată în program.

Adresa unei date

Memoria internă este o succesiune de locații de câte un octet, numerotate consecutiv începând de la 0. Numărul de ordine al unei locații se numește adresă de memorie și se scrie de obicei în baza 16.

O dată ocupă un grup de octeți consecutivi, al căror număr depinde de tipul ei. Adresa datei este adresa primului octet din grup. Declarația int a = 100; rezervă pentru variabila a 4 octeți, în care se păstrează reprezentarea binară a valorii 100.

Orice dată are atributele următoare, pe care le primește la declarare:

• numele — identificatorul prin care este folosită în program;
• tipul — stabilește mulțimea valorilor posibile, operațiile permise și modul de reprezentare internă;
• lungimea — numărul de octeți ocupați, care se obține cu operatorul sizeof;
• adresa — adresa zonei de memorie rezervate datei;
• valoarea — conținutul acestei zone la un moment dat;
• durata de viață — intervalul de timp în care data are memorie rezervată.

La o dată se poate ajunge prin numele ei, ceea ce se numește adresare directă, sau prin adresa ei, păstrată într-o altă variabilă, ceea ce se numește adresare indirectă. Variabila în care se păstrează adresa unei date este un pointer.

Zonele de memorie ale unui program

Memoria unui program C++ este organizată pe zone, iar fiecare zonă păstrează un anumit fel de date:

Variabilele globale se inițializează automat cu 0. Variabilele locale nu primesc o valoare inițială: până la prima atribuire conțin o valoare reziduală, rămasă în memorie de la datele folosite anterior.

Felul în care se ocupă și se eliberează segmentul de stivă la apelul subprogramelor este descris în subcapitolul Subprograme recursive.

Alocarea statică a memoriei

Alocarea statică a memoriei este modul de alocare în care dimensiunea zonei rezervate unei date se stabilește la compilare, pe baza declarației, și rămâne aceeași pe toată durata execuției. Variabilele pentru care memoria se alocă astfel se numesc variabile statice. Ele se află în segmentul de date, dacă sunt globale, sau în segmentul de stivă, dacă sunt locale.

Alocarea statică este potrivită atunci când dimensiunea datelor se cunoaște de la scrierea programului. Dacă numărul de elemente ale unui șir se află abia la execuție, de exemplu prin citirea lui n, tabloul se declară cu dimensiunea maximă permisă de enunț:

int v[10000];     // cel mult 10000 de elemente
int n;
cin >> n;         // n poate fi 5, dar si 10000

Dacă zona rezervată se dovedește prea mică, programul poate scrie în afara ei, peste memoria altor date, iar limbajul C++ nu semnalează eroarea. Dacă zona depășește cu mult nevoile programului, memoria rămasă neocupată nu poate fi folosită de alte date: pentru n = 5, tabloul v ocupă 40 000 de octeți, dintre care se folosesc 20.

Alocarea dinamică a memoriei

Alocarea dinamică a memoriei este modul de alocare în care zona de memorie a unei date se rezervă și se eliberează pe parcursul execuției, atunci când programul o cere. Datele pentru care memoria se alocă astfel se numesc variabile dinamice și se află în zona de adrese libere, numită heap.

O variabilă dinamică nu are nume. Programul ajunge la ea numai prin adresa ei, pe care o memorează un pointer. Pointerul este o variabilă statică obișnuită: dacă este declarat global, se află în segmentul de date, iar dacă este declarat local, în segmentul de stivă. Dinamică este numai zona de memorie a cărei adresă o păstrează el.

Adresa unei variabile dinamice poate fi păstrată în mai mulți pointeri. Dacă ea nu mai este păstrată în niciun pointer, variabila dinamică devine inaccesibilă: zona ei rămâne ocupată până la terminarea programului, iar programul nu o mai poate nici folosi, nici elibera.

Mecanismul alocării dinamice

O variabilă dinamică se folosește în C++ în etapele următoare:

1. Declararea pointerului. Se declară un pointer al cărui tip de bază este tipul variabilei dinamice.
2. Alocarea memoriei. În momentul în care variabila dinamică devine necesară, programul cere memorie cu operatorul new. În heap se rezervă o zonă de dimensiunea tipului, iar adresa ei se atribuie pointerului.
3. Eliberarea memoriei. În momentul în care variabila dinamică nu mai este necesară, programul eliberează zona cu operatorul delete. Valoarea păstrată acolo se pierde, iar zona poate fi rezervată pentru alte date.

int *p;          // 1. declararea pointerului

p = new int;     // 2. alocarea memoriei in heap
*p = 25;
cout << *p;      //    se afiseaza 25

delete p;        // 3. eliberarea memoriei

Tabloul cu dimensiunea citită

La un șir de n numere întregi, cu n citit de la tastatură, zona de memorie se poate rezerva după citirea lui n, cu exact atâtea locații câte sunt necesare. Expresia new int[n] rezervă în heap n locații consecutive de tip int și furnizează adresa primei locații. Elementele se folosesc apoi cu indici, ca la un tablou declarat obișnuit.

Problemă. Se citesc un număr natural n și apoi n numere întregi. Se afișează numerele mai mari decât media aritmetică a celor n numere.

Exemplu: pentru n = 5 și numerele 4 9 2 7 8, media este 6, iar programul afișează 9 7 8.

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int *v = new int[n];        // exact n elemente, rezervate in heap

    double s = 0;
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        s = s + v[i];
    }
    double media = s / n;

    for (int i = 0; i < n; i++)
        if (v[i] > media)
            cout << v[i] << " ";

    delete[] v;                 // se elibereaza toata zona tabloului
    return 0;
}

Pentru n = 5, tabloul ocupă 5 · sizeof(int), adică 20 de octeți. O zonă alocată cu new[] se eliberează cu delete[], scris cu paranteze drepte.

Alocarea statică și alocarea dinamică

Alocarea statică stabilește dimensiunea zonei de memorie la compilare, pe baza declarației, iar alocarea dinamică rezervă și eliberează zona în timpul execuției, la cererea programului.

Structuri de date statice și dinamice

Un tablou declarat în program este o structură de date statică: elementele lui ocupă locații consecutive, iar adresa oricărui element se calculează din adresa tabloului și din indice. O listă înlănțuită alocată dinamic este o structură de date dinamică: fiecare nod primește memorie separat, acolo unde se găsește o zonă liberă în heap, iar nodurile se regăsesc prin adresele păstrate în ele.

Listele, stivele, cozile și arborii alocați dinamic, cu operațiile lor, sunt prezentați în subcapitolul Structuri de date implementate dinamic.

Apariții la examen

La Titularizare 2005, varianta 2, Subiectul I, cerința 2, s-a cerut pentru 15 puncte:

Descrieți tehnica alocării dinamice a memoriei după următorul plan de idei:

• explicați mecanismele alocării dinamice a datelor în memorie;
• descrieți și clasificați listele liniare alocate dinamic;
• descrieți o structură de date arborescentă alocată dinamic;
• identificați trei operații specifice listelor liniare alocate dinamic și scrieți subprogramele corespunzătoare, definind în prealabil tipurile de date utilizate.

Baremul a împărțit punctele astfel:

Primele trei rânduri ale baremului corespund acestui subcapitol și celui despre operațiile de alocare și eliberare. Restul punctelor privesc structurile de date implementate dinamic.

În variantele din arhivă de după 2005, alocarea dinamică nu mai apare ca temă separată. Ea este cerută ca mod de implementare în subiectele despre liste, cozi și arbori, de exemplu la Titularizare 2015 și Definitivat 2018, precum și în problemele de programare cu liste de la Titularizare 2017, 2018 și 2021.