Clase si functii template in C++

Template-urile (sabloanele) permit crearea de clase sau functii generice, in care tipurile de date asupra carora se opereaza sunt specificate ca argumente. Un template defineste o familie de tipuri (clase) sau functii. s7c12cp
Forma generala de declarare a unui template este: template<lista_argumente> declaratie unde lista_argumente contine unul sau mai multe argumente formale, separate prin virgula, fiecare definit prin tipul argumentului si numele lui, iar declaratie trebuie sa declare sau sa defineasca o functie sau o clasa. Argumentele formale de tip predefinit din lista de argumente se introduc prin numele tipului urmat de numele argumentului, iar argumentele formale de tip definit de utilizator (clase) se introduc prin specificatorul class urmat de numele argumentului. De exemplu, o declaratie de template poate arata in felul urmator:

template<class X, class Y, int s> declaratie

7.1 Clase template

O clasa template specifica modul in care pot fi construite clase individuale, diferentiate prin tipul sau tipurile de date asupra carore se opereaza. O clasa template pentru definirea unei stive de obiecte de un tip oarecare T poate arata in felul urmator:

template<class T> class TStackA T *bot; T *top; int size; public: TStack(int s)A size = s; bot = top = new Tasi; S ITStack()Adelete ai bot;S void push(T t)A*top++ = t;S T pop()Areturn *--top;S
S;

Clasa template TStack contine ca date private doi pointeri: pointerul bot, pentru memorarea adresei de inceput a stivei si pointerul top, pentru memorarea capului stivei. Dimensiunea size a tabloului unidimensional (vector), creat dinamic la constructia unui obiect stiva, este necesara pentru testarea depasirii capacitatii stivei in functia push(), dar aceste teste nu au mai fost prezentate, pentru simplicitate.
Prefixul template<class T> specifica declararea unui template cu un argument cu numele T. Dupa aceasta intoducere, T este folosit exact la fel ca orice tip de date, in tot domeniul clasei template declarate.
Numele unei clase template urmat de numele tipurilor de date folosite ca argumente, incadrate de paranteze ascutite < > este numele unei clase (definite asa cum specifica template-ul) si poate fi folosita la fel ca oricare alta clasa. De exemplu, un obiect stiva de numere intregi istack poate fi declarat folosind clasa template TStack astfel:
TStack<int> istack(100); // stiva de numere intregi
Cu exceptia diferentei in sintaxa numelui, clasa TStack<int> se comporta exact la fel cum s-ar comporta daca ar fi fost definita astfel:

class IStackA int *bot; int *top; int size; public: IStack(int s)A size = s; bot = top = new intasi;
S
IIStack()Adelete ai bot;S void push(int t)A*top++ = t;S int pop()Areturn *--top;S
S;

Utilizarea template-urilor nu implica mecanisme run-time ci doar generarea de catre compilator a fiecarei clase care corespunde tipului (sau tipurilor) de date folosit la declararea unui obiect.

? Exemplul 7.1

Se considera implementarea unui program (programul Template) care contine descrierea clasei template TStack precum si a claselor Complex si String, care se pot prelua din sectiunile precedente. Fie functia:

void ft1()A
TStack<int> istack(100);
TStack<double> dstack(200); istack.push(2); istack.push(7); cout << istack.pop() <<' '; cout << istack.pop() << endl;

TStack<String> sstack(100); sstack.push('Primul sirn'); sstack.push('Al doilea sirn'); sstack.push('Al treilea sirn'); cout << sstack.pop(); cout << sstack.pop(); cout << sstack.pop();

TStack<Complex> cstack(100);
Complex z1(1.2, 3.4);
Complex z2(7.6, 5.4); cstack.push(z1); cstack.push(z2); cout << cstack.pop(); cout << cstack.pop();
S

Declararea variabilelor istack, dstack, cstack si sstack impune crearea claselor corespunzatoare tipurilor integer, double, Complex si, respectiv String. In fiecare stiva se introduc, se extrag si se afiseaza la consola date de tipul respectiv. Rezultatul executiei functiei ft1() este urmatorul:

7 5
Al treilea sir
Al doilea sir
Primul sir
(7.6, 3.4)(1.2, 3.4)
?

