PROGRAMAREA STRUCTURILOR DE DATE IN C++

PROGRAMAREA STRUCTURILOR DE DATE IN c++

Avantajele limbajului C++

Un limbaj cu clase permite un nivel de generalizare si de abstractizare care nu poate fi atins intr-un limbaj fara clase. In cazul structurilor de date generalizare inseamna genericitate, adica posibilitatea de a avea ca elemente componente ale structurilor de date (colectiilor) date de orice tip, inclusiv alte structuri de date.

Clasele abstracte permit implementarea conceptului de tip abstract de date, iar derivarea permite evidentierea legaturilor dintre diferite structuri de date. Astfel, un arbore binar de cautare devine o clasa derivata din clasa arbore binar, cu care foloseste in comun o serie de metode (operatii care nu depind de ordinea valorilor din noduri, cum ar fi afisarea arborelui), dar fata de care poseda metode proprii (operatii specifice, cum ar fi adaugarea de noi noduri sau cautarea unei valori date).

Din punct de vedere pragmatic, metodele C++ au mai putine argumente decat functiile C pentru aceleasi operatii, iar aceste argumente nu sunt de obicei modificate in functii. Totusi, principalul avantaj al unui limbaj cu clase este posibilitatea utilizarii

unor biblioteci de clase pentru colectii generice, ceea ce simplifica programarea anumitor aplicatii si inlocuirea unei implementari cu o alta implementare pentru acelasi tip abstract de date.

Structurile de date se preteaza foarte bine la definirea de clase, deoarece reunesc variabile de diverse tipuri si operatii (functii) asupra acestor variabile (structuri). Nu este intamplator ca singura biblioteca de clase acceptata de standardul C++ contine practic numai clase pentru structuri de date ( STL = Standard Template Library).

Programul urmator creeaza si afiseaza un dictionar ordonat pentru problema frecventei cuvintelor, folosind clasele "map", "iterator" si "string" din biblioteca STL

#include <iostream> // definitii clase de intrare-iesire

#include <string> // definitia clasei "string"

#include <map> // definitia clasei "map"

#include <iterator> // definitia classei "iterator"

using namespace std; // spatiu de nume ptr clasele standard

int main ()

Programul anterior este compact, usor de citit (dupa o familiarizare cu clasele STL) si eficient, pentru ca dictionarul este implementat ca un arbore binar cu autoechilibrare, de inaltime minima.

Faptul ca se folosesc aceleasi clase standard in toate programele C++ asigura acestora un aspect uniform, ceea ce faciliteaza si mai mult intelegerea lor rapida si modificarea lor fara introducere de erori. Programele C sunt mult mai diverse datorita multiplelor posibilitati de codificare si de asigurare a genericitatii, precum si absentei unor biblioteci standard de functii pentru operatii cu structuri de date uzuale.

Pe de alta parte, biblioteca STL (ca si biblioteca de clase colectie Java ) nu contine toate structurile de date, ci numai pe cele mai importante. De aceea, programatorii trebuie sa poata defini noi clase sablon in care sa foloseasca facilitatile oferite de STL

Clasele STL sunt definite independent unele de altele, fara a pune in evidenta relatiile existente intre ele. Tehnici specifice programarii orientate pe obiecte, cum sunt derivarea si mostenirea nu sunt folosite in definirea acestor clase. In schimb, apar functii polimorfice, cu aceeasi forma dar cu implementare diferita in clase diferite (metode comune claselor container STL).

Clase pentru structuri de date generice se pot realiza in C++ (si in Java) si altfel decat prin clase sablon ("template"), solutie folosita in multe carti de structuri de date care folosesc limbajul C++ pentru ca permite definirea unor familii de clase inrudite, folosind derivarea si mostenirea. Exista si biblioteci de clase pentru structuri de date bazate pe aceasta solutie (CLASSLIB din Borland C 3.1), dar nici una care sa se bucure de o recunoastere atat de larga ca biblioteca STL.

Aceasta solutie de definire a unor clase C++ pentru colectii generice seamana cu utilizarea de pointeri generici (void*) in limbajul C.

Ideea este ca toate clasele colectie sa contina ca elemente pointeri la obiecte de un tip abstract, foarte general ("object"), iar clasele care genereaza obiecte membre in astfel de colectii sa fie derivate din clasa "object". Deci toate clasele folosite in astfel de aplicatii ar trebui sa fie derivate direct sau indirect dintr-o clasa de baza "object", aflata la radacina arborelui de clase.

