Inserarea și ștergerea elementelor din vector

Inserarea într-un vector creează loc pentru o valoare nouă, iar ștergerea închide locul ocupat de un element. Într-un tablou continuu, ambele operații presupun deplasarea unor elemente. Trebuie să distingem dimensiunea logică n de capacitatea memoriei rezervate.

Folosim indici de la zero. Inserarea înaintea poziției p permite 0 <= p <= n, inclusiv adăugarea la sfârșit. Ștergerea cere însă 0 <= p < n, deoarece trebuie să existe un element pe poziția respectivă.

Cum funcționează

La inserare deplasăm elementele de la dreapta spre stânga: ultimul element ajunge pe poziția n, precedentul pe n-1 și continuăm până eliberăm p. Sensul contează. Dacă am muta întâi a[p] peste a[p+1], am pierde valoarea care trebuia deplasată ulterior.

După deplasare scriem noua valoare în a[p] și mărim n. La ștergere procedăm invers: a[p+1] este copiat în a[p], apoi continuăm spre dreapta. Micșorăm n; vechea ultimă celulă poate conține o valoare, dar nu mai aparține vectorului logic și nu trebuie afișată.

Programul introduce o valoare și apoi șterge exact elementul introdus, pentru a observa cele două transformări. Presupune 1 <= n <= 100, o poziție validă și o capacitate de 101. Varianta std::vector rezervă aici același număr de elemente și păstrează n separat, tocmai pentru a compara algoritmii. Metodele insert și erase ale containerului gestionează dimensiunea, dar nu fac deplasarea instantanee.

Exemplu urmărit pas cu pas

Din 10, 20, 30, cu p=1 și x=99, mutăm 30 în poziția 3 și 20 în poziția 2. Scriem 99 în poziția 1, obținând 10, 99, 20, 30. La ștergere, mutăm 20 spre stânga și apoi 30, revenind la 10, 20, 30.

Inserarea la p=n nu execută deplasări. Inserarea la zero mută întregul vector. Aceste două cazuri verifică dacă sensul și limitele buclelor sunt corecte.

Implementare C++17

Varianta cu tablou clasic:

#include <iostream>
int main() {
    int n, p, x, a[101];
    std::cin >> n;
    for (int i = 0; i < n; ++i)
        std::cin >> a[i];
    std::cin >> p >> x;
    for (int i = n; i > p; --i)
        a[i] = a[i - 1];
    a[p] = x;
    ++n;
    for (int i = 0; i < n; ++i)
        std::cout << a[i] << (i + 1 == n ? '\n' : ' ');
    for (int i = p; i + 1 < n; ++i)
        a[i] = a[i + 1];
    --n;
    for (int i = 0; i < n; ++i)
        std::cout << a[i] << (i + 1 == n ? '\n' : ' ');
}

Varianta echivalentă cu std::vector folosește aceleași limite și aceiași indici:

#include <iostream>
#include <vector>
int main() {
    int n, p, x;
    std::vector<int> a(101);
    std::cin >> n;
    for (int i = 0; i < n; ++i)
        std::cin >> a[i];
    std::cin >> p >> x;
    for (int i = n; i > p; --i)
        a[i] = a[i - 1];
    a[p] = x;
    ++n;
    for (int i = 0; i < n; ++i)
        std::cout << a[i] << (i + 1 == n ? '\n' : ' ');
    for (int i = p; i + 1 < n; ++i)
        a[i] = a[i + 1];
    --n;
    for (int i = 0; i < n; ++i)
        std::cout << a[i] << (i + 1 == n ? '\n' : ' ');
}

De ce funcționează și cât costă

La inserare, înaintea fiecărei mutări, elementele din dreapta au deja copia lor pe poziția următoare, iar sursa curentă nu a fost suprascrisă. La ștergere, copierea înaintează în aceeași direcție cu golul. Ordinea relativă a elementelor rămase este păstrată.

În cel mai rău caz, fiecare operație costă O(n) timp și O(1) memorie suplimentară. Capacitatea rezervată aparține datelor. O serie de n inserări la început poate ajunge la O(n²), chiar dacă fiecare inserare pare simplă.

Greșeli frecvente

Nu mări n înainte de a stabili ultima poziție sursă. Nu scrie în a[n] dacă nu există capacitate. La ștergerea repetată a elementelor care respectă o condiție, elementul nou deplasat pe poziția curentă trebuie verificat; incrementarea automată îl poate sări.

Exersează

Inserează 7 la sfârșitul vectorului 2,4,6. Câte atribuiri de deplasare sunt necesare? Dar la început?

Rezolvare explicată: La sfârșit nu deplasezi niciun element; scrii doar valoarea nouă. La început deplasezi cele trei valori spre dreapta, apoi scrii 7 în prima poziție.

Continuă să înveți

Declararea vectorilor, sortarea și secvențele.

Întrebări frecvente

În ce sens deplasez la inserare?

De la dreapta spre stânga, pornind de la ultimul element. Astfel, fiecare valoare este copiată înainte ca poziția sa originală să fie suprascrisă.

În ce sens deplasez la ștergere?

De la poziția eliminată spre dreapta, copiind fiecare succesor în locul precedentului. După deplasare micșorezi dimensiunea logică cu unu.

Ștergerea trebuie să pună zero în ultima celulă?

Nu pentru corectitudinea vectorului logic. După micșorarea lui n, acea celulă nu mai este parcursă. Zero nu reprezintă în general un marcaj valid de element șters.

Inserarea în std::vector este O(1)?

Inserarea la o poziție interioară deplasează elementele și este liniară. Adăugarea la final are alte proprietăți, dar nu trebuie confundată cu inserarea la început sau la mijloc.

Ce verific înaintea unei inserări?

Verific poziția, dimensiunea logică și capacitatea disponibilă. O poziție validă nu garantează că există și o celulă suplimentară pentru noul element.