Standard Template Library (STL)

(Categoria Limbaje de programare, Autor Radu Grigore)

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.
Articol scris de Meditatii Plus

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".

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:

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <string>
#include <algorithm>
#include <iterator>
#include <iostream>
#include <cassert>
using namespace std;

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
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 potrivita 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 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.

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

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;
pq.push(3);
pq.push(4);
pq.push(1);

cout << pq.top() << endl; pq.pop(); // afiseaza 4
cout << pq.top() << endl; pq.pop(); // afiseaza 3
cout << pq.top() << endl; pq.pop(); // afiseaza 1
cout << pq.empty() << endl; // afiseaza 1 (= true)

Desigur, putem redefini operatorul "mai mic" daca dorim o ordonare diferita. De exemplu putem afla cel mai apropiat punct de (0, 0, 0) astfel:

struct Point {
    int x, y, z;
    bool operator < (const Point& o) const {
        return x * x + y * y + z * z > o.x * o.x + o.y * o.y + o.z * o.z;
    }
};

priority_queue <Point> pq;

Intrucat operatiunile de extindere / micsorare la capete sunt uzuale pentru adaptorii stack / queue, acestia folosesc in mod obisnuit drept container un deque. Iar o coada de prioritati este implementata cu heap-uri asa incat rapiditatea accesului indexat este importanta si vector-ul este alegerea default. Aceste alegeri pot fi insa configurate. De exemplu daca aveti o coada de prioritati in care stiti ca veti introduce foarte multe elemente si veti extrage doar cateva ar fi poate mai bine sa folositi:

priority_queue < int, deque <int> > pq;

Cam atat despre secvente. Celalalt tip important de containeri sunt containerii asociativi: map si set (mai exista multimap si multiset dar nu vom vorbi despre ei). Primul este o multime de perechi (cheie, valoare) ce pot fi regasite rapid dupa cheie, care este unica. Implementarea este cu arbori rosu-negru, asa incat timpul de inserare si cel de cautare este O(logN). O utilizare tipica pentru map este:

map <string, int> name_to_phone;
name_to_phone["Ion Ion"] = 8234783;
name_to_phone["Me"] = 8237462;
cout << name_to_phone["Ion Ion"] << endl;

Pentru un set, utilizarea uzuala este:

set <string> s;
s.insert("Ion ion");
s.insert("baubau");
cout << (s.find("Gica") != s.end()) << endl; // afiseaza 0 = false
cout << (s.find("baubau") != s.end()) << endl; // afiseaza 1 = true

Pentru a se putea construi un arbore de cautare pentru chei de tipul T, atat set cat si map necesita ca less <T> sa fie bine definit. Daca nu oferiti voi o specializare a template-ului, cea generica apeleaza operatorul <. Cu alte cuvinte, cu exceptia unor situatii deosebite ce probabil nu apar intr-un concurs, e bine de retinut ca trebuie sa fie definit operatorul <.

Un map este foarte util pentru a memoiza o functie recursiva.

U my_func(T t) {
    // e recursiva si pura (rezultatul depinde doar de parametri)
    return result;
}

Se transforma in:

map <T, U> cache;

U my_func(T t) {
    map <T, U> :: const_iterator it = cache.find(t);
    if(it != cache.end())
        return it->second;
    // corpul vechi
    return cache[t] = result;
}

Transformarea e automata si se face foarte usor. In multe cazuri, plusul de viteza este suficient si nu e nevoie ca tot codul sa fie transformat in varianta cu programare dinamica. In plus solutia de mai sus merge si atunci cand t poate avea valori foarte mari sau nu este un intreg (de exemplu e o structura, un string etc.) si trecerea la programare dinamica n-ar fi evidenta si ar lua ceva timp de gasit o solutie.

Iteratori

Ganditi-va la algoritmul de gasire a maximului. El nu depinde de implementarea folosita pentru reprezentarea multimii! Tot ceea ce trebuie sa faci este sa accesezi toate elementele... nici macar nu conteaza ordinea. Ei bine, iteratorii permit o astfel de decuplare a structurilor de date de algoritmi.

Exemplu:

template <typename T>
typename T::value_type max(typename T::const_iterator begin, typename T::const_iterator end) {
    assert(begin != end); // container vid
    typename T::const_iterator it;
    typename T::value_type r = *begin;
    for(it = begin; it != end; ++it)
        if(*it > r)
            r = *it;
    return r;
}

Observati ca sintaxa pentru iteratori seamana mult cu sintaxa pentru pointeri. Iteratorii din C++ sunt analogul enumeratorilor din C# si Java, doar ca sunt mai flexibili. Operatile care se pot face cu ei sunt: "treci la urmatorul element" (++it), "treci la elementul anterior" (--it), "da-mi o referinta la elementul catre care arati" (*it) si compararea (it_a == it_b, it_a != it_b). Unii iteratori pot, in plus, sa se deplaseze cu n pozitii (it += n, it -= n).

Codul de mai sus poate fi utilizat pentru oricare dintre cele trei secvente prezentate anterior astfel:

deque <int> d;
vector <int> v;
// ... prelucrari ...
cout << max(d.begin(), d.end()) << endl;
cout << max(v.begin(), v.end()) << endl;

