Чому erase у циклі часто призводить до помилок

1. Вступ

Почнімо з чесного визнання: видаляти елементи «на ходу» хочеться ледь не завжди. У вас є список задач, список чисел, список рядків — і ви хочете «викинути сміття»: порожні рядки, виконані задачі, відʼємні значення — будь-що. Інтуїтивно здається, що все це — справа одного рядка: «якщо не підходить — erase». А якщо ви вже вмієте користуватися for і if, то що тут може піти не так?

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

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

2. Як працює vector::erase

Перш ніж розбирати антипатерни, спокійно зʼясуймо, що саме робить erase. Не на рівні «що там усередині реалізації», а на рівні логіки: один елемент зникає, усі елементи праворуч зсуваються вліво на одну позицію, розмір зменшується на 1, а ітератори й посилання на елементи, яких це стосується, стають недійсними.

Розгляньмо простий приклад. Нехай у нас є числа, щоб не відволікатися:

Видаляємо елемент за індексом 1 (тобто 20). Після erase:

Тобто те, що було 30, тепер стоїть там, де раніше було 20. Тому, якщо цикл «збирався» після видалення зробити ++it або i++, він майже гарантовано перестрибне через 30, бо 30 уже переїхав на місце видаленого елемента.

Ось проста схема (не про памʼять, а про сенс):

flowchart LR
    A["Ідемо по елементах"] --> B{"Умова видалити?"}
    B -->|ні| C["Зробити крок далі"]
    B -->|так| D["erase: прибрати елемент"]
    D --> E["Зсув хвоста вліво"]
    E --> F["Розмір зменшився"]
    F --> A

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

3. Міні-база TaskBook для прикладів

Щоб приклади не перетворилися на набір випадкових vector<int>, задамо мінімальну модель задачі. Так, це невеликий фрагмент «застосунку», але нам важливо, щоб далі в прикладах ми видаляли не абстрактні числа, а щось ближче до реальної програми.

#include <string>

struct Task {
    int id{};
    std::string title;
    bool done{};
};

І ще одна невелика утиліта, щоб швидко бачити результат. У реальному проєкті ви, найімовірніше, винесли б це в окрему функцію, але поки залишимо все компактним:

#include <iostream>
#include <vector>

void print_ids(const std::vector<Task>& tasks) {
    for (const auto& t : tasks) std::cout << t.id << ' ';
    std::cout << '\n';
}

Далі ми розглядатимемо різні способи видаляти виконані задачі й дивитимемося, де саме людська інтуїція та поведінка vector починають розходитися.

4. Антипатерни: erase під час обходу

erase усередині range-for

Range-for виглядає як подарунок долі: мінімум коду, максимум читабельності. Саме тому це найпопулярніший кандидат на «а давайте видаляти прямо тут». Логіка новачка проста: раз я отримав Task& t, то зараз перевірю t.done і видалю елемент. На жаль, range-for всередині теж працює через ітератори, і після зміни контейнера ви вже не контролюєте, що з ними відбувається.

Поганий приклад (зверніть увагу: я не залишаю активним небезпечний рядок, бо він справді може призвести до непередбачуваних наслідків):

#include <vector>

void remove_done_bad(std::vector<Task>& tasks) {
    for (Task& t : tasks) {
        if (t.done) {
            // ПОГАНО: range-for приховує ітератори,
            // а erase їх інвалідовує.
            // tasks.erase(...);
        }
    }
}

Чому сама ідея тут погана? Тому що range-for думає: «я зараз послідовно рухатимуся від begin до end». А ви посеред маршруту вириваєте шмат дороги й перекладаєте асфальт. Ітератор, який «обслуговує» цикл, може стати недійсним. Навіть якщо «у вас начебто працює», це саме той випадок, коли щось «працює до першого релізу».

