12. diel - Dynamická alokácia polí

Už sme si ukázali, ako si dynamicky alokovať základné dátové typy a štruktúry. Zatiaľ sme si však nepovedali, ako si dynamicky vytvárať poľa.

V čistom C sa používa funkcia malloc, viac je prebrané v článku Dynamická alokácia pamäte v jazyku C. Hoci sa jedná o céčkový prístup, odporúčam sa zoznámiť so syntaxou a použitím. Hoci C ++ poskytuje vlastnú syntax pre alokácií polí, tá z C sa bežne používa (aj v C ++ kódoch), pretože je o niečo univerzálnejšie. Teraz sa už poďme pozrieť na syntax v C ++.

Operátor new []

Tento operátor funguje rovnako ako operátor new, s tým rozdielom, že namiesto Jednota prvku ich vytvorí niekoľko. Tieto prvky sú v pamäti za sebou jeden vedľa druhého a operátor new [] nám vráti adresu prvého z nich, teda pointer na začiatok tohto bloku pamäte. Na rozdiel od vyšších programovacích jazykov si C ++ žiadnym spôsobom nepamätá veľkosť poľa (o to sa musíme postarať sami) a rovnako tak nekontroluje prístup mimo hranice poľa. Syntax je nasledovná:

#include <iostream>
using namespace std;

int main(){

int* array = new int[100];  //vytvoření 100 prvků typu int a přiřazení adresy prvního z nich pointeru array, nebo-li vytvoření pole o 100 prvcích typu int
*array = 20;  //přiřazení hodnoty 20 prvku na adrese na kterou ukazuje array, nebo-li přiřazení hodnoty 20 prvnímu prvku pole
array[0] = 20;  //toto je to samé
array[54] = 1000;  //to samé, jen přiřazujeme hodnotu pětapadesátému prvku pole
array[100] = 1;  //chyba - poslední index pole je 99

for(int i=0;i<100;i++)
    cout << array[i] << " ";
cout << endl;
}

Ako je vidieť, platia rovnaké pravidlá ako pre staré dobré pole, ako sme sa ho učili. Indexuje od nuly pomocou hranatých zátvoriek. Rovnako tak platí, že ak použijeme index rovný alebo väčšej veľkosti poľa, čítame dáta mimo poľa a dostaneme buď neplatné dáta alebo program spadne.

Operátor delete []

Pre uvoľnenie pamäte sa používa operátor delete s hranatými zátvorkami. Platia rovnaké pravidlá ako pre čisté delete, teda mali by sme ukazovateľ nastaviť na NULL a nemali by sme uvoľňovať už uvoľnenú pamäť (program by opäť mohol spadnúť). Syntax je nasledovná:

delete [] array;

Ak prichádzate z C (alebo máte skúsenosti so správou pamäte v C), je potreba zdôrazniť, že pamäť musí byť uvoľnená pomocou delete []. Syntax C (malloc a free) a C ++ (new [] a delete []) používajú iné algoritmy pre alokovanie a uvoľňovanie pamäte a nie sú kompatibilné. Pamäť alokovaná malloc musí byť uvoľnená volaním free a pamäť alokovaná new musí byť uvoľnená delete.

Tým sme prebrali syntax a teraz si ukážeme, ako vytvoriť pole, ktoré sa vedia automaticky zväčšiť.

Dynamické pole

Povedzme, že chceme uložiť niekoľko hodnôt, ale dopredu nevieme, koľko ich bude. Ak použijeme pole malé veľkosť, nemusia sa všetky hodnoty do poľa vliezť. Pokiaľ ale použijeme pole príliš veľké, tak budeme vo väčšine prípadov zbytočne zaberať veľa miesta. Riešením je dynamické pole, ktoré sa automaticky zväčšuje.

Na začiatku si vytvoríme pole určitej veľkosti (povedzme 10 prvkov). Ak budeme chcieť vložiť 11. prvok, potom vytvoríme väčšie pole, hodnoty zo starého poľa prekopíruje a jedenásty prvok vložíme do zväčšeného poľa. Staré pole potom môžeme vymazať. Ku každému takémuto poli si teda budeme musieť pamätať ukazovateľ, jeho veľkosť a počet vložených prvkov.

Jedinou funkciu ktorú budeme potrebovať bude pre vloženie ďalšieho prvku. Ide totiž o jedinú funkciu, ktorá môže pôvodnú poľa zmeniť. Najskôr si uvedieme implementáciu a až potom si funkciu vysvetlíme.

