template

Mitől template a template?

A "template" magyarul sablont jelent. A sablon egy séma, recept, amit felhasználva igény esetén elkészíthető belőle a végleges termék, önmagában viszont életképtelen. A C++ template-je is innen kapta a nevét.

A függvénysablon szó alatt magyarul nem csak a template függvényeket értjük, van OOP tervezéssel kapcsolatos vonatkozása is. Ebben a fejezetben viszont mindvégig a C++ template kulcsszaváról lesz szó.

template függvények

Találós kérdés: mi hiányzik ebből, az első fejezetből már ismerős kódrészletből?

inline int min(int a, int b) {
    return a < b ? a : b;
}

Szigorúan nézve semmi nem hiányzik belőle, így is tökéletes. Megmondja, két int közül melyik a nagyobb, bizonyos szituációkban mégis hiányérzetünk támad. Mit ír ki az alábbi kódrészlet?

std::cout << min(2.5, 2.1) << std::endl;

Ez bizony 2-t ír ki. Szóval két szám, 2.5 és 2.1 közül a kisebb egy harmadik (2). Jogos igény, hogy a min függvény működjön valós számokra is. Elvégre azokat is a < operátorral kell összehasonlítani. Írjunk hát egy overload-ot, ami két double-t vesz át, és double-t ad vissza!

inline double min(double a, double b) {
    return a < b ? a : b;
}

Ha eszünkbe jut a Tort, az std::string, vagy ezer másik osztály, amiket mind-mind a < operátorral hasonlítunk össze, elszabadulhat a pokol.

inline Tort min(Tort a, Tort b) {
    return a < b ? a : b;
}

inline std::string min(std::string a, std::string b) {
    return a < b ? a : b;
}

Itt illik érezni, hogy ez így nem mehet tovább. Az overload megírásához akár használhattuk a Search and replace funkciót is. A jóérzésű programozó sormintadetektora ettől elég hamar kiakad.

Tulajdonképp lehetne generálni is ezeket az overload-okat. Ezt a mechanikus munkát el tudja végezni helyettünk a fordító, egy nyelvi elem, a template segítségével:

template<typename T>
T min(T a, T b) {
    return a < b ? a : b;
}

Bár elsőre szokatlan a szintaxisa, később arra is rávilágítunk, miért kell ennek ilyennek lennie. Elemezzük ki apránként, mi mit jelent!

A függvényben a T-t már valóban használhatjuk típusként, két T-t vár paraméternek, és T-t ad vissza. Ha mi int-ekkel használjuk, T helyére képzeljünk int-et, ha double értékekkel hívjuk, akkor pedig double-t. A függvény belsejében gátlástalanul használjuk a < operátorát, ezzel elvárjuk, hogy csak olyan típust adjanak meg neki, aminek tényleg van ilyenje. Ha mégsincs, akkor a kód nem fordul.

A fenti kontextusban, a kacsacsőrök között a typename helyett a class kulcsszó is használható, pontosan ugyanazt jelenti (struct viszont nem használható). Tehát a lenti függvény tökéletesen ekvivalens a fentivel, T ugyanúgy lehet int is.

template<class T>
T min(T a, T b) {
    return a < b ? a : b;
}

A jegyzetben következetesen a typename-et használjuk, valamivel kifejezőbb.

template függvények hívása

A fent definiált min függvényt az alábbi módokon hívhatjuk meg:

int main() {
    double a = min(3.1, 0.0);
    int b = min<int>(0, 'b');
    Tort c = min<Tort>(Tort(2), Tort(6));
}

Az egész arra ment ki, hogy az első hívás helyes legyen, és ennek hatására két double-t hasonlítson össze a fordító által generált függvény.

A második és harmadik esetben explicit módon kiírtuk, hogy milyen típussal szeretnénk meghívni a függvényt, ez mindig működni fog. Ezen felül jogosan várjuk el a fordítótól, hogy ha mi pl. double-öket adunk meg paraméterekként, akkor legyen okos, és találja ki, hogy T == double. A fordító képes levezetni a paramétereket, ezért tud működni az első. Ezt természetesen csak akkor tudja megtenni, ha van egyáltalán a template paramétertől, typename T-től függő függvényparaméter: T a, T b (a min függvénynél természetesen van).

