Cele trei secvente difera prin implementare. Pe scurt, $vector$ tine datele intr-o zona continua de memorie, $list$ este o lista dublu inlantuita a elementelor, iar $deque$ este ceva intre: o lista inlantuita de pachete continue (deque vine de la "double ended queue", dar se pronunta "deck" = "pachet", tocmai pentru a sugera implementarea).
Este util sa stim in mare care e implementarea pentru a alege secventa in functie de operatiile pe care le avem de facut si de frecventa lor. De exemplu $vector$ are cel mai rapid acces indexat; pe de alta parte adaugarea unui element poate duce la copierea intregului continut daca nu mai exista memorie rezervata la coada (adica {$v.capacity() == v.size()$}). Lista este rapida pentru inserari de elemente in interior, dar este lenta pentru accesul la acestea. $Deque$ este mai eficienta decat $vector$ daca se fac multe operatii $push_back$ dar este ceva mai lenta pentru accese indexate uzuale. In plus mai exista si o diferenta de interfata. Atat $deque$ cat si $list$ ofera in plus fata de vector operatiile {$push_front$} si {$pop_front$}. Aceasta deoarece in cazul vectorilor ele ar fi avut complexitatea $O(n)$ daca se dorea pastrarea rapiditatii accesului indexat.
Este util sa stim in mare care e implementarea pentru a alege secventa potrivita in functie de operatiile pe care le avem de facut si de frecventa lor. De exemplu $vector$ are cel mai rapid acces indexat; pe de alta parte adaugarea unui element poate duce la copierea intregului continut daca nu mai exista memorie rezervata la coada (adica {$v.capacity() == v.size()$}). Lista este rapida pentru inserari de elemente in interior, dar este lenta pentru accesul la acestea. $Deque$ este mai eficienta decat $vector$ daca se fac multe operatii $push_back$ dar este ceva mai lenta pentru accese indexate uzuale. In plus mai exista si o diferenta de interfata. Atat $deque$, cat si $list$ ofera fata de $vector$ operatiile {$push_front$} si {$pop_front$}. Aceasta deoarece in cazul vectorilor, ele ar fi avut complexitatea $O(N)$ daca se dorea pastrarea rapiditatii accesului indexat.
Sa vedem o implementare de jucarie a unei cozi cu ajutorul $deque$ pentru a mai ilustra cateva functii membre.
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;
}
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$}:
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;
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)
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:
== 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; }
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;
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:
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 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:
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:
== code(cpp) |
map<string, int> name_to_phone;
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:
Pentru un set, utilizarea uzuala este:
== code(cpp) |
set<string> s;
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("Gica") != s.end()) << endl; // scrie 0 = false
cout << (s.find("baubau") != s.end()) << endl; // scrie 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 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 bine de retinut ca trebuie sa fie definit operatorul {$<$}.
Un map este foarte util pentru a memoiza o functie recursiva.
== code(cpp) |
template <typename T, typename U>
U my_func(T t) {
// e recursiva si pura (rezultatul depinde doar de parametrii)
return result;
// e recursiva si pura (rezultatul depinde doar de parametri)
return result;
}
==
Se transforma in:
== code(cpp) |
map<T, U> cache;
template <typename T, U>
map <T, U> cache;
U my_func(T t) {
map<T, U>::const_iterator it = cache.find(t);
if (it != cache.end()) return *it;
map <T, U> :: const_iterator it = cache.find(t);
if(it != cache.end())
return it->second;
// 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.
Sa trecem acum la iteratori.
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 cu 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 trecerea la programare dinamica n-ar fi evidenta si ar lua ceva timp de gasit o solutie.
h2(#iteratori). Iteratori
