Gyakorlati példa - Láncolt lista


Most, hogy már tudjuk mik azok a sablonok elkezdhetünk foglalkozni a C++ Standard Template Library-vel (STL). Én viszont ezt úgy fogom megtenni, hogy a fontosabb konténer típusokat implementálom. Ez azért nagyszerű ötlet, mert sokkal hatékonyabban lehet használni, ha nagyjából tudod, hogy mi van a háttérben. De azért tudd, hogy annyira nem nagyszerű ötlet, mert könnyen lábon lőheted magad (de hát akkor miért C++ -ozol?). Ebben a fejezetben egy láncolt lista sablont fogok összedobni az std::list<T> mintájára.



Először is mi a szabvány: íme. Ez azt mondja, hogy a beszúrás és a törlés konstans idejű kell legyen, az elem elérése viszont lineáris. Ha valaki meg tudja írni ennél jobbra, az ügyes (nem mondtam, hogy nem lehet). Aki meg tudja írni balra is, az már joggal nevezheti magát programozónak. A metódusok listája szintén a linken olvasható. Az egészet a következőképpen strukturáltam:

CODE
// list.hpp #ifndef _LIST_HPP_ #define _LIST_HPP_ namespace mystl { template <typename value_type> class list { // ... }; } #include "list_iterator.hpp" namespace mystl { // implementáció } #endif

Azért csináltam így, hogy az iterátorok implementációja ne foglalja a helyet (átláthatóbb kód). Mielőtt fejest ugranánk ebbe, gondoljuk végig, hogy mit is fog ez művelni. A korábban implementált tömbnél ha be akartál rakni egy új elemet, akkor a többit arrébb kellett tolni (ld. dominó). Itt viszont ilyesmit nem szabad csinálni, garantálni kell a konstans idejű beszúrást.

Volt régen egy nagyon jó kis játék: egy csomó karika, amiket össze lehetett rakni egy láncba. Nyilván ha valahova be akartam rakni egy új karikát, akkor ott szét kellett szedni, majd az első lánc végét és a második lánc elejét hozzácsapni az új karikához. Hasonlóan lehetett eljárni a Lego láncokkal is (már akinek volt technikai legója).

Már majdnem meg is van, hogy mit kéne csinálni: ilyen láncszemeket rakni össze pointerekkel.

CODE
struct link { value_type value; link* next; };

Na jó jó, de állítólag hátrafelé is kell tudnunk iterálni. Semmi gond, akkor tároljuk el az előző elemre mutató pointert is. Így a lista már kétirányú (bidirectional). Ez már jó lesz láncszemnek, de az összerakás még nem világos.

Ha a lista végére szeretnék beszúrni, akkor tudnom kell, hogy hol a vége. Ha az elejére, akkor tudnom kell hol az eleje. Legrosszabb esetben ez két pointert jelent: first és last. Fölösleges azonban két pointer, mert egy is elég, és az ezt megelőző elem legyen az utolsó. Innentől a lista ciklikus.

De még mindig lehet optimalizálni a dolgon, ha a listát fejelemessé tesszük. Legyen a neve head és ennek az érték mezőjét nem használja semmire. Egy csomó dolog egyszerűbb így, például az üres lista esetén head->next == head->prev == head, azaz nem kell külön feltételt vizsgálni beszúráskor. A lista sablon tehát a következőképpen fest:

