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

== code(cpp) |#include <iostream>

== code(cpp) |
#include <iostream>

#include <deque>
#include <list>
#include <vector>

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

== code(cpp) |
// v are 10 elemente egale cu 0

vector<int> v(10);
// acces indexat
v[1] = 2; cout << v[0] << endl;

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

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

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

== code(cpp) |priority_queue<int> pq;

== code(cpp) |
priority_queue<int> pq;

pq.push(3);
pq.push(4);
pq.push(1);

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

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

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

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:

== code(cpp) |map<string, int> name_to_phone;

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

== code(cpp) |set<string> s;

== code(cpp) |
set<string> s;

s.insert("Ion ion");
s.insert("baubau");
// scrie 0=false

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

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

== code(cpp) |
template <typename T, typename U>
U my_func(T t) {
  // e recursiva si pura (rezultatul depinde doar de parametrii)
  return result;

}
==
Se transforma in:

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

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

template <typename T, U>

U my_func(T t)
{

U my_func(T t) {

    map<T, U>::const_iterator it =  cache.find(t);
    if (it != cache.end()) return *it;
    // corpul vechi

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;

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

}
==

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

== code(cpp) |#define ALL(c) (c).begin(), (c).end()

== code(cpp) |
#define ALL(c) (c).begin(), (c).end()

deque<int> d;
vector<int> v;
// ... some work ..

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

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

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

do {
    cout << handle << endl;
 
} while (next_permutation(ALL(handle));

do 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$}.

== code(cpp) |vector<int> choose(n);
for (int i = n-k; i < n; ++i)
choose[i] = 1;

== code(cpp) |
vector<int> choose(n);
for (int i = n-k; i < n; ++i) choose[i] = 1;

do {
    // .. foloseste choose ..
} next_permutation(ALL(choose));

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

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

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:

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

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

string cuvint;

// .. pune niste valori in text si word ..
deque<char>::iterator it = text.begin();
int c = 0;

while (
 
        (it = search(it, text.end(), ALL(word))) != text.end()) {
    ++c; ++it;
}
// c contine numarul de aparitii al lui word in text

while ((it = search(it, text.end(), ALL(word))) != text.end()) { ++c; ++it; }
// c contine numarul de aparitii ale cuvintului in text, numarind aparitii care se suprapun

==

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 e prea lenta.

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

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

if (!count(ALL(v), 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$}.

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

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

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