Articole

Acest articol conține o listă cu probleme propuse pentru examenul de bacalaureat la care se cer soluții eficiente din punct de vedere a memoriei utilizate și/sau a timpului de execuție (punctul III.3).
Problemele pot fi filtrate folosind butoanele de mai sus!

12
4 6 3 7 8 1 6 2 7 9 10 8

4 6 6 7 8 8 8 8 8 9 10 10

4  1 10
1 16  1
4  2  8
2  1  5
1  5  2

5
2 10 5 20 21 0 10 60 15 3 9 20 20 5 45

Să se afişeze cel mai mare număr format din cifrele numărului luate o singură dată.

Stars and bars (Stele și bare) este o metodă de rezolvare a unor probleme de combinatorică. Se poate folosi când trebuie să determinăm numărul de modalități de a grupa un număr dat de obiecte identice.

Teoremă: Numărul de a variante de a plasa n obiecte identice în k cutii este egal cu: \( C_{n+k-1}^{k-1} \).

Demonstrația implică separarea celor n obiecte (stele) în k cutii prin k-1 bare – de unde și numele. De exemplu, configurația următoare are n=7 stele și k=4 cutii: \( \star \vert \star \star \vert \vert \star \star \star \star \) și corespunde următoarei situații:

• prima cutie conține un obiect
• a doua cutie conține două obiecte
• a treia cutie nu conține niciun obiect
• a patra cutie conține patru obiecte

Confiurația este echivalentă cu următoarea configurație de biți: 0100110000, în care bitul 1 corespunde obiectului, \( \star \), iar 1 corespunde barei, \( \vert \). Toate configurațiile convenabile au n-k+1 biți, dintre care n au valoarea 0 și k-1 au valoarea 1 și corespund submuțimilor cu k-1 elemnte ale unei mulțimi cu n+k-1 elemente.

Astfel, numărul lor este \( C_{n+k-1}^{k-1} \).

Consecință Ecuația \(x_1 + x_2 + x_3 + \cdots + x_k = n\) are \( C_{n+k-1}^{k-1} \) soluții întregi nenegative (mai mari sau egale cu 0).

Afirmația este echivalentă cu teorema de mai sus, în care \(x_i\) fiind egal cu numărul de obiecte din cutia i.

Teoremă: Numărul de a variante de a plasa n obiecte identice în k cutii astfel încât fiecare cutie conține cel puțin un obiect este egal cu: \( C_{n-1}^{k-1} \).

Demonstrația 1: Fixăm în fiecare cutie câte un obiect. Rămân \(n – k\) obiecte care trebuie plasate în \(k\) cutii, în condițiile teoremie de mai sus. Astfel, numărul de variante este \( C_{n-k+k-1}^{k-1} = C_{n-1}^{k-1} \).

Demonstrația 2: Folosim metoda Stars and bars. Separarea obiectelor în cutii se face plasând \(k\) bare în golurile dintre obiecte. Sunt \(n-1\) goluri în care putem plasa \(k\) bare în \( C_{n-1}^{k-1} \) moduri.

Coada de priorități este o structură de date de tip coadă, în care se fac operații de inserare și eliminare, dar ordinea nu este cea a cozii obișnuite. Fiecare element are asociată o anumită prioritate (de exemplu chiar valoarea sa), iar elementul de la începutul cozii este cel cu prioritate maximă, el fiind și cel care va fi eliminat din coadă în cazul operației de eliminare a unui element.

Cozile de priorități pot fi implementate sub formă de heap-uri, iar STL contine containerul adaptor priority_queue. Tehnic priority_queue implementează în mod implicit un max-heap.

Operația de determinare a elementului maxim are complexitate constantă, in timp ce operațiile de inserare și eliminare au complexități logaritmice în raport cu numărul de elemente.

Declarare

Clasa priority_queue este o clasă template definită în headerul queue:

#include <queue>

O putem declara ca în exemplul următor:

priority_queue<int> H;

Implicit, priority_queue-ul este un max-heap (elementul maxim are prioritate maximă) și se implementează pe baza operației < (less<int>)). Dacă dorim să gestionăm un min-heap (elementul minim să aibă prioritate maximă) vom folosi următoarea declarație:

