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[].

int main() {
    int arrSize = 10;
    double* arr = new double[arrSize];
    delete[] arr;
}

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>.

#include <stddef.h>
 
int main() {
    size_t arrSize = 10;
    double* arr = new double[arrSize];
    delete[] arr;
}

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:

    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;

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

    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;

• 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:

    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;

Č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:

double* d = new double;
...
delete d;

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:

struct vector {
    double* data = nullptr;
    size_t capacity = 0;
    size_t size = 0;
};

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í:

vector v;
vector v = { nullptr, 0, 0 }; // to samé

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 vectorem, 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:

vector v;
// ...
dispose(v);

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).

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

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);
}

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.

Řešení

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í.

#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';
}

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.)

#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';
}