Skip to content

Latest commit

 

History

History
182 lines (163 loc) · 6.03 KB

POO_22_C_2022-06-02.md

File metadata and controls

182 lines (163 loc) · 6.03 KB

STL

Standard Template Library - dupa cum ii spune si numele, STL este o biblioteca standard, generica pentru iteratori, containere, algoritmi, obiecte de tip functie, alocare de memorie, etc.

iteratori

Un interator este folosit pentru a parcurge, a itera o lista de obiecte. Interatorul este conceput a fi ca functionalitate in C++ asemanator cu un pointer, in consecinta, pentru interatori avem urmatorii operatori:

it++
it--
*it //returneaza o referinta catre obiectul curent

Tipuri de iteratori:

  • Input_Iterator
  • Output_Iterator
  • ForwardIterator (merge doar catre dreapta)
  • BidirectionalIterator
  • RandomAccessIterator

containere

In aceasta categorie includem structuri de date standard, cum ar fi:

  • vector
  • list
  • set (multime)
  • map
  • hash
  • stack
  • queue
  • priority_queue
#include "vector"

Metodele clasei vector din STL:

  • begin: returneaza un iterator catre pointeaza catre prima componenta a vectorului
  • end: returneaza interator catre componenta ce ar trebui sa fie dupa ultima
  • empty: verifica daca este gol (nu are componente)
  • erase: primeste un parametru de tip iterator catre o componenta pe care o sterge (o elimina din vector); exista si erase cu doi parametri care sterge elementele de la start pana la final
  • clear: curata vectorul (elimina toate componentele)
  • resize: redimensioneaza vectorul la lungimea primita ca parametru
  • insert: primeste doi parametri: un interator si o o valoare pe care o insereaza pe pozitia indicata de operator
  • push_back: adauga la sfarsit valoarea primita ca parametru
  • pop_back: scoate ultima componenta din vector si scade dimensiunea size
  • size: returneaza numarul de componente al vectorului
  • capacity: returneaza numarul de casute de memorie alocate pentru vector

Operatori:

=
[]
==

Algorithm

In STL avem implementati algoritmii standard pe care ii putem imparti in mai multe categorii:

  • non-mutated: fara mutare: find, count, search, equal
  • mutated: replace, copy, swap, generate, fill, reverse, rotate, particion
  • sorting: sort, binary_search, merge, set
  • operatii cu heapuri: min, max, permutation, compare Pentru a folosi algoritmii din STL trebuie sa includem fisierul antet:
#include "algorithm"
int a[100];
vector<int> v;
...
sort(a, a + n);
sort(a + k, a + h); //sortez de la pozitia lui k pana
					//inainte de pozitia lui h
binary_search(first, last, v);
					// se cauta v intre first si pana 
					// inainte de last si returneaza
					// un bool
lower_bound(first, last, v);
upper_bound(first, last, v);
					// returneaza iterator catre 
					// pozitia gasita
	// in cazul in care lower_bound sau upper_bound
	// nu gaseste valoarea v, se returneaza iterator
	// catre componenta care s-ar afla inaite/dupa v, 
	// daca v s-ar insera

instructiunea for aplicata pe un domeniu finit (range based for)

for(it:container)
for(&it:cont)
vector<int> v;

for(int i = 0; i < size; i++)
	cout << v[i] << endl;

for(int c:v)
	cout << c << endl;
// c se initializeaza succesiv cu valorile componentelor 
// vectorului v

// pentru modificare:
for(int &c:v)
	c++;
// incrementam fiecare componenta a vectorului v
// c = referinta succesiva pentru elemente

auto

Putem declara variabile ca fiind auto. In aceasta situatie, compilatorul identifica tipul variabilei respective din contextul programului.

int x = 1;
auto y = x + 1.1;
// la compilare, se va identifica tipul lui y ca fiind 
// double , deoarece 1.1 este de tip double

for(auto &c:v)
	c++;

Este contraindicat a se exagerat cu folosirea tipului auto.

Expresii lambda

O lambda exresie se defineste sub forma:

[...](...) -> tip_returnat {implemetare} (...)
  1    2           3             4         5

Prima sectiune poarta denumirea de zona de conditii de captare a variabilelor. A doua sectiune reprezinta parametri expresiei. A cincea sectiune: se pot da optional valori pentru parametri (initializeaza parametri din sectiunea 2). Desi se implementeaza diferit fata de o functie, din cauza structurii, o lambda expresie se evalueaza absolut asemanator cu un apel de functie. In sectiunea 1 pot fi enumerate variabilele ce sunt vizibile in corpul expresiei (sectiunea 4). Orice variabila enumerata este accesibila in sectiunea 4 prin valoare sau prin referinta. Daca in prima sectiune in enumerare apare =, atunci, toate variabilele ce nu sunt enumerate in aceasta sectiune sunt vizibile in expresie prin valoare. Daca in enumerare apare & in enumerare, toate variabilele ce nu se enumera in prima sectiune sunt vizibile in expresie prin referinta. Daca o functie in C/C++ nu poate fi implementata in interiorul altei functii, o lambda expresie poate aparea in corpul unei functii. Tipul returnat nu este obligatoriu a fi specificat, mai ales daca lambda expresia nu returneaza nicio valoare. Mai mult, putem omite tipul returnat, lambda expresia returneaza o valoare, a carui tip, daca nu este specificat explicit, se deduce din context.

void main()
{
	int x, y;
	cin >> x >> y;
	auto cmmdc = [](int a, int b)
	{
		int r;
		for(;b;r = a % b, a = b, b = r)
		return a;
	};
	cout << cmmdc(x, y) << endl;
				// 5
	// dupa denumirea lambda expresiei, intre paranteze
	// se dau valorile pentru parametri, care devin
	// practic sectiunea 5, care nu a fost data pentru
	// cmmdc 

	cout << cmmdc(x + 1, y - 1) << endl;
}
int a = 1, b = 2, c = 3, d = 4;
auto e1 = [a,b](int x) {return a * x + b;};
						// a si b nu pot fi modifica
						// a++ <- incorect
auto e2 = [&,b](int x) {return ;};
	// toate variabilele sunt cunoscute in lambda 
	// expresie si pot fi modificate, cu exceptia lui b
auto e3 = [=,&a](int x) {a++; return a * x + b - c + d;};
	// corect
	// a, b, c, d sunt cunoscute in expresie
	// doar a poate fi modificata
auto e4 = [=]...
	// toata variabilele sunt cunoscute, 
	// dar nu pot fi modificate
auto e5 = [&]...
	// toata variabilele sunt cunoscute
	// si pot fi modificate
vector<int> v;
...
int* p = &v[0];