Programozás alapjai II. (7. ea) C++

Programozás alapjai II. (7. ea) C++ generikus szerkezetek, template Szeberényi Imre BME IIT

<[email protected]>

MŰEGYTEM 1782 C++ programozási nyelv

© BME-IIT Sz.I.

2011.03.29.

-1-

Hol tartunk? • C Æ C++ javítások • OBJEKTUM: konkrét adat és a rajta végezhető műveletek megtestesítője • OO paradigmák – egységbezárás (encapsulation), többarcúság (polymorphism) , példányosítás (instantiation), öröklés (inheritance), generikus szerkezetek

• • • •

OO dekompozíció, tervezés A C++ csupán eszköz Elveket próbálunk elsajátítani Újrafelhasználhatóság

C++ programozási nyelv

© BME-IIT Sz.I.

2011.03.29.

-2-

Hol tartunk? /2 • objektum megvalósítása – osztály (egységbe zár, és elszigetel), – konstruktor, destruktor, tagfüggvények – inicializáló lista (tartalmazott obj. inicializálása) – operátor átdefiniálás (függvény átdefiniálás) – barát és konstans tagfüggvények – dinamikus adat külön kezelést igényel – öröklés és annak megvalósítása – védelem enyhítése – virtuális függvények és osztályok – absztrakt osztályok C++ programozási nyelv

© BME-IIT Sz.I.

2011.03.29.

-3-

1

Mi az objektummodell haszna? • A valóságos viselkedést írjuk le • Æ Könnyebb az analógia megteremtése • Láttuk a példát (dig. áramkör modellezése) – Digitális jel: üzenet objektum – Áramköri elemek: objektumok – Objektumok a valós jelterjedésnek megfelelően egymáshoz kapcsolódnak. (üzennek egymásnak)

• Könnyen módosítható, újrafelhasználható • Funkcionális dekompozícióval is így lenne? C++ programozási nyelv

© BME-IIT Sz.I.

2011.03.29.

-4-

Lehet-e tovább általánosítani? • Általánosíthatók-e az adatszerkezetek? Már a komplexes első példán is észrevettük, hogy bizonyos adatszerkezetek (pl. tárolók) viselkedése független a tárolt adattól. Lehet pl. adatfüggetlen tömböt vagy listát csinálni? • Általánosíthatók-e az algoritmusok? Lehet pl. adatfüggetlen rendezést csinálni ?


© BME-IIT Sz.I.

2011.03.29.

-5-

elemzés: Tömb • Tároljunk T-ket egy tömbben! Műveletek: – Létrehozás/megszüntetés – Indexelés – Egyszerűség kedvéért nem másolható, nem értékadható és nem ellenőriz indexhatárt!


© BME-IIT Sz.I.

2011.03.29.

-6-

2