Un pointer la tipul "object" poate fi inlocuit cu un pointer catre orice alt subtip al tipului "object", deci cu un pointer la o clasa derivata din "object" (derivarea creeaza subtipuri ale tipului de baza). Pentru a memora date de un tip primitiv (numere, de exemplu) intr-o astfel de colectie, va trebui sa dispunem (sau sa definim) clase cu astfel de date si care sunt derivate din clasa "object".

In containerele STL se pot introduce atat valori cat si pointeri, ceea ce permite in final si containere cu obiecte de diferite tipuri inrudite (derivate unele din altele).

Clase si obiecte in C++

Clasele C++ reprezinta o extindere a tipurilor structura, prin includerea de functii ca membri ai clase, alaturi de variabilele membre ale clasei. Functiile, numite si metode ale clasei, realizeaza operatii asupra datelor clasei, utile in aplicatii.

O clasa ce corespunde unei structuri de date grupeaza impreuna variabilele ce definesc colectia si operatiile asociate, specifice fiecarui tip de colectie. De exemplu, o clasa "Stiva" poate avea ca date un vector si un intreg (indice spre varful stivei), iar ca metode functii pentru punerea unei valori pe stiva ("push"), scoaterea valorii din varful stivei ("pop") si altele.

De obicei datele unei clase nu sunt direct accesibile pentru functii din afara clasei avand atributul "private" (implicit), ele fiind accesibile numai prin intermediul metodelor publice ale clasei. Aceste metode formeaza "interfata" clasei cu exteriorul. Exemplu de definire a unei clase pentru stive vector de numere intregi:

class Stiva // un constructor pentru obiectele clasei

void push ( int x ) // pune x in aceasta stiva

int pop () // scoate valoarea din varful stivei

int empty() // daca stiva este goala

}; // aici se termina definitia clasei

Orice clasa are unul sau mai multi constructori pentru obiectele clasei, sub forma unor functii fara nici un tip si cu numele clasei. Constructorul aloca memorie (daca sunt date alocate dinamic in clasa) si initializeaza variabilele clasei. Exemplu de clasa pentru o stiva cu vector alocat dinamic si cu doi constructori:

class Stiva

Stiva ()

. . . // metodele clasei

};

O functie constructor este apelata automat in doua situatii:

- La declararea unei variabile de un tip clasa, insotita de paranteze cu argumente pentru functia constructor. Exemplu:

Stiva a(20); // a este o stiva cu maxim 20 de elemente

- La alocarea de memorie pentru un obiect cu operatorul new (dar nu si cu functia "alloc"), care poate fi urmat de paranteze si de argumente pentru constrcutor. Exemple:

Stiva * ps = new Stiva(20);

Stiva a = * new Stiva(20);

Ambele moduri de initializare sunt posibile in C++ si pentru variabile de un tip primitiv (tipuri ale limbajului C). Exemple:

int x = *new int(7);

int x(7); // echivalent cu int x=7

In C++ functiile pot avea si argumente cu valori implicite (ultimele argumente); daca la apel lipseste argumentul efectiv corespunzator, atunci se foloseste implicit valoarea declarata cu argumentul formal corespunzator. Aceasta practica se foloseste si pentru constructori (si pentru metode). Exemplu:

class Stiva

. . .

};

O clasa este un tip de date, iar numele clasei poate fi folosit pentru a declara variabile, pointeri si functii cu rezultat de tip clasa (la fel ca si la tipuri structuri). O variabila de un tip clasa se numeste si obiect. Sintaxa apelarii metodelor unei clase C++ difera de sintaxa apelarii functiilor C si exprima actiuni de forma "apeleaza metoda push pentru obiectul stiva cu numele a". Exemplu de utilizare:

#include "stiva.h"

void main ()

Un alt exemplu este clasa urmatoare, pentru un graf reprezentat printr-o matrice de adiacente, cu cateva operatii strict necesare in aplicatiile cu grafuri:

class graf

}

int size() // dimensiune graf (numar de noduri)

int arc (int v, int w)

void addarc (int v, int w)

void print()

}

};

// utilizarea unui obiect de tip "graf"

int main ()

Alte operatii cu grafuri pot fi incluse ca metode in clasa "graf", sau pot fi metode ale unei clase derivate din "graf" sau pot fi functii separate, cu un argument "graf". Exemplu de functie independenta pentru vizitarea unui graf in adancime si crearea unui vector de noduri, in ordinea DFS:

void dfs (graf g, int v, int t[])

