Klase obilježja (traits classes)

Primjer: Napisati predložak funkcije za sumiranje elemenata u spremniku. Uz zadan pokazivač na prvi element spremnika i pokazivač na jedno mjesto iza zadnjeg elementa treba prosumirati sve elemente.

// Prva verzija algoritma.
template <typename T>
T accum(T const* begin, T const* end)
{
    T total = T();  // T() kreira nul vrijednost
    while(begin != end){
        total += *begin;
        ++begin;
    }
    return total;
}

Primjer - glavni program:

int main() {
    // Cjelobrojni niz
    int num[] = {1, 2, 3, 4 ,5 ,6};

    std::cout << "Srednja vrijednost niza je "
              << accum(num, num+6)/6 << std::endl;

    // Znakovne vrijednosti
    char name[]="templates";
    int len = sizeof(name) -1;

    std::cout << "Srednja vrijednost niza je "
              << accum(&name[0], &name[len])/len << std::endl;
}

Na naše iznenađenje izlaz programa će biti

Srednja vrijednost niza je 3
Srednja vrijednost niza je -5

Problem je u tome što accum u drugom slučaju vraća tip char koji je suviše mali za čuvanje sume svih znakova.

Rješenje 1. Uvođenju novog template parametra za povratni tip algoritma (ali, povratni tip se ne može automatski deducirati) koji će se morati eksplicitno zadavati.

Rješenje 2. Uspostaviti vezu između tipa T s kojim je algoritam instanciran i tipa koji treba koristiti za povratnu vrijednost. Tip povratne vrijednosti je ovdje shvaćen kao obilježje (trait) tipa T.

Formirajmo stoga predložak klase AccumTraits koja će sadržavati samo typedef koji daje tip povratne vrijednosti AccT za zadani tip T. U općem slučaju AccT=T, no u raznim posebnim slučajevima tu vrijednost mijenjamo specijalizacijom predloška klase.

Klase obilježja

Klase obilježja (traits classes) donose informacije o tipovima.

// Klasa obilježja tipa T i njene specijalizacije
template <typename T>
class AccumTraits{
    public:
        typedef T AccT;
};

// Eksplicitne specijalizacije
template <>
class AccumTraits<char>{
    public:
        typedef int AccT;
};

template <>
class AccumTraits<short>{
    public:
        typedef int AccT;
};

template <>
class AccumTraits<int>{
    public:
        typedef long AccT;
};
// i tako dalje za ostale tipove

Nova verzija algoritma:

// Druga verzija algoritma.
template <typename T>
inline
typename AccumTraits<T>::AccT accum(T const* begin, T const* end) {
    typedef typename AccumTraits<T>::AccT  AccT;  // pokrata

    AccT total = AccT(); // AccT() kreira nul vrijednost
    while(begin != end){
        total += *begin;
        ++begin;
    }
    return total;
}

Program sada korektno ispisuje

Srednja vrijednost niza je 3
Srednja vrijednost niza je 108

Klase obilježja - nastavak

Klase obilježja ne sadrže samo tipove već mogu sadržavati i vrijednosti. Primjer: inicijalizacija varijable total u algoritmu.

// Klasa obilježja tipa T i njene specijalizacije
template <typename T>
class AccumTraits{
    public:
        typedef T AccT;
        static AccT zero() { return T(); }
};

template <>
class AccumTraits<char>{
    public:
        typedef int AccT;
        static AccT zero() { return 0; }
};

template <>
class AccumTraits<short>{
    public:
        typedef int AccT;
        static AccT zero() { return 0; }
};

// i tako dalje za ostale tipove

Nastavak

Algoritam korigiramo na sljedeći način:

// Treća verzija algoritma.
template <typename T>
inline
typename AccumTraits<T>::AccT accum(T const* begin, T const* end)
{
    typedef typename AccumTraits<T>::AccT  AccT;  // pokrata

    AccT total = AccumTraits<T>::zero(); // kreira nul vrijednost
    while(begin != end){
        total += *begin;
        ++begin;
    }
    return total;
}

Nastavak

Fleksibilniji način konstrukcije predloška funkcije accum bio bi onaj u kome bi klasa obilježja bila dana kao parametar funkcije, pri čemu bismo parametru dali defaultnu vrijednost:

