STL (Standard Template Library)

STL (Standard Template Library)

Curs 14

STL• biblioteca C++ care contine clase pentru

containere, algoritmi si iteratori

• Furnizeaza majoritatea algoritmilor de baza si structurilor de date necesare in dezvoltarea de programe

• STL este o bibiblioteca generica – componentele sunt parametrizate – aproape fiecare componenta din STL este template

Containere• Vector• List• Deque

• Queue• Stack• Priority queue

• Set• Map• Multiset• Multimap• Bitset

Containere secventiale

Adaptori de containere

Containere asociative (cheie-valoare)

Vector• Elimina problema realocarii dinamice a spatiului de memorie

• Se redimensioneaza in partea finala astfel incat sa poata fi realizata adaugarea de noi elemente

• Compusi dintr-un bloc de memorie alocata secvential

• Folosit cand se fac adaugari/stergeri de la sfarsit

• Ineficient cand depasirile de memorie alocata pot determina copierea intregului vector

• Constrangeri asupra lui T: T();T(const T&); ~T(); T& operator=(const T&);

#include <vector>std::vector<int> myvector;

std:: vector<int>::iterator it;

Declaratie vector de intregi

Declaratie iterator pe vector de intregi

Operatii pe vectorOperatie Descriere Comple

xitate

Operator= atribuire O(n)

begin Returneaza un iterator pe primul element O(1)

end Returneaza un iterator pe ultimul element O(1)

rbegin Returneaza un reverse_iterator pe inceputul vectorului

O(1)

rend Returneaza un reverse_iterator pe sfarsitul vectorului

O(1)

size Returneaza dimensiunea vectorului O(1)

max_size Returneaza dimensiunea maxima a vectorului

resize Redimensioneaza vectorul la valoarea specificata

O(1)/O(n)

Operatii pe vectorcapacity Returneaza capacitatea vectorului O(1)

empty Returneaza true daca vectorul e vid O(1)

reserve Schimba capacitatea vectorului O(1)/O(n)

Operator[] Returneaza o referinta la obiectul de pe pozitia specificata

O(1)

at Acceseaza elementul de la pozitia paramteru

O(1)

front Acceseaza primul element al vectorului O(1)

back Acceseaza ultimul element al vectorului O(1)

assign Atribuie vectorului un nou continut O(n)

push_back Adauga element la final O(1)/O(n)

Operatii pe vectorpop_back Sterge ultimul element din vector O(1)

insert Insereaza elemente inaintea unei pozitii O(1)

erase Sterge din vector de la o singura pozitie sau elementele dintr-un domeniu [first,last)

O(n)

swap Interschimba 2 vectori O(1)

clear Distruge elementele din vector si dimensiunea devine 0

O(n)

List• Compuse din obiecte care au anterior-info-urmator

• Nu detin ownership asupra elementelor

• Folosite cand se fac inserari/stergeri oriunde in cadrul listei

• Cerinte pentru tipul T:

• T(); T(const T&); ~T(); T& operator=(const T&); T* operator&(); int operator < (const T&, const T&); int operator==(const T&, const T&);

#include <list>std::list<int> identifier;

std::list<int>::iterator identifier;

Declaratie lista de intregi

Declaratie iterator pe lista de intregi

Operatii pe tipul list

Operatie Descriere Complexitate


swap Interschimba elementele a doua liste (pointerii head si tail)

O(1)

begin Returneaza un iterator pe primul element al listei

O(1)

end Returneaza un iterator pe un element care urmeaza ultimului element al listei

O(1)

front Returneaza primul element al listei

O(1)

Operatii pe tipul listback Returneaza ultimul element al listei O(1)

empty Returneaza true daca lista e vida O(1)

size Returneaza numarul de elemente al listei O(n) sau O(1)

push_front Insereaza un element in capul listei O(1)

push_back Adauga un element la sfarsitul listei O(1)

insert Insereaza un element inainteau elementului indicat de iterator

Ex: l.insert(itr,3)

O(1)

pop_front Sterge primul element din lista O(1)

pop_back Sterge ultimul element din lista O(1)

remove Sterge toate aparitiile unui element din lista (foloseste operatorul ==)

erase 2 forme – sterge elementul indicat de iterator sau secventa dintre 2 iteratori

O(1) sau O(n)

Operatii pe tipul list

sort Sorteaza elementele listei in ordine ascendenta. Operatorul < trebuie sa fie supraincarcat

O(nlog2n)

reverse Inverseaza ordinea elementelor unei liste O(n)

merge Interclaseaza elementele a doua liste. In urma operatiei elementele din lista argument sunt inserate in lista apelanta. Ambele liste trebuie sa fie sortate

O(m*n)

m,n lungimile listelor

Deque (deck)• deque=double ended queue

• Nu e FIFO

• Permite adaugarea/stergerea elementelor la ambele capete

• Permite inserarea sau stergerea de elemente la pozitii arbitrare

• Accesul la elemente de poate realiza similar vectorilor, cu operatorul [] sau metoda at()

Declaratie coada de intregi

Declaratie iterator coada de intregi

#include <deque>std::deque<int> dequeOfIntegers; std::deque<int>::iterator itr;

Deque

Operatie Descriere Complexitate


swap Interschimba elementele a doua cozi (pointerii head si tail)

O(1)

begin Returneaza un iterator pe primul element al cozii

O(1)

end Returneaza un iterator pe un element care urmeaza ultimului element al cozii

O(1)

back Returneaza ultimul element al cozii O(1)

empty Returneaza true daca coada e vida O(1)

front Returneaza primul element al cozii O(1)

Dequesize Returneaza numarul de elemente al cozii O(n) sau

O(1)

push_front Insereaza un element in capul cozii O(1)

push_back Adauga un element la sfarsitul cozii O(1)

insert Insereaza un element inaintea elementului indicat de iterator

Ex: c.insert(itr,3)

O(1)

pop_front Sterge primul element din coada O(1)

pop_back Sterge ultimul element din coada O(1)

remove Sterge toate aparitiile unui element din coada (foloseste operatorul ==)

Deque

erase 2 forme – sterge elementul indicat de iterator sau secventa dintre 2 iteratori

O(1) sau O(n)

sort Sorteaza elementele cozii in ordine ascendenta. Operatorul < trebuie sa fie supraincarcat

O(nlog2n)

reverse Inverseaza ordinea elementelor unei cozi O(n)

merge Interclaseaza elementele a doua cozi. In urma operatiei elementele din coada argument sunt inserate in coada apelanta. Ambele cozi trebuie sa fie sortate

O(m*n)

m,n lungimile cozilor

Vector sau deque?• Deque permite inserarea/stergerea elementelor de la

inceputul/sfarsitul cozii in timp constant

• Vectorul permite inserarea/stergerea elementelor doar la sfarsit in timp constant

• Deque permite inserarea/stergerea de elemente la pozitii arbitrare mai eficient decat vectorul, dar nu in timp constant

• Accesul aleator la elemente este mai rapid la vector decat la deque

• Pentru secvente mari de elemente vectorul va aloca o zona mare de memorie contigua, pe cand deque va aloca mai multe blocuri de memorie de dimensiuni mai mici – mai eficient din punctul de vedere al sistemelor de operare

• Deque se comporta atat ca o stiva, cat si ca o coada

• Deque se expandeaza mai eficient decat vectorii

