9. hét: Generikus algoritmusok

Írj függvényt, amely paraméterként egy egész számokból álló tömböt kap, és kiírja az abban tárolt számokat!

Egészítsd ki a függvényed egy további paraméterrel, ahol egy unáris predikátumot kap (unary predicate), amelyet függvénypointerként vesz át! Legyen a függvény feladata most az, hogy csak azokat a számokat írja ki a tömbből, amelyekre a függvény azt mondja, hogy kellenek.

Ha mindent jól csinálsz, ez a programrész működni fog:

bool is_negative(int x) {
    return x < 0;
}

int main() {
    int numbers[5] = { 6, -5, 9, 12, -8 };
    print_if(numbers, 5, is_negative);  // -5 -8
}

Írd át a print_if() függvényedet úgy, hogy a tömb kezdőcíme és mérete helyett inkább pointereket kapjon paraméterként, amelyekkel a tömb belseje is könnyebben hivatkozható! A két pointer a tömb belsejéből egy tartományt jelöl ki, balról zárt (első elem), jobbról nyílt (utolsó utáni elem) intervallumban. Dolgozz a függvényen belül is pointeraritmetikával, ne indexeléssel!

A használat így módosul:

int main() {
    int numbers[10] = { 9, 5, -8, 4, -6, 7, 9, 1, 2, -9 };

    print_if(numbers, numbers + 10, is_negative); // -8 -6 -9
    print_if(numbers + 3, numbers + 8, is_negative); // -6
}

Módosítsd a függvényed úgy, hogy bármilyen típusú adatra működni tudjon! Például az ábécében sloth (lajhár) előtti szavak listázása:

bool is_before_sloth(std::string x) {
    return x < "sloth";
}

int main() {
    std::string animals[5] = {
        "spiky floof",
        "disco turkey",
        "nope rope",
        "prison pony",
        "furry potato",
    };
    print_if(animals, animals + 5, is_before_sloth);
}

Módosítsd a függvényed úgy, hogy bármilyen típusú iterátorral működjön, ne csak pointerrel! Például std::list iterátorával is:

bool is_before_sloth(std::string x) {
    return x < "sloth";
}

int main() {
    std::list<std::string>> animals = {
        "spiky floof",
        "disco turkey",
        "nope rope",
        "prison pony",
        "furry potato",
    };
    print_if(animals.begin(), animals.end(), is_before_sloth);
}

Látható, hogy a predikátumok paraméterezhetőek lennének. Negatív = 0-nál kisebb (de lehetne 5-nél kisebb, 100-nál kisebb, -800-nál kisebb is). „sloth” előtt (de lehetne „formal chicken” előtt vagy „velocirabbit” előtt is). A predikátum viszont unáris kell legyen (egy paraméterű függvény), mert egy adott szóról van számról kell eldönteni, hogy kell vagy nem kell.

A probléma könnyen kezelhető egy funktor (függvényként viselkedő objektum) bevezetésével. Ehhez hasonlóan:

class Functor {
  private:
    /* tagváltozók ... */

  public:
    bool operator() (T const & x) const {
        return /* ... */;
    }
};

Egy ilyen objektum képes függvényként viselkedni, mert van függvényhívó operátora: operator() nevű tagfüggvénye. Az operátor belsejében viszont nem csak a paraméter látszik (a vizsgálandó adat), hanem a tagváltozók is elérhetőek, amik tetszőlegesen sokan lehetnek.

Tedd sablonná a print_if() predikátum paraméterét, és írj funktorokat, amelyekkel egy adott számnál kisebb számok, illetve az ábécében egy adott szót megelőző szavak írhatók ki! Ha mindent jól csinálsz:

int main() {
    int numbers[5] = { 6, -5, 9, 12, -8 };
    print_if(numbers, numbers + 5, LessThan(8));  // 6 -5 -8

    std::string animals[5] = {
        "spiky floof",
        "disco turkey",
        "nope rope",
        "prison pony",
        "furry potato",
    };
    print_if(animals, animals + 5, BeforeThan("sloth"));
}

Vedd észre, hogy számokra és sztringekre a „kisebb-e”, illetve „ábécében előrébb van-e” függvények (funktorok) igazából ugyanúgy működnek, az x < y operátort használják. Egyesítsd a LessThan és a BeforeThan osztályodat egyetlen LessThan osztállyá, amelynek sablonparamétere a kezelt típus!

