Три стратегії видалення в std::vector

1. Вступ

Коли людина каже «видаліть елемент», легко уявити щось просте: взяли — і видалили. Але std::vector — не магічна коробка, де елементи висять у повітрі. Це щільний ряд комірок памʼяті. Тож видалення майже завжди означає «посунути хвіст», а отже, впливає на ітератори, індекси й навіть на читабельність коду. Тому тут не одна задача, а щонайменше три різні сценарії.

Перший сценарій — точковий: «видалити один конкретний елемент» — наприклад, задачу за id. Другий — масовий: «видалити всі елементи, які підпадають під умову» — наприклад, усі виконані задачі. Третій — функціональний за духом: «побудувати новий список за правилами, не змінюючи початкового» — наприклад, зробити список активних задач або список рядків для друку. Для кожного сценарію доречний свій інструмент. Саме це заощаджує вам години налагодження й робить код передбачуваним.

Щоб це не залишалося абстракцією, продовжимо наш міні-проєкт: консольний трекер задач. Зберігатимемо задачі у std::vector; кожна з них матиме id, title і статус.

#include <string>

enum class TaskStatus { Todo, Done };

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

2. Стратегія № 1: точкове видалення через erase

Якщо вам потрібно видалити рівно один елемент, найчастіше найзрозуміліший варіант — знайти його й стерти. Звучить тривіально, але тут важлива дисципліна: ми видаляємо не за «індексом, який десь запамʼятали», а за ітератором, який щойно отримали. Це зменшує ймовірність випадково стерти «не те» після інших операцій зі списком.

Почнімо з функції пошуку. std::find_if ми вже знаємо, лямбди нам теж знайомі, тож читається все цілком по-людськи.

#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;
}

Зверніть увагу на важливу дрібницю: ми обовʼязково перевіряємо, чи it не дорівнює end(). Це не «перестраховка», а нормальний контракт STL: end() не можна розіменовувати, через нього не можна стирати, та й узагалі це межа, а не елемент.

Іноді новачкам хочеться зробити так: «ну я ж знаю індекс, давайте erase(begin() + idx)». Це справді працює, але лише доти, доки індекс не починає обчислюватися «за старими даними». У проєкті це часто виглядає так: ви знайшли індекс, потім десь дорогою видалили інший елемент, а тоді стираєте за старим індексом. У підсумку маємо видалення «із сюжетом»: наче просили прибрати задачу "Купити молоко", а зникла "Сплатити оренду". І, що цікаво, компілятор не заперечить.

Якщо ви все ж працюєте з індексом, то принаймні перетворюйте його на ітератор безпосередньо перед видаленням і тримайте все це в межах однієї функції, щоб не зʼявлявся «індекс-мандрівник».

#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;
}

Тут ми свідомо перевіряємо межі. І так, приведення типу виглядає трохи «канцелярськи». Це якраз натяк на те, що варіант із find_if часто простіший і безпечніший.

Ще один важливий момент про «вартість за інтуїцією». Операція erase(it) у vector майже завжди означає, що елементи праворуч від видаленого зсунуться на одну позицію вліво. Тобто це не O(1) «клацання», а операція зі зсувом хвоста. Але якщо ви робите це один раз, усе гаразд. Проблеми починаються тоді, коли ви повторюєте це сотні разів у циклі. Тут і переходимо до наступного розділу.

3. Стратегія № 2: масове видалення через erase-remove

Коли потрібно видалити всі елементи за умовою, «наївний» шлях виглядає так: пройтися циклом і щоразу викликати erase, коли умова істинна. Іноді це ще й намагаються писати в range-for, а це вже зовсім невдала ідея. І навіть якщо ви правильно напишете цикл з ітератором, залишиться друга проблема: ви виконуватимете багато зсувів хвоста. Що більше видалень, то більше пересування елементів, а отже, то ближче ви до прихованого O(N²) на практиці.

Ідіома erase-remove розвʼязує це акуратно: спочатку ми одним проходом групуємо «хороші» елементи на початку, а потім одним erase відрізаємо хвіст. Тобто замість десятків чи сотень зсувів ми робимо одне «масове зміщення» — насправді це переміщення або присвоювання елементів — і одне реальне зменшення розміру.

Уявімо задачу: видалити всі задачі зі статусом 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;
}