Stack• LIFO• Ca implementare, in STL, o stiva e un adaptor (implementare a

sablonului de proiectare Adapter – vezi curs 11) – preia ca parametru al templateului un container secvential si lasa vizibile doar operatiile care sunt asociate unei stive

• #include <stack>• #include <C> - C containerul care dorim sa fie adaptat la stiva

#include <stack>#include <list>std::stack<int, std::list<int> > myStack;

Implicit deque (lista consuma prea multa memorie, vectorii de expandeaza costisitor)

std::stack<int> myStack;

Stack

Operatii Descriere

empty Returneaza true daca stiva e vida

size Returneaza numarul de elemente din stiva

top Returneaza o referinta la elementul din varful stivei

push Adauga un nou element in stiva

pop Extrage elementul din varful stivei

Set• Cotainer in care toate elementele sunt distincte• Pastreaza elementele sortate!!• Functia find() are complexitate logaritmica

#include <set>std::set<int> s;std::set<int>::iterator it=s.begin();

Declaratie multime de intregi

Declaratie iterator multime de intregi

#include <set>#include <iostream>using namespace std;

int main(){set<int> intSet;for(int i=0;i<25;i++) for(int j=0;j<10;j++) intSet.insert(j);

set<int>::iterator it=intSet.begin();

while(it!=intSet.end()){cout<<*it<<" "; it++;}return 0;}

0 1 2 3 4 5 6 7 8 9

Multiset

• Accepta aparitii multiple ale unui element

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 33 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 44 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 66 6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 78 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9 9 9 9 99 9 9 9 9 9 9 9 9 9

#include <set>#include <iostream>using namespace std;

int main(){

multiset<int> intSet;for(int i=0;i<25;i++) for(int j=0;j<10;j++) intSet.insert(j);

multiset<int>::iterator it=intSet.begin();

while(it!=intSet.end()){cout<<*it<<" "; it++;}return 0;}

Operatii pe SetOperatii Descriere Complexitate

swap Interschimba elementele a doua multimi

O(1)

lower_bound Returneaza un iterator pe primul element >= o cheie. Iteratorul este setat pe end() daca un astfel de element nu exista

O(log2n)

upper_bound Returneaza un iterator pe elementul imediat urmator parametrului. Returneaza end() daca un astfel de element nu exista

O(log2n)

insert Adauga un element la o multime O(log2n)

begin Returneaza un iterator pe primul element la multimii

O(1)

Operatii pe Setsize Returneaza dimensiunea multimii.

Pentru testarea de vid, preferabil de folosit empty – e mai rapida

O(n)

empty Returneaza true daca multimea e vida O(1)

find Cauta o cheie si returneaza un iterator pe elementul gasit, altfel end()

O(log2n)

Map• Asociaza chei de un anumit tip cu valori de alt tip• Elementele sunt accesate direct, pe baza cheii

– aMap["John Doe"] = 3.2; • Cheile trebuie sa fie unice

• Atentie la utilizarea operatorului [] – algoritm:– Cauta cheia in dictionar– Daca e gasita se returneaza o referinta spre valoarea asociata– Daca nu e gasita se creeaza un nou obiect de tipul valorii si se

returneaza o referinta spre el

• Pentru a verifica apartenenta unui element la dictionar se foloseste metoda find() – nu creeaza un obiect daca cheia nu exista

• Find returneaza un iterator pe o pereche de obiecte (cheie, valoare) daca cheia exista, altfel returneaza end()

#include <map>std::map<string, double> aMap;std::map<string,double>::iterator it;

Declaratie dictionar

Declaratie iterator pe dictionar

Map-pair• pair este o clasa template care are doua date membre publice

accesbile folosind pair::first (cheia), respectiv pair::second (valoarea)

• Definita in <utility>• Pentru a crea un obiect de tip pair – functia template make_pair

care are 2 parametri

• Cerinte asupra tipului cheilor/valorilor – sa aiba operatorul = supraincarcat

• Tipul cheilor trebuie sa respecte urmatoarele constrangeri (ordine stricta):– a<a e fals

– Egalitatea se poate determina din expresia (!(a<b)&&!(b<a))

– Daca a<b si b<c, atunci a<c

• Tipul valorilor trebuie sa aiba definit un constructor implicit

pair<string,double> p; p = make_pair(string("Microsoft Share Price"), double(85.27));

Operatii pe Mapswap Interschimba elementele a doua dictionare O(1)

begin Returneaza un iterator pe primul element al dictionarului

O(1)

end Returneaza un iterator pe utlimul element al dictionarului

O(1)

size Returneaza numarul de elemente din dictionar

O(n)

empty Returneaza true daca dictionarul e vid O(1)

operator[] Returneaza o referinta la obiectul asociat cheii. Daca cheia nu exista, va crea un obiect

O(log2n)

find Cauta o cheie in dictionar. Daca o gaseste, returneaza un iterator pe perechea (cheie, valoare), altfel returneaza un iterator setat pe end

O(log2n)

Operatii pe Maperase 3 supraincarcari:

1. Sterge elementul indicat de iterator

2. Sterge secventa dintre 2 iteratori

3. Primeste ca parametru un obiect de tipul cheii si sterge elementele cu cheia egala cu parametrul (cel mult 1 element)

– map1.erase(string("Bob"))

Multimap• Permite existenta aceleiasi chei de mai multe ori

• Pentru a gasi toate perechile cheie valoare corespunzatoare unei chei, vom folosi 2 iteratori-unul setat pe prima pereche din dictionar si altul setat pe ultima pereche din dictionar care corespunde cheii

#include <map>

multimap<string, int> mMap; multimap<string, int>::iterator itr;

multimap<string, int>::iterator itr; multimap<string, int>::iterator lastElement; itr = mMap.find(key); if (itr == mMap.end()) return; cout << "The following values are associated with the key " << key << endl;lastElement = mMap.upper_bound(key); for ( ; itr != lastElement; ++itr) cout << itr->second << endl;

Operatii pe multimap

swap Interschimba 2 dictionare cu chei multiple O(1)

count Returneaza numarul valorilor asociate unei chei

Ex: cout << multimap1.count("Bob");

O(log2n+m)m-numarul de valori asociate cheii

upper_bound Returneaza un iterator situat cu o pozitie dupa ultima aparitie a cheii sau end()

O(log2n)

lower_bound Returneaza un iterator situat pe o pereche a carei cheie este mai mare sau egala cu cheia data ca parametru sau end()

O(log2n)

begin Returneaza un iterator pe prima pereche din dictionar

O(1)

end Returneaza un iterator situat dupa ultimul element al dictionarului

O(1)

Operatii pe multimapsize Returneaza numarul de perechi din dictionar O(n)

empty Returneaza true daca dictionarul este vid O(1)

find Primeste o cheie ca parametru si returneaza un iterator pe prima pereche care are cheia egala cu parametrul, sau end daca nu exista

O(log2n)

insert Adauga o pereche in dictionar

Ex: multimap1.insert(make_pair(string("Bob"), int(5)));

O(log2n)

erase 3 supraincarcari:

1. Sterge elementul indicat de iterator

2. Sterge elementele dintre 2 iteratori

3. Sterge perechile care au cheia egala cu parametrul

– multimap1.erase(string("Bob"))

O(log2n+m)m-numarul de valori asociate cheii

Iteratori• Similari pointerilor in sensul ca elementele indicate sunt accesate indirect

• o abstractizare intre container si utilizatorul sau (putem scrie algoritmi pe containere fara sa stim reprezentarea acestora)