O observatie importanta in legatura cu operatiile definite intr-o clasa template este aceea ca o clasa care defineste un tip de date transmis ca argument al clasei template trebuie sa aiba prevazute functii de supraincarcare a operatorilor utilizati in clasa template.
De exemplu, in clasa template TStack<class T> se foloseste operatia de asignare in functia push(): *top++ = t, unde t este un obiect de tipul T. Daca in clasa T nu este supraincarcat operatorul de asignare, atunci compilatorul foloseste asignarea implicita, prin copiere membru-cu-membru a obiectelor (de clasa T). Pentru tipurile de date predefinite, ca si pentru clase care nu contin date alocate dinamic, acest lucru functioneaza corect. In schimb, daca o clasa T contine date alocate dinamic, atunci copierea membru-cu-membru produce erori de executie. Rezulta ca in clasele folosite ca argumente ale clasei template TStack trebuie sa se supraincarce operatorul de asignare. Un astfel de caz este clasa String care contine un sir de caractere care se aloca dinamic la crearea unui obiect si pentru care este absolut necesara supraincarcarea operatorului de asignare.
Functiile membre ale unei clase template nu trebuie sa fie obligatoriu definite inline. In clasa template TStack definita mai sus, se poate ca o functie sa fie doar declarata in interiorul clasei (de exemplu T pop(); ) si sa fie definita in afara clasei astfel:

template<class T> T TStack<T>::pop()A return *--top;
S

Domeniul functiei membre este specificat prin numele template-ului calificat cu numele parametrului, deci TStack<T>.
Pentru crearea claselor template, este o buna practica de a crea si depana o clasa particulara, de exemplu IStack, inainte de a o transforma in clasa generica TStack<T>.

7.2 Functii template

Toate functiile membre ale unei clase template sunt functii template, adica functii care definesc un set general de operatii care vor fi aplicate unor tipuri de date diferite. In afara de functiile template membre ale unei clase, se pot defini si functii template nemembru, care definesc familii de functii in acelasi mod in care clasele template definesc familii de clase.
Un astfel de exemplu este ilustrat printr-o functie template de sortare sort(), pentru care s-a folosit cel mai simplu algoritm, prin insertie lineara, deoarece in acest moment interesul este orientat catre tehnica de functie template si trasaturile limbajului, si mai putin catre agoritmul propriuzis.

template<class T> void sort(T* vect, int n)A int i,j;
T x; for(i=1; i<n; i++)A x = *(vect + i); j = i - 1;
while((j >= 0) && (x < *(vect + j)))A
*(vect + j + 1) = *(vect + j); j--;
S
*(vect + j + 1) = x;
S
S

Pentru fiecare apel, tipul argumentului determina functia de sortare care va fi folosita.

? Exemplul 7.2

Se introduce functia template sort() in programul Template si fie functia ft2()definita astfel:

void ft2()A double dvectai = A4.7, 0.66, 7.0, 1,8, 3.0S; int size = sizeof(dvect)/sizeof(double); sort(dvect, size); for (int i=0; i<size; i++) cout << dvectaii << ' '; int ivectai = A10, 9, 5, 3, -2, 4S; size = sizeof(ivect)/sizeof(int); sort(ivect, size); for (i=0; i<size; i++) cout << dvectaii << ' ';
S

Compilatorul creaza cate o functie de sortare pentru fiecare tip de data folosit ca argument de apel, deci se creaza o functie de sortare pentru vectori de numere intregi si, respectiv pentru vectori de numere de tip double. Dupa apelul functiei sort() datele sortate sunt afisate la consola. Rezultatul executiei acestei functii este urmatorul:

0.66 1.8 3.0 4.7 7.0
-2 3 4 5 9

7.3 Implementarea colectiilor de date folosind clase template

Cea mai simpla modalitate de a crea colectii sigure ca tip (type-safe) care sa contina obiecte de orice tip este prin utilizarea claselor template. Clasa sau clasele care descriu forma colectiei (vector, lista, etc.) se definesc ca si clase template, avand ca argument tipul de date din care se vor crea colectiile respective. La declararea unei colectii pentru un tip dat ca argument, compilatorul creaza colectia de forma data de clasa template si pentru tipul de date primit ca argument. Nu se folosesc conversii explicite de pointeri, astfel incat aceste clase de colectii sunt sigure ca tip.
In continuare va fi prezentat modul de implementare prin clase template a unui vector asociativ, impreuna cu o clasa care defineste un iterator al colectiei.

