I. rész: Paraméterként átadott függvények

Generikus algoritmusok kapcsán az egyik legalapvetőbb feladat az, hogy egy algoritmust függvénnyel paraméterezzünk.

Tegyük fel például, hogy egész számok tömbjében kell megszámlálnunk

• a páros elemeket,
• a pozitív elemeket,
• az 5-nél nagyobb elemeket,
• és így tovább.

A megszámlálás algoritmusa a predikátumtól független: mindenképp egy iterálásról, és egy számláló feltételhez kötött növeléséről van szó. Az eltérés az, hogy mely elemeknél növeljük a számlálót, és ez az, amit paraméterként tudunk átadni:

FÜGGVÉNY megszámlálás(tömb, predikátum):
    db = 0
    MINDEN ELEMRE(tömb):
        HA predikátum(elem):
            db += 1
    VISSZA: db

Ugyanez a kérdés általánosítható. Mi egy rendezésnél a rendezési reláció: a vagy b értékű elem közül melyik a kisebb, melyik való a tömb elejére? Mi az az egyváltozós matematikai függvény, y = f(x), amit ki kell rajzolnia a programnak? Mi történjen akkor, amikor megnyomja a felhasználó a gombot? Adott egy pointer: T*, amelyik dinamikusan foglalt memóriaterületre mutat – hogyan kell azt felszabadítani, free, delete, delete[], vagy valami más módon?

A feladatunk lényegében az, hogy egy függvénynek paraméterként egy másik függvényt adjunk át. Fontos az, hogy a paraméterként átadott függvényt is gyakran paraméterezhetővé szeretnénk tenni. Pozitív elemek? 5-nél nagyobb elemek? 6-nál nagyobb, 11-nél nagyobb elemek? Ugyanarról a feladatról van szó: egy predikátum(elem) alakú függvényt kell kapnia a megszámlálásnak, amely függvény valahonnan további adatokat kell kapjon, esetleg belső állapottal kell rendelkezzen.

Kérdés, hogy ezekre milyen lehetőségek vannak.

A Prog1 szintjén függvényre mutató pointer segítségével oldottuk meg ezt a problémát. A C és a C++ sem képes arra, hogy a globális függvényeket és a metódusokat adatként kezelje. De egy függvény memóriabeli helyét, azaz címét igen, és így válhatnak ezek akár paraméterré is. A példakód vektorral dolgozik, de a függvénypointer már C-ben is létezett:

#include <vector>
#include <iostream>

int megszamlal(std::vector<int> const & tomb, bool (*pred)(int)) {
    int db = 0;
    for (int elem : tomb)
        if (pred(elem))
            db += 1;
    return db;
}

bool paros(int szam) {
    return szam % 2 == 0;
}

int main() {
    std::vector<int> v = { -6, 8, 4, 5, 0, -2, 3, 9 };
    int db = megszamlal(v, paros);
    std::cout << db << std::endl;
}

A módszer előnye, hogy futási időben választhatunk a predikátumok közül: a megszámláló függvény második paramétere származhat változóból is, a pointer adatként eltárolható. A hátrány viszont, hogy emiatt a predikátum meghívása kicsit lassú lehet: egy indirekt, azaz pointeren keresztüli függvényhívásról van szó.

További hátrány, hogy nehéz a predikátumnak további adatokat eljuttatni. Ha keressük az 5-nél nagyobb, 7-nél nagyobb, –2-nél nagyobb stb. számokat, akkor nyilvánvalóan a predikátumnak valahogyan látnia kell az alsó határt is (aminél nagyobb számokra igennel kell válaszoljon). Ugyanakkor ezt nem vehetjük fel újabb paraméternek, mert általánosságban mégis csak egy egyparaméterű, int → bool függvényt várunk. Megoldás lehet egy globális változót használni:

int megszamlal(std::vector<int> const & tomb, bool (*pred)(int));

int minel;

bool nagyobb(int szam) {
    return szam > minel;
}

int main() {
    std::vector<int> v = { -6, 8, 4, 5, 0, -2, 3, 9 };
    std::cout << "Alsó határ? ";
    std::cin >> minel;
    int db = megszamlal(v, nagyobb);
    std::cout << db << std::endl;
}

