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
.
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;
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;
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.
#include <ctime> clock_t start, end; start = clock(); ... end = clock(); std::cout << "Cas vypoctu: " << (float)(end - start) / CLOCKS_PER_SEC << std::endl;
std::vector
(můžete použít funkci push_back
).
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.
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).
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.
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 mainVý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 mainV 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 mainVý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 mainZ 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 mainPř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:
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:
return
,
strict aliasing
, dva ukazatele různých typů neukazují na stejný kus paměti,
realloc
.