• Determina reducerea cuplarii (GRASP-low coupling) intre functii si containere accesate de acestea

• Pentru a accesa elementul, iteratorul trebuie dereferentiat

• Clase de iteratori:– Inainte (forward)-operator ++ - 3 categorii:

• Input (read-only)

• Output(write-only)

• Random access (read/write)

– Bidirectional – permit traversarea inainte/inapoi – operatorii ++/--, acces read/write

– Acces aleator (random access) –permite acces la oricare element al containerului folosind operatorii +/- si ++/--

Iteratori• Majoritatea containerelor accepta iteratori, cu exceptia stivei, cozii si

cozii cu prioritati

• Parcurgerea elementelor containerului folosind iteratori:

• Accesul la elementul curent:– Folosind * sau -> (daca obiectul referit este un agregat)– *itr=3;– struct pair { int first, second; }; – itr->first = 5; itr->second = 6;

<container>::iterator<container>::const_iterator

Declaratie iteratori

for (itr = container.begin(); itr!=container.end(); ++itr) @proceseaza(*itr);

Iteratori pe containere reversibile• Container reversibil – produce

iteratori care merg de la sfarsit spre inceput

• Toate containerele standard permit existenta iteratorilor reversibili

• Pentru initializare: rbegin(), rend()

#include <vector>#include <iostream>using namespace std;

int main(){ vector<int> v; v.push_back(3); v.push_back(4); v.push_back(5); vector<int>::reverse_iterator

rit=v.rbegin(); while (rit<v.rend()) { cout<<*rit<<endl; ++rit; }return 0;}

<container>::reverse_iterator<container>::const_reverse_iterator

5 4 3

Iteratori pe streamuri• Destinati automatizarii unor

sarcini comune (curente)

• STL furnizeaza metode de aplicare a unor algoritmi generici care sa inlocuiasca nevoia de a itera prin containere

• Un iterator pe stream foloseste un stream fie pentru intrare, fie pentru iesire

• ostream_iterator• istream_iterator

#include <iostream>#include <fstream>#include <iterator>#include <vector>using namespace std;

int main () { vector<int> myvector; int value; cout << "Please, insert values: (CTRL+Z to stop) ";

istream_iterator<int> eos; // end-of-stream iterator istream_iterator<int> iit (cin); // stdin iterator

while (iit!=eos) { myvector.push_back(*iit); iit++; }

ifstream fin("date.in"); istream_iterator<int> fiit (fin); //file iterator while (fiit!=eos) { myvector.push_back(*fiit); fiit++; }

ostream_iterator<int> out_it (cout,", "); copy ( myvector.begin(), myvector.end(), out_it );

ofstream fout("date.out"); ostream_iterator<int> fout_it(fout,"|"); copy ( myvector.begin(), myvector.end(), fout_it ); return 0;}

Iteratori de inserare (insertion/insert iterators)

• x iterator• *x=3• Daca x e un insert iterator *x=3 genereaza adaugarea elementului 3

la secventa pe care itereaza

• Necesari unor algoritmi care au scopul de umplere a containerele, nu de suprascriere

• insert_iterator – permite inserarea de elemente in mijlocul unei secvente

• 2 clase adaptor: – front_inserter – containerul trebuie sa aiba metoda push_front– back_inserter - containerul trebuie sa aiba metoda push_back

– Constructorii iau un container secvential (vector, list,deque) si produc un iterator care apeleaza push_back sau push_front

Suprascrie valoarea existenta

back_insert_iterator#include <iostream>#include <iterator>#include <vector>using namespace std;

int main () { vector<int> firstvector, secondvector; for (int i=1; i<=5; i++) { firstvector.push_back(i); secondvector.push_back(i*10); }

back_insert_iterator< vector<int> > back_it (firstvector);

copy (secondvector.begin(),secondvector.end(),back_it);

ostream_iterator<int> out_it (cout,", "); copy ( firstvector.begin(), firstvector.end(), out_it );

return 0;}

1 2 3 4 5

10 20 30 40 50

first

second

1, 2, 3, 4, 5, 10, 20, 30, 40, 50

first

back_it

front_insert_iterator#include <iostream>#include <iterator>#include <deque>using namespace std;

int main () { deque<int> firstdeque, seconddeque; for (int i=1; i<=5; i++) { firstdeque.push_back(i); seconddeque.push_back(i*10); }

front_insert_iterator< deque<int> > front_it (firstdeque);

copy (seconddeque.begin(),seconddeque.end(),front_it);

deque<int>::iterator it; ostream_iterator<int> oit(cout,","); copy(firstdeque.begin(),firstdeque.end(),oit);

return 0;}

1 2 3 4 5

10 20 30 40 50

firstdeque

seconddeque

50, 40, 30, 20, 10, 1, 2, 3, 4, 5

firstdeque

front_it

insert_iterator#include <iostream>#include <iterator>#include <list>using namespace std;

int main () { list<int> firstlist, secondlist; for (int i=1; i<=5; i++) { firstlist.push_back(i); secondlist.push_back(i*10); }

list<int>::iterator it; it = firstlist.begin(); advance (it,3);

insert_iterator< list<int> > insert_it (firstlist,it);

copy (secondlist.begin(),secondlist.end(),insert_it);

for ( it = firstlist.begin(); it!= firstlist.end(); ++it ) cout << *it << " ";

cout << endl;

return 0;}

1 2 3 10 20 30 40 50 4 5

1 2 3 4 5

10 20 30 40 50

firstlist

secondlist

firstlist

it

Algoritmi generici• Operatii care nu modifica secventa pe care opereaza

• Operatii care modifica secventa pe care opereaza

• Sortare

• Cautare binara

• Interclasare

• Ansambluri (heap)

• Min/max

Obiecte de tip functie• Folosite pentru a transmite

valori predicatelor la executie

• Obiectele de tip functie:– abstractizare care permite

comportamentul de functie

– Instanta a unei clase care supraincarca operatorul() (operatorul apel de functie)

#include <iostream>using namespace std;

class gt_n{ int val; public: gt_n(int v):val(v){} bool operator()(int n){return

val>n;}};

