Sablon metaprogramozás II.

A laborokhoz

A laborok mellé minden héten lesz kiírva egy beadandó az admin portálon. Ide óra végén töltsd fel a forráskódokat (*.cpp, *.h)! A feladatokat ezért külön projektben oldd majd meg, ne írd felül a megoldásokat.

Labor otthoni munkában

A labor teljesítéséhez legalább az első három feladatot meg kell oldani.

Javaslat a munkához: sablon kódot kell írni. Számíts arra, hogy rengeteg lesz hiba esetén a hibaüzenet, és nem lesznek túl informatívak! Ne találgass-tippelgess... Legyél szuper figyelmes a szintaxissal kapcsolatban!

A Fibonacci-féle sorozat definíciója az alábbi:

     ┌
     │ n, ha n<2
F(n) ┤
     │ F(n-2)+F(n-1), amúgy
     └

Fibonacci, mint régen

Írj egy egyszerű, rekurzív C++ függvényt, amely meghatározza az n-edik számot! Írasd ki egy ciklusban az első negyven számot! Magyarázd meg, hogy a negyvenedik szám felé közelítve miért lesz egyre lassabb a kiírás! Van ötleted, hogyan lehetne gyorsítani?

fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
...
fib(38) = 39088169
fib(39) = 63245986
fib(40) = 102334155

Fibonacci, sablon metaprogramozással I.

Írj most C++ sablon metaprogramozást használó programot, amely valamely Fibonacci számot számítja ki! A megírt kód egy osztályt kell tartalmazzon, amelynek sablonparamétere, hogy a sor hányadik elemére vagyunk kíváncsiak. Így:

/* ... */

int main() {
    std::cout << Fib<40>::value << std::endl;
}

Írd ki így a negyvenedik, és az ötvenedik számot! Hogyan lehetséges az, hogy az ötvenedik számot fordítási időben kiszámoló program lefordítása ugyanolyan gyors, mint a negyvenediket vagy a huszadikat kiszámolóé?

template <int n>
struct Fib {
    static constexpr unsigned long long value = Fib<n-1>::value + Fib<n-2>::value;
};


template <>
struct Fib<0> {
    static constexpr unsigned long long value = 0;
};


template <>
struct Fib<1> {
    static constexpr unsigned long long value = 1;
};

Fibonacci, sablon metaprogramozással II.

Sablonokat példányosítani csak fordítási időben lehet, mert a sablonparamétereknek fordítási idejű konstansoknak kell lenniük. Emiatt ez a kód nem működhet, mivel a for() ciklus futási időben dolgozna:

int main() {
    for (int i = 0; i <= 40; ++i)
        std::cout << Fib<i>::value << std::endl;    // nem működik
}

Hogyan lehetne olyan programot írni mégis sablon metaprogramozással, amely az első feladathoz hasonlóan kiírja az első negyven tagját a sorozatnak? Írj egy ilyet!

template <int i>        /* "ciklusváltozó" */
void print_fib() {
    std::cout << "fib(" << i << ") = " << Fib<i>::value << std::endl;   /* "ciklustörzs" */
    print_fib<i+1>();   /* ++i */
}


template <>
void print_fib<41>() {
                        /* i <= 40 */
}


int main() {
    print_fib<0>();     /* i = 0 */
}

Az előadáson láttuk, hogy bizonyos feladatoknál a szokványos, általános rekurzív megoldást érdemes jobbrekurzívra átírni. A jobbrekurzióban a rekurzív függvényhívás után, a rekurzióból kifelé jövet, már nem csinálunk semmit: az ilyen függvények

T f() {
    ...;
    return f();
}

/* nem jobbrekurzív, mert fact(n-1)
 * után még van egy n* szorzás! */
int fact(int n) {
    if (n == 0)
        return 1;
    else
        return n*fact(n-1);
}

/* jobbrekurzív */
int fact(int n, int acc) {
    if (n == 0)
        return acc;
    else
        return fact(n-1, acc*n);
}

int fact(int n) {
    return fact(n, 1);
}

Alakítsd jobbrekurzívvá a lenti függvényt! Írd meg sablon metaprogramozással is: pl. PowInt<2, 10>::value értéke legyen 1024!

int powint(int base, unsigned exp) {
    return exp == 0 ? 1 : base * powint(base, exp-1);
}