7.3.1 Implementarea unui vector asociativ

Un vector asociativ (associative array, dictionary, map) este o colectie de elemente, fiecare element fiind compus din doua parti: o parte numita cheie (key), care este utilizata pentru a accesa celalalta parte a elementului, numita valoare (value).
Un vector asociativ se poate implementa, desigur, in mai multe moduri, dintre care o solutie simpla si nu neaparat cea mai eficienta este prezentata in programul MapIter, printr-o lista dublu inlantuita in care elementele se mentin sortate in ordine crescatoare a cheii. Pastrarea elementelor ordonate in lista permite regasirea rapida a informatiilor.
Pentru definirea elementelor listei, a listei si a operatiilor de parcurgere a listei se folosesc trei clase template (MapNode, Map, MapIter), fiecare dintre ele avand doua argumente: tipul de date al cheii si tipul de date al valorii elementelor.
Un element (nod) al listei dublu inlantuite este definit prin clasa template MapNode, care are ca argumente doua tipuri generice, class K si class V, corespunzatoare tipului de date al cheii (key) si tipului de date al valorii (value). Dat fiind ca aceasta clasa descrie un element dintr-o lista dublu inlantuita, mai sunt necesari doi pointeri de inlantuire,left si right. Implementarea acestei clase este urmatoarea:

template <class K, class V> class MapNodeA friend class Map<K,V>; friend class MapIter<K,V>;
K key;
V value;
MapNode *left;
MapNode *right; public:
MapNode(const K& k, const V& v):key(k), value(v)A left = NULL; right = NULL;
S
IMapNode();
S;

Declararea celor doua clase friend Map si friend MapIter asigura crearea si manevrarea listei inlantuite de elemente.
Vectorul asociativ, reprezentat ca o lista dublu inlantuita de elemente de tip MapNode, este descris de clasa template Map, avand aceleasi argumente, tipurile de date class K si class V. Aceasta clasa defineste lista dublu inlantiuta printr-un pointer la primul element al listei (head) si numarul de elemente (noduri) ale listei (size). Implementarea clasei template Map este urmatoarea:

template<class K, class V> class MapA friend class MapNode<K,V>; friend class MapIter<K,V>;
MapNode<K,V>* head;
MapNode<K,V>* current;
V def_v;
K def_k; int size; void init()A size = 0; head = 0; current = 0;
S public:
Map() Ainit();S
Map(const K& k, const V& v)
:def_k(k),def_v(v) A init();
S
Map(const Map& r);
IMap(); void remove(const K& k);
Map& operator=(const Map& m);
V& operatorai (const K& k); int GetSize() const Areturn size;S

S;

Valorile implicite ale cheii (key) si ale valorii (value) sunt memorate in datele membre def_k si def_v. La crearea unui obiect din clasa Map, aceste valori implicite se transmit ca argumente ale constructorului. O data membra din clasa Map, pointerul current la un obiect de tipul MapNode, memoreaza pozitia curenta in lista inlantuita, adica ultima pozitie accesata prin functia operator de indexare.
Pentru inceput se pot ignora functiile membre care se refera la clasa MapIter, care vor fi explicate mai tarziu.
Operatia cea mai importanta a clasei Map este operatia de indexare, pentru care s-a implementat functia operatorai (). Vectorul asociativ trebuie sa se comporte ca un vector de date in care indexarea printr-un indice este inlocuita cu indexarea printr-o valoare a cheii. Ca urmare, supraincarcarea operatorului de indexare returneaza o referinta la valoarea (value) corespunzatoare cheii date, astfel incat valoarea dintr-un element (value) sa poata fi folosita atat in membrul drept al unei expresii (valoarea este citita), cat si in membrul stang al unei expresii (valoarea este scrisa). Implementarea functiei operator de indexare este urmatoarea:

template<class K, class V>
V& Map<K, V>::operatorai(const K& k)
A if(head == 0)A current = head = new MapNode<K, V>(k, def_v); current->left = current->right = 0; return current->value;
S
MapNode<K,V>* p = head; for (;;)A if(p->key == k) A // cheie gasita current = p; return current->value;
S if (k < p->key)A // inserare inainte de p current = new MapNode<K, V>(k, def_v); current->left = p->left; current->right = p; if (p == head) head = current; else p->left->right = current;