priority_queue<int , vector<int> , greater<int> > H;

Similar, putem crea cozi de priorităti cu elemente de tipuri oarecare T. Condiția este să fie definit pentru tipul T operatorul < (functorul less<T>), sau să construim un functor de comparare.

struct fcmp
{	bool operator()(const T & a , const T & b)
	{
		//returneaza true daca si numai daca a este strict in fata lui b in ordinea dorita
	}
};
priority_queue<T , vector<T> , fcmp > H;

Operații de bază

Fie următoarea coadă de priorități:

priority_queue<T> H;
T v;

Adăugarea unui element

priority_queue<T> H;
T v;
H.push(v);

Se adaugă în coadă elementul v. Elementele se reorganizează pentru se păstra proprietate de heap (elementul maxim să fie la început).

Ștergerea unui element

priority_queue<T> H;
H.pop();

Se șterge din coadă elementul de la început. Elementele se reorganizează pentru se păstra proprietate de heap.

Determinarea elementului din vârf

priority_queue<T> H;
T v;
v = H.top();

Returnează o referință la elementul de la începutul cozii. Elementul se va elimina numai la apelul metodei pop().

Stabilirea faptului că este coada vidă

priority_queue<T> H;
H.empty()

Returnează true dacă H este o coadă vidă și false în caz contrar.

Dimeniunea cozii

priority_queue<T> H;
H.size()

Returnează numărul de elemente din coada de priorități H.

Atribuirea

Conținutul unei cozi de priorități poate fi copiat în altă coadă de același tip prin operatorul de atribuire =.

priority_queue<T> A , B;
...
A = B;

Exemple

Considerăm următoarea problemă;

Se dau coordonatele întregi ale unor puncte în plan. Să se afișeze coordonatele în ordinea crescătoare a absciselor, iar la abscise egale în ordinea crescătoare a ordonatelor.

Următoarele soluții se bazează pe o coadă de priorități în care adăugăm toate punctele, apoi le extragem și le afișăm.

Soluția 1

Pentru memorarea unui punct folosim o structură (clasă) definită în mod adecvat. Pentru stabilirea ordinii între puncte folosim un functor, iar pentru afișarea coordonatelor folosim o funcție prietenă.

#include <iostream>
#include <queue>

using namespace std;

struct Punct{
	int x , y;
	Punct(int a = 0, int b = 0){ x  = a , y = b;}
	friend ostream & operator<<(ostream & os , Punct A)
	{
		os << "(" << A.x << "," << A.y << ")";
		return os;
	}
};

struct fcmp
{	bool operator()(const Punct & a , const Punct & b)
	{
		if(a.x > b.x)
			return true;
		if(a.x < b.x)
			return false;
		if(a.y > b.y)
			return true;
		return false;
	}
};

int main()
{
	priority_queue<Punct, vector<Punct>, fcmp> H;
	H.push(Punct(6,1));
	H.push(Punct(2,7));
	H.push(Punct(2,4));
	H.push(Punct(4,10));
	H.push(Punct(7,4));
	while(! H.empty())
		cout << H.top() << '\n', H.pop();
	return 0;
}

Soluția 2

În acestă soluție nu folosim un functor pentru comparare, ci supraîncărcăm operatorul < printr-o functie prietenă.

#include <iostream>
#include <queue>

using namespace std;

struct Punct{
	int x , y;
	Punct(int a = 0, int b = 0){ x  = a , y = b;}
	friend ostream & operator<<(ostream & os , const Punct & A)
	{
		os << "(" << A.x << "," << A.y << ")";
		return os;
	}
	friend bool operator<(const Punct & A , const Punct & B)
	{
		if(A.x > B.x)
			return true;
		if(A.x < B.x)
			return false;
		if(A.y > B.y)
			return true;
		return false;
	}
};

int main()
{
	priority_queue<Punct> H;
	H.push(Punct(6,1));
	H.push(Punct(2,7));
	H.push(Punct(2,4));
	H.push(Punct(4,10));
	H.push(Punct(7,4));
	while(! H.empty())
		cout << H.top() << '\n', H.pop();
	return 0;
}

Soluția 3

