Programovanie (1) v C/C++
1-INF-127, ZS 2024/25

Úvod · Pravidlá · Prednášky · Softvér · Testovač
· Kontaktujte nás pomocou e-mailovej adresy E-prg.png (bude odpovedať ten z nás, kto má príslušnú otázku na starosti alebo kto má práve čas).
· Prosíme študentov, aby si pravidelne čítali e-maily na @uniba.sk adrese alebo aby si tieto emaily preposielali na adresu, ktorú pravidelne čítajú.


Prednáška 12: Rozdiel medzi revíziami

Z Programovanie
Skočit na navigaci Skočit na vyhledávání
d (C nemá referencie.)
 
(8 medziľahlých úprav od rovnakého používateľa nie je zobrazených.)
Riadok 1: Riadok 1:
 
== Oznamy ==
 
== Oznamy ==
  
* DÚ2 zverejnená, odovzdávajte do utorka 14.11. 22:00.
+
* DÚ2 zverejnená, odovzdávajte do utorka 19.11. 22:00.
 
* Dnes nová téma: smerníky a práca s pamäťou.
 
* Dnes nová téma: smerníky a práca s pamäťou.
* Zajtra cvičenia, rozcvička z dnešného učiva, iba dva príklady.
+
* Zajtra na cvičeniach rozcvička na papieri a ďalšie tri príklady.
** Odporúčame získať na cvičeniach aspoň 2 body. Ak ich nezískate, budú pre vás povinné cvičenia v piatok budúci týždeň.
+
* Piatkové cvičenia sú dobrovoľné.
* Tento týždeň je v stredu sviatok, štvrtok a piatok voľno.
 
** Odporúčame využiť voľnejší týždeň na prácu na domácej úlohe.
 
* Budúci utorok 7.11. na cvičeniach bude krátky test podobne ako na prednáške 4.10.
 
  
 
== Ukazovateľ, smerník, pointer==
 
== Ukazovateľ, smerník, pointer==
Riadok 27: Riadok 24:
 
<pre>
 
<pre>
 
int x = 17;  // vytvorenie a inicializácia premennej x
 
int x = 17;  // vytvorenie a inicializácia premennej x
int *p;       // vytvorenie premennej p, ktorá bude smerník na int
+
int * p;     // vytvorenie premennej p, ktorá bude smerník na int
p = &x;       // &n vráti adresu premennej x, tú uložíme do premennej p
+
p = & x;     // & x vráti adresu premennej x, tú uložíme do premennej p
 
</pre>
 
</pre>
  
Riadok 34: Riadok 31:
  
 
* Ak <tt>p</tt> je smerník, pomocou <tt>*p</tt> môžeme pristúpiť k údajom na adrese reprezentovanej smerníkom <tt>p</tt>.  
 
* Ak <tt>p</tt> je smerník, pomocou <tt>*p</tt> môžeme pristúpiť k údajom na adrese reprezentovanej smerníkom <tt>p</tt>.  
* Tieto údaje potom možno aj meniť
+
* Tieto údaje potom možno aj meniť.
 
* Ak máme <tt>int x = 17; int *p = &x;</tt>, tak ďalej v programe <tt>*p</tt> aj <tt>x</tt> sú mená pre ten istý dielik pamäte.
 
* Ak máme <tt>int x = 17; int *p = &x;</tt>, tak ďalej v programe <tt>*p</tt> aj <tt>x</tt> sú mená pre ten istý dielik pamäte.
  
 
<syntaxhighlight lang="C++">
 
<syntaxhighlight lang="C++">
 
int x = 17;
 
int x = 17;
int *p = &x;        // p ukazuje na adresu premennej x
+
int * p = &x;        // p ukazuje na adresu premennej x
 
cout << *p << endl; // vypíše hodnotu z adresy p, t.j. 17
 
cout << *p << endl; // vypíše hodnotu z adresy p, t.j. 17
 
*p = 9;            // hodnota na adrese p sa zmení na 9
 
*p = 9;            // hodnota na adrese p sa zmení na 9
Riadok 65: Riadok 62:
 
using namespace std;
 
using namespace std;
  
