Table of Contents

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

Prúvodce studiem Šablony jsou základem obecného programování v jazyce C++. Jako jazyk se silným typem vyžaduje jazyk C++, aby všechny proměnné měly určitý typ, a to buď explicitně deklarovaný programátorem, nebo vyvolaný kompilátorem. Mnoho datových struktur a algoritmů ale vypadá stejně bez ohledu na to, na jakém typu pracují. Šablony umožňují definovat operace třídy nebo funkce a umožnit uživateli určit konkrétní typy těchto operací.

Opakování: Hlavičkové soubory

    #ifndef ODMENA_HPP_INCLUDED
    #define ODMENA_HPP_INCLUDED
 
    ...
 
    #endif

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

    // odmena.hpp
 
    struct Osoba;
 
    enum class Odmena {
        chlebicky, cokolada
    };
 
    Odmena odmenaPro(const Osoba& zaslouzilec);

    // util.hpp
 
    inline int maximum(int a, int b) {
    return (a > b) ? a : b;
    }

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

Š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é prezentaci nebo na 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.

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.

Ř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.

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

#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';
}

Řešení

Metaprogramování - úvod

Tento kousek kódu1) vygeneruje tabulku druhých mocnin celých čísel. 

#include <iostream>
#include <array>
 
constexpr int TABLE_SIZE = 10;
 
/**
 * Variadic template for a recursive helper struct.
 */
template<int INDEX = 0, int ...D>
struct Helper : Helper<INDEX + 1, D..., INDEX * INDEX> { };
 
/**
 * Specialization of the template to end the recursion when the table size reaches TABLE_SIZE.
 */
template<int ...D>
struct Helper<TABLE_SIZE, D...> {
  static constexpr std::array<int, TABLE_SIZE> table = { D... };
};
 
constexpr std::array<int, TABLE_SIZE> table = Helper<>::table;
 
int main() {
  for (int i=0; i < TABLE_SIZE; i++) {
    std::cout << table[i]  << std::endl; // run time use
  }
}

Úkoly k procvičení

Pole je vytvořeno již během kompilace a jeho obsah je přístupný na začátku programu bez dalšího volání funkcí, které by pole vytvářely.

Řešení

Metaprogramování

Máme připravený (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: 

#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';
}
Základní implementace je jednoduchá: 
template <typename T>
class vector {
public:
    ...
    template <typename InputIterator>
    void push_back(InputIterator from, InputIterator to) {
        while (from != to) {
            push_back(*from);
            ++from;
        }
    }

Úkoly k procvičení 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žit2).

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.

Řešení

Algoritmy

Úkoly k procvičení 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:

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í.

1)
Přejato z https://en.wikipedia.org/wiki/Template_metaprogramming#Static_Table_Generation
2)
to znamená, dostaneme alespoň Forward Iterátory