Definirea metodelor unei clase se poate face si in afara clasei, dar ele trebuie declarate la definirea clasei. De fapt, anumite metode (care contin cicluri, de ex.) chiar trebuie definite in afara clasei pentru a nu primi mesaje de la compilator. In general definitia clasei este introdusa intr-un fisier antet (de tip H), iar definitiile metodelor sunt continute in fisiere de tip CPP sau sunt deja compilate si introduse in biblioteci statice sau dinamice (LIB sau DLL in sisteme MS-Windows).

Exemplu de clasa pentru obiecte folosite in extragerea cuvintelor dintr-un sir, ca o solutie mai buna decat functia standard "strtok":

// fisier tokenizer.h

#include <string.h>

#include 'stldef.h'

class tokenizer

char* next(); // urmatorul cuvant din sirul analizat

bool hasNext () ; // verifica daca mai exista cuvinte

};

// fisier tokenizer.cpp

// daca mai sunt cuvinte in sirul analizat

bool tokenizer::hasNext()

// urmatorul cuvant

char* tokenizer::next()

Numele bibliotecii de clase sau numele fisierului OBJ cu metodele clasei trebuie sa apara in acelasi proiect cu numele fisierelor din aplicatia care le foloseste; exceptie face biblioteca standard STL, in care editorul de legaturi cauta implicit.

Exemplu de utilizare a clasei "tokenizer" :

#include <stdio.h>

void main ()

Clasa "tokenizer" este utila in aplicatii, dar suporta si alte variante de definire:

- In locul tipului "char*" sau pe langa acest tip se poate folosi si tipul "string" definit in biblioteca STL si recomandat pentru sirurile introduse in containere STL.

- In locul unui constructor cu argument sirul analizat se poate defini un constructor fara argumente si o metoda care sa preia sirul analizat; in felul acesta nu am mai fi obligati sa declaram variabila de tip "tokenizer" dupa citirea liniei analizate. Aceeasi situatie apare si la clasa "vector" din STL, pentru care capacitatea vectorului se poate specifica in constructor sau se transmite prin metoda "reserve".

Specifica limbajului C++ este supradefinirea operatorilor, care permite extinderea utilizarii limbajului C si pentru operatii asupra obiectelor unei clase (in loc de a folosi functii pentru aceste operatii). Astfel, operatorul ">>" aplicat obiectului predefinit "cin" are efectul unei citiri din fisierul standard de intrare ("console input"), iar operatorul "<<" aplicat obiectului "cout" are efectul unei scrieri in fisierul standard de iesire ("console output").

Un operator supradefinit in C++ este tot o functie dar cu un nume mai special, format din cuvantul cheie operator si unul sau doua caractere speciale, folosite in limbajul C ca operator (unar sau binar). Un operator poate fi definit in cateva moduri:

- ca metoda a unei clase (operator declarat in cadrul clasei);

- ca functie externa clasei (daca datele clasei sunt publice sau public accesibile);

- ca functie externa declarata "prieten" ("friend") in clasa, pentru ca functia externa sa aiba acces la datele "private" ale clasei.

Exemplu de supradefinire a operatorului de incrementare prefixat printr-o metoda:

class counter // constructor fara argumente

void operator++ () // metoda cu numele "operator++"

int val() // obtine valoare contor

};

// utilizare

void main ()

Exemplu de supradefinire a operatorului << ca functie prieten a clasei "counter":

class counter

void operator++ ()

int& val()

friend ostream & operator << (ostream & os, counter & c);

};

ostream & operator << (ostream & os, counter & c)

Exemplu de supradefinire a operatorului << ca functie externa clasei si care nu trebuie declarata in clasa:

ostream & operator << (ostream & os, counter & c)

Exemplu de supradefinire a operatorului de indexare intr-o clasa vector:

class Vector

int get (int i) // functie de acces la elemente

int& operator [ ] (int i) // operator de indexare []

void add (int x) // adaugare la sfarsit de vector

};

Elementul din pozitia k a unui obiect "Vector" poate fi obtinut fie prin metoda "get", fie cu operatorul de indexare, dar operatorul permite si modificarea valorii din pozitia k deoarece are rezultat referinta . Exemplu:

void main ()

Clasele ale caror obiecte se introduc in containere STL trebuie sa aiba definiti operatorii de comparatie si de afisare, folositi in cadrul claselor container. Exemplu:

// clasa ptr arce de graf

class arc

};

bool operator== (const arc &x,const arc &y)

bool operator< (const arc &x,const arc &y)

