Iterátorok, generikus algoritmusok

Az előző fejezetben láttuk, hogyan tudunk úgy tárolót írni, hogy a tárolt típust tulajdonképpen nem ismerjük, bármi lehet. Ebben a fejezetben azt nézzük meg, hogyan lehetséges, hogy egyes algoritmusaink bármilyen tárolón ugyanúgy tudnak dolgozni.

A bejárás alapproblémája

Első feladat: írjuk ki egy tömb minden elemét!

Ezt naivan egy int i ciklusváltozóval és indexeléssel tennénk meg első nekifutásra. Ehelyett alább egy pointert használunk ciklusváltozónak, a téma szempontjából sokkal tanulságosabb.

int tomb[100]; // valaki feltölti

int * iter;
for (iter = tomb; iter != tomb + 100; ++iter)
    std::cout << *iter << std::endl;

Második feladat: tegyük meg ugyanezt egy egyszeresen láncolt listával! Ezt C-ből jól ismerjük, de a példában már kicsit C++-osítottuk.

Lista lista; // valaki feltölti

ListaElem * iter;
for (iter = lista.eleje; iter != NULL; iter = iter->kov)
    std::cout << iter->adat << std::endl;

Hasonlítsuk össze a két bejárást! Mi a közös a két tároló bejárásában, és miben térnek el?

A két tároló elemeivel ugyanazokat csináljuk, csak teljesen máshogy.

A ciklusváltozók – a tömbnél az int * iter, a listánál a ListaElem * iter – ennyit "tudnak". Ezeket léptetni lehet (1), és elérni rajtuk keresztül az aktuális elemet (2).

A tárolókhoz tartozik a (3)-as és a (4)-es művelet. Egyrészt elkérjük az első elemet, hogy el tudjuk kezdeni a bejárást. Ez a listánál szépen látszik, már az elején feltűnt, hogy nem triviális. A tömbnél elsőre nem látszik, hogy mi történik, csak ha alaposan megnézzük: iter = tomb igazából iter = &tomb[0], tehát létrejött egy pointer, ami a tömb elejére mutat. Másrészt elérjük a tároló végét. Konvenció szerint ez az utolsó utáni elemet jelenti. Tömbnél ez tomb + 100, láncolt listánál ebben az esetben konstans NULL.

Vegyük észre, hogy a tömbnél és a listánál logikailag pontosan ugyanaz történt, de gyakorlatilag teljesen máshogy. A ciklusváltozón ugyanazok az elvégezhető műveletek, de más implementációval. Azért, hogy ugyanúgy lehessen használni a különböző tárolók ciklusváltozóit, az implementációs különbségeket osztályok belsejébe szokták elrejteni. Nézzük meg, hogyan.

A fenti műveleteket megvalósító osztályokat hívják iterátoroknak. A műveleteket a pointerek alapján nevezték el. Így egyrészt konzisztens, másrészt kompatibilis a használatuk.

• Két iterátort össze lehet hasonlítani az == és != operátorokkal.
• A léptetésre a ++ operátor való.
• A mutatott elem elérése a * operátorral lehetséges.

Bejárás iterátorokkal

A C++ beépített tárolói mind rendelkeznek iterátorokkal. A szabványos tárolók elejét és végét a begin és end tagfüggvényekkel érhetjük el. Az iterátor típusa konvenció szerint a tároló osztály belsejében definiált típus (angolul nested type). Például egy std::vector<int> bejárását így is lehet írni:

std::vector<int> szamok; // valaki feltölti

std::vector<int>::iterator iter;
for (iter = szamok.begin(); iter != szamok.end(); ++iter)
    std::cout << *iter << std::endl;

Figyeljük meg alaposan az egyes elemeket!

• Az iterátor típusa std::vector<int>::iterator.
• A tároló begin és end tagfüggvényei visszaadnak egy-egy iterátort: vec.begin(), vec.end().
• Az iterátorokat lehet egymással összehasonlítani: iter != vec.end(), egy iterátort lehet léptetni: ++iter és elkérni a tárolt elemet: *iter.

Erősen ajánlott a saját tárolóink és iterátoraink függvényeit pontosan ugyanígy nevezni, a többi fejlesztő lelki nyugalmának és a saját testi épségünknek az érdekében. Ha nem így teszünk, a tárolókat sokkal nehezebb lesz használni, és az STL algoritmusok sem használhatók rajta.

Ha írunk a saját listánknak is iterátort, akkor azt így kell majd bejárni:

Lista<int> szamok; // valaki feltölti

Lista<int>::iterator iter;
for (iter = szamok.begin(); iter != szamok.end(); ++iter)
    std::cout << *iter << std::endl;

A fentihez képest tehát pontosan ugyanúgy kell majd csinálni a bejárást, mint az std::vector-nál. Pusztán a típus nevét kell megváltoztatnia az azt használó kódnak! Hát nem csodálatos? De. Ez teszi majd lehetővé, hogy a tároló típusától független algoritmusokat írhassunk.

std::vector<int>::iterator iter;
for (iter = vec.begin(); iter != vec.end(); ++iter)
    std::cout << *iter << std::endl;

for (int *iter = std::begin(tomb); iter != std::end(tomb); ++iter)
    std::cout << *iter << std::endl;

std::vector<std::string>::iterator it = strvec.begin();

auto x = 5;         // x = int lesz

int i;
auto& j = i;        // int& j = i;

int *foo();
auto k = foo();     // int *k = foo();
auto *l = foo();    // int *l = foo();

for (auto iter = vec.begin(); iter != vec.end(); ++iter)
    std::cout << *iter << std::endl;

for (auto iter = std::begin(tarolo), iter_end = std::end(tarolo); iter != iter_end; ++iter) {
    const auto& elem = *iter;
    std::cout << elem << std::endl;
}

for (const auto& elem : tarolo)
    std::cout << elem << std::endl;