int main(){ gt_n f(4); cout<<f(3)<<endl;//f.operator()(3); cout<<f(5)<<endl;//f.operator()(5); return 0;}

Clasificarea obiectelor de tip functie• Pe baza tipului returnat si a numarului de argumente ale operatorului ()

• Generator – obiect de tip functie care nu ia nici un parametru si returneaza o valoare de tip arbitrar (ex: rand(), <cstdlib>)

• Functie unara – functie cu un parametru care returneaza un tip arbitrar(inclusiv void)

• Functie binara - functie cu 2 parametri care returneaza un tip arbitrar(inclusiv void)

• Predicat unar – functie unara care returneaza bool

• Predicat binar – functie binara care returneaza bool

• Ordonare stricta – predicat binar care permite o interpretare mai generala a egalitatii ( 2 elemente sunt egale daca nici unul nu e strict mai mic decat altul – nr reale)

• LessThanComparable – clasa care are operatorul<

• Assignable – clasa care are operatorul =

• EqualityComparable – clasa care are operatorul ==

Operatii care nu modifica secventa

• for_each

• find/find_end/find_first/adjacent_find

• equal

• count/count_if

• mismatch

• search/search_n

for_each

• aplica o functie data ca parametru pe fiecare element al secventei specificate

• template <class InputIterator, class Function> Function for_each (InputIterator first,

InputIterator last, Function f);

#include <iostream>#include <algorithm>#include <vector>using namespace std;

void myfunction (int i) { cout << " " << i;}

int main () { vector<int> myvector; myvector.push_back(10); myvector.push_back(20); myvector.push_back(30);

cout << "Vectorul contine:"; for_each (myvector.begin(),

myvector.end(), myfunction);

return 0;}

find• template <class InputIterator,

class T> InputIterator find ( InputIterator first, InputIterator last, const T& value );

• Returneaza un iterator pe primul element egal cu value, sau un iterator pe end(), in cazul in care nu gaseste elementul


int main () { int elems[] = { 10, 20, 30 ,40 }; vector<int> myvector(elems,elems+4); vector<int>::iterator it; it = find (myvector.begin(),

myvector.end(), 30); ++it; cout << “The element following 30 is "

<< *it << endl;

return 0;}

The element following 30 is 40

find_if• template <class InputIterator,

class Predicate> InputIterator find_if ( InputIterator first, InputIterator last, Predicate pred );

• Predicate – functie care are ca parametru un obiect de tipul template-ului si returneaza o valoare booleana

• Gaseste un element in domeniul [first, last) care sa respecte conditia specificata de pred si returneaza un iterator pe element, altfel returneaza un iterator pe end()


bool positive (int i) { return (i>0);}

int main () { vector<int> myvector; vector<int>::iterator it; myvector.push_back(-10); myvector.push_back(-95); myvector.push_back(40); myvector.push_back(-55);

it = find_if (myvector.begin(), myvector.end(), positive);

cout << "The first positive value" << *it << endl;

return 0;}

predicat

The first positive value 40

Alte variatii find• find_end – gaseste ultima aparitie a unei

secvente in alta secventa si returneaza un iterator

• find_first_of – gaseste prima aparitie a oricarui element dintr-o secventa in alta secventa

• adjacent_find – cauta prima aparitie a doua valori consecutive egale intr-o secventa si returneaza un iterator la ea

equal• Verifica daca elementele din

doua domenii sunt egale facand compararea pe perechi de elemente corespunzatoare

• 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);


bool mypredicate (int i, int j) { return (i==j);}

int main () { int myints[] = {20,40,60,80,100}; vector<int>myvector (myints,myints+5); if (equal (myvector.begin(), myvector.end(),

myints)) cout << "The contents of both sequences are

equal." << endl; else cout << "The contents of both sequences

differ." << endl; myvector[3]=81;

if (equal (myvector.begin(), myvector.end(), myints, mypredicate))

cout << "The contents of both sequences are equal." << endl;

else cout << "The contents of both sequences differ."

<< endl; return 0;}

The contents of both sequences are equal.The contents of both sequences differ.

count/count_if• Returneaza numarul de aparitii ale

unui element intr-o secventa sau / numarul elementelor pentru care o conditie este adevarata

• template <class InputIterator, class T> typename iterator_traits<InputIterator>::difference_type count ( ForwardIterator first, ForwardIterator last, const T& value );

• template <class InputIterator, class Predicate> typename iterator_traits<InputIterator>::difference_type count_if ( ForwardIterator first, ForwardIterator last, Predicate pred );


bool positive(int i) { return (i>0);}

int main () { vector<int> myvector;

myvector.push_back(-10); myvector.push_back(-95); myvector.push_back(40); myvector.push_back(-55);

int nrPos =(int) count_if (myvector.begin(), myvector.end(), positive);

cout << "The no of positive values is " << nrPos << endl;

return 0;}

-10 -95 40 -55

The no of positive values is 1

mismatch• Compara doua secvente si returneaza pozitia primei diferente


bool mypredicate (int i, int j) {return (i==j);}

int main () {

vector<int> myvector; for (int i=1; i<6; i++) myvector.push_back (i*10); int myints[] = {10,20,80,320,1024}; pair<vector<int>::iterator,int*> mypair; mypair = mismatch (myvector.begin(), myvector.end(), myints); cout << "First mismatching elements: " << *mypair.first; cout << " and " << *mypair.second << endl;; mypair.first++; mypair.second++; mypair = mismatch (mypair.first, myvector.end(), mypair.second, mypredicate); cout << "Second mismatching elements: " << *mypair.first; cout << " and " << *mypair.second << endl;; return 0;}

Comparatie implicita (==)

Comparatie cu predicatFirst mismatching elements: 30 and 80Second mismatching elements: 40 and 320

search• Cauta prima aparitie a unei secvente

in alta secventa si returneaza un iterator pe primul element al secventei (comparatia se face folosind == sau predicat)

• 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 );


bool mypredicate (int i, int j) { return (i==j);}

int main () { vector<int> myvector; vector<int>::iterator it;

for (int i=1; i<10; i++) myvector.push_back(i*10);

// using default comparison: int match1[] = {40,50,60,70}; it = search (myvector.begin(), myvector.end(), match1,

match1+4);

if (it!=myvector.end()) cout << "match1 found at position " << int(it-myvector.begin()) << endl; else cout << "match1 not found" << endl;

// using predicate comparison: int match2[] = {20,30,50}; it = search (myvector.begin(), myvector.end(), match2,

match2+3, mypredicate);

if (it!=myvector.end()) cout << "match2 found at position " << int(it-myvector.begin()) << endl; else cout << "match2 not found" << endl; return 0;}

10 20 30 40 50 60 70 80 90

40 50 60 70

20 30 50

match1 found at position 3match2 not found

search_n• Cauta prima aparitie a unei

succesiuni de n elemente egale in secventa si returneaza un iterator pe primul element

• 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 );


bool mypredicate (int i, int j) {return (i==j);}

int main () { int myints[]={10,20,30,30,20,10,10,20}; vector<int> myvector (myints,myints+8); vector<int>::iterator it;

it = search_n (myvector.begin(), myvector.end(), 2, 10);

if (it!=myvector.end()) cout << "two 10s found at position " << int(it-

myvector.begin()) << endl; else cout << "match not found" << endl;

it = search_n (myvector.begin(), myvector.end(), 2, 20, mypredicate);

if (it!=myvector.end()) cout << "two 20s found at position " << int(it-

myvector.begin()) << endl; else cout << "match not found" << endl; return 0;}

two 10s found at position 5match not found

Operatii care modifica secventa• copy/copy_backward• swap/swap_ranges/iter_swap• transform• replace/replace_if/replace_copy/replace_copy_if• fill/fill_n• generate/generate_n• remove/remove_if/remove_copy/remove_copy_if• unique/unique_copy• reverse/reverse_copy• rotate/rotate_copy• random_shuffle• partition• stable_partition

Copy/copy_backward• template <class InputIterator, class

OutputIterator> OutputIterator copy ( InputIterator first, InputIterator last, OutputIterator result );

• Copiaza elementele dintre first si last intr-un domeniu care incepe cu result

• Returneaza un iterator pe ultimul element al secventei destinatie

• template <class BidirectionalIterator1, class BidirectionalIterator2> BidirectionalIterator2 copy_backward ( BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 result );

• Copiaza elementele in ordine inversa (de la last-1 la first) – se copiaza last-1 in result-1, samd


int main () { int myints[]={10,20,30,40,50,60,70}; vector<int> myvector(7); vector<int>::iterator it;

copy ( myints, myints+7, myvector.begin() );

cout << "myvector contains:"; for (it=myvector.begin(); it!=myvector.end(); ++it) cout << " " << *it;

cout << endl;

return 0;}

10 20 30 40 50 60 70

