h1. Standard Template Library (STL)

(Categoria _Limbaje_, Autor _Radu Grigore_)

(Categoria _Limbaje de programare_, Autor _Radu Grigore_)

(toc){width: 15em}*{text-align:center;} *Continut*
* 'Introducere':stl#introducere

* 'Concluzie si referinte':stl#concluzie
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':https://meditatiiplus.ro

h2(#introducere). Introducere

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)

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:

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

priority_queue <int, deque <int> > pq;

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:

h2(#algoritmi). 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:

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:

== code(cpp) |
string handle("rgrig");

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 contrar. De exemplu, pentru a gasi toate aparitiile unui cuvant intr-un sir putem scrie:

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:

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

while((it = search(it, text.end(), word.begin(), word.end())) != text.end()) {
    ++c; ++it;
}

// c contine numarul de aparitii ale cuvintului in text, numarand aparitii care se suprapun

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

# 'Power up C++ with the Standard Template Library: Part II: Advanced Uses':http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=standardTemplateLibrary2
# "Referinta SGI":http://www.sgi.com/tech/stl/
# "Standardul C++":http://www.csci.csusb.edu/dick/c++std/cd2/

3678