Inserarea și ștergerea în vector

Într-un tablou cu elemente pe poziții consecutive, inserarea deplasează spre dreapta elementele de la poziția aleasă, iar ștergerea le deplasează spre stânga pe cele de după ea. Dacă din $[2,5,8]$ inserăm 4 înainte de 5, rezultatul este $[2,4,5,8]$. Trebuie să existe loc pentru elementul nou.

Într-un vector cu $n$ elemente memorate pe pozițiile $0,\dots ,n-1$, inserarea unei valori pe poziția $p$ cere deplasarea cu o poziție spre dreapta a elementelor de la $p$ până la $n-1$, ca să se elibereze locul; apoi valoarea se scrie pe poziția $p$, iar dimensiunea $n$ crește cu 1. Ștergerea elementului de pe poziția $p$ cere deplasarea cu o poziție spre stânga a elementelor de la $p+1$ până la $n-1$, care acoperă elementul șters; apoi $n$ scade cu 1. Deplasarea la inserare se face de la dreapta la stânga, începând cu ultimul element, pentru ca nicio valoare încă necesară să nu fie suprascrisă; la ștergere se merge de la stânga la dreapta. Tabloul trebuie să aibă capacitate pentru elementul nou: dacă $n$ este deja egal cu capacitatea, inserarea nu este posibilă. Numărul de mutări este $n-p$ la inserare și $n-p-1$ la ștergere, deci, în cel mai defavorabil caz, timpul este proporțional cu $n$.

Exemplul 1 — inserare. În vectorul $2,5,8$ ($n=3$, capacitate 6) se inserează valoarea 4 pe poziția 1.

1. Se mută 8 de la indicele 2 la 3: vectorul conține $2,5,8,8$.
2. Se mută 5 de la indicele 1 la 2: vectorul conține $2,5,5,8$.
3. Se scrie 4 pe poziția 1: $2,4,5,8$.
4. Dimensiunea devine $n=4$.

int v[6] = {2, 5, 8};
int n = 3, poz = 1, valoare = 4;
for (int i = n; i > poz; --i)
    v[i] = v[i - 1];
v[poz] = valoare;
++n;

Primele $n=4$ elemente sunt $2,4,5,8$, cu două mutări. Dacă deplasarea ar începe de la stânga, v[2] = v[1] ar copia 5, apoi v[3] = v[2] ar copia tot 5, iar valoarea 8 s-ar pierde.

Exemplul 2 — ștergere. Din vectorul $2,4,5,8$ se șterge elementul de pe poziția 1. Se mută 5 de la indicele 2 la 1 și 8 de la indicele 3 la 2, iar dimensiunea scade la 3.

for (int i = poz; i < n - 1; ++i)
    v[i] = v[i + 1];
--n;

Rezultatul este $2,5,8$, după două mutări. Elementul de la indicele 3 nu este șters fizic; el rămâne în memorie, dar nu mai face parte din vector, pentru că $n$ este acum 3.

Exemplul 3 — la capete. Inserarea pe ultima poziție, $p=n$, nu cere nicio mutare: valoarea se scrie direct în v[n]. Inserarea pe poziția 0 cere $n$ mutări, deci este cel mai costisitor caz. Ștergerea ultimului element nu cere nicio mutare, doar scăderea lui $n$. Pentru a șterge toate aparițiile unei valori nu trebuie repetată ștergerea cu mutări de fiecare dată; se pot copia elementele păstrate în aceeași parcurgere, cu un al doilea indice.

Urmărește vectorul după fiecare mutare și actualizează dimensiunea la momentul potrivit. Cele mai frecvente erori sunt sensul greșit al deplasării și limitele ciclului: la inserare ciclul pornește de la $n$ (nu de la $n-1$), iar la ștergere se oprește la $n-2$. Dacă enunțul indexează elementele de la 1, pozițiile și limitele se deplasează cu 1.

Exemplul 4 — urmărirea unei inserări. Ce se afișează în urma executării secvenței de mai jos?

int v[6] = {2, 5, 8}, n = 3;
for (int i = n; i > 1; --i)
    v[i] = v[i - 1];
v[1] = 4;
n++;
for (int i = 0; i < n; ++i)
    cout << v[i] << ' ';

• a) 2 4 5 8
• b) 2 4 8 8
• c) 2 5 4 8
• d) 4 2 5 8

Răspunsul corect este a). Ciclul pornește de la $i=3$ și merge descrescător până la $i=2$: v[3] = v[2] = 8, apoi v[2] = v[1] = 5. Se scrie v[1] = 4, iar $n$ devine 4. Se afișează primele patru elemente: 2 4 5 8. Varianta b) ar rezulta dacă deplasarea s-ar face de la stânga la dreapta și ar propaga valoarea 5. Varianta d) corespunde inserării pe poziția 0.

Greșeli frecvente

• Greșit: la inserare se deplasează elementele începând cu cel de pe poziția dorită, spre dreapta.
  Corect: deplasarea începe cu ultimul element, ca să nu se suprascrie valori.
• Greșit: după ștergere, vectorul își micșorează automat capacitatea.
  Corect: se micșorează doar numărul de elemente utile $n$.
• Greșit: inserarea unui element în vector costă mereu o singură operație.
  Corect: costă până la $n$ mutări.

Înainte și după