Útmutató a 10. laborhoz

Felkészülés a laborra

Ismételje át a 10. és a 11. előadás anyagát!
Nézze át a 9. laborgyakorlat

A laborgyakorlat az STL algoritmusok és tárolók gyakorlati felhasználásához kíván mélyebb ismereteket adni. A gyakorlat több egymásra épülő feladatot tartalmaz, melyben példát látunk az öröklés az adapter tervezési minta alkalmazására is. A 9. laboron kiegészített Array sablonból fix méretű generikus vektort készítünk.

A laborfoglalkozás végén a vektor.hpp, a mystack.hpp és a vektor_test.cpp fájlt kell feltöltenie a Jporta rendszerbe (10. önellenőrző feladat), hogy megkapja a labor elvégzéséért járó pontot! Legalább az első öt tesztesetet (ELEKESZULT >= 5) hibátlanul meg kell oldania! A feladatok feltöltésére a laborgyakorlatot követő szombat 06:00-ig van lehetősége.

Töltse le az előkészített projektet https://git.ik.bme.hu/Prog2/labor_peldak/lab_10, majd nyissa meg a projektet. Tekintse át a fájlokat:
- A gen_array_iter3.hpp állományban a 9. laboron is használt generikus tömb (Array) megvalósítását találja két apróbb kiegészítéssel:
  1. Bevezettünk egy void setsize(size_t) protected függvényt, hogy az osztály leszármazottai tudják változtatni a tömbben levő adatok számát. Ezt a siz tagváltozó protected elérésével is megoldhattuk volna, de úgy nem lenne lehetőség ellenőrzésre.
  2. Az iterator osztályt az std::iterator osztályból származtattuk. Ennek magyarázatát később adjuk meg (ld. Extra).
- A vektor.hpp állományban található a Vektor sablon hiányos deklarációja. A feladatok megoldása során részben a hiányzó tagfüggvényeket kell ebben a fájlban elkészítenie.
- A vektor_test.cpp állományban található a tesztelést (inkább próbálgatást) végző program, amit szintén ki kell majd egészítenie. Az egyes tesztesetek működését a korábbi laboralkalmakkor is használt ELKESZULT makró vezérli. Az eredmények kiértékelése ezen a laborgyakorlaton a kiírások megfigyelésével történik, most nem használunk tesztelést segítő keretrendszert.
- A mystack.hpp és compat.hpp állományoknak később lesz szerepük.
Állítsa a vektor_test.cpp fájl elején definiált ELKESZULT makró értékét 0-ra! Fordítson, futtasson! A 0. teszteset a 9. laborgyakorlaton elkészített ostreamFunktor-t és a forEach függvénysablont használja az it1 tömb adatainak kiírásához.

Az STL algoritmusok rövid leírását megtalálja a ZH-n is használható STL összefoglalóban, vagy részletesebben a http://www.cplusplus.com/reference/algorithm oldalon.

Az előadáson láthatta, hogy az STL (Standard Template Library) számos hasznos algoritmust és függvényt tartalmaz. Az egyik ilyen az std::for_each algoritmus, melynek működése pontosan megfelel a 9. laboron elkészített forEach() függvénysablonnak. Egészítse ki a tesztprogramot úgy, hogy az std::for_each algoritmussal írjon ki. A funktort paraméterlistán példányosítsa! Állítsa az ELKESZULT makró értékét 1-ra! Fordítson, futtasson!
Ha nem világos, mi a feladat, nézze meg a megoldást!
```
#if ELKESZULT >= 1
/// 1. feladat:
        /// Kiírás std::for_each segítségével
        /// A funktort a for_each paraméterlistáján példányosítsa!
        /// Próbálja ki!
        cout << "it1 (for_each): ";
        std::for_each(it1, it1+10, ostreamFunctor<int>(cout, ", "));
		cout << endl;
#endif // ELKESZULT >= 1
```
Az ELKESZULT >= 2 esetben a program létrehoz egy maximum 50 elemű valós vektort, és feltölti az első 8 elemét 5.1 értékkel! Az előző feladathoz hasonlóan egészítse ki a kódot a vektor elemeinek kiírásával! Állítsa az ELKESZULT makró értékét 2-re! Fordítson, futtasson!
???
```
		std::for_each(otos.begin(), otos.end(), ostreamFunctor<double>(cout, ", "));
```
Az ELKESZULT >= 3 esetben a program létrehoz egy maximum 100 elemű valós vektort, és feltölti dt1 tömb adataival. Melyik konstruktor kell a működéshez? Van a Vektor-nak olyan konstruktora? Egészítse ki a sablont a vektor.hpp állományban!
Állítsa az ELKESZULT makró értékét 3-ra! Fordítson, futtasson!
???
```
    template <class InputIterator>
    Vektor(InputIterator first, InputIterator last)
        : Array<T, maxsiz>(first, last) {
    }
```
Az STL-ben megvalósított sorozattárolók számos alapvető fontosságú tagfüggvénnyel rendelkeznek, így többek között a bush_back(), back(), pop_back() és empty() tagfüggvényekkel is. Ezek egyikét sem valósítja meg az Array sablon, így az abból származó Vektor sablon sem. Keresse meg ezeket a tagfüggvényeketet az STL összefoglalóban (2.2 Conatiners–Common és 2.3 Sequence Containers)!
Ötlet: Az at() tagfüggvény képes új elemet felvenni, és növeli a méretet is.

