Etichete: STL

Vectorii sunt containăre alocate dinamic exact ca tablourile statice având o organizare secvențială a elementelor.

Pentu declararea unui vector trebuie inclusă biblioteca <vector> unde se află funcții de manipulare a acestui container.

  • Structura generală a unui astfel de vector este
vector<tip_date> nume;

exemplu

vector<int> v;

Inițial vectorul este gol având 0 poziții. Se obișnuiește ca în lucrul cu tablouri statice din C să se prealoce numărul de poziții pentru cât se crede că va fi nevoie și folosirea poziților de la 1. Ambele sunt obiceiuri proaste deși poate face problemele de numărare mai ușoare se pierde o poziție în zadar care deși pare puțină memorie câte un pic de aici și deacolo într-un program mai complex și se adună iar despre prealocare nu trebuie să mai zic, ori prea multă memorie alocata inutil pentru un caz în care se folosesc doar 10 poziții sau unul mult prea mare, de aceea este folositor o astfel de clasa.

  • După declarare se pot adăuga elemente în vector folosind funcția membru ca orice membru cu .
for(int i=1;i<=10;i++)
v.push_back(i);
  • Parcurgerea vectorului unde am adugat elemente și afișarea lui
for(int i=0;i<v.size();i++)
cout<<v[i]<<" "; | cout<<v.at(i)<<" ";

pre.
1 2 3 4 5 6 7 8 9 10

.at() este un membru de random-access specific vectorului care înlocuiește operatorul [] având avantajul că dacă se întreabă de o poziție invalidă aruncă excepție.
.size() este un membru care reține câte elemente sunt în vector. Atenție Elementele sunt mereu indexate de la 0, astfel .size() va fi mereu o poziție invalidă, ex. v={5,2,1}, v[0]=5,v[1]=2,v[2]=1. .size()=3, sunt 3 elemente însă de la 0-2 sunt 3 elemente.

  • Parcurgerea vectorului și afișarea lui cu ajutorului unui Iterator.

Ce este un Iterator?
Un iterator este un pointer la adresă specific fiecărui tip de container pentru parcurgerea lui din adresă în adresă.

Cum funcționeaza?

Iteratorul se declară pentru fiecare tip de container și fiecare tip de date a containerului. NU se pot folosi pentru alte containere de alt tip. După declarare se atribuie adresa de început .begin() și se se incrementează, vectorul fiind declarat secvential se va oprii atunci cand se termină segmentual pe care este declarat vectorul.

Fiecare vector are 2 membrii .begin(), .end().
.begin() are adresa de început a vectorului și .end() adresa de sfârșit a vectorului care se află cu o poziție după ultimul element și ea este o poziție invalidă care nu face parte din vector. Fiecare element se parcurge prin dereferinta iteratorului.

! Orice operatiune de modificare a secventei din interiorul vectorului va devaliza iteratorul deoarece spatiul va fi realocat.

Exemplu

vector<int> v;
vector<int>::iterator it;
for(it=v.begin();it!=v.end();it++)
cout<<*it<<" ";

Mai Mult
Se poate forta prin instructiunea auto să determine ce fel iterator este nevoie pentru a parcurge containerul.

vector<int> v;
for(auto i:v)
cout<<i<<" ";
  • Stergerea elementului din coada in timp constant folosind pop_back())

Considerând că avem elementele de la 1-10 în vector. Vom șterge 5 elemente astfel:

while(v.size()>5)
v.pop_back();
  • Constructor și alocare
    Vectorul nu este obligatoriu să fie gol el poate să fie declarat cu un anumit număr de poziții exact cum s-ar face la cei statici și să fie modificate pe parcurs. De asemenea el are în componență un constructor care spune cu ce să umple fiecare poziție.
vector<int> v(100)

Vector cu 100 de elemente cu pozitii de la 0-99 cu valoarea 0 implicită.

vector<int> v(100,1)

Vector cu 100 de elemente cu pozitii de la 0-99 cu valoarea 1.

Schimbarea pe parcurs a lungii se face ori cu push_back ori cu pop_back care mareste sau micsorează marimea ori de cate ori este chemata functia. Însă ea poate fi facută și manual cu funcția .resize().

vector<int> v; // 0 elemente
v.push_back(5) // 1 element {5}
v.resize(2) // 2 elemente {5,0}
v.push_back(6), v.push_back(10) // 4 elemente {5,0,6,7}
v.resize(3) // 3 elemente {5,0,6}
v.resize(10) // 10 elemente {5,0,6,0,0,0,0,0,0,0}

Acest lucru se poate folosi in cazul vectorilor de fecventă.

vector<int> v;
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
    cin>>x;
    if(x>=v.size())
    v.resize(x+1)
    v[x]=1;
}
  • Stergeri și inserare
    Acest lucru se poate realiza în aproximativ o(n), limitata de modalitate de structurare a vectorului folosind .erase(), .insert().

Pentru inserarea pe poziția 2 a numarului 10 considerând că aceasta există trebuie trimis pointer de la sfârșit sau începtul vectorlui.

v.insert(v.begin()+2,10);

La fel și la stergere.

v.erase(v.begin()+2);

Pentru stergerea tuturor elementelor pare din vector.

for(int i=0;i<v.size();i++)
if(v.at(i)%2==0)
v.erase(v.begin()+i),i--;

Pentru inserarea dupa fiecare numar par dublul lui.

for(int i=0;i<v.size();i++)
if(v.at(i)%2==0)
v.insert(v.begin()+i+1,v.at(i)*2),i++;
  • Alte categorii de vectori
    vector<vector<int>> v; // matrici
    vector<string> v; // vector de cuvinte
    vector<pair<int,int>> v; // vector de perechi, elementele se aceseaza ca fiind de exemplu v[1].first, v[1].second dintr-o pereche.

Probleme ataşate

Nr. Problema Clasa Dificultate Operații I/O
1 #1452 - Stergere_Element 9 ușoară consola
2 #2737 - NrDivProd 9 dificilă fișiere
3 #1608 - Sortare Divizori 9 medie fișiere
4 #1900 - numere16 9 ușoară fișiere
5 #2594 - Partitionare 9 medie consola