Pataki Norbert - Generatív programok helyessége

Alapadatok

Év, oldalszám:2013, 134 oldal

Nyelv:magyar

Letöltések száma:49

Feltöltve:2016. július 14.

Méret:419 KB

Intézmény:
-

Megjegyzés:
ELTE IK

Csatolmány:-

Letöltés PDF-ben:Kérlek jelentkezz be!

Értékelések

Nincs még értékelés. Legyél Te az első!

Legnépszerűbb doksik ebben a kategóriában

A programozás elmélete

Fóthi-Steingart - Bevezetés a programozáshoz

Elemi programozási tételek

Aszalós László - Algoritmusok

Tartalmi kivonat

Generatı́v programok helyessége Doktori értekezés 2013 Pataki Norbert patakino@elte.hu Témavezető: Dr. Porkoláb Zoltán, egyetemi docens Eötvös Loránd Tudományegyetem, Informatikai Kar, 1117 Budapest, Pázmány Péter sétány 1/C ELTE IK Doktori Iskola Doktori program: Az informatika alapjai és módszertana Az iskola vezetője: Dr. Benczúr András A program vezetője: Dr. Demetrovics János akadémikus A projekt az Európai Unió támogatásával, az Európai Szociális Alap társfinanszı́rozásával valósul meg (a támogatás száma TÁMOP4.21/B-09/1/KMR-2010-0003) Tartalomjegyzék I. Bevezetés I.1 Célkitűzések . I.2 A dolgozat felépı́tése . II. Alapok II.1 Sablonok C++-ban II.2 Generatı́v és generikus programozás II.3 A C++ Standard Template Library II.4 Motivációs példák

II.41 Fordı́tási hibaüzenetek II.42 Invalid iterátorok II.43 Funktorokkal kapcsolatos hibák II.44 Allokátorokkal kapcsolatos hibák II.45 Másoló algoritmusokkal kapcsolatos hibák II.46 Törlő algoritmusokkal kapcsolatos hibák II.47 A unique algoritmus II.48 Algoritmusok speciális előfeltételei II.49 A find és a count algoritmus II.410 A vector<bool> konténer II.411 COAP II.412 Fejállományokkal kapcsolatos problémák II.413 Iterátorok konverziója II.414 Az asszociatı́v konténerek hordozhatósággal kapcsolatos problémái II.415 A vector és a string reallokációja II.416 Iterátorok és pointerek összetévesztése II.417 Virtuális destruktorok hiánya 5 6 7 . . . . . . . . . . . . . . . . . 9 9 13 14

24 24 27 29 35 36 38 39 40 41 42 45 47 47 . . . . 49 50 51 52 III. Az STL formális megközelı́tése 54 III.1 A Hoare-módszer bővı́tése 54 III.11 A Hoare-módszer 54 2 Tartalomjegyzék 3 III.12 A formalizmus bővı́tése III.13 Speciﬁkációk III.14 Példák III.2 LaCert III.3 Összegzés . . . . . . . . . . . . . . . . . . . . . . . . . IV. Fordı́tás idejű megoldások IV.1 Warning-ok generálása IV.2 Hibás példányosı́tások IV.21 A vector<bool> konténer IV.22 COAP IV.3 Algoritmusok IV.31 Az iterator traits kibővı́tése IV.32 Másoló algoritmusok IV.33 A count és a find algoritmus IV.34 A unique algoritmus IV.4 Adaptálható funktorok IV.5 Allokátorok IV.6 Reverse iterátorok IV.7 Lusta példányosı́tás IV.8

Összegzés V. Futási idejű megoldások V.1 Az iterator traits kibővı́tése V.2 Invalid iterátorok V.3 Másolás-biztonságos iterátorok V.4 Törlő iterátorok V.5 Algoritmusok előfeltétele V.6 Funktorok V.7 Összegzés VI. Összefoglalás A. Az A.1 A.2 A.3 STL bővı́tése Konténerek . Algoritmusok Iterátorok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 60 63 69 74 . . . . . . . . . . . . . . 75 75 78 78 81 82 82 83 87 90 94 96 97 99 100 . . . . . . . 102 102 103 107 109 111 114 116 118 a . . . C++11-ben 132 . 132 . 132 . 133 Köszönetnyilvánı́tás Legelőször szeretném témavezetőmnek, Porkoláb Zoltánnak (gsd-nek) megköszönni a sokéves témavezetői munkáját! A közös munkánk nagyon sokat jelent nekem. Még a unique-ot is legyőztük! Köszönöm páromnak, Melindának, hogy megteremtette az otthonunkat, ahol kényelmesen dolgozhattam, támogatott és gondosan lektorálta a cikkeket és a disszertációmat. Még nagyon hosszú a lista, nem szeretnék senkit sem kihagyni, de szeretném megköszönni a családomnak, a barátaimnak és a munkatársaimnak a kitartó támogatást. A

szerzőtársaimnak köszönöm a munkát, amit a közös cikkekbe öltek. 4 I. fejezet Bevezetés A programozás történetének elmúlt ötven évében egyre bonyolultabb és öszszetettebb alkalmazások születtek. Ahogy a szoftverek egyre komplexebbé váltak, a fejlesztőknek egyre több implementációs részlettel kellett foglalkozniuk. Felmerült az igény arra, hogy a rendszeresen használt kódrészleteket ne kelljen újra és újra megı́rni, hanem azok külső egységekként átvihetők legyenek akár különböző alkalmazások között is. Az ilyen elven megvalósı́tott szoftver egységeket nevezzük könyvtáraknak (library) Kezdetben, a procedurális paradigma szemléletének megfelelően, a függvénykönyvtárak terjedtek el. Alprogramok (függvények, eljárások) segı́tségével előre megı́rtak olyan funkcionalitásokat, amelyeket később különböző paraméter

értékekkel számos környezetben meghı́vhattak Például FORTRANhoz vagy C-hez számtalan ilyen elven működő könyvtár elérhető Az objektum-orientált programozás térhódı́tásával együtt a könyvtárak felépı́tése is megváltozott. Függvénykönyvtárak helyett osztálykönyvtárakat implementáltak és használtak a programozók. Ekkor előre megı́rt osztályok, öröklődés és virtuális metódusok segı́tségével hoztak létre osztályhierarchiákon alapuló könyvtárakat, amelyek a korábbi megoldásokhoz képest jobban támogatták a kódújrafelhasználást. A Simula, Smalltalk, Eiﬀel és a Java programozási nyelvek elterjedésével ezek a könyvtárak széleskörben elfogadottá váltak. Az objektum-orientált könyvtáraknál még ﬂexibilisebb megoldást nyújtanak a generikus könyvtárak. A konténerek és az algoritmusok függetlensége miatt ezek a

rendszerek egyszerre több irányba bővı́thetőek és feloldanak olyan problémákat, amelyeket régebbi megközelı́téssel nem lehet kényelmesen kezelni. A C++ sablonok segı́tségével fordı́tási időben végrehajtódó kódokat is lehet ı́rni, ezek a template metaprogramok. Léteznek metaprogramozási technikákon alapuló könyvtárak is [1, 104, 118]. Az aktı́v könyvtárak (active 5 6 Bevezetés libraries) olyan könyvtárak, amelyek fordı́tási időben dinamikusan viselkednek: döntéseket hoznak a felhasználás környezetének ismeretében, optimalizációkat végeznek fordı́tás közben, stb. [15] A C++ Standard Template Library (STL) a generikus programozási paradigmán alapuló könyvtárak mintapéldája. Professzionális C++ program elképzelhetetlen a szabványkönyvtár részét képező STL alkalmazása nélkül. Az elegáns kialakı́tású könyvtár használata csökkenti

a klasszikus C és C++ hibák lehetőségét, növeli a kód minőségét, karbantarthatóságát, érthetőségét és hatékonyságát [78]. Ugyanakkor a könyvtár alkalmazása nem garantál hibamentes kódot, sőt a könyvtár generikus megközelı́tése miatt új tı́pusú hibalehetőségek keletkezhetnek. Ezeknek egy részét a fordı́tóprogram nem ellenőrzi és futási időben nem derül ki a kód hibás jellege. Bizonyos esetekben a hiba okát is nehéz felderı́teni akár debugger alkalmazások segı́tségével is. Nem megdöbbentő, hogy ilyen hibák nagy számmal előfordulnak C++ nyelven ı́rt programok implementációjában [53]. Kutatásaim középpontjában ezen hibalehetőségek leküzdése áll mégpedig úgy, hogy az STL hatékonysága és rugalmassága megmaradjon. I.1 Célkitűzések Kutatásaim kiindulópontja a [53] könyv volt, melyben 50 tanács található az STL

helyes, hatékony használatáról. Ezek a tanácsok szövegesen (informálisan) ı́rták le, hogy mit hogyan érdemes használni, mi milyen hibát okozhat Többek között ilyen témák találhatók a könyvben: • Részesı́tsük előnyben az intervallumokat használó tagfüggvényeket • Használjuk az empty-t, a size == 0 vizsgálat helyett • Használjuk a reserve-t, hogy elkerüljük a felesleges reallokációkat • Fontoljuk meg az asszociatı́v tárolók cseréjét rendezett vector-ral • Ismerjük a lehetőségeinket a rendezésekkel kapcsolatban Szoftveres megoldást nem kı́nál a könyv a tanácsokhoz, ezért azt a célt tűztem ki magam elé, hogy a programozók dolgát megkönnyı́tem az elkövethető hibák minél átfogóbb kiszűrésével. A szűrést segı́tsem mind formális, mind szoftveres eszközökkel Egy kı́sérleti eszköz az STLlint [35], mely egy módosı́tott

fordı́tóprogram alapján működik, sokáig online elérhető volt, Bevezetés 7 de működése nem váltotta be a hozzá fűzött reményeket, támogatása megszűnt. Az STLlint kizárólag fordı́tási idejű információk alapján működött Az én megoldásaim ezzel szemben a könyvtár implementációjának bővı́tésén, változtatásán alapulnak, szabványos fordı́tóprogramok használata mellett. Én is igyekeztem a lehetséges hibákat fordı́tási időben felderı́teni és a C++ sablon konstrukciója segı́tségével fordı́tási ﬁgyelmeztetéseket generálni, de a megoldásaim egy része futási időben működik. Tehát céljaimat a következő prioritással lehet deﬁniálni: 1. Az STL generikusságából adódó hibalehetőségek kiszűrése fordı́tási időben, nem-intruzı́v módon 2. Az STL generikusságából adódó hibalehetőségek kiszűrése

fordı́tási időben, az STL implementáció módosı́tásával 3. Az STL generikusságából adódó hibalehetőségek kiszűrése futási időben, nem-intuzı́v módon, a szabványos aszimptotikus futási idők betartásával (törekedve a minimális overhead-re) 4. Az STL generikusságából adódó hibalehetőségek kiszűrése futási időben, az STL implementáció módosı́tásával, a szabványos aszimptotikus futási idők betartásával (törekedve a minimális overhead-re). 5. Az STL generikusságából adódó hibalehetőségek kiszűrése futási időben, nem-intruzı́v módon, a szabvány aszimptotikus futási idő korlátainak megsértésével 6. Az STL generikusságából adódó hibalehetőségek kiszűrése futási időben, az STL implementáció módosı́tásával, a szabvány aszimptotikus futási idő korlátainak megsértésével. Emellett törekedtem a

reverse-kompatibilitásra: meglévő (hibás) kódrészletek (legacy kódok) működhessenek az eredeti viselkedésnek megfelelően, hiszen nem lehet több millió kódsort hirtelen átı́rni például eddig nem ismert kivételek elkapására. Ha nem maradnék reverse-kompatibilis és például kivételeket dobnék hiba esetén, akkor rengeteg program abortálhatna le nem kezelt kivételek miatt. I.2 A dolgozat felépı́tése A dolgozat további fejezeteiben bemutatom a kutatásaimat, amelyekkel az STL használata biztonságosabbá tehető. A második fejezetben bemutatom a 8 Bevezetés generatı́v és generikus programozási paradigmát, részletezem az STL felépı́tését és a fontosabb részeit. Emellett példákat adok olyan kódokra, amelyek lefordulnak és hibás voltukat semmi sem fedi fel. A harmadik fejezetben bemutatom az általam kidolgozott eszközöket, amelyekkel az STL formálisan deﬁniálható.

A negyedik fejezetben olyan megoldásokat adok, amelyek fordı́tási időben elősegı́tik az STL hibás használatának kiszűrését a fordı́tóprogram módosı́tása nélkül. Az ötödik fejezetben olyan általam kidolgozott eszközöket részletezek, amelyek vagy futási időben jelzik az STL hibás használatát vagy leküzdik a hiba okát. Végezetül összefoglalom a dolgozat eredményeit Kutatásaimat a 2003-as C++ szabvány szerint végeztem Az azóta elfogadott C++11 szabvány kapcsolódó részeit a függelékben ismertetem. II. fejezet Alapok II.1 Sablonok C++-ban A CLU programozási nyelv vezette be először azt a nyelvi konstrukciót, melylyel tı́pussal paraméterezhetünk programegységeket. A parametrikus polimorﬁzmus legfontosabb eszköze lett a template vagy generic [115] A C++ template-jei segı́tségével osztály- és függvénysablonok ı́rhatóak, amelyek sablonparaméterekkel

paraméterezhetőek: fordı́tási időben ismert értékű paraméterekkel láthatóak el. Ezen paraméterek ismeretében a fordı́tóprogram (compiler) képes példányosı́tani a sablont és generálni a konkrét függvényt vagy osztályt. Vizsgáljuk meg a következő függvénysablon példát: template <class T> const T& max( const T& a, const T& b ) { return a < b ? b : a; } A kódrészlet két tetszőleges, de azonos tı́pusú objektum közül adja viszsza a nagyobbat. Használható int-ekkel, double-ökkel, stb minden olyan tı́pussal lehet ezt a sablont használni, amelynek van operator< művelete. Látható, hogy ez az elvárás csak a sablon törzséből derül ki. A sablon önmagában nem használható, a fordı́tóprogram sem elemzi a kódot átfogóan, nem generálódik belőle alacsony-szintű kód. Példányosı́tani (instantiate) kell a használathoz

Példányosı́táskor a sablonból konkrét kód generálódik, amelyben a formális sablonparaméterek helyén az aktuális paraméterek szerepelnek. C++-ban a fordı́tóprogram képes a függvénysablonok esetében a hı́vás 9 10 Alapok paramétereiből levezetni a sablon paramétereket, ezt a nevezik paraméterdedukciónak (parameter deduction). Az általánosságnak hátránya is van, például nem deﬁniált, hogy mit ı́r ki az alábbi kódrészlet: std::cout << max( "one", "ten" ); Ilyenkor a fordı́tóprogram a "one" és a "ten" literálok tı́pusát egyaránt const char[4]-nek vezeti le. A tömbök konvertálódnak első elemre mutató pointerré, és a kódrészlet két független tömb első elemére mutató pointert hasonlı́t össze, melynek eredménye nemdeﬁniált. Ha lexikograﬁkus rendezést szeretnénk használni, akkor a függvénysablon

explicit specializációját alkalmazhatjuk: std::cout << max<std::string>( "one", "ten" ); A C++ osztálysablonok esetében lehetőséget ad felhasználói specializációra is [111]. A specializációnak két fajtája van: részleges és teljes A részleges specializáció esetében egy eltérő implementáció léphet életbe, ha egy tı́pus csoport valamely tagjával példányosı́tjuk a sablont. A teljes specializáció esetében egy eltérő implementáció léphet életbe, ha egy konkrét tı́pussal példányosı́tjuk a sablont. Nézzük meg az alábbi példát: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 template <class T> class Foo { // . }; template<class T> class Foo<T*> { // . }; template <> class Foo<bool> { // . }; Foo<char> a; // 1-5 sorok példányosı́tása Alapok 20 21 11 Foo<bool*> b; // 7-11 sorok példányosı́tása

Foo<bool> c; // 13-17 sorok példányosı́tása A különböző sablonparaméterek miatt eltérő implementációt használnak a különböző objektumok. A specializációk más belső reprezentációt használhatnak, sőt a publikus interface-ük is eltérő lehet Mivel a sablon paraméterek fordı́tás idejű paraméterek, ı́gy az, hogy melyik specializációt alkalmazzuk fordı́tási időben kiderül. A sablonok specializációi egy újfajta megközelı́tést hoztak a C++ nyelvbe. Segı́tségükkel fordı́tási időben futó kódrészletek hajthatóak végre, ezeket nevezzük template metaprogramoknak [1]. A metaprogramokat funkcionális megközelı́téssel kell megı́rni: csak a rekurzı́v példányosı́tásokra és specializációkra számı́thatnak a programozók, nincsenek más vezérlési szerkezetek. A metaprogramok résznyelve Turing-teljes, de a valódi korlátai a mai napig kutatott

terület [84]. A metaprogramok tipikus alkalmazásai: extra fordı́tás-idejű ellenőrzések, algoritmusok végrehajtása, a futás-idejű programok optimalizációi, domain-speciﬁkus nyelvek deﬁniálása. A metaprogramok alanya maga a C++ program A metaprogramok lehetősége a C++ sablonjait egy rendkı́vül fontos konstrukcióvá teszi. A max sablon függvénynél már emlı́tettem, hogy a sablonparaméterekkel kapcsolatos elvárások kizárólag az implementációban jelennek meg, a deklarációban semmilyen információ nem szerepel ezzel kapcsolatban. Ha olyan tı́pussal használjuk, amelynek nincs operator< művelete (pl. komplex számok kezeléséhez használt std::complex<double>), akkor a fordı́tóprogram példányosı́tja a sablont és példányosı́tott kód fordı́tásakor realizálja, hogy a kód nem lefordı́tható és hibaüzenet ad, amelyben a sablonra hivatkozik A fordı́tóprogramok jelzik,

hogy milyen aktuális sablonparaméterek mellett jött elő a hiba, de nem a példányosı́tást jelzik a hiba okaként Ennek a jelenségnek az az oka, hogy a C++ sablonjai megszorı́tás nélküliek (unconstrained). Ez tervezési tulajdonsága a C++ sablonjainak [26] Ez a tervezési tulajdonság biztonságos abból a szempontból, hogy hibás példányosı́tás esetében fordı́tási hibaüzenetet kap a programozó, nem jön létre hibásan futó program. Ugyanakkor sokszor bonyolult, nehezen érthető hibaüzenetekkel jár a megszorı́tás nélküli sablonok hibás használata. Ezért a kutatók elkezdtek metaprogramozási alapokkal ellátott könyvtárakat implementálni, amivel a fordı́tás korábbi pontján kiderülnek a hibás példányosı́tások. Sajnos azonban ezek a könyvtárak nem tudnak minden problémát kezelni, ezért a kutatók nyelvi bővı́tést szorgalmaztak a könyvtár-alapú

megoldásokkal szemben [31]. Az új C++ nyelvi konstrukciót, a concept-et két eltérő formában képzelték el: a University of Texas A&M [95] és az Indiana University [39] 12 Alapok kutatói. A konstrukciók közös lényege, hogy tı́pusmegszorı́tások deﬁniálhatóak legyenek a C++ sablonparaméterein, oly módon, hogy megtartsák a C++ sablon rendszerének előnyeit. A két eltérő verziót egységessé formálták [33], implementációs technikákat dolgoztak ki [34, 37, 38] és egy kı́sérleti fordı́tóprogramot (ConceptC++) implementáltak, hogy gyakorlatban is ki lehessen próbálni az ötleteket. A concept lett a leginkább várt nyelvi bővı́tés az új C++ szabványban, miután 2008-ban beszavazták a C++0x-be. Stroustrup egy eltérő, egyszerűsı́tett concept fogalmat deﬁniált [94], aminek az lett a következménye, hogy 2009 nyarán a Szabványosı́tási Bizottság úgy döntött,

hogy az új C++ szabványban mégsem lesz benne a concept konstrukció. Nem csak tı́pusok lehetnek sablonparaméterek. C++-ban integrális konstansok (pl int-ek, bool-ok, char-ok, stb), mint fordı́tási idejű adatok, szintén átadhatóak sablonparaméterként. Osztálysablonok esetében lehetőség van default sablonparaméterek megadására is Az ilyen paramétereket objektumok tı́pusának megadásakor nem kötelező megadni, ha nincs megadva, akkor a default paraméterek lépnek életbe. A sablonok alkalmazásával nagymértékben növelhető a programok biztonsága. A dolgozatban részletesebben tárgyalt témák mellett az alábbi kutatásokat folytattam C++ template-kkel kapcsolatban Megvizsgáltam egy template metaprogramozás alapú tesztelési keretrendszer lehetőségét [62]. A cikkben megmutattam, hogy számos előnnyel járhat egy olyan tesztelési keretrendszer, ahol a futási idejű programokat metaprogramok

segı́tségével teszteljük. A metaprogramozás terjedését jelentősen hátráltatja a szokásos programfejlesztői eszközök hiánya. Részt vettem egy graﬁkus metaprogram debugger és olyan vizualizációs eszköz kidolgozásában, amely bemutatja a példányosı́tás folyamatát kép ﬁle-okba kiexportált gráfok formátumában Ezek az eszközök nagymértékben elősegı́tik a programozói hibák kijavı́tását és elkerülését [8, 74]. Különböző objektum-orientált nyelvek eltérően támogatják a paradigmát, minden nyelv kicsit eltérő konstrukciót ad például a metódusok deklarációjának ﬁnomhangolásához. Több olyan konstrukciót implementáltunk C++ban, ami a nyelvben eredetileg nincs benne: Java-ban használt felüldeﬁniálhatatlan ﬁnal metódusok [101], elrejthetetlen metódusok, amelyek megakadályozzák, hogy eltérő deklarációval (véletlenül)

elrejtsünk egy metódust [98], Eiﬀel-ben létező metódus átnevezés konstrukció [102]. Az Eiﬀel-ben használt tagok szelektı́v hozzáférését is megvalósı́tottuk template metaprogramok segı́tségével [56]. Ezen konstrukciók sablonok segı́tésével működnek és használatuk segı́tségével programozói hibákat lehet elkerülni. A C nyelv szabvány könyvtárának printf függvénye úgy működik, hogy első paramétere egy formázó string ami meghatározza, hogy a további pa- Alapok 13 ramétereket hogyan kell kiı́rni az kimenetre. A formázó string értékét a fordı́tóprogramok nem kezelik, ı́gy használata hibákat okozhat. Kidolgoztunk egy metastring könyvtárat, melyben a string-ek értéke fordı́tás idejű információ. Ezekkel a metastring-ekkel a megı́rtuk a printf olyan verzióját, amely képes tı́pus ellenőrzéseket elvégezni, ı́gy képes fordı́tás

közben kiszűrni a programozói hibákat [104]. Hasonló problémák jöhetnek elő a multicore programozást támogató C++ könyvtár, a FastFlow kapcsán is [2]. A különböző task-ok egy void* (tı́pustalan) pointer segı́tségével adnak át tetszőleges adatot egymásnak [99]. Ezt a hibalehetőséget sablonok segı́tségével elimináltuk a könyvtárból, sőt hatékonyabbá is tettük az implementációt: a virtuális függvények alkalmazását fordı́tási idejű mechanizmusra cseréltük sablonokkal [100]. Részt vettem a C++-hoz tervezett concept konstrukció egy bővı́tésében is, hogy a private, public és protected módosı́tók használhatóak legyenek concept map-ekben is [103]. Más nyelvek gyakran másképpen kezelik a generikus elemeket [9]. Különböző modern nyelvekben használatos nyelvi konstrukciót összehasonlı́tottam [85]. II.2 Generatı́v és generikus programozás A

máig rendkı́vül széleskörben használt objektum-orientált programozás hiányosságaira fény derült az ezredfordulóra. Kiderültek a gyengeségei, és újabb programozási technikák alakultak ki, amelyekkel ezeket a gyengeségeket próbálták legyőzni. Azok a technikák, amelyek valamilyen eszköz (tool) segı́tségével generálnak kódot a generatı́v (generative) módszerek. Sokféle generatı́v technika létezik: a már emlı́tett template metaprogramozás is egy ide tartozó módszer: a fordı́tóprogram sablonok példányosı́tásán keresztül kódot generál és értékel ki. Az aspektus-orientált programozás a logikailag elkülönülő, de ﬁzikailag egybetartozó kódokat tudja aspektusokba modularizálni, amit egy aspektus-szövő szoftver (weaver) sző össze [48]. Az objektum-orientált jellegzetes gyengeségére az ún. expression problem világı́t rá [116]. Tekintsük az alábbi

nyelvtant [109]: Exp ::= Lit | Add Lit ::= (nem-negatı́v egész) Add ::= Exp ’+’ Exp Tegyük fel, hogy megvalósı́tunk egy print() műveletet, amellyel az output-ra kiı́rhatjuk a kifejezést. A feladat objektum-orientált megoldásához két különböző megoldás adható. Az első az adatközpontú: minden műveletet 14 Alapok virtuális metódusként deﬁniálunk egy közös bázisosztályban, és minden speciﬁkus osztályban felüldeﬁniáljuk. Ez a tipikus objektum-orientált megoldás, megvan az a moduláris tulajdonsága, hogy új osztályokat vehetünk fel úgy, hogy a meglévő kódhoz nem kell hozzányúlnunk, pl. kivonáshoz: Exp ::= . | Neg Neg ::= ’-’ Exp Ha viszont egy új műveletet szeretnénk bevezetni, pl. eval, ami kiértékeli a (rész)kifejezést, akkor minden egyes osztályt módosı́tanunk kell, hogy speciﬁkusan implementálhassuk a műveletet. A visitor design pattern [29]

segı́tségével a műveleteket lehet osztályként ábrázolni: ilyenkor könnyű újabb műveleteket bevezetni a rendszerbe, de bonyolult feladat új adatszerkezeteket felvenni. Az objektum-orientált paradigma nem támogatja, hogy párhuzamosan az adat- és művelet-centrikusan is kiterjesszük az implementációt. Egy könyvtár esetében viszont, ha új műveleteket (algoritmusokat) kell bevezetni a könyvtár implementációját kellene módosı́tani, ami nem mindig oldható meg. Az egyik legfontosabb generatı́v paradigma, a generikus programozás [87] erre a problémára ad választ: az adatszerkezetek és műveletek absztrakt megfogalmazásával a komponensek konﬁgurálhatóságát és együttműködését megszervezi, miközben elvonatkoztat az érdektelen részletektől [59]. Dolgozatom központi témája a generikus programozáshoz tartozó STL helyes használata, de ezenkı́vül foglalkoztam

aspektus-orientált programok helyességével [81] és metaprogramok helyességével is [73]. II.3 A C++ Standard Template Library A C++ Standard Template Library (STL) egy generikus programozási paradigmán (generic programming paradigm) alapuló könyvtár, mely része a C++ szabvány könyvtárának. Az STL kihasználja a C++ sablonok lehetőségeit, ı́gy egy bővı́thető, hatékony, mégis ﬂexibilis rendszert alkot Az STL (és a generikus programozás) központi elve az általánosı́tás [53]. Scott Meyers az STL-t a szabványkönyvtár legforradalmibb részének tartja [54]. Kiemeli, hogy a felépı́tése, a rugalmassága, bővı́thetősége, a szabvány miatti hatékonysága teszi nagyon jól használhatóvá. Szerinte az STL nem szoftver, hanem konvenciók halmaza, és emiatt forradalmi. Dewhurst viszont azt a tulajdonságát emeli ki, hogy a tárolók szerkezetükkel és működésükkel kapcsolatos

döntések már fordı́tási időben megszületnek [17]. Emiatt hatékony és kicsi kód készül, mely teljesı́tmény tekintetében pontosan alkalmazkodik az adott felhasználási módhoz. Bruce Eckel az STL-nek azt a jó Alapok 15 tulajdonságát is kiemeli, hogy teljesen platformfüggetlen [23]. Karbantartásilag az STL egyik legnagyobb előnye a szabványos névhasználatban rejlik: az STL komponensei minden C++ programozó számára ugyanazt jelentik. Ez olyan szemantikai többlettel jár, amit semmilyen kézzel ı́rt kód nem tud megadni. A fenti jó tulajdonságok elsősorban az STL egyedi szerkezetével magyarázhatóak. Az STL alapvető komponensei: konténerek (containers), algoritmusok (algorithms), iterátorok (iterators), funktorok (functors), átalakı́tók (adaptors), allokátorok (allocators). A konténerek (pl. vector, set, map, stb) alapvető feladata az adatok memóriában történő elhelyezése,

tárolása és a memória konzisztensen tartása. A konténerek csoportosı́thatóak: szekvenciális és asszociatı́v konténerekre. (Meyers egy másik csoportosı́tást is használ az STL konténerek kapcsán: láncolt és egybefüggő-memória konténerekre [53].) Az STL-ben három szabványos szekvenciális konténer sablon található: list, vector, deque, valamint a string konténer, ami konkrétan karakterek tárolására optimalizált. Ezeknél a felhasználó deﬁniálja, hogy az elemek hova kerüljenek a konténerben A vector egy olyan konténer, amely garantáltan egybefüggő tárterületen tárolja az elemeket, ı́gy gyorsan elérhető tetszőleges eleme, de a törlés és beszúrás műveletek csak a konténer végén hatékonyak. A vector közvetlen elérésű iterátorokat biztosı́t, amelynek segı́tségével az STL összes algoritmusa használható. A list konténer egy kétirányú

láncolt lista, amelybe tetszőleges helyre hatékonyan lehet beszúrni illetve tetszőleges helyről lehet hatékonyan törölni, de a konténer tetszőleges eleme csak lineáris időben érhető el. A list konténer bidirectional, azaz kétirányú iterátorokat garantál. A deque egy kettős végű sor, ahol a konténer két végén lehet hatékonyan megváltoztatni a konténer méretét. Szintén random access kategóriájú iterátorokat biztosı́t Ugyan ezek a konténerek hasonló interface-szel rendelkeznek, nem célszerű őket egymással felcserélhetőnek feltételezni A vector és a string két nagyon hasonló adatszerkezet. Az interface különbségein túl a legfontosabb szemantikai különbség a kettő között a másolásban rejlik: a vector copy konstruktora és értékadó operátora kötelezően a sablon paraméter értékadó operátorával másolja a konténer összes elemét, a string

viszont használhat referenciaszámlálást. Az STL-ben négy szabványos asszociatı́v sablon található: set, multiset, map, multimap. Az asszociatı́v konténerek rendezetten tárolják a bennük lévő elemeket, de a mögöttes valódi adatszerkezetet nem deﬁniálja a C++ szabványa. Jellemzően piros-fekete fákat használnak az STL implementációk A map és a multimap kulcs-érték párokat tartalmaz, a set és a multiset csak kulcsokat. A set-ben, map-ben nem lehet több ekvivalens 16 Alapok kulcs, egyedieknek kell lenniük. Ezzel szemben a multiset és a multimap támogatja az ekvivalens kulcsok multiplicitását. Az iterátorok garantálják az algoritmusok és a konténerek függetlenségét. Egy egységes interface segı́tségével deﬁniálják a memóriában elhelyezett elemek elérését. Ez az interface a pointer-aritmetikán alapul: mutatók (pointerek) segı́tségével tömbökön végig lehet

iterálni Az iterátorok a pointerek absztrakciójának tekinthetőek. A pointerek használhatóak iterátorként is, a tömbökön az STL algoritmusai meghı́vhatóak. A pointer-aritmetika alapvető műveletei: • preﬁx és postﬁx operator++: a következő elemre lépteti a pointert. • operator*: a pointer által mutatott elem lekérdezése • operator==: a két pointer ugyanarra az elemre hivatkozik-e • preﬁx és postﬁx operator--: a megelőző elemre lépteti a pointert, A pointerek segı́tségével a tömbben tetszőleges pozı́cióra lehet ugrani bárhonnan. Ez nem igaz az összes STL-ben deﬁniált iterátorra Az STL iterátorai különböző kategóriákba esnek a képességeik alapján [46]. A kategóriák egy hierarchiát alakı́tottak ki a különböző iterátorok között: Ezek a kategóriák nyelvi szemszögből nincsenek megkülönböztetve, a C++ sablonjai megszorı́tás nélküliek, a

C++ nyelv jelenleg nem tartalmaz concepteket. Azok az iterátorok teljesı́tik az input iterátorok elvárásait, amelyekkel egyszer végig lehet menni egy intervallumon és a benne lévő elemeket el lehet egyszer érni olvasásra. Ilyen iterátorokat használ például a for each algoritmus. Azok az iterátorok teljesı́tik az output iterátorok elvárásait, amelyekkel az elemek szekvenciálisan elérhetőek és ı́rhatóak. Ilyet vár például a copy Alapok 17 harmadik paramétereként. Az ostream iterator<T> sablon példányai tipikus output kategóriájú iterátorok Azok az iterátorok teljesı́tik a forward iterátorok elvárásait, amelyekkel szekvenciálisan végig lehet menni az intervallumon, és az iterátorok olvasni és ı́rni is tudják az elemeket. Mivel az input iterátorokkal szemben a forward iterátorokról másolatok készülhetnek az algoritmusok törzsében, azaz többször is hivatkozhatnak

már elért elemet, akár többször is bejárható egy intervallum. Mivel a max element algoritmus iterátort ad vissza az input intervallum legnagyobb értékére, forward kategóriájú iterátort vár. Ha csak az intervallum legnagyobb értéket adná vissza, akkor input iterátort várna. Azok a forward iterátorok teljesı́tik a kétirányú (bidirectional) iterátorok elvárásait, amelyek képesek nem csak a következő, hanem az előző elemet is elérni. Például a list konténer iterátorai bidirectional iterátorok Azok az iterátorok teljesı́tik a közvetlen vagy véletlen elérésű (randomaccess) iterátorok elvárásait, amelyek bidirectional iterátorok és képesek gyorsan (konstans időben) egynél több elemmel is növelni vagy csökkenteni a relatı́v cı́mzés megvalósı́tásához. Ezenkı́vül támogatniuk kell iterátorok öszszehasonlı́tását operator<, operator>=, stb

műveletekel Ilyen kategóriájú iterátort vár például a sort algoritmus és például a vector konténer iterátorai is random-access kategóriájúak. A konténerek belső tı́pusként négy fajta iterátor tı́pust garantálnak: • iterator • const iterator • reverse iterator • const reverse iterator A konténerek begin() és end() tagfüggvényeivel tudunk konténer iterátorokat létrehozni. A begin() létrehoz egy olyan iterátort, ami konténer első elemére mutat, az end() pedig egy olyat, ami a konténer extremális végére mutat. A reverse iterátorok létrehozásához a konténerek rbegin() és rend() tagfüggvényei használhatóak. A const iterator és a const reverse iterator nem engedi az iterátor objektumokon keresztül megváltoztatni a konténer hivatkozott értékét, azt csak olvasni tudja. A C++ konstans-biztonságának fontos összetevői ezek az iterátorok. A reverse iterátorok

(reverse iterator és const reverse iterator) az iterátorokhoz képest fordı́tott irányban haladnak, a konténer végétől indulnak és a konténer elejéig mennek. Kényelmesen használhatóak, amikor például egy elem utolsó előfordulását kell megkeresni a find algoritmussal. 18 Alapok A konténerek iterátorain kı́vül az STL még biztosı́t néhány iterátor sablont, amelyekkel a stream-eken (például ﬁle-okon, standard input-on vagy output-on) lehet iterálni: • istream iterator<T> • ostream iterator<T> • istreambuf iterator<T> • ostreambuf iterator<T> Az istream iterator<T> és az ostream iterator<T> iterátorokat formázott input/output-hoz tervezték, ezek a sablon paraméter tı́pusának kiı́ró (operator<<) és beolvasó (operator>>) operátorát hı́vják meg. Ezzel szemben, az istreambuf iterator<T> és ostreambuf iterator<T>

iterátorokat karakterenkénti input/output-hoz tervezték, kevésbé rugalmasak, de a karakteres input/output-ot gyorsabban dolgozzák fel [53]. Követve az eddigi analógiát, azt mondhatnánk, hogy a függvényeket algoritmusokká általánosı́tották, melyek a használt iterátorok tı́pusa alapján paraméterezhetőek [53]. Az algoritmusok konténer-független függvénysablonok gyakori feladatokra, mint például keresés (pl find, find if), stb), rendezés (pl partial sort, sort), másolás (pl copy, unique copy), számlálás (pl. count, count if) Az algoritmusok belül valamilyen ciklusra képződnek le, azaz algoritmusok olyan függvények absztrakciói, amelyekben ciklusok vannak [4]. Az STL-nek 60 szabványos algoritmusa van [92] Az algoritmusok konténer-függetlenek, de nem igaz az, hogy az összes algoritmus az összes konténerrel együttműködik, például a sort algoritmus random-access iterátorokat vár,

