Trzy strategie usuwania w std::vector

1. Wprowadzenie

Kiedy ktoś mówi „usuń element”, umysł wyobraża coś prostego: wziął i usunął. Ale std::vector to nie magiczne pudełko, w którym elementy unoszą się w powietrzu. To gęsty ciąg komórek pamięci. Usunięcie niemal zawsze oznacza „przesunięcie ogona”, a to wpływa na iteratory, indeksy i nawet na czytelność kodu. Dlatego mamy nie jedno zadanie, lecz co najmniej trzy różne scenariusze.

Pierwszy scenariusz — punktowy: „usunąć jeden konkretny element” (np. zadanie po id). Drugi — masowy: „usunąć wszystkie elementy, które spełniają warunek” (np. wszystkie ukończone zadania). Trzeci — funkcjonalny w duchu: „zbudować nową listę według zasad, nie ruszając oryginału” (np. lista aktywnych zadań lub lista stringów do wydruku). W każdym scenariuszu właściwe narzędzie będzie inne — i to właśnie oszczędza godziny debugowania oraz sprawia, że kod jest przewidywalny.

Aby to nie było abstrakcją, kontynuujemy nasz mini-projekt: konsolowy tracker zadań. Przechowujemy zadania w std::vector, każde ma id, title i status.

#include <string>

enum class TaskStatus { Todo, Done };

struct Task {
    int id{};
    std::string title;
    TaskStatus status{TaskStatus::Todo};
};

2. Strategia nr 1: usuwanie punktowe przez erase

Jeśli trzeba usunąć dokładnie jeden element, najczęściej najbardziej czytelna opcja to znaleźć go i usunąć. Brzmi trywialnie, ale tu ważna jest dyscyplina: usuwamy nie po „indeksie, który gdzieś zapamiętaliśmy”, lecz po iteratorze, który otrzymaliśmy teraz. To zmniejsza ryzyko przypadkowego usunięcia „czegoś innego” po innych operacjach na liście.

Zacznijmy od funkcji wyszukującej. Potrafimy już używać std::find_if, lambdy też są znane — więc czyta się to całkiem po ludzku.

#include <algorithm>
#include <vector>

bool remove_task_by_id(std::vector<Task>& tasks, int id) {
    auto it = std::find_if(tasks.begin(), tasks.end(),
                           [id](const Task& t) { return t.id == id; });

    if (it == tasks.end()) return false;
    tasks.erase(it);
    return true;
}

Zwróć uwagę na istotny szczegół: sprawdzamy it != end(). To nie „nadmiarowe zabezpieczenie”, to normalny kontrakt STL: end() nie można dereferencjonować, nie można przez niego usuwać, to granica, a nie element.

Czasem nowicjusze chcą zrobić tak: „przecież znam indeks, użyjmy erase(begin() + idx)”. Działa to, ale tylko dopóki indeks nie zacznie być liczony „po starych danych”. W projekcie często wygląda to tak: znalazłeś indeks, potem gdzieś po drodze usunięto inny element, a potem usuwasz po starym indeksie. Powstaje usunięcie „z fabułą”: miało zniknąć zadanie "Buy milk", a zniknęło "Pay rent". I, co zaskakujące, kompilator milczy.

Jeśli jednak pracujesz z indeksem, przynajmniej przekonwertuj go na iterator bezpośrednio przed usunięciem i trzymaj to w jednej funkcji, aby nie było „indeksu-podróżnika”.

#include <vector>

bool remove_task_by_index(std::vector<Task>& tasks, std::size_t idx) {
    if (idx >= tasks.size()) return false;
    tasks.erase(tasks.begin() + static_cast<std::ptrdiff_t>(idx));
    return true;
}

Tu świadomie sprawdzamy granice, i tak, rzutowanie wygląda nieco „urzędowo”. To wskazówka, że wariant z find_if jest często prostszy i bezpieczniejszy.

Jeszcze jedna ważna uwaga o „koszcie z intuicji”. Pojedyncza operacja erase(it) w vector niemal zawsze oznacza, że elementy po prawej stronie usuniętego przesuną się o jedną pozycję w lewo. To nie jest O(1) „klik”, lecz operacja z przesunięciem ogona. Jeśli robisz to raz — w porządku. Problemy zaczynają się, gdy robisz to setki razy w pętli. Wtedy zapraszam do następnej sekcji.