for (int elem : tarolo)
    std::cout << elem << std::endl;

Prog1-ből egy teljes listát általában egy ListaElem* típussal írtunk le, az üres lista pedig NULL volt. Ez szemantikailag zavaró lehet, sosem szerencsés egy típusra több feladatot (Lista és Listaelem) bízni. Erre már több példát láttunk (char[] avagy std::string, bool vs. int, NULL és nullptr). Ha a listánál maradunk, akkor is előfordulnak problémák:

ListaElem * Lista_beolvas(char const * fajlnev);
ListaElem * Lista_keres(ListaElem * miben, int mit);

Az első függvény egy teljes listát ad vissza, amire majd meg kell hívnunk a felszabadító függvényt. A második függvény első argumentumának szintén teljes listát vár, de a visszatérési érték nem teljes lista, és nem kell felszabadítanunk, mert a listához tartozik.

A két zöld doboz, a Lista és a ListaElem tehát szemantikailag különbözik, ezért meg kell őket különböztetni. A fenti megoldásban a ListaElem globális típus sem a legszerencsésebb. A Lista használójának nincs szüksége a ListaElem-re, egyedül a bejárásnál használjuk, viszont ott épp most készülünk iterátorral helyettesíteni. Tehát csak zavaró, hiszen miért van ott, ha nincs vele dolgunk. Ráadásul ha valaki más akar írni egy ezektől független ListaElem típust, azt a nevet már elfoglaltuk, teljesen feleslegesen. (Ezt a jelenséget namespace pollution-nek nevezzük.)

Erre találták ki a belső osztály (nested class) nyelvi elemet. Csak annyiban tud többet egy független osztálytól, hogy belelát a tartalmazó osztály (esetünkben a Lista) privát tartalmába, esetünkben látja az eleje pointert.

C++-ban egy belső osztály definiálása a külső osztály definíciójának belsejében történik:

class Lista {
private:
    struct ListaElem { // belső típus definíciója
        ListaElem * kov;
        int adat;
    };

    ListaElem * eleje; // hivatkozás a típusra

public:

    // tagfüggvények

};

Ebben az esetben a definíció az osztály privát láthatóságú tagja, tehát ha kívülről megpróbáljuk elérni, fordítási hibát kapunk. Ezt egyébként a Lista::ListaElem módon tudnánk megtenni, később erre a szintaktikára szükség lesz.

Alakítsuk át ezt a listát úgy, hogy bármilyen típust tudjon tárolni! Ez C++-ra lefordítva azt jelenti, hogy a tárolt típus legyen template paramétere. Mivel a külső template a teljes lista osztályra vonatkozik, az annak belsejében definiált ListaElem típus is automatikusan template lesz. Ezért ott is használhatjuk a TIPUS paramétert:

template<typename TIPUS>
class Lista {
private:
    struct ListaElem {
        ListaElem * kov;
        TIPUS adat;       // <- TIPUS itt is érvényes!
    };

    ListaElem * eleje;

public:

    // tagfüggvények

};

Alapok

Írjunk a listánknak iterátort! Ez ugyanúgy egy belső osztály, ahogy a ListaElem volt, de ez publikus láthatóságú. A begin és end ilyen iterátorokkal tér vissza. Emlékeztetőképp, ennek a kódnak kell működnie:

Lista<int> szamok; // valaki feltölti

Lista<int>::iterator iter;
for (iter = szamok.begin(); iter != szamok.end(); ++iter)
    std::cout << *iter << std::endl;

template<typename TIPUS>
class Lista {
private:
    struct ListaElem {
        ListaElem * kov;
        TIPUS adat;
    };

    ListaElem * eleje;

public:

    class iterator {
        // ...
    };

    iterator begin(); // a begin és end a tárolóé!
    iterator end();

    // tagfüggvények

};

A Lista iterátorának itt szüksége van a Lista privát tartalmára, hiszen a ListaElem típus is az. Ezt az iterátort arra használjuk, amire C-ben a ListaElem*-ot használtuk, tehát az iterátor műveleteinek a megvalósításához belül elegendő egy ListaElem*-ot tárolni. Valahogy így:

template<typename TIPUS>
class Lista {
private:
    ListaElem * eleje;

public:

    class iterator {

        ListaElem * elem;

    public:
        iterator(ListaElem * elem = NULL)
            : elem(elem) {
        }

        iterator& operator++() {
            if (elem != NULL)
                elem = elem->kov;
            return *this;
        }
        iterator operator++(int) {
            iterator masolat = *this; // !
            ++(*this);
            return masolat;
        }

        TIPUS& operator*() const {
            return elem->adat;
        }

        bool operator==(iterator rhs) const {
            return elem == rhs.elem;
        }
        bool operator!=(iterator rhs) const {
            return elem != rhs.elem;
        }
    };

    iterator begin() {
        return iterator(eleje);
    }

    iterator end() {
        return iterator(NULL);
    }
};

A fenti táblázatunk így egészül ki az iterátorokkal:

Pre- és posztinkremens operátorok

Nézzük meg kicsit jobban az iterator pre- és posztinkremens operátorait!

iterator& operator++() {
    if (elem != NULL)
        elem = elem->kov;
    return *this;
}

iterator operator++(int) {
    iterator masolat = *this; // !
    ++(*this);
    return masolat;
}

A posztinkremens operátornál itt is új objektummal kell visszatérni, illetve a régi másolatával, éppúgy, ahogy a Tort-nél megtanultuk. Ez a tény viszont egy fontos aprósággal ismertet meg minket. Mi a különbség a kettő között?

Lista<int>::iterator iter;

for (iter = lista.begin(); iter != lista.end(); ++iter)
    // ...

for (iter = lista.begin(); iter != lista.end(); iter++)
    // ...