Ha explicit módon adjuk meg a template paramétert, akkor az automatikus konverzió is meg van engedve, például az első esetben 'b' konvertálódik int-re. Ha a fordító vezeti le, akkor ettől a lehetőségtől elesünk. Csak akkor vezetheti le a template paramétereket, ha a típusok pontosan passzolnak. Például min(3.1, 0) fordítási hibához vezet, mert 3.1 egy double, a 0 viszont int.

Mitől kacsa egy kacsa?

A válasz legalább annyira meghökkentő, mint a kérdés. Az kacsa, amit mi annak tekintünk. Egy séf teljesen más szempont szerint keres madarak között kacsát, mint egy genetikus. Egy kisgyerek szemében minden kacsa, ami úszik és hápog.

Egyáltalán hogy kerül ide a kacsa? Nézzük meg megint a min függvényünket!

template<typename T>
T min(T a, T b) {
    return a < b ? a : b;
}

Milyen típusokon működik ez a függvény? Mindenen, ami lemásolható (mivel érték szerint veszi át a paramétereit) és van < operátora. Ezt a függvényt semmi más nem érdekli.

Ennek a típusszemléletnek duck typing a neve. A szó nagyjából annyit takar, hogy előzetes információ nélkül kipróbáljuk, tud-e hápogni és repülni a kezünkbe adott dög. Ha igen, nekünk éppen eléggé kacsa. Nem kell előre megmondani, hogy mi itt olyan T-ket várunk, ami másolható és van < operátora. Ha nincs neki, mi ugyanúgy ledobjuk a szakadékból, de az alján nagyot csattan. Ez időben kiderül, ugyanis ilyenkor fordítási hiba keletkezik.

Éles szeműek észrevehetik, hogy a kacsát csak szintaktikailag ellenőrizzük le, akár teljesen más szemantika is lehet mögötte. Mit ír ki ez a kód?

template<typename T>
T duplaz(T const& x) {
    return x+x;
}

int main() {
    std::cout << duplaz(3) << std::endl;
    std::cout << duplaz(std::string("ha")) << std::endl;
}

A duplaz(3) visszaadja 3+3-at, ami 6, és a költő valószínűleg erre gondolt a duplaz megírása közben. A duplaz(std::string("ha")) viszont "haha" lesz! Ugyanúgy értelmesek a műveletek, de ugyanaz a függvény (ami itt operator+) az egyik típusnál összead, a másiknál összefűz. Szóval a séf megtalálta a hápogó, úszó valamit, és megfőzte. A vendég a tányérjában egy darab műanyagot talált, ugyanis az egy elemes gumikacsa volt. Persze lehet, hogy pont ez volt a cél.

A template specializáció

Mit ír ki az alábbi kódrészlet?

int main() {
    std::cout << min("hello", "vilag") << std::endl;
}

Prog1-ből tudjuk, hogy egy string literal char const-okból álló tömb. Ez függvénynek pointerként adódik át, tehát itt char const* típussal példányosodik a függvény:

char const* fordito_altal_generalt_min(char const* a, char const* b) {
    // a és b pointerek!
    return a < b ? a : b;
}

Tehát a min a pointereket hasonlította össze, nem a sztringek tartalmát!

Itt a költő valószínűleg arra gondolt, hogy annak kéne kiíródnia, amelyik ABC-sorrendben (strcmp) előrébb van. Azt szeretnénk elérni, hogy a min függvény minden típusra a < operátort használja, kivéve char const *-ra, mert ott strcmp kellene nekünk. A kivéve viszony C++-beli megfelelője a template specializáció.

template<typename T>
T min(T a, T b) {
    return a < b ? a : b;
}

template<>
char const* min<const char*>(char const* a, char const* b) {
    return strcmp(a, b) < 0 ? a : b;
}

Az eredeti függvény csak azért került ide is, nehogy félreértse valaki: a template specializáció egy kiegészítés, kell hozzá "alap". Elemezzük ki ezt is!

Ez utóbbit nem mindig muszáj megadni, de érdemes. Ezen kívül specializáció helyett néha használhatunk sima overload-ot is, az viszont kicsit mást jelent. Például az alábbi esetben az overload-trükköt nem tudnánk kihasználni.

