Prednáška 12

Ukazovateľ, smerník, pointer

• Pamäť v počítači je rozdelená na dieliky, do ktorých sa zapisujú hodnoty premenných
• Väčšinou k týmto dielikom pristupujeme pomocou mien premenných
• Každý dielik má adresu (niečo ako poradové číslo)
• Ukazovateľ (resp. smerník alebo pointer) je premenná, ktorej hodnota je adresa iného dieliku pamäte

• Na 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], budeme to kresliť ako šípku.

Definovanie smerníka

Smerník ukazujúci na premennú typu T sa definuje ako T *p, napríklad:

int    *p1;   // smerník p1 na int
char   *p2;   // smerník p2 na char
double *p3;   // smerník p3 na double

// atď

Smerníky ukazujúce na premenné rôznych typov sú takisto rôznych typov. Bez pretypovania sa nedá medzi nimi priraďovať.

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

p1 = p2;   // korektné priradenie
p3 = p1;   // chyba

Operátor & (adresa)

• Adresu premennej vieme zistiť operátorom &
• Tú potom môžeme priradiť do premennej typu smerník

int n = 12345;
int *p;
p = &n;

Premenná p teraz ukazuje na miesto, kde je uložená celočíselná premenná n.

• Operátor & možno aplikovať aj na prvky poľa
• Operátor & nemožno aplikovať na konštanty ani na výrazy

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

p = &n;     // korektné priradenie
p = &a[2];  // korektné priradenie
p = &(n+1); // chyba (výraz nemá adresu)
p = &42;    // chyba (konštanta 42 nemá adresu)

Operátor * (dereferencia, dáta na adrese)

• Ak p je smerník, pomocou *p môžeme pristúpiť k údajom na adrese reprezentovanej smerníkom p.
• Tieto údaje potom možno aj meniť

int n = 12345;
int *p;       

p = &n;              // smerník p ukazuje na adresu premennej n
cout << *p << endl;  // vypíše hodnotu z adresy p, t.j. 12345
*p = 9;              // hodnota na adrese p sa zmení na 9
cout << n << endl;   // vypíše hodnotu premennej n, t.j. 9
(*p)++;              // hodnota na adrese p sa zmení na 10
cout << n << endl;   // vypíše hodnotu premennej n, t.j. 10
n = 42;
cout << *p << endl;  // vypíše hodnotu na adrese p, t.j. 42

Riadok int *p; môžeme čítať takto:

• ak vezmeme smerník p a aplikujeme na neho operátor *, získame hodnotu typu int

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.

Pozor, ak do premennej typu smerník nič nepriradíme, má nedefinovanú hodnotu, ukazuje na náhodné miesto v pamäti, alebo niekde mimo.

Smerník ako parameter funkcie

Namiesto odovzdávania parametrov referenciou ich môžeme odovzdať pomocou smerníka. Tu je napríklad smerníková verzia funkcie swap, ktorá vymieňa hodnoty dvoch premenných.

#include <iostream>
using namespace std;

void swap(int *px, int *py) {  // parametre sú smerníky
    // hodnotu z adresy px uložíme do tmp:
    int tmp = *px;
    // na adresu px uložíme hodnotu z adresy py:
    *px = *py;
    // na adresu py uložíme tmp:
    *py = tmp;
}

int main() {
    int x, y;
    cout << "Zadaj x,y: ";
    cin >> x >> y;
    // ako parametre pošleme adresy premenných x,y
    swap(&x, &y);                                  
    cout << "x = " << x 
         << ", y = " << y << endl;
}

Knižničné funkcie v C často používajú predávanie parametrov referenciou.

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;    
}