Template

A sablonok alapvető célja a C++ nyelvben, hogy a fordítóra bízhassuk a programkódunk generálását abban az esetben, amikor csak típusok miatt másolnánk a kódot.

Gondoljunk egy tömbi algoritmusra, például a rendezésre: egész számok tömbje, valós számok tömbje, sztringek tömbje... Mindegyiket ugyanúgy kell rendezni, csak a cserélgetett adatok típusa más. Vagy egy tárolóra: egész számok listája, valós számok listája, sztringek listája... A lista építése (elem létrehozása, pointerek beállítása), az ehhez tartozó algoritmusok teljesen függetlenek attól, hogy mi a tárolt adat.

A sablonok ilyen problémák megoldásában, azaz a generikus programozásban segítenek.

Emlékezzünk vissza: a C++ megengedi azt, hogy ugyanolyan nevű, de eltérő típusú és számú paraméterekkel rendelkező függvényeket hozzunk létre. Emiatt könnyedén írhatunk olyan max() függvénycsaládot, amely tagjai két szám közül megadják a nagyobbikat:

int max(int x, int y) {
    return x > y ? x : y;
}

double max(double x, double y) {
    return x > y ? x : y;
}

Ha van olyan típusunk, amelyre szintén használható a nagyobb operátor >, akkor ez a kódrészlet ugyanolyan jó lesz arra is. Ha például írtunk egy tört (racionális szám) osztályt, amelynek ez az operátora definiált, akkor arra is működne a return után megadott kifejezés, csak írnunk kéne egy harmadik példányt a függvényből..

Ami ezen a ponton nagyon szembetűnő, hogy a függvények törzse egyforma. Copy-paste-eltünk, és ez soha nem jelent jót.

  int  max(  int  x,   int  y) {
    return x > y ? x : y;
}

double max(double x, double y) {
    return x > y ? x : y;
}

A típusnév cseréjét a fejlesztőkörnyezet „keresés és csere” műveletével is elvégezhetnénk, de érezzük, hogy ezt akár a fordító is megoldhatná helyettünk.

Erre valók a sablonok C++-ban.

Sablon kódban kifejezhetjük azt, hogy egy kódrészletben – jelen esetben egy függvényben – valamelyik típust nem ismerjük. Tehát hogy az majd később fog kiderülni, és cserélhetővé szeretnénk tenni. Ezt így tudjuk megtenni:

template <typename T>   // T helyére egy típus kerül majd
T max(T x, T y) {
    return x > y ? x : y;
}

A függvénysablont a template kulcsszóval kell bevezetni. Utána pedig a kacsacsőrök között a sablonparamétereket kell megadni, ugyanolyan szintaxissal, ahogy a függvényeknél azt megszoktuk (típus és név). Jelen esetben a T nevű sablonparaméter típusát a typename kulcsszó adja meg; ez jelenti azt, hogy oda majd egy konkrét típust kell beírni.

Itt a T annak a típusnak a neve, ahova lényegében bármi behelyettesíthető. Ha a T helyére int-et írunk, visszakapjuk az első függvényt, ha pedig T = double, akkor a másodikat. Csakhogy most nem nekünk kell majd megírni ezeket, hanem a fordító generálja majd őket teljesen automatikusan a fenti sablonból.

A függvénysablonok egészen addig nem lesznek lefordítva, amíg nem használjuk őket. Tehát amíg nem derül ki az, hogy a T helyére mit kell írni. A típus megadásával konkrét függvények keletkeznek; ezt a lépést a sablon példányosításának nevezzük. A függvény hívásakor kacsacsőrök között adhatjuk meg azt, hogy mik legyenek a konkrét sablonparaméterek:

#include <iostream>

template <typename T>   // T helyére egy típus kerül majd
T max(T x, T y) {
    return x > y ? x : y;
}

int main() {
    std::cout << max<int>(2, 5) << std::endl;
    std::cout << max<double>(3.14, 1.7) << std::endl;
}

A max<int>(2, 5) kifejezéssel a fordító tudtára adjuk a következőket:

1. Szükségünk van a max() függvénysablonnak egy olyan változatára, amelyben a T helyére mindenhova int került.
2. És szeretnénk is meghívni az így kapott függvényt a 2, 5 paraméterekkel.

A példányosítási kérés hatására a fordító automatikusan előállítja a megfelelő specializációt (példányt), behelyettesítve a sablon kódba a paramétereket. Olyan, mintha ezt a specializációt magunk megírtuk volna – de nem kellett, mert triviális, és automatikusan történt. A háttérben ez a függvény íródott meg:

template <>     // specializáció
int max<int>(int x, int y) {    // arra az esetre, amikor T = int
    return x > y ? x : y;
}