Правильний висновок не в тому, що range-for поганий. Він чудовий, коли ви не змінюєте контейнер, а лише читаєте елементи або змінюєте їх на місці (наприклад, виправляєте поле done, замінюєте рядок тощо). Але видалення елементів — це вже зміна структури контейнера, і тут range-for частіше заважає, ніж допомагає.

for (it ... ++it) + erase(it) без перепризначення

Цей варіант виглядає «розумнішим», бо ми явно використовуємо ітератори. Новачок міркує приблизно так: «йду ітератором, якщо елемент поганий — видаляю». І навіть знає, що erase існує. Але тут не враховано одразу дві проблеми: erase робить поточний ітератор недійсним, а for у заголовку все одно виконує ++it.

Поганий приклад (небезпечний рядок знову закоментовано, бо це класична пастка):

#include <vector>

void remove_done_bad2(std::vector<Task>& tasks) {
    for (auto it = tasks.begin(); it != tasks.end(); ++it) {
        if (it->done) {
            // ПОГАНО: erase інвалідовує it,
            // а потім цикл зробить ++it по "зламаному" it.
            // tasks.erase(it);
        }
    }
}

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

Робоча стратегія тут одна: якщо ви видаляєте, то зобовʼязані взяти новий ітератор, який повернув erase, і не робити додаткового кроку. Зазвичай це виглядає як «цикл без ++it у заголовку». Але сам патерн ми акуратно доведемо до гарного вигляду в одній із наступних лекцій; сьогодні нам важливо зрозуміти, чому «наївний» варіант так часто ламається.

Індексний цикл і erase(begin() + i)

Якщо ітератори здаються складними, наступна ідея звучить дуже по-людськи: «я ж умію працювати з індексами, vector[i], отже зроблю звичайний for по i і видалю tasks.begin() + i». І це знову виглядає логічно… але лише до першого реального видалення, після якого індекси елементів змінюються.

Ось типовий невдалий варіант:

#include <vector>

void remove_done_bad3(std::vector<Task>& tasks) {
    for (size_t i = 0; i < tasks.size(); ++i) {
        if (tasks[i].done) {
            tasks.erase(tasks.begin() + static_cast<long long>(i));
        }
    }
}

Симптоми такого коду зазвичай такі: «чомусь видалено не всі done», «іноді лишається одна виконана задача», «а якщо їх дві підряд — одна все одно залишається». І причина знову та сама: після erase наступний елемент переїжджає на індекс i, а ви робите i++ і пропускаєте його.

Є й друга, менш очевидна проблема: кожен erase посередині vector зсуває хвіст. Тобто що більше видалень, то більше зсувів. У підсумку простий фільтр може стати помітно повільним на великих обсягах даних.

Іноді люди намагаються «лікувати» це проходом із кінця на початок: якщо видаляти справа наліво, зсуви не ламають уже оброблені індекси. Але там на вас чекає окрема пастка зі size_t і скочуванням у нескінченний цикл (бо size_t — беззнаковий тип, і «мінус один» перетворюється на величезне число). Ми не будемо зараз робити з цього окремий урок, але важливо хоча б знати: «зворотний цикл із size_t» — один із найпопулярніших способів випадково написати вічний двигун.

Спроба «зафіксувати» end() або зберегти посилання/вказівник

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

Приклад із «збережу end()»:

#include <vector>

void remove_done_bad4(std::vector<Task>& tasks) {
    auto last = tasks.end(); // ПОГАНА ідея: end() може стати невалідним
    for (auto it = tasks.begin(); it != last; ++it) {
        if (it->done) {
            tasks.erase(it);  // тут last теж "під питанням"
            break;
        }
    }
}

Так, може здаватися, що end() — це «просто межа». Але у vector після модифікації контейнера межа змінюється, і збережений last може перестати бути коректною межею. Це один із тих випадків, коли код «інколи працює» лише тому, що випадково не натрапив на невдалу комбінацію даних.

Приклад із «збережу посилання» теж звучить привабливо, але на практиці це небезпечно:

#include <vector>

