STL C++ Avansat — Ghid Complet pentru BAC și Olimpiadă

Ce este STL?

Standard Template Library (STL) este biblioteca standard C++ care oferă structuri de date și algoritmi pre-implementați, testați și eficienți.

Principalele Containere STL

1. vector<T> — Array Dinamic

Copiază
1#include <vector>
2vector<int> v;
3v.push_back(10);      // adaugă la final: O(1) amortizat
4v.push_back(20);
5v.pop_back();         // elimină ultimul: O(1)
6v.size();             // dimensiunea: O(1)
7v[0];                 // acces prin index: O(1)
8v.front();            // primul element
9v.back();             // ultimul element
10
11// Inițializare
12vector<int> v2(5, 0);   // 5 elemente, toate 0
13vector<int> v3 = {1, 2, 3, 4, 5};
14
15// Parcurgere
16for (int x : v3) cout << x << " ";
17for (int i = 0; i < v3.size(); i++) cout << v3[i] << " ";
18
19// Iteratori
20for (auto it = v3.begin(); it != v3.end(); ++it) cout << *it << " ";
21
22// Sortare
23sort(v3.begin(), v3.end());  // crescător
24sort(v3.begin(), v3.end(), greater<int>());  // descrescător

2. map<K,V> — Dicționar Ordonat (BST)

Copiază
1#include <map>
2map<string, int> frecventa;
3
4// Inserare
5frecventa["Ana"] = 3;
6frecventa["Bogdan"]++;  // auto-inițializat cu 0
7
8// Verificare existență
9if (frecventa.count("Ana")) cout << "Există!";
10if (frecventa.find("Ion") != frecventa.end()) cout << "Există!";
11
12// Parcurgere (în ordine alfabetică/crescătoare a cheii)
13for (auto& [cheie, val] : frecventa) {
14    cout << cheie << ": " << val << "\n";
15}
16
17// Complexitate: O(log n) pentru insert, find, erase

3. unordered_map<K,V> — Dicționar Hash

Copiază
1#include <unordered_map>
2unordered_map<string, int> um;
3um["test"] = 42;
4// Complexitate: O(1) amortizat (vs O(log n) la map)
5// Dezavantaj: nu este ordonat

4. set<T> — Mulțime Ordonată (fără duplicate)

Copiază
1#include <set>
2set<int> s;
3s.insert(5);
4s.insert(3);
5s.insert(5);  // ignorat (duplicat)
6// s conține: {3, 5}
7
8s.erase(3);
9cout << s.count(5);  // 1 dacă există, 0 dacă nu
10
11// Parcurgere în ordine crescătoare
12for (int x : s) cout << x << " ";
13
14// Complexitate: O(log n) pentru toate operațiile

5. stack<T> — Stivă (LIFO)

Copiază
1#include <stack>
2stack<int> st;
3st.push(1);
4st.push(2);
5st.push(3);
6cout << st.top();  // 3
7st.pop();          // șterge 3
8cout << st.size(); // 2
9cout << st.empty(); // false

6. queue<T> — Coadă (FIFO)

Copiază
1#include <queue>
2queue<int> q;
3q.push(1);
4q.push(2);
5q.push(3);
6cout << q.front();  // 1
7cout << q.back();   // 3
8q.pop();            // șterge 1 (din față)

7. priority_queue<T> — Coadă de Priorități (Heap)

Copiază
1// Max-heap (implicit)
2priority_queue<int> pq;
3pq.push(5);
4pq.push(1);
5pq.push(10);
6cout << pq.top();  // 10 (maximul)
7pq.pop();
8
9// Min-heap
10priority_queue<int, vector<int>, greater<int>> minPQ;
11minPQ.push(5); minPQ.push(1); minPQ.push(10);
12cout << minPQ.top();  // 1 (minimul)

Algoritmi STL Esențiali

Copiază
1#include <algorithm>
2
3vector<int> v = {5, 2, 8, 1, 9};
4
5sort(v.begin(), v.end());                    // sortare
6reverse(v.begin(), v.end());                 // inversare
7int mx = *max_element(v.begin(), v.end());   // maximul
8int mn = *min_element(v.begin(), v.end());   // minimul
9int s = accumulate(v.begin(), v.end(), 0);   // suma
10
11// Binary search (pe vector sortat)
12bool found = binary_search(v.begin(), v.end(), 5);
13
14// Număr de apariții
15int cnt = count(v.begin(), v.end(), 5);

Aplicație Completă — Frecvența Cuvintelor

Copiază
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() {
5    string text = "ana are mere ana nu are pere";
6    istringstream iss(text);
7    map<string, int> freq;
8    string cuvant;
9    while (iss >> cuvant) freq[cuvant]++;
10    
11    // Sortare după frecvență (descrescător)
12    vector<pair<int, string>> v;
13    for (auto& [c, f] : freq) v.push_back({f, c});
14    sort(v.rbegin(), v.rend());
15    
16    for (auto& [f, c] : v) cout << c << ": " << f << "\n";
17}