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.

Standard Template Library – STL conține două funcții extrem de utile care realizează căutarea binară, lower_bound și upper_bound. Ele se găsesc în headerul algorithm și realizează căutarea atât pentru vectori STL cât și pentru tablourile unidimensionale standard C. În ambele cazuri elementele structurii de date trebuie să fie ordonate după un anumit criteriu, iar funcțiile au următoarele rezultate:

• lower_bound – cel mai din stânga element care este mai mare sau egal cu valoarea căutată;
• upper_bound – cel mai din stânga element care este strict mai mare decât valoarea căutată.

Observație: STL conține și funcția binary_search, care caută într-o structură de date o anumită valoare și returnează true dacă o găsește și false în caz contrar. Funcția lower_bound furnizează informații suplimentare, fiind astfel mai utilă în practică.

Căutarea în vectori STL

Antetele funcțiilor sunt:

1. Iterator lower_bound(Iterator p, Iterator u, Valoare v);
2. Iterator lower_bound(Iterator p, Iterator u, Valoare v, Comparator fcmp);

Valoare este un tip de date oarecare pentru care este definită relația de ordine < sau funcția comparator fcmp, iar p și u sunt iteratori la elemente ale unui vector STL de tip vector<Valoare>.

Funcția caută în secvența [p,u) cel mai din sțânga element mai mare sau egal cu v și returnează iterator la acel element, sau u, dacă nu există un asemenea element nu există. Dacă elementele vectorului sunt ordonate după un alt criteriu decât <, se folosește o funcție de comparare fcmp.

1. Iterator upper_bound(Iterator p, Iterator u, Valoare v);
2. Iterator upper_bound(Iterator p, Iterator u, Valoare v, Comparator fcmp);

Funcția caută în secvența [p,u) cel mai din sțânga element mai mare strict decât v și returnează iterator la acel element, sau u, dacă nu există un asemenea element nu există. Dacă elementele vectorului sunt ordonate după un alt criteriu decât <, se folosește o funcție de comparare fcmp.

În funcțiile de mai sus, numele parametrilor au următoarea semnificație:

• p – primul
• u – ultimul
• v – valoarea de căutat
• f – comparator (funcție de comparare)

Important: Elementul u nu face parte din secvența în care se caută valoarea v.

Exemplu

vector<int> A;
int k;
....
auto I = lower_bound(A.begin(), A.end(), k); // I este iterator
if(I == A.end() || *I != k)
    cout << k << " nu apare în vector";
else
    cout << k << " apare în vector pe poziția " << I - A;

Căutarea în tablouri unidimensionale standard C

Antetele funcțiilor sunt:

1. Valoare * lower_bound(Valoare * p, Valoare * u, Valoare v);
2. Valoare * lower_bound(Valoare * p, Valoare * u, Valoare v, Comparator fcmp);

Valoare este un tip de date oarecare pentru care este definită relația de ordine < sau funcția comparator fcmp, iar p și u sunt pointeri la Valoare șî reprezintă adresele unor elemente ale unui tablou declarat Valoare A[dim];.

Funcția caută în secvența [p,u) cel mai din sțânga element mai mare sau egal cu v și returnează pointer la acel element, sau u, dacă nu există un asemenea element nu există. Dacă elementele vectorului sunt ordonate după un alt criteriu decât <, se folosește o funcție de comparare fcmp.

1. Iterator upper_bound(Iterator p, Iterator u, Valoare v);
2. Iterator upper_bound(Iterator p, Iterator u, Valoare v, Comparator fcmp);

Funcția caută în secvența [p,u) cel mai din sțânga element mai mare strict decât v și returnează pointer la acel element, sau u, dacă nu există un asemenea element nu există. Dacă elementele vectorului sunt ordonate după un alt criteriu decât <, se folosește o funcție de comparare fcmp.

Exemplu 1

#include <iostream>
#include <algorithm>

int main()
{
    int n = 10, v[]={10, 20, 30, 40, 50, 60, 70, 80, 90, 100}; // indexare de la zero

    //lower_bound: cel mai din stânga iterator i pentru care v[i] >= x
    std::cout << std::lower_bound(v , v + n , 20) - v << std::endl; // 1, v[1] >= 20
    std::cout << std::lower_bound(v , v + n , 25) - v << std::endl; // 2, v[2] >= 25

    //upper_bound: cel mai din stânga iterator i pentru care v[i] > x

    std::cout << std::upper_bound(v , v + n , 20) - v << std::endl; // 2, v[2] > 20
    std::cout << std::upper_bound(v , v + n , 25) - v << std::endl; // 2, v[2] > 25

    return 0;
}

