Přidej si svou IT školu do profilu a najdi spolužáky zde na síti :)

13. díl - Šablony - pokračování

C a C++ C++ Pokročilé konstrukce v C++ Šablony - pokračování

ONEbit hosting Unicorn College Tento obsah je dostupný zdarma v rámci projektu IT lidem. Vydávání, hosting a aktualizace umožňují jeho sponzoři.

V minulém díle, Šablony, jsme si naimplementovali dynamické pole pomocí šablon. Díky tomu toto pole můžeme použít pro libovolný typ a nemusíme každý případ implementovat zvlášť. Dnes si ukážeme, jak to celé zabalit do struktury a pokusíme se ušetřit trochu paměti optimalizací pro typ bool.

Šablonové struktury

Stejně tak, jako můžeme mít šablonovou funkci, můžeme mít i šablonovou strukturu (v OOP se naučíme tvořit i šablonové třídy). Logika je naprosto stejná - použijeme template<typename T> a všechny výskyty typu, který chceme parametrizovat, nahradíme T. Naše dynamické pole ještě trochu zobecníme a do šablony vložíme jako parametr i typ hodnot, které budou určovat velikost a zaplnění pole. Můžeme mít tedy jedno pole, pro které bude velikost určena celými čísly a druhé pole, o kterém víme, že nebude obsahovat mnoho prvků a tak nám budou stačit menší hodnoty. Implementaci si můžete prohlédnout:

template<typename T, typename NUM = int>
struct dynamicke_pole
{
     T* pole;
     NUM velikost;
     NUM kapacita;
};

A odpovídající implementaci pro vložení prvku:

template<typename T, int VELIKOST = 8, int ZVETSENI = 2, typename NUM = int>
void pridej_prvek(T prvek, dynamicke_pole<T,NUM> &dyn_pole)
{
     //vytvarime nove pole
     if(dyn_pole.pole == NULL)
     {
          dyn_pole.pole = new T[VELIKOST];
          dyn_pole.kapacita = VELIKOST;
           dyn_pole.pole[0]=prvek;
          dyn_pole.velikost=1;
          return;
     }
     //pole je jiz plne - musime ho zvetsit
     if(dyn_pole.kapacita == dyn_pole.velikost)
     {
          T* vytvoreno = new T[dyn_pole.kapacita * ZVETSENI];
          dyn_pole.kapacita = dyn_pole.kapacita * ZVETSENI;
          for(int i=0;i<dyn_pole.velikost;i++)
               vytvoreno[i]=dyn_pole.pole[i]; //zkopírování původního pole
          delete [] dyn_pole.pole;
          vytvoreno[dyn_pole.velikost]=prvek;
          dyn_pole.velikost++;
          dyn_pole.pole = vytvoreno;
          return;
     }
     //je dostatek mista
     dyn_pole.pole[dyn_pole.velikost]=prvek;
     dyn_pole.velikost++;
}

Do šablonových parametrů jsem musel přidat i typ čísel (šablonový parametr NUM), protože pokud je v parametru funkce šablonová struktura, musíme specifikovat její typ. Také si všimněte, že jsem šablonový parametr NUM dal až na poslední místo. Je praděpodobnější, že uživatel bude chtít nastavit velikost popřípadě zvětšení, než typ pro uložení hodnot. Kompilátor si navíc poslední parametr dokáže vydedukovat automaticky. Nakonec jen malá poznámka - strukturu přijímáme jako referenci, můžeme ji tedy uvnitř funkce měnit.

Použití je stejně jednoduché jako u předchozí lekce.

Pozn.: Protože místní kompilátor neumožňuje standard C++11, ukázka zde nepůjde spustit. Příklad je připravený zde.

    dynamicke_pole<int> p;
    p.pole = NULL;
    for(int i=0; i<10;i++)
        pridej_prvek(i*2, p);

    cout << "Hodnoty: ";
    for(int i=0;i<p.velikost;i++)
        cout << p.pole[i] << " ";
    cout << endl << "Velikost: " << p.velikost << ", kapacita: " << p.kapacita << endl;
Konzolová aplikace
Hodnoty: 0 2 4 6 8 10 12 14 16 18
Velikost: 10, kapacita: 16

Specializace šablon

V některých případech chceme mít speciální implementaci pro konkrétní typ. Například víme, že typ bool má ve skutečnosti velikost 1 bajt. To je trochu zbytečné, když pro reprezentaci pravda/nepravda by nám stačil jeden bit. Po našem dynamickém poli bychom tedy mohli požadovat, aby se pro typ bool chovala efektivně. Díky specializaci šablon toho můžeme dosáhnout.

Implementaci je poněkud náročnější, proto si ji rozebereme detailněji. Všechen existující kód zůstane. Přidáme implementaci specializace, která vypadá shodně s šablonou, ale má již nadefinované některé typy. Například naše struktura by pro typ bool vypada takhle:

Pozn.: Je potřeba přidat knihovnu cstdint. Proč, to si řekneme později.

template<typename NUM>
struct dynamicke_pole<bool, NUM>
{
    uint8_t* pole;
    NUM velikost;
    NUM kapacita;
};

Vidíme, že nám zmizel šablonový parametr a je napevno nastaven u struktury. U specializace se nenastavují výchozí hodnoty pro parametry šablony (použijí se ty z obecné deklarace) - proto není nastaven parametr NUM na int. Pokud by vás zajímalo, jak by vypadala specializace pro typ <bool,int>, pak následovně:

template<>
struct dynamicke_pole<bool, int>
{
    uint8_t* pole;
    int velikost;
    int kapacita;
};

