Introducere în STL

Autor: Ștefan-Cosmin Dăscălescu, Alex Vasiluță

Introducere#

Până acum, programele pe care le-ați scris până acum, deși sunt corecte și compilează în limbajul C++, respectă în mare parte din cazuri sintaxa din C, exemple fiind tablourile, anumite funcții de sistem și în general, modul în care am lucrat cu variabilele și tipurile de date menționate anterior, cu o singură excepție - citirea și afișarea, care s-au făcut conform limbajului C++.

Cu alte cuvinte, putem spune că programele scrise sunt programe de C care au cin și cout. Astfel, pentru a putea folosi limbajul C++ la adevărata sa valoare, se impune folosirea structurilor de date și celorlalte facilități ale acestui limbaj. O mare parte dintre ele sunt înglobate în ceea ce vom numi STL (Standard Template Library) și ne vor ajuta să lucrăm cu foarte multe tipuri de valori într-un mod dinamic, astfel evitând marea majoritate a neajunsurilor lucrului cu structuri din C, chiar și adaptate la limbajul C++.

În acest articol, ne vom concentra pe cele mai folosite facilități, împreună cu modul în care le putem folosi în probleme.

Structuri de date de tip tablou#

În această secțiune, ne vom concentra pe structurile de date care pot fi reprezentate în sintaxa din C sub formă de tablouri. Fie că e vorba de vectori, cozi, stive sau tipuri de date mai complexe, toate acestea vor fi menționate în cele ce urmează.

Deși acest articol poate fi parcurs fără cunoștințe anterioare, se recomandă parcurgerea articolului anterior despre arrays.

Structura std::vector#

Aceasta este cea mai simplă structură de date din STL, fiind un tablou cu lungime dinamică, care este indexat de la \(0\). Pentru a putea folosi această structură de date, va trebui să includem biblioteca #include <vector>.

Sintaxa unui vector va fi de tipul vector<tip> nume;, unde tip poate fi orice tip de date cunoscut, inclusiv cele pe care le veți studia în acest articol. Cel mai frecvent, veți folosi un vector drept un înlocuitor pentru tablourile de tip array cu care sunteți obișnuiți din codurile scrise anterior.

Mai jos, puteți vedea diverse exemple de folosire a acestei structuri de date în limbajul C++.

Declarările vectorilor#

În ceea ce privește declarările, avem o flexibilitate unică pentru limbajul C++, putând declara și atribui vectorul în foarte moduri, așa cum vom prezenta mai jos. În mod particular, putem să asignăm și chiar să comparăm vectori, folosind operatorii = și ==.

În general, complexitatea operațiilor descrise aici este liniară raportat la numărul de valori cu care se lucrează.

Observație

Pentru a compara doi vectori, va trebui să aibă aceeași dimensiune și tip de date, iar dacă acest lucru este adevărat, trebuie să aibă toate valorile egale pe aceeași poziție. În mod similar, atribuirea se va face curățând eventual pozițiile în plus existente și adăugând poziții noi dacă e nevoie.

vector<int> v; // declararea vectorului
vector<int> vals = {1, 4, 0, 1, 3, 5}; // initializam un vector cu 6 valori
vector<int> v2(12); // initializam un vector cu 12 valori, toate 0
vector<int> copie = v2;
if (v2 == copie) {
    cout << "Egal\n";
}
else {
    cout << "Inegal\n";
}

Pentru a declara tablouri bidimensionale, sau chiar tablouri multidimensionale, putem folosi aceeași logică, deoarece acestea sunt vectori de vectori. Aceste tipuri de structuri vor fi folosite și ulterior, în ceea ce privește implementările unor modele matematice sau a unor structuri de date mai complexe despre care veți învăța după ce prindeți mai multă experiență.

vector<vector<int>> grid(3, vector<int> (2)); // declararea matricii cu 3 linii si 2 coloane
vector<vector<vector<int>>> cube; // declararea cubului
vector<vector<int>> grid2(n); // declaram n linii
for (int i = 0; i < n; i++) {
    grid2.resize(i+1); // matrice triunghiulara
}

Inserări, ștergeri și alte ajustări#

Pe lângă declarări, atribuiri și comparări, putem și să ajustăm vectorii, folosind foarte multe tipuri de operații care adaugă și scot valori sau chiar fac inserări în diverse poziții, fără a mai fi nevoie de implementarea manuală a operațiilor. Totuși, se remarcă faptul că operațiile de insert și erase vor fi liniare, exact cum sunt și pe tablourile statice.

