Tablouri. Pointeri. Referinte


Tablouri de Obiecte

In C++ tablourile sunt tipuri derivate, create utilizand operatorul de declarare [ ] in combinatie cu un tip fundamental (exceptand tiupl void) sau un tip definit de utilizator. Tablourile pot fi unidimensionale sau multidimensionale.  Modul de declarare a tablourilor, cunoscut din C, se regaseste integral si in C++.  In C++ tipul elementelor tabloului poate fi o clasa, caz in care spunem ca am declarat un tablou de obiecte.

Initializarea obiectelor dintr-un tablou
Asa cum am vazut deja in lucrarea anterioara la instantierea unui obiect, pe langa alocarea spatiului necesar de memorie,  are loc si initializarea obiectului prin lansarea in executie a unuia dintre constructorii clasei, corespunzator formei de declaratie. Intrucat crearea unui tablou de n obiecte reprezinta de fapt instantierea "in bloc" a n obiecte, este normal ca pentru fiecare element al tabloului sa existe cate un apel al unui constructor. Deci, pentru un tablou de n  obiecte se vor executa n apeluri de constructor. Intrebarea care se ridica este cum putem specifica modul de initializare a elementelor tabloului,  adica cum putem indica in declaratia tabloului care constructor sa fie apelat pentru a realiza initializarea? Se disting trei moduri de initializare sintetizate in exemplul de mai jos:
 

class Complex { 
public: 
 Complex() {re=0; im = 0;}
 Complex(int i) {re=i;}
 Complex(int i, int j) {re=i; im=j;}
private:
  int re;
  int im;
};

...

main() {
 Complex z[10]; //1
 Complex z1[3] = {1,2,3}; //2
 Complex z2[3] = {  //3
    cl(1,0), 
    cl(2,-1),
    cl(0,-4)
 };

...

}
Ultimele 2 modalitati de initializare se pot aplica daca dimensiunile tablourilor nu sunt prea mari. La parasirea domeniului de existenta a unui tablou de obiecte, in mod automat se va executa destructorul pentru fiecare din ele. Este valabila urmatoarea regula: la creare, obiectele ce compun tabloul sunt initializate incepand cu primul (cel de indice 0), in timp ce destructorul actioneaza incepand cu ultimul obiect.
 

Accesarea elementelor tabloului.
Operatia fundamentala asupra variabilelor de tip tablou este  indexarea, adica accesarea unui element de indice dat. Operatorul de indexare este '[ ]'. Astfel, referirea elementului cu indice i dintr-un tablou T se realizeaza cu expresia T[i]. Tipul tablou reprezinta de fapt o concretizare a conceptului de secventa. O secventa de elemente apartinand unei multimi M este o functie  definita pe multimea numerelor naturale, cu valori in M (M trebuie sa fie o multime discreta). Practic, secventa realizeaza numerotarea elementelor  lui M, inducand astfel automat o ordonare a multimii respective.

Generalizarea Tablourilor
Lipsa de generalitate a tipului tablou, asa cum este el implementat in limbajele  de programare este data de urmatoarele restrictii:

  • Elementele tabloului sunt stocate in zone contigue de memorie, indiferent daca alocarea s-a facut static sau dinamic;
  • Odata creat, un tablou nu-si mai poate modifica dimensiunile.
  • Elementele din tablou sunt toate de acelasi tip.
  • In C++, in particular, indicii tablourilor pot lua doar valori intregi, >=0.
Cu ajutorul claselor, in C++ se poate generaliza notiunea de  tablou, astfel incat sa se poata crea tablouri cu dimensiuni variabile,
ale caror elemente pot fi plasate disparat in memorie si  chiar tablouri eterogene cu care insa se poate opera, la nivelul utilizatorilor externi, ca si cu cele omogene.
Toate acestea vor fi descrise in lucrarea  Supraincarcarea Functiilor si a Operatorilor.
 

Pointeri

In C++ pointerii sunt tipuri derivate, create utilizand operatorul de declarare * in combinatie cu un tip fundamental sau  definit de utilizator.  Modul de declarare a pointerilor cunoscut din C se regaseste integral si in C++.  Un pointer la un anumit tip T nu este altceva decat o adresa la care se gaseste (sau s-ar putea gasi) un obiect de tip T.
 