bool operator> (const arc &x,const arc &y)

ostream& operator<< (ostream &s, arc a)

istream& operator >> (istream &s, arc & a)

O clasa A poate contine ca membri obiecte, deci variabile de un tip clasa B. In acest fel metodele clasei A pot (re)folosi metode ale clasei B. De exemplu, o clasa stiva poate contine un obiect de tip vector si refoloseste metode ale clasei vector, cum ar fi extinderea automata a capacitatii la umplerea vectorului.

Problema cu aceste clase agregat (compuse) este ca anumite date primite de constructorul clasei agregat A trebuie transmise constructorului obiectului continut, care le foloseste la initializarea unor variabile ale clasei B. De exemplu, capacitatea initiala a vectorului este primita de constructorul obiectelor stiva, pentru ca este si capacitatea initiala a stivei. Un constructor nu poate fi apelat ca o metoda (ca o functie) obisnuita. Din acest motiv s-a introdus o sintaxa speciala pentru transmiterea datelor de la un constructor A la un constructor B al obiectului b :

A ( tip x): b(x)

Exemplu:

class Stiva // un constructor pentru obiectele clasei

// alte metode ale clasei Stiva

Aceasta sintaxa este extinsa si pentru variabile ale clasei A care nu sunt obiecte (variabile de tipuri primitive). Exemplu de constructor pentru clasa anterioara:

Stiva(int n): s(n),sp(0) // echivalent cu sp=0

O noutate a limbajului C++ fata de limbajul C o constituie si spatiile de nume pentru functii (si clase), in sensul ca pot exista functii (si clase) cu nume diferite in spatii de nume diferite. Toate clasele si functiile STL sunt definite in spatiul de nume "std", care trebuie specificat la inceputul programelor ce folosesc biblioteca STL:

using namespace std;

Am mentionat aici acele aspecte ale definirii de clase C++ care sunt folosite si in clasele STL, pentru a facilita intelegerea exemplelor cu clase STL.

In realitate, definitiile de clase sunt mult mai complexe decat exemplele anterioare si folosesc facilitati ale limbajului C++ care nu au fost prezentate.

Clase sablon ("template")

In C++ se pot defini functii si clase sablon avand ca parametri tipurile de date folosite in functia sau in clasa respectiva.

Exemplu de functie sablon pentru determinarea valorii minime dintre doua variabile de orice tip T, tip neprecizat la definirea functiei:

// definire functie sablon cu un parametru 'class'

template <class T> T min (T a, T b)

Cuvantul 'class' arata ca T este un parametru ce desemneaza un tip de date si nu o valoare, dar nu este obligatoriu ca functia 'min' sa foloseasca un parametru efectiv de un tip clasa. In functia "min" tipul care va inlocui tipul neprecizat T trebuie sa cunoasca operatorul '<' cu rol de comparatie la mai mic. Exemplul urmator arata cum se poate folosi functia sablon 'min' cu cateva tipuri de date primitive:

// utilizari ale functiei sablon

void main ()

O clasa sablon este o clasa in a carei definire se folosesc tipuri de date neprecizate pentru variabile si/sau pentru functii membre ale clasei. Toate tipurile neprecizate trebuie declarate intr-un preambul al definitiei clasei, care incepe prin cuvantul cheie 'template' si este urmat, intre paranteze ascutite, de o lista de nume de tipuri precedate fiecare de cuvantul 'class'. Exemplu:

// o clasa stiva cu componente de orice tip T

template <class T> class Stiva

void push (T x)

T pop ()

int empty()

void print (); // definita in afara clasei

};

La declararea unei variabile de tip clasa sablon trebuie precizat numele tipului efectiv utilizat, intre paranteze ascutite, dupa numele clasei. Exemplu:

// utilizare clasa sablon

void main ()

Pentru metodele definite in afara clasei trebuie folosit cuvantul 'template'. Exemplu:

template <class T> void Stiva<T> :: print ()

Pe baza definitiei clasei sablon si a tipului parametrilor efectivi de la instantierea clasei, compilatorul inlocuieste tipul T prin tipul parametrilor efectivi. Pentru fiecare tip de parametru efectiv se genereaza o alta clasa , asa cum se face expandarea unei macroinstructiuni (definita prin 'define'). Definitia clasei este folosita de compilator ca un 'sablon' (tipar, model) pentru a genera definitii de clase 'normale'.

Intre parantezele unghiulare pot fi mai multe tipuri, daca in clasa se folosesc doua sau mai multe tipuri neprecizate. Exemplu:

