vector — tabloul care crește singur

De ce contează?

Imaginează-ți o agendă cu un număr fix de pagini. Dacă ai mai mulți prieteni decât pagini, ai încurcat-o. Acum imaginează-ți o agendă magică: de câte ori scrii pe ultima pagină, îți apar singure pagini noi. Nu te mai gândești la limită — scrii cât ai nevoie. Exact asta face un vector.

Ce este un vector?

Un vector este un tablou dinamic: un șir de elemente de același tip care își mărește singur dimensiunea când adaugi valori. Spre deosebire de tabloul static int a[100], unde fixezi mărimea când scrii programul, vectorul pornește de la zero și crește exact cât ai nevoie.

De ce contează? La concurs adesea nu știi dinainte câte numere vei citi. Cu tablou static fie ghicești o margine prea mare (memorie irosită), fie prea mică (depășire). Vectorul rezolvă problema: adaugi cu push_back și el se ocupă de restul.

Operațiile de bază:

push_back(x) — adaugă x la coadă; vectorul crește cu 1;
size() — câte elemente are acum;
v[i] — acces direct la elementul de pe poziția i, în O(1);
front() / back() — primul, respectiv ultimul element.

Cum funcționează, pas cu pas

Pornim cu vectorul gol și executăm: push_back 4, push_back 8, push_back 15.

push_back 4 → [4], size = 1
push_back 8 → [4, 8], size = 2
push_back 15 → [4, 8, 15], size = 3

Acum v[0] e 4, v[2] e 15, front() e 4 și back() e 15. Indicii merg de la 0 la size() - 1, exact ca la tabloul static.

v	4	8	15
	0	1	2
	front		back

După trei push_back, vectorul are size = 3. Indicii valizi: 0, 1, 2.

Implementare C++

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

int main() {
    vector<int> v;          // vector gol, size = 0

    v.push_back(4);         // [4]
    v.push_back(8);         // [4, 8]
    v.push_back(15);        // [4, 8, 15]

    cout << v.size() << "\n";   // 3 (numarul de elemente)
    cout << v[0] << "\n";       // 4 (acces direct, O(1))
    cout << v.front() << "\n";  // 4 (primul)
    cout << v.back() << "\n";   // 15 (ultimul)

    // parcurgere cu indici
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << " ";    // 4 8 15
    }
    cout << "\n";

    // parcurgere cu range-based for
    for (int x : v) {
        cout << x << " ";       // 4 8 15
    }
    cout << "\n";

    v.resize(5);            // [4, 8, 15, 0, 0] -> completeaza cu 0
    cout << v.size() << "\n";   // 5

    return 0;
}

Matrice cu vector de vectori

Un vector<vector<int>> e un vector ai cărui elemente sunt tot vectori — adică o matrice ale cărei linii pot avea lungimi diferite:

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

int main() {
    // matrice 2 linii x 3 coloane, initializata cu 0
    vector<vector<int>> mat(2, vector<int>(3, 0));

    mat[0][1] = 7;          // linia 0, coloana 1
    mat[1][2] = 9;          // linia 1, coloana 2

    for (int i = 0; i < mat.size(); i++) {
        for (int j = 0; j < mat[i].size(); j++) {
            cout << mat[i][j] << " ";   // 0 7 0 / 0 0 9
        }
        cout << "\n";
    }
    return 0;
}

Complexitate

Operație	Timp	De ce
`push_back`	O(1) amortizat	rareori realocă și copiază tot
`v[i]`, `front`, `back`	O(1)	acces direct prin indice
`size`, `empty`	O(1)	mărimea e ținută în memorie
`insert` la mijloc	O(n)	mută elementele de după poziție
parcurgere completă	O(n)	atingi fiecare element o dată

Observația-cheie

„Amortizat O(1)” înseamnă: când vectorul se umple, el cere de obicei dublul spațiului și copiază tot — acel pas costă O(n). Dar fiindcă dublarea se întâmplă tot mai rar, costul mediu per push_back, pe toate adăugările, rămâne O(1).

Greșeli frecvente la concurs

Greșeli frecvente

v[i] în afara dimensiunii: push_back mărește vectorul, dar v[5] pe un vector cu 3 elemente NU îl mărește — e acces invalid, comportament nedefinit. Folosește push_back ca să adaugi, nu indexare directă.
Confuzia size / ultim indice: dacă size() e 3, ultimul indice valid e 2, nu 3. Bucla corectă: i < v.size(), nu i <= v.size().
front() / back() pe vector gol: comportament nedefinit. Verifică întâi !v.empty().
resize(n) crede că șterge tot: resize doar ajustează mărimea (taie sau completează cu 0 la coadă). Ca să golești complet, folosește v.clear().

Recapitulare

Vectorul e un tablou dinamic: crește singur cu push_back, fără mărime fixă.
Accesul v[i], front, back și size sunt O(1); push_back e O(1) amortizat.
vector<vector<int>> modelează o matrice; indicii valizi merg de la 0 la size() - 1.