Atentie:  Declaratia unei variabile de tip pointer nu face decat sa rezerve spatiul necesar memorarii unei adrese; O astfel de declaratie nu initializeaza variabila declarata cu valoarea unei adrese particulare si nici nu  rezerva spatiu pentru vreun obiect valid spre care sa indice variabila respectiva. Daca tipul pointerului este o clasa, observatia de mai sus ramane valabila, consecinta  fiind ca o asemenea  declaratie nu va declansa executia nici unui constructor!!!

Pointeri la Tablouri si Functii.
O notatie mai complicata se foloseste in cazul pointerilor la  tablouri si functii:
 

int (*vp)[10];   //vp este pointer la tablou de 10
   //int-uri
int (*fp)(char,float);    // fp este pointer la o
   //functie cu parametrii (char,float) si tip
   //returnat int
Aici parantezele din jurul variabilei pointer sunt necesare deoarece  operatorii de declarare [ ] si ( ) au prioritate fata de *.

Pointerul zero
In C++ valoarea 0 este in mod normal considerata ca fiind de tip int, dar, ca urmare a existentei unui set de reguli de conversie automata, ea poate fi folosita ca o constanta a oricarui tip intreg, virgula flotanta, pointer sau pointer la membru. Tipul actual al constantei se deduce din context.
Deoarece nici unui obiect nu ii este alocata in memorie adresa 0, aceasta constanta poate fi folosita in lucrul cu tipurile pointeri ca o valoare speciala, pentru a indica faptul ca un pointer nu refera nici un obiect, deci ca echivalent al lui 'nici-o-adresa'.
In C a fost incetatenita practica de a defini un macro numit NULL pentru a reprezenta pointerul zero. Si in C++ se poate folosi acest macro, dar deoarece in acest limbaj mecanismele de verificare a tipurilor sunt mai puternice, se recomanda fie utilizarea literalului 0 ca atare, fie definirea unei constante NULL sub forma:

const int NULL = 0;

datorita prezentei lui const, aceasta definitie are un dublu avantaj: pe de o parte permite folosirea identificatorului NULL oriunde este necesara o constanta, iar pe de alta parte previne redefinirea accidentala a lui NULL.

Initializarea unei variabile pointer

 O variabila pointer poate indica la un moment dat fie un obiect  alocat static, fie unul alocat dinamic.  In cazul obiectelor alocate static avem urmatoarele exemple de initializare:
 

int x;
int *pi=&x;                                  //pi se initializeaza cu adresa lui x

int func2(char c, float f)  {. .. } 
int (*fp)(char,float)=func2;         //fp se initializeaza cu  adresa functiei
   //func2

Operatorii new si delete
In C++ au fost introdusi 2 operatori pentru alocarea dinamica a memoriei: new-pentru alocare si delete-pentru eliberare. Un exemplu de utilizare a lor a fost dat deja in lucrarea precedenta.

In afara de modificarile de sintaxa, cei 2 operatori aduc in plus fata de  functiile malloc/free un lucru important din perspectiva lucrului cu clase, si anume:

  • Operatiile de forma:
          AClass *pcl=new AClass;  //sau
          AClass *pcc=new AClass(4);
    declanseaza executia constructorului corespunzator pentru obiectul creat  in heap;


  • O operatie de forma:
          AClass *ptc=new AClass[8];
    creaza in heap un bloc de 8 obiecte de tip AClass si, in plus, declanseaza executia constructorului implicit pentru fiecare dintre cele 8 obiecte, la fel ca in cazul unui tablou static;


  • Operatiile de forma:
          delete pcl;
          delete[] ptc;
    determina executia distructorului pentru obiectul (obiectele)  indicat(e) de pcl, respectiv ptc, inainte ca zona ocupata in heap sa fie eliberata.