TArray megvalósítás class TArray { T *tp; // elemek tömbjére mutató pointer private, így nem elérhető int n; // tömb mérete TArray(const TArray&); // másoló konstr. tiltása TArray& operator=(const TArray&); // tiltás public: TArray(int n=5) :n(n) { tp = new T[n]; } T& operator[](int i); ~TArray() { delete[] tp; } }; T& TArray::operator[](int i) { return tp[i]; } C++ programozási nyelv

© BME-IIT Sz.I.

2011.03.29.

-7-

Mit kell változtatni? • Minden T-t át kell írni a kívánt (pl, int, double, Komplex stb.) típusra. • Neveket le kell cserélni (névelem csere) • Más különbség láthatóan nincs.

• (Meg kellene valósítani tisztességesen, hogy használható legyen, de most nem ez a lényeg)


© BME-IIT Sz.I.

2011.03.29.

-8-

Lehet-e általánosítani? Típusokat és neveket le kell cserélni --> Generikus adatszerkezetek: • Olyan osztályok, melyekben az adattagok és a tagfüggvények típusa fordítási időben szabadon paraméterezhető. • Megvalósítás: – preprocesszorral •

define + névkonkatenáció ##

– nyelvi elemként (template) C++ programozási nyelv

© BME-IIT Sz.I.

2011.03.29.

-9-

3

Preprocesszoral Típus és névelem csere makrókkal: • Névelem csere: – #define Array(T)

T##Array

• Osztály deklarációk: – #declare_Array(T) makro

konkatenáció

• Külső tagfüggvény definíciók: – #implement_Array(T) makro


© BME-IIT Sz.I.

2011.03.29.

- 10 -

Hogyan működik? névelem csere class TArray { T *tp; int n; public: TArray(int n=5) :n(n) { tp = new T[n]; } ...

declare_Array(int)


#define Array(T) T##Array #define declare_Array(T) class Array(T) { T *tp; int n; public: Array(T)(int n=5) :n(n) { tp = new T[n]; } ...

\ \ \ \ \ \ \

class intArray { int *tp; int n; public: intArray(int n=5) :n(n) { tp = new int[n]; } ... © BME-IIT Sz.I.

2011.03.29.

- 11 -

Array(T) #define Array(T)

T##Array

#define declare_Array(T) class Array(T) { T *tp; int n; Array(T)(const Array(T)&); Array(T)& operator=(const Array(T)&); public: Array(T)(int n=5) :n(n) { tp = new T[n]; } T& operator[](int i); ~Array(T)() { delete[] tp; } };

\ \ \ \ \ \ \ \ \ \

#define implement_Array(T) \ T& Array(T)::operator[](int i) { return tp[i]; } C++ programozási nyelv

© BME-IIT Sz.I.

2011.03.29.

- 12 -

4

Használata #include "gen_array_m.hpp" //declare+implement makr. class Valami { . . . }; // valamilyen osztály declare_Array(int) implement_Array(int) declare_Array(Valami) implement_Array(Valami)

// intArray deklarációja // intArray def. csak 1-szer ! // ValamiArray deklarációja // ValamiArray def. 1-szer !

Array(int) a1, a2, a3; Array(Valami) v1, v2, v3; a2[0] = 5; v2[1] = Valami; C++ programozási nyelv

© BME-IIT Sz.I.

2011.03.29.

- 13 -

Minden rendben ? • Tároljunk stringekre mutató pointereket: declare_Array(char *) implement_Array(char *)

• Mi lesz a makrókból? pl: #define Array(T) T##Array typedef-fel talán megoldható lenne

• Más, ennél a példánál nem jelentkező problémák is adódnak az egyszerű szöveghelyettesítésből, ezért jobb lenne nyelvi elemmel. • Megoldás: template


© BME-IIT Sz.I.

2011.03.29.

- 14 -

Megoldás: template – nyelvi elem formális sablonparaméter: tetszőleges típus

template // Sablon kezdete class Array { // Array osztály dekl. kezd. T *tp; int n; public: Array(int n=5) :n(n) { tp = new T[n]; } ... hatókör: a template kulcsszót }; követő deklaráció/definició vége

Array a1, a2, a3; Array v1, v2, v3; C++ programozási nyelv

© BME-IIT Sz.I.

aktuális sablonparaméter

2011.03.29.

- 15 -

5

Array osztály sablonja template // osztálysablon class Array { T *tp; // elemek tömbjére mutató pointer int n; // tömb mérete Array(const Array&); // másoló konstr. tiltása Array& operator=(const Array&); // tiltás public: Array(int n=5) :n(n) { tp = new T[n]; } T& operator[](int i); ~Array() { delete[] tp; } }; Névelem csere és a paraméterhelyettesítés nyelvi szinten történik. C++ programozási nyelv

© BME-IIT Sz.I.

2011.03.29.

- 16 -

Tagfüggvények sablonja sablonparaméter: tetszőleges típus

template // tagfüggvénysablon T& Array::operator[](int i) { return tp[i]; scope miatt fontos } hatókör: a template kulcsszót követő deklaráció/definició vége


© BME-IIT Sz.I.

2011.03.29.

- 17 -

Sablonok használata (példányosítás) #include "generic_array.hpp" // sablonok int main() {

sablon példányosítása aktuális template paraméterrel

Array ia(50), ia1(10); Array<double> da; Array ca;

// int array // double array // const char* array

ia[12] = 4; da[2] = 4.54; ca[2] = "Hello Template"; return 0; }


© BME-IIT Sz.I.

2011.03.29.

- 18 -

6

Array osztály másként template // osztálysablon class Array { T t[s]; // elemek tömbje int n; // tömb mérete public: T& operator[](int i) { if (i < 0 || i >= s) throw "Indexelési hiba"; return t[i]; } Többször példányosodik! Növeli a kódot, }; ugyanakkor egyszerűsödött az osztály. Array a10; Array a30; C++ programozási nyelv

© BME-IIT Sz.I.

2011.03.29.

- 19 -

Összetettebb példa: Láncolt lista • Tároljunk egész számokat egy rendezett listán. Műveletek: – Beszúr – új elem felvétele – Következő – soron következő elem kiolvasása • jelzi, ha elérte a végét és újra az elejére áll


© BME-IIT Sz.I.

2011.03.29.

- 20 -

2011.03.29.

- 21 -

Lista tervezése • Két osztály: – Lista • pointer az első elemre (első elem) • pointer az akt elemre • Művelet: beszur(), kovetkezo()

– ListaElem • adat • pointer önmagára • Művelet: másol, létrehoz


© BME-IIT Sz.I.

7

Kapcsolatok 1..*

Lista

ListaElem adat kov

elso akt

strázsa (őr/sentinel)


© BME-IIT Sz.I.

2011.03.29.

- 22 -

beszúrás másolással (ismétlés) Az 5 beszúrása

elso

p

3) p->adat = 5;

510 kov

2 kov

kov = 4) p->