Copy_backward#include <iostream>#include <algorithm>#include <vector>using namespace std;


for (int i=1; i<=5; i++) myvector.push_back(i*10);// myvector: 10 20 30 40 50

myvector.resize(myvector.size()+3);

copy_backward ( myvector.begin(), myvector.begin()+5, myvector.end() );


cout << endl;

return 0;}

10 20 30 10 20 30 40 50

10 20 30 40 50

10 20 30 40 50 x x x

swap• template <class T> void swap (

T& a, T& b ) { T c(a); a=b; b=c; }

• Interschimba 2 valori


int main () {

int x=10, y=20; swap(x,y);

vector<int> first (4,x), second (6,y); swap(first,second);

cout << "first contains:"; for (vector<int>::iterator it=first.begin(); it!=first.end(); ++it) cout << " " << *it;

cout << “second contains:"; for (vector<int>::iterator it=second.begin(); it!=second.end();

++it) cout << " " << *it;

cout << endl;

return 0;}

20 20 20 20

10 10 10 10 10 10

20 20 20 20

10 10 10 10 10 10

first

second

first

second

swap_ranges• template < class ForwardIterator1,

class ForwardIterator2 > ForwardIterator2 swap_ranges ( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2 );

• Interschimba valorile din domeniul [first1,last1) cu elementele incepand de la first2


int main () { vector<int> first (5,10); vector<int> second (5,33); vector<int>::iterator it;

swap_ranges(first.begin()+1, first.end()-1, second.begin());

cout << " first contains:"; for (it=first.begin(); it!=first.end(); ++it) cout << " " << *it;

cout << "\nsecond contains:"; for (it=second.begin(); it!=second.end(); ++it) cout << " " << *it;

cout << endl;

return 0;}

10 10 10 10 10

33 33 33 33 33

10 33 33 33 10

10 10 10 33 33

[ )

iter_swap• Interschimba

elementele indicate de 2 iteratori

• template <class ForwardIterator1, class ForwardIterator2> void iter_swap ( ForwardIterator1 a, ForwardIterator2 b );


int main () {

int myints[]={10,20,30,40,50 }; vector<int> myvector (4,99); iter_swap(myints,myvector.begin());

iter_swap(myints+3,myvector.begin()+2);

cout << "myvector contains:"; for (vector<int>::iterator it=myvector.begin(); it!=myvector.end(); +

+it) cout << " " << *it;

cout << endl;

return 0;}

10 20 30 40 50

99 99 99 99

99 20 30 40 50

10 99 99 99

99 20 30 99 50

10 40 99 99

transform• Aplica o transformare unara

fiecarui element din secventa de intrare sau o transformare binara elementelor corespunzatoare din doua secvente de intrare

• template < class InputIterator, class OutputIterator, class UnaryOperator > OutputIterator transform ( InputIterator first1, InputIterator last1, OutputIterator result, UnaryOperator op );

• Rezultatul – o noua secventa

• template < class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperator > OutputIterator transform ( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryOperator binary_op );


int op_changeSign (int i) { return (-1)*i; }int op_diff (int i, int j) { return i-j; }

int main () { vector<int> first; vector<int> second; vector<int>::iterator it;

for (int i=1; i<6; i++) first.push_back (i*10);

second.resize(first.size());

transform (first.begin(), first.end(), second.begin(), op_changeSign);

cout << "first contains:"; for (it=first.begin(); it!=first.end(); ++it) cout << " " << *it;

transform (first.begin(), first.end(), second.begin(), first.begin(), op_diff);

cout << "first contains:"; for (it=first.begin(); it!=first.end(); ++it) cout << " " << *it;

cout << endl; return 0;}

10 20 30 40 50

-10 -20 -30 -40 -50

20 40 60 80 100

replace• template < class ForwardIterator,

class T > void replace ( ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value );

• Inlocuieste toate aparitiile din [first,last) ale lui old_value cu new_value


int main () { int myints[] = { 10, 20, 30, 30, 20, 10, 10, 20 }; vector<int> myvector (myints, myints+8);

replace (myvector.begin(), myvector.end(), 20, 99);

cout << "myvector contains:"; for (vector<int>::iterator it=myvector.begin(); it!

=myvector.end(); ++it) cout << " " << *it;


10 20 30 30 20 10 10 20

10 99 30 30 99 10 10 99

fill/fill_n• template < class ForwardIterator, class

T > void fill ( ForwardIterator first, ForwardIterator last, const T& value );

• template < class OutputIterator, class Size, class T > void fill_n ( OutputIterator first, Size n, const T& value );

• Completeaza (primele n) elementele din intervalul [first,last) cu value


int main () { vector<int> myvector (8);

fill (myvector.begin(),myvector.begin()+4,5);

fill (myvector.begin()+3,myvector.end()-2,8);

cout << "myvector contains:"; for (vector<int>::iterator it=myvector.begin(); it!

=myvector.end(); ++it) cout << " " << *it;vector<int> myvector1 (8,10); fill_n (myvector1.begin(),4,20);

fill_n (myvector1.begin()+3,3,33); cout << "myvector1 contains:"; for (vector<int>::iterator it=myvector1.begin(); it!

=myvector1.end(); ++it) cout << " " << *it;return 0;}

0 0 0 0 0 0 0 0

5 5 5 5 0 0 0 0

5 5 5 8 8 8 0 0

10 10 10 10 10 10 10 10

20 20 20 20 10 10 10 10

20 20 20 33 33 33 10 10

generate/generate_n• template <class ForwardIterator,

class Generator> void generate ( ForwardIterator first, ForwardIterator last, Generator gen );

• template <class OutputIterator, class Size, class Generator> void generate_n ( OutputIterator first, Size n, Generator gen );

• Completeaza elementele dintre first si last cu valorile generate de functia gen

#include <iostream>#include <algorithm>#include <vector>#include <ctime>#include <cstdlib>using namespace std;

// function generator:int RandomNumber () { return (rand()%100); }

int current(0);int UniqueNumber () { return ++current; }

int main () { srand ( unsigned ( time(NULL) ) );

vector<int> myvector (8); vector<int>::iterator it;

generate (myvector.begin(), myvector.end(), RandomNumber);

cout << "myvector contains:"; for (it=myvector.begin(); it!=myvector.end(); ++it) cout << " " << *it; int myarray[9];

generate_n (myarray, 9, UniqueNumber);

cout << "myarray contains:"; for (int i=0; i<9; ++i) cout << " " << myarray[i];

return 0;}

remove• template < class ForwardIterator,

class T > ForwardIterator remove ( ForwardIterator first, ForwardIterator last, const T& value );

• Elimina value din intervalul [first,last)

• Returneaza un iterator spre noul sfarsit al secventei

#include <iostream>#include <algorithm>using namespace std;

int main () { int myints[] = {10,20,30,40,50,20,70};

int* pbegin = myints; int* pend =

myints+sizeof(myints)/sizeof(int);

pend = remove (pbegin, pend, 20);

cout << "range contains:"; for (int* p=pbegin; p!=pend; ++p) cout << " " << *p;


10 30 40 50 70

10 20 30 40 50 20 70

remove_copy• template <class InputIterator,

class OutputIterator, class T> OutputIterator remove_copy ( InputIterator first, InputIterator last, OutputIterator result, const T& value );

• Realizeaza o copie fara elementele egale cu value


int main () { int myints[] = {10,20,30,30,20,10,10,20}; vector<int> myvector (8);vector<int>::iterator it;

int* pend=remove_copy (myints,myints+8,myvector.begin(),20);

cout << "myvector contains:"; for (it=myvector.begin(); it!=pend; ++it) cout << " " << *it; cout << endl; for (it=myvector.begin(); it!=myvector.end(); +

+it) cout << " " << *it;

return 0;}

10 20 30 30 20 10 10 20

10 30 30 10 10 0 0 0

remove_copy_if• template <class InputIterator,

class OutputIterator, class Predicate> OutputIterator remove_copy_if ( InputIterator first, InputIterator last, OutputIterator result, Predicate pred );

• Copiaza elementele din intervalul [first,last) cu exceptia celor pt care pred e true


bool IsOdd (int i) { return ((i%2)==1); }

int main () { int myints[] = {1,2,3,4,5,6,7,8,9}; vector<int> myvector (9); vector<int>::iterator it;

remove_copy_if (myints,myints+9,myvector.begin(),IsOdd);



2 4 6 8 0 0 0 0 0

unique• template <class ForwardIterator>

ForwardIterator unique ( ForwardIterator first, ForwardIterator last );

• template <class ForwardIterator, class BinaryPredicate> ForwardIterator unique ( ForwardIterator first, ForwardIterator last, BinaryPredicate pred );

• Elimina elementele consecutive egale (==) sau le compara folosind o functie de comparare


bool myfunction (int i, int j) { return (i==j);}

int main () { int myints[] = {10,20,20,20,30,30,20,20,10};

vector<int> myvector (myints,myints+9); vector<int>::iterator it; // using default comparison:

it = unique (myvector.begin(), myvector.end());

myvector.resize( it - myvector.begin() ) // 10 20 30 20 10

// using predicate comparison: unique (myvector.begin(), myvector.end(),

myfunction); cout << "myvector contains:"; for (it=myvector.begin(); it!=myvector.end(); ++it) cout << " " << *it;

cout << endl;

return 0;}

10 20 30 20 10

10 20 30 20 10 30 20 20 10

dublurile

unique_copy• 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 );

• Copiaza elementele din intervalul [first, last) cu exceptia elementelor consecutive egale sau care respecta o relatie data ca functie


bool myfunction (int i, int j) { return (i==j);}

int main () { int myints[] = {10,20,20,20,30,30,40,40,30,10}; vector<int> myvector (10); vector<int>::iterator it;

// using default comparison: it=unique_copy (myints,myints+10,myvector.begin()); for (it=myvector.begin(); it!=myvector.end(); ++it) cout << " " << *it; cout << endl; sort (myvector.begin(),it); for (it=myvector.begin(); it!=myvector.end(); ++it) cout << " " << *it; cout << endl; it=unique_copy (myvector.begin(), it, myvector.begin(),

myfunction); myvector.resize( it - myvector.begin() );


cout << endl;

return 0;}

