Prednáška 12

Zjednodušený model pamäte

Pamäť počítača si možno veľmi zjednodušene predstaviť ako konečnú postupnosť pamäťových miest, kde každé pamäťové miesto má kapacitu práve jeden byte. To možno znázorniť nasledujúcim obrázkom.

Každé pamäťové miesto má pridelené svoju adresu. Presný formát adries závisí od konkrétnej architektúry (môže napríklad ísť o 32-bitové alebo 64-bitové čísla), z pohľadu programátora však zvyčajne nie je dôležitý.

Premenným základných typov (ako napríklad int, char, double,...) sú počas vykonávania programu pridelené súvislé úseky pamäťových miest. Napríklad na architektúre s 32-bitovým – čiže 4-bytovým – typom int sa premenným tohto typu priraďujú úseky štyroch po sebe idúcich pamäťových miest. Adresou premennej potom rozumieme adresu prvého z týchto pamäťových miest. Táto situácia je znázornená na obrázku nižšie.

Poliam sa taktiež prideľujú súvislé úseky pamäte. Pre pole dĺžky N pozostávajúce z prvkov typu T sa pritom vyhradí N po sebe idúcich pamäťových úsekov, kde každý z nich postačuje práve na uchovanie jednej hodnoty typu T. Napríklad poľu a dĺžky N prvkov typu int sa na architektúre s 32-bitovým (4-bytovým) typom int pridelí súvislý úsek 4*N pamäťových miest tak, ako na nasledujúcom obrázku.

Smerníky

Smerník (niekde tiež ukazovateľ, angl. pointer) je premenná, ktorej hodnotou je pamäťová adresa. Napríklad na nasledujúcom obrázku je na adrese [adresa 2] uložená premenná typu int, ktorej hodnota je 12345. Na adrese [adresa 1] je uložený smerník, ktorého hodnota je [adresa 2] – hovoríme, že smerník ukazuje na pamäťovú adresu [adresa 2].

Definovanie smerníka

V C++ sa smerník ukazujúci na „pamäťový objekt” typu T definuje takto:

T *p;

Napríklad teda môžeme písať:

int *p1;    // smernik p1 na int
char *p2;   // smernik p2 na char
double *p3; // smernik p3 na double

// ...

Smerníky ukazujúce na „pamäťové objekty” rôznych typov sú takisto rôznych typov. Vo všeobecnosti nemožno realizovať priradenia medzi smerníkmi rôznych typov (nedôjde k automatickému pretypovaniu).

int *p1;
int *p2;
double *p3;

p1 = p2;   // korektne priradenie
p3 = p1;   // chyba, lebo p3 a p1 su smerniky roznych typov

Bez ohľadu na typ smerníka je jeho hodnotou vždy len pamäťová adresa, a teda sa ich práve popísané správanie môže zdať na prvý pohľad zvláštnym. Smerníky rôznych typov sa však, ako onedlho uvidíme, v určitých situáciách môžu „správať” rozdielne.

Operátor & (adresa)

Operátor & poskytuje azda najjednoduchší spôsob, ako získať zmysluplný smerník. Adresu premennej x nejakého základného typu (ako napríklad int, char,...) získame tak, že napíšeme &x – túto adresu potom možno priradiť do smerníka.

Nasledujúci program vytvorí celočíselnú premennú n, ktorej adresu priradí do smerníka p.

int main(void) {
    int n = 12345;
    int *p;
    p = &n;

    return 0;
}

Stav pamäte tesne pred skončením vykonávania tohto programu je znázornený na nasledujúcom obrázku.

Rovnakým spôsobom možno operátor & aplikovať aj na prvky poľa (t.j. napríklad &a[2] je adresa druhého – resp. tretieho – prvku poľa a).

Operátor & nemožno aplikovať na konštanty (ako napríklad 3.14 alebo 'c'), ani na výrazy (ako napríklad n+2).

    int n = 0;
    int a[5] = {1, 2, 3, 4, 5};
    int *p;

    p = &n;     // korektne priradenie
    p = &a[2];  // korektne priradenie
    p = &(n+1); // chyba (vyraz nema adresu)
    p = &42;    // chyba (konstanta 42 nema adresu)
    p = &a;     // chyba (a nie je typu int)

Operátor * (dereferencia)

Kľúčovým operátorom na smerníkoch je tzv. dereferencia, ktorá sa realizuje operátorom *. Ak p je smerník, možno pomocou zápisu *p pristúpiť k údajom na adrese reprezentovanej smerníkom p. Tieto údaje potom možno aj meniť, t. j. *p môže vystupovať napríklad aj na ľavej strane priradenia. To demonštrujeme na drobnom rozšírení predchádzajúceho príkladu.

