12. fejezet - Sablonok


Az előző példában írtam egy rendezett tömböt int-ekre. Adhattam volna olyan höföt is, hogy írd meg float -ra. És double -re, és std::string -re és Kiskutya -ra és TeherAuto -ra... Egy buta programozó leülne és elkezdené megírni az osztályt mindezen típusokra. De mi okosabbak vagyunk, mert megnézzük közelebbről az osztályt és észrevesszük, hogy a tömb elemeinek típusából semmi speciálisat nem használ ki, csak a < operátort (azaz, hogy rendezhető).



A kód további újrafelhasználhatóságát elősegitendő, a C++ -ban be lett vezetve a sablon függvény és a sablon osztály fogalma, amik egy mintát vagy működési elvet adnak meg, amiből a fordító le tudja generálni a osztályt/függvényt a konkrét típusra. Például egy teherautókat tartalmazó rendezett tömböt így lehetne deklarálni: orderedarray<TeherAuto> teherautok;

Rögtön nézzük is meg milyen volt az osztály eredetileg és hogyan néz ki ha sablonként írom meg:

CODE
// eredeti class orderedarray { private: int* data; size_t mycap; size_t mysize; // ... };
CODE
// sablonos template <typename value_type> class orderedarray { private: value_type* data; size_t mycap; size_t mysize; // ... };

A különbségek tehát: az osztály elé oda kell írni a template (sablon) kulcsszót, utána kacsacsőrök között lehet megadni a sablon paramétereket. Innentől kezdve már nem int -eket tartalmazó tömb lesz, hanem value_type -okat fog tárolni, amiről jelenleg még fogalmunk nincs, hogy mi, majd a sablon használója fogja megmondani.

Amikor létre szeretnél hozni mondjuk egy float -okat tartalmazó rendezett tömböt, akkor az osztály neve után kacsacsőrök között kell megadni a konkrét paramétereket. A fordító ezekkel a paraméterekkel fogja példányosítani a sablont (azaz a sablon alapján legenerálja a float -okat tartalmazó rendezett tömb osztályt).

CODE
orderedarray<float> oaf;

Világos, hogy olyan típussal fog csak működni ez a sablon, aminek van operator < metódusa. Ha például a TeherAuto osztálynak nincsen, akkor írni kell neki egyet.

A sablonokat nem .h meg nem .cpp fájlokba szokás írni, hanem .hpp kiterjesztésűbe (ettől függetlenül persze definiálhatsz templateket a többiben is). Azt viszont szem előtt kell tartani, hogy a fordítónak mindig látnia kell a metódusok implementációját is! Tehát ezeket vagy a sablon osztályon belül, vagy a sablon osztályon kívül, de ugyanabban a fájlban ajánlott implementálni.


Általában nem szeretnénk minden osztálynak operator < -t írni sőt, vannak esetek amikor szépen nem is lehet megoldani (mert például az összehasonlításnál szükség van egyéb külső objektumokra is). Ezért az STL konténerekben bevett szokás, hogy második template paraméterként meg lehet adni egy összehasonlító típust. A követelmény annyi, hogy legyen neki operator ()-e. Az ilyen típusokat más néven funktor-nak hívják (az nem követelmény, hogy sablon legyen).

CODE
template <typename value_type> struct default_less { bool operator ()(const value_type& a, const value_type& b) const { return a < b; } };

Ez lesz az alapértelmezett összehasonlítás, tehát a típus operator < metódusa (ha nincs neki, de ezzel akarjuk használni abból fordítási hiba lehet). A rendezett tömb sablon ezek után a következőképpen fest:

