Інвалідація ітераторів у std::vector

1. Привʼязки до елементів: ітератор, посилання та вказівник

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

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

Спочатку домовімося про терміни. Коли ми кажемо «привʼязка до елемента», то маємо на увазі будь-що, що вказує на конкретний елемент вектора: ітератор, посилання (T&) або вказівник (T*). Зовні вони виглядають по-різному, але з погляду ризику мають спільний сенс: ви запамʼятали «ось цей елемент», а потім контейнер змінився.

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

Ітератор — «узагальнений вказівник» контейнера

Ітератор можна пересувати (++it) і розіменовувати (*it). У попередніх лекціях ми вже так робили, але зараз важливо відчути: ітератор — не «індекс», а обʼєкт, який вказує на позицію в діапазоні [begin, end).

#include <iostream>
#include <vector>

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

    auto it = v.begin();
    ++it; // тепер it вказує на 20

    std::cout << *it << '\n'; // 20
}

Посилання T& — «друге імʼя» конкретного елемента

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

#include <iostream>
#include <vector>

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

    int& ref = v[1];
    std::cout << ref << '\n'; // 2
}

Вказівник T* — адреса елемента в памʼяті

Вказівник найчастіше отримують так: &v[i]. Це пряма адреса елемента. Саме тому вказівник особливо «чутливий» до переміщення даних.

#include <iostream>
#include <vector>

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

    int* p = &v[0];
    std::cout << *p << '\n'; // 5
}

2. Чому std::vector інвалідує привʼязки

Зараз буде важлива аналогія, але не зловживатимемо нею. std::vector можна уявити як книжкову полицю, де книжки стоять впритул, без проміжків. Це зручно: можна миттєво взяти «книжку № 37» (доступ за індексом). Але якщо ви витягли одну книжку із середини, усі книжки праворуч мають зсунутися, щоб закрити порожнечу. А якщо полиця заповнилася, бібліотека може видати вам нову, більшу полицю — і всі книжки переїдуть на іншу адресу.

Саме через таке «щільне розміщення» vector часто інвалідує привʼязки: під час видалення відбувається зсув, а під час зростання (наприклад, через push_back) можливий «переїзд» усього масиву елементів.

Це можна візуалізувати так:

flowchart LR
    A["v: [A][B][C][D]"] -->|"erase(B)"| B["v: [A][C][D]"]
    B -->|"push_back(E) і місця бракує"| C["переїзд у нову памʼять: [A][C][D][E]"]

У реальному житті це виглядає так: наче все лишилося тим самим, але старі вказівники, посилання та ітератори вже могли перетворитися на сміття.

3. Що саме ламається під час модифікації вектора

Тут є важливий момент, який часто плутають навіть уважні новачки: проблеми бувають двох типів, і відчуваються вони по-різному.

«Невалідний» і «вказує вже не на те»

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

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

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

Операції, які найчастіше ламають привʼязки

Зараз ми акуратно зведемо ці спостереження в зрозумілу картину. Важливо: ми не вивчаємо внутрішню будову vector на рівні стандарту й алокаторів; нам потрібна прикладна модель: «що тут небезпечно».

Найчастіші «руйнівники» привʼязок — це erase(...) і операції зростання на кшталт push_back(...). Навіть у розмовах про стандартну бібліотеку окремо обговорюють те, що операції на кшталт push_back мають інвалідувати end-ітератор. Це добрий сигнал: тема не суто навчальна, а цілком практична.

Нижче — корисна таблиця «як про це думати», без претензії на юридичну точність стандарту, зате з хорошою практичною цінністю.

erase(pos)

erase(first, last)

push_back(x)

insert(...)

clear()

Головна мета цієї таблиці — не змусити вас запамʼятати все раз і назавжди, а виробити звичку: щойно бачите модифікацію vector, одразу подумки запитуйте себе: «А чи не тримаю я десь ітератор, посилання або вказівник на його елементи?»

4. Мінідемонстрації: як ламається код і як його виправити

Зараз буде серія коротких прикладів, кожен на 5–10 рядків. Ми навмисно підійдемо до краю урвища, але не стрибатимемо: небезпечні рядки закоментуємо. У реальному житті такі рядки інколи не закоментовані, і тоді у вас зʼявляється чудова нагода познайомитися з непередбачуваністю.

Вказівник на елемент + push_back: можливий переїзд

Підкреслю: переїзд можливий, а отже, покладатися на стару адресу не можна.