23 kov

32 kov

2) *uj = *p;

???? KOV

uj

10 KOV 1) uj = new ListaElem

strázsa C++ programozási nyelv

© BME-IIT Sz.I.

NULL

2011.03.29.

- 23 -

C++ megvalósítás nem csak egy fv. lehet friend class ListaElem { friend class Lista; // hozzá kell férnie a tagokhoz int adat; // tárolt érték ListaElem *kov; // következő }; class Lista { ListaElem *elso, *akt; // első és az akt. pointer public: Lista() { akt = elso = new ListaElem; elso->kov = NULL; } void beszur(int dat); // beszúrás bool kovetkezo(int& dat);// következő elem kiolvasása ~Lista() { /* házi feladat */ } }; C++ programozási nyelv

© BME-IIT Sz.I.

2011.03.29.

- 24 -

8

C++ megvalósítás/2 kilép: p elé kellene beszúrni. void Lista::beszur(int dat) { ListaElem *p; // futó pointer for (p = elso; p->kov && p->adat < dat; p = p->kov); // hely keresése ListaElem *uj = new ListaElem(*p); // régi átm. az újba p->adat = dat; p->kov = uj; // láncolás } uj = new ListaElem bool Lista::kovetkezo(int& dat) { if (akt->kov == NULL) { // végére ért *uj = *p; akt = elso; return(false); } dat = akt->adat; akt = akt->kov; return(true); // megvan } C++ programozási nyelv

© BME-IIT Sz.I.

2011.03.29.

- 25 -

int helyett double? void DblLista::beszur(double dat) { DblListaElem *p; for (p = elso; p->kov && p->adat < dat; p = p->kov); // < operátor DblListaElem *uj = new DblListaElem(*p); p->adat = dat; p->kov = uj; // = operátor } bool DblLista::kovetkezo(double &dat) { if (akt->kov == NULL) { akt = elso; return(false); } dat = akt->adat; akt = akt->kov; // = operátor return(true); } C++ programozási nyelv

© BME-IIT Sz.I.

2011.03.29.

- 26 -

Mit kell változtatni? • Minden int-et át kell írni double-re. • Más különbség nincs. • Mennyiben változik, ha nem alaptípust akarunk tárolni? • Minden int-et át kell irni. • Biztosítani kell a megfelelő műveleteket az adott típusra (operatáror=, operátor<, másoló konstruktor?) • Van még más probléma? C++ programozási nyelv

© BME-IIT Sz.I.

2011.03.29.

- 27 -

9

Rejtett problémák Lista: • Másoló konstruktor (a default jó?) – NEM

• Értékadás operátor (a default jó?) – legalább tiltsuk meg a használatukat

ListaElem: • Másoló konstruktor (a default jo?) – IGEN (ha a pointerét nem szabadítjuk fel)

• Értékadás operátor (a default jó?) – nem jó, de nem használjuk C++ programozási nyelv

© BME-IIT Sz.I.

2011.03.29.

- 28 -

Kiegészítés class ListaElem { friend class Lista; // hozzá kell férnie a mezőkhöz int adat; // tárolt érték ListaElem *kov; // következő }; class Lista { ListaElem elso, *akt; // strázsa, és az akt olv. pointer Lista(const Listar&); // copy constr. tiltása Lista& operator=(const Lista&); // op= tiltása public: Lista() { akt = elso = new ListaElem; elso->kov = NULL; } ......


© BME-IIT Sz.I.

2011.03.29.

- 29 -

Általánosított lista template // Ez kell elé, hogy a friend-nél class Lista; // már ismert legyen a Lista sablonparaméter: tetszőleges típus

template class ListaElem { friend class Lista; T adat; ListaElem *kov; };

// Sablon kezdete // ListaElem osztály dekl. kezd. // hozzá kell férnie a mezőkhöz // adat // pointer következő elemre

itt nem fontos, mert az osztály nevét automatikusan cseréli C++ programozási nyelv

© BME-IIT Sz.I.

2011.03.29.

- 30 -

10

Lista osztály sablonja template // osztálysablon class Lista { // Lista ListaElem *elso, *akt; // első + akt pointer Lista (const Lista&); // másoló konstr. letiltva void operator=(const Lista&); // operáror= letiltva public: Lista() { akt = elso = new ListaElem; elso->kov = NULL;} // első + akt. bool hasonlit(T d1, T d2) { // default hasonlító fv. return(d1
© BME-IIT Sz.I.

2011.03.29.

- 31 -

Tagfüggvények sablonja template // tagfüggvénysablon void Lista::beszur(const T& dat) { ListaElem *p; // futó pointer for (p = elso; p->kov && // elem keresése hasonlit(p->adat, dat); p = p->kov); ListaElem *uj = new ListaElem(*p); //régit másol p->adat = dat; p->kov = uj; // adat beírása } template // tagfüggvénysablon bool Lista::kovetkezo(T& dat) { // következő elem if (akt->kov == NULL) { akt = elso; return(false); } dat = akt->adat; akt = akt->kov; return(true); } C++ programozási nyelv

© BME-IIT Sz.I.

2011.03.29.

- 32 -

Lista sablon használata #include "generic_lista.hpp" // sablonok int main() sablon példányosítása { Lista L; Lista<double> Ld; Lista Ls;

// int lista // double lista // char* lista

L.beszur(1); L.beszur(19); L.beszur(-41); Ls.beszur("Alma"); Ls.beszur("Hello"); Ls.beszur("Aladar"); int x; while (L.kovetkezo(x)) cout << x << '\n'; char *s; while (Ls.kovetkezo(s)) cout << s << '\n'; return 0; } C++ programozási nyelv

© BME-IIT Sz.I.

Jól fog működni ? bool Hasonlit(T d1, T d2) { return(d1
- 33 -

11

Probléma • A < operátor nem lesz jó a char* -ra, mert a pointereket hasonlítja, és nem a sztringeket. – Már korábban megállapítottuk, hogy nem tudjuk átdefiniálni, mert nem osztály.

• Valahogyan át kellene definiálni a sablonban definiált hasonlító függvényt – (csak a megfelelő char *-os példányt).

• Megoldás: specializáció


© BME-IIT Sz.I.

2011.03.29.

- 34 -

Specializáció • Függvények különböző változatait átdefiniálással érhetjük el. • Sablonok esetében ez a specializáció. Egy sablonnal megadott osztály, vagy függvény adott változatát átdefiniálhatjuk. Ilyenkor nem a sablonban megadott módon fog példányosodni. Pl: template<> bool Lista::hasonlit(char *s1, char *s2) { return(strcmp(s1, s2) < 0); } C++ programozási nyelv

© BME-IIT Sz.I.

2011.03.29.

- 35 -

Előző példa újból #include "generic_lista.hpp" // sablonok bool Lista::hasonlit(char *s1, char *s2) {// példány spec. return(strcmp(s1, s2) < 0); } Így már ábécé szerint rendez. int main() { Lista L; // int lista Lista<double> Ld; // double lista Lista Ls; // char* lista L.beszur(1); L.beszur(19); L.beszur(-41); Ls.beszur("Alma"); Ls.beszur("Hello"); Ls.beszur("Aladar"); int x; while (L.kovetkezo(x)) cout << x << endl; char *s; while (Ls.kovetkezo(s)) cout << s << endl; return 0; } C++ programozási nyelv

© BME-IIT Sz.I.

2011.03.29.

- 36 -

12

Mi is a sablon ? • Nyelvi elem az általánosításhoz. • Gyártási forma. • A sablonparaméterektől függően példányosodik: – osztály vagy függvény jön belőle létre.

• Paraméter: típus, konstans, függvény, sablon • Default paramétere is lehet. • A példányok specializálhatók, melyek eltérhetnek az eredeti sablontól. • A példányosítás helyének és a sablonnak egy fordítási egységben kell lennie. C++ programozási nyelv

© BME-IIT Sz.I.

2011.03.29.

- 37 -

Újabb példa template struct V { default T1 a1; T2 a2; int x; V() { x = i;} V v1; }; V<double, int> v2; V::V() { a1=a2=x=i; }

Vv3;

Specializálás


© BME-IIT Sz.I.

2011.03.29.

- 38 -

Függvénysablon • Függvények, algoritmusok általánosítási eszköze. • Hatékony, paraméterezhető, újrafelhasználható, általános. template void rendez (T a[], int n) { for (int i = 1; i < n; i++) { T tmp = a[i]; int j = i-1; while (j >= 0 && a[j] > tmp) { a[j+1] = a[j]; j--; } a[j+1] = tmp; } } ..... int t[] = = { 4, 8, -2, 88, 33, 1, 4, -1 }; rendez(t, 8); C++ programozási nyelv

© BME-IIT Sz.I.

2011.03.29.

- 39 -

13

Függvénysablonok paraméterei A sablonparaméterek általában levezethetők a függvényparaméterekből. Pl: template void csere(T& p1, T& p2) { T tmp = p1; p1 = p2; p2 = tmp; } int x1, x2; csere(x1, x2);

Ha nem, akkor meg kell adni. Pl: template void fv(T t1[n], T t2[n]) { for (int i = n; i >= 0; i--) t1[i] = t2[i]; } int it1[10], it2[10]; fv(it1, it2); C++ programozási nyelv

© BME-IIT Sz.I.

2011.03.29.

- 40 -

Algoritmus módosítása • Előfordulhat, hogy egy algoritmus (pl. rendezés) működösét módosítani akarjuk egy függvénnyel (predikátum). • Sablonparaméterként egy eljárásmódot (függvényt) is átadhatunk. • Példa: Írjunk egy általános kiválasztó algoritmust, ami képes kiválasztani a legkisebb, legnagyobb, leg... elemet.


© BME-IIT Sz.I.

2011.03.29.

- 41 -

Kiválasztó algoritmus sablonnal template T keres(T t[n]) { T tmp = t[0]; for (int i = 1; i < n; i++) if (S::select(t[i], tmp)) tmp = t[i]; return tmp; } template class Min { // szokásos min. kereséshez public: static int select(T a, T b) { return a < b; } }; template class Max { // szokásos max. keresésez public: static int select(T a, T b) { return a > b; } }; C++ programozási nyelv

© BME-IIT Sz.I.

2011.03.29.

- 42 -

14

Kiválasztó algoritmus használata class intMinAbs { // szokásostól eltérő kiválasztó függvény public: static int select(int a, int b) { return abs(a) < abs(b); } }; szóköz kell, int main() különben >>-nek értené! { int it[9] = {-5, -4, -3, -2, -1, 0, 1, 2, 3 }; double dt[5] = { .0, .1, .2, .3, 4.4 }; cout << keres<double, 5, Max<double> >(dt); // maximum cout << keres >(it); // mimimum cout << keres(it); // eltérő kiv. függvény return(0); } C++ programozási nyelv

© BME-IIT Sz.I.

2011.03.29.

- 43 -

Predikátumok • Célszerűen osztálysablonba építjük a megfelelő függvényt. Ekkor statikus függvényként kell deklarálni, mert másként nem jönne létre. • Természetesen külső függvény is lehet predikátum: templateT keres(T t[n]) { T tmp = t[0]; for (int i = 1; i < n; i++) if (select(t[i], tmp)) tmp = t[i]; return tmp; } template int MinFv(T a, T b) { return a < b; } keres(it); C++ programozási nyelv

© BME-IIT Sz.I.

2011.03.29.

- 44 -

Összefoglalás • A C-ben megtanult preprocesszor trükkökkel általánosíthatók az osztályok • Nem biztonságos, és nem ad mindenre megolást. • Æ Nyelvi elem bevezetése: template • A preprocesszoros trükköt csak a működés jobb megértéséhez néztük meg, ma már nem illik használni.


© BME-IIT Sz.I.

2011.03.29.

- 45 -

15

Összefoglalás /2 • Generikus osztályokkal tovább általánosíthatjuk az adatszerkezetekről alkotott képet: – Típust paraméterként adhatunk meg. – A generikus osztály később a típusnak megfelelően példányosítható. – A specializáció során a sablontól eltérő példány hozható létre – Specializáció lehet részleges, vagy teljes C++ programozási nyelv

© BME-IIT Sz.I.

2011.03.29.

- 46 -

Összefoglalás /3 • Generikus függvényekkel tovább általánosíthatjuk az algoritmusokról alkotott képet: – Típust paraméterként adhatunk meg. – A generikus függvény később a típusnak megfelelően példányosítható. – A függvényparaméterekből a konkrét sablonpéldány • levezethető, ha nem, akkor • explicit módon kell megadni

– Függvénysablon átdefiniálható C++ programozási nyelv

© BME-IIT Sz.I.

2011.03.29.

- 47 -

Összefoglalás /4 • Ún. predikátumok segítségével megváltoztatható egy algoritmus működése • Ez lehetővé teszi olyan generikus algoritmusok írását, mely specializációval testre szabható. • Ügyetlen template használat feleslegesen megnövelheti a kódot (pl. széles skálán változó paramétert is template paraméterként adunk át.) C++ programozási nyelv

© BME-IIT Sz.I.

2011.03.29.

- 48 -

16

Programozás alapjai II. (7. ea) C++

Recommend Documents