#include "accumtraits2.h"

template <typename T,
          typename AT = AccumTraits<T>
          >
inline
typename AT::AccT accum(T const* begin, T const* end) {
    typedef typename AT::AccT  AccT;  // pokrata

    AccT total = AT::zero(); // kreira nul vrijednost
    while(begin != end){
        total += *begin;
        ++begin;
    }
    return total;
}

Akcijske klase (Policy classes)

Naš algoritam veže akumulaciju uz sumaciju, no mogli bismo zamisliti drukčiju primjenu accum() algoritma. On bi mogao, naprimjer, računati produkt brojeva umjesto sume. Da bismo to omogućili uvest ćemo novi parametar koji će predstavljati klasu koja zna koju operaciju treba izvršiti.

//  Verzija algoritma koja je parametrizirana klasom obilježja i
//  akcijskom klasom
template <typename T,
          typename Policy = SumPolicy,
          typename AT = AccumTraits<T>
          >
inline
typename AT::AccT accum(T const* begin, T const* end) {
    typedef typename AT::AccT  AccT;  // pokrata

    AccT total = AT::zero(); // kreira nul vrijednost
    while(begin != end){
        // Neka akcijska klasa izvrši odgovarajuću operaciju
        Policy::accumulate(total, *begin);
        ++begin;
    }
    return total;
}

Nastavak

Različite akcijske klase nude statičku metodu accumulate.

struct SumPolicy{
    template <typename T1, typename T2>
        static void accumulate(T1& total, T2 const& value){ total += value; } };

struct MultPolicy{
    template <typename T1, typename T2>
        static void accumulate(T1& total, T2 const& value){ total *= value; }
};

Ipak naš kod neće funkcionirati korektno s multiplikacijom kao operacijom - dobiveni rezultat uvijek je nula. Razlog je u tome što je inicijalna vrijednost uvijek nula pa je produkt nula.

Logično bi bilo da početnu vrijednost definira klasa akcije, jer ona zna koji je neutralni element njene akcije. Problem je što ona ne zna što je klasa T1.

Jedna od mogućnosti je da inicijalnu vrijednost pri akumulaciji zadamo kao parametar funkcije s defaultnom vrijednošću.

Nastavak

template <typename T,
          typename Policy = SumPolicy,
          typename AT = AccumTraits<T>
          >
inline
typename AT::AccT accum(T const* begin, T const* end, T init = AT::zero()) {
    typedef typename AT::AccT  AccT;  // pokrata

    AccT total = init;
    while(begin != end){
        // Neka akcijska klasa izvrši odgovarajuću operaciju
        Policy::accumulate(total, *begin);
        ++begin;
    }
    return total;
}

Sada će kod

// Cjelobrojni niz
int num[] = {1, 2, 3, 4 ,5 ,6};

std::cout << "Umnožak svih clanova je "
          << accum<int, MultPolicy>(num, num+6, 1) << std::endl;

// Znakovne vrijednosti
char name[]="templates";
int len = sizeof(name) -1;

std::cout << "Srednja vrijednost niza je "
          << accum(&name[0], &name[len])/len << std::endl;

korektno ispisati

Umnožak svih clanova je 720
Srednja vrijednost niza je 108

SFINAE (substitution-failure-is-not-an-error)

SFINAE je princip koji omogućava preopterećenje predložaka funkcija ali ujedno i neke specifične tehnike programiranja. Princip se sastoji u sljedećem:

Kada prevodilac pokušava instancirati funkciju iz više preopterećenih predložaka supstitucija parametra u neke od predložaka dovodi do neuspjeha. Taj neuspjeh nije grešaka već prevodilac nastavlja sa sljedećim predloškom, dok ne uspije instancirati traženu funkciju.

Primjena: identificiramo ima li zadani tip podtip X.

typedef char RT1;
typedef struct{ char a[2]; } RT2;

Zatim definiramo dva predloška funkcije: prvi uzima pokazivač na konstantan podtip X dok drugi uzima sve vrste argumenta (...) — to je C-verzija funkcije s proizvoljnim brojem argumenata za korištenje. Vidi www.cplusplus.com/reference/cstdarg/.