Persze ez általában véve nem túl előnyös, mert így a predikátum maga már nem kezelhető adatként; pl. nem tudunk több „nagyobb-e N-nél” objektumot eltárolni, mert mindegyik ugyanarra az egy közös globális változóra hivatkozik. Emiatt gyakran elengedjük azt a megkötést, hogy a predikátumnak feltétlenül egyparaméterűnek kell lennie. Továbbra is C nyelvi eszközöknél maradva, felvehetünk egy újabb, void * típusú paramétert, amely generikus pointer lévén bármilyen típusú adatra mutathat. Ennek értékét a megszámlálás megkapja, és mindig továbbadja a predikátumnak:

#include <vector>
#include <iostream>

int megszamlal(std::vector<int> const & tomb, bool (*pred)(int, void *), void *extra) {
    int db = 0;
    for (int elem : tomb)
        if (pred(elem, extra)) // !
            db += 1;
    return db;
}

bool nagyobb(int szam, void *pminel) {
    int minel = *static_cast<int*>(pminel); // !
    return szam > minel;
}

int main() {
    std::vector<int> v = { -6, 8, 4, 5, 0, -2, 3, 9 };
    std::cout << "Alsó határ? ";
    int minel;
    std::cin >> minel;
    int db = megszamlal(v, nagyobb, &minel);
    std::cout << db << std::endl;
}

A void * mutatón keresztül bármekkora, és bármilyen típusú adatot el lehetne érni; akár pl. egy objektumot, amiben több adattag is van. Sajnos így viszont át kell adnunk ezt a paramétert akkor is, ha nincs rá szükségünk. Az eredeti interfésszel tehát inkompatibilis a megoldás:

bool paros(int szam, void *) {
    return szam % 2 == 0;
}

int main() {
    std::vector<int> v = { -6, 8, 4, 5, 0, -2, 3, 9 };
    int db = megszamlal(v, paros, nullptr);
    std::cout << db << std::endl;
}

OOP elvek mentén gondolkozva eszünkbe juthat, hogy az ugyanolyan interfésszel rendelkező, egy bizonyos feladatot másképpen megoldó objektumok osztályhierarchiába szervezhetőek: az előbbi függvénypointer kiváltható egy virtuális függvénnyel is. Ezt mutatja a második megoldás. Ebben definiálunk egy Predikatum nevű interfészt annak kifejezésére, hogy egy predikátum képes egy számot megvizsgálni. A vizsgáló függvény éppenséggel lehetne a függvényhívó operátor is, de az kicsit szokatlan lenne. A lényeg inkább az, hogy ennek egy tisztán virtuális függvénynek kell lennie, amit a leszármazott implementál:

#include <vector>
#include <iostream>

class Predikatum {
  public:
    virtual bool vizsgal(int szam) = 0;
    virtual ~Predikatum() = default;
};

int megszamlal(std::vector<int> const & tomb, Predikatum & p) {
    int db = 0;
    for (int elem : tomb)
        if (p.vizsgal(elem))
            db += 1;
    return db;
}

class Paros : public Predikatum {
  public:
    virtual bool vizsgal(int szam) override {
        return szam % 2 == 0;
    }
};

int main() {
    std::vector<int> v = { -6, 8, 4, 5, 0, -2, 3, 9 };
    Paros p1;
    int db = megszamlal(v, p1);
    std::cout << db << std::endl;
}

A függvényhívás ezzel továbbra is indirekt; a predikátum objektumot referencia szerint tudjuk csak paraméterként adni, és a benne lévő virtuális függvényhívással ugyanez a helyzet. Cserébe viszont az extra paraméterek problémája elegánsan, szinte magától megoldódik, hiszen a predikátum objektumnak attribútumai is lehetnek. (Az extra paraméter persze ott van, a this pointer éppen az.) A Predikatum interfésze emiatt nem változik:

class Nagyobb : public Predikatum {
  private:
    int minel; // !
  public:
    explicit Nagyobb(int minel): minel(minel) {}
    bool vizsgal(int szam) override {
        return szam > minel; // !
    }
};

int main() {
    std::vector<int> v = { -6, 8, 4, 5, 0, -2, 3, 9 };
    std::cout << "Alsó határ? ";
    int minel;
    std::cin >> minel;
    Nagyobb n1(minel); // !
    int db = megszamlal(v, n1);
    std::cout << db << std::endl;
}

Vegyük észre, hogy ezzel tulajdonképpen a globális függvényt és globális változót csomagoltuk össze egy osztályba; a metódus látja az attribútumot; az osztályból pedig akár több objektumot is példányosíthatunk, amelyek adatként kezelhetőek:

int minel;

bool nagyobb(int szam) {
    return szam > minel;
}

class Nagyobb : public Predikatum {
    int minel;

