Usuwanie z std::vector: erase()

1. erase() i unieważnianie odniesień

Kiedy po raz pierwszy słyszysz „usunąć element z tablicy”, mózg rysuje obrazek: skreślasz jeden kwadracik, reszty nie ruszasz. W przypadku std::vector tak się nie da z praktycznych powodów: przechowuje on elementy ciągłe w pamięci, bez dziur. Dlatego usunięcie to zazwyczaj przesunięcie pozostałych elementów w lewo. A to oznacza, że „pozycje” się zmieniają i niektóre „zapamiętane wskazania” na elementy przestają być poprawne.

Wyobraźmy sobie listę zadań: ["kupić mleko", "umyć kota", "oddac laboratorium"]. Jeśli usunąć środkowy element, wektor musi sprawić, by elementy znów leżały obok siebie: ["kupić mleko", "oddac laboratorium"]. Dla ciebie to wygląda logicznie, ale dla iteratora, który „patrzył” na element „oddac laboratorium”, to już inna historia: mógł stać się nieprawidłowy albo wskazywać na „coś innego”.

Model bez dziur: co fizycznie się dzieje przy erase

Zanim zaczniesz pisać kod, warto przez chwilę włączyć „tryb rentgena” i wyobrazić sobie, jak wygląda vector od środka. Ma on bufor pamięci, który może pomieścić capacity() elementów, oraz rzeczywistą liczbę elementów size() (to, co faktycznie istnieje). Usunięcie elementu w środku to nie tylko „minus jeden do size”, ale też przesunięcie elementów, żeby zasypać dziurę.

Schematycznie można to przedstawić tak:

Przed:
indeksy:  0      1      2      3
dane:    [10]   [20]   [30]   [40]

Usuwamy element o indeksie 1 (20)

Po:
indeksy:  0      1      2
dane:    [10]   [30]   [40]

Element [30] przejechał na miejsce [20], [40] przejechał na miejsce [30]. Ważne jest to, że „na miejscu usuniętego” znajduje się inny element. Z tego powodu wszelkie odniesienia do elementów po prawej (iteratory, referencje) stają się niebezpieczne: albo wskazują nie tam, albo w ogóle „nigdzie”.

erase(pos): usuwamy jeden element przy pomocy iteratora

std::vector usuwa elementy metodą erase, a kluczowe jest to, że przyjmuje ona iterator, a nie indeks. To ma sens: iterator to „pozycja” w kontenerze, a erase umie usuwać po tej pozycji.

„Usunąć po indeksie” też się da, ale wtedy najpierw zamieniasz indeks na iterator (albo dochodzisz do pozycji używając ++), a dopiero potem wywołujesz erase.

Mini‑przykład: usuniemy drugi element (20), nie używając arytmetyki iteratorów, tylko ++.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{10, 20, 30, 40};

    auto it = v.begin();
    ++it;            // teraz it wskazuje na 20
    v.erase(it);     // usuwamy 20

    for (std::size_t i = 0; i < v.size(); ++i) {
        std::cout << v[i] << ' ';  // 10 30 40
    }
    std::cout << '\n';
}

erase(it) nie „zeruje” miejsca, lecz przebudowuje sekwencję. Po usunięciu następny element (30) zajmuje miejsce usuniętego.

erase(first, last): usuwamy zakres [first, last)

Czasem trzeba usunąć nie pojedynczy element, lecz cały fragment: na przykład „usunąć elementy od 2. do 4.”. W vector robi się to przez erase(first, last), i tu jest zasadnicza reguła, z którą spotkasz się jeszcze wiele razy w C++: zakresy są podawane jako [first, last), czyli „lewy włączony, prawy wyłączony”.

last to pozycja po ostatnim usuwanym elemencie.

Usuńmy z [1, 2, 3, 4, 5] liczby 2, 3, 4, znów ustawimy iteratory używając ++:

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{1, 2, 3, 4, 5};

    auto first = v.begin();
    ++first; // na 2

    auto last = first;
    ++last;  // na 3
    ++last;  // na 4
    ++last;  // na 5 (czyli "po 4")

    v.erase(first, last); // usuwamy 2,3,4

    for (std::size_t i = 0; i < v.size(); ++i) {
        std::cout << v[i] << ' ';  // 1 5
    }
    std::cout << '\n';
}

Przydatna praktyczna formuła do samosprawdzenia: last powinien wskazywać na element po ostatnim usuwanym. W przykładzie ostatni usuwany to 4, więc last powinien wskazywać na 5.

Co zwraca erase, i dlaczego to ratuje pętle

