## Ce este un vector? Un **vector** în C++ este un container dinamic care permite stocarea și gestionarea eficientă a unei colecții de elemente de același tip. Flexibilitatea sa constă în capacitatea de a ajusta automat dimensiunea atunci când adăugăm sau eliminăm elemente, ceea ce îl face perfect pentru situații unde dimensiunea inițială nu este cunoscută. !!! note "Comparat cu un array" Spre deosebire de array-uri, care au dimensiune fixă și nu permit redimensionare după crearea lor, vectorii se ajustează dinamic și sunt mult mai flexibili. ## Moduri de declarare si initializare În STL, vectorii oferă o flexibilitate extraordinară pentru gestionarea colecțiilor dinamice de date. Iată câteva modalități de a declara și inițializa un vector, fiecare potrivit unui context specific: 1. **Vector Gol**: Un vector fără elemente, cu dimensiunea inițială zero. ```cpp vector nume; ``` 2. **Vector cu Dimensiune Fixă**: Inițializezi un vector cu o dimensiune specificată, iar elementele sunt setate la valorile implicite (0 pentru tipuri numerice). ```cpp vector nume(size); ``` 3. **Vector cu Dimensiune și Valoare Inițială**: Creezi un vector cu o dimensiune fixă, iar toate elementele sunt inițializate cu o valoare dată. ```cpp vector nume(size, val); ``` 4. **Vector Inițializat Direct cu Valori**: Inițializezi un vector specificând direct valorile elementelor, util pentru vectori mici sau când valorile sunt cunoscute la momentul inițializării. ```cpp vector nume({val1, val2, ..., valn}); ``` 5. **Copierea unui Vector**: Creezi un vector nou, care este o copie exactă a unui alt vector. ```cpp vector nume(alt_vector); ``` ```cpp #include #include using namespace std; int main() { vector v1; // Vector gol vector v2(5); // v2 = {0, 0, 0, 0, 0} vector v3(5, 10); // v3 = {10, 10, 10, 10, 10} vector v4 = {1, 2, 3}; // v4 = {1, 2, 3} vector v5(v4); // Copie exactă a vectorului v4 -> v5 = {1, 2, 3} } ``` --- ## Transmiterea parametrilor prin referință Un aspect adesea ignorat este modul în care vectorii sunt transmiși ca parametri într-o funcție. Dacă nu ești atent, complexitatea unui algoritm poate crește semnificativ din cauza creării de copii inutile. Sa studiem urmatorul exemplu. Ce complexitate credeti care urmatorul program? Este $O(n)$, asa-i ? ```cpp #include #include using namespace std; int getSize(vector a) { return (int) a.size(); } int main() { int n = 1000000; vector a(n, 0); long long sum = 0; for (int i = 1; i <= n; i++) { sum += getSize(a); } cout << sum; return 0; } ``` **Nu!** Deși la prima vedere pare că algoritmul are o complexitate de $O(n)$, din cauza faptului că vectorul este **transmis prin valoare**, complexitatea reală devine $O(n^2)$. Asta deoarece de fiecare dată când funcția `getSize` este apelată, se creează o **copie completă** a vectorului `a`, care conține $10^6$ elemente. !!! warning "Copierea unui Vector" Atunci când un vector este copiat, fiecare element al acestuia este duplicat în noul vector. Complexitatea operației de copiere este O(n), unde n este dimensiunea vectorului. În cazul unui vector mare, operațiunea poate consuma resurse semnificative de timp și memorie. **Cum Rezolvăm Problema?** Soluția este să transmitem vectorul **prin referință**. Astfel, în loc să se creeze o copie a vectorului, funcția va lucra direct cu referința la vectorul original, eliminând copierea și păstrând complexitatea la $O(n)$. ```cpp int getSize(vector& a) { // Transmitem vectorul prin referință return (int) a.size(); } ``` !!! info "Explicație" Prin transmiterea prin referință (&), evităm copierea vectorului și lucrăm direct cu vectorul original. --- ## Funcții Esențiale pentru Vectori ### Accesarea și Modificarea Elementelor - `operator[]`: Acces direct la un element (fără verificări de limită). - `at()`: Acces direct la un element, similar cu `[]`, insa verifică dacă indicele este valid și aruncă o excepție dacă este invalid. - `front()` și `back()`: Obținerea primului și ultimului element. ```cpp #include #include using namespace std; int main() { // Inițializăm vectorul cu 5 elemente vector v = {10, 20, 30, 40, 50}; // Accesarea și modificarea elementelor folosind operator[] și at() cout << "Elementul din poziția 2 (folosind []): " << v[2] << '\n'; // 20 cout << "Elementul din poziția 2 (folosind at()): " << v.at(2) << '\n'; // 20 cout << "Primul element: " << v.front() << '\n'; // 10 cout << "Ultimul element: " << v.back() << '\n'; // 50 // Modificăm primul și ultimul element folosind front() și back() v.front() = 5; v.back() = 100; // Tentativă de accesare a unui element în afara limitelor try { cout << "Accesarea unui element în afara limitelor: " << v.at(10) << '\n'; } catch (auto& e) { cout << "Excepție prinsă: " << e.what() << '\n'; } return 0; } ``` ### Adăugare și Ștergere - `push_back()`: Adaugă un element la sfârșit - $O(1)$ - `pop_back()`: Elimină ultimul element - $O(1)$ - `insert()`: Inserează un element la o poziție specifică - $O(n)$ - `erase()`: Șterge un element sau un interval de elemente - $O(n)$ ![Inserare](https://cdn.sanity.io/images/7svjwvsp/production/4258b6f37259f0098f64144a983865f0ac540ffb-850x313.svg "Inserare") ![Stergere](https://cdn.sanity.io/images/7svjwvsp/production/8c2a4f2cd1480bc92f6922efab0fe6d861fc6120-850x301.svg "Stergere") ```cpp #include int main() { // Exemplu pentru functia insert() vector v = {8, 3, 1}; // Vector inițial: 8 3 1 v.insert(v.begin() + 1, 2); // Vectorul devine: 8 2 3 1 v.insert(v.begin() + 2, 7); // Vectorul devine: 8 2 7 3 1 v.insert(v.begin() + 1, {4, 9, 2}); // Vectorul devine: 8 4 9 2 2 7 3 1 // Exemplu pentru functia erase() vector v2 = {8, 3, 1, 9, 7}; // Vector inițial: 8 3 1 9 7 v2.erase(v2.begin() + 2); // Vectorul devine: 8 3 9 7 // Ștergem elementele din intervalul [2, 4): v2.erase(v2.begin() + 2, v2.begin() + 4); // Vectorul devine: 8 3 // Exemplu pentru functia push_back() si pop_back() vector v3 = {8, 3}; // Vector inițial: 8 3 v3.push_back(1); // Vectorul devine: 8 3 1 v3.pop_back(); // Vectorul devine: 8 3 return 0; } ``` ### Gestiunea Dimensiunii și Capacității - `size()`: Returnează numărul de elemente actuale din vector. - `capacity()`: Returnează capacitatea vectorului, adică spațiul de memorie alocat pentru vector. - `clear()`: Șterge toate elementele din vector (nu reduce capacitatea). - `resize()`: Redimensionează vectorul la o dimensiune specificată. Dacă dimensiunea nouă este mai mare decât dimensiunea curentă, elementele noi sunt inițializate cu valori implicite (0 pentru tipurile numerice). Dacă dimensiunea nouă este mai mică, vectorul va elimina elementele suplimentare. - `reserve()`: Rezervă o anumită capacitate de memorie pentru vector. Acesta este util pentru a evita realocările frecvente atunci când știi că vei adăuga un număr mare de elemente. Memoria suplimentară este alocată din timp, fără a modifica dimensiunea efectivă a vectorului. ![Diferenta dintre size si capacity](https://cdn.sanity.io/images/7svjwvsp/production/c883c21c1bc2f7df08e3d11522758f48cd121591-850x337.svg "Diferenta dintre size si capacity") ```cpp #include #include using namespace std; int main() { vector v3 = {1, 2, 3, 4, 5}; // Inițializare vector cu 5 elemente // Afișăm dimensiunea și capacitatea inițială cout << "Dimensiunea inițială: " << v3.size() << '\n'; // Dimensiunea inițială: 5 cout << "Capacitatea inițială: " << v3.capacity() << '\n'; // Capacitatea inițială: 5 // Redimensionăm vectorul la 10 elemente v3.resize(10); cout << "După resize la 10 elemente, dimensiunea: " << v3.size(); // Dimensiunea: 10 cout << "Capacitatea după resize: " << v3.capacity() << '\n'; // Capacitatea: 10 // Rezervăm spațiu pentru 20 de elemente v3.reserve(20); cout << "Capacitatea: " << v3.capacity() << '\n'; // Capacitatea: 20 // Golim vectorul, dar păstrăm capacitatea v3.clear(); cout << "După clear, dimensiunea: " << v3.size() << '\n'; // După clear, dimensiunea: 0 cout << "Capacitatea după clear: " << v3.capacity() << '\n'; // Capacitatea după clear: 20 return 0; } ``` !!! warning "Complexitatea pentru clear()" Funcția clear() are o complexitate în timp de O(n), unde n este numărul de elemente din vector. Deși vectorul devine gol, trebuie să parcurgă fiecare element pentru a-l distruge. Aceasta face ca operațiunea să fie costisitoare în cazul vectorilor mari. --- ## Parcurgerea Vectorilor Alegerea metodei potrivite de parcurgere poate influența atât claritatea, cât și eficiența codului. Iată cele mai comune metode: ### Bucla Clasică cu Index Această metodă oferă control total asupra indexării și modificării elementelor din vector. Este utilă atunci când ai nevoie să accesezi sau să modifici elementele într-o manieră directă, folosind indexul lor. ```cpp for (int i = 0; i < v.size(); i++) { cout << v[i] << " "; // v[i] ne oferă acces direct la elementul de pe poziția i } ``` ### Range-Based For Loop Aceasta este cea mai simplă și elegantă metodă de parcurgere a elementelor dintr-un vector, ideală când nu ai nevoie de index și doar vrei să procesezi fiecare element. ```cpp #include #include using namespace std; int main() { // Exemplu 1: Parcurgere simplă prin copiere (nu modificăm vectorul) vector v = {10, 20, 30, 40, 50}; for (auto x : v) { cout << x << " "; // 10 20 30 40 50 } cout << '\n'; // Exemplu 2: Parcurgere prin referință (modificăm valorile) for (auto &x : v) { // v: [15, 25, 35, 45, 55] x += 5; } // Exemplu 3: Parcurgere a unui vector bidimensional (matrice) vector> matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}; for (auto &row : matrix) { for (auto &elem : row) { cout << elem << " "; // 1 2 3 4 5 6 7 8 9 } cout << '\n'; } return 0; } ``` ### Parcurgere cu Iteratori Această metodă este folosită frecvent în STL, oferind flexibilitate și control. Iteratorii sunt esențiali atunci când lucrăm cu algoritmi STL care acceptă iteratori drept parametri. Cum functioneaza `v.begin()`, `v.end()`? - `v.begin()`: Returnează un iterator către primul element al vectorului. Funcționează ca un pointer către locația de memorie a primului element. - `v.end()`: Returnează un iterator către elementul imediat următor ultimului din vector. (Notă: acest element este "dincolo" de ultimul element și nu ar trebui accesat direct). - `v.rbegin()`: Returnează un iterator către ultimul element din vector (parcurgere inversă). - `v.rend()`: Returnează un iterator către elementul situat înaintea primului element (limita parcurgerii inverse). ```cpp #include #include using namespace std; int main() { vector v = {10, 20, 30, 40, 50}; // Inițializăm un vector cu 5 elemente // Parcurgem vectorul de la început la final folosind iteratori for (auto it = v.begin(); it != v.end(); ++it) { // Dereferențiem iteratorul (*it) pentru a obține valoarea elementului curent cout << *it << ' '; // 10 20 30 40 50 } // Parcurgem vectorul de la final la început folosind iteratori inversați for (auto it = v.rbegin(); it != v.rend(); ++it) { cout << *it << ' '; // 50 40 30 20 10 } return 0; } ``` !!! note "Ce este un iterator?" Un iterator este un obiect specific în C++ care se comportă similar cu un pointer și permite accesul și parcurgerea elementelor din containere STL (precum vectorii). Iteratorii asigură o modalitate sigură și standardizată de traversare și modificare a elementelor unui container, oferind avantajul flexibilității cu algoritmii STL. **Sfarsit!** Sper ca acum este clar cum sta treaba cu vectorii dinamici din STL, cum sa ii folositi si cand. Ca intotdeauna, daca aveti vreo intrebare, nu ezitati sa o lasati mai jos intr-un comentariu !

Vectori din STL: Declarare, Funcții și Parcurgere

Cuprins

Lasă un comentariu

Toate Comentariile