    bool vizsgal(int szam) override {
        return szam > minel;
    }
};

A polimorfizmus fordítási idejű is lehet: a predikátum paraméterként történő átadásához használhatunk sablont is:

#include <vector>
#include <iostream>

template <typename PRED>
int megszamlal(std::vector<int> const & tomb, PRED p) { // !
    int db = 0;
    for (int elem : tomb)
        if (p(elem)) // !
            db += 1;
    return db;
}

class Paros {
  public:
    bool operator() (int szam) { // !
        return szam % 2 == 0;
    }
};

int main() {
    std::vector<int> v = { -6, 8, 4, 5, 0, -2, 3, 9 };
    int db = megszamlal(v, Paros());
    std::cout << db << std::endl;
}

Ilyenkor az a szokás, hogy funktort készítünk, függvény interfésszel, azaz függvényhívó operátorral rendelkező objektumot. Ez azért fontos, mert az így megírt függvénysablon tulajdonképpen függvényre mutató pointerrel is példányosítható, PRED = bool (*)(int) sablonparaméterrel. Ilyenkor visszakapjuk az eredeti, C nyelvi elemekkel megírt változatot, amely tényleg képes akár egy függvénypointert is átvenni:

template <typename PRED>
int megszamlal(std::vector<int> const & tomb, PRED p);

bool paros(int szam) {
    return szam % 2 == 0;
}

int main() {
    std::vector<int> v = { -6, 8, 4, 5, 0, -2, 3, 9 };
    int db = megszamlal(v, paros); // megszamlal<bool (*)(int)>(v, paros)
    std::cout << db << std::endl; 
}

Fontos, hogy itt bizonyos szemszögből nézve egyszerre két paraméterátadás is történik. Egyrészt „átadjuk” a sablonparamétert: fordítási időben a fordító eldönti, hogy a PRED paraméter helyére milyen típus nevét kell helyettesíteni. Ekkor dől el, hogy melyik algoritmust fogjuk használni a vizsgálathoz: páros-e, nagyobb-e, és így tovább. Itt áll elő a megszámláló függvénynek az a specializációja, amelyik a megadott típusú objektumot, vagy függvénypointert kaphatja paraméterként. Másrészt pedig átadunk egy objektumot is. Ez az a konkrét példány, amelyik a paritást vizsgáló változatnál egy üres objektum, de a Nagyobb osztály esetében adatot is tartalmaz:

template <typename PRED>
int megszamlal(std::vector<int> const & tomb, PRED p);

class Nagyobb {
  private:
    int minel;
  public:
    explicit Nagyobb(int minel): minel(minel) {}
    bool operator() (int szam) {
        return szam > minel;
    }
};

int main() {
    std::vector<int> v = { -6, 8, 4, 5, 0, -2, 3, 9 };
    std::cout << "Alsó határ? ";
    int minel;
    std::cin >> minel;
    int db = megszamlal(v, Nagyobb(minel));
    std::cout << db << std::endl;
}

A template-es változat előnye és hátránya is, hogy a típus kiválasztása fordítási időben történik. Előnye, mert így gyorsabb kód generálható; nincs indirekció, és szinte biztosan inline-olás is történik. Hátránya viszont, hogy a hívások helyén a polimorfizmus fordítási idejű; csak a funktorba rejtett extra adatok cserélhetőek, a funktor típusa futási időben már kötött.

A C++11 újdonsága, hogy lehet benne lambda függvényeket definiálni: olyan névtelen függvényeket egy másik függvény belsejében, amelyek látják az őket becsomagoló függvény lokális változóit is. Valójában ez nem elvi újdonság, a háttérben a fordító ezekből funktor osztályokat és objektumokat gyárt. Lényegében csak lett egy nagyon egyszerű, frappáns szintaxis ezek definíciójához. A lambda függvényeket mindig sablonokkal együtt használjuk, mivel minden lambda kifejezés hatására a fordító egy új osztályt generál:

#include <vector>
#include <iostream>

template <typename PRED>
int megszamlal(std::vector<int> const & tomb, PRED p) {
    int db = 0;
    for (int elem : tomb)
        if (p(elem))
            db += 1;
    return db;
}

int main() {
    std::vector<int> v = { -6, 8, 4, 5, 0, -2, 3, 9 };
    int db = megszamlal(v, [] (int szam) {
        return szam % 2 == 0;
    });
    std::cout << db << std::endl;
}

