{{page>courses:b6b36pjc:styles#common&noheader&nofooter}}
{{page>courses:b6b36pjc:styles#cviceni&noheader&nofooter}}

===== Cvičení 4: Dynamicky alokovaná pole =====

Dnes si ukážeme práci s dynamicky alokovanými poli. Takováto pole jsou v paměti
umístěna na haldě (heap) a existují, dokud je programátor neuvolní. Jak už víte
z přednášky, pole můžeme dynamicky alokovat pomocí operátoru ''new[]'' a uvolnit
pomocí operátoru ''delete[]''.

<code cpp>
int main() {
    int arrSize = 10;
    double* arr = new double[arrSize];
    delete[] arr;
}
</code>

Na rozdíl od statických polí, ''arrSize'' nemusí být konstanta známá při
překladu (museli bychom použít typ ''const int'' namísto ''int''). Samotné
zacházení s dynamicky alokovanými poli se neliší od zacházení s běžnými poli.
Oba druhy polí můžeme reprezentovat ukazateli a indexovat pomocí operátoru
''[]''.

Typicky si musíme ve zvláštní proměnné pamatovat velikost pole. Standardní
knihovna poskytuje typ ''size_t'', který je pro ukládání velikosti pole vhodný;
je dostatečně velký a bez znaménka. Pokud program nemá přístup k ''size_t'',
stačí přidat hlavičku ''<stddef.h>''.

<code cpp>
#include <stddef.h>

int main() {
    size_t arrSize = 10;
    double* arr = new double[arrSize];
    delete[] arr;
}
</code>

==== Úlohy ====

Vytvořme pár funkcí, které nám pomohou pracovat s poli určitého typu prvku, např.
''double''.

  * Napište funkci ''print_array'' pro tisk pole na standardní výstup. Následující kód musí fungovat:

<code cpp>
    const double staticArr[3] = { 1.23, 2.34, 3.45 };
    double* dynamicArr = new double[3]{};
    print_array(staticArr, 3);  // vypíše: 1.23 2.34 3.45
    print_array(dynamicArr, 3); // vypíše 0 0 0
    delete[] dynamicArr;
</code>

  * Napište funkci ''copy_array'' pro kopírování polí. Následující kód musí fungovat:

<code cpp>
    const double staticArr[3] = { 1.23, 2.34, 3.45 };
    double* dynamicArr = new double[3]{};
    copy_array(staticArr, dynamicArr, 3);
    print_array(staticArr, 3);  // vypíše: 1.23 2.34 3.45
    print_array(dynamicArr, 3); // vypíše: 1.23 2.34 3.45
    delete[] dynamicArr;
</code>

  * Napište funkci ''resize_array'' pro změnu velikosti dynamicky alokovaného pole. Jako parametry získá: ukazatel na pole (vstupně-výstupní parametr), dosavadní velikost pole a cílovou velikost pole. V těle funkce ''resize_array'' vytvořte nové pole, překopírujte obsah původního pole do nového, a pak původní pole smažte. (Pokud je nová velikost menší než stará, přebytečné prvky zahoďte.) Následující kód musí fungovat:

<code cpp>
    double* arr = new double[3];
    arr[0] = 1.23;
    arr[1] = 2.34;
    arr[2] = 3.45;
    resize_array(arr, 3, 5);
    arr[3] = 4.56;
    arr[4] = 5.67;
    resize_array(arr, 5, 6);
    arr[5] = 6.78;
    print_array(arr, 6); // vypíše: 1.23 2.34 3.45 4.56 5.67 6.78
    delete[] arr;
</code>

===== Odbočka: dynamicky alokované objekty =====

Často potřebujeme alokovat pouze jeden prvek daného typu. K tomu slouží operátor
''new'' bez hranatých závorek ''[]''. K uvolnění slouží operátor ''delete'',
rovněž bez hranatých závorek:

<code cpp>
double* d = new double;
...
delete d;
</code>

===== Od polí k vektoru =====

Budeme implementovat strukturu, která obsluhuje dynamicky alokované pole a
udržuje si informaci o jeho velikosti. Bude plnit podobnou funkci, jako
''std::vector<double>'' ze standardní knihovny. Stejně jako u ''std::vector''
budeme chtít podporovat operace ''push_back'', ''pop_back'', ''size'', apod.
Definice takovéto struktury může vypadat například takto:

<code cpp>
struct vector {
    double* data = nullptr;
    size_t capacity = 0;
    size_t size = 0;
};
</code>

Implicitní hodnoty v definici způsobují, že pokud neurčíme jinak, položky ve
struktuře se inicializují danými výchozími hodnotami. Proto jsou následující dva
řádky ekvivalentní:

<code cpp>
vector v;
vector v = { nullptr, 0, 0 }; // to samé
</code>

Pamatujeme si dvě čísla: //kapacitu// a //logickou velikost//.

  * ''capacity'', kapacita, neboli fyzická velikost, je skutečná velikost alokovaného pole. Určeme, že kapacita může pouze růst, tedy alokované pole se může pouze zvětšovat.
  * ''size'', logická velikost, je počet prvků v poli z pohledu uživatele. Může se zvětšovat a zmenšovat.
  * vždy platí: ''capacity'' $\geq$ ''size''.

Navíc, až ukončíme práci s naším ''vector''em, chtěli bychom, aby svoje
dynamicky alokované pole uvolnil. Po uživateli budeme vyžadovat, aby vždy
nakonec zavolal funkci ''dispose'' pro každý ''vector'', který vytvořil:

<code cpp>
vector v;
// ...
dispose(v);
</code>

Pokud uživatel zapomene zavolat ''dispose'', dojde k úniku paměti (memory
leaku). Bohužel zatím nemáme k dispozici způsob, jak ''dispose'' zavolat
automaticky (ale v příštích cvičeních si ho ukážeme).

==== Úloha ====

Implementujte funkce ''dispose'', ''push_back'', ''print_vector'', ''size'' a
''at'' tak, aby následující program fungoval a neztrácel pamět:

<code cpp>
void multiply_all(vector& v, double factor) {
    for (size_t i = 0; i < size(v); ++i) {
        at(v, i) *= factor;
    }
}

double accumulate(const vector& v) {
    double sum = 0;

    for (size_t i = 0; i < size(v); ++i) {
        sum += at(v, i);
    }

    return sum;
}

int main() {
    vector v;
    push_back(v, 1.23);
    push_back(v, 2.34);
    push_back(v, 3.45);
    print_vector(v);            // capacity: 6 size: 3 data: 1.23 2.34 3.45
    multiply_all(v, 2);
    print_vector(v);            // capacity: 6 size: 3 data: 2.46 4.68 6.9
    double sum = accumulate(v);
    std::cout << sum << '\n';   // 14.04
    dispose(v);
}
</code>

Další funkce k implementaci: ''capacity'', ''pop_back'', ''reserve'', ''clear'',
''empty'', ''resize''. Všechny tyto funkce jsou také metody standardní kolekce
''std::vector''. Pokud nevíte, co mají funkce přesně dělat, najděte si
odpovídající metodu na [[http://en.cppreference.com/w/cpp/container/vector]].


{{:courses:b6b36pjc:cviceni:cviceni_4_final.zip|Řešení}}

===== Koutek nedefinovaného chování =====
C%%++%% předpokládá tzv. "strict aliasing". Zjednodušeně, pokud dva ukazatele
ukazují na jiný typ, pak neukazují na stejný kus paměti. Výjimka je ukazatel na
''char'', který smí ukazovat na stejné místo jako ukazatele na jiné typy. Strict
aliasing nic neříká o dvou ukazatelích na stejný typ a obvykle se předpokládá,
že mohou ukazovat na stejný kus paměti.

Pokud je tento předpoklad porušený, dochází k nedefinovanému chování.

==== Příklad 1 ====
<code cpp>
#include <iostream>

int foo(int* x, int* y){
    *x = 0;
    *y = 1;
    return *x;
}

int foo(int* x, long* y) {
  *x = 0;
  *y = 1;
  return *x;
}

int main(int argc, char** argv) {
    int i;
    std::cout << foo(&i, &i) << '\n';
    std::cout << foo(&i, (long*)&i) << '\n';
}
</code>

==== Příklad 2 ====
To, že libovolné dva ukazatele na stejný typ mohou ukazovat na stejnou paměť,
omezuje optimalizace. Proto se u ukazatelů vrácených z alokačních funkcí tento
předpoklad mění; předpokládá se, že na stejný kus paměti ukazovat nemohou.
Toto platí i o funkci ''realloc'', která se snaží zvětšit alokaci na místě.
(U funkcí ze standardní knihovny toto platí obecně, u jiných funkcí záleží
na přesné podobě implementace.)

<code cpp>
#include <cstdlib>
#include <iostream>

int main() {
    int *p = (int*)malloc(sizeof(int));
    int *q = (int*)realloc(p, sizeof(int));
    *p = 1;
    *q = 2;
    std::cout << *p << ' ' << *q << '\n';
    std::cout << "Addresses: " <<  p << ' ' << q << '\n';
}
</code>