STL

(Creat de Radu Grigore •rgrig la data de 2004-12-05 categoria Limbaje, autor(i) Radu Grigore)

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.

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 exista:

#include <iostream>
#include <deque>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iterator>
#include <algorithm>
#include <cassert>
#include <string>
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 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.

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(); // scrie 4
cout << pq.top() << endl; pq.pop(); // scrie 3
cout << pq.top() << endl; pq.pop(); // scrie 1
cout << pq.empty() << endl; // scrie 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 voi 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(lg n). 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");
// scrie 0=false
cout << (s.find("Gica") != s.end()) << endl;
// scrie 1=true
cout << (s.find("baubau") != s.end()) << endl;

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 ok de retinut ca trebuie sa fie definit operatorul <.

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

template <typename T, typename U>
U my_func(T t)
{
    // se autoapeleaza
    // nu are "side-effects"
    return result;
}

Se transforma in:

map<T, U> cache;
template <typename T, U>
 
U my_func(T t)
{
    map<T, U>::const_iterator it =  cache.find(t);
    if (it != cache.end()) return *it;
    // 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 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 deci trecerea la programare dinamica n-ar fi evidenta si ar lua ceva timp de gasit o solutie.

Exemplul de mai sus foloseste o functie template numai pentru a sugera ca acolo pot fi orice tipuri (nu doar intregi). In practica template-urile mai mult se folosesc decat se scriu.

Sa trecem acum la iteratori.

h2. Iteratori

Ganditiva 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 intre structurile de date si algoritmi.

Exemplu:

== code(cpp) |template <typename T>
typename T::value_type max(typename T::const_iterator begin, typename T::const_iterator end)
{
    assert (begin != end); // container empty
    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:

#define ALL(c) (c).begin(), (c).end()
deque<int> d;
vector<int> v;
// ... some work ..
cout << max(ALL(d)) << endl;
cout << max(ALL(v)) << 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. Ia primeste ca parametrii 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(ALL); // alta functie draguta

do {

cout << handle << endl;

} while (next_permutation(ALL);

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 ..
} next_permutation(ALL);

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. Asta 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(ALL, back_inserter(a));
// tipareste continutul lui a
copy(ALL, 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(ALL, ',', ' ');

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

// un deque e mai eficient decat string pt. 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(), ALL)) != text.end()) {
++c; ++it;
}
// c contine numarul de aparitii al lui word in text

Atentie: complexitatea functiei search este O(mn) asa incat uneori va trebui sa faceti totusi cautarea de mana.

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

#define ALLARRAY (a), ((a) + sizeof(a)/sizeof(a⁰))
int av[] = {1, 2, 3, 1, 2, 3, 1};

// un mod de a pune date in v

vector<int> v(ALLARRAY);

cout << count(ALL, 1) << endl; // prints 3
if (!count(ALL, 4))
cout << "v nu contine 4" << endl;

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

if (find(ALL, 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(ALLARRAY);
reverse(ALL); // 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; // prints "1 2"

Concluzie si referinte

Ce am prezentat in acest articol reprezinta o portiune reprezentativa a STL, dar este totusi doar o portiune. 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 luati cartea lui Bjarne Stroustrup "Limbajul C++" aparuta la teora. Vezi si:

1. [1]O alta prezentare introductiva

2. [2]Referinta SGI

3. [3]Referinta Dinkumware

4. [4]Standardul

References

Visible links
1. http://www.topcoder.com/index?t=features&c=feat_082803
2. http://www.sgi.com/tech/stl/
3. http://www.dinkumware.com/refxcpp.html
4. http://www.csci.csusb.edu/dick/c++std/cd2/