== code(cpp) |map<T, U> cache;
template <typename T, U>

//

U my_func(T t)
{
    map<T, U>::const_iterator it =  cache.find(t);

h2. 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");

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:
== code(cpp) |string handle("rgrig");

sort(ALL(handle)); // alta functie draguta

do {

 
cout << handle << endl;

    cout << handle << endl;

} while (next_permutation(ALL(handle));

==

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.

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

== code(cpp) |vector<int> choose(n);

for (int i = n-k; i < n; ++i)
choose[i] = 1;
do {

// .. foloseste choose ..

    // .. foloseste choose ..

} next_permutation(ALL(choose));

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.
 

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.

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;

== code(cpp) |vector<int> a, b;

// .. pune niste valori in a si b ..
// pune tot continutul lui b la sfarsitul lui a
copy(ALL(b), back_inserter(a));
// tipareste continutul lui a
copy(ALL(a), 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:

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

== code(cpp) |string s("a,b,c,d");

replace(ALL(s), ',', ' ');

==

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:

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

== code(cpp) |// un deque e mai eficient decat string pt. texte lungi

deque<char> text;
string word;
// .. pune niste valori in text si word ..

int c = 0;
while (

(it = search(it, text.end(), ALL(word))) != text.end()) {
++c; ++it;

        (it = search(it, text.end(), ALL(word))) != 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.

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.

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

#define ALLARRAY(a) (a), ((a) + sizeof(a)/sizeof(a[0]))

== code(cpp) |#define ALLARRAY(a) (a), ((a) + sizeof(a)/sizeof(a[0]))

int av[] = {1, 2, 3, 1, 2, 3, 1};

// un mod de a pune date in v

vector<int> v(ALLARRAY(av));

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

cout << "v nu contine 4" << endl;

    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.

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(v), 4) == v.end())
cout << "v nu contine 4" << endl;

== code(cpp) |if (find(ALL(v), 4) == v.end())
    cout << "v nu contine 4" << endl;
==

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

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

int av[] = {1, 1, 2, 1};

== code(cpp) |int av[] = {1, 1, 2, 1};

vector<int> v(ALLARRAY(av));
reverse(ALL(v)); // 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:

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;

== code(cpp) |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

h2. 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/

# "O alta prezentare introductiva":http://www.topcoder.com/index?t=features&c=feat_082803
# "Referinta SGI":http://www.sgi.com/tech/stl/
# "Referinta Dinkumware":http://www.dinkumware.com/refxcpp.html
# "Standardul":http://www.csci.csusb.edu/dick/c++std/cd2/