Az extra adatok eljuttatása a függvényhez nagyon egyszerű, csak használnunk kell a lambda kifejezés capture specifier részét, megjelölve a szükséges adatokat:

int main() {
    std::vector<int> v = { -6, 8, 4, 5, 0, -2, 3, 9 };
    std::cout << "Alsó határ? ";
    int minel;
    std::cin >> minel;
    int db = megszamlal(v, [minel] (int szam) { // !
        return szam > minel;
    });
    std::cout << db << std::endl;
}

Teljesítmény szempontjából nagyon előnyös lehet a lambda függvény. Ennek a törzse szinte biztosan inline-olható a felhasznált algoritmusba:

• A megszámláló függvény törzse látszik, mivel sablon függvényről van szó.
• Az általa hívott predikátum törzse pedig szintén – a lambdáknál ez nem is lehet másképp.

A lambda függvények kapcsán hamar felmerült, hogy az azokkal gyártott funktorokat adatként is kéne tudni kezelni: nem csak sablon függvényeknek átadni, hanem változókban eltárolni, tárolókba szervezni őket, és így tovább. Ezt viszont közvetlenül nem tudjuk megtenni, mivel a típusuk nem ismert. Ezért vezették be az std::function osztályt, amely type erasure-t biztosít funktor objektumok számára. Tehát ez képes bármilyen funktort eltárolni, elrejtve annak konkrét típusát; így tárolónak is használható, de akár paraméterátadásnál is:

#include <vector>
#include <iostream>
#include <functional>

int megszamlal(std::vector<int> const & tomb, std::function<bool(int)> p) { // !
    int db = 0;
    for (int elem : tomb)
        if (p(elem))
            db += 1;
    return db;
}

int main() {
    std::vector<int> v = { -6, 8, 4, 5, 0, -2, 3, 9 };
    std::cout << "Alsó határ? ";
    int minel;
    std::cin >> minel;
    int db = megszamlal(v, [minel] (int szam) {
        return szam > minel;
    });
    std::cout << db << std::endl;
}

A dolog előnye, hogy így a megszámláló algoritmus nem kell sablon legyen, ennek ellenére a paraméterként adott algoritmus és adatok futási időben változhatnak. A hátrány az, hogy az absztrakcióhoz szükséges indirekciók ott vannak az std::function belsejében; ennek futási idejű költsége van, lassabb a programunk, mintha sablonokkal dolgoznánk.

Valójában a sablont és az std::function segédosztályt egyszerre is használhatjuk a kódunkban. Ha a megszámláló függvény definícióját meghagyjuk sablonnak, az nem jelent korlátot az std::function használata szempontjából, hiszen a sablon bármikor példányosodhat PRED = std::function<bool(int)> paraméterrel is. Kicsit hosszabb ez a példaprogram, de a megszamlal() hívásának két helye jól mutatja a különbséget:

#include <vector>
#include <iostream>
#include <functional>

template <typename PRED>
int megszamlal(std::vector<int> const & tomb, PRED p) {
    int db = 0;
    for (int elem : tomb)
        if (p(elem))
            db += 1;
    return db;
}

std::function<bool(int)> negativ_vagy_nagyobb() {
    std::cout << "(N)egatívak vagy (V)alaminél nagyobbak? ";
    char c;
    std::cin >> c;
    if (toupper(c) == 'N') {
        return [](int szam) { return szam < 0; };
    } else {
        std::cout << "Minél? ";
        int minel;
        std::cin >> minel;
        return [minel](int szam) { return szam > minel; };
    }
}

int main() {
    std::vector<int> v = { -6, 8, 4, 5, 0, -2, 3, 9 };
    int db1 = megszamlal(v, [](int szam) { // megszamlal<lambda>
        return szam % 2 == 0;
    });
    std::cout << "Párosak: " << db1 << std::endl;

    std::function<bool(int)> pred = negativ_vagy_nagyobb();
    int db2 = megszamlal(v, pred); // megszamlal<std::function<bool(int)>>
    std::cout << "Találatok: " << db2 << std::endl;
}

Az első helyen a paraméter egy lambda kifejezés: így egy olyan specializációja jön létre a megszámláló függvénynek, amely konkrétan ezzel dolgozik. Gyors és inline-olható.

A második helyen std::function-nel példányosodik a függvény. Ez ugyan lassabb, viszont akár futási időben is cserélhetjük a függvényt. Ahogy a sablon függvénypointerré is képes volt változni, úgy std::function paraméterűvé is képes: de csak akkor, ha épp szükségünk van rá.