Видалення зі std::vector: erase()

1. erase() та інвалідація ітераторів і посилань

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

Уявімо список справ: ["купити молоко", "помити кота", "здати лабораторну"]. Якщо видалити елемент посередині, вектор має знову розмістити елементи підряд: ["купити молоко", "здати лабораторну"]. Для вас це виглядає цілком логічно, але для ітератора, який «дивився» на елемент «здати лабораторну», це вже зовсім інша історія: він міг стати недійсним або почати вказувати не туди.

Модель без «дір»: що фізично відбувається під час erase

Перш ніж писати код, корисно на кілька хвилин увімкнути «режим рентгену» й уявити, що таке vector усередині. У нього є буфер памʼяті, який може вмістити capacity() елементів, і фактична кількість елементів — size(). Видалення елемента посередині — це не просто «мінус один до size()», а ще й переміщення елементів, щоб заповнити порожнє місце.

Схематично це можна подати так:

До:
індекси:  0      1      2      3
дані:    [10]   [20]   [30]   [40]

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

Після:
індекси:  0      1      2
дані:    [10]   [30]   [40]

Елемент [30] переїхав на місце [20], [40] переїхав на місце [30]. Це важливо: на місці видаленого опиняється інший елемент. Через це будь-які привʼязки до елементів праворуч — ітератори й посилання — стають небезпечними: вони або дивляться не туди, або взагалі в нікуди.

erase(pos): видаляємо один елемент за ітератором

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

Видалити за індексом теж можна, але тоді ви спочатку перетворюєте індекс на ітератор, або доходите до потрібної позиції через ++, і лише потім викликаєте erase.

Мініприклад: видалимо другий елемент (20), не використовуючи арифметику ітераторів, а лише ++.

#include <iostream>
#include <vector>

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

    auto it = v.begin();
    ++it;            // тепер it вказує на 20
    v.erase(it);     // видаляємо 20

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

erase(it) не «зануляє» місце, а перебудовує послідовність. Після видалення наступний елемент (30) займає місце видаленого.

erase(first, last): видаляємо діапазон [first, last)

Іноді потрібно видалити не один елемент, а цілий фрагмент: наприклад, «видалити елементи з 2-го до 4-го». У vector це робиться через erase(first, last), і тут є найважливіше правило, з яким ви ще багато разів зустрінетеся в C++: діапазони задаються як [first, last), тобто ліву межу включаємо, праву — ні.

last — це позиція після останнього видалюваного елемента.

Видалимо з [1, 2, 3, 4, 5] числа 2, 3, 4, знову побудувавши ітератори через ++:

#include <iostream>
#include <vector>

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

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

    auto last = first;
    ++last;  // на 3
    ++last;  // на 4
    ++last;  // на 5 (тобто "після 4")

    v.erase(first, last); // видаляємо 2,3,4

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

Корисне формулювання для самоперевірки: last має вказувати на елемент після останнього видалюваного. У прикладі останній видалюваний елемент — 4, отже last має вказувати на 5.

Що повертає erase, і чому це рятує цикли

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

Мініприклад: видалимо 6 і продовжимо працювати з ітератором, який повернув erase.

#include <iostream>
#include <vector>

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

    auto it = v.begin();
    ++it;               // it на 6
    it = v.erase(it);   // видалили 6, it тепер на 7

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

Ключова звичка: після erase не довіряємо старому ітератору, а беремо той, який повернула функція.

Видалення в циклі: поганий і хороший варіант

Коли ви вперше пишете «видалити всі елементи, рівні X», рука сама просить написати щось на кшталт: «іду по вектору, якщо зустрів X — erase». І це саме той випадок, коли код може навіть «іноді працювати», а це особливо небезпечно.

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

#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); // після цього it уже небезпечний
        }
    }
}

Правильна ідея проста: якщо ми видалили поточний елемент, то наступну позицію нам уже повернув erase. А якщо не видалили — тоді спокійно робимо ++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);   // беремо повернену позицію
        } else {
            ++it;               // рухаємося далі самі
        }
    }

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

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

Інвалідація: що саме стає недійсним після erase

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

Для std::vector зручно памʼятати таку схему:

Про «переїзд» вектора ми говорили раніше, коли обговорювали capacity() і перевиділення памʼяті. Тут варто зафіксувати головне: якщо вектор змінив внутрішній буфер, то будь-яка привʼязка до елемента — ітератор, посилання чи вказівник — стає небезпечною.

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