Ha az iterátor egy egyszerű pointer lenne, beépített típus lévén ugyanazt jelentené a kettő. Itt viszont ez függvényhívás, és a fordító nem csereberélheti a kettőt. A preinkremens operátor csak a következőre lépteti, míg a posztinkremens először lemásolja, majd lépteti, aztán visszaadja a másolatot, és a végén eldobja a másolatot. Ezért lehet a preinkremens operátor hatékonyabb, mint a posztinkremens, így ha nem használjuk fel a visszatérési értéket, érdemes / illik az előbbit használni. (Az inlining és egyéb optimalizálási trükkök után persze eléggé valószínű, hogy a kettő lefordítva ugyanaz lesz.)

Nyíl operátor

Vizsgáljuk meg egy példán keresztül az iterátoroknál használt nyíl operátort is! A feladat: összegeznünk kell egy listában tárolt összes sztring hosszát.

Lista<std::string> strvec; 
// valaki feltölti

Lista<std::string>::iterator it;
int sum = 0;
for (it = strvec.begin(); it != strvec.end(); ++it)
    sum += (*it).size();

Az iterátor (it) egy pointer szemantikájú objektum, pointerként viselkedik, ugyanúgy tudjuk használni. Ezt operator overloading-gal értük el, és egyvalami még hiányzik a listából. A (*it).size() kifejezést még leírni is fáj, jó lenne, ha a nyíl operátorral elérnénk az általa mutatott objektum tagváltozóit, tagfüggvényeit, ahogy egy sima pointernél is: it->size(). Ha egy objektumunk pointerként viselkedik, a csillag operátort overload-oljuk, akkor a konzisztencia érdekében illik a nyíl operátort is.

A nyíl operátor egy érdekes állatfaj, egyedülálló a működése a többi operátorhoz képest. Ugyanis amit mi visszaadunk az operator-> függvényből, arra a fordító ismét alkalmazza a nyíl operátort. Például az alsó két sor ekvivalens:

std::size_t s1 = it->size();
std::size_t s2 = (it.operator->()) ->size();

Tehát a nyíl operátornak egy pointert kell visszaadnia, amire a nyíl operátort még egyszer alkalmazva érhetjük el azt a tagot, amit szeretnénk, itt például std::string osztály size tagfüggvényét.

A Lista<T>::iterator osztályunkat kiegészítve ez így fog kinézni:

template<typename TIPUS>
class Lista {
private:
    // ...
    struct ListaElem {
        ListaElem * kov;
        TIPUS adat;
    };

public:
    class iterator {
        ListaElem * elem;
    public:
        TIPUS* operator->() const {
            return &(elem->adat);
        }

        // minden más marad a régiben
    };

};

Ezután ha std::string-et tárol a lista, akkor it->size() működni fog rajta. Viszont ha valaki egy Lista<int>-et példányosít, akkor a fordítási szabályok miatt egészen addig nem okoz fordítási hibát a nyíl operátor, amíg valaki nem próbálja meg használni, akkor viszont fordítási hibának kell lennie – hiszen egy int-nek nincsenek tagfüggvényei.

const_iterator

Írjunk függvényt, ami egy Lista<int> minden elemét megduplázza!

void Lista_duplaz(Lista<int>& lista) {
    Lista<int>::iterator it;
    for (it = lista.begin(); it != lista.end(); ++it)
        *it *= 2;
}

Írjunk olyan függvényt, ami minden elemet kiír a szabványos kimenetre!

void Lista_kiir(Lista<int> const& lista) {
    Lista<int>::iterator it = lista.begin(); // <- ERROR
    for ( ; it != lista.end(); ++it)
        std::cout << *it << std::endl;
}

Ez a függvény hibás. A listát konstans referencia szerint vettük át, hogy ne kelljen lemásolni, de változtatni nem akarunk rajta. A begin tagfüggvény viszont nem konstans minősítésű, ezért konstans tárolón nem lehet meghívni.

Egy iterator-t visszaadó függvény logikailag nem is lehet const, ugyanis a *it-n keresztül meg kell tudni változtatni a tároló tartalmát, ahogy ezt a Lista_duplaz-nál ki is használtuk. Jó lenne viszont, ha konstans tárolókon is lehetne iterálni és az elemeket olvasni, de a módosítást ilyenkor az iterátor nem engedné. Vagyis iterátor az operator*-jának T const&-et kell visszaadnia. Ez nem lehet ugyanaz a típus, mint az iterator. Ezért a tárolóknak szokott lenni egy const_iterator típusa is, ami csak annyiban különbözik a sima iterator-tól, hogy rajta keresztül nem változtatható meg a tároló tartalma.

template<typename TIPUS>
class Lista {
private:
    // ...

public:

    class iterator { /* ... */ };
    class const_iterator {
    public:

        TIPUS const& operator*() const { // adat;
        }

        TIPUS const* operator->() const { // adat);
        }

        // minden más ugyanolyan, mint az iterator belsejében
    };

    iterator begin() {
        return iterator(eleje);
    }

    iterator end() {
        return iterator(NULL);
    }

    const_iterator begin() const {
        return const_iterator(eleje);
    }

    const_iterator end() const {
        return const_iterator(NULL);
    }
};

Ilyenkor – az indexelő operátornál megismert szabály alapján – ha a tárolót konstansként látjuk, akkor const_iterator-t ad vissza a begin és az end, egyébként iterator-t. Erre sajnos sokszor oda kell figyelni, és C++11-ig nem lehet mindig kikerülni. A helyes függvényünk tehát:

void Lista_kiir(Lista<int> const& lista) {
    Lista<int>::const_iterator it = lista.begin(); // const_iterator!
    for ( ; it != lista.end(); ++it)
        std::cout << *it << std::endl;
}

Iterátorokkal dolgozó függvények

Tarolo_kiir 1.

Írjunk függvényt, ami egy tetszőleges típusú elemeket tartalmazó Lista<TIPUS>-t ki tud írni!

