Algoritmi - algoritmi care nu modifica secventa

Algoritmii acopera un domeniu larg de operatii generale asupra containerelor precum: traversare, sortare, cautare, inserare sau stergere de elemente.

Algoritmii sunt functii generice, care se refera la containere prin intermediul iteratorilor. Tipurile iteratorilor folositi de un algoritm sunt date ca parametri ai sablonului.

Algoritmii sunt declarati in zona de nume std si semnaturile lor se afla in fisierul antet algorithm.

Cei mai multi algoritmi sunt scurti si simpli, putand fi definiti inline.

Algoritmii care produc rezultate pe care le depun intr-un container sunt clasificati ca algoritmi de copiere si au numele terminat cu sufixul _copy.

Algoritmii a caror functionare este determinata de satisfacerea unui predicat sunt cunoscuti ca algoritmi cu predicate. Lista de parametri a unui asemenea algoritm va contine un obiect functie predicat. Numele acestor algoritmi contine sufixul _if.

In prezentarea algoritmilor vom utiliza urmatoarele abrevieri:

InIt - InputIterator, OutIt - OutputIterator, FwIt - ForwardIterator,

BIt - BidirectionalIterator, RAIt - RandomAccessIterator, Pred - Predicate,

BinPred - BinaryPredicate, OpUnar - UnaryOperator, Func - Function, T - value_type (tipul elementelor din container)

Algoritmi care nu modifica secventa.

Se folosesc pentru a extrage informatii din secventa sau a gasi pozitia unor elemente din secventa.

1. for_each() elimina un ciclu explicit, repetand o operatie f asupra elementelor dintr-un interval de iteratori. Se foloseste pentru extragerea de informatii asupra elementelor secventei.

2. cautarea unei valori -familia find

find() cauta in secventa prima valoare egala cu un parametru. Intoarce un iterator la prima valoare gasita.

find_if() cauta in secventa prima valoare care satisface un predicat.

find_first_of()gaseste primul element din secventa 1 care se afla in secventa 2, sau gaseste primul element din secventa 1 care se satisface predicatul cu un element din secventa 2.

adjacent_find()gaseste prima pereche de elemente vecine egale / sau care satisfac predicatul binar.

3 contorizarea aparitiei unei valori

count() numara valorile din intervalul de iteratori egale cu valoarea data ca parametru. Numarul de elemente nu depaseste distanta intre iteratori.

count_if()numara valorile din intervalul de iteratori care satisfac predicatul.

4. - compararea a doua secvente

equal() intoarce true/false daca cele doua secvente sunt egale sau daca toate perechile satisfac predicatul

mismatch()intoarce iteratori la prima pereche de elemente neegale, respectiv perechea care nu satisface predicatul din cele doua secvente.

cautarea unei secvente

search() - determina prima aparitie a secventei2 ca subsecventa a secventei1, respectiv prima aparitie a secventei2 ca subsecventa in secventa1 cu elemente aflate in relatia data cu elementele din secventa2. Intoarce un iterator la primul element din prima secventa egalata cu secventa2.

find_end() determina ultima aparitie a secventei2 ca subsecventa a secventei1. Intoarce un iterator la primul element din ultima secventa egalata cu secventa2.

search_n() gaseste o secventa cu cel putin n elemente egale / sau in relatia p cu valoarea val. Intoarce un iterator la prima secventa de n asemenea elemente.

Algoritmi care modifica secventa.

Actualizarea unei secvente se poate face direct asupra acesteia (in situ) sau producand o noua secventa modificata in cursul traversarii (varianta _copy). Operatiile de actualizare se refera la inserari, stergeri, interschimb de valori, copiere, etc.

1. algoritmi de copiere - familia copy

copy() copiaza valorile dintr-un interval de iteratori la o destinatie, copierea incepand cu primul element din interval. Daca nu se poate suprascrie la destinatie se foloseste un iterator de insertie.

copy_backward() copiaza valorile dintr-un interval de iteratori la o destinatie, copierea incepand de la ultimul element din interval catre primul.

copy_if() copiaza toate valorile din intervalul de iteratori care satisfac predicatul, la destinatie.

inlocuiri - familia replace