#include <iostream>
using namespace std;

int main(void) {
    int n = 12345;
    int *p;       

    p = &n;              // smernik p odteraz ukazuje na adresu premennej n
    cout << *p << endl;  // vypise hodnotu uchovavanu na adrese p == &n, t. j. 12345
    *p = 9;              // hodnota uchovavana na adrese p == &n sa zmeni na 9; preto uz aj n == 9 
    cout << n << endl;   // vypise hodnotu premennej n, t. j. 9
    (*p)++;              // hodnota uchovavana na adrese p == &n sa zmeni na 10; preto uz aj n == 10 
    cout << n << endl;   // vypise hodnotu premennej n, t. j. 10
    n = 42;
    cout << *p << endl;  // vypise hodnotu uchovavanu na adrese p == &n, t. j. 42

    return 0;
}

Operátor dereferencie vysvetľuje aj spôsob, ktorým sa smerníky deklarujú. Riadok

int *p;

deklarujúci smerník na int totiž treba chápať takto: ak vezmeme smerník p a aplikujeme na neho operátor *, získame hodnotu typu int. Takáto interpretácia sa ukáže byť veľmi užitočnou pri komplikovanejších deklaráciách so smerníkmi.

Smerník NULL

Dôležitým špeciálnym prípadom smerníka je konštanta NULL reprezentujúca smerník, ktorý nikam neukazuje.

• Je definovaná vo viacerých štandardných knižniciach, ako napríklad cstdlib alebo iostream.
• Možno ju priradiť do smerníka ľubovoľného typu.

Smerník ako parameter funkcie

V „čistom C” okrem iného nie je možné predávať parametre funkcií referenciou. Rovnaký efekt však možno docieliť predávaním hodnotou tak, že sa ako hodnota pošle smerník. To demonštrujeme pomocou nasledujúcej „smerníkovej” verzie funkcie realizujúcej výmenu hodnôt dvoch premenných.

#include <iostream>
using namespace std;

void swap(int *px, int *py) {                      // parametre su smerniky (adresy v pamati)
    int tmp = *px;                                 // hodnotu na adrese px ulozime do tmp
    *px = *py;                                     // hodnotu na adrese px zmenime na hodnotu na adrese py
    *py = tmp;                                     // hodnotu na adrese py zmenime na tmp
}

int main(void) {
    int x,y;
    cout << "Zadaj x,y: ";
    cin >> x >> y;
    swap(&x, &y);                                  // ako parametre posleme adresy premennych x,y
    cout << "x = " << x << ", y = " << y << endl;

    return 0;
}

Poznať uvedenú alternatívu k predávaniu parametrov referenciou môže byť užitočné aj pri práci v C++, keďže ju často využívajú rôzne knižničné funkcie.

Dynamická alokácia a dealokácia pamäte

Doteraz sme videli:

• Globálne premenné, ktoré majú vopred známu veľkosť a vyhradenú pamäť.
• Lokálne premenné, ktoré majú vopred známu veľkosť, ale pamäť sa im prideľuje až pri volaní funkcie na tzv. zásobníku volaní funkcií (angl. call stack).

Program si ale počas behu môže podľa potreby vyhradiť aj ďalšiu pamäť:

• Používa sa na to operátor new.
• Pamäť sa vyhradí v oblasti zvanej halda (angl. heap).
• Nepotrebnú pamäť vyhradenú takýmto spôsobom je dobrým zvykom uvoľniť pomocou operátora delete.

#include <iostream>
using namespace std;

int main(void) {
    int *p;        

    p = new int;   // new int vyhradi usek pamate postacujuci na uchovanie prave jednej hodnoty typu int
                   // adresa tohto novovytvoreneho useku pamate sa ulozi do smernika p   
    *p = 50;       // do alokovanej pamate sa ulozi hodnota 50 
    cout << *p << endl;  
    delete p;      // uvolnenie alokovanej pamate

    return 0;
}

Smerníky a polia

Smerníky a polia spolu veľmi úzko súvisia. Operátor [ ] je totiž v prvom rade definovaný na smerníkoch. Nech p je smerník definovaný ako

T *p;

kde T označuje nejaký typ. V takom prípade:

