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; }
Vyvoř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. 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.
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.
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'; }
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ě.
#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'; }