3. Strategia nr 2: masowe usuwanie przez erase-remove

Gdy trzeba usunąć wszystkie elementy spełniające warunek, „naiwna” ścieżka wygląda tak: iterujesz i za każdym razem wywołujesz erase, gdy warunek prawdziwy. Czasem próbują to robić w range-for (co jest naprawdę smutne). Nawet jeśli poprawnie napiszesz pętlę iteratorową, zostaje drugi problem: będziesz wykonywać wiele przesunięć ogona. Im więcej usunięć — tym więcej „tasowania” elementów, a więc bliżej do ukrytego O(N²) w odczuciu.

Idiom erase-remove rozwiązuje to elegancko: najpierw jedną przebiegłem grupujemy „dobre” elementy na początku, a potem jednym erase odcinamy ogon. Zamiast dziesiątek/setek przesunięć mamy jedno „masowe przesunięcie” (faktycznie — move/przypisania elementów) i jedno realne zmniejszenie rozmiaru.

Wyobraźmy sobie zadanie: usuń wszystkie zadania o statusie Done.

#include <algorithm>
#include <vector>

int remove_done_tasks(std::vector<Task>& tasks) {
    auto new_end = std::remove_if(tasks.begin(), tasks.end(),
                                  [](const Task& t) {
                                      return t.status == TaskStatus::Done;
                                  });

    int removed = static_cast<int>(tasks.end() - new_end);
    tasks.erase(new_end, tasks.end());
    return removed;
}

Zauważ ważną „filozofię” predykatu: remove_if pyta nie „kogo zostawić”, lecz „kogo usunąć”. Jeśli lambda zwraca true, element jest uważany za „zły” i zostanie wypchnięty na ogon.

Bardzo pomocne jest wyobrażenie:

Przed remove_if:
[ A ][ B ][ C ][ D ][ E ][ F ]

Po remove_if (logicznie):
[ A ][ C ][ E ][ ? ][ ? ][ ? ]
                ^ new_end

Po erase(new_end, end):
[ A ][ C ][ E ]

Znaków zapytania nie należy traktować jako „zepsutej pamięci”, ale na pewno nie są to „aktualne dane”. Tam mogą być stare wartości, duplikaty — cokolwiek — i nie wolno ich czytać jako wynik.

Jeszcze jedna praktyczna uwaga: po remove_if rozmiar tasks.size() się nie zmienia. Jeśli zapomnisz drugiego kroku erase, możesz zobaczyć „dziwne ogony”. Student zwykle mówi: „u mnie remove_if nie działa”. W rzeczywistości działa, po prostu zatrzymałeś się w połowie drogi.

Jeśli chcesz wydrukować wynik zaraz po remove_if, drukuj tylko zakres [begin, new_end).

#include <iostream>
#include <algorithm>
#include <vector>

void debug_print_prefix(const std::vector<Task>& tasks) {
    auto new_end = std::remove_if(tasks.begin(), tasks.end(),
                                  [](const Task& t) {
                                      return t.status == TaskStatus::Done;
                                  });

    for (auto it = tasks.begin(); it != new_end; ++it) {
        std::cout << it->id << ": " << it->title << '\n';
    }
}

Tak, to styl „debugowy”: tymczasowo korzystamy ze znajomości new_end, aby upewnić się, że logika działa.

4. Strategia nr 3: rebuild — zbudować nowy wynik

Czasem największym problemem usuwania nie jest prędkość ani unieważnienia, lecz czytelność. Zwłaszcza gdy wokół usuwania pojawiają się dodatkowe reguły: „usuń ukończone, ale tylko jeśli są starsze…”, „usuń puste tytuły”, „usuń duplikaty…”. Zaczynasz mutować vector, jednocześnie śledząc iteratory, i w pewnym momencie kod wygląda jak „uwaga, szkło” (i to jeszcze w dobry dzień).

Podejście rebuild oznacza: nie ruszamy oryginalnego kontenera, budujemy nowy. To podobne do przepisywania schludnych notatek: nie rwiesz starego arkusza, tylko przenosisz potrzebne rzeczy.

Filtrowanie: copy_if i aktywne zadania

