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

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

    #ifndef ODMENA_HPP_INCLUDED
    #define ODMENA_HPP_INCLUDED
 
    ...
 
    #endif

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

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

  • 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é.

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

  • 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. one definition rule), a definice se musí vyskytovat v různých kompilačních jednotkách.

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

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

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

  • 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é 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.

  • Stáhněte si 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.

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

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

  • Přeložte uvedený program do objektového souboru g++ -c main.cpp -o main.o. Prohlédněte si obsah objektového souboru programem nm (ve Windows dumpbin) a zjistěte, zda a jak je v tomto souboru zapsáno pole druhých mocnin.

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.

  • Modifikujte program tak, aby pole obsahovalo tabulku třetích mocnin.
  • Modifikujte pole tak, aby obsahovalo seznam prvočísel (2, 3, 5, 7, 11, 13, …).

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

  • 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?

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

  • 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.
2)
to znamená, dostaneme alespoň Forward Iterátory
courses/b6b36pcc/cviceni/cviceni-10.txt · Last modified: 2023/08/30 09:55 by nagyoing