Ștergerea elementelor

A șterge un element dintr-un vector înseamnă a-l elimina și a „strânge” golul rămas, astfel încât elementele să rămână în continuare alăturate. Este operația complementară inserării: de data aceasta nu facem loc, ci umplem un loc.

Să presupunem că vrem să eliminăm elementul de pe poziția 3:

Pașii sunt:

1. alegem poziția elementului de șters;
2. deplasăm cu o poziție „la stânga” toate elementele de după el, suprascriind astfel valoarea eliminată;
3. scădem cu 1 numărul total de elemente.

Spre deosebire de inserare, aici deplasarea se face de la cap spre coadă (de la poziția ștearsă spre ultimul element), pentru ca fiecare element să fie copiat înainte de a fi, la rândul lui, suprascris.

Notăm cu v vectorul, cu n numărul de elemente și cu k poziția elementului eliminat:

int n, v[1001], k;
// ...
for (int i = k + 1; i < n; i++) {
    v[i - 1] = v[i];   // mutam la stanga elementele de dupa k
}
n--;                   // avem un element mai putin

Bucla copiază fiecare element de după poziția k peste cel dinaintea lui, „acoperind” valoarea ștearsă. La final scădem numărul de elemente.

Enunț. Se citește un număr n, $n \in (0, 10^3]$, urmat de n numere întregi, elementele unui vector. Să se elimine din vector toate elementele divizibile cu 12 și să se afișeze elementele rămase, separate printr-un spațiu.

Vom vedea două abordări: una intuitivă, care aplică direct schema de ștergere, și una mai eficientă.

Varianta 1: prin deplasare

#include <iostream>
using namespace std;
int n, v[1001];
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    int i = 0;
    while (i < n)
        if (v[i] % 12 == 0) {
            for (int j = i + 1; j < n; j++) {
                v[j - 1] = v[j];
            }
            n--;
        } else {
            i++;
        }
    for (i = 0; i < n; i++) {
        cout << v[i] << ' ';
    }
    return 0;
}

De fiecare dată când întâlnim un număr divizibil cu 12, îl ștergem deplasând la stânga elementele care îl urmează.

Observă că, după o ștergere, nu avansăm indicele i. Motivul este că, prin deplasare, un element nou alunecă chiar pe poziția i, iar acesta trebuie verificat la rândul lui. Tocmai de aceea am folosit aici while în locul unui for: avansăm indicele doar atunci când elementul curent rămâne în vector.

Pentru intrarea 8 și vectorul 5 24 7 12 9 36 11 8 se obține 5 7 9 11 8, iar pentru 5 și 12 24 36 72 60 (toate divizibile cu 12) vectorul rămâne gol.

Varianta 2: mai eficientă

În varianta de mai sus, fiecare ștergere declanșează o nouă deplasare, deci dacă eliminăm multe elemente facem un număr mare de mutări. Putem rezolva problema dintr-o singură parcurgere, folosind un al doilea indice.

#include <iostream>
using namespace std;
int n, v[1001];
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    int k = 0; // cate elemente am eliminat pana acum
    for (int i = 0; i < n; i++)
        if (v[i] % 12 == 0) k++;
        else v[i - k] = v[i];
    n -= k;
    for (int i = 0; i < n; i++) cout << v[i] << ' ';
    return 0;
}

Ideea este simplă: parcurgem vectorul o singură dată și ținem într-o variabilă k câte elemente am eliminat până în acel moment. Când întâlnim un element divizibil cu 12, doar creștem k; când întâlnim un element care rămâne, îl mutăm cu k poziții mai în față, pe poziția i-k. La final scădem din n numărul total de eliminări.

Această variantă mută fiecare element cel mult o dată, în timp ce prima poate muta același element de mai multe ori. Pentru vectori mari, diferența de timp de execuție devine semnificativă.

Ștergerea unui element se reduce la deplasarea spre stânga a elementelor care îl urmează, urmată de scăderea numărului de elemente. Atunci când trebuie să eliminăm mai multe elemente după o condiție, varianta cu un al doilea indice (compactarea într-o singură parcurgere) este mult mai eficientă decât ștergerea repetată. În continuare vom vedea cum putem căuta un element într-un vector.