template <typename T> RT1 test(typename T::X const*);
template <typename T> RT2 test(...);

Definirajmo jedan tip koji ima podtip X.

struct VVV{
    typedef int X;
   // ..
};

int main() {
    std::cout << sizeof(test<VVV>(0)) << std::endl;   // ispisuje 1
    std::cout << sizeof(test<double>(0)) << std::endl;  // ispisuje 2
}

Kod funkcionira na sljedeći način:

prevodilac treba odabrati koji će funkcijski predložak instancirati na osnovu parametra (0) koji je tipa const int.
Takav se parametar može konvertirati u pokazivač na const T::X (naravno kao tip T ima podtip X).
Ta konverzija je slabija od konverzije koja je potrebna za funkciju koja uzima proizvoljne parametre (...).

To znači da će prevodilac preferirati test koji vraća RT1 ako T ima podtip X.

Time smo dobili tehniku kojom možemo provjeriti (za vrijeme kompilacije) ima li neki tip podtip X (sizeof daje 1) ili nema (sizeof daje 2). Kao sljedeći korak možemo definirati makro:

#define type_has_memeber_type_X(T) \
    (sizeof(test<T>(0)) == 1)

i koristiti ga na sljedeći način,

type_has_memeber_type_X(double); // daje 0=false
type_has_memeber_type_X(VVV); // daje 1=true

Prepoznavanje klasa

Pomoću pokazane tehnike napisat ćemo kod koji prepoznaje je li zadani tip klasa (korisnički tip) ili nije.

template <typename T>
class IsClassType{
    private:
        typedef char One;
        typedef struct { char a[2]; } Two;
        // "int C::*" je pokazivač na varijablu članicu klase C tipa int
        template <typename C> static One test(int C::*);
        template <typename C> static Two test(...);
    public:
        enum { Yes = sizeof(IsClassType<T>::test<T>(0)) == 1 };
        enum { No = !Yes };
};

template <typename T>
void check()
{
    if(IsClassType<T>::Yes) std::cout << "Klasa\n";
    else                    std::cout << "Nije klasa\n";
}

// Verzija s dedukcijom parametra
template <typename T>
void check(T)
{ check<T>(); }

Napomena. O pokazivaču na varijablu članicu klase (i operatorima .*, ->*) vidi en.cppreference.com/w/cpp/language/pointer.

Primjena:

struct MyStruct{ };
class MyClass{ };
union MyUnion{ };
void myfun(){}
enum MyEnum { e1 };

int main() {
    std::cout << "int: "; check<int>();
    std::cout << "MyStruct: "; check<MyStruct>();
    std::cout << "MyClass : "; check<MyClass >();
    std::cout << "MyUnion : "; check<MyUnion >();
    std::cout << "MyEnum  : "; check<MyEnum  >();
    std::cout << "myfun   : "; check(myfun);

    MyClass c;
    std::cout << "MyClass : "; check(c);
}

daje ispis

int: Nije klasa
MyStruct: Klasa
MyClass : Klasa
MyUnion : Klasa
MyEnum  : Nije klasa
myfun   : Nije klasa
MyClass : Klasa

Podrška za manipulacije s tipovim u STL-u

U datoteci zaglavlja <type_traits> nalaze se razne metode za rad sa tipovima. Na primjer, ako imamo

struct A{
  int x_;
};

union B{
};

onda možemo ispitivati razna svojstva tipova:

std::cout << std::is_class<A>::value << std::endl;                 // 1
std::cout << std::is_class<double>::value << std::endl;            // 0
std::cout << std::is_class<B>::value << std::endl;                 // 0
std::cout << std::is_union<B>::value << std::endl;                 // 1
std::cout << std::is_default_constructible<A>::value << std::endl; // 1
std::cout << std::has_virtual_destructor<A>::value << std::endl;   // 0

Postoje i brojne druge metode za ispitivanje tipova. Druge funkcije manipuliraju s tipovima. Na primjer,

template <typename T>
struct TT{
  using  NoRef = typename std::remove_reference<T>::type;
  using  Base = typename std::remove_cv<NoRef>::type;  // remove const i volatile
  using  Pointer =  Base *;
  using  PointerToConst = const Base *;
};