template<typename TIPUS>
void Lista_kiir(Lista<TIPUS> const& lista) {
    typename Lista<TIPUS>::const_iterator it; // typename!
    for (it = lista.begin(); it != lista.end(); ++it)
        std::cout << *it << std::endl;
}

Egyelőre fogadjuk el, hogy a jelölt sor elejére kell egy typename, később lesz magyarázat, hogy pontosan miért.

Ezt így tudjuk meghívni:

Lista<int> lista; // valaki feltölti

Lista_kiir(lista); // <- TIPUS == int

Tarolo_kiir 2.

Az iterátorokat azért találták ki, hogy egymástól teljesen eltérő tárolókat lehessen ugyanúgy kezelni. Az általánosítás előtt nézzük meg a vektort kiíró függvényt:

template<typename TIPUS>
void Vektor_kiir(std::vector<TIPUS> const& vec) {
    typename std::vector<TIPUS>::const_iterator it; // ide is typename!
    for (it = vec.begin(); it != vec.end(); ++it)
        std::cout << *it << std::endl;
}

Itt erősen érezni a sormintaszagot. Annyi történt, hogy ahol eddig Lista volt, kicseréltük std::vector-ra. Tehát a függvényben nemcsak a tárolt típust lehet absztrahálni, hanem magát a tárolót is. A függvény bármilyen TAROLO-t átvehetne:

template<typename TAROLO>
void Tarolo_kiir(TAROLO const& tar) {
    typename TAROLO::const_iterator it; // ide is kell typename!
    for (it = tar.begin(); it != tar.end(); ++it)
        std::cout << *it << std::endl;
}

Tarolo_kiir 3.

Az előző függvénynél már alig van hiányérzetünk, jól működő, kellően általános függvénynek tűnik. Okos emberek rájöttek, hogy még ezen is lehet általánosítani.

• Ez a függvény nem működik tömbökre.

• Bejárja a teljes tárolót, nem mondhatunk olyat, hogy pl. a harmadik elemtől kezdve írja ki.

• Még ha osztályokról van is szó, nem tömbökről, bele van égetve, hogy

  • a begin és end tagfüggvényeket hívja,
  • és az iterator típust használja.

Egy tárolónak nemcsak egyfajta iterátora van. Konstans objektumnál const_iterator-t kellene használni, de léteznek egyéb iterátorok is: például a reverse_iterator hátrafelé járja be a tárolót. Jó lenne, ha a függvényünk ilyen esetben is működne, hiszen a különböző iterátorokat ugyanúgy kell használni.

Viszont ha a függvény nem tárolót, hanem iterátorokat venne át (méghozzá bármilyen típusú iterátorokat), egy csapásra megoldódnak a problémáink. Működni fog különböző tárolók (egyformán használandó) iterátorain, egy tároló különféle iterátorain és tömbökön is.

A bármilyen típusú iterátor azt jelenti C++-ra lefordítva, hogy a függvény template paramétere legyen az iterátor típusa.

template<typename ITER>
void Tarolo_kiir(ITER eleje, ITER vege) {
    for (ITER it = eleje; it != vege; ++it)
        std::cout << *it << ' ';
}

Ez a séma sokkal jobban használhatónak bizonyult, mint az előbbi. A szabványos könyvtár algoritmusai is ilyen paraméterezésűek, és a továbbiakban is ilyen függvényeket fogunk írni. Nézzünk meg egy példát a Tarolo_kiir használatára.

Tarolo_kiir(vec.begin(), vec.end());
Tarolo_kiir(lista.begin(), lista.end());
Tarolo_kiir(tomb, tomb + 100);

Tarolo_eleme_e

Következő feladatként írjunk függvényt, ami egy tetszőleges értékről eldönti, hogy benne van-e egy tárolóban! A keresett érték típusa legyen még egy sablonparaméter, mert az iterátorok típusából macerás lenne kiszedni, és nem is kell. Így lehet vele pl. std::string-et tartalmazó tárolóban char const*-ot keresni.

template<typename ITER, typename T>
bool Tarolo_eleme_e(ITER first, ITER last, T const& value) {
    for (ITER it = first; it != last; ++it)
        if (*it == value)
            return true;
    return false;
}

Tarolo_keres

Alakítsuk át ezt a függvényt úgy, hogy azt is megmondja, hol van a megtalált elem! Egy bool meglehetősen kevés információt tartalmaz. Viszont a return true; sorban már rendelkezésünkre áll a keresett elem helye, az épp a ciklusváltozó.

Mivel térjen vissza a függvény? A megtalált elem indexe nem jó ötlet, láncolt listában lassú az n. elemig elmászni, egy bináris fában pedig abszolút irreleváns lenne a használója számára.

Prog1-ből ilyenkor a megtalált elemre mutató pointerrel tértünk vissza, listában pl. ListaElem*-gal. Ez bármilyen tárolóra általánosítva: az iterátor! Tehát a megtalált elemre mutató iterátorral visszatérve a hívó pontosan tudja, mit jelent az a saját kollekciójában, és mit tud vele kezdeni.

Emlékezzünk vissza, mire mutat az end(): az utolsó utáni elemre, tehát nem egy létező elemre. Ezt vissza lehet adni akkor, ha nem találtuk meg az elemet, és a hívó biztosan nem fogja összekeverni egy érvényes találattal.

template<typename ITER, typename T>
ITER Tarolo_keres(ITER first, ITER last, T const& value) {
    for (ITER it = first; it != last; ++it)
        if (*it == value)
            return it;
    return last;
}

Írjuk ki ennek a függvénynek a segítségével egy std::vector<std::string>-ből a "Tagok:"-tól kezdve az összes elemet!

std::vector<std::string> strvec; // valaki feltölti

std::vector<std::string>::iterator tagok;
tagok = Tarolo_keres(strvec.begin(), strvec.end(), "Tagok:"); // keressük meg a Tagok-at
Tarolo_kiir(tagok, strvec.end()); // és írjuk ki az elemeket Tagok-tól a végéig