Załóżmy, że potrzebujemy listy tylko aktywnych zadań (status Todo), a oryginalnej listy chcemy nie naruszać (np. dla historii).

#include <algorithm>
#include <vector>

std::vector<Task> build_active_tasks(const std::vector<Task>& tasks) {
    std::vector<Task> active(tasks.size());

    auto out_end = std::copy_if(tasks.begin(), tasks.end(), active.begin(),
                                [](const Task& t) {
                                    return t.status == TaskStatus::Todo;
                                });

    active.erase(out_end, active.end());
    return active;
}

Tak, jest tu „dwukrokowość”, podobna do erase-remove, ale sens inny. Nie „usuwamy ze starego”, tylko „zbieramy nowe”. Drugi krok erase(out_end, end) to po prostu skrócenie active, bo wcześniej zarezerwowaliśmy maksymalną przestrzeń.

Nowicjusze często chcą napisać std::vector<Task> active; i potem copy_if(..., active.begin(), ...). Ale begin() pustego wektora nie wskazuje miejsca, gdzie można pisać. Dlatego albo wcześniej robimy odpowiedni rozmiar, albo używamy technik wstawiania przez inserter-y (ale to odrębny temat; tu nie rozpraszamy).

Transformacja: transform i linie do wydruku

std::transform to nie usuwanie, lecz przekształcenie jednego zbioru danych w inny. W naszym „wyborze strategii” stoi obok rebuild, ponieważ często rzeczywiste zadanie to nie „usuń”, a „stwórz reprezentację”.

Na przykład chcemy listę stringów do wydruku w formacie "[id] title".

#include <algorithm>
#include <string>
#include <vector>

std::vector<std::string> build_task_lines(const std::vector<Task>& tasks) {
    std::vector<std::string> lines(tasks.size());

    std::transform(tasks.begin(), tasks.end(), lines.begin(),
                   [](const Task& t) {
                       return "[" + std::to_string(t.id) + "] " + t.title;
                   });

    return lines;
}

Tutaj nie ma zmniejszania rozmiaru, bo transform robi „jeden do jednego”. To czyste przekształcenie: ile było zadań — tyle powstało linii.

Czasem wygodnie jest połączyć filtrowanie i transformację w dwóch krokach: najpierw build_active_tasks, potem build_task_lines. Często czyta się to lepiej niż „jeden ogromny loop na 40 linii z if-ami”.

5. Jak wybrać strategię: czytelność i „koszt z intuicji”

Gdy znasz trzy strategie, nasuwa się pytanie: „która jest właściwa?” Odpowiedź jest lekko irytująca, ale szczera: właściwa jest ta, która odpowiada zadaniu i upraszcza kod, a nie ta, która jest najbardziej sprytna. Nie piszemy kodu dla zawodów w trikach z iteratorami. Piszemy kod, który za tydzień przeczyta ktoś (może ty sam, ale już zmęczony).

Poniżej tabela, która zwykle ratuje przed rozterkami „a może zawsze erase-remove?”:

Przydatne jest też mieć w głowie prosty schemat blokowy wyboru. Nie zastąpi on myślenia, ale czasem ratuje w momencie „już się pogubiłem”.

flowchart TD
    A[Trzeba 'usunąć'] --> B{Usuwamy dokładnie 1 element?}
    B -- Tak --> C["find_if + erase(it)"]
    B -- Nie --> D{"Trzeba zmodyfikować oryginalny vector?"}
    D -- Tak --> E["remove_if + erase(new_end, end)"]
    D -- Nie --> F[rebuild: copy_if / transform]

Teraz kilka słów o „złożoności z intuicji”. Jeśli usuwasz elementy pojedynczo wiele razy, vector będzie wielokrotnie przesuwać ogon. To przypomina sytuację, gdy wyjmujesz co trzecią książkę z półki i za każdym razem przesuwasz pozostałe, żeby nie zostawić dziury. Można, ale będzie powoli i stresująco.

Dlatego „wiele pojedynczych erase” to zapach problemu. Czasem jest to uzasadnione (np. usuwasz parę elementów na żądanie użytkownika), ale jeśli czyścisz masowo — idiom erase-remove zwykle wygrywa i pod względem wydajności, i czytelności.

6. Mini-projekt: komendy usuwania w TaskTracker