Iteratori

Valori precum v.begin(), v.end() se numesc iteratori, aceștia vor fi prezentați ulterior. Aceștia reprezintă adresa de memorie de la început și de sfârșit din vector.

// aceste operatii sunt liniare
grid.resize(5, vector<int>(8)); // gridul va avea 5 linii si 8 coloane 
v2.resize(7, -3); // redimensionam vectorul sa aiba 7 valori, toate -3
v.resize(5); // redimensionam vectorul sa aiba 5 elemente

// aceste operatii se fac in O(1)
v.push_back(x); // adaugarea elementului x la final 
v.pop_back(); // eliminarea elementului de la final

// aceste operatii sunt liniare 
v.insert(v.begin() + 2, 6); // inseram 6 la pozitia 2
v.insert(v.begin() + 3, 5, 9); // inseram 9 de 5 ori incepand de la pozitia 3
v.erase(v.begin() + 4); // stergem valoarea de la pozitia 4
v.erase(v.begin() + 2, v.begin() + 5); // stergem valorile de la pozitia 2 la pozitia 4

Afișări în vector#

Pentru a afișa diverse valori din vector, vom putea proceda la fel ca în cazul tablourilor din C. Se remarcă folosirea funcției size pentru a afla dimensiunea vectorului, această funcție fiind de tip unsigned, lucru ce necesită prelucrarea cu atenție a acestor valori.

În mod particular, se remarcă folosirea tipului de date auto, care este folosit pentru a evita o declarare specifică a unei variabile, fiind folosit în acest caz pentru a parcurge valorile din vectorul vals.

Tipuri unsigned

Dacă vrem să avem un loop care va rula de (v.size() - 3) ori, vom avea de-a face cu un loop infinit în cazul în care v.size() < 3, deoarece rezultatul expresiei va fi si el unsigned, rezultatul dând underflow. Pentru a evita asta, putem fie să rescriem expresiile pentru a conține adunări, fie prin a folosi indicatorul (int) pentru a schimba tipul de date la int, care este un tip de date signed.

// afisari si prelucrari
cout << vals[3] << '\n'; // accesam vals[3], al patrulea element
cout << v2.size() << '\n'; // dimensiunea vectorului (se va afisa 7)
vals[1] = -9;

for (int i = 0; i < (int) vals.size(); i++) { // afisam vectorul vals
    cout << vals[i] << " ";
}

for (auto nr : vals) { // afisam vectorul vals folosind auto
    cout << nr << " ";
}

Structura std::array#

Această structură de date este folosită mai rar, dar poate fi utilă în cazul în care vrem să lucrăm cu un array care are avantajele array-urilor din C, dar fără majoritatea dezavantajelor acestora.

Sintaxa unui array va fi de tipul array<tip, dimensiune> nume;. De regulă, nu există diferențe semnificative de performanță între std::vector și std::array, deci în aproape toate cazurile, putem folosi std::vector fără probleme, funcțiile pe care std::array le are sunt incluse în funcțiile vectorului.

array<int,  25> arr; // array cu 25 de elemente de tip int
arr[4] = 3;
cout << arr[5] << '\n';

Structura std::string#

Această structură de date este echivalentul std::vector pentru șirurile de caractere, remarcându-se prin faptul că spre deosebire de șirurile de caractere din C, funcția de aflare a lungimii este \(O(1)\), în loc de \(O(n)\).

Se recomandă citirea în prealabil a articolului anterior despre șiruri de caractere.

De asemenea, toate proprietățile vectorului se aplică și pentru std::string. Pentru a putea folosi această structură de date, va trebui să includem biblioteca #include <string>. Se remarcă faptul că există anumite diferențe față de cum folosim șirurile de caractere din C.

Sintaxa unui string va fi de tipul string nume;

string s = "abacaba";
s[0] = 'c';
cout << s.size() << '\n'; // 7
s[6] = 0; // caracterul nul
cout << s << " " << s.size() << '\n'; // abacab 7 (nu se schimba sizeul)

În mod particular, pe lângă funcțiile vectorului, vom putea concatena două șiruri de caractere cu ușurință, folosind operatorul +. Totuși, trebuie să fim atenți cum folosim acest operator, pentru a evita efectuarea prea înceată a operațiilor.