Exemplu 2

int A[1000], n; // indexat de la  0  la n - 1
int k;
....
int * q = lower_bound(A, A + n, k); // q este pointer
    if(q == A + n || *q != k)
        cout << k << " nu apare în tablou";
    else
        cout << k << " apare în tablou la indicele " << q - A;

Funcția de comparare

Dacă elementele vectorului (tabloului) satisfac altă relație de ordine, va trebui să definim o funcție de comparare, fcmp, sau să folosim un predicat din STL. De exemplu, dacă vectorul (tabloul) are elementele în ordine descrescătoare putem folosi greater. De exemplu:

int A[1000], n; // indexat de la  0  la n - 1
int k;
....
int * q = lower_bound(A, A + n, k, greater<int>());

În cazul unei relații de ordine mai complexe, se poate defini o funcție de comparare, în felul următor:

bool fcmp(Valoare A, Valoare B);

Funcția are doi parametru de același tip cu elementel tabloului (vectorului) în care face căutarea și va returna true, dacă primul parametru, A, este strict înaintea lui B în ordinea dorită și false în caz contrar.

Referințe

• cppreference.com: lower_bound
• cppreference.com: upper_bound

Descriere Generala

Clasa String specific C++ este un container pentru șirurile de caractere alocat dinamic. Deși se boicotează folosirea claselor, există multe avantaje în utilizarea lor, altfel ar fi programare în C nu C++. Caracteristicile unui programator bun sunt creerea unui algoritm corect, eficient și concis. STL fiind una dintre cele mai folosite biblioteci alături de biblioteca adiționala Boost.

Concepte Generale

În general containărele au membrii comuni ca și nume, de exemplu .size() are aceeași denumire ca la vector și se mai regăsesc și la alte containăre de specialitate. Vezi Vector.

Declarare și constructor

In momentul declarari șirul este initial vid.

string s;

El se poate construii static initial.

string s(5,'a') // lungime 5, poziții 0-4 umplute cu 'a'.

Parcurgere și Atribuire și Concatenare și Comparare

Se realizează cu ajutorul operatorilor +,=,==,!=,>,<,>=,<=.

Citire și parcurgere și cautare