Посилання на елемент: чому T& небезпечне під час зміни vector

Коли ви пишете int& ref = v[1];, ви створюєте посилання — друге імʼя для конкретного елемента вектора. На вигляд це майже як звичайна змінна, але є важлива відмінність: посилання не живе саме по собі, а вказує на памʼять, яка належить вектору. І якщо вектор перебудувався — через видалення або «переїзд» — посилання може стати недійсним.

Приклад із серії «виглядає нешкідливо, але насправді небезпечно»:

#include <vector>

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

    int& ref = v[1];        // ref посилається на "20"
    v.erase(v.begin());     // видалили 10, елементи зсунулися

    // ref тепер може посилатися не туди.
}

Тут важливо не намагатися вгадати, що станеться в кожному конкретному випадку: у навчальній моделі достатньо зрозуміти головне — після зміни структури вектора старі посилання й ітератори використовувати не можна.

Є й ще один життєвий сценарій: ви взяли посилання, потім зробили push_back, а vector вирішив переїхати в новий буфер, бо capacity() скінчилася. Тоді таке посилання майже напевно стане недійсним.

#include <vector>

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

    int& ref = v[1];   // "20"
    v.push_back(40);   // може статися перевиділення

    // ref може стати недійсним
}

Так, це неприємно. Зате тепер зрозуміло, чому в реальних проєктах часто радять не тримати посилання на елементи vector довше, ніж це справді потрібно.

Мінісписок завдань: видаляємо завдання за індексом

Зараз у нас ще немає класів і складної архітектури, тому зробимо навчальний «мінісписок завдань»: std::vector<std::string> tasks, де кожен рядок — це одне завдання. Додамо видалення за номером, тобто за індексом, але обережно: спочатку перевіримо межі, потім знайдемо ітератор і викличемо erase.

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

int main() {
    std::vector<std::string> tasks{"Купити молоко", "Помити кота", "Здати лабораторну"};

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

Тут заховані дві важливі звички. По-перше, ми перевіряємо idx < tasks.size(), тому що індекс надходить ззовні, тобто з введення, а отже, йому не можна довіряти. По-друге, ми не намагаємося видаляти за індексом напряму, а чесно перетворюємо індекс на ітератор, тому що erase працює з позиціями.

Якщо ви зараз подумали: «Ех, хочеться tasks.begin() + idx», то вітаю: ви вже намацали ідею ітераторів довільного доступу. Але в цій частині курсу ми тримаємося в межах того, що вже ввели: begin()/end() і ++.

2. Типові помилки під час видалення зі std::vector

Помилка № 1: використовувати ітератор після erase, ніби нічого не сталося.
erase змінює структуру вектора й робить поточну позицію «слизькою». Типовий симптом: програма іноді пропускає елементи, іноді падає, а іноді просто поводиться дивно. Вирішується це простою дисципліною: після it = v.erase(it) використовуємо саме повернений ітератор і не робимо ++it автоматично, «за звичкою».

Помилка № 2: переплутати діапазон [first, last) й очікувати, що last теж видалиться.
Це класика: ви хочете видалити «з 2 по 4 включно», будуєте last на елемент 4, а потім дивуєтеся, що 4 залишився. Правильна модель тут не про «включно», а про «останній не включаємо»: last має вказувати на позицію після останнього видалюваного елемента.

Помилка № 3: тримати посилання (T&) на елемент, а потім змінювати vector.
Посилання виглядає як зручна змінна, але воно привʼязане до внутрішньої памʼяті контейнера. Після erase, push_back (якщо було перевиділення) або навіть reserve (якщо стався «переїзд») таке посилання може стати недійсним. Якщо вам потрібно просто запамʼятати значення, беріть копію, наприклад: int x = v[i];. Якщо ж потрібно памʼятати позицію, майте на увазі: під час модифікацій вона може стати недійсною.

Помилка № 4: намагатися видаляти в циклі for (...; ++it) і всередині робити erase(it).
Тут ламається логіка кроку: erase уже перебудував послідовність, а ви ще й збільшуєте ітератор за старою схемою. У найкращому разі ви пропустите перевірку для елемента, який зсунувся на видалену позицію; у найгіршому — отримаєте звернення до недійсної позиції. Надійна схема така: цикл без автоматичного ++it, де крок робиться або ++it, або it = erase(it).

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