{{page>courses:b6b36pjc:styles#common&noheader&nofooter}}
{{page>courses:b6b36pjc:styles#cviceni&noheader&nofooter}}

===== Cvičení 10: Šablony a základy metaprogramování =====

==== Opakování: Co přijde do hlavičkových souborů ====

  * Hlavičkový soubor by měl být chráněn proti opakovanému vložení.

<code cpp>
    #ifndef ODMENA_HPP_INCLUDED
    #define ODMENA_HPP_INCLUDED

    ...

    #endif
</code>

  * Deklarace funkcí. (Definice funkcí patří do zdrojových souborů.)
    * Pokud umístíme definici do hlavičkového souboru, nastane chyba, jakmile je daný hlavičkový soubor použit ve dvou nebo více zdrojových souborech.

<code cpp>
    // odmena.cpp

    Odmena odmenaPro(const Osoba& zaslouzilec) {
        if (zaslouzilec.povolani == Povolani::cukrar) return Odmena::chlebicky;
        return Odmena::cokolada;
    }
</code>

  * Deklarace funkcí, které chceme zpřístupnit ostatním zdrojovým souborům, patří do hlavičkových souborů.
    * Typy, které jsou v deklaraci funkce použity, musí být už deklarované.

<code cpp>
    // odmena.hpp

    struct Osoba;

    enum class Odmena {
        chlebicky, cokolada
    };

    Odmena odmenaPro(const Osoba& zaslouzilec);
</code>

  * Definice funkcí označených klíčovým slovem ''inline'' je povoleno umístit do hlavičkových souborů.
    * Takovéto funkce je povoleno definovat opakovaně, pokud jsou splněny dvě podmínky: všechny definice dané funkce musí být identické (viz. [[https://en.wikipedia.org/wiki/One_Definition_Rule|one definition rule]]), a definice se musí vyskytovat v různých kompilačních jednotkách.

<code cpp>
    // util.hpp

    inline int maximum(int a, int b) {
    return (a > b) ? a : b;
    }
</code>

  * Metody definované uvnitř deklarace třídy jsou implicitně označeny jako ''inline''. Proto nevadí, když jsou umístěny v hlavičkových souborech.

<code cpp>
    // osoba.hpp

    struct Osoba {
        int kolikTiJe() {
            if (pohl == Pohlavi::zena) return (4 * vek) / 5;
            else return vek;
        }
        ...
    };
</code>

  * Co chybí?

==== Šablony ====

V dnešním cvičení si hlavně budeme procvičovat psaní šablon. O tom, co šablony
jsou a jak fungují, se můžete dozvědět v přednáškové
[[courses:a7b36pjc:prednasky:start|prezentaci]] nebo na
[[http://www.codingnest.com/programovani-se-sablonami/|této stránce]]. Začneme u
našeho dobrého známého -- vektoru. Pro účely tohoto cvičení je redukovaný a
některé metody, které jsme již jednou implementovali v něm nejsou.

  * Stáhněte si {{:courses:b6b36pjc:cviceni:cviceni_10_init.zip|výchozí kód}} pro dnešní cvičení.
  * Nahraďte funkce v souboru ''array.cpp'' ''copy_array'', ''print_array'', ''resize_array'' šablonami funkcí tak, aby funkce přijímaly libovolný typ pole.

Nezapomeňte, že šablony musí být umístěny v hlavičkovém souboru, jinak zpravidla
dojde k chybě. Přesuňte tedy všechny funkce do souboru ''array.hpp''.

{{:courses:b6b36pjc:cviceni:cviceni_10_array.zip|Řešení}}

Nyní máme k dispozici všechny nástroje k tomu, abychom mohli konečně vytvořit
šablonu třídy ''vector'', která přijme libovolný typ.

  * Nahraďte třídu ''vector'' šablonou třídy ''vector''.

Chtěli bychom, aby fungoval následující kód:

<code cpp>
#include "vector.hpp"
#include <string>
#include <iostream>
#include <algorithm>

int main() {
    vector<double> v;
    v.push_back(4.56);
    v.push_back(7.89);
    v.push_back(1.23);
    std::sort(v.begin(), v.end());
    std::cout << v << '\n';

    vector<std::string> u;
    u.push_back("def");
    u.push_back("ghi");
    u.push_back("abc");
    std::sort(u.begin(), u.end());
    std::cout << u << '\n';
}
</code>

{{:courses:b6b36pjc:cviceni:cviceni_10_vector.zip|Řešení}}

=== Metaprogramování ===
Nyní máme (redukovaný) šablonový vektor, ale rádi bychom přidali ještě jednu
možnost použití, kdy se do vektoru najednou přidá více prvků z jiné kolekce nebo
range. Zkrátka bychom chtěli, aby tento kód též fungoval:
<code cpp>
#include "vector.hpp"
#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<double> vec {1.21, 3.42, 5.123, 4.232, 9.9};
    vector<double> v;
    v.push_back(4.56);
    v.push_back(7.89);
    v.push_back(1.23);
    v.push_back(begin(vec), end(vec)); // Přidá nakonec všechny prvky z vec
    // v.push_back(std::istream_iterator<double>(std::cin), std::istream_iterator<double>()); -- takto se dají načítat čísla přímo ze stdin
    std::sort(v.begin(), v.end());
    std::cout << v << '\n';
}
</code>
Základní implementace je jednoduchá:
<code cpp>
template <typename T>
class vector {
public:
    ...
    template <typename InputIterator>
    void push_back(InputIterator from, InputIterator to) {
        while (from != to) {
            push_back(*from);
            ++from;
        }
    }
</code>

Náš vektor nyní umí přidat více prvků najednou, ale implementace šablonové
metody ''vector::push_back(InputIterator from, InputIterator to)'' je velmi
primitivní a šla by zlepšit. Například bychom mohli zaručit, že dojde maximálně
k jedné alokaci během jednoho volání range ''push_back'', pokud si můžeme předem
spočítat kolik nových prvků musíme vložit((to znamená, dostaneme alespoň Forward
Iterátory)).

Protože to ale nejde udělat se všemi iterátory, musíme použit metaprogramování,
aby se během kompilace zavolala správná metoda.

  * Naimplementujte ''private'' metody ''push_back'', které slouží k implementaci veřejné metody ''push_back'' pro různé iterátory (Nezapomeňte: pro InputIterator nemůžeme posunout iterátor, aniž bychom navždy zahodili data na která ukazuje).
  * Mezi kolika implementacemi ''push_back'' musíme rozhodovat pro optimální chování? Šlo by to zjednodušit?

{{:courses:b6b36pjc:cviceni:cviceni_10_tmp.zip|Řešení}}

==== Algoritmy ====

Vyzkoušíme si úpravu funkcionality algoritmu ''std::sort''. Jako třetí parametr
tato šablonová funkce očekává //komparátor//; komparátor má za úkol pro dané dva
prvky rozhodnout, zda první je menší než druhý. Predikát může mít několik podob:

  * Použijte jako 3. parametr ''std::sort'' ukazatel na takovou funkci, aby pole bylo seřazené sestupně.
  * Použijte jako 3. parametr ''std::sort'' takový funkční objekt, aby pole bylo seřazené sestupně.
  * Použijte jako 3. parametr ''std::sort'' takovou lambda funkci, aby pole bylo seřazené sestupně.
  * Použijte jako 3. parametr ''std::sort'' instanci šablony ''std::greater'' z hlavičky ''<functional>''.

Jak docílí ''std::sort'' toho, aby mohl příjímat tak široký výběr komparátorů?
Ukážeme si, jak to udělat u vlastních funkcí.

  * Napište funkci ''is_sorted'', která ověří, zda je kolekce typu ''vector<double>'' seřazená. Kolekci předávajte konstantní referencí.
  * Nahraďte typ kolekce šablonovým parametrem ''Container''.
  * Použijte iterátory namísto kolekce, iterátory předávejte hodnotou. Typ iterátoru určete šablonovým parametrem ''Iterator'', šablonový parametr ''Container'' už nebude potřeba. Použití dvou iterátorů namísto celé kolekce má tu výhodu, že je obecnější - můžeme například ověřit seřazenost pouze části pole.
  * Vytvořte nové přetížení funkce ''is_sorted'', které navíc získá komparátor jako parametr. Typ komparátoru bude určen dalším šablonovým parametrem, ''Comparator''.
  * Vytvořte funkci ''lazy_sort'', která pro dva iterátory nejdříve ověří, zda je pole seřazené pomocí ''is_sorted''. Pokud prvky mezi komparátory seřazené nejsou, ''lazy_sort'' prvky seřadí pomocí ''std::sort''. Vytvořte ''lazy_sort'' s komparátorem a bez komparátoru.