string s,voc="aeiou";
int ap=0;
cin>>s // citirea pana la spatiu | getline(cin,s); // citirea unei linii;
for(int i=0;i<s.size();i++)
    if(voc.find(s[i]!=-1) // căutăm în voc caracterul s[i], dacă el se gasește returnează poziția altfel returnează @-1@.
          ap++; // numărăm numărul de vocale din șir.
cout<<ap;

ATENTIE. În cazul citirii normale a unui șir sau număr trebuie avansat pe următoarea linie inaintea citirii cu getline se extrage caracterul ‘\n’ cu cin.get().

Atribuire

string s;
s="aeiou";

Concatenare

string s,ss;
s+="ae" // s="ae";
if(s=="ae") // se verifică dacă s="ae"
    ss=s;   // copiere in ss a lui s
for(int i=0;i<s.size();i++)
     s+=to_string(i);           // se transforma din int in sir de caractere si se adauga la final. deci sirul devine s="ae01";
s+=ss; // s="ae01ae";
s=""; // s devine gol

Comparare Lexicografică

Afisăm lexicografic 2 șiruri.

string s="ar",ss="ae";
if(s<ss)
   swap(s,ss); // interschibăm
cout<<s<<" "<<ss;

Prelucrarea șirurilor de caractere

• Funcția pop_back() – există și aici șterge ultimul caracter.

string s="aeiou";
s.pop_back() // s="aeio"

Inserare

for(int i=0;i<s.size();i++)
            s.insert(s.begin()+i+1,s[i]+1),i++; // Inserarea dupa fiecare caracter, caracterul imediat urmator lexicografic.

Stergerea

voc="aeiou";
for(int i=0;i<s.size();i++)
        if(voc.find(s[i])!=-1)
            s.erase(s.begin()+i),i--; // Stergerea vocalelor.

• MAI MULT – Lucrarea cu Functii

Trimiterea ca parametrii la functii a containerlor stl, se face ca la variabile obisnuite, trimis obisnuit se face o copie altfel cu adresă & modifică direct.

Fara Adresă

void stergere(string s)
{
     s="";
}
int main()
{
    string s="aeiou";
    stergere(s);
    // s="aeiou"
}

Cu Adresă

void stergere(string &s)
{
     s="";
}
int main()
{
    string s="aeiou";
    stergere(s);
    // s=""
}

Returnarea Unui Șir De Caractere

string stergere(string s)
{
     s="";
     return s;
}
int main()
{
    string s="aeiou";
    s=stergere(s);
    // s=""
}

Inlocuieste

Este o noțiune nouă, înlocuiște de la poziția i, n caractere cu șirul ss.

string s="aeiou",ss="UNU";
s.replace(2,3,ss);
//s=aeUNU

Funcții Adiționale

• Convertirea unui string în cstring.

char s[500];
string str="aeiou";
strcpy(s,str.c_str());

• Spargerea în cuvinte pe spații, punerea în vector de cuvinte și sortarea lexicografică și invers lexicografică.

string s;
vector<string> v; // vector de stringri;
getline(cin,s);
istringstream b(s); // buffer de stringuri inclus in I/O <sstream> sparge default pe spații
for(string w;b>>w;) // cat timp exista cuvinte in buffer citim in w
    v.push_back(w); // punem in vector
sort(v.begin(),v.end()) // lexicografic || sort(v.begin(),v.end(),greater<string>()); // sortul din algorithm

• Gasirea unui caracter de la sfârșit spre început.

string s="aea";
//s.find('a')=0
//s.rfind('a')=2

• Creerea unui subsir.

string s="aeiou",ss;
ss=s.substr(2,3); // de la poziția 2, 3 caractere.
//ss="iou"

• Acesarea rapidă a primului și ultimului caracter.

string s="aeiou";
//s.front()='a' , s.back()='u' 

DE ASEMENEA .back() există și pentru vector.

vector<int> v={5,6,10};
//v.back()=10

• Convertirea unui numar in string

Un număr x se convertește în șir de caractere cu funcția to_string() introdusă în C++17, se poate să nu o compileze un standard mai vechi.

int x=10;
string s;
s=to_string(x),s+=to_string(x);
// s="1010";

• Inversarea unui string

Se foloseste reverse din <algorithm>.

string s="aeiou";
reverse(s.begin(),s.end());
//s="uoiea"

• Convertirea unui string intr-un numar intreg sau real

Se folosesc urmatoarele functii:

string s="105";
int x;
double y;
long long z;
unsigned long long w;
x=stoi(s); //x=105;
y=stod(s); //y=105;
z=stoll(s); //z=105;
w=stoull(s); //w=105;

• Functii din <cctype> de schimbare sau verificare a caracterelor individuale

• Pentru modificare a unor caractere din litere mici in litere mari si vice versa:

string s="AeUr";
for(int i=0;i<s.size();i++)
      s[i]=tolower(s[i]);
//s="aeur"
 for(int i=0;i<s.size();i++)
      s[i]=toupper(s[i]);
//s="AEUR"

• Pentru verificarea unor proprietati ale caracterelor Se returneaza 1 sau 0 in functie de conditie:

isalnum(char) // daca este litera sau cifre
isalpha(char) // daca este litera
isspace(char) // daca este spatiu sau caracter separator cum ar fi '\n'
iscntrl(char) // daca caracterul este caracter de control cum ar fi '\n'
isdigit(char) // daca este cifre
isgraph(char) // daca caracterul se poate printa
islower(char) // daca este litera mica
isupper(char) // daca este litera mare
isxdigit(char) // daca este cifra din reprezentarea unui numar in baza 16
ispunct(char) // daca este semn de punctuatie

Si mai multe functii de cautare in siruri de caractere

De asemenea se pot cauta in sir de la inceput spre sfarsit sau invers, primul caracter din sirul de caractere specificat ca argument sau absenta lui.

string s="aebiouq",ss="ierot";
// s.find_first_of(ss)=1 (e)
// s_find_last_of(ss)=4 (o)
// s.find_first_not_of(ss)=2 (b)
// s.find_last_not_of(ss)=6 (q)

Vectorii sunt containăre alocate dinamic exact ca tablourile statice având o organizare secvențială a elementelor.

Pentu declararea unui vector trebuie inclusă biblioteca <vector> unde se află funcții de manipulare a acestui container.

• Structura generală a unui astfel de vector este

vector<tip_date> nume;

exemplu

vector<int> v;

Inițial vectorul este gol având 0 poziții. Se obișnuiește ca în lucrul cu tablouri statice din C să se prealoce numărul de poziții pentru cât se crede că va fi nevoie și folosirea poziților de la 1. Ambele sunt obiceiuri proaste deși poate face problemele de numărare mai ușoare se pierde o poziție în zadar care deși pare puțină memorie câte un pic de aici și deacolo într-un program mai complex și se adună iar despre prealocare nu trebuie să mai zic, ori prea multă memorie alocata inutil pentru un caz în care se folosesc doar 10 poziții sau unul mult prea mare, de aceea este folositor o astfel de clasa.

• După declarare se pot adăuga elemente în vector folosind funcția membru ca orice membru cu .

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

• Parcurgerea vectorului unde am adugat elemente și afișarea lui

for(int i=0;i<v.size();i++)
cout<<v[i]<<" "; | cout<<v.at(i)<<" ";

pre.
1 2 3 4 5 6 7 8 9 10

.at() este un membru de random-access specific vectorului care înlocuiește operatorul [] având avantajul că dacă se întreabă de o poziție invalidă aruncă excepție.
.size() este un membru care reține câte elemente sunt în vector. Atenție Elementele sunt mereu indexate de la 0, astfel .size() va fi mereu o poziție invalidă, ex. v={5,2,1}, v[0]=5,v[1]=2,v[2]=1. .size()=3, sunt 3 elemente însă de la 0-2 sunt 3 elemente.

• Parcurgerea vectorului și afișarea lui cu ajutorului unui Iterator.

Ce este un Iterator?
Un iterator este un pointer la adresă specific fiecărui tip de container pentru parcurgerea lui din adresă în adresă.

Cum funcționeaza?

Iteratorul se declară pentru fiecare tip de container și fiecare tip de date a containerului. NU se pot folosi pentru alte containere de alt tip. După declarare se atribuie adresa de început .begin() și se se incrementează, vectorul fiind declarat secvential se va oprii atunci cand se termină segmentual pe care este declarat vectorul.

Fiecare vector are 2 membrii .begin(), .end().
.begin() are adresa de început a vectorului și .end() adresa de sfârșit a vectorului care se află cu o poziție după ultimul element și ea este o poziție invalidă care nu face parte din vector. Fiecare element se parcurge prin dereferinta iteratorului.

! Orice operatiune de modificare a secventei din interiorul vectorului va devaliza iteratorul deoarece spatiul va fi realocat.

Exemplu

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

Mai Mult
Se poate forta prin instructiunea auto să determine ce fel iterator este nevoie pentru a parcurge containerul.

vector<int> v;
for(auto i:v)
cout<<i<<" ";

• Stergerea elementului din coada in timp constant folosind pop_back())