Predikátum, komparátor

Tarolo_legvalamilyenebb

Az előző bekezdés szemléletmódjával rengeteg nagyon gyakran használt algoritmust lehet előre megírni, hogy a használat helyén ne éktelenkedjenek ciklusok. Ettől jóval olvashatóbb lesz a kód, a megfelelően elnevezett függvények sokat segítenek.

Vannak olyan feladatok, amik csak további általánosítással szervezhetők ki külön függvénybe. Mi a közös az alábbiakban?

• Keressük meg egy tárolóban a leghosszabb sztringet!
• Melyik az ábécében legelső szó a tárolóban?
• Határozzuk meg, melyik tárolóbeli szám van legközelebb a pi-hez!

Mindegyik egy szélsőértékkeresést sugall, ami meghatározza a tárolóban a legvalamilyenebb elemet. A "valamilyen"-t pedig jó lenne paraméterként átadni, hiszen az algoritmusnak ez nem szerves része, ha nem ismeri, akkor is tud működni.

A "valamilyen" milyen típus? Annyit tudunk róla, hogy meg tudja mondani két azonos típusú micsodáról, hogy melyik a valamilyenebb. Tehát valami, ami igazzal vagy hamissal tér vissza, és két T-t vár paraméternek. C-ben ezt függvénypointerrel oldottuk meg, első megoldásunk ezt használja:

template <typename ITER, typename T>
ITER Tarolo_legvalamilyenebb(ITER eleje, ITER vege, bool (*valamilyenebb)(T, T)) {
    if (eleje == vege)
        return vege;

    ITER leg = eleje;
    ITER i = eleje;
    ++i;
    while (i != vege) {
        if (valamilyenebb(*i, *leg))
            leg = i;
        ++i;
    }
    return leg;
}

Az eleje == vege feltétel magyarázatot érdemel. Ha a két iterátor megegyezik, akkor üres tartományt kaptunk, amiben nincs egy elem sem (hiszen a vege az utolsó utáni elemre mutat, tehát eleje is érvénytelen). Az eddigi algoritmusainknál nem kellett erre külön figyelni, hiszen ilyenkor a for ciklus magja egyszer sem futott le, a return vege; adta vissza a megfelelő iterátort. Könnyű átgondolni, hogy ez az algoritmus ennek hiányában elszállna a ciklus előtti ++i sornál.

A fenti három feladatot például így lehet megoldani a Tarolo_legvalamilyenebb felhasználásával:

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

bool abece_elorebb(std::string const& a, std::string const& b) {
    return a < b;
}

bool pihez_kozelebb(double a, double b) {
    return fabs(a - M_PI) < fabs(b - M_PI);
}

std::vector<std::string> strvec; // valaki feltölti

std::cout << *Tarolo_legvalamilyenebb(
    strvec.begin(), strvec.end(), hosszabb) << std::endl;
std::cout << *Tarolo_legvalamilyenebb(
    strvec.begin(), strvec.end(), abece_elorebb) << std::endl;

double tomb[100] = {...};

std::cout << *Tarolo_legvalamilyenebb(
    tomb, tomb+100, pihez_kozelebb) << std::endl;

Az első két függvénynél a fordító T-re std::string const&-et vezet le, a harmadiknál pedig double-t. Nem okoz gondot, hogy az egyik konstans referencia, a másik pedig érték.

Nézzük meg a pihez_kozelebb függvényt! Ebbe bele van égetve, hogy a pi-hez legközelebbi számot keressük. Jó lenne, ha ez is paraméterezhető lenne, és nem kéne az 5-höz közelebb kereséséhez külön függvényt írni.

A globális változókkal való megadás gányolás lenne, valami C++-osabb megoldást kéne keresni. A valamilyenebb paraméternek tehát más, általánosabb típus kell. Hogyan használja az algoritmus a valamilyenebb paramétert, mit kell tudnia a paraméternek?

Az algoritmus átveszi a valamilyenebb-et, és egyetlen dolgot művel vele: meghívja, mint egy függvényt. Mi más lehetne ez, mint egy függvény? A jegyzetben már volt szó a megoldás kulcsáról. A C++ megengedi, hogy az objektumok függvényhívás operátorát overload-oljuk. Legyen valamilyenebb egy objektum, aminek a függvényhívás operátora át tud venni két valamit, és visszaad egy igaz/hamis értéket. Az objektum tagváltozója pedig tárolja, hogy mihez közelebbi számot keresünk.

class valamihez_kozelebb {
private:
    double mihez;
public:
    valamihez_kozelebb(double mihez)
        : mihez(mihez) {
    }
    bool operator() (double a, double b) const {
        return fabs(a-mihez) < fabs(b-mihez);
    }
};

Ehhez a Tarolo_legvalamilyenebb függvényt is át kell írnunk. Nemcsak függvénypointert kell tudnia átvenni, hanem bármit, aminek van megfelelő függvényhívás operátora. Ez lehet egy objektum vagy egy függvénypointer is.

template <typename ITER, typename MILYENEBB>
ITER Tarolo_legvalamilyenebb(ITER eleje, ITER vege, MILYENEBB valamilyenebb) {
    // ...
    for (/*...*/) {
        if (valamilyenebb(*i, *leg)) // <- függvényhívás operátor!
            // ...
    }
    // ...
}

Az ilyen MILYENEBB típusokat hívjuk tág értelemben predikátumnak, ami megmondja valamiről vagy valamikről, hogy milyen. A predikátumok speciális fajtája például a komparátor, ami két valamiről mondja meg, hogy egymáshoz képest milyenek, ahogy a valamihez_kozelebb is.

Tarolo_szamol

Feladat: Számoljuk meg, hogy egy double tömbben hány 5-nél kisebb szám van!

