Programare Competitivă

STL - Introducere și vector

STL (Standard Template Library) este o colecție de structuri de date și algoritmi gata făcuți din C++. În loc să implementăm manual stive, cozi, sortări, STL ne oferă variante testate și optimizate.

#include <vector>
#include <algorithm>

De ce STL?

  • Nu mai reimplementăm structuri de date de la zero
  • Codul devine mai scurt și mai clar
  • Structurile sunt testate și optimizate
  • La concursuri, economisim timp prețios

vector<T> - vectorul dinamic

Un vector din STL este ca un vector clasic, dar își ajustează dimensiunea automat. Nu trebuie să declari dimensiunea dinainte.

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> v;         // vector gol de int-uri
    vector<int> w(5);      // vector cu 5 elemente (toate 0)
    vector<int> u(5, 3);   // vector cu 5 elemente, toate egale cu 3

    return 0;
}

Operații de bază

vector<int> v;

v.push_back(3);   // adaugă 3 la final: [3]
v.push_back(7);   // adaugă 7 la final: [3, 7]
v.push_back(2);   // adaugă 2 la final: [3, 7, 2]

cout << v[0];     // 3 (acces prin indice, ca la vector clasic)
cout << v[1];     // 7
cout << v.size(); // 3 (numărul de elemente)

v.pop_back();     // scoate ultimul: [3, 7]

cout << v.back();  // 7 (ultimul element)
cout << v.front(); // 3 (primul element)

cout << v.empty(); // 0 (false - nu e gol)

Tabel operații

Operație Ce face Complexitate
push_back(x) Adaugă la final O(1) amortizat
pop_back() Scoate ultimul O(1)
v[i] Acces element i O(1)
size() Număr elemente O(1)
empty() Verifică gol O(1)
front() Primul element O(1)
back() Ultimul element O(1)
clear() Golește vectorul O(n)
Cum funcționează push_back intern?

Un vector alocă intern un bloc de memorie de o anumită capacitate. Când adăugăm elemente cu push_back, le pune în spațiul disponibil.

Când vectorul se umple (size == capacity), nu mai are loc. Atunci:

  1. Alocă un bloc de două ori mai mare (capacitatea se dublează)
  2. Copiază toate elementele vechi în blocul nou
  3. Eliberează blocul vechi
  4. Adaugă elementul nou

De aceea push_back este O(1) amortizat: de cele mai multe ori e instantaneu, dar ocazional (la dublare) copiază tot - O(n). Pe termen lung, media e O(1) per operație.

Capacitate:  1 → 2 → 4 → 8 → 16 → 32 → ...
Dublare la:  1   2   4   8   16   32   elemente

push_back nr 1:  alocă 1     → copiere 0 elemente
push_back nr 2:  alocă 2     → copiere 1 element
push_back nr 3:  alocă 4     → copiere 2 elemente
push_back nr 5:  alocă 8     → copiere 4 elemente
push_back nr 9:  alocă 16    → copiere 8 elemente

Putem verifica capacitatea cu v.capacity() și o putem seta dinainte cu v.reserve(n) ca să evităm realocările:

vector<int> v;
v.reserve(100000);  // pre-alocă pentru 100000 elemente
// acum push_back nu va mai realloca până la 100000

Parcurgerea unui vector

Cu indice (clasic)

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

Cu range-based for (modern)

for (int x : v)
    cout << x << " ";

x ia pe rând fiecare valoare din vector.

Cu referință (dacă vrem să modificăm)

for (int &x : v)
    x = x * 2;   // dublează fiecare element

Fără &, x e o copie - modificările nu se păstrează.

Citire și afișare

#include <fstream>
#include <vector>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int main()
{
    int n;
    fin >> n;

    vector<int> v(n);
    for (int i = 0; i < n; i++)
        fin >> v[i];

    for (int x : v)
        fout << x << " ";

    return 0;
}

Atenție: vector folosește indexare de la 0. v[0] e primul element, v[n-1] e ultimul.

Sortarea unui vector

#include <algorithm>

vector<int> v = {3, 7, 2, 9, 4};

sort(v.begin(), v.end());         // crescător: 2 3 4 7 9
sort(v.begin(), v.end(), greater<int>()); // descrescător: 9 7 4 3 2

v.begin() și v.end() sunt iteratori - pointeri la începutul și sfârșitul vectorului.

Inițializare cu valori

vector<int> v = {3, 7, 2, 9, 4};    // listă de inițializare
vector<int> w(10, 0);                 // 10 elemente, toate 0
vector<int> u;                        // gol, adăugăm cu push_back

Vector de vectori (matrice dinamică)

vector<vector<int>> mat(n, vector<int>(m, 0));
// matrice n x m, inițializată cu 0

mat[i][j] = 5; // acces ca la matrice clasică

Exemplu complet: sortare și afișare

#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int main()
{
    int n;
    fin >> n;

    vector<int> v(n);
    for (int i = 0; i < n; i++)
        fin >> v[i];

    sort(v.begin(), v.end());

    for (int x : v)
        fout << x << " ";

    return 0;
}

date.in:

5
3 7 2 9 4

date.out:

2 3 4 7 9

Vector clasic vs vector<T>

Vector clasic (int v[100]) vector<int>
Dimensiune Fixă, la declarare Dinamică, crește automat
Indexare De la 0 (sau 1) De la 0
Declarare int v[100001]; vector<int> v;
Adăugare Manual cu contor push_back()
Dimensiune Trebuie știută v.size()
Sortare sort(v+1, v+n+1) sort(v.begin(), v.end())
Folosit la Concursuri (simplu) Concursuri + proiecte
Când alegem vector<T> vs vector clasic?

La concursuri, ambele sunt acceptate. Vectorul clasic e puțin mai rapid (fără overhead de redimensionare), dar vector<T> e mai flexibil.

Folosește vector<T> când:

  • Nu știi dimensiunea dinainte
  • Ai nevoie de vector de vectori (liste de adiacență la grafuri)
  • Vrei cod mai curat

Folosește vector clasic când:

  • Dimensiunea e cunoscută și fixă
  • Vrei performanță maximă
  • Indexezi de la 1

Greșeli frecvente

1. Acces în afara limitelor

vector<int> v(5);
cout << v[10]; // EROARE! Doar 5 elemente

2. size() returnează unsigned

for (int i = 0; i < v.size(); i++) // warning: comparație signed/unsigned
for (int i = 0; i < (int)v.size(); i++) // CORECT

3. Uitarea lui #include <vector>

Fără include, vector nu e recunoscut.

Ce să reții

  • vector<T> e un vector cu dimensiune dinamică.
  • push_back, pop_back, size, empty - operații de bază.
  • Parcurgere: for (int x : v) sau cu indice.
  • Sortare: sort(v.begin(), v.end()).
  • Indexare de la 0.
  • Include: <vector> și <algorithm> pentru sort.
Cuprins Inapoi Inainte