int* pridej_prvek(int prvek, int* pole, int &pocet_prvku, int &kapacita)
{
     //vytvoříme nove pole
     if(pole == NULL)
     {
          int* vytvoreno = new int[10];
          kapacita = 10;
          vytvoreno[0]=prvek;
          pocet_prvku=1;
          return vytvoreno;
     }
     //pole je již plne - musíme ho zvětšit
     if(kapacita == pocet_prvku)
     {
          int* vytvoreno = new int[kapacita*2]; // vytvoření nového pole
          kapacita = kapacita * 2;
          for(int i=0;i<pocet_prvku;i++)
               vytvoreno[i]=pole[i]; //zkopírování původního pole
          delete [] pole;
          vytvoreno[pocet_prvku]=prvek;
          pocet_prvku++;
          return vytvoreno;
     }
     //je dostatek místa
     pole[pocet_prvku]=prvek;
     pocet_prvku++;
     return pole;
}

Ak nám v parametri príde Nealokované poľa (alebo len NULL), potom vytvoríme poľa veľkosti 10, vložíme do neho prvý prvok a pole vrátime. Pretože sa adresa poľa môže vnútri funkcie zmeniť (napríklad keď pole zväčšujeme), musíme si návratovú hodnotu vždy uložiť namiesto pôvodného poľa. Ak už je pole plné (počet vložených prvkov sa rovná kapacite), potom si vytvoríme nové pole, prekopíruje hodnoty, staré polia uvoľníme a vrátime novovytvorenej poľa. Nakoniec nám zostáva situácia, kedy je v poli dostatok miesta. V takom prípade iba vložíme prvok na koniec a polia vrátime. Všimnite si použitie referencií u parametrov. Vďaka tomu môžeme vnútri funkcie meniť počet prvkov aj kapacitu poľa a zmeny sa prepíšu von.

Ako sa také pole používa, je na nasledujúcej ukážke:

#include <iostream>
using namespace std;

int* pridej_prvek(int prvek, int* pole, int &pocet_prvku, int &kapacita)
{
     //vytvarime nove pole
     if(pole == NULL)
     {
          int* vytvoreno = new int[10];
          kapacita = 10;
          vytvoreno[0]=prvek;
          pocet_prvku=1;
          return vytvoreno;
     }
     //pole je jiz plne - musime ho zvetsit
     if(kapacita == pocet_prvku)
     {
          int* vytvoreno = new int[kapacita*2]; // vytvoření nového pole
          kapacita = kapacita * 2;
          for(int i=0;i<pocet_prvku;i++)
               vytvoreno[i]=pole[i]; //zkopírování původního pole
          delete [] pole;
          vytvoreno[pocet_prvku]=prvek;
          pocet_prvku++;
          return vytvoreno;
     }
     //je dostatek mista
     pole[pocet_prvku]=prvek;
     pocet_prvku++;
     return pole;
}


int main()
{

     int* pole = NULL;
     int velikost, kapacita;
     for(int i=0;i<15;i++)
          pole = pridej_prvek(i*2, pole, velikost, kapacita);
     cout << "Prvky: ";
     for(int i=0;i<velikost;i++)
          cout << pole[i] << " ";
      for(int i=0;i<10;i++)
          pole = pridej_prvek(i*3, pole, velikost, kapacita);
     cout << endl << "Prvky: ";
     for(int i=0;i<velikost;i++)
          cout << pole[i] << " ";
     cout << endl << "Pocet prvku: " << velikost << ", kapacita: " << kapacita << endl;

     return 0;
}

Konzolová aplikácia
Prvky: 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28
Prvky: 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 0 3 6 9 12 15 18 21 24 27
Pocet prvku: 25, kapacita: 40

Práca je veľmi jednoduchá a pozor si musíme dať iba pri pridávaní prvkov do poľa. Prístup prebieha stále rovnako a mazanie vykonáme iba tým, že zmenšíme počet vložených prvkov. Ideálne by bolo uzavrieť počet prvkov, kapacitu a ukazovateľ do štruktúry a tým zápis ešte sprehľadniť. Funkcia by potom mala iba dva parametre a to vkladaný prvok a referenciu na štruktúru (aby sme ju mohli zmeniť).

Veľmi podobná logika je použitá vo väčšine vyšších programovacích jazykoch pre implementáciu polí, ktoré sa môžu dynamicky zväčšovať (ArrayList v Jave, List v C# alebo Array v JavaScriptu). Ak sa (rovnako ako v našom prípade) pole vždy zväčší na dvojnásobok svojej kapacity, jedná sa o najefektívnejšie riešenie v pomere výkonu a pamäťovej náročnosti.

Naša pole má stále jednu nevýhodu. Môžeme ho použiť len pre pole celých čísel. V budúcom dieli sa pozrieme na šablóny a ukážeme si, ako vytvoriť univerzálny implementáciu pre všetky dátové typy.