* 'Algoritmi':stl#algoritmi
* 'Concluzie si referinte':stl#concluzie

Biblioteca standard C++ are doua componente mari: "standard template library" (STL) si stream-uri de intrare/iesire. Acest articol prezinta un subset al STL pe care il folosesc adesea in practica.

Biblioteca standard C++ are trei mari componente: biblioteca de functii C, cea de stream-uri de intrare / iesire si Standard Template Library (STL). Acest articol prezinta un subset al STL pe care il folosesc adesea in practica.

h2(#introducere). Introducere

STL se bazeaza pe trei concepte centrale: containeri, iteratori si algoritmi. Ca tehnica de programare folosita e bine sa stiti ca orientarea pe obiecte aproape ca lipseste. In schimb se utilizeaza din plin polimorfismul parametric. In C++ numele acestuia este "template"; in C# si Java se obisnuieste sa se spuna "generice".

STL se bazeaza pe trei concepte centrale: containeri, iteratori si algoritmi. Ca tehnica de programare folosita, e bine sa stiti ca orientarea pe obiecte aproape ca lipseste. In schimb se utilizeaza din plin polimorfismul parametric. In C++ numele acestuia este "template"; in C# si Java se obisnuieste sa se spuna "generice".

In continuare voi presupune ca sunteti familiari cu utilizarea template-urilor si cunoasteti bine limbajul C. Codul folosit presupune ca la inceputul fisierului exista:

In continuare voi presupune ca sunteti familiari cu utilizarea template-urilor si cunoasteti bine limbajul C. Codul folosit presupune ca la inceputul fisierului sa existe:

== code(cpp) |

#include <iostream>
#include <deque>
#include <list>

#include <vector>

#include <set>

#include <list>

#include <map>

#include <iterator>

#include <set>
#include <deque>
#include <string>

#include <algorithm>

#include <iterator>
#include <iostream>

#include <cassert>

#include <string>

using namespace std;
==
h2(#containeri). 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:

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);

vector <int> v(10);

// acces indexat

v[1] = 2; cout << v[0] << endl;
v.push_back(3); cout << v[10] << endl;

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)

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.

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 accesul la acestea. $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.

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