Pentru memorare punctelor folosim clasa pair. Clasa pair are definit operatorul mai mic, acesta verificând ordinea lexicografică pentru membrii first și second.

#include <iostream>
#include <queue>

using namespace std;

int main()
{
	priority_queue <
		pair<int,int>,
		vector<pair<int,int>>,
		greater<pair<int,int>>
		> H;
	H.push({6,1});
	H.push({2,7});
	H.push({2,4});
	H.push({4,10});
	H.push({7,4});
	while(! H.empty())
		cout << "(" << H.top().first << "," << H.top().second << ")" << '\n', H.pop();
	return 0;
}

Declararea de mai sus trebuie făcută în acest mod, pentru a obține un min-heap. Dacă am fi folosit declararea:

priority_queue <pair<int,int> > H;

s-ar fi implementat (pe baza functorului less<pair<int,int>>) un max-heap, în care elementele de prioritate maximă ar fi fost acela care au câmpul first mai mare.

bitset este un container special din STL care permite lucrul cu șiruri de biți. Aceștia sunt memorați eficient, pentru un bit din șir folosindu-se un bit în memorie. Astfel, spațiul de memorie ocupat de un bitset cu M biți este mai mic decât un tablou bool V[M]; sau un vector cu elemente de tip bool, dar numărul de biți M din bitset trebuie să fie cunoscut în momentul compilării, deci trebuie să fie o contantă.

Pot fi folosiți de exemplu pe post de vectori caracteristici, dar suportă și operațiile pe biți cunoscute pentru tipurile întregi.

Declararea

Pentru a folosi containerul bitset trebuie inclus headerul bitset:

#include <bitset>

Declararea se face astfel:

const int M = 16;
bitset<M> B = 30;

Operații elementare

Afișarea

const int M = 16;
bitset<M> B = 30;
cout << B << endl;

Observații:

• M este constantă. Lipsa modificatorului const duce la o eroare de compilare.
• Când afișăm bitsetul, se afișează toți cei M biți.

Indexarea

Biții din bitset sunt indexați de la 0 și pot fi accesați prin operatorul []. Bitul cel mai nesemnificativ (cel mai din dreapta) este B[0], iar bitul cel mai semnificativ este B[M-1], unde M este dimensiunea bitsetului.

const int M = 16;
bitset<M> B = 30; // 0000000000011110
B[6] = 1;
cout << B;        // 0000000001011110

Compararea

Două containere bitset de aceeași dimensiune pot fi comparate cu operatorii == și !=.

Notă: operația != este eliminată în C++20.

Atribuirea

Putem să-i atribuim unui bitset valoarea unui întreg sau valoarea unui alt bitset. Prin atribuirea unui întreg, biții din bitsetul B devin identici cu biții din reprezentarea în memorie a valorii întregi care se atribuie:

const int M = 16;
bitset<M> B, A;
B = -30;
cout << B << endl; // 1111111111100010
B = 5;
cout << B << endl; // 0000000000000101
A = B;
cout << A << endl; // 0000000000000101

Manipularea biților

Numărarea bitilor setați, numărul total de biți

Pentru a afle câți biți din bitset sunt setați (au valoarea 1), folosim metoda count(). Pentru a determina numărul total de biți, folosim metoda size(). Numărul biților nesetați (cu valoarea 0), facem diferența celor două.

const int M = 16;
bitset<M> B = 63;
cout << B.count() << endl; // 6
cout << B.size() << endl; // 16

Determinarea valorii unui bit

Se face cu metoda test(k), unde k reprezintă numărul de ordine al bitului dorit (de la dreapta spre stânga, incepând de la 0), iar rezultatul este 1 sau 0.

const int M = 16;
bitset<M> B = 63;
cout << B << endl; // 0000000000111111
cout << B.test(5) << endl; // 1
cout << B.test(6) << endl; // 0

Set, reset, flip

Bitsetul oferă metode pentru:

• setarea unui bit precizat:
  • B.set(k) dă valoarea 1 pentru B[k]
  • B.set(k , r) dă valoarea r pentru B[k]
  • B.set() dă valoarea 1 pentru toți biții din B