Nyní se ještě na chvíli vrátím k tomu, proč je použit nový typ uint8_t. Pro typ bool chceme použít pouze jeden bit k uchování informace, ale nejmenší velikost, ke které se program může dostat, je 1 bajt. Cokoliv menšího je potřeba získat z bajtu pomocí binárních operací. Máme ale ten problém, že nemám typ, od kterého bychom se mohli odrazit. Ačkoliv typ char má obvykle velikost 1 bajt, není nikde zaručeno, že tak bude vždy a všude. Pokud potřebujeme přesnou velikost, je typ uint8_t z knihovny cstdint přesně pro nás, protože jeho velikost bude vždy a všude 8 bitů (tedy 1 bajt).

Specializace dynamického pole pro bool

Jak tedy získat konkrétní bit? Představme si pole bajtových hodnot a my budeme chtít získat bit na 11 pozici.

|xxxxxxxx|xxx1xxxx|

Nejdříve index vydělíme 8 - tím dostaneme index v poli, ve kterém je bit obsažen (v našem případě 11/8=1 tedy hledaný bit je ve druhé přihrádce). Následně index zmodulíme 8 a tím získáme pozici v přihrádce (v našem případě 11%8=3 tedy na 4. pozici, protože indexujeme od 0). Když víme, na které pozici bit je, můžeme hodnotu binárně posinout nejdříve doleva a poté doprava - tím se bit stane 1. bitem zprava a na zbývajících místech budou 0.

|xxx1xxxx| << 3   -->     |1xxxx000|
|1xxxx000| >> 7   -->     |00000001|

Poté už je snadné zjistit, zda je bit nastaven. Kvůli tomuto algoritmu ale musíme implementovat funkci pro získání prvoku i pro ostatní typy. Naštěstí je jednoduchá a kompletní implementaci se můžete podívat zde:

template<typename T, typename NUM>
T ziskej(int index, const dynamicke_pole<T,NUM> &from)
{
    return from.pole[index];
}

template<typename NUM>
bool ziskej(int index, const dynamicke_pole<bool,NUM> &from)
{
    int bajt = index / 8;
    int bit = index % 8;
    uint8_t hodnota_bajtu = from.pole[bajt];
    hodnota_bajtu = hodnota_bajtu << bit;
    hodnota_bajtu = hodnota_bajtu >> 7;
    return hodnota_bajtu == 1;
}

Samozřejmě musíme také specializovat funkci pro přidání nového prvku. Abych ušetřil místo, tak ji zde nebudu popisovat (logika je stejná jako pro získání prvku) a její implementace bude v následující ukázce.

Ve většině případů je potřeba specializovat všechny funkce, které s šablonou souvisí. Specializace tedy není úplně zadarmo. Nakonec přidávám ukázku fungování, kterou si můžete naživo spustit zde.

dynamicke_pole<bool> p;
p.pole = NULL;
for(int i=2; i<32;i++)
    pridej_prvek(je_prvocislo(i), p);

cout << "Hodnoty: ";
for(int i=0;i<p.velikost;i++)
    cout << ziskej(i, p) << " ";
cout << endl << "Velikost: " << p.velikost << ", kapacita: " << p.kapacita << endl;
Konzolová aplikace
Hodnoty: 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 1
Velikost: 30, kapacita: 32

Poznámky na závěr

Pokud přicházíte z vyšších programovacích jazyků, potom vám mohou šablony připomínat genericitu - minimálně syntaxe je velmi podobná. Do jisté míry máte pravdu, ale šablony a generické funkce mají jeden obrovský rozdíl - šablonu pro určitý typ se generuje během kompilace, zatímco u genericity se konkrétní typ generuje až během běhu. To má dva důsledky - za prvé se nemůžeme run-time rohodnout, která verzi šablony použijeme. Toto rozhodnutí musí být provedeno již během kompilace. Z toho plyne, že všechny vygenerované šablony jsou zabaleny v .exe souboru jako konkrétní typy. Pro každý použitý typ se vygeneruje vlastní šablona, takže ve výsledném .exe souboru může být například 10 typů vycházející ze stejné šablony. To u jazyků jako C# nebo Java neplatí, protože tam se konkrétní typy z těch generických generují až za běhu, takže generický typ je v .exe souboru pouze jednou.

Jak si řekneme v příštím díle, kompilátor při kompilaci potřebuje vědět typy parametrů a návratovou hodnotu, aby dokázal vyhradit dostatek místa na zásobníku. To u šablon nejde, protože typ ještě není známý. Nemůžeme ani žádnou část šablony předvygenerovat, protože kompilátor nezná velikosti, které potřebuje. Z toho důvodu musí být šablony i s implementací v hlavičkovém souboru (končící .h). Pokud jste si zvykli deklaraci a implementaci rozdělovat do hlavičkových a implementačních souborů (.h a .cpp soubory), je to super a určitě to tak dělejte dál, ale v případě šablon to (z výše uvedených důvodů) nejde a je nutné je mít včetně implementace v hlavičkových souborech.

Tím jsme ukončili praktickou část tohoto seriálu. Příští a zároveň i poslední díl bude spíše teoretický a bude se týkat kompilace.


 

 

Článek pro vás napsal patrik.valkovic
Avatar
Jak se ti líbí článek?
Ještě nikdo nehodnotil, buď první!
Věnuji se programování v C++ a C#. Kromě toho také programuji v PHP (Nette) a JavaScriptu (NodeJS).
Miniatura
Předchozí článek
Šablony
Miniatura
Všechny články v sekci
Pokročilé konstrukce C++
Miniatura
Následující článek
Kompilace v jazyce C a C++
Aktivity (2)

 

 

Komentáře

Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zatím nikdo nevložil komentář - buď první!