using namespace std;
==

Containeri

h2. Containeri

In limbajul de baza avem la dispozitie tablourile pentru reprezentarea unei secvente indexate de elemente. Dimensiunea unui tablou trebuie fie sa fie cunoscuta la compilare, fie sa fie gestionata explicit de programator prin alocare dinamica. Principalul avantaj al STL este ca ne scapa de aceasta grija. In afara de adresarea indexata obisnuita secventele STL au si operatia push_back: adauga un element la sfarsit (si, evident, creste dimensiunea cu 1). Exista si operatia inversa pop_back: elimina ultimul element. Cele trei secvente STL care suporta aceste operatii sunt vector, deque si list. Un exemplu de utilizare este:
 
// v are 10 elemente egale cu 0

In limbajul de baza avem la dispozitie tablourile pentru reprezentarea unei secvente indexate de elemente. Dimensiunea unui tablou trebuie fie sa fie cunoscuta la compilare, fie sa fie gestionata explicit de programator prin alocare dinamica. Principalul avantaj al STL este ca ne scapa de aceasta grija. In afara de adresarea indexata obisnuita secventele STL au si operatia {$push_back$}: adauga un element la sfarsit (si, evident, creste dimensiunea cu {$1$}). Exista si operatia inversa {$pop_back$}: elimina ultimul element. Cele trei secvente STL care suporta aceste operatii sunt {$vector$}, $deque$ si {$list$}. Un exemplu de utilizare este:
== code(cpp) |// v are 10 elemente egale cu 0

vector<int> v(10);

// acces indexat

v[1] = 2; cout << v[0] << endl;

v.push_back(3); cout << v[10] << endl;

v.pop_back();

==

Cele trei secvente difera prin implementare. Pe scurt, vector tine datele intr-o zona continua de memorie, list este o lista dublu inlantuita a elementelor, iar deque este ceva intre: o lista inlantuita de pachete continue. (deque vine de la "double ended queue" dar se pronunta "deck" -- pachet tocmai pentru a sugera implementarea)
 
Este util sa stim in mare care e implementarea pentru a alege secventa in functie de operatiile pe care le avem de facut si de frecventa lor. De exemplu vector are cel mai rapid acces indexat; pe de alta parte adaugarea unui element poate duce la copierea intregului continut daca nu mai exista memorie rezervata la coada (adica v.capacity() == v.size()). Lista este rapida pentru inserari de elemente in interior dar este lenta pentru accesele indexate. Deque este mai eficienta decat vector daca se fac multe operatii push_back dar este ceva mai lenta pentru accese indexate uzuale. In plus mai exista si o diferenta de interfata. Atat deque cat si list ofera in plus fata de vector operatiile push_front si pop_front. Aceasta deoarece in cazul vectorilor ele ar fi avut complexitatea O(n) daca se dorea pastrarea rapiditatii accesului indexat.

Cele trei secvente difera prin implementare. Pe scurt, $vector$ tine datele intr-o zona continua de memorie, $list$ este o lista dublu inlantuita a elementelor, iar $deque$ este ceva intre: o lista inlantuita de pachete continue. (deque vine de la "double ended queue" dar se pronunta "deck" -- pachet tocmai pentru a sugera implementarea)

Sa vedem o implementare de jucarie a unei cozi cu ajutorul deque pentru a mai ilustra cateva functii membre.

Este util sa stim in mare care e implementarea pentru a alege secventa in functie de operatiile pe care le avem de facut si de frecventa lor. De exemplu $vector$ are cel mai rapid acces indexat; pe de alta parte adaugarea unui element poate duce la copierea intregului continut daca nu mai exista memorie rezervata la coada (adica {$v.capacity() == v.size()$}). Lista este rapida pentru inserari de elemente in interior dar este lenta pentru accesele indexate. $Deque$ este mai eficienta decat $vector$ daca se fac multe operatii $push_back$ dar este ceva mai lenta pentru accese indexate uzuale. In plus mai exista si o diferenta de interfata. Atat $deque$ cat si $list$ ofera in plus fata de vector operatiile $push_front$ si {$pop_front$}. Aceasta deoarece in cazul vectorilor ele ar fi avut complexitatea $O(n)$ daca se dorea pastrarea rapiditatii accesului indexat.

template <typename T>

Sa vedem o implementare de jucarie a unei cozi cu ajutorul $deque$ pentru a mai ilustra cateva functii membre.
== code(cpp) |template <typename T>

class Queue

 
{
 
private:
 
deque<T> data;
 
public:
 
void Push(const T& el)
 

{

 
data.push_back(el);
 
}
 
T Pop()
 
{
 
assert(!data.empty());
 
T result(data.front());
 
data.pop_front();
 
return result;
 
}
 

    private:
        deque<T> data;
    public:
        void Push(const T& el)
        {
            data.push_back(el);
        }
        T Pop()
        {
            assert(!data.empty());
            T result(data.front());
            data.pop_front();
            return result;
        }

};

Interesant este ca STL are deja astfel de adaptori ale secventelor simple: stack, queue si priority_queue. Metodele uzuale sunt pop, push si top; push si pop au semantica uzuala iar top intoarce o referinta la elementul care va fi inlaturat de urmatorul pop. In plus se mai poate testa daca containerul e gol cu empty. Voi da un exemplu de utilizare a priority_queue:
priority_queue<int> pq;