Programovanie (2) v Jave
1-INF-166, letný semester 2023/24
Prednáška 12: Rozdiel medzi revíziami
Riadok 6: | Riadok 6: | ||
* Ukazovateľ (resp. smerník alebo pointer) je premenná, ktorej hodnota je adresa iného dieliku pamäte | * Ukazovateľ (resp. smerník alebo pointer) je premenná, ktorej hodnota je adresa iného dieliku pamäte | ||
− | + | * Na obrázku je na adrese <tt>[adresa 2]</tt> uložená premenná typu <tt>int</tt>, ktorej hodnota je 12345. | |
− | + | * Na adrese <tt>[adresa 1]</tt> je uložený smerník, ktorého hodnota je <tt>[adresa 2]</tt>. | |
− | + | ** Hovoríme, že smerník ukazuje na pamäťovú adresu <tt>[adresa 2]</tt>, budeme to kresliť ako šípku. | |
[[Súbor:Pamat5.png]] | [[Súbor:Pamat5.png]] | ||
Riadok 14: | Riadok 14: | ||
=== Definovanie smerníka === | === Definovanie smerníka === | ||
− | V C++ sa smerník ukazujúci na | + | V C++ sa smerník ukazujúci na premennú typu <tt>T</tt> definuje takto: |
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
T *p; | T *p; | ||
Riadok 20: | Riadok 20: | ||
Napríklad teda môžeme písať: | Napríklad teda môžeme písať: | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
− | int *p1; | + | int *p1; // smerník p1 na int |
− | char *p2; // | + | char *p2; // smerník p2 na char |
− | double *p3; // | + | double *p3; // smerník p3 na double |
− | // | + | // atď |
</syntaxhighlight> | </syntaxhighlight> | ||
− | Smerníky ukazujúce na | + | 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; | ||
Riadok 33: | Riadok 33: | ||
double *p3; | double *p3; | ||
− | p1 = p2; // | + | p1 = p2; // korektné priradenie |
− | p3 = p1; // chyba | + | p3 = p1; // chyba |
</syntaxhighlight> | </syntaxhighlight> | ||
− | |||
=== Operátor <tt>&</tt> (adresa) === | === Operátor <tt>&</tt> (adresa) === | ||
− | + | * Adresu nejakej premennej vieme zistiť operátorom & | |
− | + | * Tú potom môžeme priradiť do premennej typu smerník | |
− | + | * Ak do premennej typu smerník nič nepriradíme, má nedefinovanú hodnotu, ukazuje na náhodné miesto v pamäti, alebo niekde mimo | |
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
− | + | int n = 12345; | |
− | + | int *p; | |
− | + | p = &n; | |
− | |||
− | |||
− | |||
− | |||
</syntaxhighlight> | </syntaxhighlight> | ||
− | + | Premenná ''p'' teraz ukazuje na miesto, kde je uložená celočíselná premenná ''n''. | |
[[Súbor:Pamat4.png]] | [[Súbor:Pamat4.png]] | ||
− | + | * Operátor <tt>&</tt> možno aplikovať aj na prvky poľa (t.j. napríklad <tt>&a[2]</tt> je adresa prvku <tt>a[2]</tt>). | |
− | + | * Operátor <tt>&</tt> nemožno aplikovať na konštanty (ako napríklad <tt>3.14</tt> alebo <tt>'c'</tt>), ani na výrazy (ako napríklad <tt>n+2</tt>). | |
− | Operátor <tt>&</tt> | ||
<syntaxhighlight lang="C++"> | <syntaxhighlight lang="C++"> | ||
− | + | 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 (vyraz nema adresu) | |
− | + | p = &42; // chyba (konstanta 42 nema adresu) | |
− | + | p = &a; // chyba (a nie je typu int) | |
</syntaxhighlight> | </syntaxhighlight> | ||
Verzia zo dňa a času 21:18, 28. október 2021
Obsah
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
V C++ sa smerník ukazujúci na premennú typu T definuje takto:
T *p;
Napríklad teda môžeme písať:
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 nejakej premennej vieme zistiť operátorom &
- Tú potom môžeme priradiť do premennej typu smerník
- Ak do premennej typu smerník nič nepriradíme, má nedefinovanú hodnotu, ukazuje na náhodné miesto v pamäti, alebo niekde mimo
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 (t.j. napríklad &a[2] je adresa prvku a[2]).
- 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; // korektné priradenie
p = &a[2]; // korektné 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;
}