{{page>courses:b6b36pjc:styles#common&noheader&nofooter}} {{page>courses:b6b36pjc:styles#cviceni&noheader&nofooter}} ======= Cvičení 4: Dynamicky alokovaná pole ======= {{ :courses:b6b36pcc:cviceni:pruvodce.png?90|}} 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 ''''. #include int main() { size_t arrSize = 10; double* arr = new double[arrSize]; delete[] arr; } {{ :courses:b6b36pcc:cviceni:ukoly.png?90| Úkol k procvičení}} ===== Úlohy k procvičení ===== 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 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''. ===== 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: double* d = new double; ... delete d; ==== 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'' 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 ''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: 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). {{ :courses:b6b36pcc:cviceni:ukoly.png?90| Úkol k procvičení}} ==== Úloha ==== 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]]. {{:courses:b6b36pcc: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 ==== #include 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'; } ==== 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.) #include #include 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'; } {{ :courses:b6b36pcc:cviceni:ukoly.png?90| Úkol k procvičení}} ==== Úkol ==== 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? {{ :courses:b6b36pcc:cviceni:reseni.png?90| Řešení a odpovědi}} ==== Řešení a odpovědi k nedefinovanému chování ==== === Příklad 1 - strict aliasing, dva ukazatele různých typů neukazují na stejný kus paměti === 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''. \\ === Příklad 2 - přístup k ukazateli předán přes realloc === 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í. {{ :courses:b6b36pcc:cviceni:shrnuti.png?90|}} ===== Shrnutí: Nedefinované a nespecifikované chování ===== ==== Nespecifikované chování ==== 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. ==== Nedefinované chování ==== 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''.