Clasele vector<>. Sume parțiale pe matrice.

vector<>

Până acum cunoașteți tipurile tradiționale de tablou, care se declară cu sintaxa TipDeBază nume[dimensiune]. Ele funcționează, dar sunt moștenite din limbajul C (1972). Au deci câteva neajunsuri:

• nu își memorează dimensiunea, de aceea trebuie să o memorăm separat și să ne amintim pentru fiecare dimensiune care vector o folosește;
• când sunt trimise în funcții, devin un simplu pointer, și trebuie să fim atenți să nu facem operații fără sens cu acel pointer (se fac foarte ușor);
• nu pot fi redimensionați (fără alocare dinamică);
• de fapt, conform standardului, dimensiunea trebuie să fie o constantă determinată la compilare (însă GCC permite și o dimensiune variabilă).

În C++, spre deosebire de C, biblioteca standard ne pune la dispoziție o alternativă, șablonul (template-ul) de tipuri (clase) numit vector. Spre deosebire de tablourile tradiționale:

• au dimensiune, care poate fi accesată folosind funcția internă size;
• această dimensiune se poate schimba oricând;
• nu se transformă în pointer;
• îi putem returna din funcții;
• conținutul nu se alocă pe stivă, deci putem avea tablouri oricât de mari dorim fără a le aloca global sau dinamic.

vector este în antetul <vector> și în spațiul de nume std (dacă avem using namespace std; nu trebuie să scriem asta).

Declararea vectorilor

vector<int> name;

int N;
cin >> N;
struct Structure {
    int a, b;
}
vector<Structure> p(N);

vector<short int> alphabet(26, -1);

vector<int> x = y;

vector<vector<int>> x(N, vector<int>(M));

Operații de bază

vector<int> a(5);

a[0]

a[1] = 67

a.size()

a.capacity()

Operații care schimbă dimensiunea

a.resize(9)

a.resize(1)

a.reserve(32)

a.push_back(8)

a.pop_back()

Iteratori

Iteratorul este un obiect care indică o poziție din vector. Este de tipul vector<TipDeBază>::iterator; putem scrie auto pentru a nu folosi tot numele.

a.begin()

a.end()

a.begin() + 1

a.end() - a.begin()

++a

Operații bazate pe iteratori

a.erase(a.begin())

a.insert(a.begin(), 5)

a.insert(a.begin(), b.begin(), b.end())

Sume parțiale pe matrice

Definim de acum funcția safe_get care va returna valoarea de la indicele dat dintr-un vector, dacă indicele e valid; în caz contrar, va returna 0. O folosim pentru a nu fi nevoiți să testăm mereu dacă urmează să scădem din poziția -1.

inline int safe_get(vector<int> const &a, int const i) {
    if (i < 0 || a.size() <= i) {
        return 0;
    }
    return a[i];
}

inline int safe_get(vector<vector<int>> const &a, int const i, int const j) {
    if (i < 0 || a.size() <= i || j < 0 || a[0].size() <= j) {
        return 0;
    }
    return a[i];
}

Să luăm ca exemplu matricea a:

Se calculează, pentru fiecare i și j, suma elementelor aflate pe rânduri până la i și coloane până la j. Matricea ps:

Cum calculăm această sumă?

Putem trece la suma pentru o anumită celulă folosind sumele anterioare:

1. se ia valoarea celulei actuale din matrice;
2. se iau toate celulele cu i mai mic și j mai mic sau egal decât cea actuală (deci suma de deasupra celei actuale);
3. se iau toate celulele cu j mai mic și i mai mic sau egal decât cea actuală (deci suma din stânga celei actuale);
4. acum toate celulele care ne interesează sunt selectate; totuși, unele sunt selectate de două ori, mai precis cele care îndeplinesc ambele condiții 2. și 3.; trebuie, așadar, scăzute acele elemente, adică suma din stânga-sus.

ps[i][j] = a[i][j] + safe_get(ps, i - 1, j) + safe_get(ps, i, j - 1) - safe_get(ps, i - 1, j - 1);

Mai rămâne să calculăm suma pentru o anumită interogare. De exemplu, de la (1; 1) până la (3; 2). Notăm (i0; j0; i1; j1).

Putem să o calculăm folosind doar sumele calculate deja.

1. se ia valoarea ultimei celule din interval (în dreapta-jos); aceea va reprezenta evident tot intervalul, dar și alte elemente pe care le vom exclude;
2. se ia valoarea celulei de deasupra colțului dreapta-sus al intervalului, care va conține doar elemente ce trebuie excluse;
3. se ia valoarea celulei din stânga colțului stânga-jos al intervalului, care va conține doar elemente ce trebuie excluse;
4. și acum avem elemente excluse de două ori, și anume celula aflată în stânga-sus față de colțul stânga-sus al intervalului.

int get_sum(vector<vector<int>> &ps, int const i0, int const j0) {
    return safe_get(ps, i1, j1)
           - safe_get(ps, i1 - 1, j1)
           - safe_get(ps, i1, j1 - 1)
           + safe_get(ps, i1 - 1, j1 - 1);
}

Alte sume parțiale (de discutat)

• Sume parțiale pentru indici cu rație (din x în x).
• Sume parțiale pe diagonală.
• Sume parțiale pe un trapez dreptunghic delimitat la diagonală.
• Sume parțiale pe triunghi dreptunghic.
• Sume parțiale pe linii oblice care nu sunt neapărat diagonale.
• Sume parțiale pe paralelogram.