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)

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:

set <string> s;
s.insert("Ion ion");
s.insert("baubau");

cout << (s.find("Gica") != s.end()) << endl; // scrie 0 = false
cout << (s.find("baubau") != s.end()) << endl; // scrie 1 = true

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

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

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

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

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

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

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

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

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

sort(ALL(handle)); // alta functie draguta
do cout << handle << endl; while (next_permutation(ALL(handle));

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

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

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

do {

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

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

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

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

copy(b.begin(), b.end(), back_inserter(a));
 

// tipareste continutul lui a

copy(ALL(a), ostream_iterator<int>(cout, ", "));

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:

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

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

replace(s.begin(), s.end(), ',', ' ');

==

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

== code(cpp) |

// un deque e mai eficient decat string pt. texte lungi
deque<char> text;
string cuvint;
// .. pune niste valori in text si word ..
deque<char>::iterator it = text.begin();

// 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(), ALL(word))) != text.end()) { ++c; ++it; }
// c contine numarul de aparitii ale cuvintului in text, numarind aparitii care se suprapun

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

==

Atentie: complexitatea functiei $search$ este $O(mn)$ asa incat uneori e prea lenta.

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$}.
== 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;

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

== code(cpp) |

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

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:
== code(cpp) |
int av[] = {1, 1, 2, 1};

vector<int> v(ALLARRAY(av));
reverse(ALL(v)); // acum v contine 1, 2, 1, 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 m = min(a, b);
int M = max(a, b);
swap(m, M);

cout << M << " " << m << endl; // prints "1 2"

cout << M << " " << m << endl; // afiseaza "1 2"

==
h2(#concluzie). 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...

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 luati cartea lui Bjarne Stroustrup "Limbajul C++" aparuta la teora. Vezi si:

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:

# "O alta prezentare introductiva":http://www.topcoder.com/index?t=features&c=feat_082803

# 'Power up C++ with the Standard Template Library: Part I':http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=standardTemplateLibrary
# '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/

# "Referinta Dinkumware":http://www.dinkumware.com/refxcpp.html
# "Standardul":http://www.csci.csusb.edu/dick/c++std/cd2/

# "Standardul C++":http://www.csci.csusb.edu/dick/c++std/cd2/