• Zápis p[0] vyjadruje to isté ako *p – ide o hodnotu typu T uloženú na adrese reprezentovanej smerníkom p.
• Zápis p[i] vyjadruje hodnotu typu T uloženú na i-tom pamäťovom úseku (o veľkosti postačujúcej práve na uloženie hodnoty typu T) za úsekom s adresou reprezentovanou smerníkom p. Hoci tento zápis funguje vždy, je dôležité používať ho iba vtedy, keď vieme, čo na danej adrese je.

Táto situácia je znázornená na nasledujúcom obrázku.

Pole a prvkov typu T definované ako

T a[N];

je potom konštantný smerník na prvok typu T (prvý – t. j. vlastne nultý – prvok poľa). Konštantným je preto, lebo adresa prvého prvku takto definovaného poľa je počas behu programu fixná a nemôže sa meniť.

Každé pole je teda zároveň aj smerníkom na svoj prvý prvok. Každé pole typu T tak možno priradiť do smerníka na prvok typu T (avšak nie naopak, lebo polia sú konštantné smerníky a súčasťou typu poľa je aj informácia o jeho dĺžke). Zápis int a[] pre pole ľubovoľnej veľkosti predávané ako parameter funkcie je navyše len rozdielnym zápisom pre int *a. Korektný je tak napríklad aj nasledujúci program.

#include <iostream>
using namespace std;

const int maxN = 1000;