Algoritmi

Dupa cum vedeti, utilizarea functiei max este simpla, mai complicata este definitia. Din fericire header-ul <algorithm> are deja scrise tot felul de astfel de functii dragute. Una de care s-ar putea sa va indragostiti :) este next_permutation. Ea primeste ca parametri limitele unei secvente (ca mai sus) si transforma acea secventa in urmatoarea permutare in ordine lexicografica si intoarce true, sau intoarce false daca ordonarea este deja ultima. Iata cum se foloseste:

string handle("rgrig");
sort(handle.begin(), handle.end()); // alta functie folositoare
do {
    cout << handle << endl;
} while(next_permutation(handle.begin(), handle.end()));

Codul de mai sus ilustreaza o alta functie utila: sort. In exemplul urmator vom vedea cum poate fi folosita next_permutation pentru a genera toate combinarile de n elemente luate cate k.

vector <int> choose(n);
for(int i = n - k; i < n; ++i)
    choose[i] = 1;
do {
    // ... foloseste choose ...
} while(next_permutation(choose.begin(), choose.end()));

Am utilizat un vector de intregi si nu unul de booleeni asa cum ar dicta "spiritul" C++ pentru ca secventa vector are o specializare pentru tipul bool si impacheteaza cate 32 de elemente intr-un intreg nativ. Acest lucru are tot felul de efecte neplacute, printre care scaderea vitezei. Exista si un efect "placut", dar util probabil in conjuncturi speciale: ocupa mai putin spatiu.

O alta functie interesanta este copy. Pe aceasta o putem folosi pentru a concatena doua secvente sau pentru a tipari continutul unei secvente.

vector <int> a, b;
// ... pune niste valori in a si b ...

// pune tot continutul lui b la sfarsitul lui a
copy(b.begin(), b.end(), back_inserter(a));

// tipareste continutul lui a
copy(a.begin(), a.end(), ostream_iterator <int> (cout, ", "));

O functie utila pentru prelucrarea sirurilor inainte de parsare este replace. De exemplu, pentru a inlocui toate virgulele cu spatii intr-un sir se procedeaza astfel:

string s("a,b,c,d");
replace(s.begin(), s.end(), ',', ' ');

Daca doriti sa cautati o subsecventa intr-o secventa mai mare atunci puteti folosi search. Acesta intoarce un iterator care pointeaza la locul unde s-a gasit subsecventa sau end, in caz ca nu s-a gasit. De exemplu, pentru a gasi toate aparitiile unui cuvant intr-un sir putem scrie:

// un deque e mai eficient decat un string pentru texte lungi
deque <char> text;
string word;
// ... pune niste valori in text si word ...
deque <char> :: iterator it = text.begin();
int c = 0;
while((it = search(it, text.end(), word.begin(), word.end())) != text.end()) {
    ++c; ++it;
}
// c contine numarul de aparitii ale cuvintului in text, numarand si aparitii care se suprapun

Atentie: complexitatea functiei search este O(M * N) asa incat uneori e prea lenta.

Pentru a numara de cate ori apare un element intr-o secventa putem utiliza functia count.

int av[] = {1, 2, 3, 1, 2, 3, 1};
// un mod de a pune date in v
vector <int> v(av, av + sizeof(av) / sizeof(av[0]));
cout << count(v.begin(), v.end(), 1) << endl; // afiseaza 3
if(!count(v.begin(), v.end(), 4))
    cout << "v nu contine 4" << endl;

Daca vrem sa stim doar daca un element apare sau nu intr-o secventa, o varianta ce se poate dovedi mai rapida in situatii foarte particulare este sa folosim find.

if(find(v.begin(), v.end(), 4) == v.end())
    cout << "v nu contine 4" << endl;

In sfarsit, o ultima functie interesanta ce lucreaza pe secvente este reverse. Utilizare tipica:

int av[] = {1, 1, 2, 1};
vector <int> v(av, av + sizeof(av) / sizeof(av[0]));
reverse(v.begin(), v.end()); // acum v contine 1, 2, 1, 1

Alte mici utilitare care operaza cu valori normale (nu containeri) sunt: max, min, swap. Semantica este probabil evidenta din nume, dar voi da totusi un exemplu de utilizare:

int a = 2, b = 1;
int m = min(a, b);
int M = max(a, b);
swap(m, M);
cout << M << " " << m << endl; // afiseaza "1 2"

Concluzie si referinte

In acest articol am prezentat doar o portiune reprezentativa a STL. Am preferat sa dau multe exemple simple in locul unor explicatii mai teoretice. Uneori mi-a fost tare greu sa ma abtin (de exemplu sa nu povestesc mai in detaliu cum e gestionata implicit zona de memorie "rezervata" si de ce...)

Pentru mai multe detalii puteti fie sa consultati o referinta electronica, fie sa studiati cartea lui Bjarne Stroustrup, "Limbajul C++", aparuta la Teora. Alte referinte ajutatoare:

  1. Power up C++ with the Standard Template Library: Part I
  2. Power up C++ with the Standard Template Library: Part II: Advanced Uses
  3. Referinta SGI
  4. Standardul C++
remote content