string s = "roalgo";
string t = "top";
s += t; // roalgotop
s = s + t; // roalgotoptop

Deși în cazul numerelor naturale, aceste operații sunt echivalente, în cazul stringurilor, += și + sunt complet diferite. Prima dintre ele concatenează șirul primit la șirul existent, cea de-a doua copiază cele două șiruri, le unește și apoi atribuie rezultatul șirului. Această diferență devine mai dramatică în situații precum cea de mai jos.

string s;
for (int i = 1; i <= 1000000; i++) { // O(n)
    s += 'a';
}
string t;
for (int i = 1; i <= 1000000; i++) { // O(n^2)
    t = t + 'a';
}

Structura std::pair#

Această structură de date vă permite să folosiți o combinație de tipuri de date mai complexe, în mod similar cu tipul de date struct pe care l-ați învățat anterior. Un mare avantaj pe care std::pair (și ulterior, std::tuple) îl au este acela că permit instrucțiunilor de sortare să compare două instanțe ale acestui tip de date fără a mai fi nevoie să scriem o funcție suplimentară de comparare a valorilor.

Sintaxa este pair<tip1, tip2> nume;, unde tip1 și tip2 sunt tipuri de date, care pot fi de toate felurile, inclusiv alte perechi. Pentru a putea accesa tip1, respectiv tip2, va trebui să folosim comenzile nume.first și nume.second. Inițializarea unui pair se poate face similar cu cea a unui vector.

În cazul elementelor de tip pair compuse, în mod similar cu struct, notațiile vor fi la fel compuse.

De exemplu, dacă avem pair<pair<int, int>, pair<int, int>> p = {{2, 4}, {1, 3}};, cele patru elemente vor putea fi declarate și accesate după cum urmează:

pair<int, int> pr = make_pair(5, 8);
cout << pr.first << '\n';
cout << pr.second << '\n';
pair<pair<int, int>, pair<int, int>> p = {{2, 4}, {1, 3}};
cout << p.first.first << '\n'; // 2
cout << p.first.second << '\n'; // 4
cout << p.second.first << '\n'; // 1
cout << p.second.second << '\n'; // 3

Structura std::tuple#

Această structură de date reprezintă o generalizare a structurii std::pair vă permite să folosiți o combinație de tipuri de date mai complexe, într-o manieră mult mai ușoară decât ați face-o dacă ați folosi pair sau vector, profitând de avantajul că putem ține tipuri de date diferite în fiecare dintre poziții. Pentru a folosi tuple, va trebui să includeți #include <tuple>.

Chiar dacă putem ține valori multiple folosind pairuri imbricate, tuplurile vor face acest lucru mult mai ușor.

tuple<tip1, tip2, ..., tipN> t: Creăm un tuplu cu \(N\) valori, a i-a valoare având \(tip_i\).
make_tuple(a, b, c, ..., d): Returnează un tuplu cu valorile scrise în paranteză
tie(a, b, c, ..., d) = t: Asignăm la \(a, b, c, \dots, d\) valorile din tuplul \(t\) în ordinea dată.
get<i>(t): Returnează cea de-a i-a valoare din tuplul \(t\). Putem folosi această sintaxă și pentru a schimba valoarea din \(t\).

Această operație merge doar dacă \(i\) este o constantă, nu putem schimba valorile dacă \(i\) nu este o constantă.

tuple<int,  int,  int> t{3,  4,  5};
int i =  1;
cout << get<i>(t) << '\n';  // eroare

Mai jos puteți găsi un exemplu de folosire a acestor instrucțiuni.

int a = 3, b = 4, c = 5;
tuple<int, int, int> t = tie(a, b, c);
cout << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << '\n'; // 3 4 5
get<0>(t)  =  7;
cout << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << '\n'; // 7 4 5
tuple<string, string, int> tp2 = make_tuple("Hello", "world", 100);

string s1, s2;
int x;
tie(s1, s2, x)  = tp2;
cout << s1 << " " << s2 << " " << x << '\n'; // Hello world 100
}

Iteratori#

Iteratorii sunt structuri care pot fi utilizate să identifice și traverseze elementele unui container STL. Ei sunt implementați numai la structurile cu acces aleatoriu (toate mai puțin queue, stack și priority_queue).

Glosar iteratori#