CODE
template <typename value_type> class list { protected: struct link { value_type value; link* next; link* prev; }; link* head; size_t mysize; public: typedef value_type value_type; class iterator; class const_iterator; // ... };

A fejelemet a konstruktorban hozom létre és a destruktorban szabadítom fel. Lehetne egy külön destroy() metódust is csinálni, és akkor nem lesznek fura memory leakek globális változókkal sem (feltéve hogy a júzer meghívja). Én inkább úgy írom meg a destruktort, hogy kockázat nélkül hívható legyen kézzel is (ez az STL-el viszont nagyon nem ajánlott mert szinte biztos, hogy elszáll).

CODE
template <typename value_type> list<value_type>::list() { head = new link(); head->next = head->prev = head; mysize = 0; } template <typename value_type> list<value_type>::~list() { if( head ) { clear(); delete head; head = NULL; } }

Lesznek majd más konstuktorok is, ott is hasonlóan kell eljárni (de konstuktor nem hívhat másik konstruktort!).


Ennyi sok nehézség után jöjjön valami egyszerű dolog: bepakolás a lista végére és az elejére. A fejelem azt jelenti, hogy az első elem az ő rákövetkezője. Tehát az új első elemet a fejelem és a régi első elem közé kell berakni. Ez mindössze annyit jelent, hogy az új láncszemnek be kell állitani a prev és next változóit, illetve a fejelemet és a régi első elemet updatelni kell. A sorrend viszont nem mindegy:

CODE
template <typename value_type> void list<value_type>::push_front(const value_type& item) { link* first = head->next; head->next = new link(); head->next->prev = head; head->next->next = first; head->next->value = item; first->prev = head->next; ++mysize; }

Először is egy átmeneti pointerrel megfogjuk a régi első elemet, majd létrehozzuk az újat (rögtön ott ahol kell). Ezután már csak néhány állítgatás következik, de tipikusan mindig kimarad valami, ezért érdemes ötször átnézni. A végére való beszúrás teljesen hasonló elven működik, legyen höfö.

Most egy sokkal nehezebb dolog fog jönni, amit már alig lehet érteni: vegyünk ki egy elemet a lista végéről. Visszaadni nem kell, csak kivenni.

CODE
template <typename value_type> void list<value_type>::pop_back() { myerror(, "list::pop_back(): container is empty", mysize > 0); link* last = head->prev; head->prev = last->prev; last->prev->next = head; delete last; --mysize; }

Húha, mi az a myerror? Csak egy makró, hogy mégse szállogasson el a konténer, de azért diszkréten megböködje a júzert, ha üres listából akar elemet kivenni. Mi történik itt? Jobb kézzel megfogjuk az utolsó elemet, bal kézzel átláncoljuk a dolgokat, a kivett karikát pedig visszük kidobni.



Gyengébb idegzetűek most ne nézzenek ide.

CODE
inline bool empty() const { return (mysize == 0); }

Én szóltam.


Egy csomó tökjó metódus van még, de előbb implementáljunk egy iterátort (mégiscsak kellemesebb lesz a tesztelés). Hát az meg milyen állat? Egy mezei tömbön végig lehet szaladni for ciklussal, a tömböt a ciklusváltozóval indexelve. Valami hasonlót szeretnénk csinálni a lista esetében is.

A listában egy elem elérése lineáris, azaz nem lehet egy lépésben hivatkozni például a harmadik elemre. Ha viszont csak végig akarok menni az elemeken, akkor használható a háttérben levő lánc. Például for( link* pi = head->next; pi != head; pi = pi->next ) lehetne a ciklus. A baj csak az, hogy a lánc privát.

Az STL-ben egy egységes módszer a bejárásra az iterátor. Majdnem minden konténer típusnak van iterátora, sőt ezeket egységesen iterátornak hivja. Például std::list<T>::iterator vagy std::set<T>::iterator. Ami közös ezekben (amellett, hogy böszme soká tart leírni), hogy lehet őket növelni a ++ operátorral, illetve el lehet kérni az általuk mutatott elemet a * vagy -> operátorral.

CODE
template <typename value_type> class list<value_type>::iterator { friend class list; private: list* container; link* ptr; iterator(list* l, link* n) : container(l), ptr(n) {} public: typedef value_type& reference; typedef value_type* pointer; iterator() : container(NULL), ptr(NULL) {} // ... };

Ami egy fontos dolog, hogy két különböző konténer iterátorai inkompatibilisek kell hogy legyenek. Ezért az iterátorban eltároltam, hogy ki az ő listája, és ezt csak egy lista tudja majd megmondani az iterátornak. A metódusok implementációja elég egyértelmű, úgyhogy én most hibakezelés nélkül írom ide:

CODE
inline reference operator *() const { return ptr->value; } inline pointer operator ->() const { return &ptr->value; }

A csillag operátorral lehet írni/olvasni az aktuális elemet, például *it = Alma(), a nyíl operátorral pedig olyan lesz az iterátor, mintha nemis iterátor lenne, csak az elemre mutató pointer (it->Leszed()).

Találós kérdés: hogyan különböztetjük meg a prefix (++it) és a postfix (it++) növelő operátorokat? Valószínűleg a nyelv alkotójában is felmerült ez a kérdés, mert az alábbi elég érdekes módon oldotta meg:

CODE
inline iterator& operator ++() { ptr = ptr->next; return *this; } inline iterator operator ++(int) { iterator tmp = *this; ptr = ptr->next; return tmp; }

Nagyon nem jó összekeverni a kettőt! Az viszont feltűnhet, hogy a prefix ++ gyorsabb, mint a másik (hiszen nem hoz létre temporáris változót) és ezért használom mindig azt.

A többi metódust bárki ki tudja találni (ha nem akkor ott a kód), sőt valószínüleg a const_iterator-t is bárki meg tudja írni ezek után. Némely implementáció a rendes iterátort a const_iterator-ból származtatja.


Minden készen áll ahhoz, hogy megírjuk az insert és az erase metódust a listához. A fentiek tekintetében csak nem lehet olyan nehéz. Ugye?

CODE
template <typename value_type> typename list<value_type>::iterator list<value_type>::insert( const iterator& pos, const value_type& value) { mynerror(end(), "list::insert(): iterator invalid", pos.container != this); link* q = pos.ptr->prev; q->next = new link(); q->next->next = pos.ptr; q->next->prev = q; pos.ptr->prev = q->next; q->next->value = value; ++mysize; return iterator(this, q->next); }

Hoppá, mi az a typename ott elöl? Képzeljük el, hogy mi vagyunk a C++ fordító és megkapjuk ezt a kódot typename nélkül és épp most olvassuk azt, hogy list<value_type>::iterator. Ez egy minősitett név (qualified), ráadásul függ egy template paramétertől is (dependent). Hasonlitsuk össze az alábbi két lehetséges implementációt:

CODE
template <typename value_type> class list { public: typedef value_type::valami iterator; };
CODE
template <typename value_type> class list { public: int iterator; };

Az első esetben az iterator név ténylegesen függ a template paramétertől, a második esetben nem. Abból viszont, hogy list<value_type>::iterator ez abszolút nem derül ki, csak majd példányosításkor! Azaz a fordítónak fogalma nincs, hogy hogyan értelmezze ezt a nevet. Nadehát milyen buta már, hiszen nyilvánvaló, hogy itt típus kell legyen. Aha. És itt?

CODE
int it; template <typename T> void foo() { T::iterator * it; }

Éppen ezért a szabvány szerint, ha nincs kint a typename kulcsszó, akkor az ilyen minősitett függő neveket a fordító nem típusként (hanem pl. változóként) kell értelmezzen. Még akkor is ha ebből fordítási hiba lesz. Még akkor is ha egyébként tudja, hogy mi kéne legyen. Mert ilyen szemét.


Még egy fontosabb metódus van hátra, a clear(). Hogyan szoktuk elpakolni a dominókat? Megfogsz egyet és rárakod a mellette levőre. Aztán azt a kettőt fogod meg és rárakod a következőre, stb. Ha elég dominó összegyűlt, akkor berakod a dobozba.

Ezzel szemben hogy pakolsz el egy láncot? Megfogod és berakod a dobozba úgy ahogy van mindenféle memory leaket hagyva magad után. Kultúráltabb emberek úgy hagyják hátra a memory leaket, hogy a head-et azért kitörlik, hogy legalább elszálljon a program.

A cél az, hogy úgy pakoljuk el a láncot is, mint a dominót. Fogjuk meg az első láncszemet és pakoljuk rá a következőre.

CODE
template <typename value_type> void list<value_type>::clear() { link* q = head->next; link* p; while( q != head ) { p = q; q = q->next; delete p; } head->next = head->prev = head; mysize = 0; }

A különbség, hogy nem visszük magunkkal mindig az összes dominót, hanem egy laza kézmozdulattal beleejtjük a legalsót a dobozba.


A visszamaradt metódusokat mindenki megnézi a kódban. Ami feltűnő, hogy az egyik konstruktor előtt ott van az explicit kulcsszó. Ez mindössze annyit jelent, hogy ez a konstruktor nem használható implicit konverziókkal (például Alma a = 5; nem fog menni, ha a megfelelő konstruktor explicit).

Most viszont következzen a fekete leves: tesztelés. Nem lehet elég jó teszteket írni, ezért egy csomó segéd makrót csináltam. Például ha valaminek nem az az értéke amit én akarok, akkor kiír egy kedves üzenetet a konzolba.

CODE
#define ASSERT(x) { \ if( !(x) ) { std::cout << "ASSERTION FAILED: " << #x << "\n"; } } // ... mystl::list<int> l1; l1.push_back(10); l1.push_back(5); l1.push_back(1); l1.push_back(-7); l1.push_back(8); ASSERT(l1.front() == 10); ASSERT(l1.back() == 8);

Így jó eséllyel kiderül ha valamit elbaltáztam. Különösen fontos tesztelni a copy konstruktort és az értékadást:

CODE
mystl::list<int> l2(l1); mystl::list<int> l3; l3.push_back(34); l3.push_back(11); ASSERT(l2.front() == l1.front()); ASSERT(l2.back() == l1.back()); ASSERT(l3.back() == 11);

Az egyéb metódusokra ráengedhetsz akár egy kész programot is, hogy használja ezt. Ha jól irtad meg a hibakezeléseket, akkor tudod hol kell még javítani.


Ebben a fejezetben egy implementáción keresztül mutattam be az std::list<T> konténert. Ezzel a listával már elég jól el lehet játszadozni, például implementálható vele a sor vagy a verem adatszerkezet is.

A kód elérhető itt.


Höfö:

  • Írj a listához reverse_iterator-t (és a konstans párját is)!
  • Írj a listához remove_if(const value_type& value, const condition& cond) metódust! A feltétel objektum az operator () metódusán keresztül kapja meg az elemet amire a feltételt vizsgálnia kell!

Irodalomjegyzék

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

back to homepage

Valid HTML 4.01 Transitional Valid CSS!