ı́gy ha csak kétirányú list iterátorokat adunk át, akkor fordı́tási hibát kapunk. Az STL egyik nem elhanyagolható tulajdonsága, hogy az egyes tagfüggvények és algoritmusok futási ideje az intervallum vagy konténer méretéhez viszonyı́tva aszimptotikusan rögzı́tett, amit minden implementációnak be kell tartania. Így például garantált, hogy a count algoritmus lineáris futási idejű, a set<Key>::count tagfüggvény pedig logaritmikus. Az STL egyik fontos komponense a funktor [5]. Funktorok segı́tségével felhasználói kódrészleteket lehet hatékonyan végrehajtani a könyvtáron belül: funktorok deﬁniálhatnak rendezéseket, predikátumokat, vagy valamilyen műveletet, amit végre szeretnénk hajtani az elemeken. Technikailag a funktorok egyszerű osztályok, amelyek rendelkeznek egy operator()-ral. (A funktorok ügyét nagymértékben segı́ti, hogy a paraméterek száma, a többi

operátorral szemben, nincs előre deﬁniálva az operator() Alapok 19 esetében.) Jellemzően két tipikus helyen haszálnak funktorokat az STL-ben: algoritmusok paramétereként és asszociatı́v konténerek rendezéséhez. Algoritmusok esetében a funktorokhoz bevezetnek egy extra sablon paramétert, és az algoritmus egy ilyen tı́pusú objektumot vár. Belül az algoritmus kódjában hivatkozik a paraméter operator()-ra: ez lehet egy függvénypointer dereferálása vagy a funktor operator()-a. Mivel ekkor a fordı́tóprogram paraméterdedukcióval levezeti a funktor tı́pusát, képes inline-osı́tani a felhasználói kódrészletet. A függvénypointer esetében nem optimalizálhat a fordı́tóprogram, mert futás idejű információként kezeli azt, hogy a pointer hova (melyik függvényre) mutat. A funktorok osztályok, ı́gy lehetnek adattagjai, amelyek a külön hivatkozások között információ

áramlást biztosı́thatnak, és lehetnek konstruktorai, amelyeken keresztül extra paraméterek adhatóak át. Az aszszociatı́v konténerek esetében, magának a konténernek van egy extra sablon paramétere, ami a rendezés funktor tı́pusát deﬁniálja. Az alábbi példa bemutatja a for each algoritmus implementációját, amely gyakran használ funktort: template <class InputIterator, class UnaryFunction> UnaryFunction for each( InputIterator first, InputIterator last, UnaryFunction f ) { while( first != last ) { f( *first++ ); } return f; } A funktorokat lehet osztályozni, megkülönböztetünk unáris és bináris funktorokat. Az unáris funktoroknak operator()-ának egy, a bináris funktoroknak operator()-ának két paramétere van Emellett megkülönböztetjük a predikátumokat, ezek olyan funktorok, amelyek operator()-a visszatérési érték tı́pusa bool vagy konvertálódik bool-lá. Adaptálható

(alkalmazkodóképes) funktorok a funktorok azon részcsoportja, amelyre a funktor adaptorok alkalmazhatóak. Kétféle szabványos funktor adaptor található az STL-ben: binder-ek és negálók [45]. A binderek (bind1st és bind2nd) egy bináris funktorból unárisat készı́tenek a funktor egyik paraméterének rögzı́tésével A negáló adaptor-ok (not1 és not2) egy bináris vagy unáris predikátumot negálnak. Ahhoz, hogy egy funktor adaptálható legyen biztosı́tania kell néhány typedef-et, ami alapján 20 Alapok az adaptor deﬁniálja annak az adaptált funktor operator()-ának viszszatérési érték és paraméter(ek) tı́pusát. A következő typedef-ekre van szükség egy unáris funktor adaptálásához: argument type, result type. Egy bináris funktor adaptálásához szükség van a first argument type, a second argument type és result type szinonı́mákra. Ezeket a legegyszerűbben úgy

lehet beállı́tani, ha a funktorunk a megfelelően példányosı́tott unary function vagy binary function sablonból származik [17] Példaképpen nézzük meg a következő kódrészletet: struct IsEven: std::unary function<int, bool> { bool operator()( const int& i ) const { return 0 == i % 2; } }; // . std::vector<int> v; // . std::vector<int>::iterator i = std::find if( v.begin(), v.end(), std::not1( IsEven() ) ); Az IsEven egy adaptálható funktor tı́pus, amely eldönti egy int értékről, hogy páros-e. A std::not1 az unáris funktort negálja, ı́gy a find if az első páratlan számot keresi a vector-ban. A szabványos könyvtárban már előre adott néhány funktor sablon, pl. a relációs műveleteken alapuló bináris funktorok: less, greater, stb., illetve néhány aritmetikai bináris műveleten alapuló sablon: például összeadás funktor sablonja a plus, a szorzásé a multiplies, stb. Az

STL átalakı́tói nem önálló komponensei a könyvtárnak, valamely komponenst alakı́tanak át egy eltérő funkcionalitás érdekében: léteznek konténer adaptorok, (tag)függvény adaptorok, funktor adaptorok, iterátor adaptorok. Az STL-ben három konténer adaptor létezik: queue, priority queue és stack. Ezek valamely paraméterezhető szekvenciális konténert alakı́tják át oly módon, hogy szűkı́tett lehetőséggel bı́rjon speciﬁkus adatszerkezetként. Az algoritmusok, amikor felhasználói kódrészletet hı́vnak egy globális függvényt hı́vnak meg: ez vagy egy globális függvényre mutató pointer vagy Alapok 21 egy funktor tı́pus operator()-a, de semmiképpen nem egy objektum tagfüggvényének a meghı́vása és nem egy pointeren keresztüli tagfüggvény meghı́vása. Ez utóbbi esetekben van szükségünk a tagfüggvény átalakı́tókra: mem fun és mem fun ref. Mindkettő

kap egy tagfüggvény pointert, amiből a szükséges paramétereket levezeti és létrehoz egy olyan funktort, amelyben egy megfelelő tı́pusú tagfüggvény pointer szerepel adattagként. Ennek az implementációs funktornak az operator()-a delegálja a hı́vást a tagfüggvény pointerhez. A mem fun ref felelős az objektumokon keresztüli tagfüggvény hı́vásért, a mem fun a pointereken keresztüli tagfüggvény hı́vásért. A ptr fun viselkedése is hasonló: egy globális függvényből készı́t olyan funktort, amely egy függvénypointeren keresztül hı́vja meg a felhasználói kódrészletet. A függvénnyel szemben a funktor alkalmazkodóképes, azaz alkalmazhatjuk a negálókat és binder-öket. Tehát, ha adott például egy predikátumfüggvényünk és negálni szeretnénk, akkor előtte ptr fun-nal funktorrá kell alakı́tanunk. A funktor adaptorokat a funktoroknál már bemutattam: két

predikátum negáló (not1 és not2) és két binder (bind1st és bind2nd) funktor adaptor található a szabványos STL-ben. Az STL iterátor adaptorainak az a céljuk, hogy iterátort szimuláljanak speciﬁkus céllal: konténerhez adjanak új elemeket. A konténerek iterátorai nem érik el azt a konténer objektumot, amelynek elemeire hivatkoznak, nem tudják meghı́vni a tagfüggvényeit, ı́gy nem tudnak elemeket hozzáadni az adatszerkezethez: csak meglévő elemeket érik el ı́rási vagy olvasási céllal. Ez másolási algoritmusoknál problémás lehet, ha több elemet másolunk, mint amennyi átı́rható elem szerepel az output-ban. Az STL iterátor adaptorai megkapják a konténert (tı́pussal együtt), ı́gy meghı́vhatóak azok a metódusai, amelyekkel új elemek vehetőek hozzá. A különféle beszúrásokhoz különböző adaptorok használhatóak: a back insert iterator a konténerek push back

metódusát hı́vja meg, a front insert iterator pedig a push front metódusát. Mivel például az asszociatı́v konténereknek ilyen tagfüggvényei nincsenek, ekkor a insert iterator képes az insert tagfüggvény hı́vását kikényszerı́teni az algoritmuson keresztül A későbbiekben használni fogjuk az iterator traits sablont. Anélkül ı́runk le bizonyos iterátorhoz kapcsolódó tı́pusokat, hogy magát az iterátorok kódját megváltoztatnánk, ezért ez egy nem-intrúzı́v technika. Ennek a sablonnak a specializációi különféle typedef-eket tartalmaznak, amelyekre szükség lehet az algoritmusok implementálásakor, például, hogy milyen tı́pusú objektumokra hivatkoznak (value type). Az általános implementációja (ezt lehet specializálni) a következőképpen néz ki: 22 template <class T> struct iterator traits { typedef typename T::iterator category typedef typename T::value type typedef

typename T::difference type typedef typename T::pointer typedef typename T::reference }; Alapok iterator category; value type; difference type; pointer; reference; A specializációk létrehozásához az iterator sablon bázisosztályt kell példányosı́tani. Az iterator traits sablon segı́tségével az algoritmusok túlterhelhetők az iterátor kategóriája alapján a tag dispatch-nek [96] nevezett technika segı́tségével. Ennek mintapéldája az advance algoritmus, amely a paraméterül kapott iterátort lépteti előre a paraméterül kapott értékkel. A túlterhelés miatt véletlen-elérésű iterátorok esetén a futás ideje konstans, egyébként lineáris. A túlterhelést úgy valósı́tják meg, hogy a szabványos deklarációra illeszkedő implementáció továbbhı́v eggyel több paraméterrel. Az extra paraméter egy default konstruált objektum, amelynek tı́pusa az iterátor kategóriáját

reprezentáló dummy tı́pus Ha ez std::random access iterator tag tı́pusú, akkor közvetlen elérésű iterátort kapott az algoritmus és ezt kihasználhatja az implementáció: template <class InputIterator, class Distance> void advance( InputIterator& i, Distance n ) { advance( i, n, typename std::iterator traits<InputIterator>::iterator category() ); } template <class InputIterator, class Distance> void advance( InputIterator& i, Distance n, std::random access iterator tag ) { i += n; } template <class InputIterator, class Distance> void advance( InputIterator& i, Alapok 23 Distance n, std::bidirectional iterator tag ) { for( Distance j = 0; j < n; ++j ) { ++i; } } Az allokátorokat eredetileg a memóriamodellek absztrakciójaként fejlesztették ki, hogy ne kelljen megkülönböztetni a near és a far pointereket bizonyos 16-bites operációs rendszerekben. Arra is tervezték az allokátorokat, hogy