p->left = current; return current->value;
S
MapNode<K, V>* s = p->right; if(s == 0) A // inserare dupa p, la sfarsit current = new MapNode<K,V>(k, def_v); current->left = p; current->right = 0; p->right = current; return current->value;
S p = s;
S
S

Functia operatorai() se comporta in felul urmator: daca se gaseste un element a carui cheie este identica cu argumentul functiei operator ai () (considerat ca un indice generalizat), atunci se returneaza referinta la valoarea (value) corespunzatoare acestei chei. Daca, parcurgand lista inlantuita incepand cu primul element (head), la un moment dat, cheia argument este mai mica decat cheia elementului curent, se deduce ca nu exista un element cu aceasta cheie si atunci se creaza un element cu valoare (value) implicita, care se insereaza in lista ordonata. La fel, daca lista a fost parcursa in intregime si cheia de cautare este mai mare decat cheia ultimului element, se creaza un element nou cu valoare (value) implicita care se insereaza la sfarsitul listei. O tratare separata necesita cazul unei liste vide (head = 0). In aceasta situatie se creaza de asemenea un element nou, cu valoare (value) implicita care devine primul element al listei.

? Exemplul 7.3

Se implementeaza un program (programul MapIter) in care se defineste un vector asociativ generic folosind clasele MapNode si Map prezentate mai sus. In functia fm1() se creaza un vector asociativ smap ca un obiect din clasa template Map cu tipul de date intreg (int) si valoare implicita -;1 pentru argumentul key si tipul definit mai sus String, cu valoare implicita "Default" pentru argumentul value. Folosind operatorul de indexare se introduc elemente in vector, se extrag si se afiseaza la consola.

void fm1()A
Map<int, String> smap(-1,"Default"); smapa2i = "String 2"; smapa3i = "String 3"; cout << smapa3i; cout << smapa7i; cout << smapa2i;
S

La executia functiei fm1(), se obtin urmatoarele mesaje la consola:

String 3
Default
String 2
?

De cele mai multe ori, pentru parcurgerea intr-o ordine dorita a elementelor unei colectii de obiecte, asa cum este un vector asociativ, se foloseste un mecanism numit iterator. Un iterator permite parcurgerea in ordinea dorita a elementelor, fara ca aceasta ordine sa depinda de modul de ordonare interna a elementelor colectiei.
Pentru implementarea unui iterator al vectorului asociativ descris de clasele Map si MapNode se foloseste o alta clasa template, MapIter, ale carei functii membre vor fi functii de parcurgere in ordinea dorita a vectorului asociativ. De exemplu, se pot implementa functii de parcurgere in ordine crescatoare, respectiv descrescatoare a cheilor elementelor. Aceasta clasa template este definita astfel:

template <class K, class V> class MapIter
A friend class Map<K,V>;
Map<K, V>* map;
MapNode<K,V>* node; public:
MapIter()Amap = 0; node = 0;S
MapIter(Map<K,V>* pmap, MapNode<K,V>* pnode)A map = pmap; node = pnode;
S
MapIter(Map<K,V>& mm)A map = &mm; node = map->head;
S operator void*() Areturn node;S const K& key()A if (node) return node->key; else return map->def_k;
S
V& value()A if (node) return node->value; else return map->def_v;
S;
MapIter& operator--(); // decrement prefix void operator--(int); // decrement postfix
MapIter& operator++(); // increment prefix void operator++(int); // increment postfix
S; template <class K, class V>
MapIter<K,V>& MapIter<K,V>::operator--()A if(node) node = node->left; return *this;
S template <class K, class V> void MapIter<K,V>::operator--(int)A if(node) node = node->left;
S template <class K, class V>
MapIter<K,V>& MapIter<K,V>::operator++()A if (node) node = node->right; return *this;
S template <class K, class V> void MapIter<K,V>::operator++(int)A if(node) node = node->right;
S

