Gyakorló feladatok (10. hét)

Fontosabb kulcsszavak, fogalmak

• Standard Template Library (STL)
• Tárolók, tárolók műveletei
• Sorozattárolók
• Asszociatív tárolók
• Generikus algoritmusok
• Iterátorok

Feladatok megoldásokkal

1. Ismételjük át sorozattárolók közös metódusait és az std::vektor speciális metódusait az az STL összefoglaló alapján: http://infocpp.iit.bme.hu/sites/default/files/proga2/stlsummary.pdf! A közös metódusok hasonlítanak a korábban készített gyak::Array tárolónk metódusaihoz. A hasonlóság nem véletlen!
2. Magától értetődő, de talán mégis érdemes megnézni, hogy többdimenziós vektort (mátrixot) hogyan lehet létrehozni. Mit ír ki a következő kódrészlet?
   

   	
   vector<vector<int> > d2int(5, vector<int>(10, 3));
   for (size_t i = 0; i < 5; i++) {
       for (size_t j = 0; j < 10; j++) 
           std::cout << d2int[i][j] << " ";
       std::cout << endl;
   }
   

3. Készítsünk általános kiíró függvényt a hasonló felépítésű mátrixokhoz! Milyen tárolókkal működik?
   
   
   

   ???

   template <typename T>
   void printMat(const T& mat) {
       for (size_t i = 0; i < mat.size(); i++) {
         for (size_t j = 0; j < mat[i].size(); j++)
           std::cout << mat[i][j] << " ";
         std::cout << endl;
       }
   }
   

4. Vektor, lista iterator: hozzunk létre tömbből vektort, majd abból listát iterátorral:
   
   
   

   ???

       int t[] = { 1, 2, 3, 4, 5, 6 };
       vector<int> v1(t, t+6);
       list<int> l1(v1.begin(), v1.end());
       for (list<int>::iterator i = l1.begin(); i != l1.end(); ++i)
          cout << *i << endl;
   

5. Csapatokat szeretnénk alkotni. Első körben a csapatnak csak neve van (egyedi) és a csapat tagoknak is csak neve van (csapaton belül egyedi). Szeretnénk mindenféle okos névsorokat gyártani. Ha csak a neveket kell tárolni, akkor ez a fésűs listának kinéző feladat halmazok map-jével megoldható:
   

   std::map<std::string, std::set<std::string> > csapatok;
   

   A csapatnevek egyediségét a map, a csapattagok nevének csapaton belüli egyediségét pedig a set biztosítja. Olvassunk névpárokat a standard inputról (csapat, tag), és tegyük bele a tárolónkba:
   

   
   

   ???

   std::string csnev, nev;
   while (cin >> csnev >> nev)
       csapatok[csnev].insert(nev);
   

   
   Írjuk ki a neveket csapatonként rendezve! Mind a map, mind a set rendezve tárol, ezért csak be kell járnunk a tárolókat és kiírni. A bejáráshoz használhatjuk a for_each algoritmust, ami minden elemre meghív egy függvényt/funktort. Ez egy pair-t fog paraméterként kapni, aminek ez első eleme a csapat neve, a második pedig a csapattagok halmaza. Ezt a halmazt kell bejárnunk a csapattagok nevének kiírásához. Kevésbé igényesen, de kiírás ostream_iterátorral is elvégezhető.
   
   
   

   ???

   void cslist(pair<std::string, set<std::string> > p) {
       ostream_iterator<std::string> osit(std::cout, "\n");
       std::cout << "--- Csapat: " << p.first << std::endl;
       copy(p.second.begin(), p.second.end(), osit);
   }
   

   Végül a kiírás így néz ki:

   for_each(csapatok.begin(), csapatok.end(), cslist);
   