Ez a feladat másfajta predikátumot igényel, olyat, ami egyetlen számról tudja megmondani, hogy olyan-e (5-nél kisebb-e). Az ilyet unáris predikátumnak (unáris == egyoperandusú) hívjuk. Például ez egy unáris predikátum:

bool otnel_kisebb(double d) {
    return d < 5;
}

A feladat tehát arra redukálódott, hogy írjunk függvényt, ami megszámolja, hogy egy tárolóban hány valamilyen elem van. Aztán ezt fel lehet paraméterezni az otnel_kisebb függvénnyel.

template <typename ITER, typename PRED>
std::size_t Tarolo_szamol(ITER eleje, ITER vege, PRED pred) {
    std::size_t db = 0;
    for (ITER i = eleje; i != vege; ++i) {
        if (pred(*i))
            ++db;
    }
    return db;
}

std::size_t darab = Tarolo_szamol(tomb, tomb+100, otnel_kisebb);

Generikus STL algoritmusok

A fent bemutatott algoritmusokat, és még sok hasonló algoritmust nagyon sokszor újra lehet használni. Ezért a C++ STL része az <algorithm> fejlécfájl, ami ilyen algoritmusokat tartalmaz.

Az előző fejezetben a kiíró függvénynek négy verzióját mutattuk meg. Ezek közül a legutóbbi bizonyult a legjobban használhatónak, ami két tetszőleges iterátort vesz át érték szerint. Ezért az STL algoritmusok is mind ilyenek.

A fejezet példafüggvényei nem hasra ütés alapján kerültek be, mindegyik megtalálható az STL-ben is, más néven. Sokuknak két, alig különböző verziója van. Az egyik T const&-et vesz át (ha kell), a másik predikátumot.

• A Tarolo_keres-nek az STL-ben a find felel meg. Keresett értéket átvevő: std::find, predikátumot átvevő: std::find_if
• A szélsőértékkereső Tarolo_legvalamilyenebb: std::min_element, std::max_element
• A megszámláló Tarolo_szamol is elérhető értéket átvevő: std::count és predikátumot átvevő: std::count_if változatban.

Ezeket név szerint felesleges megtanulni, viszont ha kódolás során egy hasonlóan általános algoritmus szagát érezzük, érdemes megnézni, valaki megoldotta-e már. Erre a célra a cppreference.com-ot és a cplusplus.com-ot érdemes használni. Előbbi általában egy egyszerű implementációt is mellékel a leírás mellé, algoritmusoknál ez sokat segíthet a megértésben.

STL tárolók iterátorai

A Lista osztályunkhoz hasonló az STL-ben található std::list osztály (<list> fejlécfájl). A fő különbség, hogy az std::list duplán láncolt, és valamivel okosabb a mi listánknál.

A korábban említett std::vector-nak is vannak iterátorai. Hogy mennyivel tud többet egy std::vector iterátora, mint az std::list-é, a következő bekezdésben kiderül. Érdekes módon egyébként az std::string-nek is vannak iterátorai. Úgy érdemes elképzelni, mint egy karaktereket tároló std::vector, kicsit kibővített funkcionalitással. A string egyébként maga is egy template, a generikus osztály neve std::basic_string, és az std::string tulajdonképpen:

typedef basic_string<char> string;

Az iterátorokat eredetileg – ahogy a neve is mutatja – tárolók bejárására találták ki. Azonban ennél sokkal hasznosabbnak bizonyultak, a tárolók bizonyos műveleteit is iterátorokon keresztül érjük el.

erase

Feladat: írjunk – gondolatban – egy olyan tagfüggvényt az std::list-nek, ami egy elemet tud törölni belőle!

Mit vegyen át ez a függvény, mi alapján töröljön? Első gondolatunk lehetne az, hogy adjuk át neki az elemet, és abban keressen == operátorral. Ez általában azonban nem jó megoldás, ugyanis egy listában lehetnek azonos elemek, és így közülük mindig csak az elsőt tudnánk törölni.

Ha a törlendő elem indexét veszi át, az ugyanúgy durván hatékonytalan, mint az előző megoldás. Először meg kell határozni a törlendő elem indexét valahogy, ez általában O(n) komplexitású, majd a törlésnél még egyszer el kell menni a listában addig, ez szintén O(n). Egy duplán láncolt listában viszont a törlés maga O(1) is lehetne, hiszen csak néhány pointer átállítgatásáról van szó.

Ötlet: Adjunk át a törlendő elemre mutató pointert! Ha van az elemre pointerünk, onnan könnyen elérjük a szomszédos elemeket és ki tudjuk fűzni a listából. A pointer általánosítva: iterátor!

insert

Az STL tárolók törlő függvénye (erase) ezért mindig iterátort vesz át, ahogy a beszúró függvény is:

std::list<int> lista;
lista.insert(lista.begin(), 42);

Az insert a pozícióként megadott iterátor elé szúrja be az új elemet. Ha belegondolunk, ennek így kell lennie: ha a begin() elé kerül, akkor az lesz az első elem. Az end() az utolsó utáni elem, tehát ha az utolsó utáni elé szúrunk be, az lesz az utolsó.

Invalidálás

Mi történik, ha ezt a kódot futtatjuk?

std::list<int> lista; 
// valaki feltölti
lista.insert(lista.begin(), 42);

std::list<int>::iterator it = std::find(lista.begin(), lista.end(), 42);
std::cout << *it << std::endl;

lista.erase(it);
std::cout << *it << std::endl; // <- baj van

Ha listából kitöröltük a megtalált elemet – lista.erase(it) –, utána it hova mutat? Sehova, azt az elemet, amire mutatott, épp akkor töröltük. Mivel az erase érték szerint veszi át az iterátort – konvenció szerint mindig érték szerint kezeljük –, az erase nem is tudta megváltoztatni it-t, tehát a jelzett sor hibás!