Зауважте важливу «філософію» предиката: remove_if запитує не «кого залишити», а «кого видалити». Якщо лямбда повертає true, елемент вважається «поганим» і буде витіснений у хвіст.

Дуже корисно тримати в голові таку картинку:

До remove_if:
[ A ][ B ][ C ][ D ][ E ][ F ]

Після remove_if (логічно):
[ A ][ C ][ E ][ ? ][ ? ][ ? ]
                ^ new_end

Після erase(new_end, end):
[ A ][ C ][ E ]

Знаки питання — це не сміття в сенсі «зламана памʼять», але це вже точно не «ваші актуальні дані». Там можуть бути старі значення, дублікати — що завгодно. Читати їх як результат не можна.

Ще одна побутова тонкість: після remove_if розмір tasks.size() не змінюється. Якщо ви забули другий крок — erase, — то під час друку можете побачити «дивні хвости». І студент зазвичай каже: «у мене remove_if не працює». Насправді все працює, просто ви зупинилися на півдорозі.

Якщо хочете надрукувати результат одразу після remove_if, то виводьте лише діапазон [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';
    }
}

Так, це «відлагоджувальний» стиль: ми тимчасово використовуємо знання про new_end, щоб переконатися, що логіка працює.

4. Стратегія № 3: rebuild — зібрати новий результат

Іноді найбільша проблема видалення — не швидкість і не інвалідація, а читабельність. Особливо коли навколо видалення зʼявляються додаткові правила: «видали виконані, але тільки якщо вони старші…», «видали порожні назви», «видали дублікати…». Ви починаєте змінювати vector, паралельно стежите за ітератором і в якийсь момент розумієте, що код має вигляд «обережно, скло» — і це ще в хороший день.

Підхід rebuild означає, що ми не змінюємо початковий контейнер, а будуємо новий. Це схоже на ситуацію, коли ви переписуєте охайний конспект: старий аркуш не рвете, а просто переносите потрібне.

Фільтрація: copy_if і активні задачі

Припустімо, нам потрібен список лише активних задач зі статусом Todo, а початковий список ми хочемо зберегти без змін — наприклад, для історії.

#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;
}

Так, тут теж є «двокроковість», схожа на erase-remove, але сенс інший. Ми не «видаляємо зі старого», а «збираємо нове». А другий крок — erase(out_end, end) — лише вкорочує active, бо ми заздалегідь виділили максимум місця.

Новачки часто хочуть написати std::vector<Task> active;, а потім — copy_if(..., active.begin(), ...). Але begin() порожнього вектора не вказує на місце, куди можна писати. Тому ми або заздалегідь задаємо потрібний розмір, або використовуємо техніки запису через inserter-и. Але це буде окрема тема в іншому місці курсу, тож зараз не відволікаємося.

Перетворення: transform і рядки для друку

std::transform — це не про видалення, а про перетворення одного набору даних на інший. Але в нашому «виборі стратегії» він стоїть поруч із rebuild, бо дуже часто реальна задача звучить не «видали», а «зроби подання».

Наприклад, хочемо отримати список рядків для друку задач у форматі "[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;
}

Тут немає зменшення розміру, бо transform працює за принципом «один до одного». Це чисте перетворення: скільки задач було, стільки рядків і стало.

Іноді дуже зручно поєднати фільтрацію й перетворення у два кроки: спочатку build_active_tasks, потім build_task_lines. Зазвичай це читається краще, ніж «один величезний цикл на 40 рядків з if-ами».

5. Як обрати стратегію: читабельність і «вартість за інтуїцією»

Коли ви знаєте три стратегії, хочеться запитати: «а яка з них правильна?» Відповідь трохи дратує, але вона чесна: правильна — та, яка відповідає задачі й робить код простішим, а не хитрішим. Ми не пишемо код заради олімпіади з трюків з ітераторами. Ми пишемо код, який за тиждень прочитає людина — можливо, ви самі, але вже втомлені.

Нижче — таблиця, яка зазвичай рятує від вагань у стилі «а раптом треба erase-remove завжди?»:

Корисно також мати в голові просту блок-схему вибору. Вона не замінить мислення, але іноді виручає в момент «я вже заплутався».

flowchart TD
    A[Потрібно «видалити»] --> B{Видаляємо рівно 1 елемент?}
    B -- Так --> C["find_if + erase(it)"]
    B -- Ні --> D{"Потрібно змінювати початковий vector?"}
    D -- Так --> E["remove_if + erase(new_end, end)"]
    D -- Ні --> F[rebuild: copy_if / transform]

