Warning
This page is located in archive.

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

courses:b6b36pjc:cviceni:cviceni_10 [2017/09/25 17:16] (current)
richta created
Line 1: Line 1:
 +<​HTML>​
 +<​style>​
 +.code .kw1, .code .kw2, .code .kw4 { color: #00f; font-weight:​ bold; }
 +.code .br0, .code .kw3, .code .me1, .code .me2, .code .nu0 { color: #000; }
 +.code .co1, .code .coMULTI { color: #080; font-style: normal; }
 +.code .co2 { color: #888; font-style: normal; }
 +.code .st0 { color: #a31515; }
 +</​style>​
 +</​HTML>​
  
 +===== 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:​a7b36pjc:​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:​a7b36pjc:​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:​a7b36pjc:​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:​a7b36pjc:​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.
courses/b6b36pjc/cviceni/cviceni_10.txt · Last modified: 2017/09/25 17:16 by richta