Látható, hogy az így előálló függvényben már nincs zsákbamacska a típusok helyén, lefordítható a kód.

Kicsit kényelmetlennek tűnhet a fenti kódban, hogy ki kell írnunk a max() függvény hívásakor a sablonparamétereket is:

std::cout << max<int>(2, 5) << std::endl;
std::cout << max<double>(3.14, 1.7) << std::endl;

A kódot vizsgálva hamar fölmerül az a kérdésünk is: nem lehetne automatikusan kitalálni a sablonparamétereket? A 2 és az 5 paraméterek int típusúak, a 3.14 és az 1.7 pedig mindketten double típusúak. Levezethette volna a fordító magától is, hogy az első esetben T = int-et, a második esetben pedig T = double-t kell használni a max() sablonhoz.

Szerencsére ilyen is van. A fordító ki tudja találni a függvény hívásából, milyen sablonparaméterekre van szükség. Ezt automatikus sablonparaméter-levezetésnek, vagy dedukciónak nevezzük (template argument deduction). Vagyis bőven elegendő ennyit írunk:

std::cout << max(2, 5) << std::endl;
std::cout << max(3.14, 1.7) << std::endl;

A levezetésnek szigorú szabályai vannak; ha a fordító ellentmondásra jut, akkor vissza fogja utasítani a kódot. Ilyenre legegyszerűbb példa a következő kódrészlet:

std::cout << max(2.28, 7) << std::endl;     // fordítási hibát okoz

max.cpp:4:3: note: template argument deduction/substitution failed:
max.cpp:9:29: note: deduced conflicting types for parameter ‘T’ (‘double’ and ‘int’)

A hibaüzenet oka: a max() függvényünk (T x, T y) fejléce azt mondja, hogy két egyforma típusú paraméterrel lehet használni a függvényt. Az első paraméterből, a 2.28-ból viszont it T = double következne, a másodikból, a 7-ből pedig T = int. Ez ellentmondás, és mivel a fordító nem tudja, mi a célunk, nem is akar állást foglalni. Ha szeretnénk eltérő típusú paraméterekkel meghívni a függvényt, akkor explicite meg kell adnunk a sablonparamétert:

std::cout << max<double>(2.28, 7) << std::endl;

Ugyanez a probléma egyébként már előjöhetett a túlterhelt függvénynevek esetében is. Ha visszagondolunk a kézzel megírt, copy-paste-elt max() függvényeinkre, azoknál is lehetséges volt ilyen:

#include <iostream>

int max(int x, int y) {
    return x > y ? x : y;
}

double max(double x, double y) {
    return x > y ? x : y;
}

int main() {
    std::cout << max(2.28, 7) << std::endl;     // fordítási hibát okoz
}

max.cpp:17:29: error: call of overloaded ‘max(double, int)’ is ambiguous
max.cpp:8:5: note: candidate: int max(int, int)
max.cpp:12:8: note: candidate: double max(double, double)

Tehát ebben nincs semmi meglepő.

Találós kérdésként tegyük föl: vajon mit ír ki az alábbi program, almát vagy körtét?

#include <iostream>

template <typename T>
T max(T x, T y) {
    return x > y ? x : y;
}

int main() {
    std::cout << max("alma", "korte") << std::endl;
}

A helyzet az, hogy nem igazán lehet megmondani. Azt várnánk, hogy a körte szó jelenik meg (az a „nagyobb”, az van hátrébb az ábécében), de sajnos nem ez a helyzet. Vezessük végig, mi is jár a fordító fejében!

A főprogrambeli max("alma", "korte") hívásból kell kiindulnunk. Ebben a kifejezésben egy függvényhívás szerepel. A max() azonban nem függvény, hanem csak sablon, sőt a sablonparaméterei nincsenek megadva. Ezért le kell vezetni azokat.

Paraméterként a függvény két karaktertömböt kap (az almát és a körtét). Tömböt függvénynek átadni a tömb elejére mutató pointerrel lehet, tehát a két átadott paraméter típusa char const * kell legyen. Ezek egyformák, ráillik a (T x, T y) sémára, tehát a fordító létrehozza automatikusan a specializációt, és meghívja a függvényt:

template <>
char const * max<char const *>(char const * x, char const * y) {
    return x > y ? x : y;   // hibás
}

A gond csupán csak az, hogy ezt nem azt csinálja, mint amit szeretnénk. Az x > y kifejezés itt két pointert hasonlít össze; ezzel nem azt kérdezzük, hogy melyik sztring van előrébb az ábécében, hanem azt, hogy melyik sztring van előrébb a memóriában. Aminek a szótárbeli sorrendhez úgy igazán semmi köze, és amúgy is előre megjósolhatatlan.