• resetarea unui bit precizat:
  • B.reset(k) dă valoarea 0 pentru B[k]
  • B.reset() dă valoarea 0 pentru toți biții din B
• schimbarea valoare biților (din 1 devine 0, iar din 0 devine 1):
  • B.flip(k) schimbă valoarea lui B[k]
  • B.flip() schimbă valorile pentru toți biții din B

bitset<M> B;
B = 63;
cout << B << endl; // 0000000000111111
//bitii se numeroteaza de la dreapta, incepand cu 0
B.reset(5);
B.set(10);
B.set(9 , 1);
B.set(3 , 0);
B.flip(2);
cout << B << endl; // 0000011000010011
B.flip();
cout << B << endl; // 1111100111101100
B.set();
cout << B << endl; // 1111111111111111
B.reset();
cout << B << endl; // 0000000000000000

Operații pe biți

Operatii logice pe biți

Clasa bitset suportă operatorii logici pe biți (~, &, |, ^).

bitset<M> B, A;
B = -60; A = 5;
cout << "A     = " << A << endl;		// 0000000000000101
cout << "B     = " << B << endl;		// 1111111111000100
cout << "~B    = " << ~B << endl;		// 0000000000111011
cout << "A & B = " << (A & B) << endl;	// 0000000000000100
cout << "A | B = " << (A | B) << endl;	// 1111111111000101
cout << "A ^ B = " << (A ^ B) << endl;	// 1111111111000001

Operatorii de deplasare

Clasa bitset suportă operatorii de deplasare a biților (<<, >>).

bitset<M> B;
int n = 4;
B = 7;
cout << "B      = " << B << endl;				// 0000000000000111
cout << "B << n = " << (B << n) << endl;		// 0000000001110000

Atribuiri

Clasa bitset suportă atriburile scurte: &=, |=, ^=, precum și <<=, >>=.

Fie A , B două containere bitset de aceași dimensiune și n un întreg. Atunci:

• A &= B este echivalent cu A = A & B;
• A |= B este echivalent cu A = A | B;
• A ^= B este echivalent cu A = A ^ B;
• A <<= n este echivalent cu A = A << n;
• A >>= n este echivalent cu A = A >> n;

Conversii

Bitset-ul poate fi convertit la

• string – to_string
  • B.to_string() – returnează un string conținând reprezentarea binară a lui B, formată formată din caractere 0 și 1;
  • B.to_string(c0) – returnează un string conținând reprezentarea binară a lui B, caracterele 0 fiind înlocuite cu caracterul c0;
  • B.to_string(c0 , c1) – returnează un string conținând reprezentarea binară a lui B, caracterele 0 și 1 fiind înlocuite cu caracterul c0, respectiv c1;
• întreg fără semn- to_ulong(), to_uulong()
  • B.to_ulong() – retunează un întreg fără semn pe 32 de biți (unsingned int, unsigned long) cu reprezentarea binară echivalentă cu configurația bitsetului B;
  • B.to_uulong() – retunează un întreg fără semn pe 64 de biți (unsigned long long) cu reprezentarea binară echivalentă cu configurația bitsetului B;
  • dacă valoarea întreagă corespunzătoare bitsetului nu poate fi reprezentată pe 32, respectiv 64 de biți, se va ridica o excepție de tip overflow_error.

Containerul C++ vector este, probabil, cel mai folosit container STL. Vectorii sunt tablouri dinamice cu elemente omogene care au proprietatea de a se redimensiona automat când se adaugă sau se șterge un element, gestionarea memoriei fiind realizată automat de către container.

Vectorii sunt stocați într-o zonă contiguă de memorie și pot fi traversați cu ajutorul iteratorilor. Elementele se adaugă, de regulă la sfârșit. Operația de adăugare ia, de regulă, timp constant, cu excepția cazului când spatiul de memorie alocat trebuie redimensionat (mărit). Ștergerea unui element ia întotdeauna timp constant. Inserarea și ștergerea la începutul sau în interiorul vectorului iau timp liniar.

Declararea unui vector

Trebuie inclus header-ul vector:

#include <vector>;

Declararea se face astfel:

vector<T> V;