Valósítsa meg a push_back() tagfüggvényt a vektor.hpp állományban, majd állítsa az ELKESZULT makró értékét 4-re! Fordítson, futtasson!
Emlékeztetőül a tagfüggvények funkciói és paraméterei:
```
bool empty() const;         // igaz, ha üres
void push_back(const T& t); // hozzáfűz egy elemet a tárolt sorozat végéhez
T& back();                  // visszaadja a tárolt sorozat utolsó elemének referenciáját 
void pop_back()             // töröl egy elemet a sorozat végéről. 
```
???
```
   void push_back(const T& val) {
       this->at(Array<T, maxsiz>::size()) = val;
   }
```

Valósítsa meg a back(), pop_back() és empty() tagfüggvényeket is a vektor.hpp állományban, majd állítsa az ELKESZULT makró értékét 5-re! Fordítson, futtasson!

???

    T& back() {
        return this->at(Array<T, maxsiz>::size()-1);
    }

    void pop_back() {
        Array<T, maxsiz>::setsize(Array<T, maxsiz>::size()-1);
    }

    bool empty() {
        return Array<T, maxsiz>::size() == 0;
    }

A 9. laboron elkészített szamol_ha sablonhoz hasonlóan működik az std::count_if algoritmus. Az ELKESZULT >= 6 tesztesetben az std::count_if felhasználásával írja ki az it1 tömbben levő negatív elemek számát! A fájl elején talál ehhez a feladathoz egy funktort (negatív). Állítsa az ELKESZULT makró értékét 6-re! Fordítson, futtasson!
???
```
      cout << std::count_if(it1, it1+10, negativ<int>());
```
Állítsa az ELKESZULT makró értékét 7-re és egészítse ki a tesztprogramot úgy, hogy a darr vektorban is megszámolja a negatív elemeket. Fordítson, futtasson!
???
```
       cout << std::count_if(darr.begin(), darr.end(), negativ<double>());
```
Az STL egyszerű lehetőséget kínál a predikátumok előállítására is. Számos jól használható egy- és kétoperandusú funktort definiál (ld. functional header). Jól használhatók az összehasonlító függvényobjektumok, mint pl. az std::greater, vagy a std::less. Ezek két generikus adatot hasonlítanak össze, ezért két paramétert várnak. Így közvetlenül nem használhatók az std::count_if predikátumaként. A problémát az ún. lekötő függvénysablonokkal (bind1st, bind2nd) tudjuk megoldani. Ezek egyparaméteres funktort készítenek a kétparaméteres függvényekből. Pl. az
```
std::bind2nd(std::greater<int>(), 1)
```
kifejezés egy olyan 1 paraméteres függvényként használható objektumot állít elő, ami megállapítja, hogy a paraméterként kapott egész nagyobb-e, mint 1. Az objektumot tipikusan a paraméterlistán hozzuk létre, de külön is hivatkozhatnánk rá például így:
```
std::unary_function<int, bool> f = std::bind2nd(std::greater<int>(), 1);
int i = 8;
if ( f(i) ) ....
```
A C++11 szabvány a bind1st és bind2nd helyett általánosabb megoldást kínál (bind), így a fent bemutatott megoldást elavultnak tekinti. A C++17 pedig már nem is támogatja még az unary/binary_function sablonokat sem, ami az összes egy- illetve kétoperandusú függvény alapja (ld. functional). Sajnos visszafelé kompatibilis megoldást ezen a téren egyik új változat sem kínál, pedig sablonokkal megoldható lenne. A legacy kódok miatt azonban mindenképpen érdemes megismerni ezeket az eszközöket és elveket, illetve magát a problémát. Egy egyszerű sablon+makró (compat.hpp) megoldással azonban a bind1st és bind2nd verziófüggetlenül használható.
A bind2nd használatával számolja meg, hogy hány 100-nál kisebb érték van az darr vektorban! Állítsa az ELKESZULT makró értékét 8-ra! Fordítson, futtasson!
???
```
    cout << std::count_if(darr.begin(), darr.end(), std::bind2nd(std::less<double>(), 100));
```
Az std::copy algoritmus az iterátorokkal megadott adatsorozatot egy másik, szintén iterátorokkal megadott helyre másolja. Az std::ostream_iterator egy olyan speciális iterátor, ami értékadáskor nem egy tárolóba írja az adatot, hanem egy stream-be. Állítsa az ELKESZULT makró értékét 9-re! Fordítson, futtasson! Értse meg, a kiírás ezen módját is!
Az ELKESZULT == 10 esetben a tesztprogram a darr nevű objektumból törli az 100-nál kisebb számokat az std::remove_if algoritmussal! Ahogyan az előadáson is látta, a remove_if nem változtatja a tárolóban tárolt adatok számát, csak kiveszi a feltételnek eleget tevő elemeket a tárolóból. Így a tároló végén valamilyen adatszemét marad. Állítsa az ELKESZULT makró értékét 10-re! Fordítson, futtasson! Figyelje meg az adatszemetet!