CODE
template <typename value_type, typename compare = default_less<value_type> > class orderedarray { private: value_type* data; // Az adat size_t mycap; // Mennyit tud tárolni size_t mysize; // Hány elem van public: compare comp; // Összehasonlító objektum // ... };

Rögtön látható, hogy sablon paraméternek is meg lehet adni alapértelmezett típust, ilyenkor ha nem adjuk meg azt a paramétert, akkor ezt fogja használni, Fontos: ha egy sablonnak a template paramétere is sablon, akkor ügyelni kell a lezáró >-kre, ugyanis ha rosszul írtad, akkor a fordító operator >>-nek értelmezi.

A sablonban publikus memberként megjelent az összehasonlítást végző funktor (konvencionálisan publikus). Minden esetben, ahol a korábbi implementációban a < b volt, oda most comp(a, b)-t kell írni. Na jó, de ahol meg a > b vagy a == b vagy a != b volt? Vegyük észre, hogy ez utóbbiak mind kifejezhetőek a < operátorral!

Példaként a _find metódus implementációját fogom ide bemásolni. A deklaráció a sablonon belül majdnem ugyanaz mint eddig (int helyett const value_type&), az implementációt viszont ravasz módon a sablonon kívül adom meg:

CODE
template <typename value_type, typename compare> size_t orderedarray<value_type, compare>::_find(const value_type& value) const { size_t low = 0; size_t high = mysize; size_t mid = (low + high) / 2; // logaritmikus keresés while( low < high ) { if( comp(data[mid], value) ) low = mid + 1; else if( comp(value, data[mid]) ) high = mid; else return mid; mid = (low + high) / 2; } return low; }

Látható, hogy tényleg csak a <-eket kell lecserélni a megfelelő dologra, minden más változatlan. A többi metódus implementációja ez alapján már nyilvánvaló. Azt azért még megsúgom, hogy a == b ekvivalens azzal, hogy !(a < b) && !(b < a)

Külön kiemelném, hogy az előző fejezetbeli implementációval szemben itt nem szabad memmove-ot és memcpy-t használni, mert halvány fogalmad nincs, hogy a value_type miket használ. A felelősséget át kell adni neki azzal, hogy te mindig meghívod vagy a copy konstruktort, vagy az értékadó operátort. Lehet, hogy ez nem mindig hatékony, de az STL-ben a biztonság az első. Ezért a konténerek használtánál előfeltétel, hogy a value_type-nak legyen copy konstuktora és értékadó operátora (akár a default).


Tekintsük az alábbi kódot:

CODE
struct cat { std::string name; int meow; }; orderedarray<cat> cats; cats.reserve(10); cats.clear();

Vajon lefordul, vagy nem? Hiszen a macskának nincs operator < -je. De igen, lefordul, és ezzel ki is derült egy úgymond "hibája" a sablonoknak: egy adott sablon metódust csak akkor példányosít a fordító, ha az meg van hívva valahol! Más szóval, ha sosem hívom meg azokat a metódusokat amik az operator <-et használják, akkor sosem derül ki a hiba!

Az új C++ szabványban majdnem bevezetett concept -ek megoldották volna ezt a problémát, mégpedig úgy, hogy a sablon paraméterre megszorításokat lehet definiálni:

CODE
// fontos: ez nem fordul le, sőt nem is biztos hogy ilyen lesz auto concept LessThanComparable<typename T> { bool operator <(const T& a, const T& b); } template <typename value_type> requires LessThanComparable<value_type> class orderedarray { // ... };

A concepteket sajnálatos módon kivették az új szabványból (ezzel gyakoratilag meggyilkolva), merthogy nem egyértelmű, hogy mennyire biztonságosak/használhatóak (kevés visszajelzés volt).


Bizonyos esetekben előfordulhat, hogy egy konkrét típusra sokkal egyszerűbben/hatékonyabban lehet megoldani az implementációt. Most egy nagyon buta példát fogok mondani: bool Világos, hogy egy ilyeneket tartalmazó rendezett tömb legfeljebb két elemű, sőt csak bitműveleteket használva meg lehet oldani mindent.

CODE
template <> class orderedarray<bool> { private: char data; public: orderedarray() : data(0) {} bool insert(bool value) { if( data & (value + 1) ) return true; data |= (value + 1); return false; } // ... inline size_t size() const { return ((data > 1) ? (data - 1) : data); } };

Ezt a módszert teljes specializációnak hívják; azaz amikor az összes template paramétert előre megadod. Lehet azonban egy sablont parciálisan is specializálni, ekkor a paramétereknek csak egy részét adod meg. Gondoljuk meg például, hogy a tömb tartalmazhat akár pointereket is. Specializálhatnánk úgy, hogy ha pointer típust kap template paraméterként, akkor automatikusan szabadítsa fel az elemet törléskor:

CODE
template <typename value_type> class orderedarray<value_type*> { private: value_type** data; size_t mysize; size_t mycap; public: void erase(value_type* ptr) { size_t i = find(ptr); if( i != npos ) { size_t count = (mysize - i); if( count > 0 ) { delete ptr; memmove(data + i, data + i + 1, count * sizeof(int)); } --mysize; if( mysize == 0 ) clear(); } } // ... };

Ez veszélyes lehet, hiszen ha a programozó nem tudja, hogy pointerekre speciális a sablon, akkor törlés után még használni akarja a nem létező objektumot. Ezért általában ezt nem szokás implementálni.

Fontos, hogy ha specializáltál egy sablont, akkor annak semmi köze nem lesz az eredetihez (a nevén kívül), tehát a metódusokat újra meg kell írni. Az STL-ben specializált sablon például az std::vector<bool>.


A fejezetet rögtön az osztálysablonokkal vezettem fel, pedig úgy lett volna logikus, hogy a függvénysablonokkal kezdem. Például írjunk egy olyan függvénysablont ami megcserél két változót, sőt rögtön specializáljuk is int-re (mert arra tudunk egy ügyes de érdektelen trükköt):

CODE
template <typename T> void swap(T& a, T& b) { T tmp(a); a = b; b = tmp; } template <> void swap<int>(int& a, int& b) { b = a + b; a = b - a; b = b - a; }

Itt említeném meg, hogy a fordító bizonyos esetekben képes kikövetkeztetni a template paramétert. Például ha a és b két ugyanolyan típusú változó, akkor elég swap(a, b) -t írni. Sőt, ez a kikövetkeztetés implicit konverziókat is figyelembe vesz:

CODE
template <typename R, typename T, typename U> R max(const T& a, const U& b) { return (a < b ? b : a); } // ... float a = 11; double b = 6; std::cout << max<double>(a, b) << "\n";

Ebben a kódban egy template paramétert mindenképpen meg kellett adni (a visszatérő érték típusát), a másik kettőt viszont gond nélkül kitalálta a fordító. A kódban viszont van egy pici csalás. Azt mondtam, hogy visszatérő értékkel nem lehet a metódusokat túlterhelni. Vajon mit fog csinálni az alábbi kód?

CODE
class Apple { public: template <typename R> R foo(float a, float b) { return R(a + b); } }; // ... Apple a; std::cout << a.foo<int>(2, 3) << "\n"; std::cout << a.foo<float>(3.4f, 2.3f) << "\n";

Érdekes módon lefordul, sőt még jól is működik. A szabvány szerint ugyanis a template metódusok szignatúrája tartalmazza a konkrét template paramétereket is. Kicsit érdekesebb és nem teljesen nyilvánvaló amikor egy template osztálynak van template metódusa:

CODE
template <typename T> class Lemon { public: template <typename U> void foo(T a, U b); }; template <typename T> template <typename U> void Lemon<T>::foo(T a, U b) { std::cout << a << ", " << b << "\n"; } // ... Lemon<int> l; l.foo<float>(3, 5.6f);

Kényelmesebb lenne template<typename T, typename U> -t írni, de ez jelenleg még nem támogatott. Jó hír viszont, hogy általában ennél rondább kódot nem kell leírni (nem ám egy túróst...).


Egy igen érdekes feature-je a C++ -nak, hogy a templatek által használható funkcionális programozási nyelvként. Ekkor viszont a program a C++ fordítón fog futni. Nézzünk egy egyszerű példát: számoltassuk ki a fordítóval két szám legnagyobb közös osztóját!

CODE
template <signed a, signed b> class gcd { public: enum { value = gcd<b, a % b>::value }; }; template <signed a> class gcd<a, 0> { public: enum { value = a }; }; // ... std::cout << gcd<16, 8>::value << "\n";

Rögtön látható a példából, hogy a központi fogalom a rekurzió: a megállási feltételt egy template specializációval állítottam elő. Fontos, hogy template paraméterben (mint eddig) csak konstans kifejezés állhat, tehát futási idejű számokra ez nem fog működni.

A template metaprogrammingról belátható, hogy Turing teljes, azaz gyakorlatilag bármilyen (Turing géppel leírható) algoritmust implementálni lehet vele. A programozás szemléletében viszont egy érdekes változást okoz. Írjunk például egy számokat tartalmazó listát és egy value_atmetódust, ami az i-edik elemet adja vissza:

CODE
// metalista template <int head, typename tail> struct metalist { typedef tail next; enum { value = head }; }; template <int head> struct metalist<head, void> { enum { value = head }; }; // value_at metafüggvény template <typename ml, int index> struct value_at { enum { value = value_at<ml::next, index - 1>::value }; }; template <typename ml> struct value_at<ml, 0> { enum { value = ml::value }; }; // könnyebb leírni, ha előre metadeklaráljuk #define mymetalist metalist<5, metalist<3, metalist<6, void> > > // ... std::cout << value_at<mymetalist, 0>::value << "\n"; std::cout << value_at<mymetalist, 1>::value << "\n"; std::cout << value_at<mymetalist, 2>::value << "\n";

A lista végét az jelzi, ha a tail paraméternek void-ot adsz meg. Világos, hogy ez nem csak számokkal játszható el, hanem tetszőleges típussal, azaz csinálhatnék típuslistákat is; nem kell magyarázni hogy azokkal meg milyen őrültségeket lehetne művelni (pl. változó argumentumszámu sablon!).

Általában a rekurzió nem mehet a végtelenségig: a fordítókban van egy mélység ami után hibát adnak.


Röviden megmutattam a sablonok használatát, ezzel kapcsolatban majd sok gyakorlati példa lesz. Egy kicsit belenyúltam a template metaprogrammingba is, ami egy hatalmas erőssége a C++ -nak; annyira hogy léteznek már az STL-hez hasonló metaSTL konténer implementációk is, sőt ez egy aktív kutatási terület az informatikában (generikus programozás).

Amit még megemlítenék az a template osztályok forward illetve barát deklarációja:

CODE
// narancs forward deklaráció template <typename T> class Orange; // kiwi osztály narancs referenciával template <typename T> class Kiwi { public: void foo(const Orange<T>& o); }; // narancs template <typename T> class Orange { template <typename T> friend class Kiwi; private: T value; public: Orange(T v) : value(v) {} }; // metódus implementáció template <typename T> void Kiwi<T>::foo(const Orange<T>& o) { std::cout << o.value << "\n"; } // ... Kiwi<int> k; k.foo(Orange<int>(7));

Tehát a forward és a barát deklarációban is meg kell adni a sablon paraméterlistáját. Hasonlóan működik függvényekkel is. Amit nem lehet megcsinálni az a template typedef.

A sablonos rendezett tömb kódja megtalálható itt.


Höfö:
  • Írd meg az orderedmultiarray osztályt is sablonként!
  • Írj egy olyan metaprogramot, ami kiszámolja egy szám faktoriálisát!

Irodalomjegyzék

http://en.cppreference.com/w/cpp
http://www.cplusplus.com/
http://www.parashift.com/c++-faq-lite/ (ezt különösen ajánlott elolvasni)
http://aszt.inf.elte.hu/~gsd/halado_cpp/ (ezt is)

back to homepage

Valid HTML 4.01 Transitional Valid CSS!