0 bodů

C · 36 min

Struktury a dynamická paměť

Jak z více hodnot složit vlastní typ pomocí struct a typedef, jak si za běhu vyžádat paměť funkcemi malloc a free, co jsou úniky paměti a čím se liší zásobník od haldy.

Obtížnost: 4 z 5

Lidsky řečeno

Představ si kartotéční lístek s kolonkami: jméno, věk, výška. Takový lístek je struktura: spojuje několik různých údajů o jedné věci do jednoho celku. A dynamická paměť je jako půjčovna: když potřebuješ víc místa, než jsi předem počítal, půjčíš si ho za běhu programu. Důležité je, že si všechno, co jsi půjčil, musíš vrátit, jinak půjčovna časem dojde.

Struktura (struct)

Pole obsahuje prvky stejného typu. Struktura (struct) seskupuje hodnoty různých typů, kterým se říká členy. Přistupuje se k nim tečkou.

c
struct Osoba {
    char jmeno[20];
    int vek;
    double vyska;
};

struct Osoba a;          /* proměnná typu struct Osoba */
a.vek = 30;
a.vyska = 1.70;
strcpy(a.jmeno, "Eva");

Strukturu lze přiřadit jinou strukturou stejného typu (b = a;) a zkopírují se všechny členy včetně polí uvnitř. Stejně se předává hodnotou do funkce. Strukturami se nedá srovnávat operátorem ==, porovnávají se člen po členu.

typedef: kratší jméno typu

Zápis struct Osoba se opakuje. Klíčové slovo typedef vytvoří nové jméno pro existující typ:

c
typedef struct {
    char jmeno[20];
    int vek;
    double vyska;
} Osoba;

Osoba a;                 /* už bez slova struct */
Vyzkoušej v C

První struktura

Spusť a pak zkus přidat vlastní člen, třeba int body.

Velikost struktury může být větší než součet členů, protože překladač členy kvůli rychlému přístupu zarovnává (vkládá mezery, tzv. padding). Přesné číslo záleží na překladači a systému, proto vždy používej sizeof.

Ukazatel na strukturu a šipka

Přes ukazatel na strukturu se k členům dostaneš operátorem šipka ->. Zápis p->vek je zkratka za (*p).vek. Strukturu se tak vyplatí do funkce předávat adresou: nekopíruje se celá a funkce ji může změnit.

Úkol v C

Úkol: narozeniny

Dopiš funkci oslav, která zvýší věk osoby o 1. Funkce dostane ukazatel na strukturu. Program načte věk a vypíše věk po oslavě.

Zásobník a halda

Program má dvě hlavní oblasti paměti pro data:

Zásobník (stack)Halda (heap)
Co tam jelokální proměnné a parametry funkcípaměť vyžádaná malloc
Vznik a zánikautomaticky při vstupu a opuštění funkceručně: malloc a free
Velikostmalá (typicky pár MB)velká (omezená pamětí počítače)
Rychlostvelmi rychlýpomalejší
Chybypřetečení při hluboké rekurzi nebo velkých políchúniky, dvojité uvolnění

Velikost pole na zásobníku musí být známa dopředu. Když ji zjistíš až za běhu (načteš počet prvků od uživatele), nebo když data mají přežít návrat z funkce, použiješ haldu.

malloc a free

Funkce z <stdlib.h>:

  • malloc(bajty) vyžádá souvislý blok paměti a vrátí ukazatel na jeho začátek, nebo NULL, když paměť není.
  • free(p) blok vrátí systému. Po free už přes p nesmíš nic číst ani zapisovat.
  • calloc(pocet, velikost) jako malloc, ale paměť vynuluje.
  • realloc(p, nova_velikost) změní velikost bloku (může ho přesunout).

Velikost se zapisuje jako pocet * sizeof(typ), takže program nezávisí na velikosti typů. Ukazatel z malloc se v C nepřetypovává (oproti C++).

Vyzkoušej v C

Pole o velikosti zadané za běhu

Program načte počet čísel, vyžádá si pro ně paměť, spočítá průměr a paměť uvolní. Zkus ho spustit s různými vstupy.

Úkol v C

Úkol: kvadráty na haldě

Načti n, vyžádej paměť pro n čísel, ulož do k[i] hodnotu i * i a vypiš je oddělená mezerami. Nakonec paměť uvolni.

Úniky paměti a další chyby

Za každé malloc má být právě jedno free. Co se může pokazit:

ChybaCo se stane
Únik paměti (memory leak)zapomenuté free, program zabírá stále víc paměti
Použití po uvolnění (use after free)čtení nebo zápis přes ukazatel po free, nedefinované chování
Dvojité uvolnění (double free)free zavolané dvakrát na stejný blok, pád nebo poškození paměti
Neověřené NULLmalloc selhal a program zapíše na adresu 0
Zápis za konec blokupřetečení haldy, stejně jako u polí

Spojový seznam: struktura odkazuje na sebe

Struktura může obsahovat ukazatel na další strukturu stejného typu. Tak vzniká spojový seznam: uzly se vytvářejí za běhu na haldě a každý ukazuje na další. Poslední má dalsi == NULL.

Vyzkoušej v C

Spojový seznam na haldě

Uzly se přidávají na začátek. Všimni si, že před koncem programu každý uzel uvolníme.

Co simulátor nespouští

Inicializace struktury seznamem v jednom řádku, například Osoba a = {"Eva", 30, 1.70}; (nebo s pojmenovanými členy {.vek = 30}), je standardní C. Simulátor na stránce ji nemusí zvládnout, proto se v ukázkách přiřazují členy po jednom. Na vlastním počítači ji vyzkoušej, přeložíš ji příkazem gcc -Wall -o prog prog.c. K hledání úniků paměti na Linuxu a macOS slouží nástroj Valgrind (valgrind ./prog) nebo přepínač -fsanitize=address, který zapíná kontrolu paměti přímo v překladači.

Vyber

Zásobník, nebo halda

Doplň

Doplň

Spoj dvojice

Spoj pojem s významem

Roztřiď

Chyba, nebo v pořádku

Kvíz

Jak se přistupuje k členu vek přes ukazatel p na strukturu?

Kvíz

Kolik bajtů vyžádá malloc(10 * sizeof(int)) na systému, kde má int 4 bajty?

Kvíz

Co je únik paměti?

Kvíz

Co je lepší pro pole, jehož velikost zjistíš až za běhu a které má přežít návrat z funkce?

Pod kapotou · Zarovnání, flexibilní pole a union

Překladač zarovnává členy struktury na násobky jejich velikosti, takže pořadí členů ovlivňuje velikost: char, int, char zabere typicky 12 bajtů, kdežto int, char, char jen 8. Standard od C99 umožňuje flexibilní člen pole na konci struktury (int data[];), do kterého se alokuje potřebné místo jedním malloc. Podobná je unie (union): všechny členy sdílejí stejné místo v paměti, zabere se velikost největšího a platný je vždy jen jeden z nich. Používá se třeba pro hodnoty, které mohou mít různé typy. Typické chyby v práci s haldou hledá spolehlivě AddressSanitizer (gcc -fsanitize=address -g prog.c).

Kartičky

Opakování