void swap(int *px, int *py) {  // parametre sú smerníky
+
void swap(int * px, int * py) {  // parametre sú smerníky
 
     // hodnotu z adresy px uložíme do tmp:
 
     // hodnotu z adresy px uložíme do tmp:
 
     int tmp = *px;
 
     int tmp = *px;
Riadok 96: Riadok 93:
 
<syntaxhighlight lang="C++">
 
<syntaxhighlight lang="C++">
 
int a[4] = {10, 20, 30, 40};
 
int a[4] = {10, 20, 30, 40};
int *p;
+
int * p;
 
p = a;        // p ukazuje na nulty prvok pola a
 
p = a;        // p ukazuje na nulty prvok pola a
 
cout << a[1]; // vypise 20
 
cout << a[1]; // vypise 20
Riadok 108: Riadok 105:
 
<syntaxhighlight lang="C++">
 
<syntaxhighlight lang="C++">
 
int x = 10;
 
int x = 10;
int *p;
+
int * p;
 
p = &x;
 
p = &x;
 
cout << p[1]; // ??? pristupuje do pamäte za premennou x
 
cout << p[1]; // ??? pristupuje do pamäte za premennou x
Riadok 114: Riadok 111:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Pozor, polia sú konštantné smerníky, nemožno ich zmeniť
+
Polia sú konštantné smerníky, nemožno ich zmeniť.
 
<syntaxhighlight lang="C++">
 
<syntaxhighlight lang="C++">
 
int a[4] = {10, 20, 30, 40};
 
int a[4] = {10, 20, 30, 40};
 
int b[3] = {1, 2, 3};
 
int b[3] = {1, 2, 3};
int *p = b;  // ok
+
int * p = b;  // ok
a = b;       // nedá sa
+
p = a;        // ok
a = p;       // nedá sa
+
a = b;       // nedá sa
 +
a = p;       // nedá sa
 
</syntaxhighlight>
 
</syntaxhighlight>
  
Riadok 136: Riadok 134:
 
}
 
}
  