Clasa MapIter se defineste pentru parcurgerea unei liste inlantuite de tipul Map compusa din noduri de tipul MapNode si de aceea contine doi pointeri map si node la aceste tipuri de obiecte. Un obiect din clasa MapIter se poate construi implicit, cu pointerii map si node setati la valoarea 0, sau printr-unul din cei doi constructori de initializare, care seteaza corespunzator cei doi pointeri, in functie de argumentele primite. Pointerul node indica elementul curent din lista.
Functiile de parcurgere a vectorului pot fi implementate prin supraincarcarea operatorilor de incrementare si decrementare, asa cum este prezentat mai sus. Functia operator+ ) permite parcurgerea elementelor in ordine crescatoare a cheilor, iar functia operator--() permite parcurgerea elementelor in ordine descrescatoare a cheilor. Aceste functii sunt analoge operatiilor de incrementare-decrementare a pointerilor si ele modifica valoarea pointerului node astfel incat lista sa fie parcursa in sensul dorit: spre stanga (la decrementare) sau spre dreapta (la incrementare).
Functiile membre key() si value() ale clasei MapIter returneaza cheia, respectiv valoarea elementului curent din lista, indicat de pointerul node.

? Exemplul 7.4

Un vector asociativ (obiect din clasa Map) poate fi parcurs iterativ folosind un obiect din clasa MapIter (numit si iterator), care acceseaza succesiv elementele listei inlantuite. In programul MapIter se adauga functia fm2() in care este creat un vector asociativ cu numele table, cu cheie de tip String si valoare de tip intreg. Cheia si valoarea elementelor listei se afiseaza la consola la parcurgerea iterativa a listei folosind iteratorul iter. Prin apelul operatorului supraincarcat de incrementare al clasei MapIter, elementele listei sunt parcurse in ordine crescatoare a cheii.

void fm2()A
Map<String,int> table('nil', 0);

tablea'word1'i = 5; tablea'word3'i = 2; tablea'word3'i +=4; tablea'word2'i = 8;

MapIter<String,int> iter(table); for (; iter; ++iter) cout << iter.key() << iter.value() << endl;
S

La executia acestei functii sunt afisate la consola urmatoarele mesaje:

word1 5
word2 8
word3 6

In operatia de testare a limitei buclei for se subintelege testul (iter != 0) pentru efectuarea caruia are loc o operatie de conversie de la tipul MapIter la pointer la void folosind functia operator de conversie operator void*()a clasei MapIter. Acesta functie returneaza zero daca iteratorul nu se refera la nici un element, iar altfel o valoare diferita de zero.
?

Pentru acelasi vector asociativ (obiect din clasa Map) se pot crea mai multe obiecte iterator (din clasa MapIter), fiecare dintre ele parcurgand lista intr-un mod diferit, in functie de necesitatile programului. Fiecare iterator memoreaza un anumit nod curent din lista (in variabila node), in timp ce in lista insasi, nodul curent (variabila current) memoreaza ultimul nod accesat de oricare dintre iteratorii care o parcurg. In utilizarea din functia fm2(), tipul argumentului cheie este clasa String. Dat fiind ca in functia operator ai() a clasei Map se executa operatii de comparatie asupra cheii, este necesar ca in clasa String sa fie supraincarcati acesti operatori si acest lucru apare in implementarea clasei String.

? Exemplul 7.5

Se modifica functia fm2() astfel incat vectorul asociativ table sa fie inspectat simultan prin intermediul a doi iteratori, iter1 si iter2, din care iteratorul iter1 parcurge lista din element in element in ordinea crescatoare a cheii, iar iteratorul iter2 parcurge lista din doua in doua elemente in ordinea crescatoare a cheii.

void fm3()A
Map<String,int> table('nil', 0);
//readlines(table);

tablea'word1'i = 5; tablea'word3'i = 2; tablea'word3'i +=4; tablea'word2'i = 8; tablea'word4'i = 9; tablea'word5'i = 7;

MapIter<String,int> iter1(table);
MapIter<String,int> iter2(table);

for (; iter2; iter1++, iter2+=2) A cout << iter1.key() << iter2.value() << endl; cout << iter2.key() << iter2.value() << endl;
S
S

La executia functiei fm3() se afiseaza la consola urmatoarele mesaje:

word1 5
word1 5
word2 8
word3 6
word3 6
word5 7

Pentru parcurgerea din doua in doua elemente a listei inlantuite, in ordinea crescatoare a cheii, trebuie sa fie supraincarcata functia operator+ ) a clasei MapIter astfel:

template <class K, class V>
MapIter<K,V>& MapIter<K,V>::operator+=(int inc)A for (int i=0;i<inc;i++)A if (node) node = node->right; else break;
S return *this;
S

De asemenea, aceasta functie operator trebuie sa fie declarata in corpul clasei MapIter.