6. Alakítsunk ki egy olyan fésűs tárolót, amiben Jatekos pointereket tárolunk! A játékos legyen a legegyszerűbb szerkezetű, mivel nem ez most a lényeg:
   

   class Jatekos {
       std::string nev;
       int pont;
   public:
       Jatekos(std::string n, int p) :nev(n), pont(p) {}
       int getPont() const { return pont; }
       std::string getNev() const { return nev; }
   };
   
   std::ostream& operator<<(std::ostream& os, const Jatekos& j) {
       os << j.getNev() << " " << j.getPont();
       return os;
   }

   A fésű gerincének megvalósításához itt is kézenfekvőnek tűnik a map. Mivel valósítsuk meg a fésű fogait? Miben tároljuk a pointereket?

   • set - ettől nem lesznek a játékosnevek egyediek, de az az elemek elérése egyszerű, van find, amivel a beszúrás előtt könnyen tesztelhető a név egyedisége
   • list - kézenfekvő megoldás, de nincs find, nincs at/[]
   • map - van find, van at/[], de bejárás macerásabb a pair miatt
   • vector - nincs find, de van at/[]
   • deque - nincs find, de van at/[]

   A fentiek alapján adott feladatra talán a set tűnik legalkalmasabbnak a find léte miatt, de rá kell jönnünk, hogy a find nem használható az adott nevű csapattag megkeresésére, mivel azzal egy adott pointert kereshetnénk, nem nevet. Hasonló okokból a csapaton belüli automatikus rendezettséget, mint előnyt is elvesztettük. Így a set alkalmazása már nem tűnik jónak, sőt a rendezésnél nehézségeink is lehetek, ha utólag szeretnénk a halmaz elemeit rendezni. Ezzel szemben a halmaz sablon második paramétereként megadható egy alkalmas összehasonlító függvény, amivel a szükséges rendezettség megtartható. Ennek ellenére a gyakorlás kedvéért a halmaz helyett használjunk mást: válasszuk a list tárolót, és próbáljuk névsorban rendezetten tartani:
   

   
   

   ???

   std::map<std::string, std::list<Jatekos*> > csapatok;
   

   Keressük meg beszúrás előtt, hogy az adott nevű játékos már tagja-e a csapatnak! Azt is mondhatnánk, hogy számoljuk meg, hogy hányszor szerepel az adott név a csapatban, ha nullaszor, akkor nincs benne! A számláláshoz a count_if algoritmus pont megfelel egy alkalmas predikátummal. Sajnos közvetlenül egyik STL funktor sem jó, ezért kell írnunk egy funktort:

   struct jatekosFixNevCmp  {
       std::string ezzel;
       jatekosFixNevCmp(std::string n) :ezzel(n){ }
       bool operator()(Jatekos* j) { return j->getNev() == ezzel;}
   };

   Mivel egy objektumpointert tárolunk a fésű fogain, kicsit változnak a kiírás függvényei is:

   void jlist(Jatekos *j) {
       std::cout << "   " << *j << std::endl;   // itt kihasználtuk, hogy a játékos ki tudja írni az adatait
   }
   void cslist2(pair<std::string, list<Jatekos*> > p) {
       std::cout << "Csapat: " << p.first << std::endl;
       for_each(p.second.begin(), p.second.end(), jlist);
   }

   Már csak a rendezetten tartást kell megoldanunk, amit az új elem felvételénél úgy oldunk, meg, hogy az új elmenet betesszük egy egyelemű listába, amit összefésülünk (merge) a már meglevő rendezett listánkhoz. A merge műveletnek kell egy összehasonlító függvény, ami a rendezettséget adja meg:

   bool jatekosNevCmp(Jatekos* j1, Jatekos* j2) { return j1->getNev() < j2->getNev(); }
   

   Most már minden készen áll a kipróbáláshoz:

   int main() {
       std::map<std::string, std::list<Jatekos*> > csapatok;
       string csnev, nev;
       int pont;
       while (std::cin >> csnev >> nev >> pont)
           if (count_if(csapatok[csnev].begin(), csapatok[csnev].end(), jatekosNevFixCmp(nev)) == 0) {
               std::list<Jatekos*> jl(1, new Jatekos(nev, pont));
               csapatok[csnev].merge(jl, jatekosNevCmp);
           }
       for_each(csapatok.begin(), csapatok.end(), cslist2);
       return 0;
   };

   A megoldás szépséghibája hogy nem szabadítja fel a lefoglalt memóriaterületet. Látható, hogy a felszabadításhoz a listázásnál alkalmazott bejárást kellene követnünk. Csupán a tevékenység a más. Érezhető, hogy átgondolás után célszerű lenne külön osztályokat és paraméterként megadható műveleteket definiálni, ami kicsit általánosítva támogatná a fésűs listában való tárolást, bejárást, kezelést.

7. Visszatekintve az előző két feladatra, érdemes a tárolók különbségének okán elgondolkodni. A pointeres esetben set nyújtotta előnyöket egyáltalán nem tudtuk kihasználni. Mi ennek az oka? Az, hogy pointeres esetben a rendezési szempontot nem a tárolt adat adja (ha nem írunk saját hasonlítót a set-hez ill. a map-hez). Ha a pointerek helyett objektumokat tárolnánk, akkor a tároláskor alapértelmezetten használt összehasonlítás (less) művelete az objektum szintjén felüldefiniálható lenne. Nézzük meg így a feladatot:
   
   
   

   ???

   #include <iostream>
   #include <sstream>
   #include <map>
   #include <set>
   #include <iterator>
   #include <algorithm>
   
   // Csapat osztály amiben a név mellett van még egy int is.
   struct Csapat {
       std::string nev;
       int hely;
       bool operator<(Csapat cs) const { return nev < cs.nev; }  // összehasonlítható
   };
   // Kiírható
   std::ostream& operator<<(std::ostream& os, const Csapat& cs) {
       return os << cs.nev << "  " << cs.hely;
   }
   
   // jatekos osztály amiben a név mellett van még egy int is.
   struct Jatekos {
       std::string nev;
       int pont;
       bool operator<(Jatekos j) const { return nev < j.nev; }  // összehasonlítható
   };
   // Kiírható
   std::ostream& operator<<(std::ostream& os, const Jatekos& j) {
       return os << j.nev << "  " << j.pont;
   }
   
   // Egy adott csapatot kilistázó függvény
   void cslist(std::pair<Csapat, std::set<Jatekos> > p) {
       std::ostream_iterator<Jatekos> osit(std::cout, "\n");
       std::cout << "--- Csapat: " << p.first << std::endl;
       copy(p.second.begin(), p.second.end(), osit);
   }
   
   int main() {
       std::map<Csapat, std::set<Jatekos> > csapatok;
       std::stringstream ss;
       std::string s;
       s =  "Rokkerek 1 Lajos 10\nRokkerek 1 Tamas 8\nRokkerek 1 Lajos 12";
       s += "Funktorok 1 Geza 10\nFunktorok 1 Zoli 6\nFunktorok 1 Bela 6\n";
       ss.str(s); 
   
       Csapat cs;
       Jatekos j;
       while (ss >> cs.nev >> cs.hely >> j.nev >> j.pont)
           csapatok[cs].insert(j);
       for_each(csapatok.begin(), csapatok.end(), cslist);
   
       return 0;
   }

   Így a dinamikus memória kezelés is eltűnt. De tényleg nincs most a programban?