template<typename T>
T pi() {
    return 3.14159265358979323846;
}

template<>
Tort pi<Tort>() {
    return Tort(104348, 33215);
}

template osztályok

A template-et eredendően nem a template függvények miatt találták fel, hanem a template osztályok miatt. Azon belül is eredendően a tároló osztályok azok, amiknek a típusát már C-ben jó lett volna általánosítani. A jegyzetben eddig alig esett szó tároló osztályokról, pont azért, mert template nélkül sok lenne a sorminta.

Első példaként nézzünk egy dinamikusan nyújtózkodó tömböt, ami double-öket tárol. Ez az osztály a konstruktorában vegye át a kiindulási méretet, ami alapértelmezetten 0! A méretet a size(), az elemek egyenkénti elérését az operator[] fogja biztosítani. A nyújtózkodást pedig – a szabványos könyvtárral összhangban – a push_back függvény váltja ki.

class Vektor_double {
    double *adat;
    size_t meret;

public:

    explicit Vektor_double(size_t meret = 0)
        : adat(new double[meret])
        , meret(meret) {
    }

    // copy ctor, operator=, dtor kellene, házi feladat.

    size_t size() const {
        return meret;
    }

    double& operator[](size_t index) {
        return adat[index];
    }

    double const& operator[](size_t index) const {
        return adat[index];
    }

    void push_back(double uj_ertek) {
        double *uj_adat = new double[meret + 1];
        for(size_t i = 0; i < meret; ++i)
            uj_adat[i] = adat[i];
        uj_adat[meret] = uj_ertek;
        delete[] adat;
        adat = uj_adat;
        ++meret;
    }
};

Ebben a megvalósításban – ahogy a szabványos könyvtár std::vector osztályában is van – az operator[] nem ellenőrzi a határokat, mivel erre a legtöbbször semmi szükség. Ha a használója nem biztos a dolgában, akkor használhatja helyette az at tagfüggvényt.

Melyek azok a részek, amik ebben az osztályban double-specifikusak?

Erre jelen esetben egyszerű válaszolni: ahol a kódban szerepel a double szó. Például mindjárt az osztály nevében. Ha template-esíteni szeretnénk, az osztálydefiníció elejére kell írni, hogy template<typename TIPUS>. Ezen kívül ahol double típus szerepel, mind ki kell cserélni TIPUS-ra.

template<typename TIPUS>
class Vektor {
    TIPUS *adat;
    size_t meret;

public:

    explicit Vektor(size_t meret = 0) :
        adat(new TIPUS[meret]),
        meret(meret) {
    }

    // copy ctor, operator=, dtor mind kell, házi feladat.

    size_t size() const {
        return meret;
    }

    TIPUS& operator[](size_t index) {
        return adat[index];
    }

    TIPUS const& operator[](size_t index) const {
        return adat[index];
    }

    void push_back(TIPUS const& uj_ertek) {
        TIPUS *uj_adat = new TIPUS[meret + 1];
        for(size_t i = 0; i < meret; ++i)
            uj_adat[i] = adat[i];
        uj_adat[meret] = uj_ertek;
        delete[] adat;
        adat = uj_adat;
        ++meret;
    }
};

Nagyon figyelmesen nézve észrevehető, hogy még egy apróságot változtattunk ezen az osztályon. A push_back eddig érték szerint vette át az uj_ertek paramétert, a template-es verzióban pedig már const&-ként. Felelős programozóként gondolnunk kell a jövőre is. Például ha valaki a Vektor osztályunkat std::string paraméterrel szeretné használni, annak a lemásolása ott igen költséges és felesleges lenne.

Hogyan kell használni ezt az osztályt? Ahogy a függvényeknél megtanultuk, itt is meg kell adni, milyen template paraméterekkel szeretnénk példányosítani az osztályt. Fontos különbség, hogy osztályoknál nincs típuslevezetés, csak függvényeknél.

Vektor<double> v(100);
for(int i = 0; i < 100; ++i)
    v[i] = double(i) / double(i+1);

Az osztályt úgy írtuk meg, hogy a Vektor<double> lehetőleg ugyanúgy viselkedjen, mint a Vektor_double, tehát a használata csak a deklarációban különbözik. Annál viszont többet tud, akármilyen típusra cserélhetjük a double-t. Akár std::string-re is.