#include 'stldef.h'

// dictionar cu chei unice din 2 vectori

template <class KT, class VT> class mmap

public:

mmap (int m=100)

void put (KT k, VT v)

}

VT get (KT k)

void print ()

bool hasKey (KT k)

};

// utilizare dictionar ptr frecventa cuvintelor

int main ()

else

dic.put (cuv,1);

dic.print();

}

Pentru cuvinte am folosit tipul "string" (clasa STL) si nu "char*" pentru ca are (supra)definiti operatorii de comparatie, utilizati la cautarea unei chei in dictionar. In general, clasele ale caror obiecte se introduc in containere STL trebuie sa aiba definiti acesti operatori (==, !=, <, >, <=, >=), pentru ca sa putem exprima la fel comparatiile, indiferent de tipul datelor care se compara.

O alta problema, rezolvata prin exceptii, este "ce rezultat ar trebui sa aiba metoda get atunci cand cheia data nu se afla in dictionar", deoarece nu stim nimic despre tipul VT al functiei "get" si deci ce valori speciale de acest tip am putea folosi.

Exemplul urmator schiteaza o definitie a clasei "stack" din STL, clasa care poate contine orice tip de container secvential STL:

template <class E, class Container > class mstack // daca stiva goala

int size () // dimensiune stiva

E top () // valoare din varful stivei

void push ( E & x) // pune x pe stiva

void pop () // elimina valoare din varful stivei

};

// utilizare clasa mstack

int main ()

while ( !a.empty())

}

Clasa "mstack" refoloseste metodele clasei container (back, push_back, pop_back, size, s.a.) altfel decat prin mostenire, deoarece "mstack" nu este subclasa derivata din clasa container. De aceea si operatorii de comparatie trebuie definiti in clasa mstack, chiar daca definirea lor se reduce la compararea obiectelor container continute de obiectele stiva.

Clasa mstack se numeste si clasa adaptor deoarece nu face decat sa modifice interfata clasei container (alte nume pentru metodele din container), fara a modifica si comportamentul clasei (nu exista metode noi sau modificate ca efect).

Clase container din biblioteca STL

Biblioteca de clase STL contine in principal clase "container" generice pentru principalele structuri de date, dar si alte clase si functii sablon utile in aplicatii:

- Clase iterator pentru clasele container si pentru clase de I/E

- Clase adaptor, pentru modificarea interfetei unor clase container

- Functii sablon pentru algoritmi generici (nu fac parte din clase)

Clasele container se impart in doua grupe:

- Secvente liniare: clasele vector, list, deque

- Containere asociative: set, multiset,multimap

Fiecare clasa STL este definita intr-un fisier antet separat, dar fara extensia H. Exemplu de utilizare a clasei string din biblioteca STL:

#include <string>

#include <iostream>

using namespace std;

void main ()

Trecerea de la siruri C la obiecte string se face prin constructorul clasei, iar trecerea de la tipul string la siruri C se face prin metoda c_str() cu rezultat "char*"

Pentru simplificare vom considera ca avem definit un alt fisier "defstl.h" care include toate fisierele antet pentru clasele STL si declaratia "using namespace std".

Toate clasele container au cateva metode comune, dintre care mentionam:

int size(); // numar de elemente din container

bool empty(); // daca container gol (fara elemente in el)

void clear(); // golire container (eliminarea tuturor elementelor)

iterator begin(); // pozitia primului element din container

iterator end(); // pozitia urmatoare ultimului element din container

Operatorii == si < pot fi folositi pentru compararea a doua obiecte container de acelasi tip.

Containerele secventiale se folosesc pentru memorarea temporara a unor date; ele nu sunt ordonate automat la adaugarea de noi elemente, dar pot fi ordonate cu functia STL "sort". Metode mai importante comune tuturor secventelor:

void push_bak() (T & x); // adaugare x la sfarsitul secventei

void pop_back(); // eliminare element de la sfarsitul secventei

T& front(); // valoarea primului element din secventa

T& back(); // valoarea ultimului element din secventa

void erase (iterator p); // eliminare element din pozitia p

void insert (iterator p, T& x); // insertie x in pozitia p

Clasa vector corespunde unui vector extensibil, clasa list corespunde unei liste dublu inlantuite. Toate clasele secventa permit adaugarea de elemente la sfarsitul secventei (metoda "push_back") intr-un timp constant (care nu depinde de marimea secventei). Exemplu de folosire a clasei vector:

int main ()

// afisare vector