Gdyby erase po prostu usuwał i nic nie zwracał, usuwanie podczas iteracji zamieniłoby się w grę „zgadnij, gdzie teraz wskazuje iterator”. Dlatego erase zwraca iterator: pozycję na element, który znalazł się na miejscu usuniętego (albo end(), jeśli usunięto ostatni element).

Mini‑przykład: usuniemy 6 i będziemy dalej pracować z iteratorem, który zwróciło erase.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{5, 6, 7, 8};

    auto it = v.begin();
    ++it;               // it na 6
    it = v.erase(it);   // usunęliśmy 6, it teraz na 7

    if (it != v.end()) {
        std::cout << *it << '\n';  // 7
    }
}

Kluczowy nawyk: po erase nie ufamy staremu iteratorowi, tylko używamy tego, który zwróciła funkcja.

Usuwanie w pętli: zły i dobry wariant

Gdy po raz pierwszy piszesz „usuń wszystkie elementy równe X”, ręka sama wypisuje coś typu: „idę przez wektor, jeśli znalazłem X — erase”. I to jest przypadek, kiedy kod może „czasem działać”, co jest szczególnie niebezpieczne.

Zły scenariusz zwykle wygląda tak: iterator jest inkrementowany w nagłówku pętli, a wewnątrz robimy jeszcze erase, które psuje bieżącą pozycję.

#include <vector>

int main() {
    std::vector<int> v{1, 2, 2, 3};

    for (auto it = v.begin(); it != v.end(); ++it) {
        if (*it == 2) {
            v.erase(it); // po tym it jest już niebezpieczne
        }
    }
}

Prawidłowy pomysł jest taki: jeśli usunęliśmy bieżący element, to „następna pozycja” jest już zwrócona przez erase. A jeśli nie usunęliśmy — wtedy spokojnie robimy ++it.

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v{1, 2, 2, 3};

    for (auto it = v.begin(); it != v.end(); ) {
        if (*it == 2) {
            it = v.erase(it);   // bierzemy zwróconą pozycję
        } else {
            ++it;               // poruszamy się sami
        }
    }

    for (std::size_t i = 0; i < v.size(); ++i) {
        std::cout << v[i] << ' '; // 1 3
    }
    std::cout << '\n';
}

Zwróć uwagę: w nagłówku pętli nie ma ++it. To nie „sprytne zagranie”, lecz dyscyplina: teraz tylko jedno miejsce w kodzie odpowiada za przesuwanie iteratora i nie dostaniesz „podwójnego kroku” ani kroku po już nieistniejącej pozycji.

Unieważnianie: co dokładnie staje się nieprawidłowe po erase

Przez unieważnianie rozumiemy sytuację, gdy iterator/referencja/wskaźnik już nie gwarantuje poprawnego dostępu do tego elementu, na który „patrzył”. Użycie takiego obiektu to jak czytanie adresu na kopercie po tym, jak dom „przeprowadził się” do innego miasta.

Dla std::vector przydatna jest taka ściąga:

O „przeprowadzce” wektora mówiliśmy wcześniej, gdy omawialiśmy capacity() i realokację pamięci. Tutaj utrwalamy konsekwencję: jeśli wektor zmienił wewnętrzny bufor, każda „przywiązana do elementu” rzecz (iterator, referencja) staje się podejrzana.

Krótka uwaga z życia C++: sformułowania standardowych reguł dotyczących erase i unieważniania były historycznie dyskutowane i doprecyzowywane. Czyli jeśli dziś wydaje ci się, że erase jest „śliskie”, to normalne — temat jest naprawdę subtelny.

Referencja do elementu: dlaczego T& jest niebezpieczna przy modyfikacji vector

Kiedy piszesz int& ref = v[1];, tworzysz referencję — drugą nazwę dla konkretnego elementu wektora. Na pierwszy rzut oka wygląda jak zwykła zmienna, ale ma istotną różnicę: żyje nie sama, lecz odnosi się do pamięci należącej do wektora. Jeśli wektor się przebuduje (usunięcie/„przeprowadzka”), referencja może stać się nieprawidłowa.

Przykład „wygląda niegroźnie, ale w praktyce jest niebezpieczny”:

#include <vector>

int main() {
    std::vector<int> v{10, 20, 30};

    int& ref = v[1];        // ref odnosi się do "20"
    v.erase(v.begin());     // usunęliśmy 10, elementy się przesunęły

    // ref teraz może odnosić się "gdzie indziej".
}

Tu ważne jest, by nie próbować zgadywać „co dokładnie się stanie”: w modelu edukacyjnym wystarczy zrozumieć, że po zmianie struktury wektora stare referencje/iteratory nie nadają się do użycia.

Jeszcze bardziej życiowy scenariusz: weźmiesz referencję, potem zrobisz push_back, a vector postanowi się przeprowadzić do nowego bufora (bo skończyła się capacity()). Wtedy referencja najpewniej przestanie być ważna.