A C stílusú sztringek (nullával lezárt karaktertömbök) összehasonlítására a strcmp() függvényt kellene használnunk. Valahogyan azt kellene itt megmagyaráznunk a fordítónak, hogy a max() függvénysablon általában jó mindenféle típusra, kivéve a T = char const * esetén – mert ilyenkor valami egészen mást kell csinálni.

Ezt tudjuk megtenni egy explicit specializációval, amelynek a szintaxisa és megvalósítása ebben a konkrét esetben az alábbi:

template <>
char const * max<char const *>(char const * x, char const * y) {
    return strcmp(x, y) > 0 ? x : y;
}

Nézzük meg jobban, hogy kell egy ilyet megírni!

1. A kód egy template <> sorral indul. Jelezzük, hogy egy sablonról (annak specializációjáról) van szó, itt azonban már változni képes sablonparaméterek nincsenek. Ezt fejezi ki az üres kacsacsőrpár.
2. A függvény nevétől jobbra jelezzük azt is, hogy ez a max nevű függvénysablon specializációja arra az esetre, amikor T = char const *. Ezt kötelező kiírni, mert más típusokra is megadhatnánk specializációt, és itt derül ki, melyikről van itt szó.
3. Egyébiránt pont ugyanúgy megírjuk a függvényt, ahogy bármelyik másikat.

A teljes, kipróbálható program így néz ki:

#include <iostream>
#include <cstring>

template <typename T>
T max(T x, T y) {
    return x > y ? x : y;
}

template <>
char const * max<char const *>(char const * x, char const * y) {
    return strcmp(x, y) > 0 ? x : y;
}

int main() {
    std::cout << max(2, 5) << std::endl;
    std::cout << max("alma", "korte") << std::endl;
}

A valóság amúgy nem olyan szép sajnos, mint ahogyan innen nézve tűnik. Előbb-utóbb ezzel megütnénk a bokánkat. A char * és a char const * különböző típusoknak számítanak, tehát a char *-ra még mindig az alap sablont (base template) használná a fordító.

A fentiek alapján már könnyedén írhatunk egy generikus rendezőfüggvényt. Ez bármilyen típusú elemekből álló tömböt növekvő sorrendbe tud tenni. (Az algorithm fejlécben definiált std::swap() függvény is generikus. Két bármilyen, de egyforma típusú változó tartalmának megcserélésére való.)

#include <iostream>
#include <algorithm>

template <typename T>
void rendez(T *tomb, size_t meret) {
    for (size_t i = 0; i < meret-1; ++i) {
        size_t min = i;
        for (size_t j = i+1; j < meret; ++j)
            if (tomb[j] < tomb[min])    // összehasonlítás
                min = j;
        std::swap(tomb[i], tomb[min]);
    }
}

int main() {
    int tomb[5] = { 9, 6, 8, 7, 2 };
    rendez(tomb, 5);
    for (size_t i = 0; i < 5; ++i)
        std::cout << tomb[i] << ' ';
}

A függvény belsejében implementált minimumkereső algoritmus kapcsán sejthetjük, hogy itt elő fog jönni ugyanaz a probléma, mint az előbb. A kisebb operátor < karaktertömbökre mutató pointerek esetén nem azt az összehasonlítást végzi, amire nekünk szükség van.

De más probléma is van ám azzal a relációs jellel... Mi lenne, ha nem növekvő, hanem csökkenő sorrendbe szeretnénk tenni az elemeket? És ha olyan elemeket tartalmazna a tömb, amelyeket több szempont szerint is lehet rendezni? Pl. emberek név szerint, kor szerint, magasság szerint. Vagy színek fényesség szerint (sötétek előre, világosak hátra), esetleg színárnyalat szerint (pirosas színek előre, zöldebbek hátra). A rendezés algoritmusa mindig ugyanaz, csak jelzett sorban lévő feltételt cserélgetnénk.

Ez a feladattípus és a megoldása a Prog1-ben már szerepelt. Az összehasonlító függvényt paraméterként kell átadni. Ez a függvény, egy bináris predikátum (binary predicate) fogja megadni azt, hogy egy adott elem előrébb kell-e kerüljön a tömbben vagy hátrébb egy másik elemhez képest. Bináris, mert két paraméterű, és predikátum, mert igaz vagy hamis a visszatérési értéke: akkor igaz, ha előrébb való a tömbben az első paramétereként megadott elem a másodiknál, amúgy pedig hamis.

A függvényt át tudjuk adni függvényre mutató pointerként is:

template <typename T>
void rendez(T *tomb, size_t meret, bool (*elorebb)(T, T)) { // fv ptr
    /* ... */
    if (elorebb(tomb[j], tomb[min]))
    /* ... */
}