for (int i=0;i<vs.size();i++) // "size" este metoda a clasei "vector"

cout << vs[i] << ',' ; // operatorul [ ] supradefinit in clasa "vector"

cout << endl; // cout << "n"

Clasele vector si deque au redefinit operatorul de indexare [] pentru acces la elementul dintr-o pozitie data a unei secvente.

Clasele list si deque permit si adaugarea de elemente la inceputul secventei in timp O(1) (metoda "push_front"). Exemplu de utilizare a clasei list ca o stiva:

int main ()

Clasele adaptor stack, queue si priority_queue (coada cu prioritati) sunt construite pe baza claselor secventa de baza, fiind liste particulare. Clasa stack, de exemplu, adauga metodele "push" si "pop" unei secvente (implicit se foloseste un container de tip deque, dar se poate specifica explicit un container list sau vector). Exemplu de utilizare a unei stive:

int main ()

Metodele "pop", "pop_back", "pop_front" sunt de tip void si se folosesc de obicei impreuna (dupa) metodele "top","back", "front", din motive legate de limbajul C++.

Orice container de tip "cont" poate avea mai multe obiecte iterator asociate de tipul cont::iterator si folosite la fel ca variabilele pointer pentru a parcurge elementele colectiei.Exemplu:

// afisare vector, cu iterator

vector<string>::iterator it; // declarare obiect iterator ptr vector de siruri

for (it=vs.begin(); it!=vs.end();it++) // "begin", "end" metode ale clasei vector

cout << *it << ' ,' ; // afisare obiect de la adresa continuta in it

cout << endl;

Un iterator STL este o generalizare a notiunii de pointer si permite accesul secvential la elementele unui container, in acelasi fel, indiferent de structura de date folosita de container. Pentru clasele iterator sunt supradefiniti operatorii de indirectare (*), comparatie la egalitate (++) si inegalitate(!=), incrementare (++), dar operatorul de decrementare (--) exista numai pentru iteratori bidirectionali.

Prin indirectare se obtine valoarea elementului din pozitia indicata de iterator. Exemplu de functie sablon pentru cautarea unei valori date x intre doua pozitii date p1 si p2 dintr-un container si care nu depinde de tipul containerului in care se cauta:

template <class iterator, class T>

iterator find (iterator p1, iterator p2, T x)

Folosind obiecte iterator se poate specifica o subsecventa dintr-o secventa, iar mai multe functii STL (algoritmi generici) au doua argumente de tip iterator. De exemplu, ordonarea crescatoare a unui vector v se poate face astfel:

sort (v.begin(), v.end());

Pentru obiectele de tip vector sau deque nu se recomanda inserari si stergeri frecvente (metodele "insert" si "erase"); daca aplicatia foloseste secvente cu continut dinamic, atunci este mai eficienta secventa list ( timp de ordinul O(1) pentru orice pozitie din lista).

Pentru liste nu este posibil accesul prin indice (pozitional) si nici ordonarea prin metoda "sort" din biblioteca STL.

In STL multimile sunt considerate drept cazuri particulare de dictionare, la care lipsesc valorile asociate cheilor, sau un dictionar este privit ca generalizare a unei multimi cu elemente compuse dintr-o cheie si o valoare. De aceea, se foloseste denumirea de container asociativ pentru dictionare si multimi, iar metodele lor sunt practic aceleasi.

Clasele STL set si map sunt implementate ca arbori binari echilibrati (RBT) si respecta restrictia de chei distincte (unice). Clasele multiset si multimap permit si memorarea de chei identice (multimi si dictionare cu valori multiple).

Desi nu fac parte din standard, bibliotecile STL contin de obicei si clasele hash_set, hash_map, hash_multiset si hash_multimap pentru asocieri realizate ca tabele de dispersie.

Operatiile principale cu multimi, realizate ca metode ale claselor sunt:

iterator insert (T& x); // adauga x la o multime multiset (modifica multimea)

pair<iterator,bool> insert (T & x); // adauga x la o multime, daca nu exista deja

iterator insert (iterator p, T& x);    // insertie x in pozitia p din multime

void erase (iterator p); // elimina elementul din pozitia p

iterator find (T& x); // cauta pe x in multime

Metoda "insert" pentru multimi cu chei multiple are ca rezultat pozitia in care a fost inserat noul element, iar dimensiunea multimii creste dupa fiecare apel. Metoda "insert" pentru multimi cu chei unice are ca rezultat o pereche cu primul membru iterator (pozitia in multime) si cu al doilea membru un indicator care arata daca s-a modificat continutul (si dimensiunea) multimii (valoarea true), sau daca exista deja un element cu valoarea x si nu s-a modificat multimea (valoarea false).