Тепер кілька слів про «складність за інтуїцією». Якщо ви видаляєте елементи по одному багато разів, vector щоразу рухатиме хвіст. Це схоже на ситуацію, коли ви намагаєтеся витягти з середини книжкової полиці кожну третю книжку, але після кожного витягування акуратно зсуваєте решту, щоб не залишалося дірки. Можна, але це довго й виснажливо.

Тому «багато одиничних erase» — це тривожний сигнал у коді. Іноді він виправданий — наприклад, коли ви видаляєте кілька елементів за користувацькими командами, — але якщо потрібно масово очистити контейнер, ідіома erase-remove зазвичай виграє і за швидкістю, і за виразністю.

6. Міні-проєкт: команди видалення в TaskTracker

Щоб закріпити вибір стратегії, уявімо: у нашому TaskTracker є три команди — видалити за id, очистити виконані та показати лише активні, не видаляючи їх з основного списку.

Нижче — невеликі функції, які можна викликати з вашого меню або циклу обробки команд. Сам цикл ми тут не розписуємо: він у вас уже був у попередні дні.

Видалення однієї задачі за id (точкова стратегія):

#include <iostream>
#include <vector>

void cmd_delete_by_id(std::vector<Task>& tasks, int id) {
    if (remove_task_by_id(tasks, id)) {
        std::cout << "Видалено задачу id=" << id << "\n";
    } else {
        std::cout << "Задачу з id=" << id << " не знайдено\n";
    }
}

Масове очищення виконаних задач (erase-remove):

#include <iostream>
#include <vector>

void cmd_clear_done(std::vector<Task>& tasks) {
    int removed = remove_done_tasks(tasks);
    std::cout << "Видалено виконаних задач: " << removed << "\n";
}

Показати активні задачі (rebuild через 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";
    }
}

І, якщо хочеться мати «гарний вивід» окремим списком рядків (rebuild через 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";
    }
}

Зверніть увагу на приємний ефект: кожна команда читається як одна завершена думка. Усередині — виклик правильної стратегії. У цьому й полягає мета сьогоднішньої лекції: не просто «знати remove_if», а вміти обирати форму розвʼязання так, щоб код залишався спокійним і зрозумілим.

7. Типові помилки під час вибору стратегії видалення

Помилка № 1: використовувати точковий erase у масовій задачі й отримати «приховане квадратичне пекло».
Коли потрібно видалити половину елементів, а ви багато разів викликаєте erase, vector знову й знову зсуває хвіст. Код може виглядати коротким і «логічним», але працюватиме дедалі гірше зі зростанням обсягу даних. Як це виправити: якщо видаляєте багато елементів за умовою, то майже завжди потрібен erase-remove (remove_if + erase).

Помилка № 2: вважати, що remove_if «уже видалив» елементи зі vector.
Після remove_if реальний результат є лише в префіксі [begin, new_end), а size() залишається попереднім. Якщо забути про erase(new_end, end), ви побачите «хвіст» і вирішите, що алгоритм зламаний. Як це виправити: памʼятати про двокроковість — спочатку логічно стиснули, потім фізично вкоротили.

Помилка № 3: плутати «кого видалити» і «кого залишити» в предикаті remove_if.
У remove_if предикат повертає true для тих, хто має піти. Новачки часто пишуть «умову залишити», а потім дивуються, що видалилося саме те, що було потрібно. Як це виправити: проговорювати предикат словами — «return true, якщо елемент поганий».

Помилка № 4: будувати новий vector через copy_if, але не підготувати місце для запису.
std::copy_if пише у вихідний діапазон. Якщо ви створили std::vector<Task> dst; і передали dst.begin(), запис піде «в нікуди». Як це виправити в межах поточних тем курсу: заздалегідь створювати dst(src.size()), а потім викликати dst.erase(out_end, dst.end()).

Помилка № 5: змішувати зміну даних і читання так, що логіка стає крихкою.
Дуже типовий «комбайн»: в одному циклі ви друкуєте, видаляєте, рахуєте статистику і ще десь оновлюєте індекси. Це важко тестувати й легко зламати. Як це виправити: розділяти задачі. Якщо потрібно саме видалити, використовуйте одну з трьох стратегій, а збирання статистики чи друк виконуйте окремим проходом або через окремі функції.