unde T este un tip de date. Acesta va fi tipul elementelor vectorului. Vectorul declarat mai sus este vid – are 0 elemente.

Alternativ, putem declara vectorul astfel:

vector<T> V(n);

n este un întreg. Se va crea un crea un vector V cu n elemente. Valorile acestora sunt valorile implicite pentru datele de tip T. Pentru tipurile numerice, valoarea elementelor este 0.

vector<T> V(n, vT);

n este un întreg, iar vT este o dată de tip T. Se va crea un crea un vector V cu n elemente. Valorile acestora sunt copii ale lui vT.

De exemplu:

vector<int> A; // se crează un vector A cu zero elemente
cin >> n;
vector<int> B(n); // se crează un vector B cu n elemente, egale cu 0
cin >> x;
vector<int> C(n , x); // se crează un vector B cu n elemente, egale cu x

Atribuirea

Spre deosebire de tablourile standard C, vectorilor li se pot atribui valori în orice moment. Exemplu:

vector<int> A , B = {2 , 4, 6 , 8};
A = B;
A = {1 , 2 , 3 , 4 , 5};

Dimensiunea și capacitatea

Numărul de elemente din vector poate fi determinat cu funcția size():

vector<int> A = {2 , 4 , 6 , 8};
cout << A.size(); // 4

De regulă, memoria alocată pentru un vector este mai mare decât memoria folosită. Acest lucru se întâmplă pentru a se evita realocarea memoriei (operație costisitoare, care presupune copierea tuturor elementelor) de fiecare dată când se adaugă elemente.

Funcția capacity() returnează numărul de elemnte pe care le poate avea vectorul la momentul curent, fără a se realoca memoria. Are loc relația capacity() >= size(), iar numărul de elemente care pot fi adăugate fără realocare este capacity() - size().

Redimensionarea

Funcția resize() permite redimensionarea unui vector și are următoarele forme:

• V.resize(n); (1)
• V.resize(n , x); (2)

Vectorul V se redimensionează încât să aibă n elemente:

• dacă n < V.size(), în vector vor rămâne primele n elemente, celelalte vor fi șterse.
• dacă n > V.size(), în vector se vor adăuga n - V.size() elemente egale cu x , în cazul (2) sau egale cu valoarea implicită pentru tipul elementelor din vector, în cazul (1). Această valoare este 0 pentru tipurile numerice.

Adăugarea unui element

Adăugarea unui nou element în vector se face la sfârșit, cu funcția push_back():

vector<int> A;
for(int i = 1 ; i <= 5 ; i ++)
	A.push_back(2 * i);
cout << A.size();

Accesarea unui element

Elementele vectorilor pot fi accesate prin intermediul indicilor, cu operatorul []. Acesta nu verifică existență elementului cu un anumit indice, iar dacă acesta nu există, comportamentul programului este impredictibil.

vector<int> A;
for(int i = 1 ; i <= 5 ; i ++)
	A.push_back(2 * i);
for(int i = 0 ; i < A.size() ; i ++)
	cout << A[i] << ' '; // 0 2 4 6 8

De asemenea, este posibilă accesarea elementelor prin intermediul funcției at(). Aceasta returnează o referință la elementul de la poziția dată, iar dacă acesta nu există ridică o excepție care poate fi capturată prin mecanismul try … catch.

vector<int> A = {2 , 4 , 6 , 8 , 10};
A.at(1) = 20; //A = {2 , 20 , 6 , 8 , 10}
for(auto x : A)
	cout << x << " ";

Primul și ultimul element poate fi accesat prin intemediul funcțiilor front() și back(). Ele returnează referințe la primul, respectiv ultimul element al vectorului. Comportamentul este impredictibil dacă vectorul este vid.

vector<int> A = {2 , 4 , 6 , 8 , 10};
A.at(1) = 20; //A = {2 , 20 , 6 , 8 , 10}
A.front() = 7; //A = {7 , 20 , 6 , 8 , 10}
A.back() = 5; //A = {7 , 20 , 6 , 8 , 5}
for(auto x : A)
	cout << x << " ";

Iteratori

