Feladat: olvassunk be a szabványos bemenetről fájl végéig valós számokat, és írjuk vissza fordított sorrendben. Írjunk ehhez egy tárolót, ami ezt minél egyszerűbbé teszi!
A példánkban az egyszerűség kedvéért fixen double-öket fogunk tárolni. Nincs akadálya, hogy bármilyen T-t tároljunk, csak a szintaktika lenne némileg bonyolultabb, számunkra most nem érdekes.
A Prog1-ből ismerős feladat legegyszerűbben verem (Stack) adatszerkezettel oldható meg. A veremnek logikailag két alapművelete van, egy tárolt elem berakása (push), és kivétele (pop). Néhány megvalósításban a pop érték szerint visszaadja a tárolt elemet, ami több okból is kényelmetlen. Egy veremben a felső elemet látjuk anélkül, hogy kivennénk, így ha mi bármit szeretnénk csinálni a veremmel, nem feltétlenül kell módosítanunk a tartalmát. Ezért a legtöbb megvalósításban a top tagfüggvény adja vissza a legfelső elem referenciáját, és a pop nem ad vissza semmit, csak törli a legfelső elemet.
Tetszőleges típust tároló veremnél kivételkezelési okokból sem jó ötlet a két alapűveletes megvalósítás, ennek miértje azonban túlmutat a tárgy keretein.
A feladat megoldása verem használatával tehát a lenti kódra egyszerűsödik. Már csak a Stack-et kell implementálnunk.
Stack stack;
double d;
while (std::cin >> d)
stack.push(d);
while (!stack.empty()) {
std::cout << stack.top() << std::endl;
stack.pop();
}Az 5. fejezetben megismert std::vector osztálysablon egy dinamikus tömböt valósít meg, amelynek a végére hatékonyan tehetünk be elemeket (push_back), közben csak ritkán foglal újra, és a memóriát sem pazarolja.
Ha egy vermet szeretnénk implementálni, abban is lehetne használni ugyanezt az adatszerkezetet. A vektort nyújtani vagy rövidíteni természeténél fogva csak az egyik végén hatékony, a veremnél viszont a másik végéhez hozzá se szabad nyúlni. Kézenfekvőnek tűnik az ötlet, hogy a Stack osztályunk megvalósításához használjunk std::vector-t.
Kompozíció és továbbítás
Az első helyes megközelítés szerint a Stack tartalmaz egy std::vector-t, és a három alapművelet igazából a vektor műveleteire való "lefordítás".
class Stack {
std::vector<double> adat;
public:
void push(double uj) {
adat.push_back(uj); // végére beszúr
}
void pop() {
adat.pop_back(); // végéről levesz
}
double& top() {
return adat.back(); // utolsó elem
}
double const& top() const {
return adat.back();
}
};Az egyszerű használathoz ezeken kívül szeretnénk tudni lekérdezni, hogy üres-e a verem, illetve mekkora a mérete. Ezt az std::vector-tól az empty és size tagfüggvényekkel kérdezhetjük le, és a Stack-nek ugyanezen a néven illene létrehozni őket, a konzisztencia érdekében.
class Stack {
std::vector<double> adat;
public:
// ...
bool empty() const {
return adat.empty();
}
int size() const {
return adat.size();
}
};Ez így eléggé sormintagyanús. Ha további függvényeket szeretnénk delegálni az std::vector-ból, a vektor tagfüggvényeinek a deklarációját le kell másolnunk. A tartalmuk sima paramétertovábbítás, és a visszatérési értéket is változatlanul kell visszaadnunk. Ráadásul ha esetleg változna az std::vector bármely tagfüggvényének a fejléce, a Stack-ünket hozzá kell igazítanunk, csak azért, hogy a továbbítás továbbra is helyes maradjon.
Privát öröklés és delegálás
Sok esetben a fenti megoldás túl kényelmetlen, jó lenne a delegálást egyszerűbben megoldani. A vektor és a verem közötti kapcsolat különbözik az eddig bemutatottaktól. A Stack belső működése lehet olyan is, mint egy std::vector. Annyiban, hogy vermet építhetünk egy dinamikus tömb felhasználásával. Ilyenkor a Stack csak a lelke mélyén egy vektor, nem köti mindenkinek az orrára, erről más nem tudhat. Például nem enged meg mindent, amit egy vektor megenged magának: a közepét nem módosíthatjuk, csak a tetejét látjuk.
Bizonyos műveleteket ő maga "lerendez" a vektorral (push, pop, top), másokat egyszerűen rábíz a vektorra (size, empty), és semmi mást nem enged másoknak, nehogy elszemtelenedjenek. Úgy is lehetne mondani, hogy megörököl a vektortól néhány, gondosan kiválasztott funkciót.
Erre a kapcsolatra ez a C++ jelölés:
class Stack : private std::vector<double> {
};Ezzel az eszközzel a Stack-ünk leírása némileg egyszerűsödik. A Stack az ősosztály minden tagfüggvényét örökli, private láthatósággal, ezért a push, pop és top függvényeinkben sajátként használhatjuk őket:
class Stack : private std::vector<double> {
std::vector<double> adat;
public:
void push(double const& uj) {
push_back(uj); // végére beszúr
}
void pop() {
pop_back(); // végéről levesz
}
double& top() {
return back(); // utolsó elem
}
double const& top() const {
return back();
}
};Ha az így privátként megörökölt függvényeinket publikussá szeretnénk tenni (pl. size, empty), a using kulcsszó egy számunkra új használatával érhetjük el:
class Stack : private std::vector<double> {
// ...
public:
using std::vector<double>::empty;
using std::vector<double>::size;
};Ezt hívják privát öröklésnek vagy korlátozó öröklésnek is. Fontos megjegyezni, hogy semmi köze az OOP értelemben vett örökléshez, teljesen más a célja. Gyakorlatilag a tartalmazás + továbbítás egyszerűbb leírási formája.
Miért nem publikus öröklés?
Sokakban felmerül az ötlet, hogy az adapterosztályt publikus öröklés segítségével implementálják. Ez a megközelítés azonban a legtöbbször hibás.
Egy adapterosztály az esetek túlnyomó többségében szűkít vagy módosít az implementáláshoz segítségül hívott osztály interfészén. Nem engedi használni minden tagfüggvényét, esetleg egy létező tagfüggvény viselkedését módosítja. Utóbbira lehet példa egy olyan vektor, aminek az indexelő operátora szükség esetén megnyújtja a tárolót. Ha ehhez publikus öröklést használ, annak a legfontosabb alapelvét sérti, a Liskov Substitution Principle-t. Az LSP szerint ami az ősosztályon megengedett, annak a leszármazotton is helyesnek és azonos viselkedésűnek kell lennie. Márpedig egy std::vector-nak szabad a közepére elemet beszúrni, a Stack-nek viszont nem, ez tehát mindenképpen sértené az LSP-t.
A minden micsoda micsoda viszony az indexelésre nyújtózkodó vektorra sem áll fenn. Az std::vector indexelő operátora garantálja, hogy a tároló méretét nem változtatja meg, így ezt a leszármazottól is jogosan várnánk el.
Ráadásul a publikus öröklés azért publikus, mert mindenki ismeri az öröklési viszonyt. Tehát a leszármazott → ős konverzió helyes: csendben, gond nélkül átadhatnánk a Stack-et std::vector&-et váró függvénynek, ami bármit bárhol módosíthat rajta, és erre a fordítótól még figyelmezetést sem kapnánk. Persze, hiszen mi azt hazudtuk a fordítónak, hogy minden Stack egy vektor, amit kénytelen elhinni.
Egy osztály (pl. az std::vector) kódjának ilyen felhasználására nem a publikus öröklés való, hanem a tartalmazás és a privát öröklés. Ezért is írtuk, hogy a privát öröklés nem is öröklés.
Az alaposztály: std::deque
Az std::deque egy mindkét végén módosítható várakozási sor.
A neve a double-ended queue rövidítése, és ugyanúgy kell ejteni, mint a deck-et.
A jellemző műveletei: push_back, pop_back, push_front és pop_front, amelyek a sor végére illetve elejére tesznek be új elemet, illetve vesznek ki elemet. A végét és az elejét a back és a front tagfüggvényei adják vissza.
Ezen felül rendes sorozattárolóként is viselkedik, mint mondjuk egy std::vector: indexelhető, iterálható, lekérdezhető a mérete, de elsősorban nem erre lett kitalálva, hanem az elejének és a végének a gyors módosítására.
Ha egy tárolónak mindig csak az egyik végére teszünk elemet, és csak az egyik végéből veszünk el elemet, jellegzetes tárolókat kapunk, amik szemantikailag különlegesek. Ezért az STL-ben definiáltak két adaptert, ami szemantikailag egyértelművé teszi, hogyan használjuk a tárolót, a nem jellemző műveletek elrejtésével.
std::stack
Ha a tárolónak ugyanarról a végéről veszünk el, ahova teszünk, az egy LIFO (last in, first out) tároló, azaz egy verem (stack). Az std::stack template osztály alapértelmezetten egy std::deque<T> felhasználásával biztosítja a felhasználója számára a LIFO műveleteket: push, pop, top. A felhasznált tároló egyébként a stack második sablonparaméterével adható meg igény esetén.
Az alábbi kódrészlet például a standard inputon kapott szavakat kiírja a standard outputra, fordított sorrendben.
std::stack<string> verem;
std::string elem;
while (std::cin >> elem)
verem.push(elem);
while (!verem.empty()) {
std::cout << verem.back();
verem.pop();
}std::queue
Ha a tároló a másik végéről veszünk el, akkor egy FIFO (first in, first out) tárolót, azaz egy várakozási sort (queue) kapunk. Ugyanúgy paraméterezhető, mint a std::stack, a jellemző műveletei pedig push, pop, front és back. Mindig a tároló végére teszi az új elemet, és az elejéről veszi ki.
Az alábbi kódrészlet például a standard inputon kapott szavakat kiírja a standard outputra, ugyanabban a sorrendben.
std::queue<string> sor;
std::string elem;
while (std::cin >> elem)
sor.push(elem);
while (!verem.empty()) {
std::cout << sor.front();
sor.pop();
}A RAII-s fejezetben használtunk egy elképzelt Matrix osztályt, ami egy kétdimenziós double-tömböt jelentett. Az biztos, hogy a belsejében valahogyan dinamikus memóriát kezel, mert akármekkora méretű mátrixot beletehettünk. Mivel a másoló konstruktor és társai jól működtek, ezért vissza lehetett adni érték szerint. A konstruktorban adtuk meg a dimenziókat, és függvényhívás operátort használtunk az indexelésre. Valahogy így:
Matrix m(3, 4); // 3 magas, 4 széles, 0-kkal feltöltve
m(1, 2) = 1.0; // 1. sor 2. oszlopában lévő elem értéke legyen 1
std::cout << m(1, 2); // 1.0A dinamikus memóriakezelés egy lehetséges, hatékony módjára az 5. gyakorlaton láttunk példát. A trükk lényege az, hogy az elemeket sorfolytonosan, kilapítva tároltuk. Így egyetlen dinamikusan foglalt memóriaterülete van a mátrixunknak:
A dinamikus memóriakezelést a gyakorlaton "kézzel" csináltuk, most nézzünk meg egy egyszerűbb megoldást. A dinamikusan foglalt tömbre már létezik az STL-ben egy osztály, az std::vector, használjuk fel!
Az egyes elemek indexeléséhez tudnunk kell (azaz el kell tárolnunk), hogy milyen hosszú egy sor, a példánkban 4. Így ha az (1, 2) elemet akarjuk elérni, az kilapítva az 1 * 4 + 2 = 6 indexű elemet kell visszaadnunk. A vektor hossza lekérdezhető, így a magasságot egy osztással megkaphatjuk.
class Matrix {
int sz;
std::vector<double> szamok;
public:
Matrix()
: sz(0)
, szamok() // üres vektor
{ }
Matrix(int magassag, int szelesseg)
: sz(szelesseg)
, szamok(magassag * szelesseg) // a vector konstruktora 0-kkal tölti fel
{ }
int szelesseg() const {
return sz;
}
int magassag() const {
return szamok.size() / sz;
}
double& operator()(int sor, int oszlop) {
return szamok[sor * sz + oszlop];
}
const double& operator()(int sor, int oszlop) const {
return szamok[sor * sz + oszlop];
}
};Így bár ugyanolyan a memóriaképe az osztálynak, megúsztuk a memóriakezelést. Az osztály interfésze pedig a gyakorlaton előállthoz képest nem változott – azaz a globális függvényként megírt operátorokat – összeadás, szorzás, stb. – átemelhetjük változtatás nélkül. Ez az egyik előnye, hogy globálisként valósítottuk meg őket.
Az egységbe zárás elvét ezzel nem sértettük meg. Azt és csak azt tettük az osztály belsejébe, aminek feltétlenül ismernie kell a belső implementációt, de az operátoroknak nem kell.