Operatia fundamentala efectuata asupra unei variabile pointer este dereferentierea sau indirectarea, adica referirea obiectului indicat de pointer. Operatorul de indirectare este '*'.
Exemple:

        int *pi=new int;
        *pi=6; //obiectul indicat de pi este initializat cu 6
        int i=(*fp)('c',13.4); //se apeleaza functia indicata de
           //pointerul fp, iar rezultatul se depune in i

Daca obiectul indicat de un pointer este de tip struct, class sau union,  pentru a specifica accesul la unul din campurile obiectului, limbajul permite utilizarea unei notatii echivalente cu (*pointer).camp, dar mai sugestiva, si anume: pointer->camp.
Exemplu:
        struct stru {
          int un_camp;
        };
        stru *ps=new stru;
        ps->un_camp=7;

Una din cele mai frecvent intalnite categorii de erori in programele C++ este legata de lucrul cu pointeri. In aceasta categorie intra:

  • 1.Dereferentierea variabilelor pointer care contin valoarea NULL sau care nu au facut obiectul alocarii prealabile de memorie in heap; exemplu:
        char *sir, a;
        int *nr = NULL, b;
        a = *sir; // oops!
        b = *nr; // idem

  • 2.Aplicarea operatorului delete la pointeri care fie nu indica nici o zona in heap, fie indica obiecte alocate static; exemplu:
        char *sir;
        int a, *nr = &a;
        delete sir; // you, small brain!
        delete nr; // --"--"-

  • 3.Omiterea perechii de paranteze drepte in cazul aplicarii operatorului delete asupra unui pointer care indica un tablou de obiecte, ceea ce va determina un comportament imprevizibil al operatiei; de cele mai multe ori rezultatul este ca nu se va apela destructorul pentru fiecare dintre elementele tabloului si nu se va elibera in totalitate memoria ocupata de ele:
        int *tnr = new int [6];
        delete tnr; // in loc de delete[ ] tnr;

  • 4.Tentativele de utilizare a unui pointer care a facut obiectul unei operatii delete ca si cum el ar avea valoarea NULL; in realitate, operatia delete lasa pointerul respectiv cu o valoare nedefinita!!
        //. . .
        delete ptr;
        if (!ptr) {...}; //maybe yes, maybe no...

  • 5.Tentativele de acces la zone din heap aflate dincolo de zonele alocate (de obicei cand dimensiunea zonelor alocate este insuficienta); exemplu:
        char *sir=new char[6];
        strcpy(sir,"macrostabilizare"); //sir nu are suficient spatiu

  • 6.Erorile de tastare in cazuri de genul:
        tip *pt=new tip(n); //in loc de tip[n]
    ceea ce se intampla aici este ca se aloca spatiu pentru a memora 1 (!!!) obiect de tip tip, obiectul respectiv fiind initializat (daca e posibila conversia) cu valoarea n; ceea ce s-ar fi dorit de fapt, ar fi fost rezervarea de spatiu pentru n obiecte.


  • 7.Incercarea de a elibera "pe bucati" o zona de mai multe obiecte care au fost alocate in bloc (printr-o singura operatie new):
        T *p = new T[10], *q;
        for(int i=0, q=p; i<10; i++, q++)
            delete q; //don't do that!!!!
        q = &p[5]; delete[ ] q; //biiig mistake!!!
        delete[] p; //corect; este singura posibilitate de stergere!!!

Majoritatea programelor care contin asemenea erori se soldeaza, pe langa anomaliile de executie, cu afisarea mesajului "Segmentation fault" (sub Unix) sau "Null pointer assignment" (sub DOS).

 Pointerul this
Acest simbol poate fi referit doar in interiorul functiilor membru non-statice ale unei clase. El este numele generic al pointerului spre obiectul curent, adica obiectul pentru care se executa la un moment dat functiile respective (poate fi interpretat ca adresa obiectului vazuta dinspre interiorul acestuia).
Am vazut in lucrarea precedenta ca, daca intr-un program se creaza mai multe obiecte ale unei clase, din perspectiva utilizatorului lucrurile apar ca si cum fiecare obiect isi are propriile lui exemplare ale membrilor non-statici ai clasei. Pentru datele membru acest lucru este chiar adevarat. In cazul functiilor membru insa, fizic codul lor este stocat in memorie intr-un singur exemplar, iar prototipul real al acestor functii contine ca prim parametru un pointer la clasa respectiva:

      class AClass {
        ReturnType MemberFunc(lista_param_form);
        //. . .
      }
      //functia AClass::MemberFunc are prototipul real
      ReturnType MemberFunc(AClass *this,lista_param_form);