bool kisebb(int a, int b) {
    return a < b;
}

int main() {
    int tomb[5] = { 9, 6, 8, 7, 2 };
    rendez(tomb, 5, kisebb);
    /* ... */
}

Látszik, hogy a predikátum függvény, amelyre az elorebb pointer mutat, két T-t vesz át paraméterként. Mivel a tömb int típusú elemekből áll, T = int példányosítással fog próbálkozni a fordító, amiből a rendez() függvénysablon alábbi fejléce adódik:

template <>
void rendez<int>(int *tomb, size_t meret, bool (*elorebb)(int, int));

Ez helyes is, mivel a kisebb() függvény pontosan olyan paraméterezésű, mint amilyenre az elorebb nevű pointer mutatna.

Gond csak akkor adódik, ha nem pontosan ilyen. Mi lenne akkor a helyzet, ha olyan összehasonlító függvényünk lenne, amelyik konstans referenciával venné át a paramétereit, nem pedig érték szerint? Vagy akkor, ha nem is összehasonlító függvényt adnánk át, hanem egy függvényobjektumot (funktort), amelynek függvényhívó operátora végzi az összehasonlítást? (A kerek zárójel is csak egy operátor: operator(), az is megírható egy saját típusra, ahogy a plusz + és a shift << operátort is megírhattuk.) Az ilyenekre nem mutathatnánk rá az előbbi pointerrel, amelyik azt mondja, hogy a paramétereit érték szerint átvevő függvényre mutat.

Legjobb ezért, ha azt mondjuk, hogy a rendező függvény harmadik paramétereként bármit átvehet, bármilyen típusú objektumot. Ez ugyanúgy typename típusú sablonparaméterrel tudjuk megoldani, ahogyan azt a legelső példában a max() függvénynél is láttuk. Természetesen ez egy másik típus lesz, nem T, mint a tömb elemei; adjuk neki mondjuk az F nevet! A rendezést végző függvényünk az alábbi formát ölti (teljes, kipróbálható kód):

#include <iostream>
#include <algorithm>
#include <string>

template <typename T, typename F>
void rendez(T *tomb, size_t meret, F elorebb) {
    for (size_t i = 0; i < meret-1; ++i) {
        size_t min = i;
        for (size_t j = i+1; j < meret; ++j)
            if (elorebb(tomb[j], tomb[min]))
                min = j;
        std::swap(tomb[i], tomb[min]);
    }
}

bool int_kisebb(int a, int b) {
    return a < b;
}

bool sztring_nagyobb(std::string const & a, std::string const & b) {
    return a > b;
}

template <typename T>
void tomb_kiir(T *tomb, size_t meret) {
    for (size_t i = 0; i < meret; ++i)
        std::cout << tomb[i] << ' ';
    std::cout << std::endl;
}

int main() {
    int szamok[5] = { 9, 6, 8, 7, 2 };
    rendez(szamok, 5, int_kisebb);
    tomb_kiir(szamok, 5);
    
    std::string szavak[3] = { "barack", "korte", "alma" };
    rendez(szavak, 3, sztring_nagyobb);
    tomb_kiir(szavak, 3);
}

A rendez függvény mindkét hívásánál a konkrét paraméterekből vezeti le a fordító a sablonparamétereket. A szamok[] tömb esetén T = int és F = bool(*)(int, int) adódik, tehát a legyártott függvény fejléce az alábbi:

template <>
void rendez<int, bool(*)(int, int)>(int *tomb, size_t meret, bool (*elorebb)(int, int));

A szavak[] tömb esetén pedig T = std::string és F = bool(*)(std::string const &, std::string const &) lesz a levezetés eredménye. A specializáció fejléce tehát az alábbi lesz (nem is baj, hogy ezt nem kellett kézzel leírni, hanem a fordító végezte el a munkát):

template <>
void rendez<std::string, bool(*)(std::string const &, std::string const &)> (std::string *tomb, size_t meret, bool (*elorebb)(std::string const &, std::string const &));

Érdemes megfigyelni a fenti kódban a tomb_kiir() függvénysablont is. Az is bármilyen tömbre képes példányosodni. Egyetlen kitétel, hogy a tömb elemein használható legyen a << operátor a kiíráshoz – ha ez teljesül, a függvény el tudja végezni a dolgát.

Ez a típusszemlélet a programozásban a duck typing: ami úszik és hápog, az kacsa. Ami kiírható, az jó lesz ennek a tomb_kiir() függvénynek. Ami pedig használható bináris predikátumként, az jó lesz a rendez() függvénynek, legyen az akármi is.