Amikor az iterátor egy ehhez hasonló művelet hatására érvénytelenné válik, invalidálódik, tehát utána nem használhatjuk. Pontosan ugyanaz történik, mint pointereknél: ha felszabadítjuk a pointer által mutatott területet, a pointert sem használhatjuk (dangling pointer).

Szerencsére a C++ szabvány pontosan leírja, mikor invalidálódnak az iterátorok. Józan ésszel nagyjából ki lehet találni, mit szabad és mit nem: például egy std::list-be való beszúráskor a régi iterátorok megmaradnak, de std::vector-ba beszúrásnál nem feltétlenül. Ha bizonytalanok vagyunk, keressünk rá.

Feladat: egy std::list-ből töröljük az összes 42 értékű elemet!

Nem tűnik könnyűnek a feladat, pedig érezni lehet, hogy ez gyakori probléma. Ha találtunk egy 42-t, és töröljük, a ciklusváltozónk invalidálódik, és nem tudjuk, hol tartottunk, hiszen egy érvénytelen iterátoron az operator++ sem használható. Két lehetőségünk van:

• Kihasználuk azt, hogy listából törlésnél csak a törlendő elemre mutató iterátor invalidálódik, a többi nem. Elmentjük pl. a következő elemre mutató iterátort, majd töröljük az előzőt.
• Szerencsére az STL megírásakor erre is gondoltak. Az erase visszaad egy valid iterátort, ami a törölt elem utáni elemre mutat.

A második megoldás jóval általánosabb és egyszerűbben használható, nézzük meg azt kódban!

std::list<int> lista; // valaki feltölti

std::list<int>::iterator it = lista.begin();
while (it != lista.end()) {
    if (*it == 42)
        it = lista.erase(it);
    else
        ++it;
}

Ha az elem törlendő, az erase a következő elemre mutató iterátort adja vissza, ezért csak akkor kell léptetni, ha nem kellett törölni.

Bind

Feladat:

• Számoljuk meg egy std::vector<std::string>-ben az ábécé szerint a "predikátum" után lévő sztringeket!
• Számoljuk meg egy std::vector<double>-ben azokat a számokat, amik abszolút értékben kisebbek pi-nél!

Ezt a két feladatot naivan meg lehetne úgy oldani, hogy írunk két függvényt vagy predikátumot, amik visszaadják, hogy egy sztring a "predikátum" után van-e, illetve egy szám abszolút értékben kisebb-e, mint pi.

Éles szeműek észrevehetik, hogy nagyjából ugyanazokat a segédfüggvényeket kell megírni, mint az első iterátoros feladatokban, csak most kettő helyett egy paraméterrel. Sőt, akár vissza is vezethetnénk az előző függvényekre, valahogy így:

bool abece_predikatum_utan(std::string const& str) {
    return abece_elorebb("predikátum", str);
}

bool abs_kisebb_pi_nel(double szam) {
    valamihez_kozelebb vk(M_PI);
    return vk(szam, 0.0);
}

std::size_t s1 = Tarolo_szamol(strvec.begin(), strvec.end(), abece_predikatum_utan);
std::size_t s1 = Tarolo_szamol(szamok.begin(), szamok.end(), abs_kisebb_pi_nel);

A rossz hír, hogy a feladat ismét mechanikusnak tűnik, érezzük, hogy lehetne automatizálni. Pontosan mi közük van egymáshoz a régi és az új függvényeknek? Az újak fognak egy bináris predikátumot (komparátor), és rögzítik az egyik paraméterét egy fix értékre. A kapott pararamétert csak továbbítják a komparátor másik paraméterének. Ezt a műveletet nevezzük angolul bind-nak.

A jó hír pedig: ezt nem kell minden egyes ilyen szituációban megcsinálni, van rá egyszerűbb megoldás. Képzeljünk el egy objektumot, aminek tagváltozója egy bármilyen komparátor, és egy bármilyen "fix érték". Ezen kívül van egy egyparaméteres függvényhívás operátora, ami pontosan azt csinálja, amit elvárunk tőle.

using namespace std::placeholders;
std::size_t s1 = Tarolo_szamol(strvec.begin(), strvec.end(),
    std::bind(&abece_elorebb, "predikátum", _1));
std::size_t s2 = Tarolo_szamol(szamok.begin(), szamok.end(),
    std::bind(valamihez_kozelebb(M_PI), _1, 0.0));

bool f(int a, int b, int c) {
    return a + b <= c;
}

Tarolo_szamol(szamok.begin(), szamok.end(), std::bind(f, 0, _1, 4));
auto rovidebb = std::bind(hosszabb, _2, _1);

A typename kulcsszó

A fejezetben szerepelt néhány függvény, ahol kellett néhány "felesleges" typename kulcsszó, amiknek a magyarázatát későbbre ígértük. Még az iterátoros függvényeknél is ritkán van rá szükség, de ha mégis, csúnya hibaüzeneteket kapunk a fordítótól. A magyarázat ideje most jött el. Az egyik ilyen függvény ez volt:

template<typename TAROLO>
void Tarolo_kiir(TAROLO tar) {
    typename TAROLO::const_iterator it; // <- !
    for (it = tar.begin(); it != tar.end(); ++it)
        std::cout < *it < std::endl;
}

Ez a kód meglepő módon nem fordul typename nélkül. Hogy megértsük, miért, nézzünk meg két fejtörőt. Deklaráljuk A-t illetve B-t úgy, hogy az alábbi kód szintaktikailag helyes legyen!

int main() {
    // deklarációk
    A * B;
}

Itt kétfajta lehetséges megoldás van. Egy triviális megoldás például ez:

class A {};
A * B;

Ilyenkor a B egy olyan pointer, amelyik A típusú objektumra mutat. A másik lehetőség tanulságosabb:

int A, B;
A * B;

Ilyenkor a kódrészlet egy szorzást jelent.