#include <vector>

int main() {
    std::vector<int> v{10, 20, 30};

    int& ref = v[1];   // "20"
    v.push_back(40);   // może nastąpić realokacja

    // ref może stać się nieprawidłowy
}

Tak, to nieprzyjemne. Ale teraz widać, dlaczego w projektach często zaleca się nie przechowywać referencji do elementów vector dłużej niż konieczne.

Mini‑task‑lista: usuwamy zadanie po indeksie

Na razie nie mamy klas ani złożonej architektury, więc zrobimy edukacyjny „mini‑task‑lista”: std::vector<std::string> tasks, gdzie każdy string to jedno zadanie. Dodamy usuwanie po numerze (indeksie), ale ostrożnie: najpierw sprawdzimy granice, potem znajdziemy iterator i wywołamy erase.

#include <iostream>
#include <string>
#include <vector>

int main() {
    std::vector<std::string> tasks{"Buy milk", "Wash cat", "Submit lab"};

    std::size_t idx = 0;
    std::cin >> idx;

    if (idx < tasks.size()) {
        auto it = tasks.begin();
        for (std::size_t k = 0; k < idx; ++k) ++it;
        tasks.erase(it);
    }

    for (std::size_t i = 0; i < tasks.size(); ++i) {
        std::cout << i << ": " << tasks[i] << '\n';
    }
}

Tu ukryte są dwa ważne nawyki. Po pierwsze, sprawdzamy idx < tasks.size(), ponieważ indeks pochodzi „z zewnątrz” (z wejścia), więc nie zasługuje na bezwarunkowe zaufanie. Po drugie, nie próbujemy usuwać po indeksie bezpośrednio, lecz uczciwie konwertujemy indeks na iterator, bo erase działa na pozycjach.

Jeśli właśnie pomyślałeś „ech, chciałbym użyć tasks.begin() + idx”, to gratulacje: twój mózg już wyczuł ideę iteratorów random-access. Ale w tej części kursu trzymamy się tego, co już wprowadziliśmy: begin()/end() i ++.

2. Typowe błędy przy usuwaniu z std::vector

Błąd nr 1: używać iteratora po erase, jakby nic się nie stało.
erase zmienia strukturę wektora i sprawia, że bieżąca pozycja jest „śliska”. Typowy objaw: program czasem pomija elementy, czasem pada, czasem zachowuje się dziwnie. Leczy się to dyscypliną: po it = v.erase(it) używamy dokładnie zwróconego iteratora i nie robimy ++it „z przyzwyczajenia”.

Błąd nr 2: pomylić zakres [first, last) i oczekiwać, że last też zostanie usunięty.
To klasyka: chcesz usunąć „od 2 do 4 włącznie”, ustawiasz last na element 4, a potem dziwisz się, że 4 pozostał. Prawidłowy model to nie „włącznie”, lecz „ostatni niewłączony”: last powinien wskazywać na pozycję po ostatnim usuwanym elemencie.

Błąd nr 3: trzymać referencję (T&) do elementu, a potem modyfikować vector.
Referencja wygląda jak wygodna zmienna, ale jest powiązana z wewnętrzną pamięcią kontenera. Po erase, push_back (w przypadku realokacji) lub nawet reserve (jeśli nastąpiła „przeprowadzka”) taka referencja może stać się nieprawidłowa. Jeśli trzeba „po prostu zapamiętać wartość”, weź kopię (np. int x = v[i];). Jeśli chcesz „zapamiętać pozycję”, pamiętaj, że pozycja może się złamać przy modyfikacjach.

Błąd nr 4: próbować usuwać w pętli for (...; ++it) i wewnątrz robić erase(it).
Tu psuje się logika kroku: erase już przebudował sekwencję, a ty dodatkowo inkrementujesz iterator w stary sposób. W najlepszym wypadku pominiesz sprawdzenie elementu, który przesunął się na miejsce usunięte; w najgorszym — dostaniesz dostęp do nieprawidłowej pozycji. Niezawodny wzorzec: pętla bez automatycznego ++it, gdzie krok wykonuje się albo przez ++it, albo przez it = erase(it).

Błąd nr 5: myśleć, że unieważnianie występuje tylko po erase.
Nawet jeśli dziś koncentrujemy się na usuwaniu, warto pamiętać o związku z tematem capacity(): jeśli wektor przeprowadził się z powodu zwiększenia bufora, psują się wszystkie iteratory/referencje. Dlatego logika typu „zachowałem iterator, potem zrobiłem dużo push_back, potem wróciłem do iteratora” to zaproszenie do przygody, której nie zamawiałeś.