Aby utrwalić wybór strategii, wyobraźmy sobie, że nasz TaskTracker ma trzy komendy: usuń po id, wyczyść ukończone i pokaż tylko aktywne (bez usuwania ich z bazy).

Poniżej małe funkcje, które można wywołać z menu/pętli obsługi komend (sama pętla nie jest tu wypisana, była wcześniej).

Usuwanie jednego zadania po id (strategia punktowa):

#include <iostream>
#include <vector>

void cmd_delete_by_id(std::vector<Task>& tasks, int id) {
    if (remove_task_by_id(tasks, id)) {
        std::cout << "Deleted task id=" << id << "\n";
    } else {
        std::cout << "No task with id=" << id << "\n";
    }
}

Masowe czyszczenie ukończonych (erase-remove):

#include <iostream>
#include <vector>

void cmd_clear_done(std::vector<Task>& tasks) {
    int removed = remove_done_tasks(tasks);
    std::cout << "Removed done tasks: " << removed << "\n";
}

Pokaż aktywne (rebuild przez copy_if):

#include <iostream>
#include <vector>

void cmd_show_active(const std::vector<Task>& tasks) {
    auto active = build_active_tasks(tasks);
    for (const auto& t : active) {
        std::cout << t.id << ": " << t.title << "\n";
    }
}

A jeśli chcesz „ładny wydruk” jako osobna lista linii (rebuild przez transform):

#include <iostream>
#include <vector>

void cmd_print_lines(const std::vector<Task>& tasks) {
    auto lines = build_task_lines(tasks);
    for (const auto& line : lines) {
        std::cout << line << "\n";
    }
}

Zauważ przyjemny efekt: każda komenda czyta się jako jedna myśl. W środku — wywołanie właściwej strategii. To jest cel dzisiejszego wykładu: nie „znać remove_if”, lecz umieć dobrać formę rozwiązania tak, by kod był spokojny.

7. Typowe błędy przy wyborze strategii usuwania

Błąd nr 1: używać punktowego erase w zadaniu masowym i dostać „ukryte kwadratowe piekło”.
Kiedy trzeba usunąć połowę elementów, a ty robisz erase wiele razy, vector znowu i znowu przesuwa ogon. Kod może wyglądać krótko i „logicznie”, ale będzie działać coraz gorzej wraz ze wzrostem danych. Jak leczyć: jeśli usuwasz dużo według warunku — prawie zawsze użyj erase-remove (remove_if + erase).

Błąd nr 2: sądzić, że remove_if „już usunął” elementy z vector.
Po remove_if rzeczywisty rezultat jest tylko w prefiksie [begin, new_end), a size() pozostaje ten sam. Jeśli zapomnisz erase(new_end, end), zobaczysz „ogon” i pomyślisz, że algorytm nie działa. Jak leczyć: pamiętać dwukrokowość — najpierw logiczne skompresowanie, potem fizyczne skrócenie.

Błąd nr 3: mylić „kogo usunąć” i „kogo zostawić” w predykacie remove_if.
W remove_if predykat zwraca true dla tych, którzy powinni odejść. Nowicjusze często piszą „warunek zostawić” i potem dziwią się, że usunięto dokładnie to, czego chcieli. Jak leczyć: wypowiadanie predykatu słowami: „return true jeśli element jest zły”.

Błąd nr 4: budować nowy vector przez copy_if, ale nie przygotować miejsca na zapis.
std::copy_if pisze do docelowego zakresu. Jeśli zrobiłeś std::vector<Task> dst; i przekazałeś dst.begin(), zapis idzie „donikąd”. Jak leczyć w ramach obecnego kursu: wcześniej zrobić dst(src.size()), potem dst.erase(out_end, dst.end()).

Błąd nr 5: mieszać mutację i odczyt tak, że logika staje się krucha.
Bardzo typowy „kombajn”: w jednej pętli drukujesz, usuwasz, liczysz statystyki i jeszcze gdzieś aktualizujesz indeksy. To trudno testować i łatwo zepsuć. Jak leczyć: rozdzielać zadania. Jeśli trzeba usunąć — użyj jednej z trzech strategii, a zbieranie statystyk/druk rób osobnym przebiegiem lub osobnymi funkcjami.