Vektor<std::string> v;
std::string word;
while(std::cin >> word)
    v.push_back(word);

Osztályon kívül definiált template tagfüggvények

Ahogy a "sima" osztályoknál megszokhattuk, a template osztályok tagfüggvényeit is definiálhatjuk az osztályon kívül. A szintaxisa elég körülményes, némi magyarázatra szorul, miért pont úgy kell.

Emlékezzünk vissza, a tagfüggvényeknek van egy implicit paramétere, a this pointer. Mi ennek a típusa egy Vektor<double> esetén? (A const tagfüggvényektől most tekintsünk el.)

Vektor<double> * const this;

Mi a típusa általános esetben, Vektor<TIPUS>-ra?

Vektor<TIPUS> * const this;

Ebből az látszik, hogy egy template osztály tagfüggvénye is template. Tehát deklarálnunk kell a template paramétereket, és a tagfüggvény nevében egyértelműsítenünk kell, hogy ez bizony a Vektor<TIPUS> tagfüggvénye. Például az alábbi kódban az uj_adat[meret] = uj_ertek lehet int értékadás, vagy std::string::operator= hívása is.

template<typename TIPUS>
void Vektor<T>::push_back(TIPUS const& uj_ertek) {
    TIPUS *uj_adat = new TIPUS[meret + 1];
    for(size_t i = 0; i < meret; ++i)
        uj_adat[i] = adat[i];
    uj_adat[meret] = uj_ertek;
    delete[] adat;
    adat = uj_adat;
    ++meret;
}

Ennek ugyanúgy a header-ben a helye, mint a "sima" template függvényeknek, ennek okára is fény fog derülni.

template paraméterek típusai

Az eddigi template kódjainkban a template paraméterek mind típusok (typename) voltak. Ezek azonban lehetnek értékek is, például lehet egy int is. Fontos megkötés a sima függvény- vagy konstruktorparaméterekkel szemben, hogy fordítási időben ismertnek kell lennie. Ez a korlátozás néhány helyen plusz lehetőségeket hordoz, például C-s tömböt csak fordítási időben ismert mérettel deklarálhatunk.

A "nem-típus" (non-type) template paraméter lehet bármilyen beépített típus, egész típus, függvénypointer, valamilyen enumból származó érték, és még pár elvadult dolog, aminek a használata jóval körülményesebb. Lebegőpontos típus (float, double) viszont nem.

Lássunk egy példát erre! Írjunk egy Stack osztályt, ami bármilyen típust tud tárolni! A maximálisan tárolható elemek száma legyen template paraméterben megadható.

template<typename T, std::size_t N>
class Stack {

    T adat[N];
    std::size_t db;

public:

    Stack() : db(0) {
    }

    bool empty() const {
        return db == 0;
    }

    bool full() const {
        return db == N;
    }

    std::size_t size() const {
        return db;
    }

    void push(T const& uj) {
        if(full())
            throw std::overflow_error("Stack");
        adat[db] = uj;
        ++db;
    }

    T pop() {
        db--;
        return adat[db];
    }

};

A nem-típus template paramétert ugyanott kell megadni, ahol az ember várná. Az osztályon belül N ugyanúgy használható, mintha egy sima std::size_t lenne, ráadásul fordítási időben ismert.

Fontos, hogy a különböző template paraméterekkel példányosított Stack-eknek egymáshoz semmi közük! Ahogy egy Vektor<int> és egy Vektor<std::string> is inkompatibilis, ugyanúgy a Stack<int, 100> és a Stack<int, 200> is.

Vegyük észre, hogy ennek az osztálynak nem kell destruktort írni, sem copy ctort, sem op=-t. Ugyanis nincs benne dinamikus memóriakezelés, a statikus méretű tömbök adattagként ugyanúgy érték szerint másolódnak le, ahogy C-ben.

Részleges specializáció

A Stack-ünk memóriakezelése egyszerű és gyors: a tömb mint beépített tároló kezelése nem igényel különösebb figyelmet. A tárolt elemek benne vannak az objektumban, tehát egy elem gyorsan és indirekció nélkül elérhető. Egyetlen metaadatot tárolunk, a foglalt darabszámot, amire mindenképpen szükség van.