A tároló végén maradó felesleges adatot célszerűen az erase() tagfüggvénnyel lehet eltávolítani. Minden sorozattárolónak van erase() tagfüggvénye. A mi vektorunknak nincs. Valósítsa meg az erase tagfüggvényt a vektor.hpp állományban! Állítsa az ELKESZULT makró értékét 11-re! Fordítson, futtasson!
Az erase tagfüggvénynek két módozata van:

iterator erase ( iterator position );               // törli az adott pozíción levő elemet
iterator erase ( iterator first, iterator last );   // törli a [first, last) intervallumban levő elemeket

A visszatérési érték mindkét esetben az utoljára törölt elem utáni elem új helyére mutat.

Az elemek törlésével járó másolás iterátorokkal könnyen megoldható. Egyedüli problémát a tároló méretének változtatása okozhatja. Ebben pedig segít setsize függvény.

???

A vektor.hpp-ben kell megvalósítani az erase függvényeket pl. így:

...
    /// A továbbiakban egyszerűbben hivatkozhassunk az iterator-ra, mint típusra
    typedef typename Array<T, maxsiz>::iterator iterator;
    
	/// törli az adott pozíción levő elemet
    /// @param pos - a törlendő elemre mutató iterátor
	/// @return az első nem törölt elemre mutató iterátor, ha végéig törölt, akkor end()
    iterator erase(iterator pos) {
        iterator first = pos++;
        return erase(first, pos);
    }

    /// törli az adott intervallumba eső elemeket
    /// @param first - a törlendő intervalum eleje
    /// @param last - a törlendő intervallum vége
	/// @return az első nem törölt elemre mutató iterátor, ha végéig törölt, akkor end()
    iterator erase(iterator first, iterator last) { // törli a [first, last) intervallumban levő elemeket
        iterator ret = first;       // ez az első nem törölt elem helye
        while (last != Array<T, maxsiz>::end()) // átmásoljuk a törlendők mögötti részt, ha van ilyen
           *first++ = *last++;      // a törlendő területre
        size_t len=0;
        while (first != last) {     // last-first távolság nem változik
           len++;                   // megszámoljuk, milyen hosszú a törlendő;
           first++;
        }
        Array<T, maxsiz>::setsize(Array<T, maxsiz>::size()-len);                 // a méretet ennyivel csökkentjük
        return ret;
    }
...

Megj: Az erase() megvalósításához az STL tárolok legalább Random Access Iterator-t használnak, melyeknél a kivonés művelete is érvényes. Megoldásunkban az intervallum hosszának ciklussal való megszámolásával azonban nem kell iterátorokat kivonni, így elegendő a Forward Iterator tulajdonság.

Az STL-ben nem csak tárolók, hanem ún. adapterek is vannak, melyek a generikus tárolókból új tulajdonságú tárolókat hoznak létre úgy, hogy azt beburkolják, és csak az új funkcionalitást mutatják a külvilág felé. Ilyen adapter osztály pl. az std::stack, ami stack (LIFO) interfészbe burkol egy sorozat tárolót. A felhasznált tárolóval szemben támasztott követelmény mindösszesen a következő:

a default konstruktor hozzon létre egy üres tárolót
legyen másoló konstruktora

valósítsa meg a következő tagfüggvényeket:

bool empty() const;         // igaz, ha üres
size_t size() const;        // tárolt elemek száma
void push_back(const T& t); // hozzáfűz egy elemet a tárolt sorozat végéhez
T& back();                  // visszaadja a tárolt sorozat utolsó elemének referenciáját 
void pop_back()             // töröl egy elemet a sorozat végéről.

Ezeket a vektor osztályunk biztosítja.
A mystack.hpp állományban valósítson meg az std::stack adapter felhasználása nélkül egy ahhoz hasonló generikus MyStack adapter osztályt! Az adapter deklarációja a következő legyen:

template <class T, class Container = std::vector<T> > class MyStack;