Considerând că avem elementele de la 1-10 în vector. Vom șterge 5 elemente astfel:

while(v.size()>5)
v.pop_back();

• Constructor și alocare
  Vectorul nu este obligatoriu să fie gol el poate să fie declarat cu un anumit număr de poziții exact cum s-ar face la cei statici și să fie modificate pe parcurs. De asemenea el are în componență un constructor care spune cu ce să umple fiecare poziție.

vector<int> v(100)

Vector cu 100 de elemente cu pozitii de la 0-99 cu valoarea 0 implicită.

vector<int> v(100,1)

Vector cu 100 de elemente cu pozitii de la 0-99 cu valoarea 1.

Schimbarea pe parcurs a lungii se face ori cu push_back ori cu pop_back care mareste sau micsorează marimea ori de cate ori este chemata functia. Însă ea poate fi facută și manual cu funcția .resize().

vector<int> v; // 0 elemente
v.push_back(5) // 1 element {5}
v.resize(2) // 2 elemente {5,0}
v.push_back(6), v.push_back(10) // 4 elemente {5,0,6,7}
v.resize(3) // 3 elemente {5,0,6}
v.resize(10) // 10 elemente {5,0,6,0,0,0,0,0,0,0}

Acest lucru se poate folosi in cazul vectorilor de fecventă.

vector<int> v;
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
    cin>>x;
    if(x>=v.size())
    v.resize(x+1)
    v[x]=1;
}

• Stergeri și inserare
  Acest lucru se poate realiza în aproximativ o(n), limitata de modalitate de structurare a vectorului folosind .erase(), .insert().

Pentru inserarea pe poziția 2 a numarului 10 considerând că aceasta există trebuie trimis pointer de la sfârșit sau începtul vectorlui.

v.insert(v.begin()+2,10);

La fel și la stergere.

v.erase(v.begin()+2);

Pentru stergerea tuturor elementelor pare din vector.

for(int i=0;i<v.size();i++)
if(v.at(i)%2==0)
v.erase(v.begin()+i),i--;

Pentru inserarea dupa fiecare numar par dublul lui.

for(int i=0;i<v.size();i++)
if(v.at(i)%2==0)
v.insert(v.begin()+i+1,v.at(i)*2),i++;

• Alte categorii de vectori
  vector<vector<int>> v; // matrici
  vector<string> v; // vector de cuvinte
  vector<pair<int,int>> v; // vector de perechi, elementele se aceseaza ca fiind de exemplu v[1].first, v[1].second dintr-o pereche.