Dobit ćemo:

std::cout << typeid(TT<const int &>::Pointer).name() << std::endl;        // Pi
std::cout << typeid(TT<const int &>::PointerToConst).name() << std::endl; // PKi

Onemogućavanje predložaka pomoću `std::enable_if<>`

Pomoću std::enable_if<> (zaglavlje <type_traits>) možemo onemogućiti generiranje funkcije iz predloška u nekim situacijama. std::enable_if<> je parametrizirana struktura sa dva parametra predloška:

template< bool B, class T = void >
struct enable_if;

Ako je B jednak true onda je std::enable_if<true,T>::type = T. Ako je B jednak false onda std::enable_if<true,T>::type ne postoji.

Pomoću std::enable_if<> možemo spriječiti da prevodilac instancira predložak u nekim slučajevima.

Primjer:

template <typename T>
typename std::enable_if<(sizeof(T) > 3), T>::type f(T x){
  return x*x;
}

int f(int x){
  return x;
}

char  c = 'a';
int   x = 4;
long  y = 4;

cout << sizeof(c) << " : " << f(c) << endl; // int f(int)
cout << sizeof(x) << " : " << f(x) << endl; // int f(int)
cout << sizeof(y) << " : " << f(y) << endl; // instancira long f(long)

CRTP (Curiously Recurring Template Pattern)

Ova se tehnika sastoji u tome da izvedena klase pošalje samu sebe kao template-parametra baznoj klasi koja se generira iz predloška klase. Na primjer,

template <typename T>
class Base {
    public:
        Base() : px(0) {}
        Base(T* p) : px(p) {}
        T *  px;  // T će biti nepotpuni tip i stoga
                  // možemo koristiti samo reference i
                  // pokazivače na T
       // ...
};

// Klasa samu sebe šalje baznoj klasi kao parametar.
class Derived : public Base<Derived>
{
    public:
        // Inicijalizira pokazivač u Base svojom adresom
        Derived() : Base<Derived>(this), n(0) {}
        int n;
    // ...
};

Brojanje instanci klase:

Jedna moguća primjena ove tehnike je u brojanju instanci pojedine klase. To je moguće postići pomoću statičke varijable te modificiranjem konstruktora, konstruktora kopije i destruktora kako bi se pratio broj instanci. Umjesto da takav kod implementiramo u svakoj klasi možemo ga faktorizirati u baznu klasu.

template <typename T>
class ObjectCounter {
    private:
        static size_t cnt;
    protected:
        ObjectCounter(){ ++cnt; }
        ObjectCounter(ObjectCounter<T> const &){ ++cnt; }
        ~ObjectCounter() {--cnt; }
    public:
        static size_t count() {return cnt; }
};

template <typename T>
size_t ObjectCounter<T>::cnt = 0;

Nastavak

Izvedena klasa i mali test program su dani ovdje.

template <typename T>
class A : public ObjectCounter<A<T> > {
    public:
        T i;
};

template <typename T>
void f(A<T> a) { // prijenos kopiranjem
  std::cout <<  A<T>::count() << std::endl;
}

int main() {
    A<int>    i,j,k;
    A<double> x,y, z=y;
    A<double> * px = new A<double>();

    std::cout << A<int>::count() << std::endl;
    std::cout << A<double>::count() << std::endl;
    f(z);
    delete px;
    std::cout << A<double>::count() << std::endl;
}

Ispis je

Uočimo da je bazna klasa parametrizirana izvedenom klasom iako je ne koristi. To osigurava da svaka izvedena klasa nasljeđuje posebnu baznu klasu, pa ima posebnu statičku varijablu.

U suprotnom bismo imali jednu baznu klasu koja bi brojala instance svih klasa koje su iz nje izvedene.

Metaprogramiranje predlošcima (template metaprogramming)

Metaprogramiranje predstavlja "programiranje programa". To znači pisanje koda koji će generirati kod koji će se izvršavati na računalu. Ono je omogućeno predlošcima jer oni predstavljaju "program" koji prevodilac prevodi u kod koji će biti izvršen.

