Oznamy

  • Dnes nová téma: smerníky a práca s pamäťou.
  • Dnes aj zajtra na cvičeniach práca na počítači s rozcvičkou. Dnešná rozcvička bude z dnešnej prednášky.
  • Prednáška budúci pondelok 16.11. bude mimoriadne v učebni M-IV (v F2 sa koná vedecká konferencia).

Nezabudnite

  • Druhý miniprojekt odovzdávajte do štvrtka 19.11. 22:00.
  • Druhý semestrálny test bude v pondelok 7.12. počas cvičení.

Ukazovateľ, smerník, pointer

  • Pamäť v počítači je rozdelená na dieliky, napr. bajty.
  • Každá premenná zaberá niekoľko takýchto dielikov.
  • Každý dielik má adresu (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 24 uložená premenná x typu int, ktorej hodnota je 17.
  • Na adrese 40 je uložený smerník p, ktorého hodnota je 24.
    • Hovoríme, že smerník p ukazuje na premennú x, zjednodušene to budeme kresliť ako šípku, viď spodok obrázku.
    • Väčšinou nás nezaujíma, aké sú presné hodnoty adries, chceme si ale vedieť nakresliť podobný obrázok so šípkami.
Pamäť

Takúto situáciu (len s inými adresami) vyrobíme príkazmi

int x = 17;   // vytvorenie a inicializácia premennej x
int *p;       // vytvorenie premennej p, ktorá bude smerník na int
p = & x;      // & x vráti adresu premennej x, tú uložíme do premennej p

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 môžeme aj meniť.
  • Ak máme x a p ako vyššie, t.j. p = &x, tak ďalej v programe *p aj x sú mená pre ten istý dielik pamäte.
int x = 17;
int *p = &x;        // p ukazuje na adresu premennej x
printf("%d\n", *p); // vypíše hodnotu z adresy p, t.j. 17
*p = 9;             // hodnota na adrese p sa zmení na 9
printf("%d\n", x); // vypíše hodnotu premennej x, t.j. 9
(*p)++;             // hodnota na adrese p sa zmení na 10
printf("%d\n", x);  // vypíše hodnotu premennej x, t.j. 10
x = 42;
printf("%d\n", *p);  // vypíše hodnotu na adrese p, t.j. 42

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 stdlib.h alebo stdio.h.
  • 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

Ak chceme, aby funkcia mohla meniť hodnotu premennej, musíme jej adresu odovzdať ako parameter. Nižšie máme napríklad funkciu swap, ktorá dostane smerníky na dve premenné a vymení ich hodnoty.

#include <stdio.h>

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(void) {
    int x, y;
    printf("Zadaj x,y: ");
    scanf("%d %d", &x, &y);
    // ako parametre pošleme adresy premenných x,y
    swap(&x, &y);
    printf("x = %d, y = %d\n", x, y);
}

Doteraz sme používali funkciu swap, ktorá vymenila dva prvky toho istého poľa na zadaných indexoch. Teraz sme napísali funkciu, ktorá vymení hodnoty dvoch premenných typu int, ktoré nemusia byť prvkami toho istého poľa.

Smerníky sme už použili pri volaní funkcie scanf. Napr. scanf("%d", &x); odovzdá funkcii scanf adresu premennej x, aby tam mohla uložiť načítanú hodnotu.

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 nultý prvok poľa a
printf("%d\n", a[1]); // vypíše 20
printf("%d\n", p[1]); // vypíše 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;
printf("%d\n", p[1]); // ??? pristupuje do pamäte za premennou x
                      // môže to mať nepríjemné dôsledky

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
p = a;        // ok
a = b;        // nedá sa
a = p;        // nedá sa

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

#include <stdio.h>

void vypisPole(int a[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

void vypisPole2(int *a, int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

int main(void) {
    int a[3] = {10, 20, 30};
    int *b = a;
    
    //štyrikrát vypíšeme to isté
    vypisPole(a, 3); 
    vypisPole(b, 3);
    vypisPole2(a, 3);
    vypisPole2(b, 3);
}

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 funkcia malloc z knižnice stdlib.h.
  • Pamäť sa vyhradí v oblasti zvanej halda (heap).
  • Veľkosť potrebnej pamäte spočítame pomocou sizeof(typ). Napríklad malloc(sizeof(int)) alokuje pamäť veľkosti potrebnej pre premennú typu int.
  • Keď už pamäť nepotrebujeme, uvoľníme ju príkazom free.
  • Uvoľnená pamäť môže byť znovu použitá pri ďalších volaniach malloc.
  • Ak sa pamäť nepodarí alokovať, malloc vráti hodnotu NULL.

Alokácia pamäte na jednu premennú

int *p;

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

// do alokovanej pamäte sa uloží hodnota 50  
*p = 50;
printf("%d\n", *p);  // výpis 50

free(p);      // uvoľnenie alokovanej pamäte

Alokácia pamäte pre pole

int *p; 

// malloc vyhradí úsek pamäte pre pole 5 hodnôt typu int
p = malloc(sizeof(int) * 5);

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

free(p);     // uvoľnenie alokovanej pamäte

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

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    printf("Zadaj pocet cisel: ");
    int N;
    scanf("%d", &N);
    int *a = malloc(sizeof(int) * N);

    printf("Zadavaj %d cisel:\n", N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &a[i]);
    }
    printf("Tu su cisla odzadu:\n");
    for (int i = N - 1; i >= 0; i--) {
        printf("%d ", a[i]);
    }
    printf("\n");

    free(a);
}

Poznámka:

  • V našich programoch sme vytvárali polia, ktorých veľkosť bola konštanta #define NMAX 100 a potom int a[NMAX];
  • Niektoré kompilátory dovolia vytvoriť aj pole, ktorého veľkosť sa zistí počas behu programu int N; scanf("%d", &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 malloc vždy môžeme použiť veľkosť, ktorá sa zistila až počas behu int N; scanf("%d", &N); int *a = malloc(sizeof(int) * N);
    • Alokovanie má aj ďalšie výhody, takto vytvorené pole sa napríklad dá vrátiť ako výsledok funkcie.

Aplikácia smerníkov: dynamické polia

V praxi často narazíme na nasledujúci problém: chceme zo vstupu načítať do poľa nejaké údaje, ale vopred nevieme, koľko ich bude a teda aké veľké pole potrebujeme vytvoriť.

  • Doteraz sme to riešili konštantou NMAX ohraničujúcou maximálnu povolenú veľkosť vstupu, ale to má problémy:
    • Ak je vstup väčší ako NMAX, nevieme ho spracovať, aj ak by kapacity počítača postačovali.
    • Ak je vstup oveľa menší ako NMAX, zbytočne zaberáme pamäť veľkým poľom, ktorého veľká časť je nevyužitá.

V programe nižšie budeme načítavať postupnosť celých čísel až po koniec súboru a tieto čísla chceme uložiť do poľa na ďalšie spracovanie. Používateľ nám vopred nezadá počet prvkov.

Riešením je postupne alokovať väčšie a väčšie polia podľa potreby.

  • Začneme s malým poľom (napr. veľkosti 2).
  • Vždy keď sa pole zaplní, alokujeme nové pole dvojnásobnej veľkosti, prvky do neho skopírujeme a staré pole odalokujeme.
  • Presúvanie prvkov dlho trvá, preto pole vždy zdvojnásobíme, aby sme nemuseli presúvať často.
  • Dá sa dokázať, že pri načítaní n prvkov robíme spolu najviac 2n presunov jednotlivých prvkov.

Takáto verzia poľa, ktorá rastie podľa potreby, sa nazýva dynamické pole.

  • V štandardných C++ knižniciach je definovaná dátová štruktúra vector, ktorá sa správa podobne (uvidíme o týždeň).
  • My teraz implementujeme zjednodušenú verziu tejto štruktúry priamo spolu s načítaním.

Prvá verzia: presúvanie prvkov cyklom

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

int *reallocate(int *a, int length, int newSize) {
    /* Dostane pole a obsahujúce length prvkov.
     * Vytvorí nove pole veľkosti newSize,
     * prekopíruje doňho všetky prvky z a,
     * staré pole odalokuje a nové vráti. */

    assert(length <= newSize);

    // alokujeme nové pole
    int *newA = malloc(sizeof(int) * newSize);
    // prekopírujeme staré pole do nového
    for (int i = 0; i < length; i++) {
        newA[i] = a[i];
    }

    free(a);     // uvoľníme staré pole
    return newA; // vrátime nové pole
}

int *readNumbers(FILE *f, int *length) {
    /* Načíta zo vstupu *f postupnosť celých čísel
     * ukončenú koncom vstupu.
     * Vráti pole týchto čísel a do *length uloží ich počet. */

    int size = 2; // veľkosť alokovaného poľa
    *length = 0;  // počet prvkov pridaných do poľa
    int *a;       // smerník na prvý prvok poľa
    a = malloc(sizeof(int) * size);

    // načítavame čísla zo vstupu, kým je čo načítať
    while (true) {
        // načítame jedno číslo
        int x;
        int ret = fscanf(f, "%d ", &x);
        // ak sme narazili na koniec vstupu, skončíme
        if (ret == EOF) {
            break;
        }
        // ak číslo x nie je kam uložiť, zväčšíme pole
        if (*length == size) {
            size = size * 2;
            a = reallocate(a, *length, size);
        }
        // pridáme číslo x do poľa
        assert(*length < size);
        a[*length] = x;
        (*length)++;
    }

    return a; // vrátime pole
}

int main(void) {
    int n;        // počet prvkov pridaných do poľa
    int *a;       // smerník na začiatok poľa

    a = readNumbers(stdin, &n);

    // vypíšeme prvky poľa od konca
    for (int i = n - 1; i >= 0; i--) {
        printf(" %d", a[i]);
    }
    printf("\n");

    free(a);  // uvoľníme pamäť
}

Všimnime si, čo sa v tomto programe dialo s premennou, v ktorej je počet prvkov poľa:

int *reallocate(int *a, int length, int newSize) {
   // length obsahuje kópiu hodnoty z premennej n v main
   // ak by sme length menili, n sa nemení
}

int *readNumbers(FILE *f, int *length) {
    *length = 0;  // premennú n z main nastaví na 0
    // ...

    // funkcii reallocate pošle hodnotu, nie smerník
    // lebo tam nebudeme length meniť
    a = reallocate(a, *length, size);
    // ...
    (*length)++;  // zvýši premennú n z main
}

int main(void) {
    int n;  // tu sa vytvorí lokálna premenná n
    int *a;
    a = readNumbers(stdin, &n);  // pošleme smerník na n
    for (int i = n - 1; i >= 0; i--) {
      // ...
    }
    // ...
}

Druhá verzia: knižničná funkcia realloc

Naša funkcia reallocate sa dá nahradiť funkciou realloc z knižnice stdlib.h. Táto funkcia potrebuje smerník na pole a novú veľkosť a vráti smerník na nové pole. Automaticky spraví kopírovanie obsahu starého poľa aj jeho dealokáciu. Dokonca ak je to možné, zmení veľkosť poľa na pôvodnom mieste v pamäti, takže kopírovanie ani nie je potrebné.

Kľúčová zmena je riadok a = realloc(a, sizeof(int) * size);

int *readNumbers(FILE *f, int *length) {
    /* Načíta zo vstupu *f postupnosť celých čísel
     * ukončenú koncom vstupu.
     * Vráti pole týchto čísel a do *length uloží ich počet. */

    int size = 2; // veľkosť alokovaného poľa
    *length = 0;  // počet prvkov pridaných do poľa
    int *a;       // smerník na prvý prvok poľa
    a = malloc(sizeof(int) * size);

    // načítavame čísla zo vstupu, kým je čo načítať
    while (true) {
        // načítame jedno číslo
        int x;
        int ret = fscanf(f, "%d ", &x);
        // ak sme narazili na koniec vstupu, skončíme
        if (ret == EOF) {
            break;
        }
        // ak číslo x nie je kam uložiť, zväčšíme pole
        if (*length == size) {
            size = size * 2;
            a = realloc(a, sizeof(int) * size);
        }
        // pridáme číslo x do poľa
        assert(*length < size);
        a[*length] = x;
        (*length)++;
    }

    return a; // vrátime pole
}

Ďalšie detaily používania smerníkov

Typy smerníkov

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)

  • Videli sme, že adresu premennej vieme zistiť operátorom &
  • Tú potom môžeme priradiť do premennej typu smerník
int x = 17;
int *p;
p = &x;

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

  • Operátor & možno aplikovať aj na prvky poľa (alebo položky struct-u)
  • Operátor & nemožno aplikovať na konštanty ani na výrazy
int x = 0;
int a[5] = {1, 2, 3, 4, 5};
int *p;

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

Ladenie programov so smerníkmi

  • Smerníky (a polia) 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

Zhrnutie

  • Smerník, ukazovateľ, pointer je premenná, v ktorej je uložená adresa nejakého pamäťového miesta.
  • Typ smerníku určuje, na aký typ premennej by mal ukazovať, napr. int *p.
  • Do smerníku môžeme priradiť NULL, adresu nejakej premennej &i, novoalokovanú pamäť pomocou malloc, iný smerník toho istého typu.
  • Ku políčku, na ktoré ukazuje smerník p, pristupujeme pomocou *p.
  • Pole je vlastne smerník na svoj nultý prvok.
  • Pole určitej dĺžky (ktorá je známa až počas behu) alokujeme pomocou malloc(sizeof(int) * N).
  • Pamäť alokovanú cez malloc by sme mali odalokovať pomocou free.
  • Pri práci so smerníkmi ľahko spravíme chybu, pomôcť nám môže napríklad valgrind.
  • Nabudúce uvidíme: dvojrozmerné polia, smerník na smerník int **.