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:

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;

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

}
==

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.

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.

 
 
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:

template <typename T>
 
typename T::value_type max(
 
typename T::const_iterator begin,
 
typename T::const_iterator end)
 

== 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 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).

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

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

Algoritmi

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: