Získej svůj iPhone v nové soutěži! Získej svůj iPhone v nové soutěži!
Nová překladatelská soutěž ITnetwork.cz o telefon iPhone, sluchátka Beats a další věcné ceny za 4 hodiny práce.
Přidej si svou IT školu do profilu a najdi spolužáky zde na síti :)

12. díl - Dynamická alokace polí

C a C++ C++ Pokročilé konstrukce v C++ Dynamická alokace polí

ONEbit hosting Unicorn College Tento obsah je dostupný zdarma v rámci projektu IT lidem. Vydávání, hosting a aktualizace umožňují jeho sponzoři.

Již jsme si ukázali, jak si dynamicky alokovat základní datové typy a struktury. Zatím jsme si ale nepověděli, jak si dynamicky vytvářet pole.

V čistém C se používá funkce malloc, více je probráno v článku Dynamická alokace paměti v jazyce C. Ačkoliv se jedná o céčkový přístup, doporučuji se seznámit se syntaxí a použitím. Přestože C++ poskytuje vlastní syntaxi pro alokací polí, ta z C se běžně používá (i v C++ kódech), protože je o něco univerzálnější. Nyní se již pojďme podívat na syntaxi v C++.

Operátor new[]

Tento operátor funguje stejně jako operátor new, s tím rozdílem, že místo jednoto prvku jich vytvoří několik. Tyto prvky jsou v paměti za sebou jeden vedle druhého a operátor new[] nám vrátí adresu prvního z nich, tedy pointer na začátek tohoto bloku paměti. Na rozdíl od vyšších programovacích jazyků si C++ žádným způsobem nepamatuje velikost pole (o to se musíme postarat sami) a stejně tak nekontroluje přístup mimo hranice pole. Syntaxe je následující:

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

Jak je vidět, platí stejné pravidla jako pro staré dobré pole, jak jsme se ho učili. Indexujeme od nuly pomocí hranatých závorek. Stejně tak platí, že použijeme-li index roven nebo větší velikosti pole, čteme data mimo pole a dostaneme buď neplatné data nebo program spadne.

Operátor delete[]

Pro uvolnění paměti se používá operátor delete s hranatými závorkami. Platí stejná pravidla jako pro čisté delete, tedy měli bychom ukazatel nastavit na NULL a neměli bychom uvolňovat již uvolněnou paměť (program by opět mohl spadnout). Syntaxe je následující:

delete [] array;

Pokud přicházíte z C (nebo máte zkušenosti se správou paměti v C), je potřeba zdůraznit, že paměť musí být uvolněna pomocí delete []. Syntaxe C (malloc a free) a C++ (new[] a delete[]) používají jiné algoritmy pro alokování a uvolňování paměti a nejsou kompatibilní. Paměť alokovaná malloc musí být uvolněna voláním free a paměť alokována new musí být uvolněna delete.

Tím jsme probrali syntaxi a teď si ukážeme, jak vytvořit pole, které se umí automaticky zvětšit.

Dynamické pole

Řekněme, že chceme uložit několik hodnot, ale dopředu nevíme, kolik jich bude. Pokud použijeme pole malé velikost, nemusí se všechny hodnoty do pole vlézt. Pokud ale použijeme pole příliš velké, tak budeme ve většině případů zbytečně zabírat mnoho místa. Řešením je dynamické pole, které se automaticky zvětšuje.

Na začátku si vytvoříme pole určité velikosti (řekněme 10 prvků). Pokud budeme chtít vložit 11. prvek, potom vytvoříme větší pole, hodnoty ze starého pole překopírujeme a jedenáctý prvek vložíme do zvětšeného pole. Staré pole poté můžeme vymazat. Ke každému takovému poli si tedy budeme muset pamatovat ukazatel, jeho velikost a počet vložených prvků.

Jedinou funkci kterou budeme potřebovat bude pro vložení dalšího prvku. Jedná se totiž o jedinou funkci, která může původní pole změnit. Nejdřív si uvedeme implementaci a až poté si funkci vysvětlíme.

int* pridej_prvek(int prvek, int* pole, int &pocet_prvku, &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 == vlozeno)
     {
          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;
}

Pokud nám v parametru příjde nealokované pole (nebo jen NULL), potom vytvoříme pole o velikosti 10, vložíme do něj první prvek a pole vrátíme. Protože se adresa pole může uvnitř funkce změnit (například když pole zvětšujeme), musíme si návratovou hodnotu vždy uložit namísto původního pole. Pokud už je pole plné (počet vložených prvků se rovná kapacitě), poté si vytvoříme nové pole, překopírujeme hodnoty, staré pole uvolníme a vrátíme nově vytvořené pole. Nakonec nám zůstává situace, kdy je v poli dostatek místa. V takovém případě pouze vložíme prvek na konec a pole vrátíme. Všimněte si použití referencí u parametrů. Díky tomu můžeme uvnitř funkce měnit počet prvků i kapacitu pole a změny se propíšou ven.

Jak se takové pole používá, je na následující ukázce:

     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;
Konzolová aplikace
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áce je velice jednoduchá a pozor si musíme dát pouze při přidávání prvků do pole. Přístup probíhá stále stejně a mazání provedeme pouze tím, že zmenšíme počet vložených prvků. Ideální by bylo uzavřít počet prvků, kapacitu a ukazatel do struktury a tím zápis ještě zpřehlednit. Funkce by poté měla pouze dva parametry a to vkládaný prvek a referenci na strukturu (abychom ji mohli změnit).

Velmi podobná logika je použita ve většině vyšších programovacích jazycích pro implementaci polí, které se mohou dynamicky zvětšovat (ArrayList v Javě, List v C# nebo Array v JavaScriptu). Pokud se (stejně jako v našem případě) pole vždy zvětší na dvojnásobek své kapacity, jedná se o nejefektivnější řešení v poměru výkonu a paměťové náročnosti.

Naše pole má stále jednu nevýhodu. Můžeme ho použít pouze pro pole celých čísel. V příštím díle se podíváme na šablony a ukážeme si, jak vytvořit univerzální implementaci pro všechny datové typy.


 

 

Článek pro vás napsal patrik.valkovic
Avatar
Jak se ti líbí článek?
1 hlasů
Věnuji se programování v C++ a C#. Kromě toho také programuji v PHP (Nette) a JavaScriptu (NodeJS).
Miniatura
Předchozí článek
Přetypování a operátory
Miniatura
Všechny články v sekci
Pokročilé konstrukce C++
Miniatura
Následující článek
Šablony
Aktivity (2)

 

 

Komentáře

Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zatím nikdo nevložil komentář - buď první!