#include <iostream>

int powint(int base, unsigned exp, int acc) {
    return exp == 0 ? acc : powint(base, exp-1, base*acc);
}
int powint(int base, unsigned exp) {
    return powint(base, exp, 1);
}

template <int base, unsigned exp, int acc>
struct PowIntHelper : PowIntHelper<base, exp-1, base*acc> {
    /* megoldható lenne példányosítással is, lásd a következő feladat megoldását */
};
template <int base, int acc>
struct PowIntHelper<base, 0, acc> {
    static constexpr int value = acc;
};

template <int base, unsigned exp>
struct PowInt {
    static constexpr int value = PowIntHelper<base, exp, 1>::value;
};

int main() {
    std::cout << powint(2, 10) << std::endl;
    std::cout << PowInt<2, 10>::value;
}

Adott alább Euklidész legnagyobb közös osztót számító, iteratív algoritmusa. Írd meg ezt jobbrekurzív formában! (Figyeld meg a t változó szerepét! Fog az kelleni?) Írd meg ezt is sablon metaprogramként is!

int gcd(int a, int b) {
    while (b > 0) {
        int t = b;
        b = a % b;
        a = t;
    }
    return a;
}

#include <iostream>

int gcd(int a, int b) {
    if (b > 0)
        return gcd(b, a % b);
    else
        return a;
}

template <int a, int b>
struct GCD {
    /* megoldható lenne örökléssel is, lásd az előző feladat megoldását */
    static constexpr int value = GCD<b, a % b>::value;
};
template <int a>
struct GCD<a, 0> {
    static constexpr int value = a;
};

int main() {
    std::cout << gcd(30, 12) << std::endl;
    std::cout << GCD<30, 12>::value << std::endl;
}

Adott az alábbi maximumkeresés:

#include <iostream>

int greatest(int arr[], int size) {
    int max = arr[0];
    for (int i = 1; i != size; ++i)
        if (arr[i] > max)
            max = arr[i];
    return max;
}

int main() {
    int a[] = { 4, 87, 2, 65, 89, 1 };
    std::cout << greatest(a, 6) << std::endl;
}

Írd át ezt rekurzív függvénnyé! Egy számsor legnagyobb eleme megegyezik az első elemmel, vagy a többi elem közül a legnagyobbikkal. A függvényednek nem kell jobbrekurzívnak lennie, sőt a későbbi feladat egyszerűbb is, ha nem jobbrekurzívat írsz.

int greatest(int arr[], int size) {
    if (size == 1)
        return arr[0];
    else
        return std::max(arr[0], greatest(arr+1, size-1));
}

int main() {
    int a[] = { 4, 87, 2, 65, 89, 1 };
    std::cout << greatest(a, 6) << std::endl;
}

Ennek tapasztalataiból kiindulva, írj sablon metaprogramot, amelyikben a Greatest nevű metafüggvény a sablonparaméterei közül kiválasztja a legnagyobb egész számot! Pl. Greatest<3, 9, 8, 5>::value értéke 9 kell legyen.

#include <iostream>

template <int A, int B>
class Max {
    public:
        static constexpr int value = A>B ? A : B;
};

template <int HEAD, int ... TAIL>
class Greatest {
    public:
        static constexpr int value = Max<HEAD, Greatest<TAIL...>::value>::value;
};

template <int HEAD>
class Greatest<HEAD> {
    public:
        static constexpr int value = HEAD;
};


int main() {
    std::cout << Greatest<4, 87, 2, 65, 89, 1>::value << std::endl;
}

Mit csinál az alábbi függvény? Az általa visszaadott függvény, amely hívásmódjában kompatibilis az első paramétereként megadott függvénnyel (ugyanolyan paraméterek és visszatérési érték), miben viselkedik másképpen? Írj kódot a működés bemutatására!

template <typename RET, typename... ARGS>
auto memoized_func(RET (*func)(ARGS...)) -> std::function<RET(ARGS...)> {
    std::map<std::tuple<ARGS...>, RET> retvals;

    auto memoized = [=] (ARGS... args) mutable -> RET {
        auto args_tuple = std::make_tuple(args...);
        auto found = retvals.find(args_tuple);
        if (found != retvals.end())
            return found->second;

        auto retval = func(args...);
        retvals.insert(make_pair(args_tuple, retval));
        return retval;
    };

    return memoized;
}

