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.

Smerníky a polia

Smerníky a polia v jazyku C spolu veľmi úzko súvisia.

• Pole je vlastne smerník na nultý prvok.
• Môžeme ho nakopírovať do premennej typu T *.
• Na premenné typu T * môžeme použiť operátor [].

int a[4] = {10, 20, 30, 40};
int *p;
p = a;        // p ukazuje na nulty prvok pola a
cout << a[1]; // vypise 20
cout << p[1]; // vypise 20

• Polia v C pozostávajú z políčok rovnakej veľkosti uložených v pamäti jedno za druhým, veľkosť políčka je daná typom prvku
• Výraz p[i] zoberie adresu uloženú v p, zvýši ju o veľkosť_políčka * i a pozrie sa na príslušnú adresu
• p[0] je teda to isté ako *p
• Pozor, C umožní p[i] použiť aj keď p neukazuje na pole, vtedy pristupuje do pamäte s neznámym obsahom, program môže skončiť s chybou alebo sa správať "záhadne"

int x = 10;
int *p;
p = &x;
cout << p[1]; // ??? pristupuje do pamäte za premennou x
              // môže to mať nepríjemné dôsledky

Pozor, polia sú konštantné smerníky, nemožno ich zmeniť

int a[4] = {10, 20, 30, 40};
int b[3] = {1, 2, 3};
int *p = b;  // ok
a = b;       // nedá sa
a = p;       // nedá sa

Vo funkciách pracujúcich s poliami môžeme namiesto parametra int a[] aj int *a a kód ani použitie funkcie sa nemení.

#include <iostream>
using namespace std;

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

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

int main() {
    const int N  = 4;
    int a[N] = {10, 20, 30, 40};
    int *b = a;
    
    //styrikrat vypiseme to iste
    vypisPole(a, N); 
    vypisPole(b, N);
    vypisPole2(a, N);
    vypisPole2(b, N);
}

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 zásobníku volaní funkcií (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 (heap).
• Keď už pamäť nepotrebujeme, uvoľníme ju príkazom delete.
• Uvoľnená pamäť môže byť znovu použitá pri ďalších volaniach new.

Alokácia pamäte na jednu premennú

int *p;   

// new vyhradí úsek pamäte pre jednu hodnotu typu int
// adresa tohto úseku sa uloží do smerníka p
p = new int;   

// do alokovanej pamäte sa uloží hodnota 50  
*p = 50;
cout << *p << endl;  // výpis 50

delete p;      // uvoľnenie alokovanej pamäte

Alokácia pamäte pre pole

int *p;   

// new vyhradí úsek pamäte pre poli 5 hodnôt typu int
p = new int[5];

// premenná p sa dá použiť ako pole dĺžky 5
for(int i=0; i<5; i++) {
   p[i] = i;
}   

delete[] p;     // uvoľnenie alokovanej pamäte

• Pozor, ak alokujeme pole, pamäť uvoľnujeme cez delete[], nie delete
• Ak zamieňate delete[] a delete, správanie programu môže byť nedefinované

int *p;

p = new int;
// ...
delete p;

p = new int[5];
// ...
delete[] p;

Dynamickú alokáciu polí možno využiť napríklad na vytvorenie poľa, ktorého veľkosť zadá používateľ.

#include <iostream>
using namespace std;

int main(void) {
    cout << "Zadaj pocet cisel: ";
    int N;
    cin >> N;
    int *a = new int[N];
    
    cout << "Zadavaj " << N << " cisel:" << end;
    for (int i = 0; i <= N-1; i++) {
        cin >> a[i];
    }
    cout << "Tu su cisla odzadu:" << endl;
    for (int i = N-1; i >= 0; i--) {
        cout << a[i] << " ";
    }
    cout << endl;

    delete[] a;
}

Poznámka:

• V našich programoch sme vytvárali polia, ktorých veľkosť bola konštanta const int maxN = 100; int a[maxN];
• Niektoré kompilátory dovolia vytvoriť aj pole, ktorého veľkosť sa zistí počas behu programu int N; cin >> N; int a[N];
  • Nefunguje to však vždy, navyše môže byť problém s veľkými poliami, lebo veľkosť zásobníka volaní môže byť obmedzená
• Pri alokovaní poľa pomocou new vždy môžeme použiť veľkosť, ktorá sa zistila až počas behu int N; cin >> N; int *a = new int[N];
  • Alokovanie má aj ďalšie výhody, takto vytvorené pola sa napríklad dá vrátiť ako výsledok funkcie

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

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