Asa se explica faptul ca orice referire simpla a unui membru non-static d in interiorul unei functii membru non-statica este echivalenta cu: this->d.
Un apel de forma:
      AnObject.MemberFunc(lista_param_act);
se traduce de catre compilator prin:
      MemberFunc(&AnObject, lista_param_act);
Acest lucru este insa transparent pentru utilizator.
Folosind constructia *this se realizeaza referirea intregului continut al unui obiect, din interiorul lui insusi.

Tablouri si pointeri
In limbajul C notiunea de pointer a fost extinsa astfel incat  un nume de tablou poate fi asimilat cu un pointer spre inceputul tabloului. Cu alte cuvinte, fiind dat un tablou de forma:

      tip_elem tab[n];
numele tab poate fi folosit apropape in toate locurile in care se asteapta un pointer la tipul tip_elem.
Exemple:
  • Apelul unei functii care are ca parametru formal un pointer:
        tipf func(tip_elem *p, alti_param_form) {
          //. . .
        }
        tip_elem tab[10];
        //. . .
        func(tab, alti_param_act);
    aici e locul sa facem precizarea ca in C/C++ transmisia tablourilor ca parametri nu se face niciodata prin valoare, ci numai prin adresa; acest lucru este valabil chiar daca functia func de mai sus ar avea prototipul:
        tipf func(tip_elem p[ ], alti_param_form);
    sau
        tipf func(tip_elem p[10], alti_param_form);

  • Referirea unor elemente ale tabloului:
        *tab = val_elem; //se initializeaza primul elem. al tabloului
    Este valabila si situatia inversa, adica folosirea unui pointer ca nume de tablou intr-o operatie de indexare:
        tip_elem *pe = new tip_elem[k]; //se aloca spatiu contiguu
              //pt k obiecte de tip tip_elem
        for(int i=0;i < k;i++)
          pe[i] = expr; //se initializeaza al (i+1)-lea obiect
In concluzie, asimilarea numelor de tablouri cu pointerii si invers, se refera la modul de accesare a elementelor tablourilor respective; dupa cum s-a vazut in exemplele anterioare, putem aplica operatorul de indexare asupra unui pointer si, respectiv, operatorul de indirectare asupra unui nume de tablou.

Intre un nume de tablou static si un pointer exista totusi cateva deosebiri importante (in afara de accea ca elementele unui tablou static se afla in stiva, iar cele ale unui tablou dinamic se afla in heap). Vom vedea in continuare care sunt acestea:

  • numele unui tablou nu poate fi tratat ca o entitate lvalue si, ca urmare, unele instructiuni din secventa de mai jos sunt eronate:
        tip_elem tab[n], altu[n], *ptab = new tip_elem[k];
        tab = altu; //eroare
        tab = ptab; //eroare
        tab = new tip_elem[q]; //eroare
        delete[ ] tab; //eroare
        delete[ ] ptab; //corect
        ptab = altu; //corect
        delete [ ] ptab; //acum eroare (vezi eroarea 2 cu pointeri)
    Pe scurt, numele de tablouri alocate static pot fi utilizate doar ca referinte constante.


  • o alta deosebire intre tablouri statice si pointeri este urmatoarea: in interiorul domeniului in care tab si ptab au fost definite sunt adevarate egalitatile:
        sizeof(tab) = n * sizeof(tip_elem) si
        sizeof(ptab) = sizeof(tip_elem*)
    In schimb, in interiorul unei functii careia i-a fost transmis tab ca parametru, acesta nu mai este perceput ca tablou static, ci ca pointer, chiar daca in prototipul functiei el apare ca tablou (vezi exemplul). Drept urmare, in interiorul unei asemenea functii nu mai putem aplica operatorul sizeof pentru a afla dimensiunea reala a tabloului cu care se lucreaza la un moment dat. Singura solutie in acest sens este de a transmite si dimensiunea ca parametru.
      In programele C++ nu se poate realiza nici la nivelul compilarii, nici al executivului, verificari privind depasirea limitelor indicilor de tablouri, indiferent daca acestea au fost alocate static sau dinamic. Tablourile sunt tipuri de baza, iar la crearea unui tablou nu se memoreaza nicaieri dimensiunea lui. Situatiile in care au loc depasiri ale limitelor tablourilor nu sunt sesizate ca exceptii, iar efectele sunt nedefinite.