Pentru operatii cu doua multimi (includere, reuniune, intersectie si diferenta) nu exista metode in clasele multime, dar exista functii externe cu argumente iterator. In felul acesta se pot realiza operatii cu submultimi si nu numai cu multimi complete.

Parcurgerea elementelor unei multimi sau unui dictionar (pentru afisarea lor, de exemplu) se poate face numai folosind iteratori, pentru ca nu este posibil accesul prin indici (pozitional) la elementele acestor containere.

Elementele unui dictionar sunt obiecte de tip "pair" (pereche de obiecte), clasa STL definita astfel:

template <class T1,class T2> class pair {

public:

T1 first; T2 second; // date publice ale clasei

pair (T1 & x, T2 & y): first(x),second(y) // constructor de obiecte pair

Pentru dictionare, primul membru al perechii ("first") este cheia, iar al doilea membru ("second") este valoarea asociata cheii.

Metoda "insert" adauga o pereche cheie-valoare la dictionar, metoda "find" determina pozitia acelei perechi care contine o cheie data, iar obtinerea valorii asociate unei chei nu se face printr-o metoda ci prin operatorul de selectie []. Ideea ar fi ca accesul direct la o valoare prin cheie este similar accesului direct la elementul unui vector printr-un indice intreg, iar cheia este o generalizare a unui indice (cheia poate fi de orice tip, dar indicele nu poate fi decat intreg).

Exemplu de creare si afisare a unui dictionar cu frecventa de aparitie a cuvintelor intr-un fisier text:

#include 'defstl.h' // include fisiere antet ale tuturor claselor STL

int main ()

// afisare continut dictionar

for (it=dic.begin(); it !=dic.end(); it++)

cout << (*it).first <<':' << (*it).second << endl;

}

Folosind operatorul de selectie [], ciclul principal din programul anterior se poate rescrie astfel:

while (in >> cuv)

dic[cuv]++;

Operatorul de selectie [] cauta cheia data ca argument iar daca nu o gaseste introduce automat in dictionar un obiect de tip "pair", folosind constructorul implicit al acestei clase (care, la randul lui, apeleaza constructorul implicit pentru tipul "int" si initializeaza cu zero contorul de aparitii).

Utilizarea de clase STL in aplicatii

Aplicatiile care sunt mai usor de scris si de citit cu clase STL sunt cele care folosesc colectii de colectii (vector de liste, de exemplu) si cele in care datele memorate intr-o colectie au mai multe componente ( cum ar fi un arbore Huffman in care fiecare nod contine un caracter, o frecventa si eventual codul asociat).

Inainte de a relua anumite aplicatii folosind clase STL trebuie spus ca in aceste exemple nu vom folosi toate facilitatile oferite de STL pentru a face exemplele mai usor de inteles. In aplicatiile STL se foloseste frecvent functia "copy", inclusiv pentru afisarea continutului unui container pe ecran (in fisierul standard de iesire). Exemplu:

string ts[]=; // un vector de siruri C

vector<string > vs(10); // un obiect vector de siruri C++

copy (ts,ts+3, vs.begin()); // copiere din ts in vs

copy (vs.begin(), vs.end(),ostream_iterator<string> (cout,'n')); // afisare

Aceeasi operatie o vom scrie cu un ciclu explicit folosind un obiect iterator sau operatorul de selectie (numai pentru vectori):

vector<string>::iterator it;

for (it=vs.begin(); it!=vs.end();it++)

cout << *it << ';' ;

cout << endl;

Nu vom utiliza nici alte functii STL ( for_each, count, equal, s.a) care pot face programele mai compacte, dar care necesita explicatii in plus si maresc diferenta dintre programele C si programele C++ pentru aceleasi aplicatii. Vom mentiona numai functiile find si erase deoarece sunt folosite intr-un exemplu si arata care stilul de lucru specific STL.

Functia erase elimina o valoare dintr-un container si necesita ca parametru pozitia din container a valorii eliminate, deci un iterator. Obtinerea pozitiei se poate face prin functia find, deci prin cautarea unei valori intr-un container sau, mai exact, intre doua pozitii date dintr-un container (intr-o subcolectie). Exemplu de functie sablon care elimina o valoare dintr-un container de orice fel:

// elimina pe x din colectia c

template <class T1, class T2> void del (T1 & c, T2 x)

