};
==

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:
 
priority_queue<int> pq;

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;

pq.push(3);

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)

Desigur, putem redefini operatorul "mai mic" daca dorim o ordonare diferita. De exemplu putem afla cel mai apropiat punct de (0, 0, 0) astfel:
 
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;
 
}

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

};

priority_queue<Point> pq;

==

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:

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:

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

map<string, int> name_to_phone;

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;

name_to_phone["Ion Ion"] = 8234783;

name_to_phone["Me"] = 8237462;

cout << name_to_phone["Ion Ion"] << endl;

==

Pentru un set utilizarea uzuala este:

set<string> s;
 

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

s.insert("Ion ion");

s.insert("baubau");

// scrie 0=false

cout << (s.find("Gica") != s.end()) << endl;

// scrie 1=true

cout << (s.find("baubau") != s.end()) << endl;
==

cout << (s.find("baubau") != s.end()) << endl
 
 
 
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 ok de retinut ca trebuie sa fie definit operatorul <.

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 ok de retinut ca trebuie sa fie definit operatorul {$<$}.

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

template <typename T, typename U>
 

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

U my_func(T t)

{

 
// se autoapeleaza
 
// nu are "side-effects"
 
return result;
 

    // se autoapeleaza
    // nu are "side-effects"
    return result;

}

==

Se transforma in:

map<T, U> cache;
 

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

template <typename T, U>
U my_func(T t)

{

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

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

}

==
 

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.