Ebből egy fontos következtetést tudunk levonni. A fordítónak ismernie kell a deklarált típusokat, változókat, hogy el tudja dönteni egyetlen utasításról, hogy szintaktikailag helyes-e. Sőt, a deklarációk ismerete nélkül azt sem lehetne eldönteni, hogy az deklaráció, vagy utasítás! Ez a template kódoknál nagyobb problémát okoz. A következő példánkban lényegében ugyanez a feladat, picit összetettebb verzióban.

// deklarációk
int main() {
    A::B * C;
}

Itt A-tól függően B-re két lehetőség adódik.

• B lehet egy belső típus, mint például a Lista osztálynál az iterator.
• B azonban lehet A-nak egy statikus tagváltozója is. Ebben az esetben a kérdéses sor nem a C pointer deklarációja, hanem megint egy szorzás.

A template kódok fordításának ismeretében (előző fejezet) már könnyebben megérthető, mi is a baj ezzel a sorral:

TAROLO::const_iterator it = lista.begin(); // <- ERROR!

A fordító, amikor először találkozik a Lista_kiir függvénnyel, csak szintaktikai ellenőrzést végez, (zárójelek, pontosvesszők, deklarációk, stb.) még konkrét példányosítás nélkül. Tehát TAROLO még ismeretlen, akármi lehet majd. Tehát azt sem tudhatja, hogy a const_iterator neki belső típusa vagy statikus adattagja-e, mert a :: operátor mindkettőre utalhat.

Az ilyen, kérdéses esetekben a fordító azt feltételezi, hogy statikus tagról van szó, és nekünk kell jeleznünk a typename kulcsszóval, ha nested type. Ha elfelejtjük, példányosításkor úgyis kiderül.

reverse_iterator

A const_iterator-ról már esett szó, konstansként látott tárolók bejárásához a "sima" iterator-t nem használhatjuk, mert rajta keresztül meg lehetne változtatni a tárolóban tárolt elemet.

A reverse_iterator annyiban különbözik az iterator-tól, hogy a másik irányban járja be a tárolót. A "hátulról első", azaz utolsó elemre mutató iterátort a tároló rbegin tagfüggvénye adja vissza, a "hátulról utolsó utánit", azaz az első előttit pedig a rend. Ettől eltekintve pontosan ugyanúgy lehet használni.

std::list<int> lista; // valaki feltölti

std::list<int>::iterator it;
for (it = lista.begin(); it != lista.end(); ++it) { // egyik irányban
    std::cout << *it << std::endl;
}

std::list<int>::reverse_iterator rit;
for (rit = lista.rbegin(); rit != lista.rend(); ++rit) { // visszafelé
    std::cout << *rit << std::endl;
}

Figyeljük meg, hogy a reverse_iterator előre léptető operátora, az operator++ a tárolón valójában hátrafelé léptet. Ennek így kell lennie, hogy az iterator-t és a reverse_iterator-t egyformán lehessen használni, például egy STL algoritmusban. Természetesen konstans tárolót is bejárhatunk visszafelé, erre való az ijesztő nevű const_reverse_iterator típus.

Pointeraritmetika?

Tömb elemére mutató pointernél lehetőségünk van aritmetikára. Ha p egy tömb elemére mutat, akkor p+20 a hússzal arrébb lévő elemre.

Számunkra nyilvánvaló, hogy egy láncolt listával ezt nem tudjuk megtenni, a tömb ennyivel "okosabb" a memóriában való elhelyezkedés miatt. De mi a helyzet ezzel az std::vector és az std::list iterátorai esetén? Egyáltalán, van ezeken kívül még többet / kevesebbet "tudó" iterátor?

Az iterátorokat csoportosíthatjuk a rajtuk elvégezhető műveletek alapján, mit lehet velük tenni és mit nem. Ezt a felépítést a "legbutább" iterátorokkal kezdjük, és megnézzük, hogy ahhoz képest mit tudnak az "okosabbak". A leírás nem pontos, leegyszerűsítettük a könnyebb megértés érdekében.

• Input iterator: kiolvashatjuk a mutatott elem értékét. A Lista iterátora és const_iterator is ilyen.
• Output iterator: írhatjuk a mutatott elemet. A fenti iterator ilyen, de a const_iterator nem. (Vigyázat, van olyan iterátor, ami output, de nem input! A jegyzetben később lesz is szó ilyenről.) Az olvasást és írást is a * és -> operátorok biztosítják.
• Forward iterator: olyan iterator, amit előre léptethetünk, és többször is bejárhatjuk vele a tárolót. Például az egyszeresen láncolt Lista osztályunk iterátora. Léptetni a ++ operátorokkal tudjuk.
• Bidirectional iterator: előre és hátra is léptethető iterátor, például az std::list iterátora. A hátrafelé léptetésre a -- operátorok valók.
• Random access iterator: "távoli", nem szomszédos elemek is O(1) komplexitással elérhetőek, például az std::vector iterátora. Az iterátorhoz egészeket (int) adhatunk hozzá és vonhatunk ki, pont úgy, ahogy egy pointerrel tennénk.

Az STL algoritmusok ezeket ki is használják, és le van dokumentálva, hogy melyik algoritmus milyen iterátort vár. Például a rendezés, std::sort garantáltan O(n×log n) komplexitású, ennek megfelelően jellemzően quicksort-ot (gyorsrendezést) végez. Ahhoz viszont random access iterator kell, egy láncolt listával nem működik. Az std::count viszont beéri egy forward iterator-ral is, hiszen csak végigmegy az elemeken, nem ugrál összevissza.

Ha rossz, "túl buta" iterátort próbálunk meg átadni egy ilyen algoritmusnak, például std::sort-nak lista-iterátort, a fordító a kezünkre csap, hiszen használni próbálja a random access iterator extra tulajdonságait.

Az iterátorok típusai közötti viszony programozásban gyakran előforduló kapcsolat, az öröklésről szóló fejezeben visszatérünk rá.