Warning
This page is located in archive. Go to the latest version of this course pages.

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Last revision Both sides next revision
courses:b6b36pjc:cviceni:cviceni_4 [2017/09/25 17:12]
richta created 		courses:b6b36pjc:cviceni:cviceni_4 [2017/10/22 22:14]
horenmar
Line 1: Line 1:
-<​HTML>​ +{{page>​courses:b6b36pjc:styles#common&​noheader&​nofooter}} 
-<​style>​ +{{page>​courses:b6b36pjc:styles#cviceni&​noheader&​nofooter}}
-.code .kw1, .code .kw2, .code .kw4 { color: #00f; font-weight:​ bold; } +
-.code .br0, .code .kw3, .code .me1, .code .me2, .code .nu0 { color: #000; } +
-.code .co1, .code .coMULTI { color: #080; font-style: normal; ​} +
-.code .co2 { color: #888; font-style: normal; } +
-.code .st0 { color: #a31515; ​} +
-</​style>​ +
-</​HTML>​+
  
 ===== Dynamicky alokovaná pole ===== ===== 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[]''​.+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> <code cpp>
Line 21: Line 17:
 </​code>​ </​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 ''​[]''​.+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>''​.+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> <code cpp>
Line 37: Line 40:
 ==== Úlohy ==== ==== Úlohy ====
  
-Vyvořme pár funkcí, které nám pomohou pracovat s poli určitého typu prvku, např. ''​double''​.+Vyvoř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:   * Napište funkci ''​print_array''​ pro tisk pole na standardní výstup. Následující kód musí fungovat:
Line 60: Line 64:
 </​code>​ </​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. Následující kód musí fungovat:+  * 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> <code cpp>
Line 78: Line 82:
 ===== Odbočka: dynamicky alokované objekty ===== ===== 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:+Č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> <code cpp>
Line 88: Line 94:
 ===== Od polí k vektoru ===== ===== 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:+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> <code cpp>
Line 98: Line 108:
 </​code>​ </​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í:​+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> <code cpp>
Line 111: Line 123:
   * vždy platí: ''​capacity''​ $\geq$ ''​size''​.   * 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:+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> <code cpp>
Line 119: Line 133:
 </​code>​ </​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.+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 ==== ==== Úloha ====
  
-Implementujte funkce ''​dispose'',​ ''​push_back'',​ ''​print_vector'',​ ''​size''​ a ''​at''​ tak, aby následující program fungoval a neztrácel pamět:+Implementujte funkce ''​dispose'',​ ''​push_back'',​ ''​print_vector'',​ ''​size''​ a 
 +''​at''​ tak, aby následující program fungoval a neztrácel pamět:
  
 <code cpp> <code cpp>
Line 156: Line 173:
 </​code>​ </​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]].+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]].
  
  
Line 162: Line 182:
  
 ===== Koutek nedefinovaného chování ===== ===== 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.+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í. Pokud je tento předpoklad porušený, dochází k nedefinovanému chování.
Line 190: Line 214:
  
 ==== Příklad 2 ==== ==== Příklad 2 ====
-Protože předpoklad, že libovolné dva ukazatele na stejný typ mohou ukazovat na stejnou paměť, ​brání optimalizacím,​ předpokládá ​se, že ukazatele získané ​z alokačních funkcí, ​nemohou ukazovat ​na stejný kus paměti. Toto platí i o funkci ''​realloc'',​ která se snaží zvětšit alokaci na místě.+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> <code cpp>
Line 205: Line 234:
 } }
 </​code>​ </​code>​
 +
courses/b6b36pjc/cviceni/cviceni_4.txt · Last modified: 2017/10/22 22:18 by horenmar