Extra kérdések: Mikor érdemes ilyet használni? Mikor nem szabad ilyet használni?

double sin_with_print(double x) {
    std::cout << "sin_with_print(x) called\n";
    return sin(x);
}

int main() {
    auto msin = memoized_func(sin_with_print);
    std::cout << msin(1.0) << std::endl;
    std::cout << msin(1.0) << std::endl;
    std::cout << msin(2.0) << std::endl;
    std::cout << msin(2.0) << std::endl;
    std::cout << msin(1.0) << std::endl;
    std::cout << msin(1.0) << std::endl;
}

sin_with_print(x) called
0.841471                sin(1.0) először
0.841471
sin_with_print(x) called
0.909297                sin(2.0) először
0.909297
0.841471
0.841471

Mit csinál ez a két osztálysablon? Próbáld ki, hogy példányosítod valamilyen kicsi egész számmal (papíron vagy jegyzettömbben)! Pl. mivel egyenértékű a gens<4>::type belső típus?

template<int ...>
struct seq { };

template<int N, int ...S>
struct gens : gens<N-1, N-1, S...> { };

template<int ...S>
struct gens<0, S...> {
    using type = seq<S...>;
};

/* gens<4> -> N = 4, S = üres */
class gens<4> : gens<3, 3> { };

/* gens<3, 3> -> N = 3, S = 3 */
class gens<3, 3> : gens<2, 2, 3> { };

/* gens<2, 2, 3> -> N = 2, S = 2, 3 */
class gens<2, 2, 3> : gens<1, 1, 2, 3> { };

/* gens<1, 1, 2, 3> -> N = 1, S = 1, 2, 3 */
class gens<1, 1, 2, 3> : gens<0, 0, 1, 2, 3> { };

/* gens<0, 0, 1, 2, 3> -> specializáció! nincs N, S = 0, 1, 2, 3 */
class gens<0, 1, 2, 3> {
    using type = seq<0, 1, 2, 3>;
};

Az std::tuple osztálysablonnak bármennyi sablonparamétere lehet: az ott megadott típusú adatokat tudja eltárolni. Pl. std::tuple<int, double> egy egész és egy valós számot tárol. Ha adott egy ilyen objektum t néven, std::get<0>(t) veszi ki belőle az egész számot, std::get<1>(t) pedig a valósat.

Tegyük fel, hogy van egy függvényük, amely épp egy int és egy double paramétert vár. És azt, hogy van egy tuple-ünk, amelyben egy egész és egy valós szám van. A feladat: meghívni a függvényt a tuple-ben tárolt adatokkal. Egészen pontosan, a feladat: írni egy olyan osztályt, amely képes eltárolni egy tetszőleges típusú (paraméterezésű) függvényre mutató pointert, továbbá a függvény paraméterezésének megfelelő objektumokat tartalmazó tuple-t – hogy aztán valamikor azt a függvényt, azokkal a paraméterekkel, meg lehessen hívni. Így tetszőlegesen eltárolható egy „felparaméterezett” függvény, hogy később, egy tetszőelges időpontban meg lehessen hívni.

Az alábbi kód ezt a problémát oldja meg. Elemezd a kódot, értsd meg a működését!

#include <tuple>
#include <iostream>


template<int ...> struct seq {};
template<int N, int ...S> struct gens : gens<N-1, N-1, S...> {};
template<int ...S> struct gens<0, S...>{ using type = seq<S...>; };


double foo(int x, float y, double z) {
    return x + y + z;
}


template <typename Ret, typename ...Args>
struct save_it_for_later {
    Ret (*func)(Args...);
    std::tuple<Args...> params;

    template<int ...S>
    Ret callFunc(seq<S...>) {
        return func(std::get<S>(params) ...);
    }

    Ret delayed_dispatch() {
        return callFunc(typename gens<sizeof...(Args)>::type());
    }
};


int main(void) {
    std::tuple<int, float, double> t = std::make_tuple(1, 1.2, 5);
    save_it_for_later<double, int, float, double> saved = {foo, t};

    std::cout << saved.delayed_dispatch() << std::endl;
}

A C++14 tartalmaz ehhez hasonló eszközöket is.