Metaprogramming - Többtípusos lista


A programozás már önmagában is elég jól tornáztatja az agyat, de ezt tovább lehet fokozni, ha valaki funkcionális programozásra adja a fejét. A legjobb eszköz erre a Prolog, de C++-ban is lehet hasonlóan érdekes feladatokat megoldani a template metaprogramming segítségével.

Ez nem egy hasznos cikk, inkább ilyen C++ cukorka. Implementálni fogom a variadic template-eket és a segítségükkel egy több típust támogató lista sablont.

Mentolos cukorka

A sablonos cikkben írtam egy számokat kezelő metalistát, ebből fogok kiindulni. A különbség annyi, hogy enum helyett typedef-ként nevesítem a metaváltozókat:

CODE
template <typename _head, typename _tail> struct typelist { typedef _head head; typedef _tail tail; }; template <typename _head> struct typelist<_head, void> { typedef _head head; typedef void tail; };

Hasonlóan lehet megadni a listát, mint a számok esetében, pl. typelist<int, typelist<float, typelist<double, void> > >. Ezt így hosszú leírni, ezért néhány makróval könnyítem meg a dolgot:

CODE
#define TL1(a) typelist<a, void> #define TL2(a, b) typelist<a, typelist<b, void> > #define TL3(a, b, c) typelist<a, typelist<b, typelist<c, void> > >

A könnyű kezeléshez két darab metafüggvényt kell implementálni: a lista i-edik elemének elérése és a lista hossza. Ily módon lehet majd iterálni a listán. Ezeknek a megvalósítása rekurzív sablonokkal történik:

CODE
template <typename ml, int index> struct type_at { typedef typename type_at<typename ml::tail, index - 1>::value value; }; template <typename ml> struct type_at<ml, 0> { typedef typename ml::head value; };

Feltűnhet, hogy sok helyen kell a typename kulcsszó, ugyanis a legtöbb név függ valamilyen sablon paramétertől és minősített. A baj az, hogy a fordítási hibákból elég nehéz kikövetkeztetni, hogy hova kéne typename.

CODE
template <typename ml> struct length { enum { value = length<typename ml::tail>::value + 1 }; }; template <> struct length<void> { enum { value = 0 }; };

Höfö append és erase metafüggvényt írni (ne felejtsük el, hogy a TMP Turing teljes, tehát ezek nem okozhatnak problémát).


Variálós sablon

Nem nehéz kitalálni, hogy egy variadic template paramétere egy ilyen típuslista lesz. A kérdés inkább az, hogy hogyan dolgozzuk fel a listaelemeket? Egy olyan listát kéne csinálni, aminek többféle push_back metódusa van, méghozzá olyanok, amik a típuslista egy adott elemét fogadják be.

Nagyon jó kis agytorna, de könnyen rá lehet jönni, hogy az öröklődést és a metódustúlterhelést kell kihasználni. Maga a multilista származzon egy olyan multilistából, ami tud iterálni a metalistán (azaz van egy int sablon paramétere):

CODE
template <typename type_list> class mtlist : public _mtlist<type_list, length<type_list>::value - 1> { };

Ebben az iterálós sablonban pedig lépésenként adjunk hozzá egy új metódust a már létezőkhöz. Fontos, hogy az ősosztály metódusait láthatóvá tegyük a using kulcsszóval, különben csak az utolsó lesz érvényes.

CODE
template <typename type_list, int index> class _mtlist : public _mtlist<type_list, index - 1> { typedef typename type_at<type_list, index>::value value_type; public: using _mtlist<type_list, index - 1>::push_back; void push_back(const value_type& value); };

A rekurziót a 0-s jelzésű specializált sablon fogja megállítani:

CODE
template <typename type_list> class _mtlist<type_list, 0> { typedef typename type_at<type_list, 0>::value value_type; public: virtual ~_mtlist(); void push_back(const value_type& value); };

Szemfüles olvasók észrevehetik, hogy a typedefeket priváttá tettem, így mindegyik osztályban tudom használni ugyanazt a nevet, nem lesz ütközés. Az érdekes dolgok most kezdődnek; hogyan lehetne implementálni a push_back metódusokat?

Lehet, hogy ez egy létező tervminta, mert sok helyen lehet alkalmazni: van egy absztrakt struktúra, legyen ez metalink_base, és ebből származtatok le konkrét, sablonos linkeket. Mindezt a legősibb (azaz a 0-s) multilistben kell megcsinálni, és ez fogja tárolni a fejelemet is.

CODE
protected: struct metalink_base { virtual ~metalink_base() {} metalink_base* next; metalink_base* prev; }; template <typename value_type> struct metalink : metalink_base { value_type value; }; metalink_base* head;

Egy érdekes észrevétel, hogy a sima listával szemben a fejelem itt nem foglal extra memóriát. Ugyanúgy a konstruktorban kell létrehozni. A metódusok implementációja innentől már magától értetődő, úgyhogy nem is írom le.


Iterátor

Csak a rend kedvéért egy iterátort is írtam az osztályhoz, ezt viszont már a legfiatalabb osztályba kell rakni. Ami érdekes ebben, hogy az operator * metódusa is sablon függvény kell legyen. Semmi akadálya, de én inkább egy get metódust írok, mert könnyebb leírni (megj.: ugyanis it.operator *<típus>()-t kéne egyébként, hacsak a fordító ki nem következteti a paramétert).

CODE
template <typename deref_type> deref_type& get() { metalink<deref_type>* cp = dynamic_cast<metalink<deref_type>*>(ptr); if( !cp ) throw 1; return cp->value; }

A típusbiztosságot a dynamic_cast garanáltja, tehát ha rossz típussal akarod dereferálni az iterátort, akkor vidám exceptiont kapsz. Ez nem mindig vicces, ezért csináltam még egy get_ptr metódust is (ez lenne az operator ->), ami viszont 0-t ad vissza, ha rossz a típus.


Summarum

Nézzük meg hogy működik ez:

CODE
typedef mtlist<TL3(int, float, Apple)> meta3_ifA; meta3_ifA l1; Apple a; a.name = "apple"; l1.push_back(a); l1.push_back(5); l1.push_back(3.5f); l1.push_back(2); l1.push_back(0.1f); int cnt = 0; for( meta3_ifA::iterator it = l1.begin(); it != l1.end(); ++it ) { if( cnt == 0 ) std::cout << it.get<Apple>().name << "\n"; if( cnt == 1 || cnt == 3 ) std::cout << it.get<int>() << "\n"; else if( cnt == 2 || cnt == 4 ) std::cout << it.get<float>() << "\n"; ++cnt; }

Látszólag semmi haszna nincs, hiszen elemenként le kell kezelni mindent. A pointeres metódus használatával viszont nem muszáj, például végrehajthatsz valamit csak Apple típusú elemekre. Mivel más nyelvekben nyelvi szinten van ilyen lista (pl. Objective-C), talán C++-ban is lehetne valamire használni. Hasonlóan őrült implementációk találhatóak a boost C++ libraryban.

Kód itt.


Höfö:
  • Bővítsd ki az implementációt a hiányzó metódusokkal!

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!