Iteratorii sunt similari cu pointerii. Cu ajutorul lor putem identifica adresa elementelor din vector. Iteratorii pot fi dereferențiați (obtinând referințe la elemente), pot fi incrementați/decrementați și pot fi adunați cu scalari.

Vectorii oferă prin intermediul funcției begin() un iterator la primul element al funcției, iar prin end() un iterator la elementul de după ultimul element al vectorului.

vector<int> A = {2 , 4 , 6 , 8 , 10};
vector<int>::iterator I;
for(I = A.begin() ; I < A.end() ; I ++)
	cout << *I << " "; // 2 4 6 8 10

Observații:

• tipul variabilei iterator trebuie să fie în concordanță cu tipul elementelor vectorului;
• pentru a lucra cu elementul pentru care cunoaștem iteratorul, acesta trebuie să fie dereferențiat: *I;
• rezultatul funcției A.end() este un iterator, dar acestuia nu-i corespunde un element al vectorului. Valoarea sa este adresa de după ultimul element al vectorului.

Clasa vector conține și funcțiile rbegin() și rend(), care returnează iteratori de tip reverse iterator, care permit parcurgerea vectorului în ordien inversă:

vector<int> A = {2 , 4 , 6 , 8 , 10};
for(vector<int>::reverse_iterator I = A.rbegin() ; I < A.rend() ; I ++)
	cout << *I << " ";

Acești iteratori fac parte din categoria iteratorilor cu acces aleatoriu. Este cea mai puternică categorie de iteratori (cu cele mai multe operații definite). Aceste operații sunt:

Parcurgerea unui vector

O primă modalitate de parcurgere este folosind indicii, similar cu parcurgerea tablourilor standard C. Pentru determinarea numărului de elemnte există functia size():

vector<int> A = {2 , 4 , 6 , 8 , 10};
for(int i = 0 ; i < A.size(); i ++)
	cout << A[i] << " ";

De asemenea, putem folosi iteratorii:

vector<int> A = {2 , 4 , 6 , 8 , 10};
for(vector<int>::iterator I = A.begin() ; I < A.end() ; I ++)
	cout << *I << " ";

Pentru ușurință, putem folosi specificatorul de tip auto pentru a stabili tipul iteratorului:

vector<int> A = {2 , 4 , 6 , 8 , 10};
for(auto I = A.begin() ; I < A.end() ; I ++)
	cout << *I << " ";

Începând de la versiunea 2011 a stadardului C++ există o formă specială a instrucțiunii for, care permite parcurgerea elementelor unui container:

vector<int> A = {2 , 4 , 6 , 8 , 10};
for(int x : A)
	cout << x << " ";

Specificatorul de tip auto poate fi folosit și aici. În secvența de mai sus, x reprezintă pe rând câte o copie a elementelor din A. Eventualele modificări ale lui x nu vor modifica valorile elementelor din A. Dacă se dorește modificare elemenelor din A, atunci x trebuie să fie o referință:

vector<int> A = {2 , 4 , 6 , 8 , 10};
for(int & x : A)
	x *= 2;
for(int x : A)
	cout << x << " ";

Parcurgerea inversă

Vectorii suportă iteratori reversibili, care permit parcurgerea containerului în ordine inversă. Clasa vector are metodele:

• rbegin() – returnează un iterator reversibil la ultimul element din container
• rend() – returnează un iterator reversibil la elementul din fața primului

Parcurgerea se poate face astfel:

for(vector<int>::reverse_iterator I  = V.rbegin() ; I < V.rend() ; I ++)
	cout << *I << " ";

Inserarea elementelor

Pentru adăugarea la sfârșit se folosește metoda push_back(). Pentru inserarea de noi elemente în interiorul containerului se folosește metoda insert(), care are mai multe forme:

• V.insert(pos , x) – inserează în vectorul V, în fața iteratorului pos un nou element cu valoarea x;
• V.insert(pos , cnt , x) inserează în vectorul V, în fața iteratorului pos, cnt noi elemente egale cu x;
• V.insert(pos , st , dr) inserează în vectorul V, în fața iteratorului pos, dr-st noi elemente, având valorile egale cu cele ale elementelor din secvența [st, dr) dintr-un container oarecare. Dacă vectorul V și secvența [st,dr) se suprapun rezultatul este impredictibil.

