Získej svůj iPhone v nové soutěži! Získej svůj iPhone v nové soutěži!
Nová překladatelská soutěž ITnetwork.cz o telefon iPhone, sluchátka Beats a další věcné ceny za 4 hodiny práce.
Přidej si svou IT školu do profilu a najdi spolužáky zde na síti :)

14. 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ě posunout 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í prvku i pro ostatní typy. Naštěstí je jednoduchá a na 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 (3)

 

 

Komentáře

Avatar
Mate
Člen
Avatar
Mate:23. srpna 19:52

Dobrý den, chtěl bych se zeptat, proč mi výše uvedený kód dynamického pole nefunguje? NetBeans mi píše tento výpis:

cd 'C:\Users\Mate\Do­cuments\NetBe­ansProjects\Sa­blonoveStruktu­ry'
C:\cygwin64\bin\ma­ke.exe -f Makefile CONF=Debug
"/usr/bin/make" -f nbproject/Makefile-Debug.mk QMAKE= SUBPROJECTS= .build-conf
make[1]: Entering directory '/cygdrive/c/U­sers/Mate/Docu­ments/NetBean­sProjects/Sablo­noveStruktury'
"/usr/bin/make" -f nbproject/Makefile-Debug.mk dist/Debug/Cygwin-Windows/sablo­novestruktury­.exe
make[2]: Entering directory '/cygdrive/c/U­sers/Mate/Docu­ments/NetBean­sProjects/Sablo­noveStruktury'
mkdir -p build/Debug/Cygwin-Windows
rm -f "build/Debug/Cygwin-Windows/main.o.d"
g++ -c -g -MMD -MP -MF "build/Debug/Cygwin-Windows/main.o.d" -o build/Debug/Cygwin-Windows/main.o main.cpp
main.cpp:13:59: error: default template arguments may not be used in function templates without -std=c++11 or -std=gnu++11
void pridej_prvek(T prvek, dynamicke_pole<T,NUM> &dyn_pole)
^
main.cpp: In function 'int main()':
main.cpp:47:28: error: no matching function for call to 'pridej_prvek(int, dynamicke_pole<in­t>&)'
pridej_prvek(i*2, p);
^
main.cpp:13:6: note: candidate: template<class T, int VELIKOST, int ZVETSENI, class NUM> void pridej_prvek(T, dynamicke_pole<T, NUM>&)
void pridej_prvek(T prvek, dynamicke_pole<T,NUM> &dyn_pole)
^
main.cpp:13:6: note: template argument deduction/sub­stitution failed:
main.cpp:47:28: note: couldn't deduce template parameter 'VELIKOST'
pridej_prvek(i*2, p);
^
make[2]: *** [nbproject/Makefile-Debug.mk:68: build/Debug/Cygwin-Windows/main.o] Error 1
make[2]: Leaving directory '/cygdrive/c/U­sers/Mate/Docu­ments/NetBean­sProjects/Sablo­noveStruktury'
make[1]: *** [nbproject/Makefile-Debug.mk:59: .build-conf] Error 2
make[1]: Leaving directory '/cygdrive/c/U­sers/Mate/Docu­ments/NetBean­sProjects/Sablo­noveStruktury'
make: *** [nbproject/Makefile-impl.mk:40: .build-impl] Error 2

BUILD FAILED (exit value 2, total time: 1s)

chybu se mi nedaří opravit :/. Děkuji vám za případnou radu

CHYBU UŽ SE MI PODAŘILO OPRAVIT. Pokud by měl někdo stejný problém tak stačí změnit nastavení kompilátoru na standart C++11.

Editováno 23. srpna 19:55
 
Odpovědět 23. srpna 19:52
Avatar
Martin Dida
Člen
Avatar
Martin Dida:21. listopadu 9:05

Zdravim

Pri hladani toho bitu v priklade s dynamickym polom a template funkciou "ziskej", ktora by mala vratit, ci je byt nastaveny alebo nie mate chybu. Uz v popise ako nato hovorite o bite na 11 indexe, zatial co pracujete s bitom na indexe 12

S pozdravom Martin :)

 
Odpovědět 21. listopadu 9:05
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Martin Dida
patrik.valkovic:21. listopadu 10:51

Zdravím. protože se počítá od nuly, jedná se o bit na idnexu 11, což je vlastně 12. bit v pořadí.

Odpovědět 21. listopadu 10:51
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Martin Dida
Člen
Avatar
Odpovídá na patrik.valkovic
Martin Dida:21. listopadu 11:02

Presne ako si napisal
Z tvojho prikladu |xxxxxxxx|xxx1xxxx| tvoj bit '1' je na indexu 11 to hovoris. Dobre berme, ze index 11 je v druhom bajte, lebo prvy bajt obsahuje bity s indexami 0-7 (co je pre ludi lepsie chapatelne 1-8). Takze druhy bajt zacina indexom 8, takze poradie indexov |15,14,13,12,­11,10,9,8| pozri, kde mas vo svojom priklade (vyssie som to znova uviedol) nastavenu '1', ked dobre vidim nie je to na indexe 11 ako tvrdis, ale na index 12 teda poradove cislo 13 kedze to je o jednu viac ako indexy, ktore zacinaju od nuly. A tym padom ani funkcia "ziskej" nie je v poriadku, akurat sedi pre tento pripad.

S pozdravom Martin :)

 
Odpovědět 21. listopadu 11:02
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Martin Dida
patrik.valkovic:21. listopadu 11:19

Ale my indexujeme zleva...tedy |8,9,10,11,12­,13,14,15|. Ano, ve finále ten bit potřebuješ dostat jako prvné zprava (proto je posun doprava druhý), ale indexovat |7,6,5,4,3,2,­1,0|15,14,13,12,11,10,9,­8| přece nedává smysl.

Odpovědět 21. listopadu 11:19
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Martin Dida
Člen
Avatar
Odpovídá na patrik.valkovic
Martin Dida:21. listopadu 11:58

Tak to potom sedi. Aj ked som sa nikdy nestretol s indexovanim BITOV z lava. Viem, ze architektury su little a big endian, kde musis davat pozor na zarovnanie MSB, ale indexovanie bitov viem, ze je z prava s LSb ako prvym. Potom v podstate usetris jednu instrukciu nutnu na posun toho bitu uplne doprava aby si dostal logicku hodnotu. Ale diky za vysvetlenie uz to teraz chapem. Aj ked na nizsom levely programovania trebars pre embedded systemy to moze byt dost matuce ;)

Dik Martin :)

 
Odpovědět 21. listopadu 11:58
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Martin Dida
patrik.valkovic:21. listopadu 12:26

No my se snažíme emulovat pole. V tom případě indexujeme klasicky zleva doprava. Pořadí uložení bitů je nám v tuto chvíli jedno. A posuny stejně budou vždy dva (i když optimalizovat by to šlo - otázka zda se vyplatí nahradit posun podmínkou, když je to přímá instrukce procesoru), protože na druhé straně toho čísla může být hodnota (na pozicích x).

Odpovědět 21. listopadu 12:26
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
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.

Zobrazeno 7 zpráv z 7.