ALGORITMII STL

Mihail Croitor

Cuprins

Noțiune de algoritm

Predicate

Denumirile algoritmilor în STL

Algoritmii, care nu modifică containere

Algoritmii, care modifică containere

Noțiune de algoritm

Algoritmul este …O secvența finită de acțiuni, care aduce la rezultatul dorit.

Predicate

Predicatul este o funcție ce returnează o valoare logică.

Mulți algoritmi STL operează cu predicate unari sau binari.

Denumirile algoritmilor în STL

Există algoritmii care au forma cât operațională atât și de copiere. Pentru un algoritm <algorithm>forma de copiere va avea denumire<algorithm>_copy

Dacă algoritmul <algorithm> are forma predicativă, atunci ea are denumire <algorithm>_if

Dacă algoritmul <algorithm> are formă predicativă de copiere, atunci ea are denumire <algorithm>_copy_if

Legenda

T Tipul elementelor ce se conțin în container

IIter Input Iterator

OIter Output Iterator

FIter Forward Iterator

BIter Bidirectional Iterator

RAIter Random Access Iterator

Pred Predicat Functor

UPred Predicat unar

BPred Predicat binar

Func functor Function

Algoritmii care nu modifică containere

Algoritmul Descriere

template <class IIter, class Func>Func for_each(IIter first, IIter last, Func f);

Aplică funcția f la fiecare valoare din semiinterval [first, last).

template <class IIter, class T>IIter find(IIter first, IIter last, const T& val);template <class IIter, class UPred>IIter find_if(IIter first, IIter last, UPredpred);

Returnează primul iterator din diapazonul [first, last), valoarea căruia este egală cu val(*i == val).Forma predicativă returnează primul iteratorcare corespunde condiției pred(*i) == true

template <class IIter, class T>typenameiterator_traits<IIter>::difference_typecount (IIter first, IIter last, const T& val);template <class IIter, class Pred>typenameiterator_traits<IIter>::difference_typecount_if(IIter first, IIter last, UPred pred);

Numără elementele care sunt egale cu val în diapazonul [first, last). Există forma predicativă.

Algoritmii care nu modifică containere 2

Algoritmul Descriere

template <class IIter1, class IIter2>bool equal (IIter1 first1, IIter1 last1, IIter2 first2);template <class IIter1, class IIter2, class BPred>bool equal (IIter1 first1, IIter1 last1, IIter2 first2, BPred pred);

Compară segmentele [first1, last1) și[first2, first2 +(last1-first1)). Dacă segmentele sunt egale, atunci se returnează true.Forma predicativă are același nume și verifică condiția pred(*i1, *i2) == true, unde i1 din [first1, last1) și i2 din [first2, first2 +(last1-first1)).

template <class FIter1, class FIter2>FIter1 search(FIter1 first1, FIter1 last1,FIter2 first2, FIter2 last2);

template <class FIter1, class FIter2,class BPred>FIter1 search(FIter1 first1, FIter1 last1,FIter2 first2, FIter2 last2, BPred pred);

Algoritmul caută segmentul [first2, last2)în segmentul [first1, last1) și returnează poziția primului element, dacă găsește, saulast1 – în caz contrar.Forma predicativă verifică dacă subsegmentul [first2, last2) satisface cerințelor predicatului.

Algoritmii care modifică containere

Algoritmul Descriere

template <class IIter, class OIter>OIter copy(IIter first, IIter last, OIterresult);template <class BIter1, class BIter2>BIter2 copy_backward(BIter1 first,BIter1 last, BIter2 result);template <class IIter, class OIter, class UPred>OIter copy_if(IIter first, IIter last, OIterresult, UPred p);

Algoritmul copie elementele din segmentul [first, last) în [result, result + (last - first)). copy_backward copie elementele în ordinea inversă. copy_ifcopie elementele, ce satisfac condiției p. Algoritmul copy_if a fost întrodus în standardul С++11.

template <class T> void swap(T& a,T& b);template < class FIter1 , class FIter2>FIter2 swap_ranges ( FIter1 first1, FIter1 last1, FIter2 first2 );template < class FIter1 , class FIter2>void iter_swap ( FIter1 a , FIter2 b );

Algoritmul swap schimbă cu locuri valori la 2 variabile. swap_ranges – schimbă cu locuri valorile la 2 segmente. iter_swap –schimbă cu locuri valorile la 2 iteratori.

Algoritmii care modifică containere 2

Algoritmul Descriere

template < class FIter , class T>void replace ( FIter first , FIter last , const T& old_value , const T& new_value );template < class FIter, class Pred, class T>void replace_if ( FIter first , FIter last , UPred pred , const T& new_value );

Schimbă old_value cu new_value pe segmentul [first, last). Forma predicativă schimbă toate valori care îndeplinesc cerințele predicatului.

template <class FIter, class T> FIter remove (FIter first, FIter last, const T& val);template <class IIter, class OIter, class T> OIter remove_copy (IIter first, IIter last, OIter result, const T& val);template <class FIter, class UPred>FIter remove_if (FIter first, FIter last, UPred pred);

Elimină toate elemente egale cu val din segment [first, last).Forma predicativă elimină toate elementele care satisfac condiția predicatului pred.

Algoritmii care modifică containere 3

Algoritmul Descriere

template <class FIter>FIter unique (FIter first, FIter last); template <class FIter, class BPred>FIter unique (FIter first, FIter last, BPredpred);

Elimină toate repetări din segmentul [first, last)Forma predicativă elimină toate repetări, comparând elementele din segment conform predicatului pred

template <class FIter, class Generator> void generate (FIter first, FIter last, Generator gen);

Completează segmentul [first, last) cu valori care returnează funcția gen

template <class IIter, class OIter, class UOper>OIter transform (IIter first1, IIter last1, OIterresult, UOper op); template <class IIter, class IIter, class OIter, class BOper>OIter transform (IIter first1, IIter1 last1, IIter2 first2, OIter result, BOper binary_op);

Prima versiune scrie în segmentul de ieșire[result, result + (last-first)) valori op(*it),unde it este din segmentul [first, last)Versiunea a doua scrie în segmentul de ieșire [result, result + (last1-first1)) valoriop(*it1, *it2), unde it1 este din [first1, last1), it2 este din [first2, first2+(last1-first1))