Rezultatul apelurilor de mai sus este un iterator la primul element inserat.

Apelurile de mai sus invalidează toți iteratorii și referințele la elemente din V, dacă în urma inserării se realocă memorie, respectiv se invalidează iteratorii și referințele din dreapta lui pos, în caz contrar.

Mai multe detalii despre insert() aici: https://en.cppreference.com/w/cpp/container/vector/insert.

Eliminarea elementelor

Pentru eliminarea tuturor elementelor intr-un vector există metoda clear().

V.clear();

În urma eliminării, rezultatul lui V.size() este 0.

Pentru eliminarea ultimului element al tabloului există metoda pop_back(). În urma apelului se invalidează iteratorii și referințele la ultimul element, precum și iteratorul end().

Pentru eliminarea unor elemente oarecare se folosește metoda erase(), cu următoarele forme:

• V.erase(pos) – elimină elementul indicat de iteratorul pos. pos nu poate fi egal cu end()
• V.erase(st , dr) – elimină elementele din intervalul [st,dr), unde st și dr sunt iteratori la elemente din V

Rezultatul funcției erase() este un iterator la elementul de după ultimul element eliminat.

Se invalidează iteratorii și iteratorii din dreapta lui posm inclusiv iteratorul end().

Mai multe detalii aici: https://en.cppreference.com/w/cpp/container/vector/erase.

Clasa C++ pair este definită în header-ul utility și permite încapsularea într-un obiect a unei perechi ordonate de date. Acestea pot fi de orice tip, inclusiv obiecte sau containere.

O variabilă de tip pair se declară astfel:

pair<T1 , T2> P;

de exemplu

pair<int , double> P;

P are două câmpuri. Primul este de tip T1 (int), al doilea de tip T2 (double). Acestea au numele first și second, iar accesul la ele se face prin operatorul de acces la câmp .: P.first și P.second.

Câmpurile lui P pot primi valori direct, prin atribuiri, de exemplu:

P.first = 10;
P.second = 1.5;

O altă metodă prin care câmpurile pot primi valori este folosirea funcției make_pair(). Aceasta are doi parametri, de tipul celor două câmpuri:

P = make_pair(10 , 1.5);

Datele de același tip pair pot fi comparate cu operatorii ==, !=, <, <=, >, >=. Ordinea lor este cea lexicografică.

Standard Template Library este o componentă importantă a limbajului C++, oferind structuri de date eficiente, mecanisme de utilizare a acestora și multe altele.

STL nu este cuprins în programa de informatică pentru liceu, dar poate fi folosit în rezolvarea multor probleme.

Introducere

• Introducere în STL
• Clasa pair

Containere

Containerele stochează date; acestea pot fi de orice tip, inclusiv obiecte sau containere. Modul de stocare și operațiile existente diferă de la un container la altul.

• vector
  • C++ vector – scurt tutorial
  • Tablouri bidimensionale folosind STL
• set, map
  • Set & Map
• bitset
  • C++ STL Bitset
• stack, queue
  • Stiva
  • Coada
• priority_queue
  • C++ STL priority_queue

Algoritmi

Algoritmii se aplică la secvențe de elemente, care pot fi containere, părți ale containerelor sau alte structuri de date ce pot fi gestionate cu ajutorul pointerilor – de exemplu tablouri standard C.

• Algoritmi care nu modifică secvența
• Algoritmi care mută elementele din secvență
• Algoritmi de sortare și căutare
  • Sort pentru tablouri standard C
  • lower_bound, upper_bound

Standard Template Library reprezintă un ansamblu de mecanisme scrise în C++ pentru gestionarea eficientă a unor colecții de date, împreună cu algoritmi eficienți care prelucrează aceste date. Este parte a Bibliotecii Standard C++, fiind astfel disponibilă în orice compilator care respectă standardul C++.

Introducere

STL are trei componente fundamentale: containerele, iteratorii și algoritmii, precum și o serie de componente suplimentare: containerele speciale, functorii, alocatorii.

Containerele

Containerele sunt obiecte care conțin date (de orice tip, putând fi la rândul containere). Alocarea memoriei pentru conținutul containerelor se face automat (de regulă dinamic), de către container.