Valósítsa meg az osztály a következő tagfüggvényeket:

MyStack()                   // üres stack készítése
~MytStack()                 // destruktor
T& top();                   // stack tetején levő elem elérése. Üres tároló esetén dobjon hibát!
void push(const T& t)       // új elemet tesz a stackbe
void pop()                  // törli a legfelső elemet. Üres tároló esetén dobjon hibát!
bool empty()                // igaz értékkel tér vissza, ha a stack üres.

Állítsa az ELKESZULT makró értékét 12-re! Fordítson, futtasson!

???

template <class T, class Container = std::vector<T> >
class MyStack {
    Container tar;
public:
    bool empty() const { 
        return tar.size() == 0; 
    }
 
    T& top() {
        if (empty()) throw std::out_of_range("MyStack.top(): empty");
        return tar.back();
    }
 
    void push(const T& t) {
        tar.push_back(t);
    }
 
    void pop() {
        if (empty()) throw std::out_of_range("MyStack.pop(): empty");
        tar.pop_back();
    }
};

Töltse fel az elkészített vektor.hpp, mystack.hpp, valamint a vektor_test.cpp állományokat a Jporta rendszerbe (10. labor, önellenőrzés! Ne felejtse el átemelni a vektor_test.cpp fáljból az ELKESZULT makrót a feladat készültségi fokának megfelelő értékkel a vektor.hpp fájlba! Ha elfelejti, a Jporta ELKESZULT==5 értéket tételez fel.

Extra:
A gen_array_iter3.hpp állományban az iterator osztály az std::iterator<std::forward_iterator_tag, T> osztályból származik. Ha definiálva van a NO_ARRAY_ITERATOR_TRAITS makró, akkor az iterator osztály nem örököl ebből az osztályból. Definiálja projekt szinten a NO_ARRAY_ITERATOR_TRAITS makrót, és fordítsa újra a programot!

Fordítási hibát kap. Ennek az az oka, hogy az STL-ben levő algoritmusok nagy része (pl. a count_if is) elvárja, hogy a paraméterként kapott iterátorok rendelkezzenek bizonyos jól definiált tulajdonságokkal, belső típusokkal. Egy iterátorral működő generikus algoritmus megvalósítása függhet pl. az iterátor kategóriájától (Input, Output, Random, stb.), ami meghatározza, hogy milyen műveleteket valósít meg az adott iterátor. Ezeket a tulajdonságokat/attribútumokat traits-eknek nevezik, melyeket erre a célra készített sablonok segítségével definiálják. Ilyen az std::iterator sablon:

template <class Category, class T, class Distance = ptrdiff_t, class Pointer = T*, class Reference = T&>
    typedef T value_type; // Ez az adat típusa, amit az iterátorral el lehet érni.
    typedef Distance difference_type; // két iterátor közötti távolság
    typedef Pointer pointer; // az adatra mutató pointer
    typedef Reference reference; // adat referecia típusa
    typedef Category iterator_category; // iterátor kategóriája
};

Látható, hogy az osztálynak működést megvalósító tagfüggvénye nincs is, csupán magától értetődő típusokat definiál. Ez arra jó, hogy a különböző STL algoritmusok ezekre a típusokra hivatkozhassanak. Így a szokásostól eltérő működés a típusokhoz rendelhetően külön megvalósítható. Általában persze jó az alapértelmezés, mint pl. az, hogy a pointer az T*, de ezzel a megoldással egy tömb esetén lehetne akár indextípus is. A kategória (Category) paraméter az iterátor használati módjára utal. Az STL 5 kategóriát különböztet meg:

Category	Kategória neve (Használati mód)
input_iterator_tag	Input Iterator
output_iterator_tag	Output Iterator
forward_iterator_tag	Forward Iterator
bidirectional_iterator_tag	Bidirectional Iterator
random_access_iterator_tag	Random Access Iterator

Az 5 kategória 5 különböző tulajdonsághalmazt jelöl, ami egyben megadja azt a működésre vonatkozó követelményhalmazt is, amit a STL algoritmusok minimálisan elvárnak az adott kategóriában. Bár a kategóriák nem valós osztályok, az osztályok tulajdonságainál megismert jelöléssel tömören megadhatjuk azok jelentését:

Természetesen az output_iterator tulajdonság konstans objektumok esetén nem értelmezett egyik típusnál sem.
Az Array osztályunk csupán a forward_iterator_tag művelethalmazát valósítja meg, ezért ilyen attribútummal látjuk el.

Jó munkát!

Szeberényi Imre

Csatolmány	Méret
iterator_kat.png	22.96 KB

Utolsó frissítés: 2024-01-31 18.22

Keresés űrlap

Útmutató a 10. laborhoz

Felkészülés a laborra

Főmenü