Tablouri de pointeri
Un tablou de pointeri la un tip T poate fi asimilat cu o matrice de elemente de tip T, diferenta fiind ca, in primul caz liniile matricei pot avea lungimi diferite:

        int matr[n][m]; //matrice de intregi alocata static; fiecare
            //linie are cate m int-uri
        int *tab[n]; //tablou de n pointeri la int
        int dim(int); //functie care returneaza un intreg
        for(int i=0;i<n;i++)
          tab[i]=new int[dim(i)]; //elementele lui tab sunt tablouri
              //de int-uri, de dimens.variabile

Variabilele matr si tab pot fi folosite in continuare ca nume de matrici obisnuite, cu observatia ca, in cazul lui tab este sarcina programatorului sa elibereze memoria alocata.
    In Anexa 3, prin intermediul unui exemplu cuprinzator se face o tratare mai detaliata a modului de interpretare a tablourilor bidimensionale ca pointeri (si invers).

Aritmetica pointerilor
In limbajul C++ s-a definit un set de operatii aritmetice in care unul din operanzi este un pointer, iar celalalt o expresie de tip intreg. Astfel: orice constructie de forma: p[i], unde p este un pointer la un tip T sau numele unui tablou cu elemente de tip T, este echivalenta cu *(p+i), cu conditia ca T sa nu fie void. Cu alte cuvinte, p+i reprezinta adresa unui obiect aflat la deplasament i*sizeof(T) fata de adresa indicata de p.

Este posibila si aplicarea operatiei de scadere, sub forma: p-i, expresia reprezentand adresa unui obiect aflat la deplasament (-i)*sizeof(T) fata de adresa indicata de p. Este evident ca daca avem secventa:

        int *p=new int[5];
        *(p-2)=6;
a doua instructiune reprezinta o tentativa de accesare a unui spatiu de memorie la care nu avem dreptul, rezultatul fiind o comportare nedefinita a programului (vezi eroarea 5 cu pointeri). In schimb, secventa:
        int *p=new int[5], *q;
        for(i=5,q=p+5;i>0;i--) *(q-i)=expr;
este corecta.

Este posibila si scaderea intre 2 pointeri, cu conditia ca ei sa fie de acelasi tip si, in plus, sa indice elemente ale aceluiasi tablou. Aceasta ultima conditie nu poate fi verificata automat, asigurarea ei fiind o sarcina a programatorului. Daca avem urmatoarea secventa:

        T *p=new T[n];
        T *q,*r;
        q=p+i; // i<n
        r=p+j; // j<n
rezultatul expresiei q-r este un numar intreg, reprezentand numarul elementelor tabloului p aflate intre pointerii q si r.
 

Referinte

Prin referinta la un obiect se intelege o alternativa la numele obiectului. Notatia X& inseamna referinta la un obiect de tip X.
Exemple:

        int i = 4;
        int& alt_i = &i; //i si alt_i sunt nume ale aceluiasi obiect
In continuare, simbolurile i si alt_i vor putea fi utilizate in domeniul lor de vizibilitate unul in locul altuia. Astfel:
        alt_i = 5; //efectul: i=5
        i = 7;
        int j = alt_i+2; //efectul: j=9
        alt_i++; //efect: i=8

Notiunea de referinta a fost introdusa in limbajul C++ in primul rand cu scopul de a rezolva problema parametrilor de intrare/iesire ai unei functii intr-o maniera mai comoda pentru programator decat o fac pointerii.
Exemplu: fie functia:

        void func(int *p) {
          //. . .
          *p = ...;
          //. . .
        }