int main() {
    print_if(numbers, numbers + 5, LessThan<int>(8));
    print_if(animals, animals + 5, LessThan<std::string>("sloth"));
}

Írj függvénysablont, amely megszámolja egy (tömb-)tartományban az adott tulajdonságú elemeket!

• Az első két paraméter a bemeneti tartomány, [balról zárt, jobbról nyílt) intervallum (lásd fent).
• A harmadik paraméter a predikátum.
• A visszatérési érték a darabszám.

int main() {
    int numbers[10] = { 9, 5, -8, 4, -6, 7, 9, 1, 2, -9 };

    int cnt = count_if(numbers, numbers + 10, LessThan<int>(5));
    std::cout << "A tömbben " << cnt << " db 5-nél kisebb szám van.";
}

Írj függvénysablont, amely egy (tömb-)tartomány elemeit másolja egy másik tömbbe, de csak akkor, ha az elemek egy bizonyos feltételnek megfelelnek!

• Az első két paraméter a bemeneti tartomány, [balról zárt, jobbról nyílt) intervallum.
• A harmadik paraméter a cél tömb kezdőcíme.
• A negyedik paraméter a predikátum.
• A visszatérési érték egy pointer, amelyik azt mutatja, hogy a cél tömbben meddig lettek adatok.

int main() {
    int numbers[10] = { 9, 5, -8, 4, -6, 7, 9, 1, 2, -9 };
    int negative[10];

    int *p = copy_if(numbers, numbers + 10, negative, LessThan<int>(0));
    std::cout << "A cél tömbbe " << (p-negative) << " elem került:";
    for (int *i = negative; i != p; ++i)
        std::cout << *i << " ";
}

A rendezéshez kétparaméterű, bináris predikátum kell (binary predicate): a rendezés közben a kérdésünk mindig az, hogy a két vizsgált elem közül melyik való előbbre a tömbben.

Írj rendezőfüggvényt, amely paraméterként egy tömb kezdőcímét és méretét kapja, továbbá egy bináris predikátumot (komparátort), amely a rendezési szempontot adja meg!

int main() {
    int numbers[10] = { 9, 5, -8, 4, -6, 7, 9, 1, 2, -9 };

    my_sort_1(numbers, 10, less);       // a<b -> növekvő sorrend
    my_sort_1(numbers, 10, greater);    // a>b -> csökkenő sorrend
}

Ha nem tetszik, hogy meg kell írni a less és greater függvényeket, használhatod a beépített funktorokat: std::less<int> és std::greater<int>, az #include <functional> fejlécfájlból. Ügyelj arra, hogy ne függvénypointereket használj a kódodban; az előbb említett funktorok osztályok, amelyeket példányosítani is kell.

Írd meg úgy a rendezőfüggvényt, hogy ne tömböt és méretet, hanem a fent látott módon pointerekkel megadott tartományt vegyen át paraméterként!

int main() {
    int numbers[10] = { 9, 5, -8, 4, -6, 7, 9, 1, 2, -9 };

    my_sort_2(numbers + 2, numbers + 8, less);       // csak a belsejét
}

Extra: írd meg úgy a rendezést, hogy a pointernek csak a ++, *, == és != operátorát használod! Tehát ptr-ptr tilos, ptr[i] tilos, ptr+int tilos. Később meglátod, ennek mi a jelentősége.

Mi a hiba az alábbi kódban?

Legalább háromféleképpen lehet javítani. Hogyan?

#include <iostream>

template <typename T>
void print_if(T* arr, size_t siz, bool (*pred)(T)) {
    for (size_t i = 0; i < siz; ++i)
        if (pred(arr[i]))
            std::cout << arr[i];
}

bool is_negative(int x) {
    return x < 0;
}

bool is_before_sloth(std::string const & x) {
    return x < "sloth";
}

int main() {
    int numbers[5] = { 6, -5, 9, 12, -8 };
    print_if(numbers, 5, is_negative);

    std::string animals[5] = {
        "spiky floof",
        "disco turkey",
        "nope rope",
        "prison pony",
        "furry potato",
    };
    print_if(animals, 5, is_before_sloth);
}