10 20 30 40 30 10 0 0 0 0

0 0 0 0 10 10 20 30 30 40

0 10 20 30 40

reverse• template <class

BidirectionalIterator> void reverse ( BidirectionalIterator first, BidirectionalIterator last);

• Inverseaza ordinea elementelor dintre [first,last)



for (int i=1; i<10; ++i) myvector.push_back(i);

reverse(myvector.begin(),myvector.end();


cout << endl;

return 0;}

9 8 7 6 5 4 3 2 1

reverse_copy• template <class

BidirectionalIterator, class OutputIterator> OutputIterator reverse_copy ( BidirectionalIterator first, BidirectionalIterator last, OutputIterator result );

• Copiaza elementele dintre [first,last) in ordine inversa incepand de la result


int main () { int myints[] ={1,2,3,4,5,6,7,8,9}; vector<int> myvector(9); vector<int>::iterator it;

myvector.push_back(100); myvector.push_back(101); myvector.push_back(102);

reverse_copy (myints, myints+9, myvector.begin() );


cout << endl;

return 0;}

100 101 102

9 8 7 6 5 4 3 2 1 100 101 102

partition• template <class

BidirectionalIterator, class Predicate> BidirectionalIterator partition ( BidirectionalIterator first, BidirectionalIterator last, Predicate pred );

• Rearanjeaza elementele unei secvente astfel incat toate elementele pentru care un predicat returneaza true sunt asezate inaintea celor pt care returneaza false

• Returneaza un pointer spre cel de-al doilea grup


bool IsOdd (int i) { return (i%2)==1; }

int main () { vector<int> myvector; vector<int>::iterator it, bound;

for (int i=1; i<10; ++i) myvector.push_back(i); // 1 2 3 4

5 6 7 8 9

bound = partition (myvector.begin(), myvector.end(), IsOdd);

cout << "odd members:"; for (it=myvector.begin(); it!=bound; ++it) cout << " " << *it;

cout << "\neven members:"; for (it=bound; it!=myvector.end(); ++it) cout << " " << *it;

cout << endl;

return 0;}

1 9 3 7 5

6 4 8 2

Sortare

• sort

• stable_sort

• partial_sort

• partial_sort_copy

• n_th_element

sort/stable_sort• template <class RandomAccessIterator>

void sort ( RandomAccessIterator first, RandomAccessIterator last );

• template <class RandomAccessIterator, class Compare> void sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp );

• Sorteaza elementele dintre first si last in ordine crescatoare sau folosind un criteriu comp

• Compare – obiect de tipul functie de comparare care ia ca argumente 2 obiecte de tipul templateului si returneaza true daca primul argument<al doilea argument

• Stable_sort asigura faptul ca elementele cu valori egale raman pe pozitii


bool myfunction (int i,int j) { return (i<j); }

struct myclass { bool operator() (int i,int j) { return (i<j);}} myobject;

int main () { int myints[] = {32,71,12,45,26,80,53,33}; vector<int> myvector (myints, myints+8); vector<int>::iterator it;

// operator < sort (myvector.begin(), myvector.begin()+4);

// folosire functii pentru comparare sort (myvector.begin()+4, myvector.end(), myfunction);

// folosire obiecte pt comparare sort (myvector.begin(), myvector.end(), myobject);


cout << endl;

return 0;}

Tipul functie de comparatie

32 71 12 45 26 80 53 33

(12 32 45 71)26 80 53 33

12 32 45 71(26 33 53 80)

(12 26 32 33 45 53 71 80)

partial_sort• template <class

RandomAccessIterator> void partial_sort ( RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last );

• T• emplate <class

RandomAccessIterator, class Compare> void partial_sort ( RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp );

• Sorteaza elementele din domeniul [first,last) astfel incat elementele din [first, middle) contine elementele sortate crescator, iar restul nu sunt ordonate



int main () { int myints[] = {9,8,7,6,5,4,3,2,1}; vector<int> myvector (myints, myints+9); vector<int>::iterator it; partial_sort (myvector.begin(),

myvector.begin()+5, myvector.end());

cout << "myvector contains:"; for (it=myvector.begin(); it!=myvector.end(); ++it) cout << " " << *it; cout << endl;

partial_sort (myvector.begin(), myvector.begin()+5, myvector.end(),myfunction);


cout << endl;

return 0;}

1 2 3 4 5 9 8 7 6

1 2 3 4 5 9 8 7 6

partial_sort_copy• 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 );

• Copiaza elementele din domeniul [first,last) in domeniul [result_first, result_last), sortand elementele copiate



int main () { int myints[] = {9,8,7,6,5,4,3,2,1}; vector<int> myvector (5); vector<int>::iterator it;

// operator < partial_sort_copy (myints, myints+9,

myvector.begin(), myvector.end());