replace() inlocuieste toate aparitiile ale unei valori vechi valv din intervalul de iteratori cu o valoare noua valn

replace_if() inlocuieste toate valorile care satisfac o anumita conditie din intervalul de iteratori cu o valoare noua.

Cei doi algoritmi au si variante replace_copy() si replace_copy_if(), in care inlocuirea nu se face in situ ci la o destinatie, specificata printr-un iterator.

3. stergeri - familia remove

remove() sterge toate valorile din domeniul de iteratori egale cu o valoare data

remove_if() sterge toate valorile din domeniul de iteratori care satisfac un predicat

si variantele remove_copy() si remove_copy_if()

4. interschimbari - familia swap interschimba elementele sau chiar containerele

swap() interschimba doua elemente individuale (chiar din containere diferite)

iter_swap ()interschimba doua elemente localizate prin iteratori

swap_ranges() interschimba elementele din doua intervale de iteratori

transform() aplica un operator unar elementelor dintr-un interval de iteratori, depunand elementele transformate in alt interval de iteratori

generate() completeaza elementele din intervalul de iteratori cu valori obtinute de la un functor generator (predicat fara argumente)

generate_n() completeaza cu valori furnizate de generator primele n elemente dintr-un domeniu de iteratori

fill() completeaza cu aceeasi valoare elementele dintr-un domeniu de iteratori

fill_n() completeaza cu aceeasi valoare primele n elemente dintr-un domeniu de iteratori

unique() sterge elementele consecutive identice cu un element / sau elementele consecutive elementului, aflate in relatie cu acesta.

si variantele _copy:

reverse() inverseaza ordinea elementelor din secventa

rotate() deplaseaza la stanga elemenetele secventei; elementele scoase sunt inserate la sfarsitul secventei (deplasare circulara). Iteratorul med indica inceputul secventei de elemente rotite.

partition() imparte secventa in doua intervale, astfel ca elementele care satisfac un predicat vor fi plasate in primul interval (inaintea celorlalte).

stable_partition() realizeaza in plus fata de algoritmul precedent, ordonarea relativa a elementelor din fiecare partitie

random_shuffle() amesteca aleatoriu ordinea elementelor din secventa. Generatorul de numere aleatoare poate fi specificat ca argument

iota() umple un interval de iteratori cu valori crescatoare, pornind cu o valoare data ca parametru

Algoritmi pentru secvente sortate.

Algoritmii din aceasta clasa se impart in doua categorii: prima foloseste in mod implicit functia de comparatie < , iar cealalta necesita ca argument un obiect functie Compare comp furnizat de utilizator.

sort() realizeaza sortarea elementelor din intervalul de iteratori. Se preteaza folosirii de catre containere cu acces direct (vector si deque). Pentru containerul list se foloseste functia membra list::sort().

Algoritmul sort() utilizeaza sortarea rapida (quicksort), avand in medie complexitatea O(N logN) si O(N²) in cazul cel mai nefavorabil, cu N=ultim-prim, dar sortarea nu este stabila, in sensul ca elementele cu aceeasi cheie pot sa nu mai ocupe acelesi pozitii relative dupa sortare.

stable_sort() algoritmul de sortare stabila stable_sort() , desi are in medie un timp de executie cu 40% mai mare, are in toate situatiile complexitatea O(N logN)

partial_sort() sorteaza primele M elemente din secventa, restul ramanand nesortate. Valoarea lui M nu este data in mod explicit, ci prin intermediul unui iterator med, astfel ca M=med-prim. Complexitatea este O(N log M)

Exista si variante _copy, care au ca parametri suplimentari iteratori la intervalul destinatie.

nth_element() furnizeaza cel de al n-lea element din secventa sortata crescator sau descrescator (fara a sorta secventa).

Valoarea lui n este precizata prin cel de-al doilea parametru n=nth-prim, inainte de apel; dupa apel *nth contine cel de-al n-lea element din secventa sortata. Complexitatea in medie este O(N).

binary_search() permite localizarea foarte rapida in O(log n) a unui element intr-un container cu acces direct sortat.

lower_bound() gaseste prima pozitie i dintr-o secventa sortata, in care poate fi inserata o valoare val astfel ca relatia de ordine sa se pastreze, adica *j < val (respectiv comp(*j, val)=true)pentru j I [prim, i)