range reprezintă un interval de elemente de tip [start, end).
iterator de început: iterator care marchează începutul unui range
iterator past-the-end: iterator care marchează finalul unui range. Deși uneori poate fi accesat, în cele mai multe cazuri accesarea lui duce la erori (de exemplu, rezultatul pentru .end()).

Cum obțin un iterator?#

.begin() - iterator la primul element din structură;
.end() - iterator past-the-end pentru structură.

Ce pot face cu un iterator?#

Să parcurgi structura
- Fiecare iterator permite să îl incrementezi (++it) să se ducă mai departe.
- Putem folosi și it++, dar de obicei este mai lent.
Să îl pui drept parametru la o funcție
- Multe funcții din <algorithm> care merg pe range-uri cer un iterator de început și un iterator "past-the-end".
  - De exemplu, funcția sort() cere doi iteratori: unul care marchează începutul și elementul de după sfârșit (cum ar fi begin() și end()).
- Structurile std::vector și std::deque oferă și funcțiile .erase() și .insert()
  - Funcția .insert() adaugă un element înaintea elementului iteratorului.
  - Funcția .erase() poate primi un singur argument, elementul care să fie șters, sau două argumente, range-ul pe care să îl șteargă.
Foarte multe funcții returnează iteratori, exemple fiind funcțiile lower_bound() și upper_bound() din diverse structuri de date precum std::set, std::map.

Structuri de date liniare#

Structura std::queue#

În general, folosim această structură de date pentru a simula funcționalitățile unei cozi. Pentru a folosi std::queue, avem nevoie de biblioteca #include <queue>.

Deși pentru mai multe detalii, puteți accesa articolul nostru despre cozi, mai jos puteți găsi un exemplu de folosire a acestor instrucțiuni.

queue<int> q;
q.push(2);
q.push(4);
while (!q.empty()) {
    int val = q.front(); // accesam varful cozii
    q.pop();
    cout << val << " "; // afisam 2 4
}
cout << '\n';

Structura std::stack#

În general, folosim această structură de date pentru a simula funcționalitățile unei stive. Pentru a folosi std::stack, avem nevoie de biblioteca #include <stack>.

Deși pentru mai multe detalii, puteți accesa articolul nostru despre stive, mai jos puteți găsi un exemplu de folosire a acestor instrucțiuni.

stack<int> s;
s.push(5);
s.push(8);
while (!s.empty()) {
    int val = s.top(); // accesam varful stivei
    s.pop();
    cout << val << " "; // afisam 8 5
}
cout << '\n';

Structura std::deque#

În general, folosim această structură de date pentru a simula funcționalitățile unui deque. Pentru a folosi std::deque, avem nevoie de biblioteca #include <deque>.

Deși pentru mai multe detalii, puteți accesa articolul nostru despre deques, mai jos puteți găsi un exemplu de folosire a acestor instrucțiuni.

Accesarea pozițiilor oarecare

Spre deosebire de stack și queue, deque permite accesarea pozițiilor oarecare, la fel ca la vector. În multe contexte, putem spune că deque este un vector mai complex, cu toate că un dezavantaj ar fi viteza un pic mai redusă a instrucțiunilor la deque spre deosebire de vector.

deque<int> d;
d.push_front(4);
d.push_front(5);
d.push_back(7);
d.push_back(8);
d.push_front(3);

// deque-ul contine 3 5 4 7 8
int x = d[3]; // putem accesa valori din pozitii oarecare, ca la vector

while (!d.empty()) {
    int val = d.front(); // accesam prima valoare
    cout << val << " ";
    d.pop_front(); // stergem prima valoare
    if (d.size() > 0) {
        val = d.back(); // accesam ultima valoare
        d.pop_back(); // stergem ultima valoare
        cout << val << " ";
    }
}
cout << '\n';
// afisam 3 8 5 7 4

Structuri de date arborescente#

Structurile de date arborescente ne permit să putem lucra cu valori ordonate în mod dinamic, având o performanță foarte bună, complexitatea operațiilor fiind în cele mai multe cazuri logaritimică, deoarece se bazează pe diverși arbori binari care permit sortări dintre cele mai rapide.

Structura std::map#

Structura std::set#

std::unordered_map și std::unordered_set#

std::multimap și std::multiset#

Structura std::priority_queue#