Clasele container existente pot fi utilizate ca atare sau in definirea unor alte clase container.

Clasa vector o vom folosi atunci cand nu putem aprecia dimensiunea maxima a unui vector, deci vectorul trebuie sa se extinda dinamic. In plus, utilizarea unui obiect vector in locul unui vector C ca argument in functii are avantajul reducerii numarului de argumente (nu mai trebuie data dimensiunea vectorului ca argument).

De observat ca metoda "size" are ca rezultat numarul de elemente introduse in vector, iar metoda "capacity" are ca rezultat capacitatea vectorului (care se poate modifica in urma adaugarilor de elemente la vector). Capacitatea initiala poate fi sau specificata in constructorul obiectului vector sau in metoda "reserve".

Programele cu clase STL pot fi simplificate folosind nume de tipuri introduse prin declaratia "typedef" sau prin directiva "define".

Exemplul urmator este o sortare topologica care foloseste un vector de liste de conditionari, unde elementele sortate sunt numere intregi, dar programul se poate modifica usor pentru alte tipuri de date (siruri de exemplu):

// tipul "clist" este o colectie de liste de intregi

typedef vector<list <int> > clist ;

// creare liste de conditionari

void readdata ( clist & cond)

// afisare liste de conditionari

void writedata (clist cond)

}

// elimina x din toate listele colectiei clist

void eraseall (clist & cond, int x)

// sortare topologica cu rezultat in vectorul t

bool topsort (clist cond, vector<int>& t)

} while (gasit);

return ns < n? false: true; // false daca sortare imposibila

}

void main ()

In stilul specific programarii orientate pe obiecte ar trebui definite si utilizate noi clase in loc sa scriem functii ca in C. Programul anterior se poate rescrie cu o clasa pentru obiecte "sortator topologic", avand ca metoda principala pe "topsort".

Definirea de noi clase container

Biblioteca STL contine un numar redus de clase container, considerate esentiale, si care pot fi folosite in definirea altor clase.

Exemplul urmator arata cum se poate defini o clasa pentru grafuri, folosind clasele "vector" si "list", pentru implementarea prin liste de adiacente a grafului:

#include 'defstl.h' // include fisiere antet ale tuturor claselor STL

// clasa pentru un graf ca vector de liste de vecini

class graf

// determina daca exista arc intre nodurile v si w

bool arc (int v, int w)

// adauga la graf arc de la v la w

void addarc (int v, int w)

// dimensiune graf (numar de noduri)

int size()

// afisare graf ca liste de vecini ptr fiecare nod

void print()

}

};

Un alt exemplu este definirea unei clase pentru colectii de multimi disjuncte ca vector de multimi:

// fisier DS.H

#include 'defstl.h'

class sets ;

// fisier DS.CPP

#include "ds.h"

sets::sets(int n): a(n+1)

}

int sets::find (int x)

return -1;

}

void sets::unif (int x, int y)

void sets::print()

}

Un program pentru algoritmul Kruskal, care foloseste clase STL si clasa "arc" definita anterior, va arata astfel:

#include "arc.h"

#include "ds.h"

#include "defstl.h"

int main ()

sets ds(n);

sort (graf.begin(), graf.end()); // ordonare arce dupa costuri

// algoritmul greedy

while ( !graf.empty())

}

// afisare arce din arbore de acoperire de cost minim

cout << 'n';

for ( vector<arc>::iterator p = mst.begin(); p != mst.end(); p++)

cout << *p; // operatorul << supradefinit in clasa arc

}

Definirea unor noi clase container, pentru arbori de exemplu, ar trebui sa se faca in spiritul claselor STL existente, deci folosind iteratori si operatori supradefiniti pentru operatii cu date din container. Pentru simplificare, vom folosi aici metode pentru enumerarea datelor dintr-un container.

In exemplul urmator se defineste o clasa minimala pentru arbori binari de cautare, din care se poate vedea ca pentru metode ce corespund unor algoritmi recursivi trebuie definite functii auxiliare recursive (metodele nu pot fi recursive deoarece nu au ca argument radacina (sub)arborelui prelucrat):

#include 'stldef.h'

// un nod de arbore binar

template <class T> class tnode

};

// un arbore binar de cautare

template <class T > class bst

}

// functie nepublica recursiva de adaugare

void iadd (tnode<T>*& r, T x)

}

public:

bst ( ) // un constructor

void print() // afisare infixata arbore

void add ( T x ) // adaugare la arbore

};

// utilizare

void main ()