elősegı́tse a memóriakezelők fejlesztését. A memóriaallokálás testreszabásához az összes szabványos STL konténer ad megoldást: az utolsó sablon paraméter az allokátor tı́pusát deﬁniálja. Van default értéke, de másik tı́pus is megadható helyette. Az operator new-hoz és az operator new[]-hoz hasonlóan az STL allokátorok felelősek a nyers memória allokációjáért (és deallokációjáért), de az allokátorok kliensei kevés hasonlóságot hordoznak az operator new-hoz, az operator new[]-hoz vagy akár a malloc-hoz viszonyı́tva. Végül (de talán a legjelentősebb), hogy a szabványos konténerek nagyrésze sosem kér memóriát az allokátorától. Ennek az az oka, hogy láncolt adatszerkezetek (pl list vagy az asszociatı́v adatszerkezetek nem a konténer value type typedef-je alapján kell memóriát allokálniuk, hanem egy belső implementációs struktúra elemeinek (pl. List

node) [53] Saját allokátorokat olyan helyzetben érdemes ı́rni, ha a default allokátor szál-biztos (thread-safe) és nincs erre szükség, vagy speciális heap memóriát szeretnénk használni, ahol a konténer elemei egymáshoz közel helyezkednek el. Több folyamat által használt osztott memória használatakor is érdemes lehet saját allokátort ı́rni. Az új C++ szabvány (C++11) magát az STL-t is bővı́tette. Ezek a bővı́tmények nem oldják meg a dolgozatban szereplő problémákat A C++11 által biztosı́tott STL új lehetőségeit később ismertetem az A függelékben. Az STL-t szekvenciális környezetre tervezték, ezért használata a szűk keresztmetszete lehet a multicore (többmagos) fejlesztéseknek. Részt vettem egy multicore környezetre optimalizált STL fejlesztésében is [105, 106, 107, 108]. Eközben végtelen intervallumok iterátorainak támogatását is megvalósı́tottuk [51]

24 II.4 Alapok Motivációs példák Ebben a fejezetben bemutatom azokat a nehézségeket, amelyekkel a programozóknak szembe kell nézniük az STL használatakor. Ismertetem azokat a problémákat, amelyeket az STL hibás használata okozhat. Ezek a hibák okozhatnak nehezen értelmezhető fordı́tási hibaüzeneteket, nem portábilis kódot, hibás futási eredményeket, memória szivárgást, korrupttá vagy inkonzisztenssé váló adatszerkezeteket illetve szükségtelen hatékonyságromlást. A most felsorolt problémák egy részére dolgozatom megoldást kı́nál, más problémák további kutatások tárgyai. II.41 Fordı́tási hibaüzenetek Az egyik leggyakoribb kritika ami az STL-t éri, az a fordı́tási hibaüzenetek érthetetlensége. A hosszú fordı́tási hibaüzenetek az STL implementációjára hivakoznak és nehéz kiderı́teni a probléma valódi okát. Ennek gyakori oka, hogy a C++

sablonok esetében nincs nyelvi eszköz a sablon paraméterekkel kapcsolatos elvárások leı́rására. Vegyük például az alábbi kódrészletet: std::list<int> a; std::sort( a.begin(), aend() ); A kód látszólag rendben van, a sort (konténer-független) algoritmussal rendezni próbálunk egy lista adatszerkezetet. Mégis az alábbi hibaüzenetet kapjuk a fordı́tóprogramtól: /usr/include/c++/4.3/bits/stl algoh: In function ’void std::sort( RAIter, RAIter) [with RAIter = std:: List iterator<int>]’: listsort.cpp:7: instantiated from here /usr/include/c++/4.3/bits/stl algoh:4783: error: no match for ’operator-’ in ’ last - first’ /usr/include/c++/4.3/bits/stl algoh: In function ’void std:: final insertion sort( RandomAccessIterator, RandomAccessIterator) [with RandomAccessIterator = std:: List iterator<int>]’: /usr/include/c++/4.3/bits/stl algoh:4785: instantiated from ’void std::sort( RAIter, RAIter) [with

RAIter = std:: List iterator<int>]’ listsort.cpp:7: instantiated from here Alapok 25 /usr/include/c++/4.3/bits/stl algoh:1827: error: no match for ’operator-’ in ’ last - first’ /usr/include/c++/4.3/bits/stl algoh:1829: error: no match for ’operator+’ in ’ first + 16’ /usr/include/c++/4.3/bits/stl algoh:1830: error: no match for ’operator+’ in ’ first + 16’ /usr/include/c++/4.3/bits/stl algoh: In function ’void std:: insertion sort( RandomAccessIterator, RandomAccessIterator) [with RandomAccessIterator = std:: List iterator<int>]’: /usr/include/c++/4.3/bits/stl algoh:1833: instantiated from ’void std:: final insertion sort( RandomAccessIterator, RandomAccessIterator) [with RandomAccessIterator = std:: List iterator<int>]’ /usr/include/c++/4.3/bits/stl algoh:4785: instantiated from ’void std::sort( RAIter, RAIter) [with RAIter = std:: List iterator<int>]’ listsort.cpp:7: instantiated from here

/usr/include/c++/4.3/bits/stl algoh:1753: error: no match for ’operator+’ in ’ first + 1’ /usr/include/c++/4.3/bits/stl algoh:1833: instantiated from ’void std:: final insertion sort( RandomAccessIterator, RandomAccessIterator) [with RandomAccessIterator = std:: List iterator<int>]’ /usr/include/c++/4.3/bits/stl algoh:4785: instantiated from ’void std::sort( RAIter, RAIter) [with RAIter = std:: List iterator<int>]’ listsort.cpp:7: instantiated from here /usr/include/c++/4.3/bits/stl algoh:1759: error: no match for ’operator+’ in ’ i + 1’ A hiba valódi oka az, hogy a sort algoritmus random-access kategóriájú iterátorokat vár, de a list konténernek csak bidirectional iterátorai vannak. A sort implementációjában azok a műveletek, amelyek kihasználják a közvetlen elérést fordı́tási hibákat okoznak, hiszen ilyen műveleteket a list bejárói nem támogatnak. Sajnos a hibaüzenet nem fejezi ki elég

világosan, hogy a sort algoritmus nem használható a list konténerrel. Az ilyen jellegű problémákra olyan metaprogram könyvtárak adnak megoldást, amelyek fordı́tási időben már korábban ellenőrzik, hogy a sablon paraméter megfelele az elvárásoknak [118]. Ezek a könyvtárak azonban közel sem teljesek és implementáció-függőek. A kutatók a mai napig dolgoznak a concept-eken, 26 Alapok melyek nyelvi szintű konstrukcióként támogatják a sablonok tı́pus paramétereinek ellenőrzését [103]. Ugyanennek a jelenségnek egy másik oka is van: a fordı́tóprogramok a hibaüzenetekben nem mindig arra az azonosı́tóra (vagy nem ugyanabban a formátumban) hivatkoznak, mint ami a forráskódban szerepel. A string-ek kezeléséhez az std::string tı́pus használják a programozók Maga az std::string nem önálló tı́pus, hanem egy typedef Az std::string egy szinonı́mája a std::basic string<char,

char traits<char>, allocator<char> > tı́pusnak. A hibaüzenetekben viszont ez utóbbi tı́pusra hivatkozik a fordı́tóprogram, akkor is, ha a programozó az std::string-ként használja. A fenti hibaüzenetben ilyen a List iterator<int> implementáció-speciﬁkus azonosı́tó is, ami az std::list<int>::iterator szabványos tı́pus álneve. Az asszociatı́v konténerek alatt lévő adatszerkezetet nem deﬁniálja a C++ szabványa. A leggyakrabban piros-fekete fák [12] segı́tségével implementálják az asszociatı́v adatszerkezeteket. Egy implementációtól függő segéd sablon tı́pusban (pl. Rb tree vagy Tree) megvalósı́tják az adatszerkezetet, a szabványos konténerek pedig ezeket a segédtı́pusokat használják Vegyük most az alábbi hibás kódrészletet: std::set<std::string> a; a.insert( a ); A g++ fordı́tóprogram az alábbi hibaüzenetet adja az előző kódrészletre:

seterr.cpp:11: error: no matching function for call to ’std::set<std::basic string<char, std::char traits<char>, std::allocator<char> >, std::less<std::basic string<char, std::char traits<char>, std::allocator<char> > >, std::allocator<std::basic string<char, std::char traits<char>, std::allocator<char> > > >::insert( std::set<std::basic string<char, std::char traits<char>, std::allocator<char> >, std::less<std::basic string<char, std::char traits<char>, std::allocator<char> > >, std::allocator<std::basic string<char, std::char traits<char>, std::allocator<char> > > >&)’ /usr/include/c++/4.3/bits/stl seth:378: note: candidates are: std::pair<typename std:: Rb tree< Key, Key, std:: Identity< Key>, Compare, typename Alloc::rebind< Key>::other>::const iterator, bool> std::set< Key, Compare,

Alloc>::insert(const Key&) [with Key = std::basic string<char, std::char traits<char>, std::allocator<char> >, Compare = std::less<std::basic string<char, Alapok 27 std::char traits<char>, std::allocator<char> > >, Alloc = std::allocator<std::basic string<char, std::char traits<char>, std::allocator<char> > >] /usr/include/c++/4.3/bits/stl seth:405: note: typename std:: Rb tree< Key, Key, std:: Identity< Key>, Compare, typename Alloc::rebind< Key>::other>::const iterator std::set< Key, Compare, Alloc>::insert(typename std:: Rb tree< Key, Key, std:: Identity< Key>, Compare, typename Alloc::rebind< Key>::other>::const iterator, const Key&) [with Key = std::basic string<char, std::char traits<char>, std::allocator<char> >, Compare = std::less<std::basic string<char, std::char traits<char>, std::allocator<char> >

>, Alloc = std::allocator<std::basic string<char, std::char traits<char>, std::allocator<char> > >] Látható, hogy a hibaüzenetben olyan tı́pusok is megjelennek nagy menynyiségben, melyek a forráskódban sehol sem láthatóak: például konténer default sablonparaméterei és egyéb implementációs segédtı́pusok. Világos, hogy ezek a hibaüzenetek megértése nagy gyakorlatot kı́ván. Létezik platform speciﬁkus eszköz a hibaüzenetek megértéséhez [117], de nincsen általánosan használható kényelmes eszköz erre a problémára. II.42 Invalid iterátorok Az iterátorok központi elemei az STL-nek: összekötik az algoritmusokat a konténerekkel, és a konténerek bejárását biztosı́tják. Sajnos azonban az iterátor objektumok élettartama nem feltétlenül esik egybe a hivatkozott objektum élettartalmával. Előfordulhat, hogy egy iterátor olyan objektumra hivatkozik,

ami már nincs a memóriában vagy máshova került. A vector konténer sablon tipikus implementációja olyan, hogy lefoglal egy egybefüggő tárterületet valamekkora kapacitással. Ha betelik ez a kapacitás, akkor lefoglal egy nagyobb (jellemzően kétszer akkora) egybefüggő tárterületet, az elemeket átmásolja a régi tárterületről az újra, és a régi tárterületet felszabadı́tja a konténer. Nem garantált, hogy ezt a konténerhez tartozó iterátorok észreveszik. Több STL implementációnál az iterátorok továbbra is régi tárterületre hivatkoznak, és ha hivatkozunk ezekre az iterátorokra, akkor az nemdeﬁniált eredményhez vezet. Vegyük például az alábbi kódrészletet: std::vector<int> v; int x; // . 28 Alapok std::vector<int>::iterator i = v.begin(); v.push back( x ); std::cout << *i; A vector a push back hatására reallokálhat, ha betelt a kapacitása. Ilyenkor

az i iterátor objektum invaliddá válhat. A vector konténer publikus interface-én azonban lekérdezhető, hogy mikor reallokál: std::vector<int> v; int x; // . std::vector<int>::iterator i = v.begin(); if ( v.size() < vcapacity() ) { v.push back( x ); } std::cout << *i; Ebben az esetben garantált, hogy i nem vált invaliddá. Sajnos, nem egységes, hogy az iterátorok mikor invalidálódnak az STL-es konténekben, és nem is mindig adnak erre választ a konténerek publikus interface-ei. A deque esetében a következőt állı́tja a szabvány: beszúráskor fel kell tenni, hogy az iterátorok érvénytelenné váltak, a deque közepéből történő törléskor fel kell tenni, hogy az iterátorok érvénytelenné válnak, viszont valamely széléről törlés csak a törölt iterátort érvénytelenı́ti, ráadásul a deque iterátorai invaliddá válhatnak anélkül, hogy az elemeire hivatkozó

pointerek és referenciák is invalidálódnának. Az iterátor invalidálásnak egy jellegzetes esete az alábbi kódrészlet is: std::list<int> li; // . for( std::list<int>::iterator i = li.begin(); i != li.end(); ++i ) { if ( *i == 0 ) { li.erase( i ); } } Alapok 29 Ha törlünk egy elemet a konténerből egy iterátoron keresztül, akkor az iterátor invaliddá vált, ı́gy nem garantált, hogy meg tudja adni, hogy hol a következő elem a konténerben. Egy láncolt adatszerkezetnél, törlés végén felszabadul a listaelem, ı́gy az iterátor olyan helyre hivatkozik, ahol már nincs nincsen meg a listaelem, ezért nem is deﬁniálhatja, hogy hol van a memóriában a következő elem. Jellemző, hogy az algoritmusok alkalmazásával az invalid iterátorok könnyebben elkerülhetőek Kidolgoztam egy technikát, amellyel futási időben ellenőrizhető, hogy az iterátorok validak-e, és ha nem akkor kivétel

kiváltásával jelzi, hogy az iterátor nem használható (V.2) II.43 Funktorokkal kapcsolatos hibák Az STL-ben a funktorok a legalapvetőbb eszközök, amelyekkel hatékonyan lehet felhasználói kódrészleteket a könyvtáron belül végrehajtani. Rendkı́vül egyszerű osztályoknak tűnnek, mégis nagyon sok különböző dologra kell odaﬁgyelni, amikor magunk ı́runk új funktortı́pusokat. Most bemutatom a funktorokkal kapcsolatos leggyakoribb hibákat. Az STL-ben több helyen paraméterezhető a rendezés: az asszociatı́v konténereknél és az olyan algoritmusoknál, amelyek rendeznek (pl. sort vagy rendezett intervallumban keresenek (pl. binary search) Az asszociatı́v konténereknél sablonparaméterként egy funktortı́pus deﬁniálja a kulcs tı́puson értelmezett rendezést. Ennek van default paramétere, ami életbe lép, ha a felhasználó nem ad meg másikat. A set deklarációja például a

következőképpen néz ki: template <class Key, class Compare = std::less<Key>, class Allocator = std::allocator<Key> > class set; Azok az algoritmusok, amelyek rendezést használnak, túl vannak terhelve: van egy rendezés paraméter nélküli verzió, amely a szokásos növekvő sorrendet használja és van egy olyan verzió, amely vár egy rendezési paramétert. Például a sort algoritmus deklarációi a következőképpen néznek ki: template <class RandomAccessIterator> void sort( RandomAccessIterator first, RandomAccessIterator last ); template <class RandomAccessIterator, class Compare> 30 Alapok void sort( RandomAccessIterator first, RandomAccessIterator last, Compare compare ); Az STL rendezéseknél szigorú részbenrendezést (strict weak ordering) igényel, de ezt a tulajdonságot nem ellenőrzi a fordı́tóprogram, és futás közben sem jelzi a hibát a könyvtár. Egy ilyen szempontból

hibásan megı́rt funktor tı́pus hatása elég szokatlan. Az STL kódjában gyakran történik meg az, hogy két objektumot hasonlı́t össze a könyvtár. Az STL-nek két különböző módja van, hogy eldöntse a két objektumról, hogy megegyeznek-e: az egyenlőség és az ekvivalencia [53]. Az egyenlőség fogalma az operator==-n alapszik. Ezt használja például a find vagy a count algoritmus. Az ekvivalencia fogalma inkább a rendezésekhez kapcsolódik Két objektum ekvivalens, akkor és csak akkor, ha a rendezés szerint egyik sem előzi meg a másikat, azaz a és b ekvivalens: !keycomp()( a, b ) && !keycomp()( b, a ) Az asszociatı́v adatszerkezetekben az ekvivalenciát ellenőrzik, amikor el kell eldönteni, hogy két objektum megegyezik-e, mivel azok rendezetten tárolják az elemeket [97]. A funktor tı́pusát nem vizsgálja meg a fordı́tóprogram, hogy teljesı́ti-e a szigorú részbenrendezés

feltételét. Futás közben sem jelzik ezt a problémát a különböző implementációk. Vizsgáljuk meg, mi történik, ha hibás funktort ı́r a könyvtár felhasználója: struct Compare : std::binary function<int, int, bool> { bool operator()( int i, int j ) const { return !(i < j); } }; struct StringLengthLess : std::binary function<std::string, std::string, bool> { bool operator()( const std::string& a, const std::string& b ) const { return a.length() <= blength(); } }; Alapok 31 Mindkét fenti funktor tı́pust le tudja fordı́tani a C++ fordı́tóprogram, sőt használatukkor sem jelzi a rendszer, hogy hibás lenne. Mivel azonban az irreﬂexivitás nem teljesül, az asszociatı́v konténerek inkonzisztenssé válnak: std::set<int, Compare> sc; sc.insert( 3 ); sc.insert( 3 ); // sc.size() == 2 // sc.count( 3 ) == 0 std::multiset<int, Compare> mc; mc.insert( 7 ); // mc.count( 7 ) == 0 Az sc objektum

nem viselkedik set-ként, a tagfüggvények nem találják az eltárolt elemeket, stb. A problémát a hibásan megı́rt funktor okozza: az asszociatı́v konténerek tagfüggvényei az ekvivalenciát vizsgálják ezekben az esetekben. Vizsgáljuk meg például a insert-et: sc.insert( 3 ); sc.insert( 3 ); Az insert második hı́vása kiértékeli a következő kifejezést, hogy ellenőrizze, hogy a 3-as érték benne van-e már a konténerben: !( 3 <= 3 ) && !( 3 <= 3 ) Ennek a kifejezésnek hamis az értéke, amit úgy lehet interpretálni, hogy a ,,3 nem ekvivalens a 3-mal” a rendezés szerint. Emiatt van, hogy a count, stb. tagfüggvények hibás eredményt adnak vissza Nehéz a hiba okát megtalálni ilyen esetben, mert a programozók nem gyanı́tják, hogy például egy set-be kétszer is berakhatnak egyenlő értékeket. A legtöbb programozó azt sem gyanı́tja, hogy azok a jól ismert tagfüggvények,

amelyek kihasználják az ekvivalenciát szintén hibás adatokat ad vissza, ha a predikátum a hibás. Ezért kidolgoztam egy technikát, amelynek segı́tségével a funktorok automatikusan ellenőrzésre kerülnek, ha egy másik ősosztályból is leszármaznak [66]. Az ellenőrzés futási időben történik, és kivételt vált ki, ha a funktor megsérti a szigorú részbenrendezési elvárást (V.6) Az alkalmazkodóképes funktorok alapproblémája, hogy az átalakı́tott (negált vagy lekötött változóval ellátott) funktor operator() visszatérési értékének és paramétereinek tı́pusait nem az eredeti operator() deﬁniálja, hanem ettől függetlenül megadható typedef-ek deﬁniálják, amiket jellemzően 32 Alapok speciális bázistı́puson keresztül állı́t be a felhasználó, hogy ne kelljen ismernie ezeket a typedef-eket. Ez kódduplikátumot okoz, ami karbantartási vagy egyéb

okokból inkonzisztenssé válhat. Vizsgáljuk meg az alábbi funktort [63]: struct AnotherBadPredicate: std::unary function<int, bool> { AnotherBadPredicate( const double& d ): x( d ) {} bool operator()( const double& a ) const { return a < x; } private: double x; }; Ez a predikátumtı́pus teljesen jól használható, ha nem adaptáljuk. Viszont, ha a predikátum negáltja szerint próbálunk keresni, hibás eredményt kaphatunk: std::vector<double> v; v.push back( 25 ); v.push back( 83 ); std::vector<double>::iterator i = std::find if( v.begin(), v.end(), std::not1( AnotherBadPredicate( 2.3 ) ); if ( i != v.end() ) { std::cout << *i << std::endl; } Ez a kódrészlet azt mutatja, hogy a vector-ban a 8.3 érték az első, amely nem kisebb, mint 2.3 Ez hibás eredmény, hiszen a 25 az első olyan érték, amely nem kisebb, mint 2.3 Azért kapunk hibás eredményt, mert a negált funktor nem lebegőpontos (double),

hanem egész számokkal (int) dolgozik, és ekkor a 2.3 nem kisebb, mint 25 Azért dolgozik a negált funktor int-ekkel, mert a funktor a std::unary function<int, bool> tı́pusból Alapok 33 származik. Erre a hibalehetőségre olyan megoldást adok, amely fordı́tási időben ﬁgyelmeztetést ad, ha a funktor bázis tı́pusa és visszatérési érték és paraméterek tı́pusa nem felelnek meg egymásnak. Viszont a fenti kód is alátámasztja azt, hogy a funktor operator() paramétereinek tı́pusa nem teljesen egyezik meg a bázis tı́pusnál megadottal: referenciáknál és const referenciáknál mind a referencia, mind a const eltűnik. Pointereknél viszont nem szabad a pointerséget eliminálni. Az adaptálható funktorok bázistı́pusát fordı́tási időben ellenőrzöm, és a fordı́tóprogram ﬁgyelmeztetést vált ki, ha nem felel meg az operator() paramétereinek (IV.4) A korábbi példák alapján

látható, hogy az algoritmusok a funktorokat érték szerint veszik át, azaz a funktor a copy konstruktora meghı́vásával adódik át. Ez általános szabály az STL-ben, ami C-s reverse kompatibilitás miatt van: a C szabványkönyvtárában a függvénypointerek mindig másolódnak [53]. Így le kell mondanunk a funktorok polimorf viselkedéséről és ﬁgyelni kell a másolás költségére A polimorf funktorok megı́rását semmi nem gátolja meg, de a fordı́tóprogram nem tudja levezetni a funktor dinamikus tı́pusát, hiszen az futási idejű információ [92]. Így szeletelődéshez (slicing) vezet a polimorﬁkus funktorok alkalmazása és nem az a funktor hı́vódik meg, amit a felhasználó elképzelt. Azoknál a funktoroknál, amelyek predikátumok, van még egy indok, hogy a funktorok helyesen viselkedjenek másoláskor. Az algoritmusok készı́thetnek másolatokat a funktorokról és tárolhatják egy

ideig használat előtt. Néhány algoritmus implementációja kihasználja ezt a szabadságot. Ennek az észrevételnek a kritikus következménye az, hogy a predikátumoknak tiszta függvényeknek kell lenniük, azaz az eredménye csak a paramétereitől függhet Vizsgáljuk meg az alábbi funktort, amely megsérti ezt a szabályt: struct BadPredicate: std::unary function<Widget, bool> { BadPredicate(): timesCalled( 0 ) { } bool operator()( const Widget& ) { return ++timesCalled==3; } private: size t timesCalled; }; Tegyük fel, hogy van konténerünk, ami Widget-eket tárol, és a funktor segı́tségével szeretnénk eltávolı́tani a harmadik elemét: 34 Alapok vector<Widget> vw; // . vw.erase( std::remove if( vwbegin(), vw.end(), BadPredicate() ), vw.end() ); Ez a kód elég logikusnak tűnik, de néhány STL implementációval nem csak a harmadik elemet távolı́tja el, hanem a hatodikat is! Ennek magyarázata a

remove if implementációban rejlik. Egy lehetséges megvalósı́tása az algoritmusnak a például következő: template <typename FwdIterator, typename Predicate> FwdIterator remove if( FwdIterator first, FwdIterator last, Predicate p ) { first = find if( first, last, p ); if ( first == last ) return begin; else { FwdIterator next = first; return remove copy if( ++next, last, first, p ); } } A furcsa viselkedésnek az az oka, hogy a p predikátumot először átadjuk a find if-nek, majd később a remove copy if-nek. Természetesen mindkét esetben p érték szerint adódik át – másolódik – az algoritmusokba. A remove if meghı́vása (egyetlen hı́vása van a kliens kódban, ami el szeretné távolı́tani a harmadik elemet a vw-ből) létrehoz egy névtelen BadPredicate objektumot, ez 0-val inicializálja a timesCalled-ot. Ezt az objektumot (ami p névvel rendelkezik a remove if-en belül) lemásolja find if-be, tehát a find

if-nek is lesz egy BadPredicate objektuma, ahol a timesCalled 0. A find if addig ,,hı́vja” meg az objektumot, amı́g igazzal nem tér vissza, tehát háromszor. Ezután visszaadja a vezérlést a remove ifnek Ez folytatja a végrehajtást és végül meghı́vja a remove copy if-et, aminek p-ről egy másik másolatot ad át predikátumként. De a p-nek a timesCalled tagja még mindig 0! A find if soha nem hı́vta meg a p-t, csak p egy másolatát! Ennek eredményeképpen, amikor a remove copy if Alapok 35 harmadszor hı́vja meg a predikátumot, az igazzal fog visszatérni. Emiatt van az, hogy remove if végül is két elemet fog törölni a vw-ből egy helyett. A legegyszerűbb megoldás, hogy elkerüljük ezt a hibát, ha a funktor operator()-át const-nak deklaráljuk. Ha ı́gy teszünk, akkor a fordı́tó nem fogja engedni, hogy módosı́tsuk az osztály adattagjait. Ez azonban sajnos nem elég: ettől még a funktor

elérhet pl. globális változókat, amelyek miatt a funktor operator()-a nem lesz tiszta Ehhez célszerű lenne egy olyan tagfüggvény módosı́tót megadni, amivel ez a tulajdonság deﬁniálható és ellenőrizhető lenne, és csak ilyen tı́pusú funktorokat fogadna el az STL. II.44 Allokátorokkal kapcsolatos hibák A memóriaallokálás testreszabásához az összes szabványos STL konténer ad lehetőséget: mindegyiknek van egy allokátor sablon paramétere. Ennek van default értéke, ami, ha nem felel meg az elvárásoknak, akkor deﬁniálható másik tı́pussal is. Az allokátorok objektumok és ez azt jelenti, hogy lehetnek tagfüggvényeik, adattagjaik, beágyazott tı́pusaik és typedef-jeik stb., de a C++ Szabvány azt mondja, hogy az STL implementációk feltehetik, hogy az összes azonos tı́pusú allokátor objektum ekvivalens, és mindig egyenlőek. Ennek oka az alábbi kódban keresendő: template

<typename T> class CustomAllocator {.}; typedef CustomAllocator<Widget> WidgetAlloc; list<Widget, WidgetAlloc> L1; list<Widget, WidgetAlloc> L2; // . L1.splice( L1begin(), L2 ); Amikor a splice-szal listaelemeket hozzáadunk egy másikhoz, akkor nem történik másolás, hanem csak néhány pointert állı́t be és azok az elemek, amelyek az egyik listában voltak, a másikban találják magukat. Ez teszi a splice műveletet gyorssá és kivétel-biztossá. Az előző példában, azok az elemek, amelyek L2-ben voltak a splice meghı́vása előtt, a függvényhı́vás után az L1-ben lesznek. 36 Alapok Amikor L1 megszűnik természetesen meg kell szüntetnie az összes elemét (és deallokálnia kell a memóriáját) és mivel most azokat az elemeket, amelyek eredetileg L2-ben voltak és L2 allokátora hozta létre, L1 allokátorának kell megszüntetnie. Ez az oka annak, hogy a szabvány miért engedi a

fejlesztőknek, hogy feltegyék, hogy azonos tı́pusú allokátor objektumok ekvivalensek Így az egyik allokátor objektummal (mint az L2-é) allokált objektumok biztonságosan felszabadı́thatóak egy második allokátor objektummal (mint az L1-é). Ha nem lehetne élni ezzel a feltétellel, akkor bonyolultabb lenne implementálni a splice-jellegű műveleteket. Biztosan nem lenne anynyira hatékony, mint ı́gy Ennek az a következménye, hogy az allokátornak nem lehet állapota (illetve nem használhatja ki az allokációnál és a deallokációnál), azaz stateless tı́pusnak kell lennie. Ha ezt megsértjük, akkor a fordı́tóprogram nem ad hibajelzést, az STL implementáció pedig kihasználja a szabvány lehetőségeit, tönkretéve ı́gy az adatszerkezetet. Ezért egy olyan megoldást dolgoztam ki, ami fordı́tási időben képes észrevenni, ha megsértjük ezt a szabályt (IV.5) Az új C++11 szabvány

jelentősen megváltoztatta a konténerek és az allokátorok kapcsolatát, bevezette az allocator traits sablont, amelynek segı́tségével már engedélyezetté váltak az állapottal rendelkező allokátorok [42]. A meglévő legacy kódok miatt az ellenőrzés továbbra is hasznos marad II.45 Másoló algoritmusokkal kapcsolatos hibák Az STL algoritmusai között van egy olyan csoport, amelyek elemeket, objektumokat másolnak egy output iterátor által meghatározott helyre, pl. copy, transform, unique copy, reverse copy if, stb. Ezek az algoritmusok konténer-függetlenek, ı́gy nem ismerik, hogyan tudnak az output-hoz új elemeket hozzáadni. Felteszik és kihasználják, hogy az output-on van elegendő terület, ahova másolhatják az elemeket. Az alábbi példában egy vector elemeit másoljuk egy listába, amelynek mérete akkora, mint amenynyi eleme van a vector-nak és ı́gy az ott lévő elemeket felül tudja

ı́rni a copy: std::vector<int> data; // . std::list<int> datacopy( data.size() ); std::copy( data.begin(), dataend(), datacopybegin() ); A copy algoritmus egy lehetséges implementációja a következő kódrészlet: template <class InputIterator, class OutputIterator> Alapok 37 OutputIterator copy( InputIterator first, InputIterator last, OutputIterator res ) { while( first != last ) { *res++ = first++; } return res; } Látható, hogy semmilyen speciﬁkus eltároló metódust nem hı́v a copy. Ha mégis szeretnénk egy konténerhez elemeket hozzáadni, iterátor adaptorokat használhatunk: std::vector<int> data; // . std::list<int> datacopy; std::copy( data.begin(), data.end(), std::back inserter( datacopy ) ); Ekkor a back inserter egy sablon, amely paraméterdedukcióval levezeti az output konténer tı́pusát, és ezzel példányosı́tja a back insert iterator sablont. A back insert iterator sablon értékadó

operátora kikényszerı́ti a konténer push back tagfüggvényének a hı́vását. Ha az output konténer nem üres, akkor az elemei megmaradnak és a copy input intervallumát az output végére beszúrja. Létezik front inserter is, amely egy front insert iterator tı́pusú iterátort hoz létre és a konténer push front metódusát hı́vja meg. Az inserter insert iterator-t hoz létre, amivel a konténerek insert tagfüggvényét lehet meghı́vni. Sajnos azonban lefordul az a kód is, amikor adapter nélkül egy üres konténerre hivatkozó iterátort adunk át valamely másoló algoritmusnak. Általában hibához vezet, ha nagyobb az input elemszáma, mint azt output mérete és semelyik előzőekben bemutatott adaptort nem használjuk [36]: std::vector<int> data; // . std::list<int> datacopy; std::copy( data.begin(), data.end(), datacopy.begin() ); 38 Alapok Ebben az esetben semmi nem kényszerı́ti ki, hogy

a list konténer létrehozzon új listaelemeket, ı́gy olyan tárterületre próbál ı́rni a copy, ami nincsen allokálva. A problémát nem oldaná meg, ha a list konténer helyett például vector-t használnánk: a vector lehet, hogy lefoglalna egy nagyobb egybefüggő tárterületet, ahova a copy tudna ı́rni, de a konténer nem venné észre, hogy új eleme van és például a vector mérete ( size() metódus által visszaadott érték) nem változna meg a copy hatására. Az én megoldásom fordı́tási ﬁgyelmeztetéseket generál, ha a fordı́tási ismeretek alapján nem garantálható, hogy az STL valamely másoló algoritmusa hiba nélkül végrehajtható (IV.32) Ezenkı́vül kidolgoztam olyan másolás-biztonságos iterátorokat is, amelyek másolás közben ellenőrzik, hogy van-e még szabad hely, és ha nincs, akkor meghı́vják a konténer megfelelő tagfüggvényét (V.3) II.46 Törlő

algoritmusokkal kapcsolatos hibák Az algoritmusok konténer-függetlenek komponensek az STL-ben. Nem ismerik, hogy milyen konténerrel dolgoznak, nem tudják, hogy milyen metódusai vannak, és azt sem, hogyan kell kitörölni belőlük egy-egy elemet. Az algoritmusok szemszögéből a konténerek műveletei nem elérhetőek Éppen ezért nem meglepő, hogy a törlő algoritmusok (pl. remove, remove if, unique) – a nevükkel ellentétben – nem törölnek elemet: vector<int> v; v.reserve( 10 ); for ( int i = 1 ; i <= 10; ++i ) { v.push back( i ); } cout << v.size(); // 10-et ı́r ki // 3 elemet 99-re változtatunk: v[3] = v[5] = v[9] = 99; remove( v.begin(), vend(), 99 ); cout << v.size(); // még mindig 10! Mivel a remove algoritmus nem tud elemet eltávolı́tani a konténerből, ezért az a viselkedése, hogy a konténer elejére másolja azokat az elemeket, Alapok 39 amelyek a törlés után megmaradnak. Az

ezutáni elemek általában megegyeznek az eredeti állapottal Ezt hatékonysági okokból teszi a remove, nem akar olyan elemekre másikat másolni, amit feltehetően törölni fog a felhasználó. Ha erre lenne szükség, akkor a partition algoritmus ad helyes megoldást. A remove visszaad egy iterátort, ami az ,,új, logikai vége” a konténernek Ha ténylegesen el szeretnénk távolı́tani az elemeket a konténerből, akkor ettől az iterátortól a konténer végéig lévő intervallum kitörölhető a konténer tagfüggvényével. Ezen probléma elkerüléséhez kidolgoztam olyan iterátorokat, amelyek képesek tényleges kitörölni a konténer elemeit és közben nem is invalidálódnak (V.4) A remove if algoritmus a remove-hoz hasonlóan nem tárolja el a konténer végére a törlendő elemeket. Ha speciálisan a heap-en allokált objektumokra mutató pointereket tárol a konténer, akkor könnyen

memória szivárgást okozhat a remove if, mert az algoritmus felszabadı́tás előtt felülı́rhat olyan pointereket, amelyek nem megmaradó objektumokra mutatnak. Az ilyen tı́pusú hibákat valgrind-jellegű alkalmazások tudják felderı́teni [58]. II.47 A unique algoritmus A unique és unique copy algoritmusok előzőekben bemutatott problémák speciális eseteként is felfogható. A unique algoritmus célja, hogy az inputból kiszűrjük a duplikátumokat, de a unique algoritmus viselkedése elsőre megtévesztő lehet: csak az egymásután csoportosı́tott duplikátumokból hagy meg egyet. A remove algoritmushoz hasonlóan képtelen elemeket eltávolı́tani az input konténerből Ugyanúgy, mint a remove, a unique is a konténer elejére másolja a megtartandó elemeket, és visszaad egy iterátort az új, logikai végére. Célszerűnek tűnik a unique algoritmus meghı́vása előtt rendezni a konténert, mert az

garantálja, hogy a duplikátumok egymás mellé kerüljenek. Ugyanakkor a unique algoritmusnak akkor is deﬁniált az eredménye, ha az elemek rendezetlenül szerepelnek a konténerben, nem okoz nemdeﬁniált eredményt, legfeljebb nem erre az eredményre számı́t a könyvtár felhasználója. A problémát bonyolı́tja, hogy helyes eredményt kaphatunk akkor is, ha a duplikátumok egymás mellett vannak, függetlenül a rendezettségtől. A unique nem használja ki a rendezhetőséget az értékeken, csak az egyenlőségvizsgálatot: meghı́vható olyan tı́pusú elemek konténerén, amin nem értelmezett rendezés. Ezenkı́vül léteznek olyan konténerek, mint például a list, amelynek van unique tagfüggvénye, mely hatékonyan eltávolı́tja a duplikátumokat a konténerből. 40 Alapok Az én megoldásommal a fordı́tóprogram ﬁgyelmeztet a unique vélhetően hibás használatára (IV.34) Ha a

felhasználó deﬁniálja, hogy mit szeretne kihasználni, hogy helyes eredményt kapjon a unique hı́vásakor, nem kap ﬁgyelmeztetést a fordı́tóprogramtól. II.48 Algoritmusok speciális előfeltételei Az algoritmusok mindegyike rendelekezik előfeltételekkel, melyek teljesülése esetén garantálja a speciﬁkációnak megfelelő működést. Az algoritmusoknak vannak olyan előfeltételei, amelyeket a fordı́tóprogram ellenőrizni tud, például, a sort algoritmus hı́vási paramétere tı́pusából kiderül, ha nem véletlen elérésű iterátorokat adunk át paraméterként. Egyes előfeltételek olyanok, amelyeket a fordı́tóprogramok nem ellenőriznek, de az előfeltétel megsértése nemdeﬁniált viselkedést okoz futási időben. A rendezett intervallumokat váró algoritmusok (például binary search, lower bound, upper bound, equal range, stb.) esetében a fordı́tóprogram nem ellenőrzi,

hogy rendezett-e az input intervallum. Az algoritmus implementációja szintén nem ellenőrzi ezt az előfeltételt, hanem kihasználja, hogy az adatok rendezettek. Ha nem rendezett intervallumon hı́vjuk meg ezeket az algoritmusokat, akkor az eredményük nemdeﬁniált. Figyeljük meg az alábbi kódrészletet: std::vector<int> v; int x; //. std::vector<int>::iterator i = std::lower bound( v.begin(), vend(), x ); A lower bound algoritmus célja, hogy megtaláljon egy elemet egy rendezett intervallumban: ez egy variánsa a logaritmikus keresésnek, a futás ideje logaritmikus, mivel kihasználja az input rendezettségét. Ha a konténer elemei nem növekvő sorrendben voltak, akkor a fenti kód viselkedése nemdeﬁniált. A rendezett intervallumokat váró algoritmusok futás közben nem ellenőrzik, hogy megfelelően rendezett-e az input. Még az sem feltétlenül elegendő, ha a sort algoritmust használjuk, mielőtt

meghı́vjuk a lower bound-ot: std::vector<int> v; int x; //. std::sort( v.begin(), vend(), std::greater<int>() ); Alapok 41 std::vector<int>::iterator i = std::lower bound( v.begin(), vend(), x ); A fenti kódnak ugyanúgy nemdeﬁniált a viselkedése, mintha nem is rendeztük volna a konténert: más rendezést használ a rendezéshez, mint a kereséshez. A rendezés nem feltétlenül áll rendelkezésünkre fordı́tási időben: például egy függvénypointert adunk át a sort-nak. Emiatt egy olyan megoldást adunk a problémára, amely futási időben ellenőrzi a speciális előfeltételeket (V5) II.49 A find és a count algoritmus A find algoritmus feladata, hogy két input iterátor által megadott intervallumban megkeressen egy értéket. A count algoritmus két input iterátor által megadott intervallumban megszámolja egy érték előfordulásának számát. Egyszerű algoritmusok, amelyek ennek

ellenére mégis okozhatnak meglepetéseket. Ezek az algoritmusok input iterátorokat várnak, ı́gy meghı́vhatóak egy set vagy multiset konténeren is: std::set<std::string> fruits; // . std::set<std::string>::iterator i = std::find( fruits.begin(), fruitsend(), "apple" ); if ( i != fruits.end() ) { // . } Ezek az algoritmusok azonban nem használhatják ki az adatszerkezet rendezettségét: lineáris futási idővel rendelkeznek. A szabványos asszociatı́v adatszerkezetek rendelkeznek find és count nevű tagfüggvénnyel, amelyek hatékonyabbak: logaritmikus futási idővel rendelkeznek: std::set<std::string> fruits; // . std::set<std::string>::iterator i = fruits.find( "apple" ); if ( i != fruits.end() ) { 42 Alapok // . } Ez utóbbi hatékonyabban, gyorsabban keresi meg az értéket a konténerben. Nem csak a hatékonyság miatt érdemes ez utóbbit használni: a find tagfüggvény és a

find algoritmus nem feltétlenül ugyanazt az eredményt adja. A find algoritmus az egyenlőség vizsgálatot használja annak eldöntésére, hogy két objektum megegyezik-e, mı́g a find tagfüggvény a rendezésen alapuló ekvivalenciát Nem garantált, hogy a kettő megegyezik Például egy string-eket tartalmazó asszociatı́v konténer használhat olyan rendezést, amely nem különbözteti meg a kis- és nagybetűket (case-insensitive). Figyeljük meg az alábbi kódot: typedef std::set<std::string, CICompare> Cont; Cont fruits; // . Cont::iterator i = fruits.find( "apPLe" ); Cont::iterator j = std::find( fruits.begin(), fruitsend(), "apPLe" ); Ebben a kódban ugyanazt a string-et keressük tagfüggvénnyel, mint algoritmussal. A string tı́pus operator==-je case-sensitive, azaz megkülönbözteti a kisbetűt a nagybetűtől, nem biztos, hogy ugyanazt az eredményt adja vissza a két különböző

megközelı́tés. Mivel az asszociatı́v konténerek enkapszulálják a rendezést, a tagfüggvények kihasználják. Ezért keresésnél és számlálásnál mindig érdemes a tagfüggvényt használni. A biztonság és a hatékonyság miatt kidolgoztam egy technikát, amely fordı́tási időben ﬁgyelmeztet, ha nem az optimálisat választottuk (IV.33) II.410 A vector<bool> konténer A vector<bool> egy speciális eset az STL-en belül: egy olyan konténer, ami megsérti a szabvány elvárásait. Használata jellemzően nem ajánlott, pedig az alapötlet hasznos lenne. A C programozási nyelv nagyon sokáig (1999-ig) nem deﬁniált külön tı́pust a logikai értékek leı́rására, ı́gy elterjedt az a gyakorlat, hogy az int tı́pust használták logikai értékek reprezentálására: a logikai tı́pus egy typedefje volt az int tı́pusnak. Létrehozták az igaznak és hamisnak megfelelő egész

értékeket és innentől kezdve nem használtak külön tı́pust a logikai értékekhez. Alapok 43 A ,,reverse-kompatibilitás” miatt a legtöbb C++ megvalósı́tásra érvényes az, hogy a bool-okat és az int-eket ugyanakkora tárterületen ábrázolják. (Ez egy mai átlagos gépen azt jelenti, hogy 32 biten ábrázolunk egy darab logikai értéket, ami 32-szeres pazarlást jelent.) Ha sok logikai értéket szeretnénk egy vector-ban tárolni, akkor a felesleges memóriapazarlás nagy lehet. A vector<bool>-t úgy deﬁniálták, hogy kihasználja a C++ sablonok specializációjának lehetőségét: nem a vector sablon példányosı́tása, hanem egyedi implementációval bı́r, hogy elkerülje a felesleges memória pazarlást. Jellemző reprezentációja, hogy egy egész érték (pl. long) számjegyeit használja a vector-ban szereplő bit-ek leı́rására: ekkor 32 biten 32 logikai értéket lehet

leı́rni. Az alábbi kódrészlet bemutatja a vector sablon és a vector<bool> kapcsolatát: template <class T, class Alloc = std::allocator<T> > class vector { T* p; size t capacity; size t size; public: vector() { // . } void push back( const T& t ) { // . } // . }; template <class Alloc> class vector<bool, class Alloc> { // speciális reprezentációja a vector<bool>-nak, ahol // nincs bool* adattag public: // publikus interface nagyon hasonló a fentihez 44 Alapok void push back( const bool& t ) { // . } vector() { //. } }; Ez látszólag jó ötlet, hogy hatékonyabban tároljuk a logikai értékeket. A vector<bool> furcsa viselkedését az alábbi kódrészletben ﬁgyelhetjük meg: std::vector<int> a; a.push back( 3 ); int* p = &a[0]; std::vector<bool> b; b.push back( true ); bool* q = &b[0]; // fordı́tási hiba! Az előző kódrészlet nem fordul le bool* q = &b[0];

sor miatt. Amikor viszont az általános vector sablont használjuk, a megfelelő sorral nincs probléma. Ez egy önellentmondás, mert ı́gy a vector<bool> nem teljesı́ti a C++ szabvány előı́rását. Így használata nem ajánlott Ráadásul a legtöbb STL referencia csak apróbetűvel megemlı́ti, hogy a vector<bool> egy specializáció. Nézzük meg a hátterét a fordı́tási hibának: template <class T, class Alloc = std::alloc> class vector { T* p; //. public: T& operator[]( int idx ) { return p[idx]; } Alapok 45 const T& operator[]( int idx ) const { return p[idx]; } // . }; template <class Alloc> class vector<bool, class Alloc> { // speciális reprezentációja a vector<bool>-nak, ahol // nincs bool* adattag public: class bool reference { // . }; bool reference operator[]( int idx ) { // . } }; Mivel a vector<bool> valójában nem bool értékeket tárol, az indexelő operátor

nem képes visszaadni egy bool&-t. Ezért egy proxyosztályt deﬁniálnak, amivel szimulálni lehet a bool&-t: bool reference Sajnos azonban nem lehet konverziót deﬁniálni egy bool reference-re mutató pointer és egy bool-ra mutató pointer között. Ez a viselkedés még furcsább lehet, ha valaki a vector-t használja ősosztályként: misztikus hibaüzeneteket kaphat a felhasználó, ha az altı́pust bool-lal példányosı́tja. Az én megoldásommal a fordı́tóprogram ﬁgyelmeztetést ad, ha valaki példányosı́tja a vector<bool>-t (IV.21) II.411 COAP Az STL konténereit értékek tárolására tervezték. Ugyanakkor gyakori, hogy heap-en allokált objektumokra mutató pointereket kell tárolnunk. Ilyenkor az STL kevéssé segı́ti elő a felmerülő problémák (pl. memória szivárgás) leküzdését. A szabvány könyvtárban viszont van egy sablon, amit pontosan 46 Alapok erre terveztek:

auto ptr, a C++ 2003-as szabványának egyetlen szabványos smart-pointere. Az auto ptr úgy működik, hogy egy heap-en létrehozott objektumra legfeljebb egy auto ptr objektum hivatkozhat, ez a tulajdonos, aki felel a tárterület felszabadı́tásáért. Amikor egy auto ptr-t másolunk, a lemásolt pointer nullpointer-ré változik és tovább nem hivatkozik a heap-en allokált tárterületre. Nincsenek felesleges másolatok, és garantált, hogy ki és mikor szabadı́tja fel a tárterületet. Sajnos azonban az auto ptr-eket nem szabad STL konténerekben tárolni (Containers of auto pointers (COAP)). Ennek az az oka, hogy a könyvtáron belül másolásokat hajthatnak végre, és emiatt a konténerben lévő auto ptrek nullpointer-ré válhatnának. Vegyük például az alábbi példát: struct Auto ptr less { bool operator()( const std::auto ptr<int>& a, const std::auto ptr<int>& b ) { return *a < b; } };

std::vector<std::auto ptr<int> > v; v.push back( new int( 7 ) ); // . std::sort( v.begin(), vend(), Auto ptr less() ); A fenti kódrészletben a konténer által tárolt pointer közül számos nullpointer-ré válhatna a rendezés során. Ezt elkerülendő a C++ Szabvány letiltotta a COAP-ok használatát. Azonban a fordı́tóprogramok nem mindegyike tartja be ezt a szabályt, ı́gy a COAP-ok használata hordozhatósági problémákat is felvet: attól, hogy az egyik fordı́tóprogrammal lefordul a kód még nem garantált, hogy másik fordı́tóval is lefordul. Az én megoldásommal a fordı́tóprogram mindenképpen hibaüzenetet ad, ha valaki COAP-ot használ (IV.22) Az új C++ szabvány bevezet STL-lel együttműködő smart-pointereket is, de meglévő legacy code-ok miatt szükséges továbbra is ﬁgyelni a COAP-ok használatát. Alapok II.412 47 Fejállományokkal kapcsolatos problémák A C++

Szabványa nem deﬁniálja, hogy a szabványos könyvtáron belül melyik fejállomány melyik másikat használja. Mivel használatkor a fejállomány elejére bekerül egy másiknak a tartalma, ez tranzitivitást eredményez. Ez az alapja egy hordozhatósági problémának. A különböző STL implementációknak más és más az include függősége. Ezt egy ı́rányı́tott gráfként ı́rhatjuk le: a gráf csúcsai a szabványkönyvtár fejállományai, és ı́rányı́tott él van két csúcs között, ha az egyik tartalmaz egy include direktı́vát egy másik fejállományra. Ez a gráf különbözhet különböző STL implementációk esetében. Az alapvető gond, hogy könnyű kihasználni egy adott rendszer include függőségét, hiszen a compiler a tranzitivitás miatt megtalál egy olyan komponenst, amit ugyan a felhasználó nem include-olt direktben, csak közvetett módon egy másik

fejállomány segı́tségével. Semmilyen ﬁgyelmeztetést nem kap a könyvtár felhasználója, hogy hibásan használja az STL-t. Ha egy ilyen kódot átviszünk egy másik gépre, más implementációk esetében esélyes, hogy nem fordul le a programunk. Létezik olyan STL megvalósı́tás, ahol például a vector fejállomány bemásoltatja az algorithm fejállományt. Ilyen megvalósı́tás esetében, a felhasználó include-olja a vector-t, akkor meg tudja hı́vni az algorithm fejállományban megı́rt algoritmusokat, anélkül, hogy extra direktı́vát ı́rna a kódjába. Ha ebben a formában a kódot átviszi máshova, a kód nem biztos, hogy lefordul. A problémát tetézi, hogy a C++ az include függőség miatt lassan fordul, ezért a fejlesztők mindig próbálnak spórolni a direktı́vákkal, hogy ne kelljen annyiszor feldolgoznia a fordı́tóprogramnak [55]. II.413 Iterátorok konverziója Ahogy

már korábban emlı́tettem, az STL konténerei négy különböző tı́pusú iterátort deﬁniálnak, hogy a felhasználók minél jobban igényeikhez igazı́thassák a bejárás módját. A probléma, hogy az STL minden szabványos konténerének van három olyan metódusa, amely csak a iterator tı́pusú iterátort fogad. Tehát, bár a konténerek négyfajta iterátortı́pust támogatnak, az egyiknek olyan privilégiumai vannak, amilyenek a többinek nincsenek [53]. A problémát bonyolı́tja, hogy const iterator objektumok nem konvertálódhatnak iterator-rá konstans-biztonsági okokból. Tehát, ha a felhasználónak van const iterator-a, akkor ezzel az objektummal nem tudja meghı́vni a fent emlı́tett metódusokat (pl. erase) Még a const cast sem tud segı́teni, hiszen a const iterator az nem const iterator. A 48 Alapok legésszerűbb megoldás a következő: std::list<int> li; // .

std::list<int>::const iterator ci = li.begin(); // . std::list<int>::iterator i = li.begin(); std::advance( i, std::distance<std::list<int>::const iterator>( i, ci ) ); A reverse iterator szintén nem konvertálódik iterator-rá automatikusan. A reverse iterator-nak van egy tagfüggvénye, amellyel iteratorrá lehet konvertálni: base() Ez ı́gy látszólag egyszerűnek tűnik, de mégsem triviális. Vegyük például az alábbi példát: const int max = 5; vector<int> v; v.reserve( max ); for ( int i = 1 ;i <= max; ++i ) { v.push back( i ); } vector<int>::reverse iterator ri= find( v.rbegin(), vrend(), 3 ); // Most ri a 3-ra mutat. vector<int>::iterator i( ri.base() ); Az alábbi ábra bemutatja a kódrészlet végrehajtása utáni állapotot: Az ábráról leolvasható, hogy van egy eltolás a reverse iterator-ok és az iterator-ok között, és emiatt a fenti kódrészletben lévő iterator nem

a 3-as értékre mutat, hanem a 4-esre. Ez félreértést okozhat, könnyen használható hibásan, például törlés esetén. Az én megoldásom fordı́tási ﬁgyelmeztetést generál, ha valaki meghı́vja a reverse iterátor base() metódusát (IV.6) Alapok II.414 49 Az asszociatı́v konténerek hordozhatósággal kapcsolatos problémái Az STL tervezésekor fontos szempont volt a hordozhatóság. Azonban a szabványban maradtak olyan kérdések, amelyeknek a megválaszolása az STL implementációira maradt. Ha kihasználjuk az implementációnk ilyen jellegű sajátosságait, akkor komoly problémáink lehetnek, ha másik platformra portoljuk a programunkat. Ennek a legtipikusabb esetei az asszociatı́v konténerekhez tartoznak. A multimap és a multiset nem deﬁniálja az ekvivalens kulcsú elemek sorrendjét. Amikor egy ilyen konténerben azonos kulcsú elemek vannak, akkor ezek között nincsen deﬁnit

sorrend: STL implementációnként változhat. Lényegesen nagyobb problémát vet fel a következő hordozhatósági kérdés. Mivel az asszociatı́v konténerek rendezetten tárolják az elemeiket, az garantált, hogy az asszociatı́v konténerek közül a map és a multimap a kulcsok tı́pusát const módosı́tóval látja el, hogy letiltsa a kulcsok megváltoztathatóságát: ı́gy például nem romlik a rendezettség. Mivel a set és a multiset az előzőek kulcstı́pusaiként foghatóak fel, felmerülhet, hogy ott vajon konstansok-e az elemek. A set és a multiset nem konstansokat tárol. Erre azért van szükség, hogy egy ilyen konténer elemein azokat a műveleteket meghı́vhassuk, ami nem rontja el a rendezettséget. Vegyük például az alábbi példát: class Employee { public: Employee( const std::string& name ); const string& name() const; const string& title() const; void setTitle( const string&

title ); . }; struct EmployeeCompare : std:binary function<Employee, Employee, bool> { bool operator()( const Employee& a, const Employee& b ) const { 50 Alapok return a.name() < bname(); } }; // . std::multiset<Employee, EmployeeCompare> employees; Van egy Employee tı́pusunk az alkalmazottak kezeléséhez. Az alkalmazottakat egy multiset-ben tároljuk név alapján rendezve Ilyenkor egy beosztott beosztását megváltoztathatjuk anélkül, hogy a rendezettség elromlana és a konténer inkonzisztenssé válna: std::string name = "John Doe"; employees.find( name )->setTitle( "vice president" ); Ha az alkalmazott nevét változtatnánk meg, akkor a konténer inkonzisztenssé válhatna. Sajnos, a szabvány inkonzisztens ezen a területen, ı́gy vitatható, de szabályos lehet olyan implementáció is, ahol const T&-val tér vissza a std::set<T>::iterator tı́pus operator* művelete, ı́gy

letiltva bárminemű módosı́tást. Összefoglalva, nem célszerű kihasználni azt, ha az STL implementációnk set vagy multiset iterátora nem tiltja le a konténer elemeinek a módosı́tását. Ha mégis megtesszük, akkor hordozhatósági problémákba ütközhetünk Az elegáns megoldást az jelenthetné, ha a tagfüggvényeknél megadható lenne egy order safe módosı́tó, a megfelelő operator* pedig order safe T& viszszatérési értékkel rendelkezne. II.415 A vector és a string reallokációja A vector-nak és a string-nek szükségszerűen egybefüggő tárterületet kell használnia: allokál egy adott kapacitással rendelkező területet a heap-en. (Az allokált memóriaterület mérete lekérdezhető capacity nevű tagfüggvénnyel.) Amikor ez a kapacitás betelik a konténer reallokációt hajt végre: allokál egy nagyobb tárterületet (jellemzően az addigi kapacitás

kétszeresét), átmásolja az elemeket a régi tárterületről az új tárterületre, és felszabadı́tja a régi tárterületet. Ez az eljárás jelentősen lassı́tja a program futását és invalidálja a konténer iterátorait. Célszerű elkerülni, amennyiben lehetséges Az alábbi kódrészlet nem optimális, mert a vector számos felesleges reallokációt hajt végre: std::vector<int> v; for( int i = 1; i <= 1000; ++i ) Alapok 51 { v.push back( i ); } A vector és a string támogatja a reallokációk elkerülését a reserve metódus segı́tségével. A reserve nem változtatja meg a konténer elemszámát (size), csak a kapacitását növeli A fenti kódrészlet hatékonyabb és biztonságosabb megfelelője: const int max = 1000; std::vector<int> v; v.reserve( max ); for( int i = 1; i <= max; ++i ) { v.push back( i ); } II.416 Iterátorok és pointerek összetévesztése A kezdeti

STL implementációkban gyakran a vector konténer iterátorai valódi pointerek voltak, az std::vector<T>::iterator szinonı́mája volt a T*-nak, az std::vector<T>::const iterator pedig a const T szinonı́mája volt. A vector C nyelven ı́rt API-kkal (Application Programming Interface) való kompatibilitást garantál. A vector tartalma paraméterként átadható olyan C kódoknak, ami egy tömböt vár: void doSomething( const int* pInts, size t numInts ); // . std::vector<int> v; // . if ( !v.empty() ) { doSomething( &v[0], v.size() ); } Azon STL implementációknál, ahol az iterator nem önálló tı́pus, hanem egy typedef, működhet a következő hı́vás is: if ( !v.empty() ) { 52 Alapok doSomething( v.begin(), vsize() ); } Újabb STL implementációk esetében ez nem fordul le, mert jellemzően áttértek a felhasználói iterátor tı́pusok használatára, például az öröklődés

lehetősége miatt. A fordı́tott irány is okozhat gondot: std::vector<int> v; // . int* p = &v[0]; // . v.erase( p ); Ehelyett az alábbi módon lehet törölni a pointer által hivatkozott elemet: v.erase( vbegin() + (p - &v[0]) ); Mindenképpen hordozhatósági problémához vezet, ha kihasználjuk, hogy egy implementáció esetében az iterátor valójában egy pointer [4]. II.417 Virtuális destruktorok hiánya A Java Collections Framework-kel ellentétben a C++ STL konténerei nem az öröklődésen alapulnak, nincsen például absztrakt bázisosztály megfelelője a szekvenciális konténereknek. Hatékonysági megfontolásból a C++ STL konténereinek nincsenek virtuális destruktoraik, ami legjellemzőbb tulajdonsága annak, hogy nem polimorﬁkus bázistı́pusnak szánták a konténereket [17]. Ha valaki mégis polimorﬁkus bázistı́pusként próbálja a konténereket használni, akkor az

nemdeﬁniált viselkedéshez vezethet [17]: class MyVector : public std::vector<int> { // . }; // . std::vector<int>* p = new MyVector(); // . delete p; Alapok 53 A kódrészlet lefordul, de az eredménye nemdeﬁniált viselkedéshez vezethet, jellemzően a delete hatására csak a std::vector<int> destruktora fut le, a MyVector-é nem. Ha valamilyen extra erőforrással dolgozik a MyVector tı́pus, annak felszabadı́tása nem megy automatikusan, destruktora segı́tségével. Ennek legtipikusabb esete, amikor memóriaszivárgás lép fel Mindenképpen problémához vezet, ha az STL konténereit polimorﬁkus bázistı́pusként próbáljuk felhasználni, amit a fordı́tóprogram nem szűr ki. III. fejezet Az STL formális megközelı́tése A C++ nyelv szabványa az STL speciﬁkációját is tartalmazza. Sajnos az STL speciﬁkációja informális [72]. Ez félreérthető és megnehezı́ti a helyesség

vizsgálatát. Ebben a fejezetben különböző speciﬁkációs eszközöket mutatok be, amivel az STL komponensei formálisan deﬁniálhatóak. Ezekkel az eszközökkel formális speciﬁkációkat adunk az STL egyes komponenseire. Bemutatom az általam kidolgozott technikát, amely a Hoare-módszer kibővı́tésén alapul. Ezenkı́vül a LaCert nyelv alapú STL speciﬁkáció lehetőségét mutatom be, amely főként a LaCert nyelv kitalálója és megvalósı́tója, Dévai Gergely munkájának tekinthető. Ezeket a speciﬁkációkat felhasználhatjuk a STL-t használó programok és könyvtárak helyességének az ellenőrzésére, az esetleges hibák kiszűrésére, STL implementációk helyességének vizsgálatára [77]. A LaCert nyelvű speciﬁkációk integrációjával olyan STL alapú kódok generálhatók, amelyek formálisan bizonyı́tottak [22]. III.1 A Hoare-módszer bővı́tése

III.11 A Hoare-módszer A Hoare-módszer[49] lényege, hogy a matematikai logikában tételek bizonyı́tására használt deduktı́v módszert alkalmazza a programok helyességének bizonyı́tására. Ez azt jelenti, hogy a programok helyességére vonatkozó tételek az axiómákból következtetési szabályok segı́tségével bebizonyı́thatók. Az axiómákat és a következtetési szabályokat a nyelv szemantikája alapján származtatjuk. A bizonyı́tásokat az elő-, utófeltételes formával végezhetjük el [43]. 54 Az STL formális megközelı́tése 55 {P (x, y)}skip{P (x, y)} {P (x, g(x, y))}y ← g(x, y){P (x, y)} (SKIP) (ASSIGN) III.1 táblázat A Hoare-módszer axiómái {P }S1 {Q1 } és {Q1 }S2 {Q} {P }S1 ; S2 {Q} (SEQ) {P ∧ α}S1 {Q} és {P ∧ ¬α}S2 {Q} {P }if α then S1 else S2 {Q} (IF) {P ∧ α}S{P } és (P ∧ ¬α) ⇒ Q {P }while α do S od{Q} (WHILE) (P ⇒ P1 ) és {P1 }S{Q1 }

és (Q1 ⇒ Q) {P }S{Q} (CONC) III.2 táblázat A Hoare-módszer következtetési szabályai 56 Az STL formális megközelı́tése P (x, y) ⇒ Q(x, g(x, y)) {P (x, y)}y ← g(x, y){Q(x, y)} (ASSIGN-2) P ⇒ P1 és {P1 }S1 {Q1 } és Q1 ⇒ P2 és {P2 }S2 {Q2 } és Q2 ⇒ Q {P }S1 ; S2 {Q} (SEQ-2) P ⇒ P1 és {P1 ∧ α}S1 {Q1 } és {P1 ∧ ¬α}S2 {Q1 } és Q1 ⇒ Q {P }if α then S1 else S2 f i{Q} (IF-2) P ⇒ P1 és {P1 ∧ α}S{Q1 } és (P1 ∧ ¬α) ⇒ Q1 és Q1 ⇒ Q {P }if α then Sf i{Q} (IF-3) P (x,y)⇒I(x,y) és {I(x,y)∧α(x,y)}S{I(x,y)} és I(x,y)∧¬α(x,y)⇒Q(x,y) {P (x,y)}while α(x,y) do S od{Q(x,y)} (ITER) III.3 táblázat A Hoare-módszer további szabályai P (x, y) ⇒ I(x, y) és I(x, y) ⇒ E(x, y) ∈ W< és {I(x, y) ∧ α(x, y) ∧ E = E(x, y)}S{I(x, y) ∧ E(x, y) < E} és I(x, y) ∧ ¬α(x, y) ⇒ Q(x, y) {P (x, y)}while α(x, y) do S od{Q(x, y)} III.4 táblázat A teljes helyesség

bizonyı́tásának következtetési szabálya Az STL formális megközelı́tése 57 P (x, y) ⇒ I(x, y, 0) és I(x, y, i) ⇒ i < k(x) és {I(x, y, i) ∧ α(x, y)}S{I(x, y, i + 1} és I(x, y, i) ∧ ¬α(x, y) ⇒ Q(x, y) {P (x, y)}while α(x, y) do S od{Q(x, y)} III.5 táblázat Az iteráció következtetési szabálya termináló függvénnyel Tétel : A Hoare-módszer következtetési szabályai helyesek. A bizonyı́tás megtalálható [49]-ben. Legyen adott az S(x, y) struktúrált program, amelynek egy tetszőleges részprogramját s(x, y) jelöli. Tegyük fel, hogy igaz a következő tétel minden ilyen s(x, y) részprogramra: {Q(x) ∧ y = Is (x)}s(x, y){Q(x) ∧ y = Os (x)}, ahol fs (x, Is (x)) = Os (x), azaz Is (x) jelöli az s(x, y) függvény bemenő és Os (x) a hozzá tartozó eredmény adatát a program x bemenő paraméterei mellett. Tétel : Minden ilyen tulajdonságú részprogramra vonatkozó

fenti tétel, a Hoare-módszer segı́tségével bebizonyı́tható. Ez utóbbi tétel mondja ki a Hoare-módszer teljességét. A bizonyı́tás megtalálható [49]-ben. A különböző STL implementációk helyességének bizonyı́tásához is ad módszert [49]: Procedurálisan adott konkrét speciﬁkáció elő-, és utófeltételekkel adott absztrakt speciﬁkáció helyessége cı́mű fejezetben található a következő tétel: Adottak a da és a dc speciﬁkációk közös szignatúrával: da = (A, F, E); aholfi ∈ F ; {true}a = f0 {postf0 (a)}, {prefi (a)}b = fi (a){postfi (a, b)} ∈ Ea , i = 1, 2, . , n; dc = (C, G, EC ); Qgi ∈ EC , gi ∈ G, i = 1, 2, . , n; 58 Az STL formális megközelı́tése Legyen az absztrakt invariáns A = {a|Ia (a)}, a konkrét invariáns C = {c|Ic (c)}. Legyenek a konkrét szemantika eljárásai a következők: procedure g0 begin Q0 end; procedure gi begin Qi end; i=1,2,.

,n; A reprezentációs függvény: φ : C A. Ha a következő tételek teljesülnek: 1. (∀c ∈ C)(Ic (c) ⇒ Ia (φ(c)); 2. {true}Q0 {postf0 (φ(c)) ∧ Ic (c)}; 3. (∀f ∈ F ) : {prefi (φ(c)) ∧ Ic (c)}Qi {postfi (φ(c), φ(c′ )) ∧ Ic (c′ )}; ahol a 2. és 3 a teljes helyességi tételek, akkor a dc konkrét speciﬁkáció helyes a da absztrakt speciﬁkáció szerint. A bizonyı́tás megtalálható [49]-ben. III.12 A formalizmus bővı́tése Először bemutatom az elő-, utófeltételes speciﬁkáció [49] leı́rását: {P }S{Q} jelöli a továbbiakban, azt hogy P előfeltétel (precondition) esetén S program hatására a Q utófeltételhez (postcondition) jutunk. A P és Q leı́rásához elsőrendű logikai[60] kifejezéseket használunk. Az S program a továbbiakban szintaktikusan helyes C++ utası́tás vagy utası́tássorozat, hiszen a módszer jól használható C++ nyelven ı́rt programokra [110].

Nézzünk egy egyszerű példát! {true}int a = 1; {a = 1} {a = 1} + +a; {a = 2} Egy inicializálatlan (lokális) változó értékének a leı́rására a ? szimbólumot használjuk: {true}int a; {a =?} Szükség esetén ezek indexelhetők is: {true} Az STL formális megközelı́tése 59 int a; int b = a; int c; {a =?1 ∧ b =?1 ∧ c =?2 } U ndef szimbólummal jelöljük azt, hogy az utası́tásnak vagy programnak nemdeﬁniált az eredménye. Ha a program olyan utası́tást hajt végre, ami egy kivételt(exception) vált ki, azt Exc(a) módon jelöljük, ahol a a kivétel. Ha egy utófeltételben több függvény szekvenciális végrehajtását kell leı́rni, azt a SEQ(f (a), g(b)) kifejezés fogja leı́rni, tehát ez azt jelenti, hogy először az f (a) függvény lefut, aztán pedig a g(b). Egy adott osztály esetén I-vel jelöljük az osztályhoz tartozó tı́pus- vagy osztályinvariánst. Az

iterátoroknak sok jellemzője van, ezért a formális modell is szerteágazó speciﬁkációt használ. A const it(it) predikátum deﬁniálja, hogy az it azonosı́tójú iterátor const iterator Ha egy it nem const iterator, azt akkor azt a speciﬁkációban ¬const it(it) ı́rja le. Hasonlóképpen rev it(it) predikátum az iterátor haladási irányát ı́rja le. Ebben az esetben az it iterátor hátrafelé halad, és az előrefele haladó iterátorra ¬rev it(it) speciﬁkációt használjuk. Az iterátorok legfontosabb tulajdonsága, az hogy egy konténer elemére mutatnak. Az it nevű iterátor által jelölt elemet ∗it = xj kifejezés ı́rja le Ha a konténer végére mutat: ∗it = x.end, itt x a konténer objektum azonosı́tója Ha hátrafele halad a bejárás: ∗it = x.rend A bejáróknak létezik kategóriája is, ezt a cat(it) függvény fogja kifejezni. Ennek a függvénynek 5 értéke van:

In/Out/For/Bi/Ran Az In input iterátorok kategóriája, az Out output iterátorok kategóriája A For a forward iterátorok kategóriáját speciﬁkálja, a Bi (bidirectional) a kétirányú iterátorok és végül a Ran (random-access) pedig a véletlen elérésű iterátorok kategóriája. Egy bejáróról azt is tudni kell, hogy milyen tı́pusú konténerhez tartozik. A type(it) függvénnyel fejezzük ki ezt. A konténerekben egy adott tı́pushoz tartozó objektumok vannak, azaz objektumok egy sorozata egy konténer. Az < x1 , x2 , , xn > jelöl egy n elemből álló sorozatot. Az üres sorozat jele értelemszerűen: <> Egy konténer lehet konstans és nemkonstans is. A C++ nyelv megengedi a const-on való tagfüggvény túlterhelést, azaz más függvény futhat le egy konstans és egy nemkonstans objektumon azonos tagfüggvényhı́vás esetén is. Ha egy x objektum konstans, azt a következő

predikátum deﬁniálja: const(x). 60 Az STL formális megközelı́tése III.13 Specifikációk Most STL speciﬁkációs példákat mutatok az általam kidolgozott formalizmus segı́tségével. Ennél részletesebb speciﬁkációm is elérhető [61] LessThenComparable Ez a concept azt fejezi ki, hogy a T osztályon értelmezett egy f : T × T 7 L függvény, ami egy szigorú részbenrendezés. Alapértelmezésben f neve operator<. Ennek a tı́pusnak az operator()-a értékeli ki, hogy a két paraméter milyen viszonyban áll a rendezés szerint. LT C(T, f ) : I = {(∀x ∈ T : f (x, x) = f alse) ∧ ∀x, y ∈ T : f (x, y) ⇒ ¬f (y, x) ∧ ∀x, y, z ∈ T : f (x, y) ∧ f (y, z) ⇒ f (x, y)} A tı́pusinvariáns mutatja meg, hogy a rendezési funktornak milyen feltételekkel kell rendelkeznie. Iterátorok hierarchiája cat(it) = Ran ⇒ cat(it) = Bi cat(it) = Bi ⇒ cat(it) = F or cat(it) = F or ⇒ cat(it) = In cat(it) = F

or ⇒ cat(it) = Out Iterátor kategóriák type(it) = list < T >⇒ cat(it) = Bi type(it) = deque < T >⇒ cat(it) = Ran type(it) = vector < T >⇒ cat(it) = Ran type(it) = set < T >⇒ cat(it) = Bi ∧ const it(it) type(it) = multiset < T >⇒ cat(it) = Bi ∧ const it(it) type(it) = map < I, T >⇒ cat(it) = Bi ∧ const it(it) type(it) = multimap < I, T >⇒ cat(it) = Bi ∧ const it(it) Az STL formális megközelı́tése 61 Iterátorok létrehozása {true}list < T >:: iterator it; {type(it) = list < T > ∧ ∗ it =?∧ ∧¬const it(it) ∧ ¬rev it(it)} {true}list < T >:: const iterator cit; {type(cit) = list < T > ∧ ∗ cit =?∧ ∧const it(cit) ∧ ¬rev it(cit)} {true}list < T >:: reverse iterator rit; {type(rit) = list < T > ∧ ∗ rit =?∧ ∧¬const it(rit) ∧ rev it(rit)} {true}list < T >:: const reverse iterator crit; {type(crit) = list < T > ∧ ∧ ∗ crit

=? ∧ const it(crit) ∧ rev it(crit)} Néhány iterátor művelet Valid iterátor dereferálása: {x =< x1 , x2 , . , xn > ∧cat(it) = In∧∗it = xj }T e = ∗it; {e = xj ∧∗it = xj ∧ ∧cat(it) = In ∧ x =< x1 , x2 , . , xn >} Invalid iterátor dereferálása: {x =< x1 , x2 , . , xn > ∧cat(it) = In ∧ ∗it = xend}T e = ∗it; {U ndef } Iterátor inkrementálása: {x =< x1 , x2 , . , xn > ∧cat(it) = In ∧ ∗it = xj ∧ j < n ∧ ¬rev it(it)} + +it; {∗it = xj+1 ∧ x =< x1 , x2 , . , xn > ∧cat(it) = In ∧ ¬rev it(it)} End iterátor elérése: {x =< x1 , x2 , . , xn > ∧cat(it) = In∧∗it = xn ∧¬rev it(it)}++it; {∗it = xend∧ ∧x =< x1 , x2 , . , xn > ∧cat(it) = In ∧ ¬rev it(it)} End iterátor inkrementálása: {x =< x1 , x2 , . , xn > ∧cat(it) = In∧∗it = xend∧¬rev it(it)}++it; {U ndef } 62 Az STL formális megközelı́tése Néhány

algoritmus {x =< x1 , x2 , . , xn > ∧cat(it1 ) = Bi ∧ cat(it2 ) = Bi ∧ ∗it1 = xk ∧ ∧ ∗ it2 = xl ∧ ¬const(x)} reverse(it1 , it2 ); {x =< x1 , x2 , . , xk−1 , xl−1 , xl−2 , , xk , xl , xl+1 , , xn > ∧¬const(x)∧ ∧ ∗ it1 = xl ∧ ∗it2 = xl−1 ∧ cat(it1 ) = Bi ∧ cat(it2 ) = Bi} {cat(it1 ) = Bi ∧ cat(it2 ) = Bi ∧ (∗it1 =? ∨ ∗it2 =?)} reverse(it1 , it2 ); {U ndef } {x =< x1 , x2 , . , xn > ∧∗it1 = xi ∧∗it2 = xj ∧cat(it1 ) = F or∧cat(it2 ) = F or ∧cat(it3 ) = F or ∧ LT C(T, operator <)} it3 = max element(it1 , it2 ); {∗it3 = xk ∧ k ∈ [i, j) ∧ ∀l ∈ [i, j) : xl < xk ∧ cat(it3 ) = F or∧ ∧x =< x1 , x2 , . , xn > ∧∗it1 = xi ∧∗it2 = xj ∧cat(it1 ) = F or∧cat(it2 ) = F or} {cat(it1 ) = F or ∧ cat(it2 ) = F or ∧ cat(it3 ) = F or ∧ LT C(T, operator <)∧ ∧(∗it1 =? ∨ ∗it2 =?)} it3 = max element(it1 , it2 ); {U ndef } Az STL formális

megközelı́tése 63 A vector specifikációjának részlete Mivel nem a specializált vector-t speciﬁkáljuk a tı́pusinvariáns: I = {T ̸= bool} Üres vector létrehozása: {true}vector < T > v; {v =<> ∧¬const(v)} Elem beszúrása a konténer végéhez: {v =< v0 , v1 , . , vn > ∧¬const(v)}vpush back(x); {v =< v0 , v1 , . , vn , x > ∧¬const(v)} A konténer mérete: {v =< v0 , v1 , . , vn >}s = vsize(); {s = n + 1 ∧ v =< v0 , v1 , , vn >} {v =<>}s = v.size(); {s = 0 ∧ v =<>} Üres konténer első és utolsó elemének megváltoztatása nemdeﬁniált: {v =<> ∧¬const(v)}v.f ront() = c; {U ndef } {v =<> ∧¬const(v)}v.back() = c; {U ndef } Konténer elemének törlése: {v =< v0 , v1 , . , vn > ∧ ∗ it = vi ∧ type(it) = vector < T > ∧¬const it(it)∧ ∧¬rev it(it) ∧ ¬const(v)}v.erase(it); {v =< v0 , v1 , . , vi−1 , vi+1 , , vn

> ∧ ∗ it = vi+1 ∧ ¬const(v)} III.14 Példák Tegyük fel, hogy adott egy vector<char> objektum, ami tehát karaktereket tárol, azaz egy szöveg betűit tartalmazza. Fordı́tsuk meg a szöveget! Első megoldás Az első megoldás egy stack adapter segı́tségével fordı́tja meg a szöveget: 64 Az STL formális megközelı́tése std::vector<char> megford( const std::vector<char>& v ) { std::stack<char> ut; int i = 0; while( i != v.size() ) { char t = v[i]; ut.push( t ); ++i; } std::vector<char> ret; while ( !ut.empty() ) { char t = ut.top(); ret.push back( t ); ut.pop(); } return ret; } Az alprogram előfeltétele: φ = {v =< b1 , b2 , . , bn > ∧const(v) ∧ n ≥ 0} És az utófeltétele: ψ = {ret =< bn , bn−1 , . , b1 > ∧v =< b1 , b2 , , bn >} A szekvencia szabályát kétszer alkalmazva az első ciklus előtt: φ′ = {const(v) ∧ v =< b1 , b2 , . , bn > ∧n

≥ 0 ∧ ut =<> ∧¬const(ut) ∧ i = 0 ∧ ¬const(i)}. Legyen φ′′ = {v =< b1 , b2 , . , bn > ∧const(v)∧n ≥ 0∧ut =< b1 , b2 , , bn > ∧¬const(ut)}. Az első ciklus parciális helyességéhez invariánsra van szükség: I1 = {v =< b1 , b2 , . , bn > ∧const(original) ∧ ut =< b1 , b2 , , bj > ∧¬const(ut) ∧ i = j} Ekkor a következő nyilvánvalóan igaz: φ′ ⇒ I1 {I1 ∧ i = v.size()} ⇒ φ′′ szintén igaz, hiszen {I1 ∧ i = vsize()} ⇒ ⇒ {I1 ∧ i = n} ⇒ {v =< b1 , b2 , . , bn > ∧const(original) ∧ j = n∧ ∧ut =< b1 , b2 , . , bj >} ⇒ {v =< b1 , b2 , , bn > ∧const(original)∧ ∧ut =< b1 , b2 , . , bn >⇒ φ′′ Az STL formális megközelı́tése 65 Továbbá be kell látni, hogy a ciklusmag megtartja az invariánst: {v =< b1 , b2 , . , bn > ∧const(original)∧ut =< b1 , b2 , , bj−1 > ∧¬const(ut)∧ ∧j = i

− 1} char t = v[i]; ut.push( t ); ++i; {v =< b1 , b2 , . , bn > ∧const(original)∧ut =< b1 , b2 , , bi−1 , bi > ∧¬const(ut)∧ ∧j = i}. Alkalmazva a szekvencia szabályát, és a vector-ra vonatkozó szabályokat: {v =< b1 , b2 , . , bn > ∧const(original)∧ut =< b1 , b2 , , bj−1 > ∧¬const(ut)∧ j = i − 1} char t = v[i]; {v =< b1 , b2 , . , bn > ∧const(original)∧ut =< b1 , b2 , , bj−1 > ∧¬const(ut)∧ ∧j = i − 1 ∧ t = bi+1 } ⇒ {v =< b1 , b2 , . , bn > ∧const(original)∧ ∧ut =< b1 , b2 , . , bj−1 > ∧¬const(ut) ∧ j = i − 1 ∧ t = bj } A szekvencia és a stack-re vonatkozó szabályok szerint: {v =< b1 , b2 , . , bn > ∧const(original)∧ut =< b1 , b2 , , bj−1 > ∧¬const(ut)∧ ∧j = i − 1 ∧ t = bj } ut.push( t ); {v =< b1 , b2 , . , bn > ∧const(original)∧ut =< b1 , b2 , , bj−1 , bj > ∧¬const(ut)∧ ∧j = i

− 1 ∧ t = bj }. Ismét alkalmazva a szekvenciára vontakozó szabályt: {v =< b1 , b2 , . , bn > ∧const(original)∧ut =< b1 , b2 , , bj−1 , bj > ∧¬const(ut)∧ ∧j = i − 1 ∧ t = bj } ++i; {v =< b1 , b2 , . , bn > ∧const(original)∧ut =< b1 , b2 , , bj−1 , bj > ∧¬const(ut)∧ ∧j = i ∧ t = bj } ⇒ I1 . Az első ciklus teljes helyességéhez még termináló függvényre van szükségünk: t = i, korlátja: n. Világos, hogy φ′ ⇒ t = 0, valamint, hogy I1 invariáns teljesülése esetén t < k. Nyilvánvaló a fenti bizonyı́tásból és terminálófüggvény deﬁnı́ciójából, hogy a ciklusmag 1-gyel növeli a terminálófüggvény értékét. Legyen φ′′′ = {v =< b1 , b2 , . , bn > ∧const(v) ∧ ut =< b1 , b2 , , bn > ∧ ∧n ≥ 0 ∧ ¬const(ut) ∧ ret =<> ∧¬const(ret)}. Világos a szekvencia és a vector létrehozására

vonatkozó szabály alapján, hogy φ′′ (std::vector<char> ret;)φ′′′ . A második ciklus helyességéhez újabb invariánsra van szükségünk: I2 = {v =< b1 , b2 , . , bn > ∧const(original) ∧ ut =< b1 , b2 , , bj > ∧ ∧¬const(ut) ∧ ret =< bn , bn−1 , . bj+1 > ∧¬const(ret)} 66 Az STL formális megközelı́tése Ekkor a következő nyilvánvalóan igaz: φ′′′ ⇒ I2 {I2 ∧ ut.empty()} ⇒ ψ-t sem nehéz belátni: a stack-re vonatkozó szabályok szerint az invariáns és ut.empty() akkor teljesülhet egyszerre, ha j = 0 A {I2 ∧ j = 0} ⇒ ψ magától értetődő. Be kell még látni, hogy a második ciklus magja megtartja az invariánst, azaz: {v =< b1 , b2 , . , bn > ∧const(original) ∧ ut =< b1 , b2 , , bj > ∧ ∧¬const(ut) ∧ ret =< bn , bn−1 , . bj+1 > ∧¬const(ret)} char t = ut.top(); ret.push back( t ); ut.pop(); {v =< b1 , b2 , . ,

bn > ∧const(original) ∧ ut =< b1 , b2 , , bj−1 > ∧ ∧¬const(ut) ∧ ret =< bn , bn−1 , . bj > ∧¬const(ret)} Ehhez először alkalmazzuk a szekvenciára és a stack-re vonatkozó szabályt: {v =< b1 , b2 , . , bn > ∧const(original) ∧ ut =< b1 , b2 , , bj > ∧ ∧¬const(ut) ∧ ret =< bn , bn−1 , . bj+1 > ∧¬const(ret)} char t = ut.top(); {v =< b1 , b2 , . , bn > ∧const(original) ∧ ut =< b1 , b2 , , bj > ∧ ∧¬const(ut) ∧ ret =< bn , bn−1 , . bj+1 > ∧¬const(ret) ∧ t = bj } Most a vector push back-jére vonatkozó szabályt alkalmazzuk a szekvencia szabályával: {v =< b1 , b2 , . , bn > ∧const(original) ∧ ut =< b1 , b2 , , bj > ∧ ∧¬const(ut) ∧ ret =< bn , bn−1 , . bj+1 > ∧¬const(ret) ∧ t = bj } ret.push back( t ); {v =< b1 , b2 , . , bn > ∧const(original) ∧ ut =< b1 , b2 , , bj > ∧ ∧¬const(ut) ∧

ret =< bn , bn−1 , . bj > ∧¬const(ret) ∧ t = bj } Még egyszer alkalmazzuk a szekvenciára és a stack-re vonatkozó szabályt: {v =< b1 , b2 , . , bn > ∧const(original) ∧ ut =< b1 , b2 , , bj > ∧ ∧¬const(ut) ∧ ret =< bn , bn−1 , . bj > ∧¬const(ret) ∧ t = bj } ut.pop(); {v =< b1 , b2 , . , bn > ∧const(original) ∧ ut =< b1 , b2 , , bj−1 > ∧ ∧¬const(ut) ∧ ret =< bn , bn−1 , . bj > ∧¬const(ret) ∧ t = bj } ⇒ I2 A második ciklus teljes helyességéhez még egy termináló függvényre van szükségünk: t = ret.size(), korlátja k = n Látható, hogy φ′′′ ⇒ t = 0 A ciklusmagban mindig lefutó push back művelet garantálja, hogy a terminálófüggvény értéke eggyel nő. Látható, hogy I2 invariáns teljesülése esetén t = n − j < k = n. Ezzel beláttuk, hogy a függvény megoldja a speciﬁkált feladot. Az STL formális

megközelı́tése 67 Második megoldás A második megoldás iterátorok segı́tségével oldja meg a feladatot: std::vector<char> megford( const std::vector<char>& v ) { std::vector<char> ret; std::vector<char>::const reverse iterator it = v.rbegin(); while( it != v.rend() ) { char t = *it; ret.push back( t ); ++it; } return ret; } Az alprogram ugyanazzal az elő- és utófeltétellel rendelkezik, mint az előbb: φ = {v =< b1 , b2 , . , bn > ∧const(v) ∧ n ≥ 0} ψ = {ret =< bn , bn−1 , . , b1 > ∧v =< b1 , b2 , , bn >} Legyen φ′ = {v =< b1 , b2 , . , bn > ∧const(v) ∧ n ≥ 0 ∧ ret =<> ∧ ∧¬const(ret)}. A szekvenciára, valamint a vector létrehozására vonatkozó szabály szerint: φ (std::vector<char> ret;) φ′ . Legyen φ′′ = {v =< b1 , b2 , . , bn > ∧const(v) ∧ n ≥ 0 ∧ ret =<> ∧ ∧¬const(ret)∧∗it = bn ∧const it(it)∧type(it)

= vector < char > ∧rev it(it)}. A szekvenciára, valamint az iterátor létrehozására vonatkozó szabály szerint: φ′ (std::vector<char>::const reverse iterator it;) φ′′ . A ciklus parciális helyességéhez invariáns szükséges: I = {v =< b1 , b2 , . , bn > ∧const(v) ∧ n ≥ 0 ∧ ret =< bn , bn−1 , , bj+1 > ∧ ∧¬const(ret)∧∗it = bj ∧const it(it)∧type(it) = vector < char > ∧rev it(it)}. Látható, hogy φ′′ ⇒ I. Továbbá {I ∧ it = v.rend()} ⇒ ψ, mert {I ∧ it = vrend()} ⇒ {I ∧ it = v.rend()} ⇒ j = 0 {I ∧ j = 0} ⇒ ψ Ezenkı́vül be kell látni, hogy a ciklusmag megtartja az invariánst, azaz: {v =< b1 , b2 , . , bn > ∧const(v) ∧ n ≥ 0 ∧ ret =< bn , bn−1 , , bj+1 > ∧ ∧¬const(ret) ∧ ∗it = bj ∧ const it(it) ∧ type(it) = vector < char > ∧ ∧rev it(it)} char t = *it; 68 Az STL formális megközelı́tése ret.push back( t

); ++it; {v =< b1 , b2 , . , bn > ∧const(v) ∧ n ≥ 0 ∧ ret =< bn , bn−1 , , bj+1 , bj > ∧ ∧¬const(ret) ∧ ∗it = bj−1 ∧ const it(it) ∧ type(it) = vector < char > ∧rev it(it)}. Ehhez először használjuk a szekvenciára és az iterátorokra vonatkozó szabályokat: {v =< b1 , b2 , . , bn > ∧const(v) ∧ n ≥ 0 ∧ ret =< bn , bn−1 , , bj+1 > ∧ ∧¬const(ret) ∧ ∗it = bj ∧ const it(it) ∧ type(it) = vector < char > ∧ ∧rev it(it)} char t = *it; {v =< b1 , b2 , . , bn > ∧const(v) ∧ n ≥ 0 ∧ ret =< bn , bn−1 , , bj+1 > ∧ ∧¬const(ret) ∧ ∗it = bj ∧ const it(it) ∧ type(it) = vector < char > ∧ ∧rev it(it) ∧ t = bj }. Ezután a szekvenciára és a vector-ra vonatkozó szabályokat: {v =< b1 , b2 , . , bn > ∧const(v) ∧ n ≥ 0 ∧ ret =< bn , bn−1 , , bj+1 > ∧ ∧¬const(ret) ∧ ∗it = bj ∧ const it(it) ∧ type(it) =

vector < char > ∧ ∧rev it(it) ∧ t = bj } ret.push back( t ); {v =< b1 , b2 , . , bn > ∧const(v) ∧ n ≥ 0 ∧ ret =< bn , bn−1 , , bj+1 , t > ∧ ∧¬const(ret) ∧ ∗it = bj ∧ const it(it) ∧ type(it) = vector < char > ∧ ∧rev it(it) ∧ t = bj } {v =< b1 , b2 , . , bn > ∧const(v) ∧ n ≥ 0 ∧ ret =< bn , bn−1 , , bj+1 , t > ∧ ∧¬const(ret) ∧ ∗it = bj ∧ const it(it) ∧ type(it) = vector < char > ∧ ∧rev it(it) ∧ t = bj } ⇒ {v =< b1 , b2 , . , bn > ∧const(v) ∧ n ≥ 0∧ ∧ret =< bn , bn−1 , . , bj+1 , bj > ∧¬const(ret) ∧ ∗it = bj ∧ const it(it)∧ ∧type(it) = vector < char > ∧rev it(it) ∧ t = bj }. {v =< b1 , b2 , . , bn > ∧const(v) ∧ n ≥ 0 ∧ ret =< bn , bn−1 , , bj+1 , bj > ∧ ∧¬const(ret) ∧ ∗it = bj ∧ const it(it) ∧ type(it) = vector < char > ∧ ∧rev it(it) ∧ t = bj } ++it; {v =< b1 , b2 , .

, bn > ∧const(v) ∧ n ≥ 0 ∧ ret =< bn , bn−1 , , bj+1 , bj > ∧ ∧¬const(ret) ∧ ∗it = bj−1 ∧ const it(it) ∧ type(it) = vector < char > ∧ ∧rev it(it) ∧ t = bj } ⇒ I. A ciklus teljes helyességéhez még egy termináló függvényre van szükségünk: t = ret.size(), korlátja k = n Látható, hogy φ′′ ⇒ t = 0 A ciklusmagban mindig lefutó push back művelet garantálja, hogy a terminálófüggvény értéke eggyel nő. Látható, hogy I invariáns teljesülése esetén Az STL formális megközelı́tése 69 t = n − j < k = n. Ezzel beláttuk, hogy az alprogram megoldja a feladatot. Harmadik megoldás A harmadik megoldásban STL algoritmus hı́vással oldom meg a feladatot: std::vector<char> megford( const std::vector<char>& v ) { std::vector<char> ret = v; std::reverse( ret.begin(), retend() ); return ret; } Az alprogram ugyanazzal az elő- és

utófeltétellel rendelkezik, mint az előbb: φ = {v =< b1 , b2 , . , bn > ∧const(v) ∧ n ≥ 0} ψ = {ret =< bn , bn−1 , . , b1 > ∧v =< b1 , b2 , , bn >} Alkalmazzuk a szekvencia és a vector-ra vonatkozó szabályokat: {v =< b1 , b2 , . , bn > ∧const(v) ∧ n ≥ 0} std::vector<char> ret = v; {v =< b1 , b2 , . , bn > ∧const(v)∧n ≥ 0∧ret =< b1 , b2 , , bn > ∧¬const(ret)} Mivel type(v.begin()) = vector < int >⇒ cat(vbegin()) = Ran ⇒ cat(v.begin()) = Bi, valamint type(vend()) = vector < int >⇒ cat(vend()) = Ran ⇒ cat(v.end()) = Bi, ı́gy az algoritmus előfeltétele teljesül Alkalmazzuk a szekvencia és a reverse-ra vonatkozó szabályokat: {v =< b1 , b2 , . , bn > ∧const(v)∧n ≥ 0∧ret =< b1 , b2 , , bn > ∧¬const(ret)} std::reverse( ret.begin(), retend() ); {v =< b1 , b2 , . , bn > ∧const(v) ∧ n ≥ 0 ∧ ret =< bn , bn−1 , , b2 ,

b1 > ∧ ∧¬const(ret)} ⇒ ψ. Ezzel beláttuk, hogy az alprogram megoldja a feladatot. III.2 LaCert A LaCert programozási nyelv célja, hogy garantáltan helyes programok ı́rását megkönnyı́tse [18]. Ebben a nyelvben a programozó először egy formális speciﬁkációt ı́r, és a speciﬁkáció lépésenkénti ﬁnomı́tásával addig ﬁnomı́tja, amı́g a bizonyı́tás el nem készül. Fordı́táskor a fordı́tóprogram ellenőrzi a bizonyı́tást és generálja a garantáltan helyes program kódját valamely szokásos programozási nyelven [19]. 70 Az STL formális megközelı́tése Ebben a nyelvben a program állapotát elsőrendű logikai formulával ı́rjuk le kifejezésekként [60]. Az állapotok között temporális haladási tulajdonságokat speciﬁkál a programozó, amelyet a >> szimbólummal lehet leı́rni Szokásos elsőrendű logikai és temporális logikai operátorok

megtalálhatóak LaCert-ben [18, 19]. Az ip (instrution pointer) egy előre deﬁniált változó, ami a program végrehajtásának pillanatnyi időpillanatát deﬁnálja. Például az alábbi speciﬁkáció azt ı́rja le, hogy A-ból eljutunk B-be és ekkor s értéke a ”Hello!” string lesz: ip = A > > ip = B & s = "Hello!"; A LaCert nyelv segı́tségével formális leı́rást adunk az STL-hez [21, 22]. Ehhez először három elemi függvényt deklarálunk: a nil() függvény egy üres konténert hoz létre, a .+ és + operátorok pedig egy-egy elemet adnak a konténer elejéhez illetve végére A LaCert deklarációi ezeknek a műveleteknek: type( Seq, 1 ); function( ’’nil’’, Seq(#T) ); function( ’’.+’’, Seq(#T), #T, Seq(#T) ); function( ’’+.’’, Seq(#T), Seq(#T), #T ); A tı́pusdeklaráció bevezeti a Seq sablont egy tı́pusparaméterrel, ahol a tı́pusparaméter a tárolt elemek

tı́pusa. Ezt jelöli a #T a deklarációkban A függvénydeklarációkban a függvény neve után közvetlenül a visszatérési érték tı́pusa szerepel, utána pedig a függvény paramétereinek a tı́pusa. A következő kifejezés reprezentálja az a, b és c karakterekből álló karaktersorozatot: ’a’ .+ ( ’b’ + ( ’c’ + nil() ) ) Mivel a .+ operátor jobb asszociatı́v, a zárójel elhagyható: ’a’ .+ ’b’ + ’c’ + nil() A következő predikátum hasznos lesz, amikor az STL konténerek műveleteit speciﬁkáljuk: function( ’’split’’, Boolean, Seq(#T), Seq(#T), Seq(#T) ); Ez a predikátum kap paraméterként három elemsorozatot és egy logikai értéket ad vissza. Lényegében a split(a, b, c) kifejezés azt ı́rja le, hogy az a a b és c konkatenációja. Ezt a tulajdonságot a következő két axiómával fejezzük LaCert-ben: Az STL formális megközelı́tése 71 axiom

split1( Seq(#T) #seq, Seq(#T) #seqVal ) { #seq = #seqVal => split( #seq, nil(), #seqVal ); } axiom split2( Seq(#T) #seq, Seq(#T) #front, Seq(#T) #tail ) { split( #seq, #front, #elem .+ #tail ) => split( #seq, #front +. #elem, #tail ); } A split1 axiómának két formális paramétere van: #seq és #seqV al, mindkettő tı́pusa Seq(#T ). Ezekkel az axiómákkal tudjuk például a következőt bizonyı́tani: s = ’a’ .+ ’b’ + ’c’ + nil() => split( s, nil() +. ’a’, ’b’ + ’c’ + nil() ) { split1( s, ’a’ .+ ’b’ + ’c’ + nil() ); split2( s, nil(), ’a’ .+ ’b’ + ’c’ + nil() ); } A felső két sorban található a bizonyı́tandó állı́tás, a kapcsos zárójelben a bizonyı́tás. Ez a fajta érvelés szükséges, amikor az STL adatszerkezeteit használó programok tulajdonságait bizonyı́tjuk, ezért készı́tünk egy taktikát, hogy kiegészı́tse a bizonyı́tást automatikusan. Így elég

ennyit ı́rni, hogy a rendszer bebizonyı́tsa: s = ’a’ .+ ’b’ + ’c’ + nil() => split( s, nil() +. ’a’, ’b’ + ’c’ + nil() ); Bevezetem a values függvényt, amely egy konténer elemeit adja meg. Ha például v egy V ector(Character), akkor a values( v ) = nil() leı́rja, hogy v üres. LaCert-ben van explicit információnk a program végrehajtásának aktuális pillanatáról Ezt az információt az ip azonosı́tójú predeﬁnit változó tartalmazza. Például, ha az L-lel cı́mkézett állapotban a v vector üres, akkor a következőt speciﬁkálhatjuk: ip = L & values( v ) = nil() Ha két ilyen állı́tást összekötünk az >> operátorral, akkor temporális haladási tulajdonságokhoz [52] juthatunk: 72 Az STL formális megközelı́tése ip = K >> ip = L & values( v ) = nil() Ez a haladási tulajdonság leı́rja, hogy bármikor, amikor a program végrehajtása eléri a K

cı́mkét, akkor a programnak el kell érnie az L-lel jelölt cı́mkét és akkor a vector-nak üresnek kell lennie. Ha le szeretnénk ı́rni, hogy ezen haladás alatt egy másik w azonosı́tójú vector megőrzi az egyetlen elemét (a 2-es értéket), akkor egy biztonságossági tulajdonságot [10] használhatunk a haladási tulajdonság előtt: [ values( w ) = 2 .+ nil() ]; ip = K >> ip = L & values( v ) = nil() Ha azt szeretnénk kifejezni, hogy a programnak ez a része csak az ip és a v változókat módosı́tja, akkor leı́rhatjuk, hogy minden formula, amely nem tartalmazza az ip-t és v-t, egy biztonságossági tulajdonság: independent( $prop, ip ) & independent( $prop, v ) : [ $prop ]; ip = K >> ip = L & values( v ) = nil() Amikor a LaCert fordı́tónak el kell döntenie, hogy egy values(w) = 2. + nil() jellegű kifejezés egy biztonsági tulajdonság-e, akkor lecseréli $prop kifejezés változót egy

kifejezésre és feltételként kiértékeli. Mivel a values(w) = 2. + nil() formula független ip-től és v-től, ezért kielégı́ti a feltételt Most speciﬁkáljuk a vector clear() tagfüggvényét: atom clear( Vector(#T) #vect, Label #before, Label #after ) { independent( $prop, ip ) & independent( $prop, #vect ) : [ $prop ]; ip = #before >> ip = #after & values( #vect ) = nil(); } Az axiom kulcsszóval klasszikus logika eszközeivel deﬁniált axiómák deﬁniálhatók, az atom kulcsszóval temporális tulajdonságokat deﬁniálhatunk. A split függvényünk segı́tségével könnyen speciﬁkálhatjuk a push back műveletet. A #val értéket szeretnénk a konténer végéhez adni és #vV al az a sorozat, amit a vector korábban tartalmazott. Ekkor a haladási tulajdonság a következő: ip = #before & split( values(#vect), #vVal, nil() ) >> ip = #after & split( values(#vect), #vVal, #val .+ nil()

); Az STL formális megközelı́tése 73 Ha felcseréljük az elő- és utófeltételt, akkor a pop back művelet haladási tulajdonságának speciﬁkációját kapjuk: ip = #before & split( values(#vect), #vVal, #val .+ nil() ) >> ip = #after & split( values(#vect), #vVal, nil() ); Ez a speciﬁkáció megakadályozza, hogy üres konténeren alkalmazzuk a pop back függvényt: az előfeltétel igényli, hogy egy elem (#val) már a konténer végén legyen. Ha values(#vect) = nil() tulajdonság teljesül, az előfeltétel nem bizonyı́tható. Az iterátorok leı́rásához a split-hez új paramétert adunk: egy iterátort. Az első paraméteren is változtatunk: a vector értékei helyett magát a vector objektumot ı́rjuk. A következő predikátum leı́rja, hogy ha konkatenáljuk a f ront-ot és tail-t, akkor megkapjuk a vect vector, és ha tail nem üres, az iter iterátor a tail első elemére

hivatkozik elemeit, ha tail nil(), akkor az iter a vect.end() extremális iterátorral egyezik meg: split( vect, iter, front, tail ). Ennek segı́tségével egy iterátor inkrementálása a következőképpen ı́rható le: ip = #before & split( #vect, #iter, #front, #elem .+ #tail ) >> ip = #after & split( #vect, #iter, #front +. #elem, #tail ); A speciﬁkáció utófeltételében az #elem-et a #f ront végéhez konkatenáltuk, ı́gy a bővı́tett split jelentése alapján #iter a #tail első elemére hivatkozik, ami az #elem utáni következő elem. Egy iterátor dekrementálása hasonlóan ı́rható le. Most a konténer egy elemének iterátoron keresztüli megváltoztatását ı́rjuk le (a #val az értékül adandó érték): ip = #before & split( #vect, #iter, #front, #elem .+ #tail ) >> ip = #after & split( #vect, #iter, #front, #val .+ #tail ); Általában nagy szoftverrendszerekben nem

szükséges minden kódrészletet formális eszközzel bizonyı́tani, de lehetnek biztonság-kritikus részletek. Ha a formális módszer költsége nem túl magas, akkor megéri ezeket a kódrészeket bizonyı́tott tulajdonságokkal ellátni. Sajnos mindig vannak nem túl bonyolult részek, amelyeket egy szoftver nem tud automatikusan bizonyı́tani. A mi megközelı́tésünk az, hogy ezeket a részleteket általánosı́tani kell 74 Az STL formális megközelı́tése és sablonokba helyezni. A sablonok és a taktikák segı́tségével a formális programfejlesztési költségeket nagymértékben lehet csökkenteni és a LaCert rendszer használatához szükséges erőforrások elfogadhatóvá válnak. III.3 Összegzés Ebben a fejezetben az STL formális speciﬁkációs lehetőségeivel foglalkoztam. Az STL speciﬁkációja informális, ami nem szerencsés: nehezen kezelhető a programhelyesség

vizsgálata, valamint félreértésekre adhat okot. Kétféle formális eszközt mutattam be az STL speciﬁkációjához: az első az általam kidolgozott technika, amely elő- és utófeltételek segı́tségével deﬁniálja az STL-t. A technika a számı́tástudomány mai napig népszerű Hoare módszerén alapul, felhasználható STL-t használó programok, könyvtárak, valamint STL implementációk helyességének vizsgálatához. A technikát példákkal illusztrálva mutattam be A másik technika LaCert nyelven ı́rt temporális logikai eszközöket használó speciﬁkáció Ennek alapvető célja, hogy speciﬁkációkból a LaCert fordı́tóprogram generálja az STL alapú C++ kódokat kritikus pontokon. Ezen speciﬁkáció elkészı́tésében részt vettem, de Dévai Gergely munkájának tartom. Ezek a formális eszközök csak körülményesen használatóak nagyobb kódok esetén. A

továbbiakban olyan általam kidolgozott szoftveres eszközöket mutatok be, amelyekkel ugyan helyesség nem garantálható, de az STL-lel elkövethető hibák bizonyos részei detektálhatóak. 1. Tézis Eszközrendszert dolgoztam ki, amely alkalmas generikus programok formális speciﬁkációjára Az eszközrendszer alkalmasságát a C++ Standard Template Library alapvető komponenseinek formális speciﬁkálásával mutattam meg. A módszer segı́tségével pontosabbá tehető a könyvtár deﬁnı́ciója és kisebb méretek esetén a program-helyességi vizsgálatokban is felhasználható. A tézishez kapcsolódó publikációim: [21, 22, 61, 64, 72, 77]. IV. fejezet Fordı́tás idejű megoldások IV.1 Warning-ok generálása A fordı́tóprogramok megkülönböztetnek fordı́tási hibákat (errors) és fordı́tási ﬁgyelmeztetéseket (warnings) a forráskód elemzése során. Fordı́tási hibát

akkor kapunk, amikor a fordı́tandó kódban olyan hiba van, amely miatt nem lehet a kódot lefordı́tani, mert megsérti a nyelv szintaktikus és/vagy szemantikai szabályait. Ha a kód ugyan betartja a szabályokat, de olyan tı́pusú hiba van a kódban, ami futás közben problémát okozhat, akkor a fordı́tóprogramok ﬁgyelmeztetéseket adhatnak. Ez nem jelenti azt, hogy a program feltétlenül hibásan fog működni. A C++ más nyelvekhez képest sokkal több konstrukciót enged ﬁgyelmeztetésekkel lefordı́tani, ezért a programozók ténylegesen ﬁgyelnek a fordı́tóprogram üzeneteire [4]. Nézzük például az alábbi kódrészletet: std::vector<int> v; // . for( int i = 0; i < v.size(); ++i ) { // . } A fenti kódrészletre a legtöbb fordı́tóprogram ﬁgyelmeztetést ad, hogy egy előjeles egészet (i) hasonlı́tunk össze egy előjel nélkülivel (v.size()) Mivel a C++ nyelv szabályai szerint ekkor

az előjeles egész előjel nélkülivé konvertálódik, hibás viselkedéshez vezethet, amikor az előjel bit igaz, az az egy negatı́v szám az érték. A fenti kódrészletben az előjeles egész mindig nemnegatı́v, ı́gy nem okoz hibát futás közben. Ugyanezt a ﬁgyelmeztetést kapjuk az alábbi kódrészlet fordı́tásakor is: 75 76 Fordı́tás idejű megoldások int i = -5; unsigned int j = 2; if ( i < j ) { // . } Futás közben az elágazás feltétele hamisra értékelődik, ami elsőre furcsán hat. Eszerint a -5 nem kisebb, mint 2, de ez megint abból adódik, hogy az előjeles -5 érték ,,nagy” előjel nélkülivé konvertálódik a C++ konverziós szabálya miatt. A fordı́tóprogramok nem tudnak ﬁgyelmeztetéseket (warning-okat) adni az STL (vélhetően) szemantikusan hibás alkalmazásakor [93, 112]. Az én megoldásaim a könyvtár minimális megváltoztatásával képesek

,,tetszőleges” ﬁgyelmeztetés jelzésére bármelyik szabványos fordı́tóprogram esetén annak módosı́tása nélkül. Így megoldásaim könnyedén átvihetőek bármelyik platformra Ráadásul a hibalehetőségek ismerete a könyvtárak feladata A fordı́tóprogramok nem ismerhetik az összes generikus programozási könyvtárat Egy másik megközelı́tés ami használható a könyvtárak ezirányú problémáira a nyelvi bővı́tésekkel operáló bővı́thető fordı́tóprogramok [112]. A fordı́tási idejű megoldások egyik nagy előnye az, hogy a leforduló kódok futási ideje nem változik, ı́gy megmarad az STL hatékonysága és a speciﬁkációt továbbra is betartja a megváltozott implementáció. Az én megoldásom, hogy ﬁgyelmeztetéseket generálok A meglévő kód örökség (legacy kódok) miatt nem támogatom a fordı́tási hibákat, minden meglévő leforduló

kód továbbra is fordulni fog. Egyetlen kivétel a COAP, amiket a szabvány eleve tilt, mégis található fordı́tóprogram, amely engedi a használatukat. A C++11 bevezeti a static assert-et, amely konstrukció segı́tségével fordı́tási hibákat lehet kiadni valamilyen fordı́tási idejű feltétel teljesülése esetén. Sajnos nem terveztek hasonló funkcionalitást fordı́tási ﬁgyelmeztetésekhez, ezért ehhez saját eszközt alkalmazok Az alábbi kódrészlet a magja a fordı́tási üzenetek generálásának [63]: template <class T> inline void warning( T t ) { } A kódrészlet egy üres inline függvénysablon, mely egy tetszőleges tı́pusú paramétert fogad. A függvénysablon nem csinál semmit, a paraméterét sem használja, ez váltja ki a ﬁgyelmeztetést. A ﬁgyelmeztetés csak akkor jelenik meg, ha a sablont példányosı́tjuk, önmagában a sablon jelenléte a kódban nem okoz

ﬁgyelmeztetést. Abban Fordı́tás idejű megoldások 77 az esetben viszont, ha példányosı́tottuk a függvénysablont, ﬁgyelmeztetés generálódik, hogy az adott tı́pussal példányosı́tott sablon nem használja a paraméterét (unused parameter). A hibaüzenetben megjelenik a sablonparaméter tı́pus neve is A futási idő nem növekszik meg, warning generálása esetén sem, a fordı́tóprogram képes kioptimalizálni az üres függvénytörzset. Minden új fajta ﬁgyelmeztetéshez kell ı́rni egy új dummy tı́pust. Ennek a tı́pusnak az azonosı́tója jelenik meg a generált ﬁgyelmeztetésekben: struct DO NOT CALL FIND ALGORITHM ON SORTED CONTAINER { }; Amikor a warning sablont meghı́vjuk egy ilyen objektummal fordı́tási üzenetet kapunk: warning( DO NOT CALL FIND ALGORITHM ON SORTED CONTAINER() ); A különböző fordı́tóprogramok különböző módon jelzik ezt a ﬁgyelmeztetést. Például

a Microsoft Visual Studio fordı́tóprogramja az alábbi üzenetet adja: warning C4100: ’t’ : unreferenced formal parameter . see reference to function template instantiation ’void warning<DO NOT CALL FIND ALGORITHM ON SORTED CONTAINER>(T)’ being compiled with [ T=DO NOT CALL FIND ALGORITHM ON SORTED CONTAINER ] A g++ fordı́tóprogram az alábbi módon jelzi a lehetséges hibát: In instantiation of ’void warning(T) [with T = DO NOT CALL FIND ALGORITHM ON SORTED CONTAINER]’: . instantiated from here . warning: unused parameter ’t’ 78 Fordı́tás idejű megoldások Látható, hogy ennél a két fordı́tóprogramnál (melyek a legelterjedtebbek) a ﬁgyelmeztetés jól kiemeli a sablon paraméter nevét, ı́gy ez a megközelı́tés jól alkalmazató ﬁgyelmeztetések leı́rására. Ugyanakkor a warning-ok kezelése nem egységes, implementációjuk függhet fordı́tóprogramtól. Viszont, minden

fordı́tóprogramnál testreszabható ez a megoldás. A fordı́tóprogramok nem tudják speciﬁkusan az általam generált ﬁgyelmeztetéseket letiltani (például valamilyen compiler kapcsolóval). Mivel fordı́tási időben általában csak potenciális hibákat tudunk jelezni, futási időben nem feltétlenül észlelünk problémát. Például a másoló algoritmusok inserter iterátorok nélkül is probléma nélkül másolhatnak, ha van elegendő felülı́randó elem. Ahhoz, hogy a programozók ilyen esetben letilthassák az általam generált ﬁgyelmeztetéseket believe-me mark -okat [50] használok. A believeme mark-ok olyan annotációk, amelyek nem eredményeznek futás idejű aktivitást, csak az általam generált speciﬁkus warning-ok letiltására terveztett kódrészletek. Így az üzenet láttán végiggondolva a programozóknak esélye van átalakı́tani a kódot vagy egy believe-me mark

annotációval megkérni a fordı́tóprogramot, hogy most higgye el, hogy az adott kódrészlet helyes, nem fog problémát okozni futási időben. Csak azoknál az eseteknél biztosı́tok ilyen annotációkat, ahol lehetséges, hogy nem jelentkezik hiba futás közben és a programozó láthatja, hogy miért nem lesz gond. Generált warning-okat más célokkal is használtunk kutatásaim során. Metaprogramok vizualizációjánál sikeresen használtunk sablonok példányosı́tásának felderı́tésére [8]. A C++11 újı́tásait kihasználva szűrhető ﬁgyelmeztető annotációkat dolgoztam ki, melyekkel a programozó különböző szinteken jelezheti a programkódban még meglévő hiányosságokat, problémákat [82]. IV.2 Hibás példányosı́tások Az STL generikus megközelı́téséből adódóan olyan példányosı́tást is végre tud hajthatani a fordı́tóprogram, amely szemantikus

problémákba ütközhet a későbbiek során. Ennek két tipikus példája ismert: a vector<bool> tı́pus, amely a C++ szabványa szerint nem is konténer, és az auto ptr-eket tároló konténerek(COAP-ok), amit a C++ szabványa tilt. IV.21 A vector<bool> konténer A vector<bool> konténer egy olyan specializációja a vector sablonnak, amely bool-ok hatékony tárolására terveztek: nem bool-okat tárol, hanem számok bitjei reprezentálják a konténert. Így nem tudták teljesen megfeleltetni a vector sablon interface-ének megfeleltetni a vector<bool>-t és emi- Fordı́tás idejű megoldások 79 att nem tudja teljesı́teni a C++ szabvány elvárását (II.410) Használata nem javasolt [53]. Az én megoldásom a warning függvénysablon segı́tségével fordı́tási ﬁgyelmeztetéseket generál, ha valaki példányosı́tja a vector<bool>-t [67]. Szerencsére a vector<bool>

továbbra is sablon, mert az allokátor tı́pusa sablonparaméter továbbra is Így a fordı́tási ﬁgyelmeztetés csak akkor generálódik, ha valaki példányosı́tja, azaz használja a vector<bool>-t. A konténer összes konstruktorában meghı́vjuk a warning sablont. Ezt mutatja be a következő kódrészlet: template<class Allocator> class vector<bool, Allocator> { // . public: vector() { warning( VECTOR BOOL IS IN USE() ); // . } template<class InputIterator> vector( InputIterator first, InputIterator last ) { warning( VECTOR BOOL IS IN USE() ); // . } vector( size t n, const bool& value = bool() ) { warning( VECTOR BOOL IS IN USE() ); // . } vector( const vector& rhs ) { warning( VECTOR BOOL IS IN USE() ); // . } }; 80 Fordı́tás idejű megoldások Az eddigi megoldás nem támogatja a believe-me mark-ok bevezetését. Most átalakı́tom az eddigi megoldást, hogy believe-me mark-ok segı́tségével

letiltható legyen a warning generálása. Ehhez először elkészı́tem a belive-me markot jelentő tı́pust: struct I KNOW VECTOR BOOL { }; Most a vector sablon konténert kibővı́tem egy plusz sablon paraméterrel, melyhez default paraméter értéket rendelek, ı́gy a megoldás reverse-kompatibilis marad az szabványos STL-lel. Ezt a paramétert az implementáció nem használja, nincs hatása a konténerre: template <class T, class Alloc = std::allocator<T>, class Info = int> class vector { }; Most az eredeti vector<bool> megvalósı́tását egy új sablon tı́pusba helyezem át. Ez az a verzió, amely még nem vált ki ﬁgyelmeztetést példányosı́táskor: template <class Alloc> class VectorBool { // a vector<bool> eredeti implementációja }; Az új sablon paraméternek a vector<bool> specializációnál van hatása: template <class Alloc> class vector<bool, I KNOW VECTOR BOOL,

Alloc>: public VectorBool<Alloc> { }; template <class Alloc> class vector<bool, Alloc, I KNOW VECTOR BOOL>: public VectorBool<Alloc> { }; template <class Alloc, class Info> class vector<bool, Alloc, Info>: public VectorBool<Alloc> { Fordı́tás idejű megoldások 81 public: vector(): VectorBool<Alloc>() { warning( VECTOR BOOL IS IN USE() ); } template<class InputIterator> vector( InputIterator first, InputIterator last ): VectorBool<Alloc>( first, last ) { warning( VECTOR BOOL IS IN USE() ); } vector( size t n, const bool& value = bool() ): VectorBool<Alloc>( n, value ) { warning( VECTOR BOOL IS IN USE() ); } vector( const vector& rhs): VectorBool<Alloc>( rhs ) { warning( VECTOR BOOL IS IN USE() ); } }; Abban az esetben nem kap a programozó ﬁgyelmeztetést a fordı́tóprogramtól, ha az I KNOW VECTOR BOOL tı́pust átadja a vector példányosı́tásakor utolsó

extra sablonparaméterként. IV.22 COAP Az auto ptr-eket tároló konténereket (Containers of auto pointers, COAP) tiltja a C++ Szabványa, mert a könyvtáron belüli másolások következtében a tárolókban nullpointer-ré változhatnának az auto ptr-ek (II.411) Az én megoldásomban COAP használatakor fordı́tási hibaüzenetet generálok és a kód nem fordul le. Ehhez a konténereket parciálisan specializáljuk auto ptr-ekre. A trükk az, hogy nem ı́rok implementációt a specializációkhoz, ı́gy létrehozva deklarált, de nem deﬁniált tı́pusokat Példaképpen a vector specializáció deklarációja következőképpen néz ki: template <class T, class Alloc> class vector< std::auto ptr<T>, Alloc>; 82 Fordı́tás idejű megoldások Egy COAP példányosı́tásakor az alábbi hibaüzenetet kapjuk: error: aggregate ’std::vector<std::auto ptr<int>, std::allocator<std::auto

ptr<int> > > v’ has incomplete type and cannot be defined Ezeket a deklarációkat meg kell ı́rni az összes szabványos konténerhez. A deklarációk segı́tségével a C++ kódjaink hordozhatóbbak és egy hibalehetőséget kizártam. IV.3 Algoritmusok IV.31 Az iterator traits kibővı́tése Az algoritmusok biztonságosabbá tételéhez először kibővı́tjük új attribútumokkal az iterator traits tı́pust. Ezen kibővı́tett iterator traits tı́pus segı́tségével az algoritmusokat túl lehet terhelni, és a problémás esetekben fordı́tási ﬁgyelmeztetéseket generálok [76]. Először két új dummy tı́pust készı́tek, amivel a konténerek rendezettségét lehet leı́rni: class sorted tag {}; class unsorted tag {}; Másik két dummy tı́pus az iterátorok másolási stratégiáját deﬁniálja: class inserting iterator tag {}; class non inserting iterator tag {}; Írok két

új tı́pust, amivel a konténerek azon tulajdonságát ı́rom le, hogy van-e unique nevű tagfüggvénye. class uniqable tag {}; class non uniqable tag {}; Az alapértelmezett iterator traits a következőképpen deﬁniálható: template <class T> struct iterator traits { typedef typename T::iterator category iterator category; typedef typename T::value type value type; typedef typename T::difference type difference type; Fordı́tás idejű megoldások typedef typedef typedef typedef typedef }; typename T::pointer typename T::reference unsorted tag non inserting iterator tag non uniqable tag 83 pointer; reference; sortedness; inserter; uniqability; Három új iterátor jellemzőt adtunk az iterator traits sablonhoz: a rendezettségi attribútumot, másolási stratégia attibútumát inserter néven, és a uniqability azonosı́tójú attribútumot, ami deﬁniálja, hogy használható-e a unique algoritmusnál jobb

megoldás a feladatra. Ezek az attribútumok mindegyike egy tı́pus alias: a sortedness egy álneve a sorted tag vagy az unsorted tag tı́pusnak. Az inserter vagy a non inserting iterator tag vagy a inserting iterator tag álneve. Hasonlóképpen, a uniqable tag a non uniqable tag és unsorted tag valamelyike. A három attribútum default ,,értéke”: unsorted tag, non inserting iterator tag és a non uniqable tag. Ezt úgy lehet interpretálni, hogy általában egy iterátor rendezetlen intervallumot jár be, nem tud beszúrni új elemet az intervallumba, csak felülı́rni, illetve nem támogat jobb megoldást a unique algoritmusnál. Egy hasonló megoldást a futás idejű eszközöknél is használok (V.1) Ezeket az új jellemzőket a specializációkban is be kell állı́tani. Az aszszociatı́v konténerek esetében az a sortedness jellemzőt sorted tag-ként kell deﬁniálni. Az inserter adaptor-oknál illetve a ostream iterator

tı́pus esetén az inserter-nek megfelelő tı́pus legyen az inserting iterator tag. A list iterátoránál a uniqability tag legyen a uniqable tag álneve. Ezt könnyedén be lehet állı́tani, ha ezzel a három attribútummal kibővı́tjük az iterator bázis tı́pust, amit kifejezetten a trait-ek kényelmes beállı́tására terveztek. Ezekkel az új attribútumokkal fordı́tási időben ellenőrizni tudunk bizonyos feltételeket. A következő fejezetekben bemutatom, hogyan alkalmazom ezeket az STL biztonságosabbá tételéhez. IV.32 Másoló algoritmusok Az STL-nek számos olyan algoritmusa van, ami elemeket másol: transform, copy, replace copy if, stb. Ezek az algoritmusok felteszik, hogy nem kell már tárterületet allokálniuk, csak a már lefoglalt egymás utáni helyekre bemásolni az objektumokat. Számos olyan helyzet adódhat, hogy az algoritmus nem tud hova másolni, de ezt nem veszi észre és a

fordı́tóprogram sem ad jelzést ezzel a hibalehetőséggel kapcsolatban. Az ilyen programnak 84 Fordı́tás idejű megoldások nemdeﬁniált az eredménye (II.45) Az én megoldásomban a fordı́tóprogram eldönti az output iterátorról, hogy garantálható-e, hogy a másolások sikeresek lesznek. Ha ez nem teljesül, akkor a fordı́tóprogam ﬁgyelmeztetést ad a programozónak a lehetséges hibáról. Most a copy és transform algoritmusokon mutatom be az általam kidolgozott technikát, amely az imént bemutatott, kibővı́tett iterator traitsen alapul. A többi másoló algoritmus hasonlóan tehető biztonságosabbá Ehhez először a szabványos algoritmusokat ı́rjuk meg. Ezek annyit csinálnak, hogy az eredmény iterátor tı́pusa alapján eldöntik, hogy okozhat-e problémát az algoritmus meghı́vása: template <class InputIt, class OutputIt> inline OutputIt copy( InputIt first, InputIt last, OutputIt

result ) { return copy( first, last, result, typename iterator traits<OutputIt>::inserter() ); } template <class InputIterator, class OutputIterator, class Fun> inline OutputIterator transform( InputIterator first, InputIterator last, OutputIterator result, Fun f ) { return transform( first, last, result, f, typename iterator traits<OutputIterator>:: inserter() ); Fordı́tás idejű megoldások 85 } Elkészı́tem a megszokott implementációját ennek a két algoritmusnak, amely nem generál fordı́tási ﬁgyelmeztetést. Ha az output iterátor inserterjellegű, akkor ezeket a verziókat hı́vják meg az előző kódok: template <class InputIterator, class OutputIterator> OutputIterator copy( InputIterator first, InputIterator last, OutputIterator result, inserting iterator tag ) { while( first != last ) { *result++ = first++; } return result; } template <class InputIterator, class OutputIterator, class Fun> OutputIterator

transform( InputIterator first, InputIterator last, OutputIterator result, Fun f, inserting iterator tag ) { while( first != last ) { *result++ = f(first++); } return result; } Végül elkészı́tjük azt a verziót, amikor olyan output iterátorokkal dolgozik az algoritmus, ami nem biztos, hogy tud új elemeket az output-ba szúrni. Itt a korábban ismertett warning függvénysablon segı́tségével ﬁgyelmeztetéseket generálunk: template <class InputIterator, 86 Fordı́tás idejű megoldások class OutputIterator> OutputIterator copy( InputIterator first, InputIterator last, OutputIterator result, non inserting iterator tag ) { warning( COPY ALGORITHM WITHOUT INSERTER ITERATOR() ); return copy( first, last, result, inserting iterator tag() ); } template <class InputIterator, class OutputIterator, class Fun> OutputIterator transform( InputIterator first, InputIterator last, OutputIterator result, Fun f, non inserting iterator tag ) {

warning( TRANSFORM ALGORITHM WITHOUT INSERTER ITERATOR() ); return copy( first, last, result, f, inserting iterator tag() ); } A trait-en alkalmazott túlterhelési technika nem ismeretlen az STL-ben. Hasonlóképpen az advance és distance algoritmus túl van terhelve az iterátorok kategóriájának dummy tı́pusán, hogy kihasználhassa a közvetlen elérést random access kategóriájú iterátorok esetén (II.3) Fordı́tás idejű megoldások IV.33 87 A count és a find algoritmus A count és a find algoritmus a legegyszerűbb algoritmusok közé tartoznak. A count megadja, hogy egy érték hányszor szerepel az input intervallumban, a find pedig a legelső találatnál megáll és visszaad egy iterátort a keresett elemre. Ha nincs találat, akkor visszaadja a második paraméterét, ami az intervallum végét jelzi. Deklarációja a szabvány szerint: template <class Iterator, class T> Iterator find( Iterator

first, Iterator last, const T& t ); A fordı́tási ﬁgyelmeztetésekhez először elkészı́tem a dummy tı́pusokat: struct DO NOT CALL FIND ALGORITHM ON SORTED CONTAINER { }; struct DO NOT CALL COUNT ALGORITHM ON SORTED CONTAINER { }; Az én megoldásom eldönti, hogy a find rendezett input-on hı́vták-e meg, mert ebben az esetben adható hatékonyabb megoldás a lineáris futásidejű megoldásnál. Ennek nem csak hatékonysági, hanem biztonsági oka is van: az asszociatı́v konténerek enkapszulálják a használt rendezést, és annak megfelelően tudnak keresni, mı́g ebben az esetben ez hiba forrása lehet. Ehhez elkészı́tem a find olyan változatait, amelyek eggyel több paramétert vár. Ez a paraméter egy default konstruált objektum mely sorted tag vagy unsorted tag tı́pusú, a kibővı́tett iterator traits-től függően: template <class Iterator, class T> inline Iterator find( Iterator first, Iterator last,

const T& t ) { return find( first, last, t, typename iterator traits<Iterator>::sortedness() ); } Most túlterhelem a find sablont a negyedik paraméterének tı́pusa alapján. Ehhez először megı́rom a find ,,szokásos” változatát a rendezetlen intervallumokhoz: 88 Fordı́tás idejű megoldások template <class Iterator, class T> Iterator find( Iterator first, Iterator last, const T& t, unsorted tag ) { for ( ; first != last; ++first ) { if ( *first == t ) { return first; } } return last; } Végül megı́rom a rendezett intervallumokhoz készült változatot. Ez kiváltja a fordı́tási ﬁgyelmeztetést majd meghı́vja az előző verziót: template <class Iterator, class T> Iterator find( Iterator first, Iterator last, const T& t, sorted tag ) { warning( DO NOT CALL FIND ALGORITHM ON SORTED CONTAINER() ); return find( first, last, t, unsorted tag() ); } A count-ra is érvényes az, hogy rendezett

intervallumon jobb, ha nem az algoritmust alkalmazzuk, ezért a find-hoz hasonlóan implementálom a count algoritmust is: template <class Iterator, class T> inline typename iterator traits<Iterator>::difference type Fordı́tás idejű megoldások count( Iterator first, Iterator last, const T& t ) { return count( first, last, t, typename iterator traits<Iterator>::sortedness() ); } template <class Iterator, class T> typename iterator traits<Iterator>::difference type count( Iterator first, Iterator last, const T& t, unsorted tag ) { typename iterator traits<Iterator>::difference type i = 0; for ( ; first != last; ++first ) { if ( *first == t ) { ++i; } } return i; } template <class Iterator, class T> typename iterator traits<Iterator>::difference type count( Iterator first, Iterator last, const T& t, sorted tag ) { warning( DO NOT CALL COUNT ALGORITHM ON SORTED CONTAINER() ); return count( first, last, t, 89

90 Fordı́tás idejű megoldások unsorted tag() ); } Ezekhez az esetekhez nem készı́tek ,,believe-me” jeleket, mert mindig van alternatı́va, ami hatékonyabb a feladat ellátására, nincs értelme letiltatni ezeket a ﬁgyelmeztetéseket. IV.34 A unique algoritmus A unique algoritmus könnyedén félreérthető: feladata, hogy eltávolı́tsa az input intervallumból a duplikátumokat. Valójában, csak az egymás mellett álló duplikátumokból hagy meg egyet. Az input-ban nem egymás mellett lévő azonos értékek továbbra is megmaradnak. Mivel a unique egy algoritmus, nem tud elemet törölni az input-ból: a megmaradó elemeket az input elejére másolja. Bizonyos konténereknek (mint például a list) van unique nevű tagfüggvénye, ami már hatékonyan azonnal ki is tudja törölni a duplikátumokat a konténerből. Először néhány segéd komponenst készı́tek: warning generálásához

használt dummy tı́pusokat, illetve egy check uniqability függvénysablont, mely generálja a warning-ot, ha az iterátor olyan konténerhez tartozik, amelynél jobb megoldás lenne, ha unique metódust használata, mint a unique algoritmus. Más esetben nem történik semmi: struct USE UNIQUE METHOD INSTEAD OF ALGORITHM { }; struct UNIQUE ALGORITHM MAY CAUSE ERROUNEOUS RESULT { }; template <class It> inline void check uniqability( It t ) { check uniqability( t, typename iterator traits<It>::uniqability() ); } template<class It> inline void check uniqability( It, non uniqable tag ) { } template<class It> inline void check uniqability( It, uniqable tag ) { Fordı́tás idejű megoldások 91 warning( USE UNIQUE METHOD INSTEAD OF ALGORITHM() ); } Most elkészı́tem a unique algoritmus szabványhoz illeszkedő verzióját. Ez ﬁgyelmeztetést vált ki, hogy jelezze, hogy az eredménye nem intuitı́v. Ellenőrzi az

iterátor tı́pusát is az előző sablonok segı́tségével. Meghı́vja az algoritmus eredeti implementációját, amely nem eredményez ﬁgyelmeztetést: ennek a neve unique without warning. template <class FwdIt> FwdIt unique( FwdIt first, FwdIt last ) { WARNING( UNIQUE ALGORITHM MAY CAUSE ERROUNEOUS RESULT() ); check uniqability( first ); return unique without warning( first, last ); } template <class It> It unique without warning( It first, It last ) { first = adjacent find( first, last ); if ( first == last ) { return last; } It dest = first; ++first; while( ++first != last ) { if ( !( *first == dest ) ) { *++dest = first; } } return ++dest; } Új implementációkat dolgozok ki unique algoritmushoz. A felhasználó választhat ezek közül mark-ok segı́tségével. Ehhez újabb dummy osztályokat készı́tek: 92 Fordı́tás idejű megoldások class with sort {}; class without sort {}; class default unique is needed

{}; Ha egy default unique is needed tı́pusú objektumot kap a unique, akkor nem váltok ki ﬁgyelmeztetést és az eredeti implementációt hı́vom meg. Ugyanakkor, ha speciﬁkusan olyan konténeren hı́vjuk meg, amelynek van unique tagfüggvénye, akkor kapunk ﬁgyelmeztetést a fordı́tóprogramtól. Később believe-me mark-ot készı́tek ehhez az esethez: template <class FwdIt> FwdIt unique( FwdIt first, FwdIt last ) { check uniqability( first ); return unique without warning( first, last ); } Ha a felhasználó with sort tı́pusú objektumot speciﬁkál, akkor az algoritmus rendezéssel garantálja, hogy a duplikátumok egymás mellé kerüljenek. Ekkor két különböző megközelı́tés lehetséges az iterátor kategóriájától függően. Az első, ha véletlen elérésű iterátorokkal dolgozik az algoritmus Ebben az esetben a sort algoritmus meghı́vható és rendezi az elemeket a unique meghı́vása

előtt. Ebben az esetben feleslegesnek tűnhet az iterátor vizsgálata, hiszen a list konténernek nincs random-access kategóriájú iterátora. Ugyanakkor, új, nem-szabványos STL-jellegű konténerek támogathatják egyszerre a unique tagfüggvényt és közvetlen elérésű iterátorokat. Ezért szükséges az ellenőrzés. A második megközelı́tés, ha nem véletlen elérésű iterátorokat kap az algoritmus. Ehhez az iterátor kategóriáján terheljük túl az algoritmust Mindegyik verzióban ellenőrzöm, hogy a unique tagfüggvény használható-e. template <class Iterator> Iterator unique( Iterator first, Iterator last, with sort s ) { check uniqability( first ); return unique( first, last, s, typename Fordı́tás idejű megoldások 93 iterator traits<Iterator> ::iterator category() ); } template <class Iterator> Iterator unique( Iterator first, Iterator last, with sort, random access

iterator tag ) { std::sort( first, last ); return unique without warning( first, last ); } template <class Iterator> Iterator unique( Iterator first, Iterator last, with sort, bidirectional iterator tag ) { set < typename iterator traits<Iterator>::value type > unique elements( first, last ); return copy( unique elements.begin(), unique elements.end(), first ); } A unique copy implementációja hasonló, de a másolás eredményét a copy vagy a transform algoritmushoz hasonlóan kell kezelni. 94 IV.4 Fordı́tás idejű megoldások Adaptálható funktorok Az adaptálható funktorok azok a funktorok, amelyekre az átalakı́tókat lehet alkalmazni. A könyvtárban négy szabványos funktoradapter található ( not1, not2, bind1st, bind2nd), de ezeken kı́vül nemszabványosak is találhatóak az implementációkban. Az adaptálhatósághoz néhány typedef szükséges, amelyeket a unary function, illetve a binary

function bázisosztályok segı́tségével adhatunk meg a legegyszerűbben. Ezek bázisok sablonok, csak példányosı́tva lehet felhasználni bázistı́pusként. A sablon paramétereket a funktor tı́pus operator()-ának paraméterei határozzák meg. A hibát az okozza, hogy ı́gy kód duplikátumok kerülnek a funktorok megvalósı́tásába: a bázistı́pus sablon paramétereit kézzel adjuk meg, nem adódik automatikusan a funktor megı́rása alapján. Ha valamilyen oknál fogva (pl a kód megváltozásából adódóan) ez a duplikátum inkonzisztenssé válik, akkor ez kihathat a futási időre (II.43) Az én megoldásom alapötlete az, hogy a C++ sablonjainak segı́tségével megvizsgálom, hogy a funktor operator()-ának paraméterei megfelelnek-e a bázistı́pusnak [63]. Ha ezek a tı́pusok nem felelnek meg egymásnak, akkor egy fordı́tási ﬁgyelmeztetést generálok a már ismertett technika alapján.

Ehhez az alábbiakat fogom felhasználni: class IMPROPER FUNCTION BASE { }; template<bool b, class Fun> struct WARNING { WARNING() { warning( IMPROPER FUNCTOR BASE() ); } }; template <class Fun> struct WARNING<true, Fun> { }; Az unáris adaptálható funktorok esetében az alábbi kódrészlet dönti el, hogy az operator() paraméterei megfelelnek-e a bázistı́puson keresztül beállı́tott typedef-eknek: Fordı́tás idejű megoldások 95 template <class Fun> class check unary adaptability { typedef BOOST TYPEOF(&Fun::operator()) f type; typedef typename boost::mpl::at c< boost::function types::parameter types<f type>, 1>::type arg type; WARNING< boost::is same< typename boost::remove const< typename boost::remove reference<arg type>::type>::type, typename Fun::argument type>::value, Fun > w; }; #define CHECK UNARY FUNCTOR(F) check unary adaptability<F>(); Hasonló módon

ellenőrizhető a bináris funktorok adaptálhatósága: template <class Fun> class check binary adaptability { typedef BOOST TYPEOF(&Fun::operator()) f type; typedef typename boost::mpl::at c< boost::function types::parameter types<f type>, 1>::type arg1 type; typedef typename boost::mpl::at c< boost::function types::parameter types<f type>, 2>::type arg2 type; WARNING< boost::is same< typename boost::remove const< typename boost::remove reference<arg1 type>::type>::type, typename Fun::first argument type>::value, Fun > w1; WARNING< boost::is same< 96 Fordı́tás idejű megoldások typename boost::remove const< typename boost::remove reference<arg2 type>::type>::type, typename Fun::second argument type>::value, Fun > w2; }; #define CHECK BINARY FUNCTOR(F) check binary adaptability<F>(); Itt a megoldásban a Boost MPL könyvtárát használom, amely hatékony

segı́tséget nyújt metaprogramozási problémák megoldásában [47]. IV.5 Allokátorok Az allokátorok esetében fontos garantálni, hogy azonos tı́pusú allokátorok egyenlőek legyenek, azaz nem lehet állapotuk. Az allokátoroknak nem lehet nem statikus tagjuk, valamint csak triviális konstruktoruk és destruktoruk lehet. Az STL implementációk kihasználják ezt a tulajdonságát az allokátoroknak A fordı́tóprogramok viszont nem ellenőrzik ezt a tulajdonságot, és futás közben sem jelzik a hibát. Az ilyen allokátorok tönkretehetik az adatszerkezeteket (II.44) Ehhez egy hasonló megoldást adok, mint a funktorok esetében: class ALLOCATOR WITH STATE { }; template<bool b, class Allocator> struct WARNING { WARNING() { warning( ALLOCATOR WITH STATE() ); } }; template <class Fun> struct WARNING<true, Fun> { }; Most készı́tek az allokátor tı́pus fölé egy olyan burkoló (wrapper) osztályt,

ami trigger-eli a fordı́tás idejű ellenőrzést. Mivel ez származik az allokátorból, Fordı́tás idejű megoldások 97 minden publikus művelet ugyanúgy elérhető, mint az eredeti allokátor esetén. Az ellenőrzést megint a Boost type traits library segı́tségével végzem el, ahol egy tı́pus stateless-ségének lekérdezése már implementálva van [47]: template <class Alloc> class Stateless: public Alloc { WARNING< boost::is stateless<Alloc>::value, Alloc > ; }; Ezenkı́vül annyit kell változtatni az STL kódokon, hogy a konténerekben, ahol allokátor adattagot deﬁniálnak, annak tı́pusát, Stateless sablonnal kell használni, például az alábbi módon: template <class T, class Alloc = allocator<T> > class list { Stateless<Alloc> allocator; // . }; Ha egy felhasználói allokátor megsérti a szabályt, fordı́tási ﬁgyelmeztetést kap a programozó, hogy

hibás lehet az allokátor használata. A hibaüzenetben látható az allokátor tı́pusa és a ALLOCATOR WITH STATE azonosı́tó is. Ehhez a megoldáshoz nem biztosı́tok believe-me mark-ot, hiszen állapottal rendelkező allokátor nem használata nem ésszerű a C++ 2003-as szabványa szerint. A C++11 jelentősen megváltoztatta az allokátorok és a konténerek kapcsolatát, és támogatottá váltak az állapottal rendelkező allokátorok is [42]. IV.6 Reverse iterátorok A konténerek bizonyos tagfüggvényei csak iterator tı́pusú iterátort várnak paraméterként, reverse iterator-t nem. A reverse iterator-ok fordı́tott irányba haladnak, ezért sokszor jól lehet használni elemek utolsó előfordulásának megkeresésére. A reverse iterator-ok iterator-rá történő konverziójához nyújt egy base metódust, de a base által visszaadott iterátor nem ugyanarra az elemere hivatkozik, mint az eredeti

iterátor, hanem a következő elemre. Emiatt a base használata félreérthető (II413) Ahhoz, hogy a base ﬁgyelmeztetést adhasson két adapter osztályt kell módosı́tani: a reverse bidirectional iterator-t és a reverse iteratort. A reverse iterator-on mutatom be az én megközelı́tésemet: 98 Fordı́tás idejű megoldások struct BASE ITERATOR POINTS TO THE NEXT ELEMENT{}; struct I Know What Base Returns{}; #define I KNOW WHAT BASE RETURNS I Know What Base Returns() template <typename Iterator> class reverse iterator: public std::iterator< typename std::iterator traits<Iterator>::iterator category, typename std::iterator traits<Iterator>::value type, typename std::iterator traits<Iterator>::difference type, typename std::iterator traits<Iterator>::pointer, typename std::iterator traits<Iterator>::reference > { // . public: Iterator base() const { warning( BASE ITERATOR POINTS TO THE NEXT ELEMENT() ); return

base( I Know What Base Returns() ); } Iterator base( I Know What Base Returns ) const { // a base eredeti implementációja } }; A megoldás a warning segı́tségével ﬁgyelmeztetést generál. Magát a base-t túlterheljük, a szabványos meghı́vja a túlterheltet (a believe-me markkal ellátott verziót). Így a következő hı́vás helyes és warning-ot sem generál: std::vector<int> v; int x; // . v.erase( std::find( vrbegin(), v.rend(), x ).base( I KNOW WHAT BASE RETURNS ) - 1 ); A reverse bidirectional iterator implementációja hasonlóképpen készı́thető el. Fordı́tás idejű megoldások IV.7 99 Lusta példányosı́tás A C++ szabványa szerint egy sablonból addig nem generálódik kód, amı́g a sablon nem példányosul. Ezt nevezik lusta példányosı́tásnak (lazy instantiation) Egy osztálysablon esetében a tagfüggvények csak akkor példányosulnak, amikor valaki először meghı́vja az

adott tagfüggvényt Ez szándékos döntés volt, mert ı́gy a sablonnal kapcsolatos elvárásokat a fordı́tóprogram csak akkor ellenőrzi, amikor már tényleg szükséges [26]. Maga az STL is számos helyen kihasználja ezt a tulajdonságát a nyelvnek: például a list konténernek van egy sort nevű tagfüggvénye, de ez nem jelenti azt, hogy a list sablonparaméter tı́pusának mindig rendezhetőnek kell lennie, csak abban az esetben a sort tagfüggvény nem hı́vható meg. Ugyanakkor ennek a nyelvi tulajdonságnak van hátránya is. Tegyük fel, hogy ı́rtunk egy Complex tı́pust, ami komplex számokat reprezentál: class Complex { // . }; A komplex számokon nem deﬁniálunk rendezést, ı́gy a Complex tı́pus nem használható az STL asszociatı́v konténereivel, amelyek elvárják a rendezhetőséget. Mégis az alábbi kódrészlet lefordul: std::set<Complex> s; Ennek az oka a lusta példányosı́tás. A

set default konstruktora feltehetően néhány pointert inicializál, de nem hı́v meg olyan műveletet, ami a rendezéssel kapcsolatos lenne, ı́gy ez a konstruktor hı́vás lefordul, anélkül, hogy kiderülne, hogy a Complex tı́pus nem rendezhető. Ha megpróbálunk egy értéket eltárolni a konténerbe, akkor fordı́tási hibát kapunk: s.insert( Complex( 00, 10 ) ); Az előző megoldásokkal szemben itt nem fordı́tási ﬁgyelmeztetéseket használok a hiba jelzésére, hanem egy fordı́tási hiba felderı́tését korábbra időzı́tem, ı́gy szimulálom a concept-ek működését, amelyek korábban a C++0x részét képezték, de 2009 nyarán eltávolı́tották a szabványtervezetből. E terminológia szerint, ellenőrzöm, hogy az asszociatı́v konténer első paramétere teljesı́ti-e a LessThanComparable conceptet. Mivel a concept-ek nem lesznek benne a C++ következő szabványában, minden igyekezet

fontos, ami pótolja a mechanizmust [83]. 100 Fordı́tás idejű megoldások template <class T, class Comp = std::less<T>, class Alloc = std::allocator<T> > class set { // . public: set() { #ifdef CHECK LESS THAN COMPARABLE CONCEPT if ( false ) Comp()( T(), T() ); #endif // . } // . }; A problémát úgy oldottam meg, hogy egy elérhetetlen kódrészletben belehı́vtam a rendezést deﬁniáló paraméterbe átadva két default konstruált objektumot. Így kényszerı́tem a fordı́tóprogramot arra, hogy ellenőrizze, hogy teljesül-e a LessThanComparable concept. Futás közben semmilyen overhead nem keletkezik, hiszen a funktor hı́vása nem történik meg. Innentől kezdve viszont elvárás, hogy legyen default konstruktora az asszociatı́v konténerben tárolt elemek tı́pusának. Egy preprocesszor makró segı́tségével garantáltam, hogy az STL eredeti viselkedése elérhető legyen. IV.8 Összegzés

Ebben a fejezetben az STL biztonságos használatához adtam olyan eszközöket, amelyek fordı́tási időben ellenőrzik az STL használatát. Ha valamelyik konstrukcióról feltehető, hogy hibás viselkedése lehet futás közben, arról fordı́tási ﬁgyelmeztetést ad a fordı́tóprogram. Ehhez a viselkedéshez nem a fordı́tóprogramokat változtattam meg, hanem a könyvtár kódját módosı́tottam A ﬁgyelmeztetésekhez believe-me mark-okat adtam, ezekkel speciﬁkusan ezek a ﬁgyelmeztetések kikapcsolhatóak. Megoldásom fordı́tási időben ellenőrzi, hogy helyes bázistı́pusa van-e egy adaptálható funktornak, használ-e valaki auto ptr-t tartalmazó konténert, esetleg vector<bool>-t. Fordı́tási ﬁgyelmeztetést kap a felhasználó, ha má- Fordı́tás idejű megoldások 101 soló algoritmust nem inserter iterátorral használ vagy find vagy count algoritmust hı́v meg egy rendezett

adatszerkezeten. Ellenőrzöm az allokátorok tı́pusait, hogy ne legyen állapotuk. A unique algoritmust biztonságosabbá tettem ﬁgyelmeztetésekkel és különböző mark-okkal, amelyek befolyásolják az algoritmus viselkedését. Emellett a LessThanComparable concept-et modellezem az asszociatı́v konténereknél 2. Tézis Módszereket dolgoztam ki, melyekkel fordı́tási időben detektálhatjuk az STL bizonyos hibás használati eseteit A módszer a könyvtár implementációjának C++ szabvány szerinti módosı́tásán alapul, ezért megoldásaim minden szabványos C++ fordı́tó használata esetén alkalmazhatóak. A módszerek a hibás példányosı́tásokat (21), egyes algoritmusokat (22), adaptálható funktorokat (2.3), az allokátorokat (24), a reverse iterátorokat (2.5) és a lusta példányosı́tást (26) érintik Hibás példányosı́tások Algoritmusok Adaptálható funktorok Allokátorok

Reverse iterátorok Lusta példányosı́tások [67] [76] [63] [71] [71] [66] IV.1 táblázat A tézishez kapcsolódó publikációim V. fejezet Futási idejű megoldások Sajnos nem mindig lehet fordı́tási időben előrejelezni azt, hogy valami futás közben hibásan fog működni. Például fordı́tási időben nem kerül ki, hogy a copy algoritmus hány elemet tud felülı́rni a célként megadott pozı́ción. Ez esetben célszerű lehet futási időben jelezni a hibát ahelyett hogy hibásan futna vagy abortálna a program. Bizonyos speciális esetekben ezt a módszert alkalmazza az STLport [53] is. Ebben a fejezetben bemutatom azokat az általam kidolgozott eszközöket, amelyek futási időben teszik az STL használatát biztonságosabbá. V.1 Az iterator traits kibővı́tése Ebben a fejezetben számos új iterátor tı́pust vezetek be, amelyek elősegı́tik az STL helyes használatát. Ezen

iterátorok új tulajdonság leı́rásokat igényelnek az iterator traits tı́pustól, hogy ezen tulajdonságok alapján fordı́táskor döntéseket hozhassanak a fordı́tóprogramok, hogy az algoritmusok melyik verziója fusson le. A fejezetben bevezetem az alábbi fogalmakat: • törlő iterátor • előfeltétel-biztos iterátor Ezekhez a fogalmakhoz két-két jellemző osztályt készı́tek: struct erasable{}; struct unerasable{}; struct precondition safe{}; struct precondition unsafe{}; 102 Futási idejű megoldások 103 Az előző fejezetben (IV.31) látottakhoz hasonlóan ezen jellemzőkkel kibővı́tem az iterator traits tı́pust A IV31-es és az itt bevezetett megoldások ortogonálisak, együtt is használhatóak Most az iterator traits tı́pus alapértelmezett verziója ı́gy nézhet ki: template <class T> struct iterator traits { typedef typename T::iterator category typedef typename T::value type typedef

typename T::difference type typedef typename T::pointer typedef typename T::reference typedef unerasable typedef typename T::precondition safety }; iterator category; value type; difference type; pointer; reference; erasability; precondition safety; Itt a két új fogalom az erasability és a precondition safety szinonı́mákban deﬁniált. Az alapértelmezett esetben az iterátorok nem törlő-iterátorok és nem előfeltétel-biztosak Az iterator bázistı́pus bővı́tésével ezek a tulajdonságok is állı́thatóak A törlő iterátorok (V4) esetében az erasability szinonı́mája az erase fogalom legyen, mı́g az előfeltételbiztonságos iterátorok (V.5) a precondition safety szinonı́mája legyen a precondition safe tı́pus. Minden más esetben a default-tal kell deﬁniálni ezeket a jellemzőket. V.2 Invalid iterátorok Az invalid iterátorok olyan konténer elemre hivatkoznak, amelyeket vagy már töröltek, vagy esetleg a

memóriában máshova kerültek a konténer stratégiája miatt. Ha egy ilyen invalid iterátort használunk, akkor annak nemdeﬁniált a viselkedése. Az invalid iterátorok problémája azért jöhet elő, mert nincsen kapcsolat a konténerek és az iterátorok között: a konténer nem ismeri az elemeire hivatkozó iterátorokat, az iterátor nem tudja, hogy melyik konténer elemére hivatkozik. Az alábbiakban bemutatom az általam kidolgozott technikát, amellyel futási időben kezelhetőek az invalid iterátorok [79]. A technika lényegét egy vector konténer esetén mutatom be, de más konténerekre is alkalmazható. 1 template <class T, 104 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 Futási idejű megoldások class Alloc = std::allocator<T>, bool debug = false> class vector { typedef ItCont std::list<shared ptr<iterator impl> >;

T* p; int cap, s; ItCont iterators; public: struct iterator impl { private: bool isvalid; T* curr; public: iterator impl( T* c ) : curr( c ), isvalid( true ) {} T& operator*() { if ( !isdebug ) return *curr; if( isvalid ) return *curr; else throw invalid iterator(); } iterator impl& operator++() { ++curr; return *this; Futási idejű megoldások 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 } iterator impl operator++( int ) { iterator impl tmp( *this ); ++curr; return tmp; } // . }; struct iterator: std::iterator< std::random access iterator tag, T> { iterator impl* p; // delegates // iterator impl’s operations }; private: void realloc() { cap*=2; T* t = new T[cap]; std::copy( p, p + s, t ); delete [] p; p = t; } void invalid() { for( typename ItCont::iterator it = iterators.begin(); it != iterators.end(); ++it) 105 106 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 Futási idejű megoldások { (*it)->isvalid = false; } } public: vector(): cap( 1 ), s( 0 ) { p = new T[cap]; } vector() { delete [] p; } void push back( const T& a ) { if ( s < cap ) p[ s++ ] = a; else { realloc(); invalid(); push back( a ); } } iterator begin() { iterator impl* x = new iterator impl( p ); iterators.push back( x ); return iterator( x ); } iterator end() { iterator impl* x = new iterator impl( p + s ); iterators.push back( x ); Futási idejű megoldások 125 126 127 128 129 130 107 return iterator( x ); } // . }; A konténer smart-pointereket tárol egy list-ben (14.sor), amelyek a begin és end tagfüggvényekkel létrehozott iterátorokra mutat. Amikor a vector reallokál, akkor a listában lévő pointereken keresztül értesı́ti az iterátorait, hogy invalidálódtak (107.sor) Az iterátor tı́pus rendelkezik egy olyan adattaggal

(isvalid, 21sor), ami alapján eldönthető, hogy az érvényes-e A reverse kompatibilitást úgy garantálom, hogy a konténernek van egy (nemszabványos) bool sablon paramétere (3.sor), amelynek értékétől függ, hogy a konténer ellenőrzi-e az iterátorok érvényességét. A default értéke a paraméternek az, hogy ne vizsgálja az iterátorok validságát Ha valaki használni szeretné, akkor ezt a paramétert kell beállı́tania. Mivel a sablon paraméterek fordı́tás idejű adatok, ennek eldöntése fordı́táskor megtörténik és ı́gy a futási idő nem nő meg. Több hasonló implementációt is megvizsgáltam [80] hatékonysági megfontolások alapján. Az eltérő verziók megpróbálták a szükségtelen iterátorokat kitörölni a listából A fenti bizonyolult a leghatékonyabbnak a tesztek alapján [80]. V.3 Másolás-biztonságos iterátorok Az STL másoló algoritmusai (pl.

copy, transform, stb) konténer-független módon másolnak elemeket egy output iterátor által meghatározott helyre Felteszik és kihasználják, hogy az output-on van elegendő lefoglalt hely, ahova másolhatnak elemeket: ez lehet egy konténer iterátor, ı́gy a konténerben lévő elemeket lehet felülı́rni vagy lehet egy inserter adapter, ı́gy mindenképpen megmaradnak a konténer eredeti elemei, nem ı́rják felül azokat. Nem lehet egyszerűen megoldani a következő problémát: adott két konténer: si és li. Tudjuk, hogy si.size()>lisize() és lisize()>0 Azt szeretnénk, hogy li-ben lévő elemeket felülı́rjuk si kezdő elemeivel, majd, amikor már li elemeit felülı́rtuk, a si maradék elemeit hozzáadjuk a li-hez. A problémát mutatja, hogy jelenleg csak az alábbi bonyolult lépéssorozattal oldható meg a feladat: std::set<int> si; // . 108 Futási idejű megoldások std::list<int> li;

// . std::set<int>::iterator i = si.begin(); std::advance( i, li.size() ); std::copy( si.begin(), i, libegin() ); std::copy( i, si.end(), std::back inserter( li ) ); Ezen probléma elegáns megoldásához az általam kidolgozott másolás-biztonságos iterátor használható [68]: std::copy( si.begin(), siend(), licsbegin() ); A másolás-biztonságos iterátorok működési alapelve, hogy amı́g lehet, addig szokásos iterátorként felülı́rható elemeket biztosı́t és ha a konténernek nincs több eleme, akkor beszúr egy új elemet és ezt adja vissza az algoritmusnak felülı́rásra. Ennek a megoldásnak egy lehetséges implementációja lehet a következő (a példában az implementációt egy vector konténer esetén mutatom be, ahol a vector<T>::iterator-nak van egy p nevű pointer tagja, ami a vector egy elemére mutat): template <class T, class Alloc = std::allocator<T> > class vector { // szokásos

adattagok, metódusok, typedef-ek, stb. class copy safe iterator: public iterator { vector<T, Alloc>* v; public: copy safe iterator( iterator i, vector<T, Alloc>* vt ) : iterator( i ), v( vt ) { } T& operator*() { if ( *this == v->end() ) { v->push back( T() ); iterator::p = &( v->back() ); } return iterator::operator*(); Futási idejű megoldások 109 } }; copy safe iterator csbegin() { return copy safe iterator( begin(), this ); } copy safe iterator csend() { return copy safe iterator( end(), this ); } }; V.4 Törlő iterátorok Az STL algoritmusai konténer-függetlenek, nem is ismerik, hogy milyen adatszerkezeten alkalmazzák. Emiatt azok az algoritmusok, amelyek valamilyen ,,törlési” műveletet hajtanak végre (unique, remove és remove if) nem törölnek elemet a konténerből, hanem a megmaradó elemeket a konténer elejére másolják, és visszaadnak egy iterátort, ami a logikai végét jelzi a

konténernek. Ennek az a következménye, hogy a törlő algoritmusok nem intuitı́vak. Ez egyrészt könnyen lehet oka hibásan működő kódoknak, másrészről a programozók az algoritmusokat kézzel ı́rt ciklusokra cserélve iterátor invalidálást idézhetnek elő (II.42) Ezen probléma megoldásához bevezetem a törlő iterátorok fogalmát: ezek olyan konténerekhez kapcsolódó iterátorok, melyeknek van egy plusz tagfüggvénye: erase, ami kitörli a konténerből az iterátor által hivatkozott elemet és ezután újra valid elemre hivatkozik, a konténer következő elemére. A törlő iterátorokat a következőképpen hoztam létre [68]: template <class T, class Alloc = std::allocator<T> > class vector { // szokásos adattagok, metódusok, typedef-ek, stb. class iterator: public std::iterator<std::random access iterator tag, T> 110 Futási idejű megoldások { protected: T* p; //

szokásos operator-ok, stb. }; class erasable iterator: public iterator { vector<T, Alloc>* v; public: erasable iterator( iterator i, vector<T, Alloc>* vt ) : iterator( i ), v( vt ) { } void erase() { T* tmp = iterator::p + 1; v->erase( *this ); iterator::p = tmp; } }; erasable iterator ebegin() { return erasable iterator( begin(), this ); } erasable iterator eend() { return erasable iterator( end(), this ); } }; A törlő iterátorok olyanok, mint a szokásos iterátorok, ugyanazokkal a műveletekkel, de eltárolnak egy mutatót a konténerre, amikor létrehozzuk őket. Az erase metódus ezen a pointeren keresztül eléri a konténert és ki tudja törölni az elemet a konténerből, miközben elkerüli az iterátor invalidálását. Az STL szabványos algoritmusai természetesen nem ismerik ezt az iterátort, tehát az olyan algoritmusokat is meg kell ı́rni, amelyeket ezt is kihasználhatják. A kibővı́tett iterator traits

alapján eldönthető, hogy törlő vagy Futási idejű megoldások 111 nem törlő iterátorokkal dolgozik az algoritmus, és a törlő esetben direktben kihasználható a törlés művelet. template <class Iterator, class T> Iterator remove( Iterator first, Iterator last, const T& t ) { return remove( first, last, t, typename std::iterator traits<Iterator>::erasability() ); } A törlő változat a következőképpen implementálható: template <class Iter, class T> void remove( Iter first, Iter last, const T& t, erasable ) { while( first != last ) { if ( t == *first ) { first.erase(); } else { ++first; } } return first; } Az a változat, ami nem törlő iterátorok esetén működik, megegyezik az eredeti megvalósı́tással. V.5 Algoritmusok előfeltétele Az STL algoritmusai csak akkor működnek a speciﬁkációnak megfelelően, ha teljesülnek az előfeltételei. Jellemzően az input

rendezettségét elváró algoritmusok nem ellenőrzik sem fordı́tási-, sem futási időben, hogy az input 112 Futási idejű megoldások rendezett-e. Ha megsértjük ezt az előfeltételt, akkor az algoritmus hatása nemdeﬁniált. Ezen problémák elkerüléséhez az előfeltétel-biztos iterátor adaptort vezetem be [79]. Az implementáció a következő: template <class T> struct Precond safe: T { Precond safe( T t ): T( t ) { } typedef precondition safe precondition safety; }; Az adapter a mixin technikán alapul: az iterátor tı́pusa a bázisosztály [91]. Tehát a Precond safe pontosan ugyanazokkal a tulajdonságokkal és műveletekkel bı́r, mint az eredeti iterátor tı́pus, csak a biztonsági tı́pust deﬁniálja precondition safe-nek. Ezen tı́pusinformáció alapján az algoritmusok túlterhelhetők A sablonparaméter levezetéshez egy függvénysablon készı́thető: template <class T> Precond

safe<T> Precond( T t ) { return Precond safe<T>( t ); } Példaképpen megmutatom, hogy a lower bound algoritmust hogyan lehet biztonságosabbá tenni ennek a technikának a segı́tségével. Először is készı́tek egy kivétel tı́pust a hiba jelzéséhez: class not sorted{}; A szabványos algoritmus az iterátor tı́pusa alapján eldönti, hogy az előfeltétel-biztos-e: template <class It, class T> It lower bound( It first, It last, const T& t ) { return lower bound( first, last, Futási idejű megoldások 113 t, typename std::iterator traits<It>::precondition safety() ); } Az előfeltétel-biztos megoldás először ellenőrzi az algoritmus előfeltételét, és ha az nem teljesül, akkor kivételt vált ki, egyébként meghı́vja az eredeti változatot: template <class Iterator, class T> Iterator lower bound( Iterator first, Iterator last, const T& t, precondition safe ) { if ( !std::is sorted(

first, last ) ) { throw not sorted(); } return lower bound( first, last, t, precondition unsafe() ); } Az eredeti implementáció mostantól a nem-előfeltétel-biztos megoldás: template <class Iterator, class T> Iterator lower bound( Iterator first, Iterator last, const T& t, precondition unsafe ) { // eredeti implementáció. } Ha a szokásos módon hı́vjuk meg az algoritmust, akkor az eredeti implementáció fut le: std::vector<int> v; int x; // . std::vector<int>::iterator i = std::lower bound( v.begin(), vend(), x ); Ha viszont kihasználjuk az adapter-t, akkor a biztonságos verzió. A viszszatérési érték konverziója bázistı́pusra triviálisan működik: 114 Futási idejű megoldások std::vector<int> v; int x; // . std::vector<int>::iterator i = std::lower bound( Precond(v.begin()), Precond(vend()), x ); Vegyük észre, hogy a biztonságos esetben a lower bound futási idejét logaritmikusról

lineárisra növeltük. A felhasználói predikátummal túlterhelt verzió teljesen hasonlóan megy, csak a bináris predikátumot mindenhol át kell adni egy plusz sablonparaméter bevezetésével. A technika általánosabban is használható, tetszőleges algoritmus előfeltételének ellenőrzésére. V.6 Funktorok Az STL szabványa szerint a rendezéshez használt funktoroknak szigorú részbenrendezésnek kell lennie. Ha ez a feltétel megsérül, akkor az asszociatı́v konténerek inkonzisztenssé válnak, mert a megegyező értékek nem lesznek ekvivalensek, és az enkapszulált rendezés miatt hibás eredményt adnak a tagfüggvények (II.43) Kidolgoztam egy megoldást, ami nem intruzı́v módon, futási időben ellenőrzi a funktor tulajdonságait. Ehhez először ı́runk egy kivételtı́pust a hiba jelzéséhez: struct bad functor exception { // . }; Az ellenőrzés magja a következő kódrészlet:

template <class T, class functor to check> struct strict weak ordering { strict weak ordering() { if ( static cast <functor to check*>( this )-> operator()( T(), T() ) ) { Futási idejű megoldások 115 throw bad functor exception(); } } }; A kódrészlet az ún. ,,curiously recurring template pattern”-en (CRTP) alapul. Ez a minta sablonok segı́tségével fordı́tási időben szimulálja a virtuális függvények viselkedését [3] Azért volt erre szükségem, mert C++-ban a konstruktorban lefutó virtuális függvény csak a statikus tı́pusinformációk alapján működik [92]. A CRTP mintát széleskörben használom [99, 100] Ez a sablon könnyen használható, amikor valaki egy új funktor tı́pust ı́r: a funktornak származnia kell a példányosı́tott strict weak ordering osztályból is. Így ez egy nem intruzı́v megoldás a problémára: struct Compare : std::binary function<int, int, bool>,

strict weak ordering<int, Compare> { bool operator()( int i, int j ) const { // . } }; A sablon specializálható is: konkrét tı́pusokra külön komplexebb tesztesetek is megadhatóak: template <class functor to check> struct strict weak ordering<int, functor to check> { strict weak ordering() { functor to check* p = static cast<functor to check>( this ); if ( p->operator()( 3, 3 ) && p->operator()( 22, 22 ) ) { throw bad functor exception(); } } }; 116 Futási idejű megoldások template <class functor to check> struct strict weak ordering<std::string, functor to check> { strict weak ordering() { const std::string test = "Hello World"; if ( static cast <functor to check*>( this ) -> operator()( test, test ) ) { throw bad functor exception(); } } }; Egy ilyen funktor tı́pus használata megegyezik a megszokottal: std::set<int, Compare> s; Mivel mielőtt a kódban bármilyen rendezés

történne a set létrehoz egy funktor objektumot, azaz meghı́vja a funktor tı́pus default konstruktorát. Ez először meghı́vja a bázistı́pus(ok) default konstruktorát és ennek hatására lefut a strict weak ordering konstruktorában lévő ellenőrzés. A funktor csak abban az esetben jöhet létre és használható rendezéshez, ha teljesı́ti a szigorú részbenrendezést. V.7 Összegzés Ebben a fejezetben olyan megoldásokat mutattam be, amelyek nagyobb futási idő mellett az STL biztonságosabban használható. Kidolgoztam egy olyan konténer-iterátor modellt, amellyel az invalid iterátorok használata kiszűrhető. A másolási algoritmusok helyes használatához másolás-biztonságos iterátorokat deﬁniáltam A törlő algoritmusok kényelmes alkalmazásához törlő iterátorokat dolgoztam ki. Az STL algoritmusainak speciális előfeltételeit futási időben ellenőrző megoldást mutattam

be A funktorok rendezési tulajdonságainak ellenőrzéséhez egy nem-intruzı́v technikát fejlesztettem ki, amely automatikusan kiértékeli a felhasználói rendezéseket. 3. Tézis Módszereket dolgoztam ki, melyek segı́tségével futási időben lehet a C++ Standard Template Library egyes hibás használati eseteit detektálni illetve elkerülni, A módszerek az iterátor invalidációt (3.1), a má- Futási idejű megoldások 117 solás-biztos iterátorokat (3.2), a törlő iterátorokat (33), egyes algoritmusok előfeltételeit (3.4) és a funktorok használatát (35) érintik Invalid iterátorok [70, 79, 80] Másolás-biztonságos iterátorok [68, 70] Törlő iterátorok [68, 70] Algoritmusok előfeltétele [70, 79, 80] Funktorok [63, 66] V.1 táblázat A tézishez kapcsolódó publikációim VI. fejezet Összefoglalás A C++ STL a legfontosabb generikus programozási paradigmán alapuló könyvtár,

mivel részét képezi a C++ szabványnak. Az STL nagymértékben segı́ti a tipikus C/C++ hibák leküzdését. Használata növeli a kód karbantarthatóságát, minőségét és hatékonyságát [78] Az STL-nek számos kiterjesztése, módosı́tása létezik. A C++ Persistent Standard Template Library célja a perzisztencia biztosı́tása, ı́gy olyan STL-kompatibilis konténereket biztosı́t, ami háttértárolón tárolja az adatokat [40]. A STXXL könyvtár az STL egy olyan változata, ami kifejezetten nagy adatmennyiségre terveztek [16]. A CPH STL az algoritmikus optimalizációt helyezi előtérbe, megpróbál aszimptotikusan minél gyorsabb implementációt biztosı́tani [24, 25, 27] Multicore környezetre optimalizált STL implementációk is elérhetőek [90, 105, 106]. Sajnos az STL generikus megközelı́téséből adódóan új fajta hibalehetőségeket csempészett a nyelvbe: iterátorok

invalidációja, hibás funktorok, stb. Ezen hibák egy részét nehéz programozói szemmel észrevenni, és a meglévő eszközök sem mindig tudnak segı́teni. Az STL helyes és hatékony használatát mutatja be [53], de szoftveres megoldást nem biztosı́t. Jelen dolgozat központi témája a C++ STL. Egy rövid bevezetés után ismertettem a könyvtár felépı́tését, komponenseit, és bemutattam a könyvtárral elkövethető hibákat. A dolgozatban eszközöket adtam a hibák elkerülésére: formális és szoftveres eszközök segı́tségével biztosı́tottam, hogy a hibák egy jelentős részét ne kövessék el a könyvtárt használó programozók. A szoftveres eszközök egyik része fordı́tási időben detektálja a potenciális hibákat, a másik része pedig futási időben szűri ki a hibákat. Az STL formális speciﬁkációjára két különböző módszert mutattam be (III.

fejezet): az általam kidolgozott, Hoare-módszeren alapuló elő- és utófeltételekkel deﬁniált technikát, valamint a LaCert nyelven alapuló temporális logikát használó speciﬁkációt Előbbi felhasználható STL-t használó 118 Összefoglalás 119 programok, könyvtárak, valamint STL implementációk helyességének vizsgálatához, utóbbi pedig speciﬁkációkból a LaCert fordı́tóprogram generálja az STL alapú C++ kódokat kritikus pontokon. Az STLlint a legismertebb eszköz, amely az STL hibás használatának kiszűrésére terveztek [32, 35]. Az STLlint statikus elemzésen alapszik, azaz fordı́tás idejű adatok alapján működik. Ezzel nem lehet minden hibát kiszűrni, hiszen a legtöbb információ csak futási időben derül ki Az STLlint nem működik együtt nem-szabványos bővı́tményekkel. Az STLlint online elérhető volt, de támogatottsága megszűnt.

Véleményem szerint nem járható út, hogy minden használt könyvtárhoz külön statikus elemző eszközt futtassanak a fejlesztők, hiszen a C++ programok elemzése kifejezetten lassú. Az a döntés sem tűnik helyesnek, hogy ezek az elemzések a fordı́tóprogramokban legyenek implementálva, hiszen a fordı́tóprogramok nem ismerhetik az összes könyvtárat. Az STLlint-hez hasonlóan végez ellenőrzéseket az STL használatával kapcsolatban a cppcheck [28] statikus elemzésen alapú ellenőrző program, melynek célja, hogy csak a tényleges hibákat jelezze. Általában csak a potenciális hibákat lehet jelezni fordı́tási időben, mivel akkor még nem ismerjük a futási idejű adatokat. Így ez az eszköz nehézkesen használható hibák kiszűrésére Ezekkel szemben az én fordı́tási idejű megoldásaim (IV. fejezet) a könyvtár forráskódjának módosı́tásán és bővı́tésén

alapul Ez ı́gy minden platformra port-olható, hiszen az STL forráskódjának minden környezetben meg kell lennie, előre nem lefordı́tható. Használata nem igényli külső eszközök meghı́vását, a fordı́tóprogram egyúttal kiértékeli, ellenőrzi a könyvtár használatát Az én megoldásom támogatja a könyvtár bővı́tését, ami az STL alapﬁlozóﬁája. Ugyanakkor a megoldásom nem olyan általános, mint egy absztrakt szintaxisfa-alapú (AST) implementáció [44], mert kevesebb kontextust lát a forráskóddal kapcsolatban. Az én megoldásom fordı́tási időben tudja detektálni a hibás példányosı́tásokat: jelzi a vector<bool> konténer példányosı́tását, letiltja a COAPok használatát. Számos algoritmustı́pust biztonságosabbá tettem: másoló algoritmusok, kereső algoritmusok, unique algoritmus vélhetően hibás használatát jelzem a programozók

számára. Ellenőrzöm továbbá a funktorok bázistı́pusának helyességét, az allokátorok állapotmentességét és a reverse iterátorok konverzióját. Wang az STL algoritmusainak helyességét vizsgálta [113, 114]. Egy dinamikus veriﬁkációnak nevezett eljárást dolgozott ki, ami kihasználja az algoritmusok sablon paramétereit Olyan (iterátor) tı́pussal példányosı́totta a sablonokat (RAO, Run-time Analysis Oracle)), amely szimbólikus inputtal dolgozva kiszámolja az output-ot. A lefordı́tott kódot a gdb debugger alkalmazás segı́tségével futtatják, a függvény elő- és utófeltételeket speci- 120 Összefoglalás ﬁkációs osztályokban ellenőrzik. Break-point-ok segı́tségével a felhasználó befolyásolni tudja a veriﬁkációs adatokat és a működést. A futási idejű ellenőrzések is hasznosak tudnak lenni, hiszen ilyenkor sokkal több információ áll a

rendelkezésünkre, mint fordı́tási időben, ı́gy pontosabban lehet jelezni a hibát és annak okát. A legtöbbször nem dönthető el fordı́tási időben, hogy a potenciális hiba okoz-e futási időben problémát, vagy akár a jelenség sem biztos, hogy észrevehető Futási időben nem csak észrevehető ha valami hibás eredményhez vezetne, hanem korrigálható is lehet a rendszer viselkedése. Az STLport implementációja végez futási idejű ellenőrzéseket [53], amikor a kódot debug módban fordı́tjuk: például garantálja, hogy egy konténer tagfüggvényének átadott iterátor tényleges arra konténerre hivatkozik vagy egy intervallumot két külön konténerhez tartozó iterátorral deﬁniálunk. Az STLport szintén képes ellenőrizni az iterátorok érvényességét. A futás idejű megoldások általános problémája a futási idő növekedése. Én is ellenőrzök bizonyos

tulajdonságok futási időben (V. fejezet): iterátorok invalidációit, a funktorok tulajdonságait, algoritmusok speciális előfeltételeit Kidolgoztam olyan másolás-biztonságos iterátorokat, amelyek garantálják, hogy a másoló algoritmusok helyesen lefussanak. Ezenkı́vül deﬁniáltam törlő iterátorokat, amelyek iterátor szintű műveletként garantálják elemek törlését és az iterátor további érvényességét. Nem adtam megoldást a bemutatott hibalehetőségék mindegyikére. Ezek további kutatási feladatokat jelentenek. Irodalomjegyzék [1] Abrahams, D., Gurtovoy, A: C++ Template Metaprogramming: Concepts, Tools, and Techniques from Boost and Beyond, Addison-Wesley (2004). [2] Aldinucci, M., Danelutto, M, Meneghin, M, Kilpatrick, P, Torquati, M.: Eﬃcient streaming applications on multi-core with FastFlow: the biosequence alignment test-bed, in Proc. of Intl Parallel Computing (PARCO) 2009. [3]

Alexandrescu, A.: Modern C++ Design: Generic Programming and Design Patterns Applied, Addison-Wesley (2001). [4] Alexandrescu, A., Sutter, H: C++ kódolási szabályok, Kiskapu Kiadó (2005). [5] Austern, M. H: Generic Programming and the STL: Using and Extending the C++ Standard Template Library, Addison-Wesley (1998) [6] Baus, C., Becker, T: Custom Iterators for the STL, in Proc of First Workshop on C++ Template Programming. [7] Becker, T.: STL and generic programming: writing your own iterators, C/C++ Users Journal 19(8) (2001), pp. 51–57 [8] Borók-Nagy, Z., Májer, V, Mihalicza, J, Pataki, N, Porkoláb, Z: Visualization of C++ Template Metaprograms, in Proc of Tenth IEEE International Working Conference on Source Code Analysis and Manipulation (SCAM 2010), pp. 167–176 [9] Brosgol, B. M: A Comparison of Generic Template Support: Ada, C++, C#, and Java, in Proc. of Ada-Europe 2010, Lecture Notes in Computer Science 6106, pp. 222–237 [10] Chandy, K. M, Misra, J: Parallel

program design: a foundation, Addison-Wesley, (1988). 121 122 Irodalomjegyzék [11] Coplien, J. O: Multi-Paradigm Design for C++, Addison-Wesley (1998). [12] Cormen, T. H, Leiserson, C E, Rivest, R L: Algoritmusok, Műszaki Könyvkiadó (2001). [13] Csörnyei, Z.: Fordı́tóprogramok, Typotex (2006) [14] Czarnecki K., Eisenecker, U W: Generative Programming: Methods, Tools and Applications, Addison-Wesley (2000). [15] Czarnecki K., Eisenecker, U W, Glück, R, Vandevoorde, D, Veldhuizen, T L: Generative Programming and Active Libraries, in Proc of Generic Programming ’98, Lecture Notes in Computer Science 1766, pp. 25–39 [16] Dementiev, R., Kettner, L, Sanders, P: Stxxl: Standard Template Library for XXL Data Sets, in Procof 13th Annual European Symposium on Algorithms (ESA 2005), Lecture Notes in Computer Science 3669, pp. 640–651 [17] Dewhurst, S. C: C++ hibaelhárı́tó, Kiskapu Kiadó (2003) [18] Dévai, G.: Programming language elements for proof

construction, Pure Mathematics and Applications, 17(3-4) (2006), pp. 263–288 [19] Dévai, G.: Programming Language Elements for Correctness Proofs, Acta Cybernetica, 18(3) (2008), pp. 403–425 [20] Dévai, G.: Meta programming on the proof level, Acta Universitatis Sapientiae, Informatica 1(1) (2009), pp. 15–34 [21] Dévai, G., Pataki, N: Towards veriﬁed usage of the C++ Standard Template Library, In Proc. of The 10th Symposium on Programming Languages and Software Tools (SPLST) 2007, pp. 360–371 [22] Dévai, G., Pataki, N: A tool for formally specifying the C++ Standard Template Library, Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae, Sectio Computatorica 31 (2009), pp. 147–166. [23] Eckel, B.: Thinking in C++, Prentice Hall (2000) Irodalomjegyzék 123 [24] Edelkamp, S., Elmasry, A, Katajainen, J: Two Constant-FactorOptimal Realizations of Adaptive Heapsort, in Proc of the 22nd International Workshop on Combinatorial Algorithms

(IWOCA 2011), pp. 195–208 [25] Edelkamp, S., Elmasry, A, Katajainen, J: The Weak-Heap Family of Priority Queues in Theory and Praxis, in Proc. of the Eighteenth Computing: The Australasian Theory Symposium (CATS 2012), pp. 103–112. [26] Ellis, M. A, Stroustrup, B: The Annotated C++ Reference Manual, Addison-Wesley (1990). [27] Elmasry, A., Katajainen, J: Fat Heaps Without Regular Counters, in Proc. of the 6th Workshop on Algorithms and Computation (WALCOM 2012), Lecture Notes in Computer Science 7157, pp 173–185 [28] Ermakov, A., Kushik, N: Detecting C Program Vulnerabilities, in Proc of the 5th Spring/Summer Young Researchers’ Colloquium on Software Engineering (SYRCoSE 2011), pp. 61–64 [29] Gamma, E., Helm, R, Johnson, R, Vlissides, J: Design Patterns: Elements of Reusable Object-Oriented Software, Addison-Wesley (1994) [30] Garcia, R., Järvi, J, Lumdaine, A, Siek, J, Willcock, J: A Comparative Study of Language Support for Generic Programming, In Proc of Object-Oriented

Programming, Systems, Languages & Applications 2003, SIGPLAN Notices, 38(10) (2003), pp. 115–134 [31] Garcia, R., Järvi, J, Lumdaine, A, Siek, J, Willcock, J: An Extended Comparative Study of Language Support for Generic Programming, Journal of Functional Programming, 17(2) (2007), pp 145–205 [32] Gregor, D.: High-level Static Analysis for Generic Libraries (PhD Thesis) [33] Gregor, D., Järvi, J, Siek, J, Stroustrup, B, Dos Reis, G, Lumsdaine, A.: Concepts: linguistic support for generic programming in C++, in Proc. of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications (OOPSLA 2006), pp. 291–310 124 Irodalomjegyzék [34] Gregor, D., Marcus, M, Witt, T, Lumsdaine, A: Foundational Concepts for the C++0x Standard Library, Technical Report N2677=080187, ISO/IEC JTC 1, Information Technology, Subcommittee 22, Programming Language C++, 2008 [35] Gregor, D., Schupp, S: STLlint: Lifting static checking from languages

to libraries, Software: Practice and Experience 36(3) (2006), pp. 225– 254. [36] Gregor, D., Schupp, S: Making the usage of STL safe, in Proc of the IFIP TC2Working Conference on Generic Programming (2003). [37] Gregor, D., Siek, J: Implementing Concepts, Technical Report N2617=08-0127, ISO/IEC JTC 1, Information Technology, Subcommittee 22, Programming Language C++, May 2008. [38] Gregor, D., Stroustrup, B: Wording for Concepts (revision 1), Technical Report N2193=07-0053, ISO/IEC JTC 1, Information Technology, Subcommittee 22, Programming Language C++, 2007. [39] Gregor, D., Willcock, J, Siek, J, Järvi, J, Garcia, R, Lumsdaine, A: Concepts for C++0x (Revision 1), Technical Report N1849=05-0109, ISO/IEC JTC 1, Information Technology, Subcommittee 22, Programming Language C++, August 2005. [40] Gschwind, T.: PSTL – A C++ Persistent Standard Template Library, in Proc. of 6th USENIX Conference on Object-Oriented Technologies and Systems (COOTS ’01) (2001), pp. 147–158 [41]

Guttag, J. V, Horowitz, E, Musser, D R: Abstract Data Types and Software Validation, Communications of the ACM, 21(12) (1978), pp. 1048–1064. [42] Halpern, P.: Allocators post Removal of C++ Concepts (Revision 1), Technical Report N2982=09-0172, ISO/IEC JTC 1, Information Technology, Subcommittee 22, Programming Language C++, 2009. [43] Hoare, C. A R: An axiomatic basis for computer programming, Communications of the ACM, 12(10) (1969), pp 576–580 [44] Horváth, G.: Mintaillesztési módszerek vizsgálata absztrakt szintaxisfákon, TDK Dolgozat (2013) Irodalomjegyzék 125 [45] Järvi, J.: C++ Function Object Binders Made Easy, in Proc of Generative and Component-based Software Engineering (GCSE’99), Lecture Notes in Computer Science 1799, pp. 165–177 [46] Josuttis, N. M: The C++ Standard Library: A Tutorial and Reference, Addison-Wesley (2009). [47] Karlsson, B.: Beyond the C++ Standard Library: An Introduction to Boost, Addison-Wesley (2005). [48] Kiczales, G.:

Aspect-oriented Programming, ACM Computing Surveys 28(4) (1996). [49] Kozma, L., Varga L: A szoftvertechnológia elméleti kérdései, ELTE Eötvös Kiadó (2003). [50] Kozsik, T.: Tutorial on Subtype Marks, in Proc of the Central European Functional Programming School (CEFP 2006), Lectures Notes in Computer Science 4164, pp. 191–222 [51] Kozsik, T., Pataki, N, Szűgyi, Z: C++ Standard Template Library by inﬁnite iterators, Annales Mathematicae et Informaticae 38 (2011), pp. 75–86 [52] Kröger, F.: Temporal Logic of Programs, Springer-Verlag, Berlin Heidelberg (1987) [53] Meyers, S.: Eﬀective STL - 50 Speciﬁc Ways to Improve Your Use of the Standard Template Library, Addison-Wesley (2001). [54] Meyers, S.: Hatékony C++, Scolar Kiadó (2003) [55] Mihalicza, J.: How #includes Aﬀect Build Time in Large Systems, in Proc. of the 8th International Conference on Applied Informatics (ICAI 2010) Vol. 2, pp 343–350 [56] Mihalicza, J., Pataki, N, Porkoláb, Z, Sipos,

Á: Towards More Sophisticated Access Control, in Proc of 11th Symposium on Programming Languages and Software Tools and 7th Nordic Workshop on Model Driven Software Engineering (SPLST 2009), pp. 117–131 [57] Musser, D. R, Stepanov, A A: Generic Programming, in Proc of the International Symposium ISSAC’88 on Symbolic and Algebraic Computation, Lecture Notes in Computer Science 358, pp. 13–25 126 Irodalomjegyzék [58] Nethercote, N., Seward, J: Valgrind: a framework for heavyweight dynamic binary instrumentation, in Proc. of the 2007 ACM SIGPLAN conference on Programming language design and implementation (PLDI ’07), ACM SIGPLAN Notices 42(6), pp 89–100 [59] Nyékyné Gaizler, J.: Programozási Nyelvek, Kiskapu Kiadó (2003) [60] Pásztorné Varga, K., Várterész, M: A matematikai logika alkalmazásszemléletű tárgyalása, Panem Kiadó (2003) [61] Pataki, N.: A C++ Standard Template Library helyességvizsgálata (TDK Dolgozat), Országos

Tudományos Diákköri Konferencia (2005). [62] Pataki, N.: Testing by C++ template metaprograms, Acta Universitatis Sapientiae, Informatica 2(2) (2010), pp. 154–167 [63] Pataki, N.: Advanced Functor Framework for C++ Standard Template Library Studia Universitatis Babeş-Bolyai, Informatica, Vol. LVI(1) (2011), pp. 99–113 [64] Pataki, N.: A C++ Standard Template Library biztonságos használata, (poszter) ELTE Innovációs Nap 2011 [65] Pataki, N.: C++ Standard Template Library by Ranges, in Proc of the 8th International Conference on Applied Informatics (ICAI 2010) Vol. 2., pp 367–374 [66] Pataki, N.: C++ Standard Template Library by Safe Functors, in Proc of 8th Joint Conference on Mathematics and Computer Science, MaCS 2010, Selected Papers, pp. 363–374 [67] Pataki, N.: C++ Standard Template Library by template specialized containers, Acta Universitatis Sapientiae, Informatica 3(2) (2011), pp. 141–157. [68] Pataki, N.: Advanced Safe Iterators for the C++ Standard

Template Library, in Proc. of the Eleventh International Conference on Informatics, Informatics 2011, pp 86–89 [69] Pataki, N.: Fordı́tási ellenőrzések a C++ Standard Template Libraryben, (poszter) ELTE Innovációs Nap 2012 [70] Pataki, N.: Safe Iterator Framework for the C++ Standard Template Library, Acta Electrotechnica et Informatica, Vol. 12(1), pp 17–24 Irodalomjegyzék 127 [71] Pataki, N.: Compile-time Advances of the C++ Standard Template Library, Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae, Sectio Computatorica 36 (2012), Selected papers of 9th Joint Conference on Mathematics and Computer Science MaCS 2012, pp. 341–353 [72] Pataki, N., Dévai, G: A Comparative Study of C++ Standard Template Library’s Formal Speciﬁcation, in Conference of PhD Students in Computer Science, CSCS 2008, Volume of extended abstracts, 2008, p. 48. [73] Pataki, N., Kozsik, T, Porkoláb, Z: Properties of C++ Template Metaprograms, in

Proc. of the 7th International Conference on Applied Informatics (ICAI 2007), Eger, Hungary Vol. 2 pp 293–299 [74] Pataki, N., Mihalicza, J, Szűgyi, Z, Májer, V, Porkoláb, Z: Features of C++ Template Metaprograms, in Proc. of the 8th International Conference on Applied Informatics (ICAI 2010) Vol 2, p 451 [75] Pataki, N., Pócza, K, Porkoláb, Z: Towards a Software Metric for Generic Programming Paradigm, in Proc. of Sixteenth Electrotechnical and Computer Science Conference (ERK 2007), Vol. A, pp 342–345 [76] Pataki, N., Porkoláb, Z: Extension of Iterator Traits in the C++ Standard Template Library, in Proc of the Federated Conference on Computer Science and Information Systems (FedCSIS 2011), pp 919–922 [77] Pataki, N., Porkoláb, Z, Istenes, Z: Towards Soundness Examination of the C++ Standard Template Library, In Proc. of Electronic Computers and Informatics, ECI 2006, pp 186–191 [78] Pataki, N., Szűgyi, Z: C++ Exam Methodology, Annales Mathematicae et

Informaticae 37 (2010), pp 211–223 [79] Pataki, N., Szűgyi, Z, Dévai, G: C++ Standard Template Library in a Safer Way, In Proc. of Workshop on Generative Technologies 2010 (WGT 2010), pp. 46–55 [80] Pataki, N., Szűgyi, Z, Dévai, G: Measuring the Overhead of C++ Standard Template Library Safe Variants, Electronic Notes in Theoretical Computer Science (ENTCS) Vol. 264(5) (2011), pp 71–83 128 Irodalomjegyzék [81] Pataki, N., Szűgyi, Z, Kozsik, T: On the Correctness of AspectOriented Programs, In Proc of CSE 2008 International Scientiﬁc Conference on Computer Science and Engineering (CSE 2008), Slovakia, pp. 126–132 [82] Pataki, N., Török, M: Towards Warning Annotations in C++11, in Proc. of CSE 2012 International Scientiﬁc Conference on Computer Science and Engineering (CSE 2012), pp. 79–86 [83] Pirkelbauer, P., Parent, S, Marcus, M, Stroustrup, B: Runtime Concepts for the C++ Standard Template Library, In Proc of the 2008 ACM Symposium on Applied

Computing, pp. 171–177 [84] Porkoláb, Z.: Functional Programming with C++ Template Metaprograms, in Proc of Central European Functional Programming School, Revised Selected Lectures, Lecture Notes in Computer Science, 6299, pp. 306–353 [85] Porkoláb, Z., Sipos, Á, Pataki, N: Parametrikus polimorﬁzmus a modern programozási nyelvekben, A GAMF Közleményei XXI (2007), pp. 25–31 [86] Porkoláb, Z., Sipos, Á, Pataki, N: Inconsistencies of Metrics in C++ Standard Template Library, In Proc. of 11th ECOOP Workshop on Quantitative Approaches in Object-Oriented Software Engineering QAOOSE Workshop, ECOOP 2007, Berlin, pp. 2–6 [87] Reis, G. D, Järvi, J: What is Generic Programming?, in Proc of the First International Workshop on Library-Centric Software Design (LCSD ’05), pp. 1–10 [88] Reppy, J., Turon, A: Metaprogramming with Traits, In Proc of European Conference on Object-Oriented Programming (ECOOP 2007), Lectures Notes in Computer Science 4609, pp. 373–398

[89] Siek, J., Taha, W: A Semantic Analysis of C++ Templates, In Proc of European Conference on Object-Oriented Programming (ECOOP 2006), Lectures Notes in Computer Science 4067, pp. 304–327 [90] Singler, J., Sanders, P, Putze, F: The Multi-Core Standard Template Library, In Proc. of 13th International Euro-Par Conference, Lectures Notes in Computer Science 4641, pp. 682–694 Irodalomjegyzék 129 [91] Smaragdakis, Y., Bathory, D: Mixin-Based Programming in C++, in Proc. of Generative and Component-Based Software Engineering (GCSE) 2000, Lecture Notes in Computer Science 2177, pp. 164–178 [92] Stroustrup, B.: A C++ programozási nyelv, Kiskapu Kiadó (2000) [93] Stroustrup, B.: A Rationale for Semantically Enhanced Library Languages, in Proc of of the First International Workshop on LibraryCentric Software Design (LCSD ’05), pp 44–52 [94] Stroustrup, B.: Simplifying the use of concepts, Technical Report N2906=09-0096, ISO/IEC JTC 1, Information Technology, Subcommittee

22, Programming Language C++, June 2009. [95] Stroustrup, B., Reis, G D: Concepts – design choices for template argument checking, Technical Report N1522=03-0105, ISO/IEC JTC 1, Information Technology, Subcommittee 22, Programming Language C++, October 2003. [96] Sutton, A., Holeman, R, Maletic, J I: Identiﬁcation of Idiom Usage in C++ Generic Libraries, in Proc. of the 2010 IEEE 18th International Conference on Program Comprehension (ICPC ’10), pp. 160–169 [97] Szűgyi, Z., Klár, G: Generating Member Functions and Operators by Tagged Fields in a C++, in Proc. of the Eleventh International Conference on Informatics, Informatics 2011, pp. 96-99 [98] Szűgyi, Z., Pataki, N: Sophisticated Methods in C++, in Proc of International Scientiﬁc Conference on Computer Science and Engineering (CSE 2010), pp. 93–100 [99] Szűgyi, Z., Pataki, N: A More Eﬃcient and Type-Safe Version of FastFlow, in Proc. of Workshop on Generative Technologies (WGT 2011), pp. 24–37 [100]

Szűgyi, Z., Pataki, N: Generative Version of the FastFlow Multicore Library, Electronic Notes in Theoretical Computer Science 279(3), pp. 73–84. [101] Szűgyi, Z., Pataki, N, Mihalicza, J: Subtle Methods in C++, Acta Electrotechnica et Informatica, Vol. 11(3), pp 11–16 [102] Szűgyi, Z., Pataki, N, Mihalicza, J, Porkoláb, Z: C++ Method Utilities, in Proc of the Tenth International Conference on Informatics (Informatics 2009), pp. 112–117 130 Irodalomjegyzék [103] Szűgyi, Z., Pataki, N, Porkoláb, Z: Towards More Scalable C++ Concept Maps, in Proc of the 12th Symposium on Programming Languages and Software Tools (SPLST) 2011, pp. 8-19 [104] Szűgyi, Z., Sinkovics, Á, Pataki, N, Porkoláb, Z: C++ Metastring Library and its Applications, in Proc of Generative and Transformational Techniques in Software Engineering 2009, Lecture Notes in Computer Science 6491, pp. 461–480 [105] Szűgyi, Z., Török, M, Pataki, N: Towards a Multicore C++ Standard Template

Library, in Proc. of Workshop on Generative Technologies (WGT 2011), pp. 38–48 [106] Szűgyi, Z., Török, M, Pataki, N: Multicore C++ Standard Template Library in a Generative Way, Electronic Notes in Theoretical Computer Science 279(3), pp. 63–72 [107] Szűgyi, Z., Török, M, Pataki, N, Kozsik, T: Multicore C++ Standard Template Library with C++0x, in AIP Conf. Proc Vol 1389, NUMERICAL ANALYSIS AND APPLIED MATHEMATICS ICNAAM 2011: International Conference on Numerical Analysis and Applied Mathematics, pp. 857-860 [108] Szűgyi, Z., Török, M, Pataki, N, Kozsik, T: High-level Multicore Programming with C++11, in Computer Science and Information Systems (ComSIS) 9(3), pp. 1187–1202 [109] Torgersen, M.: The Expression Problem Revisited – Four New Solutions Using Generics, in Proc of European Conference on ObjectOriented Programming (ECOOP) 2004, Lecture Notes in Computer Science 3086, pp. 123–143 [110] Tucker, A., Noonan, R: Programming Languages – Principles and

Paradigms, McGraw-Hill (2002). [111] Vandervoorde, D., Josuttis, N M: C++ Templates – The Complete Guide, Addison-Wesley (2003). [112] Van Wyk, E., Borin, D, Huntington, P: Adding Syntax and Static Analysis to Libraries via Extensible Compilers and Language Extensions, in Proc. of the Second International Workshop on LibraryCentric Software Design (LCSD ’06), pp 35–44 Irodalomjegyzék 131 [113] Wang, C.: Integrating Tools and Methods for Rigourous Analysis of C++ Generic Library Components (PhD Thesis) [114] Wang, C., Musser, D R: Dynamic Veriﬁcation of C++ Generic Algorithms, IEEE Transaction on Software Engineering 23(5), pp 314–323 [115] Wegner, P.: Dimensions of Object-Based Language Design, SIGPLAN Notices 22(12), (1987). pp 168–182 [116] Zenger, M., Odersky, M: Independently Extensible Solutions to the Expression Problem (Tech. Rep IC/2004/33) [117] Zolman, L.: An STL message decryptor for visual C++, C/C++ Users Journal 19(7) (2001), pp. 24–30 [118]

Zólyomi, I., Porkoláb, Z: Towards a General Template Introspection Library, in Proc. of Generative Programming and Component Engineering: Third International Conference (GPCE 2004), Lecture Notes in Computer Science 3286, pp. 266–282 A. Függelék Az STL bővı́tése a C++11-ben A.1 Konténerek Az új C++ szabvány előı́rja a következő rendezetlen asszociatı́v tárolókat: az unordered set-et, az unordered multiset-et, az unordered map-et és az unordered multimap-et. Ez utóbbi kettő a hası́tótábla (hashtable) adatszerkezeteket hivatott biztosı́tani, mı́g az előző kettő szintén hası́tással működő hatékony elemlekérdezést biztosı́tó konténerek, amelyek csak forward iterátorral rendelkeznek. Az új C++ szabvány továbbá igényli a forward list adatszerkezetet. Ez a konténer a szokásos, kétirányú list-től annyiban különbözik, hogy egyirányú, ı́gy a tárolása kevesebb heap

memóriát igényel, viszont csak forward iterátora van és kevesebb műveletet támogat (hatékonyan) a list műveletei közül. A régi tömbök lecserélésére bevezetésre bekerült a speciﬁkációba az array konténer. Ez ellentétben a C tı́pusú tömbökkel STL-jellegű interface-t kapott Az array mérete sablonparaméter, azaz fordı́tás-idejű adat, ami nem változhat meg futási időben. A.2 Algoritmusok A C++11 új algoritmusokat is bevezetett az STL-be. Néhány korábban hiányolt algoritmus mellett bekerült az std::initializer list és a ,,move” szemantika támogatása is. Az új algoritmusok között vannak, melyek a predikátumokat teljesülését ellenőrzik az intervallum elemein: all of, any of, none of. Vannak új algoritmusok, amelyek a rendezettséget, illetve a heap-tulajdonságot ellenőrzik az input intervallummal kapcsolatban: is sorted és 132 Az STL bővı́tése a C++11-ben 133 is

sorted until, illetve is heap és is heap until. Az is sorted until megvizsgálja, hogy az input intervallum elejétől kezdve melyik elemig rendezettek az elemek. Az is sorted eldönti az input intervallumról, hogy rendezett-e. Ezt az algoritmust már a saját megoldásomban ki használtam (V.5) Eredeti megoldásomban még az algoritmust magam implementáltam [79]. A partı́ciónálással kapcsolatban is kerültek új STL algoritmusok a C++ szabványba: is partitioned, partition copy, partition point. Szabványossá válik az eredeti HP STL implementációjának copy if algoritmusa is. A többi másolási algoritmus az új C++ szabvány szerint: copy n, uninitialized copy n, partial sort copy. Az iota algoritmusa olyan intervallumot hoz létre, amiben egy kezdőértéktől kezdve eggyel növekvő értékek állnak egymás után. A régi tömbök elemekkel történő inicializálásához hasonlóan az STL konténerek is

létrehozhatóak megadott elemekből. Ehhez bevezetésre került az initializer list sablon. Például az alábbi objektum létrehozása az initializer list-et fogadó konstruktorát hı́vja a konténernek: std::vector<int> v = { 3, 2, 7, 5 }; A minimum- és maximumkiválasztás lehetőségei is bővültek: lehet alkalmazni initializer list-en is a min és max-ot. A szimultán minimum és maximum kereséshez a minmax és minmax element algoritmusok nyújtanak hatékony megoldást. Az új szabvány jobbérték referencia fogalmával bevezetésre került a ,,move” szemantika. A másoló műveleteknél általában a másolandó objektum nem változik meg. (Kivételként emlı́thető például az auto ptr, ami pont ezen tulajdonsága miatt nem használható STL konténerekben.) A move szemantikát az auto ptr másolásával lehet párhuzamba állı́tani: a paraméter az átmozgatás végeztével nem kell hogy

megegyezzen a lemásolt objektummal. Ez a szemantika a másolásnál hatékonyabban alkalmazható, amikor például temporáris objektumokkal dolgozunk. A move szemantika támogatásához az STL-be új algoritmusok kerültek: move és move backward, ami az input intervallumot az output-ba mozgatja. A.3 Iterátorok A legjelentősebb változás az iterátorokkal kapcsolatban, hogy a konténerek interface-e eltér az előző szabványétól: a konténereknek biztosı́taniuk kell külön tagfüggvényeket különböző tı́pusú iterátorok létrehozásához: például a cbegin metódus const iterator-ral tér vissza, ami a konténer első elemére 134 Az STL bővı́tése a C++11-ben hivatkozik, a crbegin pedig const reverse iterator-ral tér vissza. Ezeket az eltérő nevű tagfüggvényeket az auto kulcsszó új működése tette szükségessé. Az auto deklaráció segı́tségével egy változó tı́pusa

fordı́tóprogram által kikövetkeztethető a létrehozás paraméterei alapján. Az auto deklaráció nem működhetne az STL eredeti megvalósı́tásával. A move szemantika támogatásához az STL biztosı́t egy új iterátor átalakı́tót, melynek neve move iterator. Ez annyiban alakı́tja át az eredeti iterátort, hogy dereferáláskor jobbérték referenciával tér vissza, a megszokott referencia helyett. Ha move iterátorokkal hı́vjuk meg a generikus algoritmusokat, akkor a másolásokat áthelyezéssel lehet helyettesı́teni: list<string> s; // . vector<string> v1( s.begin(), send() ); vector<string> v2( make move iterator( s.begin() ), make move iterator( s.end() ) ); Az új C++ szabvány bevezetette az ,,range-for” ciklust. Ezzel bármilyen konténeren, initializer list-en, fordı́tási időben ismert méretű tömbön stb. könnyű végigiterálni: std::vector<int> v; // . for( int& i

: v ) { ++i; } // . for( int i : v ) { std::cout << i << ’ ’; } Ehhez globális begin és end függvényhı́vásokkal derı́ti ki, hogy a ciklus honnan és meddig megy. A begin és end globális függvények túlterheltek a szokásos STL-es konténerekre. Ezekkel a bővı́tményekkel az STL-ben lévő hibalehetőségek megmaradtak, ı́gy a dolgozatomban lévő állı́tások továbbra is igazak

Programozás | Programozás-elmélet » Pataki Norbert - Generatív programok helyessége

Alapadatok

Legnépszerűbb doksik ebben a kategóriában

A programozás elmélete

Fóthi-Steingart - Bevezetés a programozáshoz

Elemi programozási tételek

Aszalós László - Algoritmusok

Tartalmi kivonat

Cikkajánló

Hogyan írjunk szakdolgozatot?

Doksiajánló

Tartalmak

Navigáció

Programozás | Programozás-elmélet » Pataki Norbert - Generatív programok helyessége

Alapadatok

Doksi olvasó beágyazása

Legnépszerűbb doksik ebben a kategóriában

A programozás elmélete

Fóthi-Steingart - Bevezetés a programozáshoz

Elemi programozási tételek

Aszalós László - Algoritmusok

Tartalmi kivonat

Cikkajánló

Hogyan írjunk szakdolgozatot?

Doksiajánló

Tartalmak

Navigáció