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

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;

Definovanou funkci resize_array využijte k experimentu.

• Zavolejte funkci opakovaně s tím, že velikost pole pokaždé zvýšíte o 1. Vytvořte tímto způsobem pole velikosti stotisíc nebo milion prvků. Čas výpočtu můžete změřit následovně:

    #include <ctime>
 
    clock_t start, end;
    start = clock();
    ...
    end = clock();
    std::cout << "Cas vypoctu: " << (float)(end - start) / CLOCKS_PER_SEC << std::endl;

• Porovnejte naměřený čas s dobou, kterou trvá vytvoření stejného pole typu std::vector (můžete použít funkci push_back).
• Porovnejte naměřený čas s dobou, kterou trvá vytvoření pole stejným způsobem (postupnou realokací o jeden prvek) s využitím funkce realloc.

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

Jak jsme si řekli, ukazatel na char smí ukazovat na stejné místo jako ukazatele na jiné typy.

Definujeme jednoduché pole celých čísel a ukazatel :

    int arr[3] = { 10, 256, 19786 };

Definujte ukazatel typu char a projděte pole bajt po bajtu. Kolik bajtů musíte projít? Jak jsou čísla v paměti organizována?

Standardní překlad z příkazové řádky:

g++ -Wall -Wextra -Wunreachable-code -Wpedantic -std=c++17 main.cpp -o main
clang++ -Wall -Wextra -Wunreachable-code -Wpedantic -std=c++17 main.cpp -o main

Výstupem programu jsou dvě čísla – 1, 1. V případě využití překladače g++ navíc program skončí s chybou Stack smashing. Proměnná i nemá při přetypování kam ukazovat, ukazuje tedy na stejnou paměť bez ohledu na typ.

Kompilace s optimalizací:

g++ -Wall -Wextra -Wunreachable-code -Wpedantic -std=c++17 –O3 main.cpp -o main
clang++ -Wall -Wextra -Wunreachable-code -Wpedantic -std=c++17 –O3 main.cpp -o main

V obou případech se vypíšou dvě čísla – 1 a 0. Optimalizace automaticky vyhodnotí strict aliasing a v druhé verzi funkce foo() vrátí hodnotu danou adresou x.

Standardní překlad z příkazové řádky:

g++ -Wall -Wextra -Wunreachable-code -Wpedantic -std=c++17 main.cpp -o main
clang++ -Wall -Wextra -Wunreachable-code -Wpedantic -std=c++17 main.cpp -o main

Výstupem programu jsou podle očekávání dvě čísla – 2 a 2, adresy ukazatelů p a q jsou stejné.

Kompilace s optimalizací:

g++ -Wall -Wextra -Wunreachable-code -Wpedantic -std=c++17 –O3 main.cpp -o main

Z hlediska výstupu programu dostáváme stejný výsledek i při použití překladače g++ s optimalizací.

clang++ -Wall -Wextra -Wunreachable-code -Wpedantic -std=c++17 –O3 main.cpp -o main

Při využití překladače clang++ s optimalizací jsou výstupem dvě čísla 1 a 2, adresy definovaných ukazatelů jsou stejné. Optimalizace předpokládá, že ukazatele neukazují na stejnou paměť a zachová rozdílné hodnoty na místech, kam oba ukazatele ukazují.

Při nespecifikovaném chování není přesně určeno, co se má v dané situaci stát. Různé typy překladačů mohou zpracovat program různě, a tak ovlivnit jeho výsledné chování. Nespecifikované chování se nejčastěji projevuje v:

• pořadí vyhodnocení argumentů funkce,
• pořadí zpracování podvýrazů.

Obvykle předpokládáme, že argumenty funkce nebo podvýrazy jsou zpracovávány zleva doprava. Tento předpoklad byl v mnoha případech definován ve standardu C++17, přesto k nespecifikovanému chování dochází. Prevencí je vyhnout se akumulaci vice argumentů nebo podvýrazů, tj. ukládat průběžně mezivýsledky do pomocných proměnných, které následně využijeme pro konečný výpočet.

K nedefinovanému chování by podle standardu jazyka C++ nikdy nemělo dojít. Jazyk sám ale nebrání, aby k podobným situacím docházelo a kompilátor tak může při optimalizaci nedefinované chování zanedbat a předpokládat, že programátor zajistil, aby k němu nedošlo. Jak jsme mohli vidět v předchozích cvičeních, jedná se například o následující situace:

• dělení nulou,
• pokus o úpravu řetězcového literálu (konstanty),
• přetečení hodnoty se znaménkem,
• nekonečná smyčka bez vedlejších účinků,
• index mimo hranice pole,
• funkce vracející hodnotu daného typu bez příkazu return,
• neinicializovaný nebo nulový ukazatel,
• strict aliasing, dva ukazatele různých typů neukazují na stejný kus paměti,
• vzájemné srovnávání (menší, větší) ukazatelů na různé objekty (definováno je pouze, pokud ukazatele ukazují na prvky stejného objektu, pole),
• přístup k ukazateli předán přes realloc.