Ștergerea din vector în timpul parcurgerii C++
Evită să sari peste elemente după o ștergere. Urmărește deplasarea valorilor și alege între continuarea corectă a parcurgerii și compactare.
În acest material
Dacă ștergi un element din mijlocul unui vector, elementele din dreapta se mută cu o poziție la stânga. Dacă mărești imediat și indicele de parcurgere, poți sări peste valoarea care tocmai a ajuns pe poziția curentă.
Un exemplu cu două eliminări consecutive
Vrei să elimini valorile pare din 2 4 5. După ștergerea lui 2 de pe poziția 0, vectorul devine 4 5. Dacă i crește la 1, examinezi direct 5 și păstrezi din greșeală 4. Un test cu o singură valoare pară nu ar arăta această eroare.
La o parcurgere prin indici, poziția curentă trebuie reverificată după ștergere, deoarece acum conține alt element. Mărești indicele numai când păstrezi elementul sau când logica ta stabilește explicit următoarea poziție validă.
Continuarea cu iteratorul returnat
Pentru std::vector, erase întoarce un iterator către elementul de după cel eliminat, în noua secvență, sau end dacă nu mai există unul. O parcurgere cu iteratori trebuie să folosească acea continuare, nu să incrementeze un iterator invalidat de ștergere.
end() reprezintă poziția de după ultimul element și nu poate fi dereferențiat. După eliminarea ultimului element, verifici din nou condiția de oprire înainte să citești o valoare.
Din 2,4,5 eliminăm 2 de la indicele 0. Vectorul devine 4,5. Dacă mărim imediat indicele, sărim peste 4, care trebuie și el eliminat.Mărește schema ↗
Ștergerile repetate pot costa mult
Fiecare ștergere din interior poate muta multe elemente. Dacă elimini astfel un număr mare de poziții, costul total poate deveni pătratic. O alternativă este compactarea: un indice citește, iar altul scrie în față numai valorile păstrate.
Pentru un tablou clasic, după compactare actualizezi dimensiunea logică. Pentru un vector, după compactare poți micșora dimensiunea la numărul elementelor păstrate. În ambele cazuri, trebuie să păstrezi ordinea dacă aceasta este cerută de problemă.
Teste care separă cazurile
Folosește două elemente consecutive de eliminat, primul element, ultimul element și cazul în care toate trebuie eliminate. Verifică și cazul în care nu elimini nimic. Pentru 2 4 5, rezultatul corect este numai 5; pentru 2 4, rezultatul este vectorul gol.
Nu confunda eliminarea unei valori cu eliminarea unei poziții. Dacă aceeași valoare apare de mai multe ori, enunțul trebuie să precizeze dacă elimini prima apariție sau toate aparițiile.
Continuă cu ștergerea din tablouri, iteratorii și complexitatea.
Întrebări frecvente
De ce sar peste elemente când șterg din vector într-un for?
Ștergerea mută elementele următoare spre stânga. Dacă mărești imediat indicele, nu mai examinezi elementul care tocmai a ajuns pe poziția curentă. Duplicate consecutive ale valorilor de eliminat evidențiază eroarea.
Ce iterator folosesc după vector.erase?
Pentru continuarea parcurgerii, folosește iteratorul returnat de erase, care desemnează următorul element sau sfârșitul. Iteratorul către elementul șters nu mai este valid.
De ce sunt costisitoare ștergerile repetate din mijlocul vectorului?
Fiecare ștergere poate muta multe elemente. Repetate de O(n) ori, pot produce O(n²) muncă. Compactarea elementelor păstrate și o singură scurtare finală evită aceste mutări repetate.