apelul la o asemenea functie ar fi: func(&a), unde a este o variabila de tip int.
In varianta cu referinte, aceeasi functie, respectiv apel ar arata astfel:
        void func(int &p) {
          //. . .
          p = ...;
          //. . .
        }
        . . .
        func(a);

In ambele variante modificarile aduse parametrului formal in timpul executiei lui func se pastreaza la revenirea din functie. Se observa ca in varianta a doua, referirea parametrilor, atat a celui formal, cat si a celui actual, se face mai natural, intr-o maniera similara manipularii parametrilor declarati cu var in programele Pascal.

Nu intotdeauna insa scopul transmiterii de parametri prin referinta este acela ca ei sa serveasca drept parametri de iesire, ci acela de economisire de spatiu. Corespunzator parametrilor declarati ca referinte, de fapt se transmite adresa parametrilor de apel. Ca urmare, pentru un tip T care satisface conditia

sizeof(T) > sizeof(T *)

este mai eficient sa se utilizeze transmiterea prin referinte, indiferent daca parametrii sunt doar de intrare sau de intrare/iesire.
Exemplu:
        struct S {
          //. . .
        };
        tipf func(const S& p) {
          //. . .
        }
Prezenta lui const in declaratia parametrului p implica interdictia de a-l modifica pe p in corpul functiei.

In cazul in care tipul T reprezinta o clasa, transmiterea prin referinta a obiectelor de tip T ca parametri in apelul unei functii evita executia copy-constructorului clasei respective.

Referintele pot fi utilizate si in cazul rezultatelor returnate de unele functii. In acest caz apelurile la functiile respective vor reprezenta expresii lvalue, deci vor putea sa apara ca membri stangi in atribuiri, de exemplu.

Problema
Sa se implementeze in C++, in varianta cu alocare dinamica stiva de la problema din lucrarea precedenta, respectand aceeasi interfata. Clasa va trebui sa aiba implementati urmatorii constructori:

    • Stack() - acest constructor va crea o stiva in care nu se aloca memorie pentru nici un element;
    • Stack(const Stack &) - copy-constructor;
    • Stack(int n) - acest constructor va crea o stiva in care este alocata memorie pentru n elemente.
La  o operatie push(), daca stiva este plina (adica nu mai este memorie alocata) , se aloca memorie si se insereaza noul element. (O varianta optimizata ar fi ca, in cazul in care stiva este plina, sa se aloce spatiu pentru mai mult de un element).
In cazul un operatii pop(), pe langa extragerea elementului din varful stivei, se si elibereaza memoria alocata.
Cerinte de implementare:
    1. Elementele stivei NU vor mai fi numere intregi ca in exemplul precedent, ci vor fi instante ale unei clase CElement (echivalentul structurii "nod" folosita la construirea unei liste simplu inlantuite). Clasa CElement va contine, pe langa structura de date propriu-zisa - informatie + legatura spre urmatorul element - si doi constructori si un destructor. Acestia vor fi:
      • CElement() - se aloca memorie pentru campul de informatie din nod.
      • CElement(TipInformatie) - unde TipInformatie se va considera pentru problema aceasta char* (adica un sir de caractere). Se aloca memorie si se copiaza informatia transmisa ca parametru.
      • ~Celement() - dezaloca spatiul pentru TipInformatie.

    2. Sa se incerce implementarea destructorilor pentru clasa Stack si CElement in asa fel incat distrugerea intregii stive sa se faca prin simpla apelare a destructorului pentru elementul din varful stivei, iar acesta la randul lui sa apleze destructorul pentru urmatorul element s.a.m.d (deci, apel recursiv al destructorului ~CElement). Care este oribilul bug ascuns in spatele acestei "geniale" idei? Poate fi el corectat, pastrand insa ideea pentru stiva? Ar putea fi corectat si pentru cazul implementarii dinamice a unei liste? 


Bibliografie

[Cop94]    J. Coplien  - "Advanced C++ Programming Styles and Idioms",  Addison-Wesley, 1991
[Str97]    B. Stroustrup - "The C++ Programming Language", 3rd ed., AT&T, 1997

Hosted by www.Geocities.ws

1