Programare orientata pe obiecte

Curs 12 – Containere

C
++{};
C++ Acest curs
› Exemplu de implementare a unui container
› Iterator
› STL
C++ Introducere – simplă clasă vector
› Fie clasa CVector:
class CVector
{
int *v;
size_t sz;
size_t idx;
const size_t chunk = 10;
public:
CVector();
CVector(size_t size);
CVector(const CVector &c);
~CVector();
size_t GetSize(void);
int& GetItem(size_t index);
void PushBack(int item);
int PopBack(void);
};
C++
CVector::CVector() : v(nullptr), sz(0), idx(0)
{}

CVector::CVector(size_t size) : sz(size), idx(0)

{
try
{
v = new int[sz];
}
catch (std::bad_alloc& ba)
{
std::cerr << "bad_alloc: " << ba.what() << "\n";
v = nullptr;
sz = 0;
idx = 0;
}
}
 CVector::CVector(const CVector &c) : sz(c.sz), idx(c.idx)
{
if (c.sz > 0)
C++ {
try
{
v = new int[c.sz];
}
catch (std::bad_alloc& ba)
{
std::cerr << "bad_alloc: " << ba.what() << "\n";
v = nullptr;
sz = 0;
idx = 0;
}
if (v != nullptr)
{
memcpy(v, c.v, sz * sizeof(int));
}
}
else
{
v = nullptr;
}
}
 CVector::~CVector()
{
if (v != nullptr)
C++ {
delete[] v;
v = nullptr;
sz = 0;
idx = 0;
}
}

size_t CVector::GetSize(void)
{
return idx;
}

int& CVector::GetItem(size_t index)