void vypisPole(int a[], int pokial) {
    for (int i = 0; i <= pokial; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
}

void vypisPoleOdzadu(int *a, int odkial) {
    for (int i = odkial; i >= 0; i--) {
        cout << a[i] << " ";
    }
    cout << endl;
}

int main(void) {
    int N;
    int a[maxN];
    int *b;
    cout << "Zadaj pocet cisel: ";
    cin >> N;
    for (int i = 0; i <= N-1; i++) {
        cout << "Zadaj cislo " << i+1 << ": ";
        cin >> a[i];
    }
    
    vypisPole(a,N-1); 
    b = a;
    vypisPole(b,N-1);
    
    vypisPoleOdzadu(a,N-1);
    
    return 0;
}

Dynamické alokovanie poľa

Operátorom new možno alokovať aj pole zadanej dĺžky N (t. j. súvislý úsek pamäte postačujúci na uchovanie práve N hodnôt daného typu). Napríklad príkaz

int *p = new int[10];

vyhradí pamäť postačujúcu práve na uchovanie desiatich celých čísel – čiže vlastne pole veľkosti 10. Z pozorovaní učinených vyššie vyplýva, že smerník p je potom možné používať úplne rovnakým spôsobom, ako polia:

• Hodnota p[0] je tá istá ako *p.
• Hodnota p[i] pre i = 0,...,9 reprezentuje hodnotu i-teho prvku poľa.

Vytvorené a už nepotrebné pole je dobrým zvykom uvoľniť operátorom delete[] (hranaté zátvorky na konci sú naozaj podstatné; program používajúci na pole iba operátor delete síce skompiluje, ale jeho správanie je nedefinované).

Takúto dynamickú alokáciu polí možno využiť napríklad na vytvorenie poľa o používateľom zadanej veľkosti tak, ako v nasledujúcom ukážkovom programe.

#include <iostream>
using namespace std;

int main(void) {
    cout << "Zadaj pocet cisel: ";
    int N;
    cin >> N;
    int *a = new int[N];
    
    for (int i = 0; i <= N-1; i++) {
        cout << "Zadaj cislo " << i+1 << ": ";
        cin >> a[i];
    }
    for (int i = N-1; i >= 0; i--) {
        cout << a[i] << " ";
    }
    delete[] a;
    cout << endl;

    return 0;   
}

Poznámka: Niektoré kompilátory (ako napríklad gcc) umožňujú vytvoriť pole o používateľom zadanej veľkosti aj jednoduchším spôsobom, keďže akceptujú deklarácie typu int a[N];, kde N môže byť aj premenná, ktorej hodnota už bola načítaná príkazom cin >> N;. Nemusí to ale fungovať vždy – odporúčané je používať radšej dynamickú alokáciu poľa tak, ako v príklade vyššie.

Aplikácia smerníkov: dynamické polia

Asi najvýraznejším nedostatkom polí je ich fixná veľkosť. Počas behu programu totiž môže vzniknúť potreba pridávať ďalšie a ďalšie prvky, ktoré sa postupne do poľa nemusia vojsť. Riešenie tejto situácie nadhodnotením veľkosti poľa nie je ideálne, keďže sa tak plytvá pamäťou.

Ako riešenie tohto problému teraz naprogramujeme tzv. dynamické pole, ktoré mení svoju veľkosť s tým, ako sa doň pridávajú prvky. Základná idea pritom bude nasledovná:

• Zakaždým, keď sa pole plne naplní, alokujeme preň nový a väčší pamäťový úsek, kam celé pole presunieme. Starý pamäťový úsek z pamäte uvoľníme.
• Keďže kopírovanie poľa do novoalokovaného pamäťového úseku bude mierne neefektívne (bude potrebné prejsť cez celé pole), budeme sa snažiť vyvarovať toho, aby sme ho museli realizovať zakaždým, keď do poľa pridáme nejaký prvok. Na druhej strane však nechceme alokovať zbytočne veľké úseky pamäte. Rozumným kompromisom sa javí byť zdvojnásobenie veľkosti alokovaného úseku zakaždým, keď sa pole naplní.
• V štandardných C++ knižniciach je definovaná dátová štruktúra vector, ktorá sa správa podobne. My teraz vo svojej podstate implementujeme zjednodušenú verziu tejto štruktúry.

Pre jednoduchosť napíšeme iba verziu dynamického poľa pre celé čísla (typ int). Analogicky by sme však mohli postupovať aj pre iné typy.

Dynamické pole celých čísel budeme reprezentovať ako štruktúru typu dynArray, ktorá bude pozostávať z nasledujúcich troch zložiek:

• Zo smerníku p ukazujúceho na prvý prvok poľa (čiže vlastne pole samotné).
• Z celočíselnej premennej size, v ktorej bude uchovávaná veľkosť alokovanej pamäte pre pole p.
• Z celočíselnej premennej length, v ktorej bude uchovávaný počet prvkov doposiaľ pridaných do poľa.

Napíšeme potom niekoľko funkcií, pomocou ktorých budeme s dynamickými poľami manipulovať.

• Funkcia void init(dynArray &a) inicializuje dynamické pole a, pričom mu alokuje nejaký rozumne malý objem pamäte (ten v našej implementácii bude postačovať na uchovanie práve dvoch prvkov typu int).
• Funkcia void add(dynArray &a, int x) pridá na koniec dynamického poľa a prvok s hodnotou x. V prípade potreby ešte predtým realokuje pamäť.
• Funkcia int get(dynArray a, int index) vráti prvok dynamického poľa a na pozícii index. V prípade, že index nereprezentuje korektnú pozíciu prvku poľa (teda je menší ako 0 alebo väčší, než a.length - 1), ukončí vykonávanie programu pomocou assert.
• Funkcia void set(dynArray &a, int index, int x) nastaví prvok dynamického poľa na pozícii index na hodnotou x. Ak index nereprezentuje korektnú pozíciu prvku poľa, ukončí vykonávanie programu pomocou assert.
• Funkcia int length(dynArray a) vráti počet prvkov doposiaľ uložených do dynamického poľa a.
• Funkcia void destroy(dynArray &a) zlikviduje dynamické pole a (uvoľní pamäť).

Bez ohľadu na implementáciu samotného dynamického poľa už teda vieme napísať kostru programu, ktorý ho využíva:

#include <iostream>
#include <cassert>
using namespace std;

struct dynArray {
// ...
};

void init(dynArray &a) {
// ...
}

void add(dynArray &a, int x) {
// ...
}

int get(dynArray &a, int index) {
// ...
} 

void set(dynArray &a, int index, int x) {
// ...
}

int length(dynArray &a) {
// ...
}

void destroy(dynArray &a) {
// ...
}

int main(void) {
    dynArray a;
    init(a);
    
    int k;
    cin >> k;
    while (k >= 0) {                 
        add(a,k);                    // pridava prvky do pola, kym su nezaporne
        cin >> k;    
    }
    for (int i = length(a) - 1; i >= 0; i--) {
        cout << get(a,i) << " ";     // vypise prvky pola od konca
    }
    cout << endl;
    set(a,0,42);
    cout << get(a,0) << endl;

    destroy(a);

    return 0;    
}

Môžeme teraz prejsť k samotnej implementácii dynamického poľa:

#include <iostream>
#include <cassert>
using namespace std;

/* Dynamicke pole celych cisel */

struct dynArray {
    int *p;                   // smernik na prvy prvok pola
    int size;                 // velkost alokovaneho pola
    int length;               // pocet prvkov pridanych do pola
};

void init(dynArray &a) {
/* Inicializuje dynamicke pole, pricom na zaciatok pren alokuje pole velkosti 2 */
    a.size = 2;
    a.length = 0;
    a.p = new int[a.size];
}

void add(dynArray &a, int x) {
/* Prida na koniec dynamickeho pola prvok x a v pripade potreby realokuje pole */
    if (a.length == a.size) {                // ak uz sa x do pola nevojde
        a.size *= 2;
        int *newp = new int[a.size];         // alokuje pole dvojnasobnej velkosti
        for (int i = 0; i <= a.length - 1; i++) { 
            newp[i] = a.p[i];                // prekopiruje stare pole do noveho
        }
        delete[] a.p;                        // zmaze stare pole
        a.p = newp;                          // a.p odteraz ukazuje na nove pole
    }
    a.p[a.length] = x;                       // ulozi x na koniec pola
    a.length++;                              // zvysi pocet prvkov ulozenych v poli 
}

int get(dynArray &a, int index) {
/* Vrati prvok dynamickeho pola a na pozicii index (ak ide o korektnu poziciu)*/
    assert(index >= 0 && index <= a.length - 1);
    return a.p[index];
} 

void set(dynArray &a, int index, int x) {
/* Nastavi prvok dynamickeho pola a na pozicii index na hodnotu x (ak ide o korektnu poziciu)*/
    assert(index >= 0 && index <= a.length - 1);
    a.p[index] = x;
}

int length(dynArray &a) {
/* Vrati pocet prvkov ulozenych v dynamickom poli a */
    return a.length;
}

void destroy(dynArray &a) {
/* Zlikviduje dynamicke pole a (uvolni alokovanu pamat) */
    delete[] a.p;
}

int main(void) {
    dynArray a;
    init(a);
 
    int k;
    cin >> k;
    while (k >= 0) {                 
        add(a,k);                    // pridava prvky do pola, kym su nezaporne
        cin >> k;    
    }
    for (int i = length(a) - 1; i >= 0; i--) {
        cout << get(a,i) << " ";     // vypise prvky pola od konca
    }
    cout << endl;
    set(a,0,42);
    cout << get(a,0) << endl;
 
    destroy(a);

    return 0;    
}

Smerníková aritmetika

Na smerníkoch možno vykonávať určité operácie, súhrn ktorých býva honosne nazývaný smerníkovou aritmetikou. Nech p, p1, p2 sú smerníky definované ako

T *p;
T *p1;
T *p2;

kde T označuje nejaký typ. Nech n je typu int. Potom:

• p + n označuje smerník na n-tý pamäťový úsek (postačujúci práve na uchovanie hodnoty typu T) za adresou p.
  • Napríklad p+n je to isté ako &p[n] a *(p+n) je to isté ako p[n].
  • p++ je skratkou pre p = p+1, ...
• Operátor [ ] je teda nadbytočný – p[n] je len skratkou pre často používaný výraz *(p+n).
• p - n označuje smerník na n-tý pamäťový úsek (postačujúci práve na uchovanie hodnoty typu T) pred adresou p.
• p1 - p2 je celé číslo k také, že p1 == p2 + k. Zmysluplný výsledok možno očakávať len vtedy, keď p1 a p2 sú adresami prvkov v tom istom poli (v jedinom súvislom kuse pamäte).
• Smerníky tiež možno prirodzene porovnávať relačnými operátormi ==, <, >, <=, >=, !=. Výsledok je zmysluplný opäť len vtedy, keď p1 a p2 sú adresami prvkov v tom istom poli.

Program, ktorý najprv načíta pole a následne prvky tohto poľa vypíše od konca, tak možno napísať napríklad aj takto:

#include <iostream>
using namespace std;

const int maxN = 1000;

int main(void) {
    int a[maxN];
    int N;
    cout << "Zadaj pocet cisel: ";
    cin >> N;
    for (int i = 0; i <= N-1; i++) {
        cout << "Zadaj cislo " << i + 1 << ": ";
        cin >> *(a + i);    
    }
    for (int i = N-1; i >= 0; i--) {
        cout << *(a + i) << " ";
    }
    cout << endl;
    return 0;
}

Ladenie programov so smerníkmi

• Smerníky môžu byť nepríjemným zdrojom chýb, keďže kompilátor nekontroluje, či sú používané správne.
• Napríklad možno čítať aj zapisovať mimo alokovanej pamäte.
• S odchytávaním takýchto chýb môžu pomôcť automatizované nástroje, ako napríklad Valgrind (pre Linux) alebo Dr. Memory (pre Windows aj Linux).
• Návod na prácu s programom valgrind