#include <vector>

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

    int* p = &v[0];
    v.push_back(4); // можливий переїзд

    // Небезпечно: p може стати невалідним.
    // int x = *p;
    // (void)x;
}

Ітератор + erase: старий ітератор використовувати не можна

Це базова причина, через яку «erase у циклі» так часто ламає обхід.

#include <vector>

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

    auto it = v.begin();
    ++it; // 20

    v.erase(it);

    // Небезпечно: it більше не можна розіменовувати чи зсувати.
    // ++it;
}

Правильна опора: erase повертає ітератор

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

#include <iostream>
#include <vector>

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

    auto it = v.begin();
    ++it; // 20

    it = v.erase(it);          // видалили 20, it тепер вказує на 30
    std::cout << *it << '\n';  // 30
}

Це не просто зручно. Саме так ви продовжуєте роботу без використання мертвого ітератора.

5. Приклад: мініменеджер задач і видалення за id

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

Спочатку — модель задачі: мінімум деталей, без класів і без складної архітектури.

#include <string>

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

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

#include <algorithm>
#include <vector>

bool erase_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;
}

Зверніть увагу на підхід: функція повертає bool, щоб код, який її викликає, розумів, чи знайшлася задача. У винятки ми поки не заглиблюємося — за курсом це буде пізніше; зараз нам достатньо простого й зрозумілого контракту.

Хибний підхід: «запамʼятаю вказівник на вибрану задачу»

Саме так і хочеться зробити, особливо якщо ви думаєте: «Ну це ж швидше». А потім ви додаєте нову задачу — і «швидше» перетворюється на «чому все падає?».

#include <vector>

void add_task(std::vector<Task>& tasks, Task t) {
    tasks.push_back(t);
}

int main() {
    std::vector<Task> tasks{{1, "Read C++", false}};

    Task* selected = &tasks[0];
    add_task(tasks, Task{2, "Write C++", false}); // можливий переїзд

    // Небезпечно: selected може стати висячим вказівником.
    // selected->done = true;
}

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

Якщо вам потрібно «памʼятати вибрану задачу», запамʼятовуйте id, а не Task*. Тоді під час наступної дії ви знову знайдете задачу за id і отримаєте актуальний ітератор.

#include <algorithm>
#include <vector>

bool mark_done_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;

    it->done = true; // безпечно: працюємо з актуальним ітератором
    return true;
}

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

6. Практична модель безпеки

Зараз сформулюємо модель, яку зручно тримати в голові під час читання й написання коду. Сприймайте це не як список заборон, а як маленький внутрішній компас. Щойно ви змінюєте std::vector, цей компас має підказувати: «Обережно, старі привʼязки можуть бути зіпсовані».

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

Якщо вам потрібно зберігати «посилання» на вибраний елемент, не тримайте T& або T* на елемент vector між операціями, що змінюють контейнер. Це майже завжди пастка. У прикладних задачах зазвичай краще зберігати id (або індекс, якщо ви точно розумієте, як він змінюватиметься) і заново знаходити елемент саме тоді, коли він справді потрібен.

7. Типові помилки під час роботи з інвалідацією в std::vector

Помилка № 1: зберігати вказівник або посилання на елемент вектора, а потім робити push_back.
Такий код часто «працює на малих даних», бо vector може не переїжджати одразу. Але щойно переїзд стався, ваш вказівник перетворюється на висячий, і будь-яке розіменування стає лотереєю. Рятує проста звичка: зберігати не адресу елемента, а його ідентифікатор, а перед дією заново знаходити елемент через find_if.

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

Помилка № 3: видаляти елементи з vector усередині range-for за цим самим vector.
Range-for під капотом використовує ітератори діапазону. Якщо ви всередині циклу змінюєте контейнер, то ризикуєте зламати ці ітератори, а отже — і сам цикл. У результаті зʼявляються «пропуски елементів», дивні падіння та відчуття, що C++ вас не любить. Для видалення використовуйте явний цикл з ітератором, де ви самі контролюєте крок.

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

Помилка № 5: розіменовувати end().
end() — це «позиція після останнього елемента». Її можна порівнювати (it != end), але не можна розіменовувати. Інколи ця помилка проявляється саме після видалення, коли ви очікували, що ітератор «точно на елемент», а він раптом став end(). Тому перевірка it != v.end() — це не бюрократія, а страховка від дуже неприємного падіння.