void bad_ref(std::vector<Task>& tasks) {
    Task& ref = tasks[0];
    tasks.erase(tasks.begin()); // ref тепер може посилатися "не туди"
    // ref.id; // небезпечно використовувати
}

Посилання та вказівники на елементи vector привʼязані до конкретних позицій у масиві. А erase ці позиції змінює: зсуває елементи, знищує видалений, інколи переміщує обʼєкти. Тому «посилання на елемент» і «видалення елемента» — це майже завжди конфлікт інтересів.

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

Багато одиночних erase і раптове O(N²)

Є особливий вид болю: коли код логічно «майже правильний», інколи навіть коректний, але раптом починає гальмувати. Типовий сценарій: у вас 100000 задач, і ви хочете видалити всі виконані. Ви пишете цикл і робите erase щоразу, коли бачите done. На малих даних усе літає. На великих — раптом виникає запитання: «чому так довго?».

Інтуїтивна причина проста: erase посередині vector зсуває хвіст. Якщо ви видаляєте багато елементів, то робите багато таких зсувів. У підсумку це схоже на ситуацію, коли ви намагаєтеся прибрати людей із черги й щоразу пересуваєте всю чергу на один крок ближче до каси.

Ось ідея, яка погана з погляду витрат, у формі, яку легко зустріти:

#include <vector>

void remove_done_slow(std::vector<Task>& tasks) {
    for (auto it = tasks.begin(); it != tasks.end(); ++it) {
        if (it->done) {
            tasks.erase(it); // навіть якщо “лагодити” ітератор, зсуви все одно дорогі
            break;
        }
    }
}

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

5. Шпаргалка: як думати перед видаленням

Коли ви наступного разу захочете видалити елементи зі std::vector, спробуйте зупинитися на дві секунди й поставити собі одне запитання: «я видаляю один елемент чи багато?». Якщо ви видаляєте багато елементів за умовою, майже завжди краще не «висмикувати по одному в циклі», а обрати підхід, який робить мінімум зсувів і не ламає обхід. Якщо ж ви видаляєте точково під час обходу, вам потрібен такий патерн циклу, у якому крок ітератора контролюється вручну, а після видалення ви продовжуєте з ітератора, який повернув erase.

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

Сенс сьогоднішньої лекції не в тому, щоб ви запамʼятали «правильний магічний рядок», а в тому, щоб навчилися впізнавати антипатерни в обличчя. Коли ви їх упізнаєте, то автоматично перестанете писати крихкий код «на удачу» й почнете писати код «за контрактом контейнера».

6. Типові помилки

Помилка № 1: видалення зі std::vector усередині range-for для цього самого vector.
Range-for виглядає безпечно, але він приховує ітератори. Коли ви робите erase, то змінюєте контейнер і можете зробити недійсним ітератор, яким range-for керує зсередини. У найкращому разі ви отримаєте пропуски елементів, у найгіршому — невизначену поведінку.

Помилка № 2: erase(it) усередині for (...; ++it) без перепризначення ітератора.
Тут одразу дві проблеми: erase робить it недійсним, а заголовок циклу все одно намагається виконати ++it. Навіть якщо програма «не впала», вона часто пропускає елементи, особливо коли елементи, які треба видалити, стоять підряд.

Помилка № 3: індексний цикл for (i...) + erase(begin()+i) і наївне i++.
Після видалення елемент праворуч зсувається вліво на поточну позицію i, а ви збільшуєте i і перестрибуєте через нього. У результаті видаляється не все, що мало б видалитися. Додатково ви отримуєте багато зсувів хвоста, і на великих даних код починає помітно гальмувати.

Помилка № 4: спроба «зафіксувати» межі обходу (end()) або зберегти посилання/вказівники на елементи, а потім змінювати контейнер.
У vector будь-яка зміна, повʼязана зі зсувом елементів, робить збережені привʼязки ненадійними. end() після видалення — уже не той end(), а посилання на елемент після erase може почати вказувати на інший обʼєкт або взагалі стати небезпечним для використання.

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