{
if (index >= idx)
{
throw "Index too large!";
}
return v[index];
}
 void CVector::PushBack(int item)
{
if (idx >= sz)

C++ {
int *tmp = nullptr;
try
{
tmp = new int[sz + chunk];
}
catch (std::bad_alloc& ba)
{
std::cerr << "bad_alloc: " << ba.what() << "\n";
}
if (tmp != nullptr)
{
memcpy(tmp, v, idx * sizeof(int));
sz = sz + chunk; tmp[idx] = item; idx++;
delete[] v;
v = tmp;
}
}
else
{
v[idx] = item; idx++;
}
C++
int CVector::PopBack(void)
{
if (idx > 0)
{
idx--;
return v[idx];
}
else
{
throw "No more items!";
}
}
C++ Introducere – simplă clasă vector
› Utilizarea tipului de date CVector:
int main(void)
{
CVector v;

v.PushBack(1);
v.PushBack(2);
v.PushBack(3);
v.PushBack(4);
v.PushBack(5);

for(size_t i = 0; i<v.GetSize(); i++)

{
cout << v.GetItem(i) <<endl;
}
return 0;
}
C++ Introducere – class CVector – lift up
› Fie clasa template MyVector:
template<class T>
class CVector
{
T *v;
size_t sz;
size_t idx;
const size_t chunk = 10;
public:
CVector();
CVector(size_t size);
CVector(const CVector &c);
~CVector();
size_t GetSize(void);
T& GetItem(size_t index);
void PushBack(T item);
T PopBack(void);
};
 template<typename T>
void CVector::PushBack(int item)
{

C++ if (idx >= sz)

{
T *tmp = nullptr;
try
{
tmp = new T[sz + chunk];
}
catch (std::bad_alloc& ba)
{
std::cerr << "bad_alloc: " << ba.what() << "\n";
}
if (tmp != nullptr)
{
memcpy(tmp, v, idx * sizeof(T));
sz = sz + chunk; tmp[idx] = item; idx++;
delete[] v; v = tmp;
}
}
else
{
v[idx] = item; idx++;
}
C++
template<typename T>
T CVector::PopBack(void)
{
if (idx > 0)
{
idx--;
return v[idx];
}
else
{
throw "No more items!";
}
}
C++ Introducere – class MyVector – lift up
int main(void)
{
CVector<double> v;

v.PushBack(1.1);
v.PushBack(2.2);
v.PushBack(3.3);
v.PushBack(4.4);
v.PushBack(5.5);

for(size_t i = 0; i<v.GetSize(); i++)

{
cout << v.GetItem(i) <<endl;
}
return 0;
}
C++ Introducere – adăugarea unei clase iterator
template<class T>
class CVector
{
T *v;
size_t sz;
size_t idx;
const size_t chunk = 10;
public:
class CIterator
{ … };
CIterator Begin(void) { return CIterator(v); }
CIterator End(void) { return CIterator(v + idx); }
CVector();
CVector(size_t size);
CVector(const CVector &c);
~CVector();
size_t GetSize(void);
T& GetItem(size_t index);
void PushBack(T item);
T PopBack(void);
C++ Introducere – class CIterator
class CIterator
{
int *ptr;
public:
CIterator() : ptr(nullptr) {};
CIterator(int *p) :ptr(p) {}
CIterator(const CIterator& c) : ptr(c.ptr) {}
CIterator& operator++() { ptr++; return *this; }
CIterator operator++(int)
{
CIterator tmp(*this);
ptr++;
return tmp;
}
bool operator==(const CIterator& c) { return ptr == c.ptr; }
bool operator!=(const CIterator& c) { return ptr != c.ptr; }
int& operator*() { return *ptr; }
};
C++ Introducere – utilizare iterator
int main(void)
{
MyVector<int> v;

v.PushBack(1);
v.PushBack(2);
v.PushBack(3);
v.PushBack(4);
v.PushBack(5);

for(MyVector::CIterator it = v.Begin(); it!=v.End(); it++)

{
cout << *it <<endl;
}
return 0;
}
C++ Introducere - STL
› Librăria standard este un set de componente specificate în standardul ISO
C++, furnizate cu un comportament identic de către orice implementare
C++.
› Componentele sunt reutilizabile
› În anii ’70 componentele folosite de programatori erau structurile de control
şi funcţiile
› În anii ’80 programatorii foloseau clase dintr-o gamă largă de biblioteci
dependente de platformă
› Odată cu standardul STL din anul ’97 se introduc componente definite prin
clase independente de platformă
› Structurile de date sunt colecţii de date (containeri) organizate după diverse
reguli
C++ Introducere - STL
› În C++ structurile de date sunt obiecte ce conţin colecţii de obiecte:
– Clasa vector reprezintă un vector de obiecte de tip int
– Prin utilizarea template-urilor se redefineşte clasa vector la vector<T> astfel
încât se extinde acest tip de date la vector<char>, vector<double>,
vector<Angajat> sau orice tip de dată
– Similar se poate proceda cu implementarea structurilor de tip stivă, lista, arbori,
grafuri etc.
› STL este o biblioteacă de clase template dar conţine şi implementări ale
structurilor de date.
› În C şi C++ elementele unui tablou sunt accesate prin intermediul
pointerilor. În C++ STL elementele unui container sunt accesate prin
intermediul iteratorilor care sunt tot pointeri dar care se comportă
inteligent.
C++ Introducere - STL
› Containerii implementează operaţii primitive.
› Algoritmii ce utilizează containeri sunt independenţi de tipurile de date
conţinute.
› În STL s-a evitat folosirea moştenirii şi a funcţiilor virtuale din
considerente de performanţă.
› S-a evitat utilizarea operatorilor new şi delete în favoarea alocatorilor
(permit metode de control pentru alocare şi dealocare de memorie)
› Managementul erorilor
C++ STL - structură
› STL cuprinde trei elemente principale:
– Containeri – obiecte ce conţin obiecte
– Iteratori – pointeri „inteligenţi” pentru acces la elementele unui
container
– Algoritmi – funcţionalităţi de acces şi prelucrare asupra
elementelor containerilor.
C++ Containere
C++ Iteratori
› Iteratorii sunt obiecte care se comportă asemănător pointerilor şi care
sunt utilizaţi pentru a accesa elementele unui container.
› Iteratorii se aseamănă cu pointerii, dar sunt de fapt obiecte ce
adresează alte obiecte. Cu ajutorul lor pot fi adresate elemente ale
containerelor care aparţin anumitor intervale. Iteratorii reprezintă
interfaţa de comunicaţie între algoritmi şi containere, fiind preluaţi ca
parametrii de către algoritmi. Containerele le furnizează algoritmilor o
cale de acces către elementele lor prin intermediul iteratorilor.
› Algoritmii furnizează funcţionalităţi de acces şi prelucrare asupra
elementelor containerelor
C++ Iteratori
C++ Algoritmi
› Algoritmii STL se împart în patru mari categorii:
– Algoritmi care modifică ordinea elementelor în container - modifying sequence
operations: copy(), replace(), transform() şi remove().
– Algoritmi care nu modifică ordinea elementelor în container – non-modifying
sequence operations: for_each(), find(), count() şi equal().
– Algoritmi de sortare şi operaţii similare: sort(), equal_range(), merge() şi
includes().
– Algoritmi generali pentru operaţii numerice: min(), max().
C++ Containere
› Containerele secvenţiale sunt colecţii liniare şi ordonate de date în care
accesul se face pe baza poziţiei elementului în cadrul containerului.
– vector (adaugare pe la un singur capăt)
– list (adaugare pe la ambele capete)
– deque (adăugare pe la ambele capete)
› Ordinea elementelor este dată de ordinea în care au fost adăugate
› Containere asociative se diferenţiază prin faptul că stocarea elementelor se
face pe baza unor chei. Ordinea elementelor este dată de valorile cheilor şi
relaţia dintre ele. Accesul este direct prin intermediul cheii.
– set
– multiset
– map
– multimap
C++ Containere
› Containere adaptive – adaugă funcţionalităţi containerelor secvenţiale.
› Nu pot fi parcurse cu ajutorul iteratorilor intrucât nu sunt folosite în mod
independent
› Programatorul trebuie să aleagă containerul de bază căruia să îi aplice
un container adaptiv.
› Un container stack poate adapta containere vector, list, deque, un
container queue poate adapta list şi deque, priroty_queue poate
adapta un vector sau deque.
C++ Containere secvenţiale - exemple
class CStudent
{
private:
int nrMat;
char nume[20];
public:
CStudent(int nr = 0, char* n = "Student"):nrMat(nr);
CStudent(const Student& s);
int GetNrMat(void);
char* GetNume(void);
void SetNume(char* n);
bool operator<(Student& s);
friend ostream& operator<<(ostream& s, const CStudent& c);
};
 void main(void )
{
vector<int> vectInt;
C++ vectInt.push_back(5);
vectInt.push_back(0);
vectInt.push_back(15);
vectInt.push_back(13);

for(int i=0; i<vectInt.size(); i++)

cout<<vectInt[i].GetNrMat()<<" "<< vectInt[i].GetNume()<<endl;
cout<<endl;

CStudent stud1(1, „Popescu");

CStudent stud2(2, „Marian");
CStudent stud3(3, „Gica");
vector<Student> vectStud;
vectStud.push_back(stud1);
vectStud.push_back(stud2);
vectStud.push_back(stud3);

for(int i=0; i<vectStud.size(); i++)

cout<<vectStud[i]<<" ";
cout<<endl;
}
C++
list<int> listInt;
listInt.push_front(-4);
listInt.push_back(15);
listInt.insert(listInt.begin(),19);
listInt.insert(listInt.end(),3);

list<int>::iterator it;
for(it=listInt.begin(); it!=listInt.end(); it++)
cout<<*it<<" ";
cout<<endl;
listInt.sort();
cout<<"Lista sortata"<<endl;
for(it=listInt.begin(); it!=listInt.end(); it++)
cout<<*it<<" ";
cout<<endl;
C++
list<Student> listStud;
listStud.push_back(stud2);
listStud.push_front(stud3);
listStud.insert(listStud.end(),s1);

list<Student>::iterator it;
for(it=listStud.begin(); it!=listStud.end(); it++)
cout<<(*it).GetNrMat()<<" "<< vectInt[i].GetNume()<<endl;
cout<<endl;

listStud.sort();

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

cout<<*it<<" ";
cout<<endl;