void vypisPole2(int *a, int n) {
+
void vypisPole2(int * a, int n) {
 
     for (int i = 0; i < n; i++) {
 
     for (int i = 0; i < n; i++) {
 
         cout << a[i] << " ";
 
         cout << a[i] << " ";
Riadok 171: Riadok 169:
  
 
<syntaxhighlight lang="C++">
 
<syntaxhighlight lang="C++">
int *p;   
+
int * p;   
  
 
// new vyhradí úsek pamäte pre jednu hodnotu typu int
 
// new vyhradí úsek pamäte pre jednu hodnotu typu int
Riadok 187: Riadok 185:
  
 
<syntaxhighlight lang="C++">
 
<syntaxhighlight lang="C++">
int *p;  
+
int * p;  
  
// new vyhradí úsek pamäte pre poli 5 hodnôt typu int
+
// new vyhradí úsek pamäte pre pole 5 hodnôt typu int
 
p = new int[5];
 
p = new int[5];
  
 
// premenná p sa dá použiť ako pole dĺžky 5
 
// premenná p sa dá použiť ako pole dĺžky 5
for(int i=0; i<5; i++) {
+
for(int i = 0; i < 5; i++) {
 
   p[i] = i;
 
   p[i] = i;
 
}   
 
}   
Riadok 204: Riadok 202:
 
* Ak zamieňate <tt>delete[]</tt> a <tt>delete</tt>, správanie programu môže byť nedefinované
 
* Ak zamieňate <tt>delete[]</tt> a <tt>delete</tt>, správanie programu môže byť nedefinované
 
<pre>
 
<pre>
int *p;
+
int * p;
  
 
p = new int;
 
p = new int;
Riadok 225: Riadok 223:
 
     int N;
 
     int N;
 
     cin >> N;
 
     cin >> N;
     int *a = new int[N];
+
     int * a = new int[N];
 
      
 
      
 
     cout << "Zadavaj " << N << " cisel:" << end;
 
     cout << "Zadavaj " << N << " cisel:" << end;
Riadok 244: Riadok 242:
 
* V našich programoch sme vytvárali polia, ktorých veľkosť bola konštanta <tt>const int maxN = 100; int a[maxN];</tt>
 
* V našich programoch sme vytvárali polia, ktorých veľkosť bola konštanta <tt>const int maxN = 100; int a[maxN];</tt>
 
* Niektoré kompilátory dovolia vytvoriť aj pole, ktorého veľkosť sa zistí počas behu programu <tt>int N; cin >> N; int a[N];</tt>
 
* Niektoré kompilátory dovolia vytvoriť aj pole, ktorého veľkosť sa zistí počas behu programu <tt>int N; cin >> N; int a[N];</tt>
** 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á
+
** 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 <tt>new</tt> vždy môžeme použiť veľkosť, ktorá sa zistila až počas behu <tt>int N; cin >> N; int *a = new int[N];</tt>
 
* Pri alokovaní poľa pomocou <tt>new</tt> vždy môžeme použiť veľkosť, ktorá sa zistila až počas behu <tt>int N; cin >> N; int *a = new int[N];</tt>
** Alokovanie má aj ďalšie výhody, takto vytvorené pole sa napríklad dá vrátiť ako výsledok funkcie
+
** 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 ==
 
== Aplikácia smerníkov: dynamické polia ==
Riadok 270: Riadok 268:
  
 
Dynamické pole celých čísel budeme reprezentovať ako štruktúru typu <tt>dynArray</tt>, ktorá bude pozostávať z nasledujúcich troch zložiek:
 
Dynamické pole celých čísel budeme reprezentovať ako štruktúru typu <tt>dynArray</tt>, ktorá bude pozostávať z nasledujúcich troch zložiek:
* Zo smerníku <tt>p</tt> ukazujúceho na nultý prvok poľa (čiže vlastne pole samotné).
+
* Zo smerníku <tt>items</tt> ukazujúceho na nultý prvok poľa (čiže vlastne pole samotné).
 
* Z celočíselnej premennej <tt>length</tt>, v ktorej bude počet prvkov, ktoré sú aktuálne v poli.
 
* Z celočíselnej premennej <tt>length</tt>, v ktorej bude počet prvkov, ktoré sú aktuálne v poli.
* Z celočíselnej premennej <tt>size</tt>, v ktorej bude veľkosť alokovanej pamäte pre pole <tt>p</tt>.
+
* Z celočíselnej premennej <tt>size</tt>, v ktorej bude veľkosť alokovanej pamäte pre pole <tt>items</tt>.
 
Štruktúra <tt>dynArray</tt> teda v sebe združuje pole aj jeho dĺžku, stačí posielať jeden parameter.
 
Štruktúra <tt>dynArray</tt> teda v sebe združuje pole aj jeho dĺžku, stačí posielať jeden parameter.
  
Riadok 330: Riadok 328:
 
/* Dynamicke pole celych cisel */
 
/* Dynamicke pole celych cisel */
 
struct dynArray {
 
struct dynArray {
     int *p;         // smernik na prvy prvok pola
+
     int * items;   // smerník na prvý prvok poľa
     int size;      // velkost alokovaneho pola
+
     int size;      // veľkosť alokovaného poľa
     int length;    // pocet prvkov pridanych do pola
+
     int length;    // počet prvkov pridaných do poľa
 
};
 
};
  
void init(dynArray &a) {
+
void init(dynArray & a) {
     /* Inicializuje dynamicke pole velkosti 2 */
+
     /* Inicializuje dynamické pole veľkosti 2 */
 
     a.size = 2;
 
     a.size = 2;
 
     a.length = 0;
 
     a.length = 0;
     a.p = new int[a.size];
+
     a.items = new int[a.size];
 
}
 
}
  
void add(dynArray &a, int x) {
+
void reallocate(dynArray & a, int newSize) {
 +
    /* Pomocna funkcia, ktora sa pouziva vo funkcii add.
 +
    * Zmeni velkost pola zo size na newSize,
 +
    * prekopiruje vsetky prvky do noveho pola. */
 +
 
 +
    assert(a.length <= newSize);
 +
    a.size = newSize;
 +
    // alokujeme nove pole
 +
    int * newItems = new int[a.size];
 +
    // prekopirujeme stare pole do noveho
 +
    for (int i = 0; i < a.length; i++) {
 +
        newItems[i] = a.items[i];
 +
    }
 +
    // uvolnime stare pole
 +
    delete[] a.items;
 +
    a.items = newItems;  // a.items teraz ukazuje na nove pole
 +
}
 +
 
 +
void add(dynArray & a, int x) {
 
     /* Prida na koniec dynamickeho pola prvok x
 
     /* Prida na koniec dynamickeho pola prvok x
 
     * a v pripade potreby realokuje pole */
 
     * a v pripade potreby realokuje pole */
Riadok 348: Riadok 364:
 
     // ak uz sa x do pola nevojde
 
     // ak uz sa x do pola nevojde
 
     if (a.length == a.size) {
 
     if (a.length == a.size) {
         // zdvojnasobime velkost
+
         // zdvojnasobime velkost pola items
         a.size *= 2;
+
         reallocate(a, a.size * 2);
        // alokujeme vacsie pole
 
        int *newp = new int[a.size];
 
        // prekopirujeme stare pole do noveho
 
        for (int i = 0; i < a.length; i++) {
 
            newp[i] = a.p[i];         
 
        }
 
        // uvolnime stare pole
 
        delete[] a.p;                 
 
        a.p = newp; // a.p teraz ukazuje na nove pole
 
 
     }
 
     }
 
     // teraz je pole urcite dost velke
 
     // teraz je pole urcite dost velke
 
     // pridame x a zvysime pocet prvkov
 
     // pridame x a zvysime pocet prvkov
     a.p[a.length] = x;
+
     a.items[a.length] = x;
 
     a.length++;
 
     a.length++;
 
}
 
}
  
int get(dynArray &a, int index) {
+
int get(dynArray & a, int index) {
     /* Vrati prvok dynamickeho pola a na pozicii index  
+
     /* Vrati prvok dynamickeho pola a na pozicii index
 
     * (ak ide o korektnu poziciu)*/
 
     * (ak ide o korektnu poziciu)*/
 
     assert(index >= 0 && index <= a.length - 1);
 
     assert(index >= 0 && index <= a.length - 1);
     return a.p[index];
+
     return a.items[index];
}  
+
}
  
void set(dynArray &a, int index, int x) {
+
void set(dynArray & a, int index, int x) {
     /* Ulozi na poziciu index dynamickeho pola a hodnotu x  
+
     /* Ulozi na poziciu index dynamickeho pola a hodnotu x
 
     * (ak ide o korektnu poziciu)*/
 
     * (ak ide o korektnu poziciu)*/
 
     assert(index >= 0 && index <= a.length - 1);
 
     assert(index >= 0 && index <= a.length - 1);
     a.p[index] = x;
+
     a.items[index] = x;
 
}
 
}
  
int length(dynArray &a) {
+
int length(dynArray & a) {
 
     /* Vrati pocet prvkov v dynamickom poli a */
 
     /* Vrati pocet prvkov v dynamickom poli a */
 
     return a.length;
 
     return a.length;
 
}
 
}
  
void destroy(dynArray &a) {
+
void destroy(dynArray & a) {
 
     /* Uvolni alokovanu pamat pre pole a */
 
     /* Uvolni alokovanu pamat pre pole a */
     delete[] a.p;
+
     delete[] a.items;
 
}
 
}
  
Riadok 393: Riadok 400:
 
     dynArray a;
 
     dynArray a;
 
     init(a);  // inicializuje a
 
     init(a);  // inicializuje a
   
+
 
 
     int x;
 
     int x;
 
     cin >> x;
 
     cin >> x;
 
     // pridavame prvky, kym su nezaporne
 
     // pridavame prvky, kym su nezaporne
     while (x >= 0) {                
+
     while (x >= 0) {
         add(a, x);    
+
         add(a, x);
         cin >> x;  
+
         cin >> x;
 
     }
 
     }
 
     // vypise prvky pola od konca
 
     // vypise prvky pola od konca
 
     for (int i = length(a) - 1; i >= 0; i--) {
 
     for (int i = length(a) - 1; i >= 0; i--) {
         cout << get(a, i) << " ";    
+
         cout << get(a, i) << " ";
 
     }
 
     }
 
     cout << endl;
 
     cout << endl;
  
 
     // ukazka pouzitia get a set
 
     // ukazka pouzitia get a set
     set(a, 0, 42);  
+
     set(a, 0, 42);
     cout << get(a, 0) << endl;
+
     cout << get(a, 0) << endl;
  
 
     destroy(a);  // uvolni pamat
 
     destroy(a);  // uvolni pamat
Riadok 421: Riadok 428:
 
Smerník ukazujúci na premennú typu <tt>T</tt> sa definuje ako <tt>T *p</tt>, napríklad:
 
Smerník ukazujúci na premennú typu <tt>T</tt> sa definuje ako <tt>T *p</tt>, napríklad:
 
<syntaxhighlight lang="C++">
 
<syntaxhighlight lang="C++">
int    *p1;  // smerník p1 na int
+
int    * p1;  // smerník p1 na int
char  *p2;  // smerník p2 na char
+
char  * p2;  // smerník p2 na char
double *p3;  // smerník p3 na double
+
double * p3;  // smerník p3 na double
 
 
 
// atď
 
// atď
 
</syntaxhighlight>
 
</syntaxhighlight>
Riadok 430: Riadok 436:
 
Smerníky ukazujúce na premenné rôznych typov sú takisto rôznych typov. Bez pretypovania sa nedá medzi nimi priraďovať.
 
Smerníky ukazujúce na premenné rôznych typov sú takisto rôznych typov. Bez pretypovania sa nedá medzi nimi priraďovať.
 
<syntaxhighlight lang="C++">
 
<syntaxhighlight lang="C++">
int *p1;
+
int * p1;
int *p2;
+
int * p2;
double *p3;
+
double * p3;
  
 
p1 = p2;  // korektné priradenie
 
p1 = p2;  // korektné priradenie
 
p3 = p1;  // chyba
 
p3 = p1;  // chyba
 
</syntaxhighlight>
 
</syntaxhighlight>
 
  
 
=== Operátor <tt>&</tt> (adresa) ===
 
=== Operátor <tt>&</tt> (adresa) ===
Riadok 446: Riadok 451:
 
<syntaxhighlight lang="C++">
 
<syntaxhighlight lang="C++">
 
int x = 17;
 
int x = 17;
int *p;
+
int * p;
 
p = &x;
 
p = &x;
 
</syntaxhighlight>
 
</syntaxhighlight>
Riadok 458: Riadok 463:
 
int x = 0;
 
int x = 0;
 
int a[5] = {1, 2, 3, 4, 5};
 
int a[5] = {1, 2, 3, 4, 5};
int *p;
+
int * p;
  
 
p = &x;      // korektné priradenie
 
p = &x;      // korektné priradenie
Riadok 475: Riadok 480:
  
 
==Zhrnutie==
 
==Zhrnutie==
* Smerník, ukazovateľ, pointer je premenná, v ktorej je uložená adresa nejakého pamäťového miesta
+
* 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. <tt>int *p</tt>
+
* Typ smerníku určuje, na aký typ premennej by mal ukazovať, napr. <tt>int *p</tt>.
* Do smerníku môžeme priradiť <tt>NULL</tt>, adresu nejakej premennej (<tt>&i</tt>), novoalokovanú pamäť pomocou <tt>new</tt>, iný smerník toho istého typu
+
* Do smerníku môžeme priradiť <tt>NULL</tt>, adresu nejakej premennej <tt>&i</tt>, novoalokovanú pamäť pomocou <tt>new</tt>, iný smerník toho istého typu.
* Ku políčku, na ktoré ukazuje smerník ''p'', pristupujeme pomocou (<tt>*p</tt>)
+
* Ku políčku, na ktoré ukazuje smerník ''p'', pristupujeme pomocou <tt>*p</tt>.
* Pole je vlastne smerník na svoj prvý (nultý) prvok
+
* Pole je vlastne smerník na svoj prvý (nultý) prvok.
* Pole určitej dĺžky (ktorá je známa až počas behu) alokujeme pomocou <tt>new typ[pocet]</tt>
+
* Pole určitej dĺžky (ktorá je známa až počas behu) alokujeme pomocou <tt>new typ[pocet]</tt>.
* Pamäť alokovanú cez <tt>new</tt> by sme mali odalokovať pomocou <tt>delete</tt> alebo <tt>delete[]</tt> (podľa toho, či to bolo pole)
+
* Pamäť alokovanú cez <tt>new</tt> by sme mali odalokovať pomocou <tt>delete</tt> alebo <tt>delete[]</tt> (podľa toho, či to bolo pole).
* Pri práci so smerníkmi ľahko spravíme chybu, pomôcť nám môže napríklad valgrind
+
* 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 <tt>int **</tt>.

Aktuálna revízia z 13:23, 5. november 2024

Oznamy

  • DÚ2 zverejnená, odovzdávajte do utorka 19.11. 22:00.
  • Dnes nová téma: smerníky a práca s pamäťou.
  • Zajtra na cvičeniach rozcvička na papieri a ďalšie tri príklady.
  • Piatkové cvičenia sú dobrovoľné.

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.

Memory-c.png


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 možno aj meniť.
  • Ak máme int x = 17; int *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
cout << *p << endl; // vypíše hodnotu z adresy p, t.j. 17
*p = 9;             // hodnota na adrese p sa zmení na 9
cout << x << endl;  // vypíše hodnotu premennej x, t.j. 9
(*p)++;             // hodnota na adrese p sa zmení na 10
cout << x << endl;  // vypíše hodnotu premennej x, t.j. 10
x = 42;
cout << *p << endl;  // 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 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ú odovzdávanie parametrov cez smerníky.

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

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 <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 pole 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é 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 MaxN ohraničujúcou maximálnu povolenú veľkosť vstupu, ale to má problémy:
    • Ak je vstup väčší ako MaxN, nevieme ho spracovať, aj ak by inak kapacity počítača postačovali
    • Ak je vstup oveľa menší ako MaxN, zbytočne zaberáme pamäť veľkým poľom, ktorého veľká časť je nevyužitá
  • Pre jednoduchosť budeme uvažovať na vstupe postupnosť nezáporných čísel ukončenú -1, napr. 7 3 0 4 3 -1
    • Do poľa chceme uložiť všetko okrem poslednej -1
    • 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
  • Spolu pri načítaní n prvkov robíme 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.
  • My teraz implementujeme zjednodušenú verziu tejto štruktúry.
  • Pre jednoduchosť napíšeme iba verziu dynamického poľa pre typ int. Analogicky by sme postupovali 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 items ukazujúceho na nultý prvok poľa (čiže vlastne pole samotné).
  • Z celočíselnej premennej length, v ktorej bude počet prvkov, ktoré sú aktuálne v poli.
  • Z celočíselnej premennej size, v ktorej bude veľkosť alokovanej pamäte pre pole items.

Štruktúra dynArray teda v sebe združuje pole aj jeho dĺžku, stačí posielať jeden parameter.

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

  • Funkcia void init(dynArray &a) inicializuje dynamické pole a, v ktorom je nula prvkov. Funkcia ale alokuje nejaký malý objem pamäte (u nás dva prvky).
  • Funkcia void add(dynArray &a, int x) pridá do dynamického poľa a prvok s hodnotou x, čím počet prvkov vzrastie o jedna. 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 aktuálne uložených v dynamickom poli 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, napríklad na výpis vstupu odzadu.

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

struct dynArray {
// ...
};

// definície funkcií init, add, get, set, length, destroy

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

    // ukazka pouzitia get a set
    set(a, 0, 42);   
    cout << get(a, 0) << endl;  

    destroy(a);  // uvolni pamat
}

Implementácia dynamického poľa

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

/* Dynamicke pole celych cisel */
struct dynArray {
    int * items;    // smerník na prvý prvok poľa
    int size;       // veľkosť alokovaného poľa
    int length;     // počet prvkov pridaných do poľa
};

void init(dynArray & a) {
    /* Inicializuje dynamické pole veľkosti 2 */
    a.size = 2;
    a.length = 0;
    a.items = new int[a.size];
}

void reallocate(dynArray & a, int newSize) {
    /* Pomocna funkcia, ktora sa pouziva vo funkcii add.
     * Zmeni velkost pola zo size na newSize,
     * prekopiruje vsetky prvky do noveho pola. */

    assert(a.length <= newSize);
    a.size = newSize;
    // alokujeme nove pole
    int * newItems = new int[a.size];
    // prekopirujeme stare pole do noveho
    for (int i = 0; i < a.length; i++) {
        newItems[i] = a.items[i];
    }
    // uvolnime stare pole
    delete[] a.items;
    a.items = newItems;  // a.items teraz ukazuje na nove pole
}

void add(dynArray & a, int x) {
    /* Prida na koniec dynamickeho pola prvok x
     * a v pripade potreby realokuje pole */

    // ak uz sa x do pola nevojde
    if (a.length == a.size) {
        // zdvojnasobime velkost pola items
        reallocate(a, a.size * 2);
    }
    // teraz je pole urcite dost velke
    // pridame x a zvysime pocet prvkov
    a.items[a.length] = x;
    a.length++;
}

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.items[index];
}

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

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

void destroy(dynArray & a) {
    /* Uvolni alokovanu pamat pre pole a */
    delete[] a.items;
}

int main() {
    dynArray a;
    init(a);  // inicializuje a

    int x;
    cin >> x;
    // pridavame prvky, kym su nezaporne
    while (x >= 0) {
        add(a, x);
        cin >> x;
    }
    // vypise prvky pola od konca
    for (int i = length(a) - 1; i >= 0; i--) {
        cout << get(a, i) << " ";
    }
    cout << endl;

    // ukazka pouzitia get a set
    set(a, 0, 42);
    cout << get(a, 0) << endl;

    destroy(a);  // uvolni pamat
}

Ď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 new, 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 prvý (nultý) prvok.
  • Pole určitej dĺžky (ktorá je známa až počas behu) alokujeme pomocou new typ[pocet].
  • Pamäť alokovanú cez new by sme mali odalokovať pomocou delete alebo delete[] (podľa toho, či to bolo pole).
  • 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 **.