Metodele si functiile STL
Scopul STL este sa asigure implementari eficiente pentru algoritmii obisnuiti. Acesti algoritmi sunt exprimati ca functii generale care pot fi folosite cu orice container care satisface cerintele specifice algoritmului si ca metode care pot fi folosite cu instantieri ale unor clase container. În aceasta anexa se presupune ca sunteti familiarizati deja cu STL, desigur, daca ati citit Capitolul 15. De exemplu, se presupune ca stiti ce sunt iteratorii si constructorii.
Membri comuni pentru toate containerele
Toate containerele definesc tipurile din Tabelul G.1. În acest tabel, X este un tip de container, cum ar fi vector<int>, iar T este tipul stocat în container, cum ar fi int
Tabelul G.1 Tipuri definite pentru toate containerele.
Tip Valoare
X::value_type T, tipul elementului
X::reference Se comporta ca T &
X::const_reference Se comporta ca si const T &
X::iterator Tip iterator care indica tipul T, se comporta ca si T *
X::const_iterator Tip iterator care indica tipul const T, se comporta ca si const T *
X::difference_type Tip întreg cu semn folosit pentru a indica distanta de la un iterator la
altul; de exemplu, diferenta dintre doi pointeri
X::size_type Tip întreg fara semn care poate reprezenta dimensiunea obiectelor,
numarul de elemente sau indici
În definitia clasei se va folosi un typedef pentru definirea acestor membri. Puteti folosi aceste tipuri pentru a declara variabile potrivite. De exemplu, în cele ce urmeaza se înlocuieste prima aparitie a cuvântului "premiu" dintr-un vector de obiecte string cu "craniu" pentru a demonstra declararea variabilelor utilizând tipuri membre:
vector<string> intrare;
string temp;
while (cin >> temp && temp != "gata")
intrare.push_back(temp);
vector<string>::iterator dorit =
find(intrare.begin(), intrare.end(), string("premiu"));
if (dorit != intrare.end())
Acest cod declara r ca referinta la elementul din intrare pe care îl indica dorit
Aceste tipuri pot fi folosite si în cod mai general, în care tipul containerului si tipul elementelor sunt generice. De exemplu, sa presupunem ca doriti o functie min() care primeste ca argument o referinta la un container si returneaza cel mai mic element din container. Acest lucru presupune ca operatorul < este definit pentru tipul valorilor din container si ca nu doriti sa folositi algoritmul STL min_element(), care foloseste o interfata cu iteratori. Deoarece argumentul poate fi vector<int> list<string> sau deque<double>, folositi un sablon cu un parametru sablon, cum ar fi Punga, pentru a reprezenta containerul. Deci tipul argumentului functiei va fi const Punga & p. Dar tipul returnat? Trebuie sa fie tipul valorii pastrate în container, adica Punga::value_type. Totusi, în acest moment, Punga este doar un parametru sablon, iar compilatorul nu are de unde sa stie ca membrul value_type este chiar un tip. Însa puteti folosi cuvântul cheie typename pentru a clarifica statutul de membru al unui typedef
vector<string>::value_type st;// vector<string> clasa definita
typename Punga::value_type m; // Punga, tip inca nedefinit
Pentru prima definitie, compilatorul are acces la definitia sablonului vector, în care se declara value_type ca un typedef. Pentru a doua definitie, cuvântul cheie typename asigura faptul ca Punga::value_type este un typedef. Prin urmare, respectând aceste consideratii, functia va avea definitia:
template<typename Punga>
typename Punga::value_type min(const Punga & p)
De asemenea, toate containerele contin functiile membre si operatiile listate în Tabelul G.2. Din nou, X este un tip container, cum ar fi vector<int>, iar T este tipul stocat în container, cum ar fi int. De asemenea, a si b sunt valori de tip X
Tabelul G.2 Metode definite pentru toate containerele.
Metoda / Operatie Descriere
begin() Returneaza un iterator la primul element
end() Returneaza un iterator la dincolo-de-sfârsit
rbegin() Returneaza un iterator invers la dincolo-de-sfârsit
rend() Returneaza un iterator invers la primul element
size() Returneaza numarul de elemente
maxsize() Returneaza marimea maxima pe care o poate avea un container
empty() Returneaza true în cazul în care containerul este gol
swap() Schimba între ele continuturile a doua containere
== Returneaza true daca doua containere au aceeasi dimensiune si aceleasi
elemente în aceeasi ordine
!= a != b este identic cu !(a == b)
< Returneaza true daca a îl precede lexicografic pe b
> a > b este identic cu b < a
<= a <= b este identic cu !(a > b)
>= a >= b este identic cu !(a < b)
Operatorul > pentru un container presupune ca operatorul > este definit pentru tipul stocat. O comparatie lexicografica este o generalizare a ordonarii alfabetice. Se compara cele doua containere element cu element pâna c 21321r177v ând se întâlneste un element într-un container care nu este egal cu elementul corespunzator din celalalt container. În acest caz, containerele sunt considerate în aceeasi ordine ca si perechea de elemente diferite. De exemplu, daca doua containere sunt identice pâna la al zecelea element, dar al unsprezecelea element din primul container este mai mic decât al unsprezecelea element din al doilea container, primul container îl precede pe al doilea. Daca doua containere sunt egale pâna când unul nu mai are elemente, containerul mai scurt îl precede pe cel mai lung.
Membri aditionali pentru vectori, liste si cozi cu doua capete
Vectorii, listele si cozile cu doua capete sunt secvente si asigura metodele listate în Tabelul G.3. Din nou, X este un tip container, cum ar fi vector<int>, iar T este tipul stocat în container, cum ar fi int a este o valoare de tip X t este o valoare de tip X::value_type i si j sunt iteratori de intrare, q2 si p sunt iteratori, q si q1 sunt iteratori care pot fi dereferentiati (le puteti aplica operatorul ), iar n este un întreg de tip X::size_type
Tabelul G.3 Metode definite pentru vectori, liste si cozi cu doua capete.
Metoda Descriere
a.insert(p,t) Insereaza o copie a lui t înainte de p; returneaza un iterator care indica copia
inserata a lui t. Valoarea prestabilita pentru t este T() adica valoarea folosita
pentru tipul T daca nu este initializat explicit.
a.insert(p,n,t)Insereaza n copii ale lui t înainte de p; nu returneaza nici o valoare.
a.insert(p,i,j)Insereaza copiile elementelor din intervalul [i j) înainte de p; nu returneaza
nici o valoare.
a.resize(n,t) Daca n > a.size(), insereaza n - a.size() copii ale lui t înainte de
a.end(); valoarea prestabilita pentru t este T() adica valoarea folosita
pentru tipul T daca nu este initializat explicit. Daca n < a.size(), atunci
elementele de dupa elementul n sunt sterse.
a.assign(i,j) Înlocuieste continutul curent al lui a cu copiile elementelor din intervalul
[i j
a.assign(n,t) Înlocuieste continutul curent al lui a cu n copii ale lui t. Valoarea prestabilita
pentru t este T() adica valoarea folosita pentru tipul T daca nu este initializat
explicit.
a.erase(q) sterge elementul indicat de q; returneaza un iterator la elementul care era
înaintea lui q
a.erase(q1,q2) sterge elementele din intervalul [q1 q2); returneaza un iterator care indica
elementul care era indicat de q2
a.clear() La fel cu erase(a.begin(), a.end())
a.front() Returneaza *a.begin() (primul element).
a.back() Returneaza *--a.end() (ultimul element).
a.push_back(t) Insereaza t înainte de a.end()
a.pop_back() sterge ultimul element.
Tabelul G.4 listeaza metodele care sunt comune pentru doua din cele trei clase secventa.
Tabelul G.4 Metode definite pentru unele secvente.
Metoda Descriere Container
a.push_front(t)Insereaza o copie a lui t înainte de primul element. list deque
a.pop_front() sterge primul element. list deque
a[n] Returneaza *(a.begin() + n) vector deque
a.at(n) Returneaza *(a.begin() + n), arunca o exceptie vector deque
out_of_range daca n > a.size()
sablonul list mai asigura în plus metodele din Tabelul G.5. Aici a si b sunt containere list, iar T este tipul stocat în lista, cum ar fi int t este o valoare de tip T i si j sunt iteratori de intrare, q2 si p sunt iteratori, q si q1 sunt iteratori care pot fi dereferentiati, iar n este un întreg de tip X::size_type. Tabelul foloseste notatia STL [i j) pentru intervalul de la i pâna la j, fara a-l include pe acesta din urma.
Tabelul G.5 Metode suplimentare pentru liste.
Metoda Descriere
a.splice(p,b) Muta continutul listei b în lista a, inserându-l înaintea lui p
a.splice(p,b,i) Muta elementul din lista b indicat de i înaintea pozitiei p din
lista a
a.splice(p,b,i,j) Muta elementele din intervalul [i j) al listei b înaintea pozitiei
p din lista a
a.remove(const T& t) sterge toate elementele din lista a care au valoarea t
a.remove_if(Predicate pred)Daca i este un iterator în lista a, sterge toate valorile pentru
care pred(*i) este adevarat. (Un predicat este o functie sau
un functor boolean, vezi Capitolul 15.)
a.unique() sterge toate elementele dintr-un grup de elemente consecutive
egale, în afara de primul.
a.unique sterge toate elementele dintr-un grup de elemente consecutive
(BinaryPredicate bin_pred)pentru care bin_pred(*i,*(i-1)) este adevarat, în
afara de primul. (Un predicat binar este o functie sau un functor
boolean, vezi Capitolul 15.)
a.merge(b) Uneste listele a si b utilizând operatorul < definit pentru tipul
stocat. Daca un element din a este echivalent cu un element
din b, elementul din a este plasat primul. Lista b ramâne
goala dupa unire.
a.merge(b, Compare comp) Uneste listele a si b utilizând functia sau obiectul functie
comp. Daca un element din a este echivalent cu un element
din b, elementul din a este plasat primul. Lista b ramâne
goala dupa unire.
a.sort() Sorteaza lista a folosind operatorul <
a.sort(Compare comp) Sorteaza lista a folosind functia sau obiectul functie comp
a.reverse() Inverseaza ordinea elementelor din lista a
Membri aditionali pentru containerele set si map
Containerele asociative, cum sunt set si map, au un parametru sablon Key (cheie) si un parametru sablon Compare, care indica tipul cheii folosite la ordonarea elementelor si, respectiv, un obiect functie, numit obiect comparator, folosit la compararea valorilor cheilor. Pentru containerele set si multiset, cheile sunt chiar valorile stocate, deci tipul cheii este acelasi cu tipul valorii. Pentru containerele map si multimap, valorile stocate de un anumit tip (parametrul sablon T) sunt asociate cu un tip de cheie (parametrul sablon Key), iar tipul valorii este pair<const Key, T>. Containerele asociative includ membri aditionali care descriu aceste caracteristici, asa cum puteti vedea în Tabelul G.6.
Tabelul G.6 Tipuri definite pentru containere asociative.
Tip Valoare
X::key_type Key, tipul cheii
X::key_compare Compare, care are valoarea prestabilita less<key_type>
X::value_compare Un tip predicat binar, care este identic cu key_compare pentru set
si multiset si care permite ordonarea valorilor
pair<const Key, T> pentru map si multimap
X::mapped_type T, tipul datelor asociate (numai pentru map si multimap
Containerele asociative asigura metodele listate în Tabelul G.7. În general, obiectul comparator nu cere ca valorile cu aceeasi cheie sa fie identice; termenul echivalente în cheie înseamna ca doua valori, care pot fi sau nu egale, au aceeasi cheie. În tabel X este o clasa container, a este un obiect de tip X. Daca X foloseste chei unice (adica este set sau map a_uniq este un obiect de tip X. Daca X foloseste chei multiple (adica este multiset sau multimap a_eq este un obiect de tip X. Ca mai înainte, i si j sunt iteratori de intrare ce se refera la valori value_type i j) este un interval valid, q2 si p sunt iteratori ai a q si q1 sunt iteratori care pot fi dereferentiati, [q1 q2) este un interval valid, t este o valoare de tip X::value_type (care poate fi pereche). De asemenea, k este o valoare de tip X::key_type
Tabelul G.7 Metode definite pentru containere set multiset map si multimap
Metoda Descriere
a.key_comp() Returneaza obiectul comparator folosit la constructia lui a
a.value_comp() Returneaza un obiect de tip value_compare
a_uniq.insert(t) Insereaza valoarea t în containerul a, daca si numai daca a nu contine
deja o valoare cu o cheie echivalenta. Metoda returneaza o valoare de tip
pair<iterator, bool>. Componenta bool este true daca
inserarea a avut loc si false în caz contrar. Componenta iterator
indica elementul a carui cheie este echivalenta cu cheia lui t
a_eq.insert(t) Insereaza t si returneaza un iterator care îi indica locatia.
a.insert(p,t) Insereaza t folosind p ca indicatie a pozitiei din care insert() ar
trebui sa înceapa cautarea. Daca a este un container cu cheie unica,
atunci inserarea are loc daca si numai daca a nu contine un element cu
cheie echivalenta; în caz contrar insertia are loc. Metoda returneaza un
iterator care indica locatia cu cheie echivalenta, indiferent daca inserarea
a avut loc sau nu.
a.insert(i,j) Insereaza elementele din intervalul [i j) în a
a.erase(k) sterge toate elementele din a care au o cheie echivalenta cu k si
returneaza numarul de elemente sterse.
a.erase(q) sterge elementul indicat de q
a.erase(q1,q2) sterge elementele din intervalul [q1 q2
a.clear() Identic cu erase(a.begin(), a.end())
a.find(k) Returneaza un iterator care indica un element cu cheie echivalenta cu k
returneaza a.end() daca nu se gaseste un astfel de element.
a.count(k) Returneaza numarul de elemente care au cheia echivalenta cu k
a.lower_bound(k) Returneaza un iterator care indica primul element care are o cheie care
nu este mai mica decât k
a.upper_bound(k) Returneaza un iterator care indica primul element care are o cheie care
este mai mare decât k
a.equal_range(k) Returneaza o pereche a carei prim membru este
a.lower_bound(k), iar al doilea membru este
a.upper_bound(k)
a.operator[](k) Returneaza o referinta la valoarea asociata cu cheia k (numai la
containere map
Functii STL
Biblioteca de algoritmi STL continuta în fisierele antet algorithm si numeric, furnizeaza un numar mare de functii sablon, bazate pe iteratori, care nu sunt functii membre ale claselor. Dupa cum am spus în Capitolul 15, numele parametrilor sablon sunt alese astfel încât sa indice conceptul modelat de parametrul respectiv. De exemplu, ForwardIterator este utilizat pentru a indica faptul ca un parametru ar trebui sa satisfaca cel putin cerintele unui iterator de înaintare, iar Predicate este folosit pentru a indica faptul ca un parametru trebuie sa fie un obiect functie care primeste un singur argument si returneaza o valoare bool. Standardul împarte algoritmii în patru grupe: operatii care nu modifica secventa, operatii care modifica secventa, sortare si operatori înruditi si operatii numerice. Termenul operatie secventiala arata ca functia primeste ca argumente o pereche de iteratori ce definesc un interval, adica o secventa, asupra caruia se va face operatia. Modifica înseamna ca functia poate schimba containerul.
Operatii care nu modifica secventa
Tabelul G.8 rezuma operatiile care nu modifica secventa. Argumentele nu sunt prezentate, iar functiile supraîncarcate sunt listate doar o singura data. O descriere mai detaliata, incluzând prototipurile, urmeaza dupa tabel. Astfel, puteti consulta tabelul pentru a avea o idee despre actiunea unei functii, iar apoi, daca vi se pare ca functia este utila, cautati detaliile.
Tabelul G.8 Operatii care nu modifica secventa.
Functie Descriere
for_each() Aplica un obiect functie fiecarui element dintr-un interval, fara a-l modifica.
find() Gaseste prima aparitie a unei valori într-un interval.
find_if() Gaseste prima valoare dintr-un interval, care satisface criteriul unui predicat.
find_end() Gaseste ultima aparitie a unei subsecvente ale carei valori se potrivesc cu
valorile unei alte secvente. Valorile se potrivesc daca sunt egale sau daca
satisfac un predicat binar.
find_first_of()Gaseste prima aparitie a oricarui element dintr-o a doua secventa care se
potriveste cu o valoare din prima secventa. Valorile se potrivesc daca sunt
egale sau daca satisfac un predicat binar.
adjacent_find()Gaseste primul element care se potriveste cu elementul imediat urmator.
Valorile se potrivesc daca sunt egale sau daca satisfac un predicat binar.
count() Returneaza numarul de aparitii a unei valori date într-un interval.
count_if() Returneaza numarul de potriviri ale unei valori date cu valorile dintr-un
interval, potrivirea se determina utilizând un predicat binar.
mismatch() Gaseste primul element dintr-un interval care nu se potriveste cu elementul
corespunzator dintr-un al doilea interval si returneaza iteratori care indica
ambele elemente. Valorile se potrivesc daca sunt egale sau daca satisfac un
predicat binar.
equal() Returneaza true daca fiecare element dintr-un interval se potriveste cu
elementul corespunzator dintr-un al doilea interval. Valorile se potrivesc daca
sunt egale sau daca satisfac un predicat binar.
search() Gaseste prima aparitie a unei subsecvente ale carei valori se potrivesc cu
valorile unei a doua secvente. Valorile se potrivesc daca sunt egale sau daca
satisfac un predicat binar.
search_n() Gaseste prima subsecventa de n elemente fiecare potrivindu-se cu o valoare
data. Valorile se potrivesc daca sunt egale sau daca satisfac un predicat binar.
Acum, sa studiem prototipurile. Perechile de iteratori indica intervale, numele parametrului sablon indicând tipul iteratorului. Ca de obicei, un interval de forma [first last) contine elementele de la first pâna la last, fara a-l include si pe acesta din urma. Unele functii primesc ca argumente doua intervale care nu trebuie neaparat sa fie în acelasi tip de container. De exemplu, puteti folosi equal() pentru a compara o lista cu un vector. Functiile transferate ca argumente sunt obiecte functie, care pot fi pointeri (numele de functii sunt asa ceva) sau obiecte pentru care operatia este definita. Ca în Capitolul 15, un predicat este o functie booleana cu un argument, iar un predicat binar este o functie booleana cu doua argumente. (Functiile nu trebuie sa returneze neaparat valori bool dar sa returneze valoarea 0 pentru fals si o valoare nenula pentru adevarat.)
template<class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last,
Function f);
Functia for_each() aplica obiectul functie f fiecarui element din intervalul [first last). Returneaza f
template<class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last,
const T& value);
Functia find() returneaza un iterator la primul element din intervalul [first last) care are valoarea value
template<class InputIterator, class Predicate>
InputIterator find_if(InputIterator first, InputIterator last,
Predicate pred);
Functia find_if() returneaza un iterator it la primul element din intervalul [first last), pentru care apelul obiectului functie pred(*it) este adevarat.
template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_end(ForwardIterator1 first1,
ForwardIterator1 last1, ForwardIterator2 first2,
ForwardIterator2 last2);
template<class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
ForwardIterator1 find_end(ForwardIterator1 first1,
ForwardIterator1 last1, ForwardIterator2 first2,
ForwardIterator2 last2, BinaryPredicate pred);
Functia find_end() returneaza un iterator it la ultimul element din intervalul [first1 last1), care marcheaza începutul unei subsecvente care se potriveste cu continutul intervalului [first2 last2). Prima versiune utilizeaza pentru comparare operatorul definit pentru tipul stocat în container. A doua versiune utilizeaza pentru compararea elementelor obiectul functie predicat binar pred. Adica, elementele indicate de it1 si it2 se potrivesc daca pred(*it1, *it2) este adevarat.
template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_first_of(ForwardIterator1 first1,
ForwardIterator1 last1, ForwardIterator2 first2,
ForwardIterator2 last2);
template<class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
ForwardIterator1 find_first_of(ForwardIterator1 first1,
ForwardIterator1 last1, ForwardIterator2 first2,
ForwardIterator2 last2, BinaryPredicate pred);
Functia find_first_of() returneaza un iterator it la primul element din intervalul [first1 last1), care se potriveste cu oricare element din intervalul [first2 last2). Prima versiune utilizeaza pentru comparare operatorul definit pentru tipul stocat în container. A doua versiune utilizeaza pentru compararea elementelor obiectul functie predicat binar pred. Adica, elementele indicate de it1 si it2 se potrivesc daca pred(*it1, *it2) este adevarat.
template<class ForwardIterator>
ForwardIterator adjacent_find(ForwardIterator first,
ForwardIterator last);
template<class ForwardIterator, class BinaryPredicate>
ForwardIterator adjacent_find(ForwardIterator first,
ForwardIterator last, BinaryPredicate pred);
Functia adjacent_find() returneaza un iterator it la primul element din intervalul [first1 last1) (N.T.: Trebuie [first last care se potriveste cu elementul imediat urmator. Functia returneaza last daca nu s-a gasit o astfel de pereche. Prima versiune utilizeaza pentru comparare operatorul definit pentru tipul stocat în container. A doua versiune utilizeaza pentru compararea elementelor obiectul functie predicat binar pred. Adica, elementele indicate de it1 si it2 se potrivesc daca pred(*it1, *it2) este adevarat.
template<class InputIterator, class T>
iterator_traits<InputIterator>::difference_type count(
InputIterator first, InputIterator last, const T& value);
Functia count() returneaza numarul de elemente din intervalul [first last) care se potrivesc cu valoarea value. Pentru compararea valorilor se foloseste operatorul definit pentru tipul stocat. Tipul returnat este un tip întreg suficient de mare pentru a putea contine numarul maxim de elemente care pot fi stocate într-un container.
template<class InputIterator, class Predicate>
iterator_traits<InputIterator>::difference_type count_if(
InputIterator first, InputIterator last, Predicate pred);
Functia count_if() returneaza numarul de elemente din intervalul [first last) pentru care obiectul functie pred returneaza o valoare adevarata când primeste elementul ca argument.
template<class InputIterator1, class InputIterator2>
pair<InputIterator1, InputIterator2> mismatch(
InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2);
template<class InputIterator1, class InputIterator2,
class BinaryPredicate>
pair<InputIterator1, InputIterator2> mismatch(
InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, BinaryPredicate pred);
Functia mismatch() gaseste primul element din intervalul [first1 last1) care nu se potriveste cu elementul corespunzator din intervalul care începe cu first2 si returneaza o pereche care pastreaza iteratorii ce indica cele doua elemente care nu se potrivesc. Daca nu se gaseste nici o nepotrivire valoarea returnata este pair<last1, first2 + (last1 - first1)>. Prima versiune utilizeaza pentru comparare operatorul . A doua versiune utilizeaza pentru compararea elementelor obiectul functie predicat binar pred. Adica, elementele indicate de it1 si it2 se potrivesc daca pred(*it1, *it2) este adevarat.
template<class InputIterator1, class InputIterator2>
bool equal(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2);
template<class InputIterator1, class InputIterator2,
class BinaryPredicate>
bool equal(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, BinaryPredicate pred);
Functia equal() returneaza true daca fiecare element din intervalul [first1 last1) se potriveste cu elementul corespunzator din secventa care începe cu first2 si false în caz contrar. Prima versiune utilizeaza pentru comparare operatorul definit pentru tipul stocat în container. A doua versiune utilizeaza pentru compararea elementelor obiectul functie predicat binar pred. Adica, elementele indicate de it1 si it2 se potrivesc daca pred(*it1, *it2) este adevarat.
template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search(ForwardIterator1 first1,
ForwardIterator1 last1, ForwardIterator2 first2,
ForwardIterator2 last2);
template<class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate>
ForwardIterator1 search(ForwardIterator1 first1,
ForwardIterator1 last1, ForwardIterator2 first2,
ForwardIterator2 last2, BinaryPredicate pred);
Functia search() gaseste prima aparitie din intervalul [first1 last1), care se potriveste cu secventa corespunzatoare din intervalul [first2 last2). Returneaza last1 daca nu gaseste nici o astfel de secventa. Prima versiune utilizeaza pentru comparare operatorul definit pentru tipul stocat în container. A doua versiune utilizeaza pentru compararea elementelor obiectul functie predicat binar pred. Adica, elementele indicate de it1 si it2 se potrivesc daca pred(*it1, *it2) este adevarat.
template<class ForwardIterator, class Size, class T>
ForwardIterator search_n(ForwardIterator first,
ForwardIterator last, Size count, const T& value);
template<class ForwardIterator, class Size, class T,
class BinaryPredicate>
ForwardIterator search_n(ForwardIterator first,
ForwardIterator last, Size count, const T& value,
BinaryPredicate pred);
Functia search_n() gaseste prima aparitie din intervalul [first1 last1), care se potriveste cu secventa alcatuita din count aparitii consecutive ale lui value. Returneaza last1 daca nu gaseste nici o astfel de secventa. Prima versiune utilizeaza pentru comparare operatorul definit pentru tipul stocat în container. A doua versiune utilizeaza pentru compararea elementelor obiectul functie predicat binar pred. Adica, elementele indicate de it1 si it2 se potrivesc daca pred(*it1, *it2) este adevarat.
Operatii care modifica secventa
Tabelul G.9 rezuma operatiile care modifica secventa. Argumentele nu sunt prezentate, iar functiile supraîncarcate sunt listate doar o singura data. O descriere mai detaliata, incluzând prototipurile, urmeaza dupa tabel. Astfel, puteti consulta tabelul pentru a avea o idee despre actiunea unei functii, iar apoi, daca vi se pare ca functia este utila, cautati detaliile.
Tabelul G.9 Operatii care modifica secventa.
Functie Descriere
copy() Copiaza elemente dintr-un interval la o locatie indicata de un iterator.
copy_backward()Copiaza elemente dintr-un interval la o locatie indicata de un iterator.
Copierea începe la sfârsitul intervalului si merge spre început.
swap() Schimba între ele doua valori stocate la locatii specificate prin referinte.
swap_ranges() Schimba între ele valorile corespondente din doua intervale.
iter_swap() Schimba între ele doua valori stocate la locatii specificate prin iteratori.
transform() Aplica un obiect functie fiecarui element dintr-un interval (sau fiecarei
perechi de elemente dintr-o pereche de intervale), copiind valoarea returnata
la o locatie din alt interval.
replace() Înlocuieste fiecare aparitie a unei valori dintr-un interval cu o alta valoare.
replace_if() Înlocuieste fiecare aparitie a unei valori dintr-un interval cu o alta valoare,
daca un predicat aplicat valorii originale returneaza true
replace_copy() Copiaza un interval în altul, înlocuind fiecare aparitie a unei valori cu o alta
valoare.
replace_copy_if()Copiaza un interval în altul, înlocuind fiecare valoare pentru care un predicat
returneaza true, cu o alta valoare.
fill() Seteaza fiecare valoare dintr-un interval la valoarea indicata.
fill_n() Seteaza n elemente consecutive la o valoare data.
generate() Seteaza fiecare valoare dintr-un interval la valoarea returnata de un generator,
care este un obiect functie care nu primeste argumente.
generate_n() Seteaza primele n valori dintr-un interval la valoarea returnata de un
generator, care este un obiect functie care nu primeste argumente.
remove() Elimina toate aparitiile unei valori indicate dintr-un interval si returneaza un
iterator dincolo-de-sfârsit pentru intervalul rezultat.
remove_if() Elimina dintr-un interval toate aparitiile unor valori pentru care un obiect
predicat returneaza true si returneaza un iterator dincolo-de-sfârsit pentru
intervalul rezultat.
remove_copy() Copiaza elementele dintr-un interval în altul, omitând elementele egale cu o
valoare specificata.
remove_copy_if()Copiaza elementele dintr-un interval în altul, omitând elementele pentru care
un obiect predicat returneaza true
unique() Reduce fiecare secventa de doua sau mai multe elemente echivalente dintr-un
interval la un singur element.
unique_copy() Copiaza elementele dintr-un interval în altul, reducând fiecare secventa de
doua sau mai multe elemente echivalente la unul singur.
reverse() Inverseaza elementele dintr-un interval.
reverse_copy() Copiaza un interval, în al doilea interval, în ordine inversa.
rotate() Considera intervalul ordonat circular si roteste elementele la stânga.
rotate_copy() Copiaza un interval în altul într-o ordine ciclica.
random_shuffle()Rearanjeaza aleator elementele dintr-un interval.
partition() Plaseaza toate elementele care satisfac un obiect predicat înaintea tuturor
elementelor care nu îl satisfac.
stable_partition()Plaseaza toate elementele care satisfac un obiect predicat înaintea tuturor
elementelor care nu îl satisfac. Ordinea relativa a elementelor din fiecare grup
este pastrata.
Acum, sa vedem prototipurile. Cum am vazut mai înainte, perechile de iteratori indica intervale, numele parametrului sablon indicând tipul iteratorului. Ca de obicei, un interval de forma [first last) contine elementele de la first pâna la last, fara a-l include si pe acesta din urma. Functiile transferate ca argumente sunt obiecte functie, care pot fi pointeri la functii sau obiecte pentru care operatia este definita. Ca în Capitolul 15, un predicat este o functie booleana cu un argument, iar un predicat binar este o functie booleana cu doua argumente. (Functiile nu trebuie sa returneze neaparat valori bool dar sa returneze valoarea 0 pentru fals si o valoare nenula pentru adevarat.) De asemenea, ca în Capitolul 15, un obiect functie unara primeste un singur argument, iar un obiect functie binara primeste doua argumente.
template<class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, InputIterator last,
OutputIterator result)
Functia copy() copiaza elementele din intervalul [first last) în intervalul [result result + (last - first)). Returneaza result + (last - first), adica un iterator care indica pozitia imediat urmatoare ultimei locatii în care s-a copiat. Functia cere ca result sa nu fie în intervalul [first last), adica destinatia nu se poate suprapune cu sursa.
template<class BidirectionalIterator1,
class BidirectionalIterator2>
BidirectionalIterator2 copy_backward(BidirectionalIterator1 first,
BidirectionalIterator1 last, BidirectionalIterator2 result)
Functia copy_backward() copiaza elementele din intervalul [first last) în intervalul [result - (last - first) result). Copierea începe cu elementul din pozitia last - 1, care este copiat la locatia result - 1, si continua în sens invers spre first. Returneaza result - (last - first), adica un iterator care indica pozitia imediat urmatoare ultimei locatii în care s-a copiat. Functia cere ca result sa nu fie în intervalul [first last). Totusi, deoarece copierea se face în sens invers, destinatia se poate suprapune cu sursa.
template<class T> void swap(T& a, T& b);
Functia swap() schimba între ele valorile stocate în doua locatii specificate prin referinte.
template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator2 swap_ranges(ForwardIterator1 first1,
ForwardIterator1 last1, ForwardIterator2 first2);
Functia swap_ranges() schimba valorile din intervalul [first1 last1) cu valorile corespunzatoare din intervalul care începe cu first2. Cele doua intervale nu pot sa se suprapuna.
template<class ForwardIterator1, class ForwardIterator2>
void iter_swap(ForwardIterator1 a, ForwardIterator2 b);
Functia iter_swap() schimba între ele valorile stocate în doua locatii specificate prin iteratori.
template<class InputIterator, class OutputIterator,
class UnaryOperation>
OutputIterator transform(InputIterator first, InputIterator last,
OutputIterator result, UnaryOperation op);
Aceasta versiune a lui transform() aplica obiectul functie unara op fiecarui element din intervalul [first last) si atribuie valoarea returnata elementului corespunzator din intervalul care începe cu result. Prin urmare *result este setat la valoarea op(*first), si asa mai departe. Returneaza result + (last - first), adica valoarea dincolo-de-sfârsit pentru intervalul destinatie.
template<class InputIterator1, class InputIterator2,
class OutputIterator, class BinaryOperation>
OutputIterator transform(InputIterator1 first1,
InputIterator1 last1, InputIterator2 first2,
OutputIterator result, BinaryOperation binary_op);
Aceasta versiune a lui transform() aplica obiectul functie binara op (N.T.: Trebuie binary_op fiecarui element din intervalul [first1 last1) si fiecarui element din intervalul [first2 last2) (N.T.: Trebuie: intervalul care începe cu first2 si atribuie valoarea returnata elementului corespunzator din intervalul care începe cu result. Prin urmare *result este setat la valoarea op(*first1, *first2) (N.T.: Trebuie binary_op(*first1, *first2) , si asa mai departe. Returneaza result + (last - first) (N.T.: Trebuie result + (last1 - first1) , adica valoarea dincolo-de-sfârsit pentru intervalul destinatie.
template<class ForwardIterator, class T>
void replace(ForwardIterator first, ForwardIterator last,
const T& old_value, const T& new_value);
Functia replace() înlocuieste fiecare aparitie a valorii old_value din intervalul [first last) cu valoarea new_value
template<class ForwardIterator, class Predicate, class T>
void replace_if(ForwardIterator first, ForwardIterator last,
Predicate pred, const T& new_value);
Functia replace_if() înlocuieste fiecare valoare old din intervalul [first last), pentru care pred(old) este adevarat, cu valoarea new_value
template<class InputIterator, class OutputIterator, class T>
OutputIterator replace_copy(InputIterator first,
InputIterator last, OutputIterator result,
const T& old_value, const T& new_value)
Functia replace_copy() copiaza elementele din intervalul [first last) în intervalul care începe cu result, dar înlocuind fiecare aparitie a old_value cu new_value. Returneaza result + (last - first), adica valoarea dincolo-de-sfârsit pentru intervalul destinatie.
template<class InputIterator, class OutputIterator,
class Predicate, class T>
OutputIterator replace_copy_if(InputIterator first,
InputIterator last, OutputIterator result, Predicate pred,
const T& new_value)
Functia replace_copy_if() copiaza elementele din intervalul [first last) în intervalul care începe cu result, dar înlocuind fiecare valoare old pentru care pred(old) este adevarat, cu new_value. Returneaza result + (last - first), adica valoarea dincolo-de-sfârsit pentru intervalul destinatie.
template<class ForwardIterator, class T>
void fill(ForwardIterator first, ForwardIterator last,
const T& value);
Functia fill() seteaza fiecare element din intervalul [first last) la value
template<class OutputIterator, class Size, class T>
void fill_n(OutputIterator first, Size n, const T& value);
Functia fill_n() seteaza primele n elemente începând de la locatia first la value
template<class ForwardIterator, class Generator>
void generate(ForwardIterator first, ForwardIterator last,
Generator g);
Functia generator() (N.T.: Trebuie generate() seteaza fiecare element din intervalul [first last) la gen(), unde gen este un obiect functie generator, adica unul care nu ia nici un argument. De exemplu, gen poate fi un pointer la rand()
template<class OutputIterator, class Size, class Generator>
void generate_n(OutputIterator first, Size n, Generator gen);
Functia generator_n() (N.T.: Trebuie generate_n() seteaza primele n elemente începând de la locatia first la gen(), unde gen este un obiect functie generator, adica unul care nu ia nici un argument. De exemplu, gen poate fi un pointer la rand()
template<class ForwardIterator, class T>
ForwardIterator remove(ForwardIterator first,
ForwardIterator last, const T& value);
Functia remove() elimina toate aparitiile lui value din intervalul [first last) si returneaza un iterator care indica dincolo-de-sfârsit pentru intervalul rezultat. Functia este stabila, adica ordinea elementelor ramase nu este modificata.
Nota
Deoarece diversele variante ale functiilor remove() si unique() nu sunt functii membre si nici nu sunt limitate doar la containerele STL, acestea nu pot sa modifice dimensiunea containerului. În schimb, ele returneaza un iterator care indica noua locatie dincolo-de-sfârsit. De obicei, elementele eliminate sunt pur si simplu deplasate la sfârsitul containerului. Totusi, pentru containerele STL puteti folosi iteratorul returnat si una din metodele erase() pentru a reseta end()
template<class ForwardIterator, class Predicate>
ForwardIterator remove_if(ForwardIterator first,
ForwardIterator last, Predicate pred);
Functia remove_if() elimina, din intervalul [first last), toate aparitiile lui val pentru care pred(val) este adevarat si returneaza un iterator dincolo-de-sfârsit pentru intervalul rezultat. Functia este stabila, adica ordinea elementelor ramase nu este modificata.
template<class InputIterator, class OutputIterator, class T>
OutputIterator remove_copy(InputIterator first,
InputIterator last, OutputIterator result, const T& value);
Functia remove_copy() copiaza valorile din intervalul [first last) în intervalul care începe cu result, sarind peste aparitiile lui value. Returneaza un iterator dincolo-de-sfârsit pentru intervalul destinatie. Functia este stabila, adica ordinea elementelor ramase nu este modificata.
template<class InputIterator, class OutputIterator,
class Predicate>
OutputIterator remove_copy_if(InputIterator first,
InputIterator last, OutputIterator result, Predicate pred);
Functia remove_copy_if() copiaza valorile din intervalul [first last) în intervalul care începe cu result, sarind peste aparitiile lui val, pentru care pred(val) este adevarat. Returneaza un iterator dincolo-de-sfârsit pentru intervalul destinatie. Functia este stabila, adica ordinea elementelor ramase nu este modificata.
template<class ForwardIterator>
ForwardIterator unique(ForwardIterator first,
ForwardIterator last);
template<class ForwardIterator, class BinaryPredicate>
ForwardIterator unique(ForwardIterator first,
ForwardIterator last, BinaryPredicate pred);
Functia unique() reduce fiecare secventa de doua sau mai multe elemente echivalente din intervalul [first last) la un singur element si returneaza un iterator dincolo-de-sfârsit pentru noul interval. Prima versiune utilizeaza pentru comparare operatorul definit pentru tipul stocat în container. A doua versiune utilizeaza pentru compararea elementelor obiectul functie predicat binar pred. Adica, elementele indicate de it1 si it2 se potrivesc daca pred(*it1, *it2) este adevarat.
template<class InputIterator, class OutputIterator>
OutputIterator unique_copy(InputIterator first,
InputIterator last, OutputIterator result);
template<class InputIterator, class OutputIterator,
class BinaryPredicate>
OutputIterator unique_copy(InputIterator first,
InputIterator last, OutputIterator result,
BinaryPredicate pred);
Functia unique_copy() copiaza elementele din intervalul [first last) în intervalul care începe cu result, reducând fiecare secventa de doua sau mai multe elemente identice la un singur element. Returneaza un iterator dincolo-de-sfârsit pentru noul interval. Prima versiune utilizeaza pentru comparare operatorul definit pentru tipul stocat în container. A doua versiune utilizeaza pentru compararea elementelor obiectul functie predicat binar pred. Adica, elementele indicate de it1 si it2 se potrivesc daca pred(*it1, *it2) este adevarat.
template<class BidirectionalIterator>
void reverse(BidirectionalIterator first,
BidirectionalIterator last);
Functia reverse() inverseaza elementele din intervalul [first last) apelând swap(first, last - 1), si asa mai departe.
template<class BidirectionalIterator, class OutputIterator>
OutputIterator reverse_copy(BidirectionalIterator first,
BidirectionalIterator last, OutputIterator result);
Functia reverse_copy() copiaza elementele din intervalul [first last) în intervalul care începe cu result în ordine inversa. Cele doua intervale nu pot sa se suprapuna.
template<class ForwardIterator>
void rotate(ForwardIterator first, ForwardIterator middle,
ForwardIterator last);
Functia rotate() realizeaza o rotatie la stânga a elementelor din intervalul [first last). Elementul din pozitia middle este mutat la first, elementul middle + 1 la first + 1, si asa mai departe. Elementele care îl preceda pe middle sunt mutate spre sfârsitul containerului, astfel încât elementul first urmeaza dupa elementul care era last - 1
template<class ForwardIterator, class OutputIterator>
OutputIterator rotate_copy(ForwardIterator first,
ForwardIterator middle, ForwardIterator last,
OutputIterator result);
Functia rotate_copy() copiaza elementele din intervalul [first last) în intervalul care începe cu result, utilizând secventa de rotatie descrisa pentru rotate()
template<class RandomAccessIterator>
void random_shuffle(RandomAccessIterator first,
RandomAccessIterator last);
Aceasta versiune a functiei random_shuffle() amesteca elementele din intervalul [first last). Distributia este uniforma; adica fiecare permutare posibila a ordinii originale are aceeasi probabilitate.
template<class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle(RandomAccessIterator first,
RandomAccessIterator last, RandomNumberGenerator& random);
Aceasta versiune a functiei random_shuffle() amesteca elementele din intervalul [first last). Obiectul functie random determina distributia. Având n elemente date, expresia random(n) trebuie sa returneze o valoare în intervalul [ n
template<class BidirectionalIterator, class Predicate>
BidirectionalIterator partition(BidirectionalIterator first,
BidirectionalIterator last, Predicate pred);
Functia partition() plaseaza fiecare element val, pentru care pred(val) este adevarat, înaintea tuturor elementelor care nu satisfac aceasta conditie. Returneaza un iterator care indica pozitia imediat urmatoare ultimei valori pentru care predicatul este adevarat.
template<class BidirectionalIterator, class Predicate>
BidirectionalIterator stable_partition(
BidirectionalIterator first, BidirectionalIterator last,
Predicate pred);
Functia stable_partition() plaseaza fiecare element val, pentru care pred(val) este adevarat, înaintea tuturor elementelor care nu satisfac aceasta conditie. Functia pastreaza ordinea relativa în fiecare grup. Returneaza un iterator care indica pozitia imediat urmatoare ultimei valori pentru care predicatul este adevarat.
Sortare si operatii înrudite
Tabelul G.10 rezuma sortarea si operatiile înrudite. Argumentele nu sunt prezentate, iar functiile supraîncarcate sunt listate doar o singura data. Fiecare functie are o versiune care foloseste < pentru ordonarea elementelor si o versiune care, în acelasi scop, foloseste un obiect functie de comparare. O descriere mai detaliata, incluzând prototipurile, urmeaza dupa tabel. Astfel, puteti consulta tabelul pentru a avea o idee despre actiunea unei functii, iar apoi, daca vi se pare ca functia este utila, cautati detaliile.
Tabelul G.10 Sortare si operatii înrudite.
Functie Descriere
sort() Sorteaza un interval.
stable_sort() Sorteaza un interval, pastrând ordinea relativa a elementelor
echivalente.
partial_sort() Sorteaza partial un interval, primele n elemente fiind sortate complet.
partial_sort_copy() Copiaza un interval sortat partial în alt interval.
nth_element() Fiind dat un iterator într-un interval, gaseste elementul care ar trebui
sa fie acolo daca intervalul ar fi sortat si plaseaza elementul acolo.
lower_bound() Fiind data o valoare, gaseste prima pozitie într-un interval sortat
înaintea careia valoarea poate fi inserata, pastrându-se ordinea.
upper_bound() Fiind data o valoare, gaseste ultima pozitie într-un interval sortat
înaintea careia valoarea poate fi inserata, pastrându-se ordinea.
equal_range() Fiind data o valoare, gaseste cel mai mare subinterval într-un interval
sortat, astfel încât valoarea sa poata fi inserata înaintea oricarui
element din subinterval, fara a modifica ordinea.
binary_search() Returneaza true daca un interval sortat contine o valoare echivalenta
cu o valoare data si false în caz contrar.
merge() Îmbina doua intervale sortate, într-un al treilea interval.
inplace_merge() Îmbina pe loc doua intervale sortate consecutive.
includes() Returneaza true daca toate elementele dintr-o multime exista si în
alta multime.
set_union() Construieste reuniunea a doua multimi, adica o multime care contine
toate elementele celor doua multimi.
set_intersection() Construieste intersectia a doua multimi, adica o multime care contine
doar elementele comune ale celor doua multimi.
set_difference() Construieste diferenta a doua multimi, adica o multime care contine
doar elementele care apartin primei multimi, dar nu si celei de a doua.
set_symmetric_difference() Construieste o multime alcatuita din elemente care
apartin unei multimi sau celeilalte dar nu exista în ambele.
make_heap() Converteste un interval într-un heap.
push_heap() Adauga un element într-un heap.
pop_heap() Extrage cel mai mare element din heap.
sort_heap() Sorteaza un heap.
min() Returneaza minimul a doua valori.
max() Returneaza maximul a doua valori.
min_element() Gaseste prima aparitie a celei mai mici valori dintr-un interval.
max_element() Gaseste prima aparitie a celei mai mari valori dintr-un interval.
lexicographic_compare() Compara doua secvente în mod lexicografic, returnând true
daca prima secventa este mai mica lexicografic decât cea de a doua si
false în caz contrar.
next_permutation() Genereaza urmatoarea permutare a unei secvente.
previous_permutation() Genereaza permutarea anterioara a unei secvente.
(N.T.: În linia de mai sus trebuie prev_permutation()
Functiile din aceasta sectiune determina ordinea elementelor utilizând operatorul < definit pentru elemente sau un obiect comparator desemnat prin tipul sablon Compare. Daca comp este un obiect de tip Compare, atunci comp(a, b) este o generalizare pentru a < b si returneaza true daca a este înaintea lui b în schema de ordonare. Daca atât a < b cât si b < a sunt false, atunci a si b sunt echivalente. Un obiect comparator trebuie sa furnizeze cel putin o relatie de ordine partiala. Asta înseamna ca:
Expresia comp(a, a) trebuie sa fie falsa, o generalizare a faptului ca o valoare nu poate fi mai mica decât ea însasi. (Aceasta este partea stricta.)
Daca comp(a, b) este adevarata si comp(b, c) este adevarata, atunci comp(a, c) este adevarata (adica comparatia este o relatie tranzitiva).
Daca a este echivalent cu b si b este echivalent cu c, atunci a este echivalent cu c (adica echivalenta este o relatie tranzitiva).
Daca va gânditi la aplicarea < la întregi, atunci echivalenta implica egalitate, dar acest lucru nu este neaparat adevarat în cazuri mai generale. De exemplu, puteti defini o structura cu mai multi membri care descrie o adresa postala si sa definiti un obiect comparator comp care ordoneaza structurile dupa codul postal. Atunci, oricare doua adrese cu acelasi cod postal sunt echivalente dar nu sunt egale.
Acum, sa vedem prototipurile. Vom împarti aceasta sectiune în mai multe subsectiuni. Cum am vazut mai înainte, perechile de iteratori indica intervale, numele parametrului sablon indicând tipul iteratorului. Ca de obicei, un interval de forma [first last) contine elementele de la first pâna la last, fara a-l include si pe acesta din urma. Functiile transferate ca argumente sunt obiecte functie, care pot fi pointeri sau obiecte pentru care operatia este definita. Ca în Capitolul 15, un predicat este o functie booleana cu un argument, iar un predicat binar este o functie booleana cu doua argumente. (Functiile nu trebuie sa returneze neaparat valori bool dar sa returneze valoarea 0 pentru fals si o valoare nenula pentru adevarat.) De asemenea, ca în Capitolul 15, un obiect functie unara primeste un singur argument, iar un obiect functie binara primeste doua argumente.
Sortare
Mai întâi sa examinam algoritmii de sortare.
template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
Functia sort() sorteaza intervalul [first last) în ordine crescatoare folosind pentru comparare operatorul < definit pentru tipul stocat în container. Pentru a determina ordinea, prima versiune foloseste < iar a doua foloseste obiectul comparator comp
template<class RandomAccessIterator>
void stable_sort(RandomAccessIterator first,
RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void stable_sort(RandomAccessIterator first,
RandomAccessIterator last, Compare comp);
Functia stable_sort() sorteaza intervalul [first last) pastrând ordinea relativa a elementelor echivalente. Pentru a determina ordinea, prima versiune foloseste < iar a doua foloseste obiectul comparator comp
template<class RandomAccessIterator>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle, RandomAccessIterator last,
Compare comp);
Functia partial_sort() sorteaza partial intervalul [first last). Primele middle - first elemente ale intervalului sortat sunt plasate în intervalul [first middle), iar elementele ramase nu sunt sortate. Pentru a determina ordinea, prima versiune foloseste < iar a doua foloseste obiectul comparator comp
template<class InputIterator, class RandomAccessIterator>
RandomAccessIterator partial_sort_copy(InputIterator first,
InputIterator last, RandomAccessIterator result_first,
RandomAccessIterator result_last);
template<class InputIterator, class RandomAccessIterator,
class Compare>
RandomAccessIterator partial_sort_copy(InputIterator first,
InputIterator last, RandomAccessIterator result_first,
RandomAccessIterator result_last, Compare comp);
Functia partial_sort_copy() copiaza primele n elemente din intervalul sortat [first last) în intervalul [result_first result_first + n). Valoarea lui n este minimul dintre last - first si result_last - result_first. Functia returneaza result_first + n. Pentru a determina ordinea, prima versiune foloseste < iar a doua foloseste obiectul comparator comp
template<class RandomAccessIterator>
void nth_element(RandomAccessIterator first,
RandomAccessIterator nth, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void nth_element(RandomAccessIterator first,
RandomAccessIterator nth, RandomAccessIterator last,
Compare comp);
Functia nth_element() gaseste elementul din intervalul [first last) care ar fi în pozitia nth daca intervalul ar fi sortat si plaseaza elementul la pozitia nth. Pentru a determina ordinea, prima versiune foloseste < iar a doua foloseste obiectul comparator comp
Cautare binara
Algoritmii din grupul cautarii binare presupun intervale sortate. Necesita doar un iterator de înaintare, dar sunt mai eficiente pentru iteratori cu acces aleator.
template<class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first,
ForwardIterator last, const T& value);
template<class ForwardIterator, class T, class Compare>
ForwardIterator lower_bound(ForwardIterator first,
ForwardIterator last, const T& value, Compare comp);
Functia lower_bound() gaseste prima pozitie din intervalul sortat [first last) înaintea careia poate fi inserat value fara a încalca ordinea. Returneaza un iterator care indica aceasta pozitie. Pentru a determina ordinea, prima versiune foloseste < iar a doua foloseste obiectul comparator comp
template<class ForwardIterator, class T>
ForwardIterator upper_bound(ForwardIterator first,
ForwardIterator last, const T& value);
template<class ForwardIterator, class T, class Compare>
ForwardIterator upper_bound(ForwardIterator first,
ForwardIterator last, const T& value, Compare comp);
Functia upper_bound() gaseste ultima pozitie din intervalul sortat [first last) înaintea careia poate fi inserat value fara a încalca ordinea. Returneaza un iterator care indica aceasta pozitie. Pentru a determina ordinea, prima versiune foloseste < iar a doua foloseste obiectul comparator comp
template<class ForwardIterator, class T>
pair<ForwardIterator, ForwardIterator> equal_range(
ForwardIterator first, ForwardIterator last, const T& value);
template<class ForwardIterator, class T, class Compare>
pair<ForwardIterator, ForwardIterator> equal_range(
ForwardIterator first, ForwardIterator last, const T& value,
Compare comp);
Functia equal_range() gaseste cel mai mare subinterval [it1 it2) în intervalul sortat [first last) astfel încât value poate fi inserat înaintea oricarui iterator din acest interval fara a încalca ordinea. Functia returneaza un obiect pair format din it1 si it2. Pentru a determina ordinea, prima versiune foloseste < iar a doua foloseste obiectul comparator comp
template<class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class T, class Compare>
bool binary_search(ForwardIterator first, ForwardIterator last,
const T& value, Compare comp);
Functia binary_search() returneaza true daca o valoare echivalenta cu value exista în intervalul sortat [first last) si false în caz contrar. Pentru a determina ordinea, prima versiune foloseste < iar a doua foloseste obiectul comparator comp
Nota
Retineti ca daca < este utilizat pentru ordonare, valorile a si b sunt echivalente daca atât a < b, cât si b < a sunt false. Pentru numere obisnuite echivalenta implica egalitatea, dar nu putem spune acelasi lucru pentru structuri sortate dupa un singur membru. Prin urmare, pot sa existe mai multe locatii unde poate fi inserata o valoare noua fara a modifica ordinea. Analog, daca obiectul comparator comp este folosit pentru ordonare, echivalenta presupune ca atât comp(a, b) cât si comp(b, a) sunt false. (Aceasta este o generalizare a afirmatiei ca a si b sunt echivalente daca a nu este mai mic decât b si b nu este mai mic decât a
Interclasare
Functiile de interclasare presupun ca intervalele sunt sortate.
template<class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator merge(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
Functia merge() îmbina elementele din intervalele sortate [first1 last1) si [first2 last2), plasând rezultatul în intervalul care începe cu result. Intervalul destinatie nu se poate suprapune cu celelalte doua intervale. Când se gasesc elemente echivalente în ambele intervale, cele din primul interval sunt plasate înaintea celor din al doilea interval. Valoarea returnata este un iterator dincolo-de-sfârsit pentru intervalul rezultat. Pentru a determina ordinea, prima versiune foloseste < iar a doua foloseste obiectul comparator comp
template<class BidirectionalIterator>
void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle, BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle, BidirectionalIterator last,
Compare comp);
Functia inplace_merge() îmbina doua intervale sortate consecutive - [first middle) si [middle last) - într-o singura secventa sortata, stocata în intervalul [first last). Elementele din primul interval vor fi plasate înaintea elementelor echivalente din al doilea interval. Pentru a determina ordinea, prima versiune foloseste < iar a doua foloseste obiectul comparator comp
Operatii pentru multimi
Operatiile pentru multimi functioneaza cu toate secventele sortate, inclusiv set si multiset. Pentru containere care pastreaza mai multe aparitii ale unei valori, cum ar fi multiset, definitiile sunt generalizate. O reuniune a doua containere multiset contine cel mai mare numar de aparitii a fiecarui element, iar o intersectie contine cel mai mic numar de aparitii a fiecarui element. De exemplu, sa presupunem ca obiectul multiset A contine sirul "mar" de sapte ori, iar obiectul multiset B contine acelasi sir de patru ori. Atunci, reuniunea lui A si B va contine sapte aparitii ale lui "mar" iar intersectia va contine patru aparitii.
template<class InputIterator1, class InputIterator2>
bool includes(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2);
template<class InputIterator1, class InputIterator2,
class Compare>
bool includes(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2, Compare comp);
Functia includes() returneaza true daca fiecare element din intervalul [first2 last2) se gaseste si în intervalul [first1 last1) si false în caz contrar. Pentru a determina ordinea, prima versiune foloseste < iar a doua foloseste obiectul comparator comp
template<class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator set_union(InputIterator1 first1,
InputIterator1 last1, InputIterator2 first2,
InputIterator2 last2, OutputIterator result);
template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator set_union(InputIterator1 first1,
InputIterator1 last1, InputIterator2 first2,
InputIterator2 last2, OutputIterator result, Compare comp);
Functia set_union() construieste o multime care este reuniunea intervalelor [first1 last1) si [first2 last2) si copiaza rezultatul la locatia indicata de result. Intervalul rezultat nu se poate suprapune cu intervalele originale. Functia returneaza un iterator dincolo-de-sfârsit pentru intervalul creat. Reuniunea este multimea care contine toate elementele gasite în fiecare sau în ambele multimi. Pentru a determina ordinea, prima versiune foloseste < iar a doua foloseste obiectul comparator comp
template<class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator set_intersection(InputIterator1 first1,
InputIterator1 last1, InputIterator2 first2,
InputIterator2 last2, OutputIterator result);
template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator set_intersection(InputIterator1 first1,
InputIterator1 last1, InputIterator2 first2,
InputIterator2 last2, OutputIterator result, Compare comp);
Functia set_intersection() construieste multimea care este intersectia intervalelor [first1 last1) si [first2 last2) si copiaza rezultatul la locatia indicata de result. Intervalul rezultat nu se poate suprapune cu intervalele originale. Functia returneaza un iterator dincolo-de-sfârsit pentru intervalul creat. Intersectia este multimea care contine elementele comune ambelor multimi. Pentru a determina ordinea, prima versiune foloseste < iar a doua foloseste obiectul comparator comp
template<class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator set_difference(InputIterator1 first1,
InputIterator1 last1, InputIterator2 first2,
InputIterator2 last2, OutputIterator result);
template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator set_difference(InputIterator1 first1,
InputIterator1 last1, InputIterator2 first2,
InputIterator2 last2, OutputIterator result, Compare comp);
Functia set_difference() construieste multimea care este diferenta intervalelor [first1 last1) si [first2 last2) si copiaza rezultatul la locatia indicata de result. Intervalul rezultat nu se poate suprapune cu intervalele originale. Functia returneaza un iterator dincolo-de-sfârsit pentru intervalul creat. Diferenta este multimea care contine elementele care exista în prima multime, dar nu si în a doua. Pentru a determina ordinea, prima versiune foloseste < iar a doua foloseste obiectul comparator comp
template<class InputIterator1, class InputIterator2,
class OutputIterator>
OutputIterator set_symmetric_difference(
InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template<class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator set_symmetric_difference(
InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
Functia set_symmetric_difference() construieste multimea care este diferenta simetrica a intervalelor [first1 last1) si [first2 last2) si copiaza rezultatul la locatia indicata de result. Intervalul rezultat nu se poate suprapune cu intervalele originale. Functia returneaza un iterator dincolo-de-sfârsit pentru intervalul creat. Diferenta simetrica este multimea care contine elementele existente în prima multime dar care nu exista în a doua si acele elemente care exista în a doua dar nu exista în prima. Este acelasi lucru cu diferenta dintre reuniune si intersectie. Pentru a determina ordinea, prima versiune foloseste < iar a doua foloseste obiectul comparator comp
Operatii pentru heap
Un heap este o structura de date uzuala care are proprietatea ca primul sau element este cel mai mare. De câte ori primul element este eliminat sau orice element este adaugat, heap-ul trebuie sa fie aranjat din nou pentru a pastra aceasta proprietate. Un heap este proiectat în asa fel încât aceste doua operatii sa se efectueze cât mai eficient.
template<class RandomAccessIterator>
void make_heap(RandomAccessIterator first,
RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void make_heap(RandomAccessIterator first,
RandomAccessIterator last, Compare comp);
Functia make_heap() creeaza un heap din intervalul [first last). Prima versiune foloseste < pentru a determina ordinea, iar a doua foloseste obiectul comparator comp
template<class RandomAccessIterator>
void push_heap(RandomAccessIterator first,
RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void push_heap(RandomAccessIterator first,
RandomAccessIterator last, Compare comp);
Functia push_heap() presupune ca intervalul [first last - 1) este într-adevar un heap si adauga valoarea de la locatia last - 1 (adica, cu o pozitie dupa heap-ul presupus) în heap, transformând [first last) într-un heap. Prima versiune foloseste < pentru a determina ordinea, iar a doua foloseste obiectul comparator comp
template<class RandomAccessIterator>
void pop_heap(RandomAccessIterator first,
RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void pop_heap(RandomAccessIterator first,
RandomAccessIterator last, Compare comp);
Functia pop_heap() presupune ca intervalul [first last) este într-adevar un heap. Schimba valoarea de la locatia last - 1 cu valoarea first, transformând astfel [first last - 1) într-un heap. Prima versiune foloseste < pentru a determina ordinea, iar a doua foloseste obiectul comparator comp
template<class RandomAccessIterator>
void sort_heap(RandomAccessIterator first,
RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void sort_heap(RandomAccessIterator first,
RandomAccessIterator last, Compare comp);
Functia sort_heap() presupune ca intervalul [first last) este într-adevar un heap si îl sorteaza. Prima versiune foloseste < pentru a determina ordinea, iar a doua foloseste obiectul comparator comp
Minime si maxime
Functiile de minim si maxim returneaza valorile minime si maxime pentru perechi de valori sau pentru secvente de valori.
template<class T>
const T& min(const T& a, const T& b);
template<class T, class Compare>
const T& min(const T& a, const T& b, Compare comp);
Functia min() returneaza minimul celor doua valori. Daca doua valori sunt echivalente, atunci o returneaza pe prima. Prima versiune foloseste < pentru a determina ordinea, iar a doua foloseste obiectul comparator comp
template<class T>
const T& max(const T& a, const T& b);
template<class T, class Compare>
const T& max(const T& a, const T& b, Compare comp);
Functia max() returneaza minimul celor doua valori (N.T.: Evident, trebuie maximul celor doua valori.). Daca doua valori sunt echivalente, atunci o returneaza pe prima. Prima versiune foloseste < pentru a determina ordinea, iar a doua foloseste obiectul comparator comp
template<class ForwardIterator>
ForwardIterator min_element(ForwardIterator first,
ForwardIterator last);
template<class ForwardIterator, class Compare>
ForwardIterator min_element(ForwardIterator first,
ForwardIterator last, Compare comp);
Functia min_element() returneaza primul iterator it din intervalul [first last) pentru care nici un element din interval nu este mai mic decât *it. Prima versiune foloseste < pentru a determina ordinea, iar a doua foloseste obiectul comparator comp
template<class ForwardIterator>
ForwardIterator max_element(ForwardIterator first,
ForwardIterator last);
template<class ForwardIterator, class Compare>
ForwardIterator max_element(ForwardIterator first,
ForwardIterator last, Compare comp);
Functia max_element() returneaza primul iterator it din intervalul [first last) pentru care nici un element din interval nu este mai mare decât *it. Prima versiune foloseste < pentru a determina ordinea, iar a doua foloseste obiectul comparator comp
template<class InputIterator1, class InputIterator2>
bool lexicographical_compare(InputIterator1 first1,
InputIterator1 last1, InputIterator2 first2,
InputIterator2 last2);
template<class InputIterator1, class InputIterator2,
class Compare>
bool lexicographical_compare(InputIterator1 first1,
InputIterator1 last1, InputIterator2 first2,
InputIterator2 last2, Compare comp);
Functia lexicographical_compare() returneaza true daca secventa de elemente din intervalul [first1 last1) este lexicografic mai mica decât secventa de elemente din intervalul [first2 last2) si false în caz contrar. Prin comparare lexicografica se compara primul element al unei secvente cu primul element al celei de a doua, adica se compara *first1 cu *first2. Daca *first1 este mai mic decât *first2, atunci functia returneaza true. Daca *first2 este mai mic decât *first1, atunci functia returneaza false. Daca cele doua sunt echivalente, atunci comparatia continua cu urmatorul element din fiecare secventa. Acest proces continua pâna în momentul în care doua elemente corespondente nu sunt echivalente sau pâna când se ajunge la sfârsitul unei secvente. Daca doua secvente sunt echivalente pâna la sfârsitul uneia dintre ele, atunci secventa mai scurta este mai mica. Daca doua secvente sunt echivalente si au aceeasi lungime, atunci nici una nu este mai mica deci functia returneaza false. Prima versiune foloseste < pentru a determina ordinea, iar a doua foloseste obiectul comparator comp. Compararea lexicografica este o generalizare a compararii alfabetice.
Permutari
O permutare a unei secvente este o reordonare a elementelor sale. De exemplu, o secventa de trei elemente are sase ordonari posibile, deoarece puteti alege trei elemente pentru prima pozitie, dupa aceasta alegere ramân doar doua optiuni pentru a doua si una pentru a treia. De exemplu, cele sase permutari ale cifrelor 1, 3 si 5 sunt urmatoarele (N.T.: Adica 1, 2 si 3.):
123 132 213 232 312 321 (N.T.: Adica,
În general, o secventa de n elemente are n * (n-1) * ... * 1, adica n! permutari posibile.
Functiile legate de permutari presupun ca multimea tuturor permutarilor posibile poate fi aranjata în ordine lexicografica, ca în exemplul celor sase permutari de mai sus. Aceasta înseamna în general ca exista o permutare anume înainte si dupa fiecare permutare. De exemplu, 213 este imediat înaintea lui 232 (N.T.: 231.), iar 312 urmeaza imediat. Totusi, prima permutare (123 din exemplu) nu are predecesor iar ultima permutare (321) nu are un succesor.
template<class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last, Compare comp);
Functia next_permutation() transforma secventa din intervalul [first last) în permutarea care urmeaza în ordine lexicografica. Daca aceasta exista, atunci functia returneaza true. Daca nu exista (adica intervalul contine ultima permutare în ordine lexicografica), atunci functia returneaza false si transforma intervalul în prima permutare în ordine lexicografica. Prima versiune foloseste < pentru a determina ordinea, iar a doua foloseste obiectul comparator comp
template<class BidirectionalIterator>
bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last, Compare comp);
Functia previous_permutation() (N.T.: Trebuie prev_permutation() transforma secventa din intervalul [first last) în permutarea anterioara în ordine lexicografica. Daca aceasta exista, atunci functia returneaza true. Daca nu exista (adica intervalul contine prima permutare în ordine lexicografica), atunci functia returneaza false si transforma intervalul în ultima permutare în ordine lexicografica. Prima versiune foloseste < pentru a determina ordinea, iar a doua foloseste obiectul comparator comp
Operatii numerice
Tabelul G.11 rezuma operatiile numerice, care sunt descrise în fisierul antet numeric. Argumentele nu sunt prezentate, iar functiile supraîncarcate sunt listate doar o singura data. Fiecare functie are o versiune care foloseste < pentru ordonarea elementelor si o versiune care, în acelasi scop, foloseste un obiect functie de comparare. O descriere mai detaliata, incluzând prototipurile, urmeaza dupa tabel. Astfel, puteti consulta tabelul pentru a avea o idee despre actiunea unei functii, iar apoi, daca vi se pare ca functia este utila, cautati detaliile.
Tabelul G.11 Sortare si operatii înrudite. (N.T.: Evident, trebuie: Operatii numerice.)
Functie Descriere
accumulate() Calculeaza un total al valorilor din interval.
inner_product() Calculeaza produsul interior a doua intervale.
partial_sum() Copiaza sume partiale calculate dintr-un interval în alt interval.
adjacent_difference() Copiaza diferente adiacente calculate din elementele unui
interval în alt interval.
template<class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init);
template<class InputIterator, class T, class BinaryOperation>
T accumulate(InputIterator first, InputIterator last, T init,
BinaryOperation binary_op);
Functia accumulate() initializeaza o valoare acc cu init; apoi realizeaza operatia acc = acc + *i (prima versiune) sau acc = binary_op(acc, *i) (a doua versiune), în ordine, pentru fiecare iterator i din intervalul [first last). Apoi, returneaza valoarea rezultata a lui acc
template<class InputIterator1, class InputIterator2, class T>
T inner_product(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, T init);
template<class InputIterator1, class InputIterator2, class T,
class BinaryOperation1, class BinaryOperation2>
T inner_product(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, T init, BinaryOperation1 binary_op1,
BinaryOperation2 binary_op2);
Functia inner_product() initializeaza o valoare acc cu init; apoi realizeaza operatia acc = *i * *j (N.T.: Trebuie acc = acc + *i * *j (prima versiune) sau acc = binary_op(*i, *j) (N.T.: Trebuie acc = binary_op1(acc, binary_op2(*i, *j)); (a doua versiune), în ordine, pentru fiecare iterator i din intervalul [first1 last1) si fiecare iterator j corespunzator din intervalul [first2 first2 + (last1 - first1)). Adica, calculeaza o valoare din primele elemente ale fiecarei secvente, apoi din elementele de pe a doua pozitie din fiecare secventa, si asa mai departe pâna când ajunge la sfârsitul primei secvente. (Prin urmare, a doua secventa trebuie sa fie cel putin la fel de lunga ca si prima.) Apoi, functia returneaza valoarea rezultata a lui acc
template<class InputIterator, class OutputIterator>
OutputIterator partial_sum(InputIterator first,
InputIterator last, OutputIterator result);
template<class InputIterator, class OutputIterator,
class BinaryOperation>
OutputIterator partial_sum(InputIterator first,
InputIterator last, OutputIterator result,
BinaryOperation binary_op);
Functia partial_sum() atribuie *first lui *result *first + *(first + 1) lui *(result + 1) (prima versiune), sau binary_op(*first, *(first + 1)) lui *(result + 1) (a doua versiune), si asa mai departe. Prin urmare, al n-lea element al secventei care începe la result contine suma (sau echivalentul binary_op) primelor n elemente ale secventei care începe la first. Functia returneaza un iterator dincolo-de-sfârsit pentru rezultat. Algoritmul permite ca result sa fie first, adica permite, daca este necesar, ca rezultatul sa fie copiat peste secventa originala.
template<class InputIterator, class OutputIterator>
OutputIterator adjacent_difference(InputIterator first,
InputIterator last, OutputIterator result);
template<class InputIterator, class OutputIterator,
class BinaryOperation>
OutputIterator adjacent_difference(InputIterator first,
InputIterator last, OutputIterator result,
BinaryOperation binary_op);
Functia adjacent_difference() atribuie *first la locatia result *result = *first). Locatiilor urmatoare din intervalul destinatie li se atribuie diferentele (sau echivalentul binary_op) locatiilor adiacente din intervalul sursa. Adica, urmatoarei locatii din intervalul destinatie (result + 1) i se atribuie *(first + 1) - *first (prima versiune), sau binary_op(*(first + 1), *first) (a doua versiune), si asa mai departe. Functia returneaza un iterator dincolo-de-sfârsit pentru rezultat. Algoritmul permite ca result sa fie first, adica permite, daca este necesar, ca rezultatul sa fie copiat peste secventa originala.
|