// using function as comp partial_sort_copy (myints, myints+9,

myvector.begin(), myvector.end(), myfunction);


cout << endl;

return 0;}

1 2 3 4 5

n_th_element• 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)

• Rearanjeaza elementele dintre first si last astel incat nth va reprezenta elementul de pe pozitia n intr-o ordonare crescatoare a elementelor, fara a garanta ca elementele anterioare sau posterioare ar fi ordonate




for (int i=1; i<10; i++) myvector.push_back(i); // 1 2 3 4 5 6 7 8 9

//random_shuffle (myvector.begin(), myvector.end());

//(operator <): nth_element (myvector.begin(), myvector.begin()+5,

myvector.end());

// using function as comp nth_element (myvector.begin(), myvector.begin()+5,

myvector.end(),myfunction);


cout << endl;

return 0;}

Cautare binara

• lower_bound

• upper_bound

• equal_range

• binary_search

lower_bound/upper_bound• 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 );

• Returneaza un iterator spre primul element din intervalul [first,last) care e >= value sau <value


int main () { int myints[] = {10,20,30,30,20,10,10,20}; vector<int> v(myints,myints+8); vector<int>::iterator low,up;

sort (v.begin(), v.end()); low=lower_bound (v.begin(), v.end(), 20); up= upper_bound (v.begin(), v.end(), 20); cout << "lower_bound at position " << int(low-

v.begin()) << endl; cout << "upper_bound at position " << int(up -

v.begin()) << endl;

return 0;}

lower_bound at position 3upper_bound at position 6

binary_search• 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 );

• Verifica daca value apartine domeniului [first, last) care trebuie sa fie sortat


bool myfunction (int i,int j) { return (i<j); }class myCmp {public:int operator()(const int i, const int j){return i<j;}}myComp;

int main () { int myints[] = {1,2,3,4,5,4,3,2,1}; vector<int> v(myints,myints+9); // using default comparison: sort (v.begin(), v.end());

cout << "looking for a 3... "; if (binary_search (v.begin(), v.end(), 3)) cout << "found!\n"; else cout << "not found.\n";

// using myfunction as comp: sort (v.begin(), v.end(), myfunction);

cout << "looking for a 6... "; if (binary_search (v.begin(), v.end(), 6, myComp)) cout << "found!\n"; else cout << "not found.\n";

return 0;}

Algoritmi de Interclasare• merge

• inplace_merge

• includes

• set_union

• set_intersection

• set_difference

• set_symmetric_difference

merge• Interclaseaza 2 secvente

ordonate

• 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 );


int main () { int first[] = {5,10,15,20,25}; int second[] = {50,40,30,20,10}; vector<int> v(10); vector<int>::iterator it;

sort (first,first+5); sort (second,second+5); merge (first,first+5,second,second+5,v.begin());

cout << "The resulting vector contains:"; for (it=v.begin(); it!=v.end(); ++it) cout << " " << *it;


inplace_merge• Interclaseaza 2 secvente

consecutive

• 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 );

#include <algorithm>#include <vector>using namespace std;

int main () { int first[] = {5,10,15,20,25}; int second[] = {50,40,30,20,10}; vector<int> v(10); vector<int>::iterator it;

sort (first,first+5); sort (second,second+5);

copy (first,first+5,v.begin()); copy (second,second+5,v.begin()+5);

inplace_merge (v.begin(),v.begin()+5,v.end());

cout << "The resulting vector contains:"; for (it=v.begin(); it!=v.end(); ++it) cout << " " << *it;


first middle last

includes• 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 );

• Verifica daca toate elementele din domeniul [first1,last1) se regasesc in domeniul [first2,last2)

#include <iostream>#include <algorithm>using namespace std;

bool myfunction (int i, int j) { return i<j; }

int main () { int container[] = {5,10,15,20,25,30,35,40,45,50}; int continent[] = {40,30,20,10}; int continent1[] = {40,30,20,10,9};

sort (container,container+10); sort (continent,continent+4); sort (continent1,continent1+5);

// using default comparison: if ( includes(container,container+10,continent,continent+4) ) cout << "container includes continent!" << endl;

// using myfunction as comp: if ( includes(container,container+10,continent,continent+4,

myfunction) ) cout << "container includes continent!" << endl;

if ( includes(container,container+10,continent1,continent1+5)) cout << "container includes continent1!" << endl; else cout << "container does not include continent1!" << endl; return 0;}

Set_union/intersection/difference/symmetric_difference

• Realizeaza reuniunea, intersectia, diferenta si diferenta simetrica a doua domenii sortate

• Returneaza un iterator la sfarsitul secventei obtinute ca rezultat


int main () { int first[] = {5,10,15,20,25}; int second[] = {50,40,30,20,10}; vector<int> reun(10); vector<int>::iterator it;

sort (first,first+5); sort (second,second+5); it=set_union (first, first+5, second, second+5, reun.begin()); cout<<"UNION:"<<endl; for(vector<int>::iterator it1=reun.begin();it1!=it;it1++) cout<<*it1<<" "; cout<<endl;

cout<<"INTERSECTION:"<<endl; vector<int> inters(10); it=set_intersection (first, first+5, second, second+5, inters.begin()); for(vector<int>::iterator it1=inters.begin();it1!=it;it1++) cout<<*it1<<" "; cout<<endl;

vector<int> diff(10); it=set_difference (first, first+5, second, second+5, diff.begin()); cout<<"DIFFERENCE: "; for(vector<int>::iterator it1=diff.begin();it1!=it;it1++) cout<<*it1<<" "; cout<<endl;

vector<int> symDiff(10); it=set_symmetric_difference (first, first+5, second, second+5,

symDiff.begin()); cout<<"SYMMETRIC DIFFERENCE: "; for(vector<int>::iterator it1=symDiff.begin();it1!=it;it1++) cout<<*it1<<" "; cout<<endl;

return 0;}

UNION:5 10 15 20 25 30 40 50INTERSECTION:10 20DIFFERENCE: 5 15 25SYMMETRIC DIFFERENCE: 5 15 25 30 40 50

Algoritmi pentru heap-uri

• push_heap

• pop_heap

• make_heap

• sort_heap

Operatii pe heap#include <iostream>#include <algorithm>#include <vector>using namespace std;

int main () { int myints[] = {10,20,30,5,15}; vector<int> v(myints,myints+5); vector<int>::iterator it;

make_heap (v.begin(),v.end()); cout << "initial max heap : " << v.front() << endl;

pop_heap (v.begin(),v.end()); v.pop_back(); cout << "max heap after pop : " << v.front() << endl;

v.push_back(99); push_heap (v.begin(),v.end()); cout << "max heap after push: " << v.front() << endl;

sort_heap (v.begin(),v.end());

cout << "final sorted range :"; for (unsigned i=0; i<v.size(); i++) cout << " " << v[i];

cout << endl;

return 0;}

30 20 15 10 5

20 15 10 5 30 20 15 10 5

20

99 20 15 10 5

5 10 15 20 99

Algoritmi de mimin/maxim

• min

• max

• min_element

• max_element

• lexicographical_compare

• next_permutation

• prev_permutation

min_element/max_element#include <iostream>#include <algorithm>using namespace std;

bool myfn(int i, int j) { return i<j; }struct myclass { bool operator() (int i,int j) { return i<j; }} myobj;