O coadă de priorități este o coadă pe care o folosim pentru a păstra datele într-o ordine dată (by default, descrescătoare). Implementarea ei este bazată pe o structură de date de tip heap, permițând operații de push, pop și top, în mod similar cu cele de la coadă, cu diferența că valorile sunt ținute ordonat. Complexitatea operațiilor este \(O(\log n)\). Chiar dacă această structură de date este un pic mai rapidă decât set și map, un mare dezavantaj este dat de faptul că doar elementul din vârf poate fi accesat, în mod similar cu funcționalitatea heap-ului.

În general, vom vrea să folosim o coadă de priorități atunci când vrem să aflăm mai rapid cel mai mare sau cel mai mic element, constanta fiind bună, fapt ce face această structură de date principala metodă de a implementa diverși algoritmi de tip greedy mai complicați, cel mai cunoscut fiind algoritmul lui Dijkstra pe grafuri cu costuri.

Pentru a folosi această structură de date, biblioteca #include <queue> este necesară. Sintaxa unei cozi de priorități este priority_queue<tip> nume. Mai jos găsiți un exemplu de implementare a acestei structuri de date.

priority_queue<int> pq; 
pq.push(5); // adaugam valori
pq.push(9);
pq.push(1);

while (!pq.empty()) {
    int val = pq.top(); // varful cozii
    pq.pop(); // scoatem varful cozii

    cout << val << " "; // se vor afisa 9, 5, 1 
}

Accesarea valorilor în ordine crescătoare

Pentru a accesa valorile în ordine crescătoare, avem două opțiuni: Fie le adăugăm cu semn schimbat, fără a schimba sintaxa structurii de date, fie adăugăm un comparator custom. Mai jos aveți sintaxa cu comparator custom.

struct cmp {
    bool operator()(int a, int b) {
        return a > b;
    }
};
priority_queue<int, vector<int>, cmp>q;

Policy based data structures#

Structurile de date menționate anterior, deși puternice, nu ne permit să răspundem la întrebări de tipul:

Care este a \(k\)-a valoare în ordine crescătoare prezentă în set/map?
Câte valori sunt mai mici decât \(x\) în set/map?

Deși aceste întrebări pot fi rezolvate folosind structuri de date complexe, precum arborii de intervale dinamici sau eventual folosind normalizări dificil de implementat, există o opțiune inbuilt destul de ușor de folosit și destul de rapidă, complexitatea operațiilor fiind \(O(\log n)\), la fel ca la set și map.

Atenție la constante

Totuși, se remarcă faptul că constanta este una foarte mare, fiind mult mai înceată decât alte metode care ar fi mai greu de implementat.

Această structură de date ne va permite să folosim facilitățile setului, împreună cu două funcții noi:

find_by_order(k) - Al \(k\)-lea cel mai mare element, începând de la \(0\).
order_of_key(x) - Numărul de valori strict mai mici decât \(x\).

Pentru a putea folosi această structură de date, trebuie să declarăm următoarele biblioteci, namespace-uri și typedefs:

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> order_set;

Alte tipuri de date

Pentru a folosi policy based data structures și cu alte tipuri de date, trebuie înlocuite cele două inturi cu tipul de date potrivit. De exemplu, typedef tree<pair<int, int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> order_set; ne permite să ținem pairuri și să operăm în mod similar, fiind foarte util atunci când vrem să lucrăm cu duplicate și eventual să stocăm valori mai complexe.

Mai jos găsiți un exemplu de folosire a acestei structuri de date, așa cum a fost folosită în problema AIB de pe pbinfo.

#include <iostream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> order_set;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    order_set X;

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;

        cout << X.order_of_key(x) << " ";
        X.insert(x);
        // X.find_by_order(x) ar afla al x-lea cel mai mare element
    }
    return 0;
}

Pe lângă o mare parte din problemele cu structuri de date, această structură de date poate fi aplicată și pentru a rezolva problema Greetings de pe Codeforces.

Concluzii#

Structurile de date din STL sunt unul dintre cele mai importante tooluri pe care le puteți folosi în programare și cunoașterea lor este esențială pentru a putea fi programatori cât mai buni. De asemenea, flexibilitatea lor ușurează multe implementări în special în condiții de concurs, unde timpul este limitat.

Totuși, trebuie să aveți în vedere faptul că este de preferat înțelegerea conținuturilor, pentru a evita folosirea lor oricând și oricum, fără a avea în vedere abordările alternative care ar putea exista la probleme, lucru care se remarcă mai ales la structurile de date arborescente, precum std::set și std::map.