Van egy különleges eset: amikor a tárolt elem bool. A memóriában egy bool változó nem tud egy bájtnál kevesebb helyet foglalni (hiszen címezhetőnek kell lennie), viszont logikai értelemben egyetlen bitnyi információt tartalmaz. Írjunk egy olyan Stack-et, ami a bool-okat hatékonyabban tárolja! A tömbben tároljunk unsigned char-okból álló tömböt, a push és a pop pedig a megfelelő helyre tologatja a biteket.

Jó lenne, ha a Stack ugyanúgy működne, mint eddig, kivéve ha a T helyére bool kerül. A "kivéve" viszony C++-ban specializációt jelent, ez azonban egy másfajta specializációt igényel, mint a fentebb bemutatott függvényé. A Stack<bool, N> ugyanis szintén egy template osztály, viszont bármilyen N-re ennek a specializációnak kell életbe lépnie.

A specializált osztálynak tehát N továbbra is template paramétere, T viszont rögzítve van bool-ra. Az ilyen neve részleges specializáció.

A Stack<bool, N> ez lett, a specializációt az első két sorban láthatjuk.

template<std::size_t N>
class Stack<bool, N> {

    unsigned char adat[N/8 + 1];
    std::size_t db;

public:

    Stack() : db(0) {
    }

    bool full() const {
        return db == N;
    }

    bool empty() const {
        return db == 0;
    }

    std::size_t size() const {
        return db;
    }

    void push(bool uj) {
        if(full())
            throw std::overflow_error("Stack");

        int bajt = db / 8;
        int bit = db % 8;

        if(uj)
            adat[bajt] |= 1 << bit;
        else
            adat[bajt] &= ~0 ^ (1 << bit);

        ++db;
    }

    T pop() {
        db--;
        return adat[db / 8] & (db % 8);
    }

};

Teljesen korrektek vagyunk itt a 8-as számot illetően? Tudni kellene, hogy egy bájtba (unsigned char-ba) hány bit fér. A climits header-ben definiált CHAR_BIT makró megmondja nekünk, de ezzel most nem foglalkozunk, 8-nak vesszük. A szabvány egyébként garantálja, hogy legalább 8, tehát ezzel nem követünk el hibát.

STL-vonatkozások

A fent bemutatott Vektor osztály ihletője az std::vector volt, a vector standard header-ből. Utóbbi jóval okosabb: nem hív feleslegesen T-konstruktorokat, csak azt, amire kértük. A push_back-je jóval hatékonyabb, a memóriát nem egyesével nyújtogatja, hanem nagyobb darabokban. Az általa lefoglalt méret sokkal nagyobb lehet, mint a ténylegesen feltöltött.

Az std::vector részlegesen specializált a bool-ra, ez adta az ötletet a Stack<bool>-hoz. Az eredeti cél egy memóriahatékonyabb bitset megalkotása volt, azonban ennek súlyos az ára: az std::vector<bool> butább, mint a többi std::vector, és a koncepció megtartásával nem javítható, így a használata ellenjavallott.

Az STL-ben stacket is találunk a stack header-ben, a neve std::stack. Ez szerencsére nincs specializálva bool-ra. Különbség a mi implementációnkhoz képest, hogy megkülönbözteti a legfelső elem kiolvasását és törlését. A pop függvénye nem adja vissza a kivett elemet, csak eldobja. A legfelső elemet a top tagfüggvénnyel érjük el, méghozzá referencia szerint.

Haladó template függvények

Írjunk függvényt, ami egy fenti stacket megfordít! A függvény bármilyen típusú és méretű Stack-ekre működjön!

A második kitétel azt okozza, hogy a függvénynek két template paraméter kell, a típus és a méret.

template <typename T, std::size_t N>
void megfordit(Stack<T, N> & s) {
    Stack<T, N> ujstack;
    while (!s.empty())
        ujstack.push(s.pop());
    s = ujstack;
}

A fordító varázsereje

Arról már esett szó, hogy a fordító generálja le a sablonokból a kész függvényeket. Nézzük meg ismét első template függvényünkön, hogyan történik mindez.

