Vectori în C++: declarare, indici și parcurgere

Un vector păstrează mai multe valori de același tip, într-o ordine precisă. Fiecare element are un indice, prin care îl poți citi sau modifica. Dacă ai patru note, nu ai nevoie de patru variabile cu nume diferite: poți folosi un singur vector și o buclă.

Recapitulează variabilele și structurile repetitive. Prin „vector” înțelegem aici un tablou unidimensional. Îl reprezentăm întâi printr-un tablou clasic, apoi prin containerul std::vector din biblioteca C++. În această lecție numerotăm indicii de la zero. Un vector cu n elemente are indicii valizi de la 0 la n - 1.

Elementul și indicele sunt lucruri diferite

Pentru valorile 7 2 9 4, elementul a[0] este 7, iar a[2] este 9. Indicele spune unde se află valoarea, nu cât valorează ea. a[4] nu este al patrulea element: ar fi al cincilea și nu există în acest exemplu.

Indicii încep de la zero; ultima poziție validă este n - 1.

Expresia a[i] folosește valoarea curentă a lui i. Dacă i crește cu unu, la următoarea citire accesezi elementul vecin din dreapta. Nu se modifică automat datele din vector când schimbi indicele.

Citire și sumă

Programul citește n, cu 0 <= n <= 100000, apoi n numere întregi între -1000000 și 1000000. Afișează suma lor.

Varianta cu tablou clasic

Tabloul a[100000] are capacitate fixă. Datele ocupă doar primele n poziții, iar indicii folosiți sunt de la 0 la n - 1. Limita lui n trebuie să respecte această capacitate.

#include <iostream>

int main() {
    int n = 0;
    std::cin >> n;
    int a[100000]{};
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    long long suma = 0;
    for (int i = 0; i < n; ++i) {
        suma += a[i];
    }
    std::cout << suma << '\n';
    return 0;
}

Varianta cu std::vector

std::vector<int> a(n) creează exact n elemente. Citirea, accesul a[i] și algoritmul rămân aceleași; se schimbă declararea și modul de gestionare a dimensiunii.

#include <iostream>
#include <vector>

int main() {
    int n = 0;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    long long suma = 0;
    for (int i = 0; i < n; ++i) {
        suma += a[i];
    }
    std::cout << suma << '\n';
    return 0;
}

Antetul <vector> pune la dispoziție std::vector. Declarația std::vector<int> a(n); creează aici n elemente de tip int, inițializate cu zero. Citirea le înlocuiește cu datele primite. Pentru 4 și valorile 7 2 9 4, rezultatul este 22.

Cele două bucle au roluri diferite: prima memorează datele, a doua le prelucrează. Pentru o simplă sumă ai putea calcula rezultatul imediat după fiecare citire, fără vector. Păstrarea valorilor devine utilă când trebuie să le recitești, să le compari sau să le afișezi în altă ordine.

Tipul sumei este long long: limita rezultatului poate depăși ce încape într-un int de 32 de biți, chiar dacă fiecare element încape. La n = 0, nu se citește niciun element, iar suma este 0.

Parcurgerea inversă

În multe probleme introductive întâlnești declarații precum int a[1000]{};. Tabloul are 1000 de elemente, dar problema poate folosi doar primele n. Aici cerem 0 <= n <= 1000, cu aceleași limite pentru valori.

Varianta cu tablou clasic

Tabloul a[1000] are capacitate fixă. Datele ocupă doar primele n poziții, iar indicii folosiți sunt de la 0 la n - 1. Limita lui n trebuie să respecte această capacitate.

#include <iostream>

int main() {
    int n = 0;
    std::cin >> n;
    int a[1000]{};
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    for (int i = n - 1; i >= 0; --i) {
        if (i != n - 1) {
            std::cout << ' ';
        }
        std::cout << a[i];
    }
    std::cout << '\n';
    return 0;
}

Varianta cu std::vector

std::vector<int> a(n) creează exact n elemente. Citirea, accesul a[i] și algoritmul rămân aceleași; se schimbă declararea și modul de gestionare a dimensiunii.

#include <iostream>
#include <vector>

int main() {
    int n = 0;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    for (int i = n - 1; i >= 0; --i) {
        if (i != n - 1) {
            std::cout << ' ';
        }
        std::cout << a[i];
    }
    std::cout << '\n';
    return 0;
}

Pentru aceleași patru valori se afișează 4 9 2 7. Datele rămân în ordinea inițială în memorie; doar parcurgerea este inversă. Contorul este un întreg cu semn, ca să poată ajunge la -1 și să oprească bucla. Pentru n = 0, pornește chiar de la -1, deci nu accesează tabloul.

Limite și cost

Scrie i < n, nu i <= n, când pornești de la zero. Nici tablourile obișnuite, nici accesul a[i] al unui std::vector nu îți corectează automat un indice greșit. Un acces în afara limitelor are comportament nedefinit; nu te baza pe faptul că o rulare pare să funcționeze.

Declarația int a[n];, cu n citit la rulare, nu face parte din C++17 standard. Folosește o capacitate constantă suficientă sau std::vector. Fiecare variantă parcurge n valori, deci timpul este O(n). Tabloul clasic rezervă întreaga capacitate declarată, chiar dacă folosești mai puține poziții. std::vector creează aici n elemente, deci ocupă spațiu O(n).

În variantele clasice, memoria rezervată este dată de capacitatea din declarație, nu de numărul de elemente folosite. În variantele cu std::vector, stocarea din aceste exemple este proporțională cu dimensiunile citite. Algoritmul și numărul de elemente prelucrate nu se schimbă între reprezentări. Inițializarea cu {} a tabloului clasic pune la zero întreaga capacitate, inclusiv pozițiile nefolosite; acest cost este separat de parcurgerea celor n elemente sau a celor n * m celule.

Exersează

1. Care sunt primul și ultimul indice pentru n = 5?
2. Ce afișează programul de parcurgere inversă pentru un singur element, -8?
3. Cum afișezi doar elementele de pe indicii pari?
4. Modifică programul de calcul al sumei pentru a număra valorile negative.

Răspunsuri: 0 și 4; afișează -8; parcurgi indicii 0, 2, 4, ... cât timp sunt mai mici decât n; inițializezi un contor cu zero și îl mărești când a[i] < 0. Un indice par nu înseamnă că valoarea memorată acolo este pară.

Continuă cu căutarea în vectori.