Ebben a tananyagrészben a template osztályokról lesz szó. A template a C++ nyelv terminológiájában típusparaméterezést jelent, vagyis azt oldja meg, hogy ne kelljen egy adatszerkezetből külön létrehozni olyat, amiben inteket tárolunk, illetve olyat, amiben doubleket tárolunk... satöbbi, hanem a példányosításkor eldönthető, hogy az adott adatszerkezetet milyen típussal (ez nem csak alaptípus lehet) használjuk.
előző tananyagrész: öröklődés és polimorfizmus
következő tanayagrész: STL
Tartalom
- sorted array
- sorted list
- priority stack
Sorted array
Ebben a példában egy nagyon egyszerű rendezett tömböt valósítunk meg. Ahogy beleteszünk egy új elemet, az rendezetten lesz beletéve.
Ez egy template osztály, vagyis a példányosításkor meg lehet adni, hogy milyen típusú elemeket tárolunk benne (pl. int, double, esetleg std::string).
A data nevű változóban tároljuk a dinamikusan allokált tömböt.
Nem érdemes mindig egy új elem hozzáadásakor növelni a tömb méretét, hanem például megduplázhatjuk a tömb méret, ha már nem fér el benne több elem. Ekkor viszont kell tárolnunk azt, hogy éppen aktuálisan hány elem van benne (size változó) és hogy mennyi fér el benne maximum (capacity változó).
Konstruktor és destruktor
Akár a konstruktorban is adhatnánk kezdőértéket a size és capacity változóknak, de ebben a példában a változódefinícióban inicializáltuk ezt a két változót.
A konstruktorban allokáljuk a tömböt, a destruktorban pedig felszabadítjuk az általa lefoglalt memóriát.
Osztályon kívül definiált tagfüggvények
Mivel ez egy tempate osztály, ezért minden osztályon kívül definiált tagfüggvény előtt szerepelnie kell ennek a sornak:
template <typename T>Illetve a scope operátor előtt is jelölni kell a típusparamétert, például:
void sorted_array<T>::insert(T element) { /*...*/ }Copy konstruktor
A copy konstruktor akkor fut le, amikor létrehozunk egy sorted_array-t, és annak értékül adunk egy másik (már létező) sorted_arrayt. Például:
sorted_array<int> example2 = example1;A copy konstruktorban átvesszük a másik sorted_array size és capacity változóinak értékét, illetve lemásoljuk a data tömböt.
operator=
Az operator= akkor fut le, ha egy már létrehozott sorted_array-nek adunk értékül egy másik sorted_array-t.
sorted_array<int> example3;
example3 = example2;A copy konstruktorhoz képest annyi eltérés van, hogy egyrészt a láncolhatóság miatt (a = b = c) vissza kell adnunk magát az objektumot (return *this), másrészt ha már van a forrásobjektumnak (amibe át akarjuk másolni a másik objektum adatait) allokált tömbje, azt törölni kell, illetve ellenőrízni kell, hogy nem saját magát akarjuk-e értékül adni, mert akkor a már leallokált tömb törlése hibát eredményezne
operator<< túlterhelése
Sajnos ahhoz, hogy működjön az insertion operátor túlterhelése egy template osztályban, a kód elején szerepelnie kell egy forward deklarációnak, amiben az osztályt és a globális függvényt deklaráljuk.
Ügyeljünk arra, hogy a függvény deklarációjában és definíciójában különböző helyekre kell írnunk típusparamétert.
Deklaráció (az osztályon belül):
friend std::ostream& operator<< <T>(std::ostream& p_ostream, const sorted_array<T>& p_sorted_array);Definíció:
template <typename T>
std::ostream& operator<<(std::ostream& p_ostream, const sorted_array<T>& p_sorted_array) { /*...*/ }A függvénydefiníció viszonylag magától értetődő, egy for ciklussal kiíratjuk az elemeket, majd a láncolhatóság (std::cout << a << b;) érdekében visszaadjuk a streamobjektumot (return p_ostream;).
A tömb növelése
A tömb növelését a data_grow nevű függvény látja el.
Ahogy pakoljuk a tömbbe az elemeket, a size változó úgy növekszik, és ha egyenlő lesz a capacity változó értékével, akkor a duplájára növeljük a capacity változót és újraallokáljuk a tömböt.
Ahhoz, hogy újraallokáljuk a tömböt, törölni kell a régit, ekkor viszont elvesznek az adatok, éppen ezért át kell másolni az adatokat egy másik tömbbe.
Miután felszabadítottuk az eredeti tömböt, ezt a másik tömböt értékül adhatjuk neki, mivel itt dinamikusan allokált tömbökről van szó, amiket pointerekkel kezelünk (hagyományos tömbök esetén nem lehetne egy tömböt egy másik tömbnek értékül adni).
Új elem beillesztése
Az új elem beillesztését az insert függvény látja el.
Ebben a függvényben ellenőrízzük, hogy betelt-e már a tömb, mert ha igen, meg kell növelnünk a data_grow nevű függvénnyel.
Ha a tömbben még nincs egy elem se (azaz size == 0), akkor egyszerűen csak beleteszünk egy elemet, nem kell vizsgálni, hogy a többi elemnél kisebb vagy nagyobb-e.
data[size] = element;Ha a tömbben lévő elemek száma legalább 1 (size >= 1), akkor egy egyszerű algoritmussal szépen végiglépkedünk az elemeken, egészen addig, amíg az adott érték kisebb, mint az addigi elemek, ha nagyobb, akkor a további elemeket először egyel arrébb helyezzük, majd a felszabadult helyre beillesztjük az éppen hozzáadni kívánt elemet.
main függvény
A main függvényben létrehozunk egy int típusú elemek tárolására alkalmas tömböt, elhelyezünk benne néhány tetszőleges elemet, majd a copy konstruktor és operator= működését is leteszteljük.
A teljes példaprogram
//plain sorted array example
#include <iostream>
//this is needed for the overload of insertion operator inside a template class
//forward declaration
template <typename T>
class sorted_array;
template <typename T>
std::ostream& operator<<(std::ostream& p_ostream, const sorted_array<T>& p_sorted_array);
//class definition
template <typename T>
class sorted_array {
public:
//constructor
sorted_array() {
data = new T[capacity];
}
//destructor
~sorted_array() {
delete[] data;
}
//copy constructor declaration
sorted_array(const sorted_array& rhs);
//operator= declaration
sorted_array& operator=(const sorted_array& rhs);
//insertion operator overload declaration
friend std::ostream& operator<< <T>(std::ostream& p_ostream, const sorted_array<T>& p_sorted_array);
void insert(T element);
private:
T* data;
int size = 0;
int capacity = 2;
void data_grow();
};
//copy constructor definition
template <typename T>
sorted_array<T>::sorted_array(const sorted_array& rhs) {
size = rhs.size;
capacity = rhs.capacity;
data = new T[capacity];
for (int i = 0; i < size; ++i) {
data[i] = rhs.data[i];
}
}
//operator= definition
template <typename T>
sorted_array<T>& sorted_array<T>::operator=(const sorted_array& rhs) {
if (this == &rhs) {
return *this;
}
if (data) { delete[] data; }
size = rhs.size;
capacity = rhs.capacity;
data = new T[capacity];
for (int i = 0; i < size; ++i) {
data[i] = rhs.data[i];
}
return *this;
}
//insertion operator overload definition
template <typename T>
std::ostream& operator<<(std::ostream& p_ostream, const sorted_array<T>& p_sorted_array) {
for (int i = 0; i < p_sorted_array.size-1; ++i) {
p_ostream << p_sorted_array.data[i] << ' ';
}
//last element
p_ostream << p_sorted_array.data[p_sorted_array.size-1] << '\n';
return p_ostream;
}
template <typename T>
void sorted_array<T>::data_grow() {
//grow size
capacity *= 2;
//allocate backup array
T* data_backup = new T[capacity];
//copy elements to backup array
for (int i = 0; i < size; ++i) {
data_backup[i] = data[i];
}
//delete original array
delete[] data;
//assign the backup array to original array
data = data_backup;
}
template <typename T>
void sorted_array<T>::insert(T element) {
//adding more capacity if needed
if (capacity == size) {
data_grow();
}
if (size >= 1) {
for (int i = 0; i < size; ++i) {
if (element <= data[i]) {
for (int j = size+1; j > i; --j) {
//move the elements after the inserted element
data[j] = data[j-1];
}
//insert element before the moved elements
data[i] = element;
break;
} else {
//insert element after another elements
data[size] = element;
}
}
} else {
//insert element if the array don't have any elements
data[size] = element;
}
++size;
}
int main() {
sorted_array<int> example1;
//insert test
example1.insert(5);
example1.insert(3);
example1.insert(6);
example1.insert(2);
example1.insert(1);
example1.insert(5);
example1.insert(7);
example1.insert(-3);
//copy constructor test
sorted_array<int> example2 = example1;
//operator= test
sorted_array<int> example3;
example3 = example2;
std::cout << example3 << '\n';
}Sorted list
Ebben a példában egy rendezett listát valósítunk meg az STL-re alapozva. Az stl-ből használni fogjuk az std::listet, az std::less-t és az std::lower_bound függvényt. Látható, hogy ily módon sokkal rövidebb a megvalósítás, mint a fenti példában.
//sorted list example
#include <iostream>
#include <list>
#include <algorithm>
#include <functional>
template <class T, class Comp=std::less<T> >
class SortedList {
std::list<T> c;
public:
typedef typename std::list<T>::const_iterator iterator;
template <class InIt>
SortedList(InIt first, InIt last): c(first, last) {
c.sort(Comp());
}
SortedList() {}
void insert( const T& t) {
c.insert(std::lower_bound(c.begin(), c.end(), t, Comp()), t);
}
int size() const { return c.size(); }
const T& front() const { return c.front(); }
const T& back() const { return c.back(); }
void remove( const T& t ) { c.remove(t); }
iterator begin() const { return c.begin(); }
iterator end() const { return c.end(); }
};
int main() {
SortedList<int> example;
example.insert(1);
example.insert(5);
example.insert(9);
example.insert(2);
example.insert(-1);
std::for_each(example.begin(), example.end(), [](const int& element){ std::cout << element << ' ';});
}Priority stack
Szintén az STL-re támaszkodva egy std::map adatszerkezetben elhelyezett std::stackeket valósítunk meg, amely mindig a nagyobb prioritással beletett elemet veszi ki először, akkor is, ha azután az elem után már raktunk bele új elemet kisebb prioritással.
Például 5-ös prioritással belerakunk egy 1-est, majd 4-es prioritással egy 2-est, akkor az 1-est fogja visszaadni a top() tagfüggvény, illetve a pop() tagfüggvény is az 1-es veszi ki.
//priority stack example
#include <iostream>
#include <map>
#include <stack>
#include <functional>
template <class T, class Pr=int, class Comp=std::less<Pr>>
class priority_stack {
typedef std::map<Pr, std::stack<T>, Comp> prs;
prs ps;
public:
void push(const Pr& p, const T& t){
ps[p].push(t);
}
int size(const Pr& p) const {
return ps.find(p)->second.size();
}
const T& top() const { return ps.rbegin()->second.top(); }
T& top() { return ps.rbegin()->second.top(); }
int size() const {
int ret = 0;
for(typename prs::const_iterator i = ps.begin(); i != ps.end(); ++i) {
ret += i->second.size();
}
return ret;
}
void pop(){
const Pr p = ps.rbegin()->first;
ps.rbegin()->second.pop();
if (ps.rbegin()->second.empty()) {
ps.erase(p);
}
}
};
int main() {
priority_stack<int> prst_example;
prst_example.push(5,1);
prst_example.push(4,2);
prst_example.push(4,3);
std::cout << prst_example.top() << '\n';
prst_example.pop();
std::cout << prst_example.top() << '\n';
}Egyéb tananyagok
előző tananyagrész: öröklődés és polimorfizmus
következő tanayagrész: STL