template<typename T>
T min(T a, T b) {
    return a < b ? a : b;
}

Észre kell vennünk azt, hogy ezt a függvényt nem lehet lefordítani, amíg nem tudjuk meg, hogy a T típus pontosan micsoda. Amíg ez az információ nem áll rendelkezésre, addig nem tud kódot generálni.

Például beépített típusok esetén a paramétereket és a visszatérési értéket bitenként kell másolni, az összehasonlítás egyetlen gépi utasítással történik. Ezzel szemben egy objektumnál (pl. egy std::string-nél) a visszatérési érték bemásolásához az std::string másoló konstruktorát kell hívni. Az összehasonlításnál olyan operator<-t kell keresnie a fordítónak, ami két std::string-et tud összehasonlítani, ez lehet tagfüggvény vagy globális függvény is.

Ennyire aprólékosan kifejtve szépen látszik, hogy egy template függvény típusonként nagyon eltérő tartalmú. Mégis, hogyan tud ez egyáltalán működni?

A template kód fordításának menete nem tartozik szigorúan a tárgy anyagához, de a megértést nagyon megkönnyíti, egy csapásra világossá válik az egész. Nem pontos technikailag a leírás, de nagy vonalakban stimmel.

Először, amikor a fordító elemzi a kódot, csak nagyvonalú szintaktikai ellenőrzést végez. Zárójelek, pontosvesszők, függvényhívások, operátorok szintaxisa, stb. Aztán amikor a kódban ilyet talál:

int a = min(1, 2);

Akkor visszatér a min függvényhez, és legenerál belőle egy példányt. Ekkor már pontosan tudja, hogy itt a min<int> függvény kell, int template paraméterrel. Az így kapott specializációt hívja meg a fenti sorban. (Ugyanabban a fájlban még egy min<int> hívásnál természetesen nem generálja újra ugyanazt, csak beilleszti a megfelelő hívást.)

Ha a kódban van egy min<std::string> hívás is, akkor legenerál egy másik specializációt, ami már std::string paraméterű, és ennek felel meg a törzse is. Ha meg min<char const *>-ot, akkor használja az általunk megadott specializációt.

Mi történik, ha egy template függvény definíciója nem a header-ben (pl. min.h), hanem egy önálló fordítási egységben (min.cpp) van, és egy másik fájlban (main.cpp) használni próbáljuk? Tehát tegyük fel, hogy úgy írjuk a kódot, ahogy C-ből tanultuk, a függvénynek csak a deklarációját írva a fejlécfájlba:

#ifndef MIN_H_INCLUDED
#define MIN_H_INCLUDED

template<typename T>
T min(T a, T b);

#endif

A main.cpp-ben nem tudja a fordító legenerálni a megfelelő min() példányt, hiszen nem ismert a törzs. A min.cpp fordításakor viszont azt sem tudja a fordító, hogy mi a main.cpp-ben egyáltalán használni szeretnénk, tehát nem tudja, milyen típusokkal kellene példányosítania.

Tehát az az egy megoldás marad, hogy a header-be tesszük a definíciót is, függetlenül attól, hogy önálló függvény, osztályon belül vagy kívül definiált tagfüggvény. Az ilyen header-ök a szokványostól eltérően nem csak deklarációkat tartalmaznak, és nem tartozik hozzájuk *.cpp fájl sem. Ezért ezek konvenció szerint hpp kiterjesztést kapnak (pl. min.hpp). Tehát így:

#ifndef MIN_HPP_INCLUDED
#define MIN_HPP_INCLUDED

template<typename T>
T min(T a, T b) {
    return a < b ? a : b;
}

#endif

Trükkös kérdés: ha a min<int> példányt több fájlban is használjuk, a linker hogyhogy engedi? Szokványos függvényeket csak egy helyen definiálhatunk, míg így több fájlban is szerepel a definíciója.

Ezért van biztosítva a C++ szabványban, hogy minden template függvény definíciója inline-nak minősül, akkor is, ha mi nem írjuk ki. Így ugyan többször lefordul a függvény, de erről a linker tudja, hogy normális (és feltételezhető, hogy egyformák is lettek a lefordított függvények), és ezért csak az egyik kerül be végül a programba.