Containerele sunt de două tipuri: containere secvențiale și containere asociative.

Containerele secvețiale gestionează un ansamblu de elemente dispuse strict liniar. Fiecare element al containerului are o poziție bine stabilită, care nu depinde de valoarea elementului. Avem următoarele contaniere secvențiale:

• vector – gestionează o secvență de elemente asemănătoare tablourilor standard C;
• deque (double-ended queue)- este o coadă cu operații rapide de adăugare și eliminare la ambele capete;
• list – gestionează o listă alocată dinamic, oferind operațiile de bază cu aceasta.

Timpul necesar pentru operațiile uzuale asupra containerelor secvențiale este redat mai jos:

Containerele asociative sunt structuri de date în care fiecare element are asociată o anumită cheie și are o anumită valoare. Ordinea elementelor în container depinde de cheie și se poate schimba în funcție de celelalte elemente. Aceste containere implementează eficient operațiile de adăugare de noi elemente, ștergere a elementelor în funcție de cheie, precum și căutarea elementelor după cheie.

Sunt două familii de containere asociative:

• set – în care cheia și valoarea elementelor sunt identice; containerele de acest tip sunt:
  • set – memorează elemente distincte; elementele sunt menținute în ordine (strict) crescătoare;
  • multiset – elementele pot fi egale și sunt menținute în ordine crescătoare;
  • unordered_set – memorează elemente distincte; nu este garantată o anumită ordine a elementelor;
  • unordered_multiset – elementele pot fi egale și nu este garantată o anumită ordine a elementelor

• map – cheile și valorile diferă; accesul la elemente se face prin intermediul cheii; containerele de acest tip sunt:
  • map – cheile sunt distincte; elementele sunt menținute în ordine (strict) crescătoare a cheilor;
  • multimap – cheile pot fi egale și sunt menținute în ordinea crescătoare a cheilor;
  • unordered_map – cheile sunt distincte; nu este garantată o anumită ordine a elementelor;
  • unordered_map – cheile pot fi egale și nu este garantată o anumită ordine a elementelor.

Timpii necesari pentru operațiile de adăugare, ștergere și acces sunt logaritmici pentru containerele asociative care menține elementele ordonate și constanți pentru containerele care nu mențin elementele în ordine.

Iteratorii

Iteratorii reprezintă o generalizare a conceputului de pointer. Ei oferă acces la elementele containerelor într-o manieră uniformă, pentru toate containere și pentru toți algoritmii STL.

Operațiile cu iteratorii sunt similare cu operațiile cu pointeri, putându-i dereferenția, incrementa/decrementa, compara, aduna cu întreg, etc. Unele operații sunt disponibile pentru toți iteratorii, altele doar pentru cei ai unor anumite tipuri de container.

Algoritmii

Algoritmii prelucrează colecții de elemente. Aceste colecții pot fi containere, părți ale unor containere sau slte structuri de date care permit lucrul cu pointeri (de exemplu tablouri standard C).

Algoritmii sunt folosiți sub formă de funcții, iar prelucrările pe care le fac sunt diverse: sortări, căutări, modificări, etc.

Containere speciale

Containerele speciale sunt:

• bitset – folosit pentru manipularea eficientă a șirurilor de biți
• containere adaptor – acoperă necesități speciale și sunt create pornind de la containere standard: containerele stack și queue permit gestionarea ușoară a unei stive, respectiv a unei cozi și sunt create pe baza containerului deque, iar containerul priority_queue gestionează o coadă de priorități (heap) și este creat pe baza clasei vector.

Functori și alocatori

Functorii sunt obiecte care se folosesc în maniera unui apel de funcție. Sunt folosite frecvent în cadrul algoritmilor.

Alocatorii sunt obiecte care gestionează alocarea memoriei pentru orice obiect și, în particular, pentru obiectele care fac parte dintr-un container.

Buna ziua, De doua zile incerc conectarea pentru un copil de clasa 5, la grupa C2 si dupa completarea formularului imi da mesajul
“ Ne pare rau inregistrarile ne arata ca sunteti un robot spam. Mai incercati”
Ce gresim? Ce putem face?