int main () { int myints[] = {3,7,2,5,6,4,9};

cout << "The smallest element is " << *min_element(myints,myints+7) << endl;

cout << "The largest element is " << *max_element(myints,myints+7) << endl;

// using function myfn as comp: cout << "The smallest element is " <<

*min_element(myints,myints+7,myfn) << endl; cout << "The largest element is " <<

*max_element(myints,myints+7,myfn) << endl;

// using object myobj as comp: cout << "The smallest element is " <<

*min_element(myints,myints+7,myobj) << endl; cout << "The largest element is " <<

*max_element(myints,myints+7,myobj) << endl;

return 0;}

• Returneaza un iterator la elementul minim/maxim din domeniu

• template <class ForwardIterator> ForwardIterator min_element ( ForwardIterator first, ForwardIterator last );

• template <class ForwardIterator, class Compare> ForwardIterator min_element ( ForwardIterator first, ForwardIterator last, Compare comp );

lexicographical_compare

• Comparare lexicala a elementelor a doua secvente

• 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 );

#include <iostream>#include <algorithm>#include <cctype>using namespace std;

// a case-insensitive comparison function:bool mycomp (char c1, char c2){ return tolower(c1)<tolower(c2); }

int main () { char first[]="Apple"; // 5 letters char second[]="apartment"; // 9 letters

cout << "Using default comparison (operator<): "; if (lexicographical_compare(first,first+5,second,second+9)) cout << first << " is less than " << second << endl; else if (lexicographical_compare(second,second+9,first,first+5)) cout << first << " is greater than " << second << endl; else cout << first << " and " << second << " are equivalent\n";

cout << "Using mycomp as comparison object: "; if

(lexicographical_compare(first,first+5,second,second+9,mycomp))

cout << first << " is less than " << second << endl; else if

(lexicographical_compare(second,second+9,first,first+5,mycomp))

cout << first << " is greater than " << second << endl; else cout << first << " and " << second << " are equivalent\n"; return 0;}

prev_permutation/next_permutation• Genereaza urmatoarea/anterioara

permutare (ordonate lexicografic)#include <iostream>#include <algorithm>using namespace std;

int main () { int myints[] = {1,2,3};

cout << "The 3! possible previous permutations with 3 elements:\n";

sort (myints,myints+3); reverse (myints,myints+3);

do { cout << myints[0] << " " << myints[1] << " " <<

myints[2] << endl; } while ( prev_permutation (myints,myints+3) );

int my2ints[] = {7,8,9};

cout << "The 3! possible next permutations with 3 elements:\n";

sort (my2ints,my2ints+3);

do { cout << my2ints[0] << " " << my2ints[1] << " " <<

my2ints[2] << endl; } while ( next_permutation (my2ints,my2ints+3) );

The 3! possible previous permutations with 3 elements:3 2 13 1 22 3 12 1 31 3 21 2 3

The 3! possible next permutations with 3 elements:7 8 97 9 88 7 98 9 79 7 89 8 7

Tipul de data string

• Un tip special de container

• Capacitate:– Size, length, max_size, resize, capacity,

reserve, clear, empty

• Acces la elemente: [], at

• Modificatori:– +=, append, push_back,assign, insert, erase,

replace, copy, swap

Operatii specifice stringurilor• c_str

– Returneaza reprezentarea C corespunzatoare (cu \0 la sfarsit)• data

– Returneaza vectorul de caractere fara \0 la sfarsit• find

– Cauta prima aparitie a unui caracter/string• rfind

– Cauta ultima aparitie a unui caracter/string• find_first(last)_of

– Cauta in string oricare din caracterele date ca parametru • find_firt(last)_not_of

– Cauta in string primul caracter care nu apare in parametru• substr

– Returneaza un string care este un substring al obiectului curent• compare

– Compara 2 stringuri (~strcmp)

Exemplu stringuri#include <string>#include <iostream>using namespace std;

main(){ string a("abcd efg"); string b("xyz ijk"); string c;

cout << a << " " << b << endl; // Output: abcd efg xyz ijk

cout << "String empty: " << c.empty() << endl; // String empty: 1 c = a + b; // concatenation cout << c << endl; // abcd efgxyz ijk cout << "String length: " << c.length() << endl; // String length: 15 cout << "String size: " << c.size() << endl; // String size: 15 cout << "String capacity: " << c.capacity() << endl; // String capacity: 15 cout << "String empty: " << c.empty() << endl; // String empty: 0 string d = c; cout << d << endl; // abcd efgxyz ijk

// First character: a cout << "First character: " << c[0] << endl; string f(" Leading and trailing blanks "); cout << "String f:" << f << endl; cout << "String length: " << f.length() << endl; // String length: 37 cout << "String f:" << f.append("ZZZ") << endl; // String f: Leading

and trailing blanks ZZZ cout << "String length: " << f.length() << endl; // String length: 40

string g("abc abc abd abc"); cout << "String g: " << g << endl; // String g: abc abc abd abc cout << "Replace 12,1,\"xyz\",3: " << g.replace(12,1,"xyz",3) << endl; // Replace 12,1,"xyz",3: abc abc abd xyzbc

cout << g.replace(0,3,"xyz",3) << endl; // xyz abc abd xyzbc cout << g.replace(4,3,"xyz",3) << endl; // xyz xyz abd xyzbc cout << g.replace(4,3,"ijk",1) << endl; // xyz i abd xyzbc cout << "Find: " << g.find("abd",1) << endl; // Find: 6 cout << g.find("qrs",1) << endl;

string h("abc abc abd abc"); cout << "String h: " << h << endl; cout << "Find \"abc\",0: " << h.find("abc",0) << endl; // Find "abc",0:

0 cout << "Find \"abc\",1: " << h.find("abc",1) << endl; // Find "abc",1:

4 cout << "Find_first_of \"abc\",0: " << h.find_first_of("abc",0) <<

endl; // Find_first_of "abc",0: 0 cout << "Find_last_of \"abc\",0: " << h.find_last_of("abc",0) << endl;

// Find_last_of "abc",0: 0 cout << "Find_first_not_of \"abc\",0: " <<

h.find_first_not_of("abc",0) << endl; // Find_first_not_of "abc",0: 3

cout << "Find_first_not_of \" \": " << h.find_first_not_of(" ") << endl; // Find_first_not_of " ": 0

cout << "Substr 5,9: " << h.substr(5,9) << endl; // Substr 5,9: bc abd ab

cout << "Compare 0,3,\"abc\": " << h.compare("abc“,0,3) << endl; // Compare 0,3,"abc": 0

cout << "Compare 0,3,\"abd\": " << h.compare("abd“,0,3) << endl; // Compare 0,3,"abd": -1

cout << h.assign("xyz",0,3) << endl; // xyz cout << "First character: " << h[0] << endl; // Strings start with 0 //

First character: xreturn 0;}

Retrospectiva POO• Abstractizare+incapsulare+ascundere informatie:

– void*, pointeri– clase+polimorfism

• tilizarea interfetelor in programare

• principiul substitutiei

• legarea intarziata

– Template

• Exceptii

• Sabloane de proiectare:Singleton, Adapter, Iterator

Examen scris

• Conditie eliminatorie: Nota 5 la laborator!!!

• 1p oficiu

• Teorie:– Grila -1p (raspuns corect+argumentare)– Sinteza – 2p

• Problema:– 6 p

MULTUMESC!

SUCCES!

STL (Standard Template Library)

Documents

Transcript of STL (Standard Template Library)