Primjer: računanje potencije broja 3 — rekurzivno, za vrijeme kompilacije.

template <int N>
struct Pow3{
    static constexpr int result = 3 * Pow3<N-1>::result;
};

// puna specijalizacija za N=0
template <>
struct Pow3<0>{
    static constexpr int result = 1;
};

int main() {
    std::cout << "Pow3<4>::result = " << Pow3<4>::result
              << std::endl;
}

Prevodilac će izvršiti sljedeći račun:

Pow3<4>::result = 3* Pow3<3>::result
                = 3* 3* Pow3<2>::result
                = 3* 3* 3* Pow3<1>::result
                = 3* 3* 3* 3* Pow3<0>::result
                = 3* 3* 3* 3*  1

Primjer: loop unrolling

Numerički kod vrlo često radi s petljama u kojima se računaju elementarne operacije nad vektorima. Na primjer, skalarni produkt bismo prirodno implementirali na ovaj način:

// Standardna implementacija skalarnog produkta
template <typename T>
T dot_prod(int dim, T*a, T*b) {
    T result = T();
    for(int i=0; i<dim; ++i) result += a[i]*b[i];
    return result;
}

Problem s takvom implementacijom je u efikasnosti koda kojom dominira brzina dohvaćanja elemenata iz memorije. Pokazuje se da je kod efikasniji ako se petlja "razmota", odnosno da je

result = a[0]*b[0] + a[1]*b[1] + a[2]*b[2]  + a[3]*b[3]  + a[4]*b[4]  + a[5]*b[5];

efikasnije od

for(int i=0; i<6; ++i) result += a[i]*b[i];

Pokažimo kako taj efekt možemo postići pomoću metaprogramiranja.

Nastavak

template <int DIM, typename T>
struct DotProduct{
    static T result(T* a, T*b){
        return *a * *b + DotProduct<DIM-1,T>::result(a+1,b+1);
    }
};

// parcijalna specijalizacija
template <typename T>
struct DotProduct<1,T>{
    static T result(T* a, T*b){
        return *a * *b;
    }
};

// Parametriziran funkcija (dedukcija parametara predloška)
template <int DIM, typename T>
inline
T dot_product(T* a, T*b) {
    return DotProduct<DIM,T>::result(a,b);
}

Objašnjenje:

Sada, na primjer, dot_product<3>(a,b); povlači sljedeću instancijaciju:

DotProduct<3,T>::result(a,b)
= *a * *b + DotProduct<2,T>::result(a+1,b+1)
= *a * *b + *(a+1) * *(b+1) + DotProduct<1,T>::result(a+2,b+2)
= *a * *b + *(a+1) * *(b+1) + *(a+2) * *(b+2)

Ovdje je dan test program koji ispituje efikasnost nove implementacije u odnosu na standardnu.

int main() {
    int a[] = {1,2,3,4,5,6};
    int b[] = {4,5,6,7,8,9};

    clock_t start, finish;
    int result =0;
    int MAX = 1000000;

    start = clock();
    for(int i=0; i< MAX; ++i)
    {
        result = dot_prod(6,a,b);
    }
    finish = clock();
    std::cout << (double) (finish - start) << std::endl;

    result = 0;
    start = clock();
    for(int i=0; i< MAX; ++i)
    {
        result = dot_product<6>(a,b);
    }
    finish = clock();
    std::cout << (double) (finish - start) << std::endl;
}

Programiranje s predlošcima

Klase obilježja (traits classes)

Primjer - glavni program:

Klase obilježja

Nova verzija algoritma:

Klase obilježja - nastavak

Nastavak

Nastavak

Akcijske klase (Policy classes)

Nastavak

Nastavak

SFINAE (substitution-failure-is-not-an-error)

Prepoznavanje klasa

Primjena:

Podrška za manipulacije s tipovim u STL-u

Onemogućavanje predložaka pomoću std::enable_if<>

CRTP (Curiously Recurring Template Pattern)

Brojanje instanci klase:

Nastavak

Metaprogramiranje predlošcima (template metaprogramming)

Primjer: loop unrolling

Nastavak

Objašnjenje:

Onemogućavanje predložaka pomoću `std::enable_if<>`