STL, lecția 2 – Vector

Vectorul din STL este o metodă mai ușoară de a stoca un șir de elemente. Face același lucru ca un array, doar că este mult mai bun, deoarece funcțiile cu care vine vă vor ușura semnificativ munca depusă pentru rezolvarea unei probleme de informatică.

Pentru început, să vedem de ce este mai bun vectorul decât array-ul:

În ceea ce privește funcțiile pe care le putem folosi, cele mai importante sunt:

1. size(), cu complexitatea O(1) – returneaza dimensiunea vectorului
2. clear(), cu complexitatea O(N) – șterge toate elementele vectorului (N elemente)
3. empty(), cu complexitatea O(1) – returneaza 0 dacă vectorului conține cel puțin un element, 1 în caz contrar
4. erase(), cu complexitatea O(N + M) – șterge un singur element sau mai multe elemente(N) aflate pe poziții consecutive. M reprezintă numărul de elemente mutate la ștergere
5. insert(), cu complexitatea O(N + M) – adaugă un element sau mai multe elemente(N) la o anumită poziție. M reprezintă numărul de elemente mutate la adăugare
6. push_back(), cu complexitatea O(1) – adaugă un element la sfârșitul vectorului
7. pop_back(), cu complexitatea O(1) – șterge ultimul element din vector

Să rezolvăm o problemă de pe pbinfo pentru a vedea cum funcționează vectorul. Problema inserareDupa #159 ne cere să inserăm după fiecare element par dublul său. Aceasta este rezolvarea problemei explicată pas cu pas în comentarii:

#include <iostream>
#include <vector> // includem libraria ca sa putem folosi vectorul
using namespace std;

int main()
{
   vector<int> v; // declaram vectorul v
   int n, i, x;
   cin >> n; // pe n il folosim doar ca sa stim cate numere sa citim.
   // dupa citire, nu mai avem nevoie de n, pt ca avem functia v.size()

   for (i = 0; i < n; ++i)
   {
      cin >> x; // citim un numar,
      v.push_back(x); // ca mai apoi sa il punem la sfarsitul vectorului v.
   }

   // dupa fiecare inserare, ar trebui sa adunam pe n cu 1.
   // dar, pentru ca folosim vector, nu mai trebuia sa avem grija de acest lucru.
   // v.size() se schimba pentru fiecare inserare/stergere!
   for (i = 0; i < v.size(); ++i)
      if (v[i] % 2 == 0)
      {
         // inseram pe iteratorul v.begin()+i+1 valoarea v[i]*2.
         // tineti minte ca functia insert accepta ca pozitie un ITERATOR, nu un NUMAR.
         v.insert(v.begin()+i+1, v[i]*2);
         i++; // daca nu adunam pe i cu 1, la urmatoarea faza a for-ului ar verifica numarul introdus acum.
      }

   for (int elem : v) // pentru fiecare element din v,
      cout << elem << ' '; // il afisam.
   return 0;
}

Avantajele acestei soluții: În primul rând, dacă am fi lucrat cu array, ar fi trebuit să precizăm dimensiunea 2*n. La vector nu precizăm nicio dimensiune. În al doilea rând, mecanismul de inserare a unui număr în vector este deja implementat și trebuie scrisă doar o linie de cod pentru a insera. Iar în al treilea rând, după fiecare inserare nu trebuie să creștem pe n cu 1. Funcția size() returnează tot timpul numărul de element.

Poziția specificată la funcția insert() trebuie să fie un iterator, ci nu un număr. Trebuie să știți că iteratorii sunt ca niște pointeri. Vom explica iteratorii și pointerii într-o altă lecție.

A doua și ultima problemă pe care o rezolvăm în acest articol este Unice1 #270. Această problemă cere afișarea numărului de numere care apar o singură dată într-un șir de numere.

#include <fstream>
#include <vector>
#include <algorithm> // de aici folosim find()
using namespace std;

int main()
{
   ifstream cin ("unice1.in");
   ofstream cout ("unice1.out");
   vector<int> v;
   int n, i, x, k;
   cin >> n;

   for (i = 0; i < n; ++i)
   {
      // cin >> v[i];  nu putem folosi aceasta citire!!
      // pentru ca nu am specificat dimensiunea, v[i] nu exista cand vrem sa citim!!
      cin >> x;
      v.push_back(x);
   }

   k = 0;
   for (i = 0; i < n; ++i)
      if (find(v.begin(), v.begin()+i, v[i]) == v.begin()+i &&
          find(v.begin()+i+1, v.end(), v[i]) == v.end())
         k++;
         
   cout << k;
   return 0;
}

Funcția find() este o funcție care se află în librăria <algorithm> și are la primii doi parametrii doi iteratori, și la al treilea parametru un număr întreg. Această funcție caută în intervalul impus de cei doi parametrii valoarea din al treilea parametru. De exemplu, un apel al funcției de genul find(v.begin(), v.begin()+3, 10); caută în primele 3 valori din vector valoarea 10, pentru că intervalul este [v.begin(), v.begin()+3). Returnează un iterator la prima apariție a acestei valori. Dacă această valoare nu apare deloc în acest interval, returnează iteratorul precizat la al doilea parametru.

În această problemă ne interesează ca, la căutarea în numerele din stânga și din dreapta poziției curente, să nu existe alt număr la fel cu cel de pe poziția i. Cele două funcții de find() caută în stânga și în dreapta lui i să nu existe numere egale cu v[i].

Este important să știți să lucrați cu vectorul din STL, deoarece acesta vă poate ușura munca depusă la rezolvarea unor probleme și, în cele mai multe cazuri, va reduce probabilitatea de a produce erori. Sper că ați înțeles și că vă va fi de folos această lecție în viitor. Spor la învățat!