upper_bound() gaseste ultima pozitie i dintr-o secventa sortata, in care poate fi inserata o valoare val astfel ca relatia de ordine sa se pastreze.

equal_range() determina cel mai mare interval dintr-o secventa sortata, in care poate fi inserata o valoare val , in orice pozitie, astfel ca relatia de ordine sa se pastreze.

9. interclasare

merge() combina doua secvente sortate intr-o secventa de asemeni sortata. Are complexitate liniara.

inplace_merge() daca cele doua domenii de iteratori sunt contigue([prim, med) si [med, ultim)), s-ar putea face interclasare peste ele, daca s-ar utiliza o zona tampon de memorie. Rezultatul interclasarii va fi plasat in [prim,ultim)

Algoritmi cu multimi.

Descriu principalele operatii cu multimi (incluziune, reuniune, intersectie, diferenta) pentru multimi (containere sortate). Au complexitate liniara O(N₁+N₂), unde N₁ si N₂ sunt cardinalele celor doua multimi.

includes() determina daca multimea M₂ este inclusa in multimea M₁.

set_union() construieste multimea reuniune M₁ M₂ a multimilor date prin intervalele de iteratori

set_intersection()construieste multimea intersectie M₁ M₂ a multimilor date prin intervalele de iteratori

set_difference() construieste multimea diferenta M₁-M₂ a multimilor date prin intervalele de iteratori (contine elementele din prima multime care nu apar in cea de a doua)

set_symmetric_difference() construieste multimea diferenta simetrica (M₁-M₂) (M₂-M₁)=(M₁ M₂)-(M₁ M₂) a multimilor date prin intervalele de iteratori (contine elementele din cele doua multimi exceptand elementele comune)

Algoritmi cu heapuri.

Un heap este un arbore binar complet partial ordont, folosit pentru implementarea cozii prioritare.

pop_heap()rearanjeaza elementele din intervalul [prim, ultim-1), astfel ca daca se extrage un element din varful heapului (din pozitia prim) prin interschimbul cu elementul din pozitia ultim-1 , noul interval [prim,ultim-1) sa reprezinte un heap. Complexitatea operatiei este O(log(ultim-prim)).

push_heap()rearanjeaza elementele din heap astfel ca daca se adauga un element in ultima pozitie ultim-1 intervalul [prim, ultim) sa reprezinte in continuare un heap. Complexitatea operatiei este O(log(ultim-prim))

make_heap() aranjeaza elementele din intervalul de iteratori, astfel incat acestea sa reprezinte un heap

sort_heap() transforma un heap intr-o secventa sortata (metoda de sortare heapsort). Complexitatea este O(N log N) si sortarea nu este stabila.

Algoritmi pentru minim si maxim.

min(), max()determina cel mai mic (respectiv cel mai mare) intre doua elemente

min_element(), max_element() furnizeaza un iterator la cel mai mic (cel mai mare) element din intervalul de iteratori.

Algoritmi de permutare.

O permutare provine dintr-o secventa prin schimbarea intre ele a doua elemente. Pentru o secventa avand N elemente, exista N! permutari. Multimea celor N! permutari se poate considera ordonata dupa relatia < (si in general comp) intre elemente. Conform acestei relatii de ordine putem defini permutarea urmatoare (respectiv permutarea precedenta) in raport cu permutarea curenta.

prev_permutation(), next_permutation() genereaza in intervalul de iteratori permutarea precedenta (urmatoare). Intoarece true daca exista permutarea precedenta (urmatoare) si false in caz contrar.

Algoritmi numerici.

Descriu operatii numerice generale. Accesul la acestia se obtine prin includerea fisierului antet <numeric>.

accumulate() aduna la elementele din intervalul de iteratori o valoare initiala data ca parametru.

inner_product() adauga o valoare initiala la produsul scalar al celor doua containere x si y:

.

partial_sum() calculeaza in containerul rezultat valorile acumulate din prima pozitie, primele doua, primele trei, etc.

adjacent_difference() calculeaza diferentele intre elementele consecutive ale unui container c, adica d₀=c₀, d_i=c_i-c_i-1, i>0.