Безпечне видалення під час обходу колекцій

1. Чому видалення під час обходу часто ламає програму

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

Головна причина, чому видалення під час обходу небезпечне, у тому, що механізм for (через ітератор) очікує: колекція не змінюватиметься «в обхід правил». Колекції Kotlin/JVM часто вміють виявляти такі втручання й відповідати винятком ConcurrentModificationException. Іноді винятку немає, але з’являється логічна помилка: ви видаляєте елемент, індекси зсуваються, і наступний елемент «прослизає повз перевірку».

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

Заборонений патерн: remove(...) усередині for (x in list)

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

fun main() {
    val items = mutableListOf("keep", "remove", "keep")

    for (x in items) {
        if (x == "remove") {
            items.remove(x) // небезпечно
        }
    }

    println(items)
}

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

Важливо вловити думку: for (x in items) використовує ітератор «під капотом», а items.remove(x) змінює колекцію безпосередньо. Це як їхати за навігатором, а комусь паралельно — у реальному часі — перекладати дороги.

Заборонений патерн: видалення за індексами зліва направо

Друга пастка частіше трапляється в тих, хто вже зрозумів: «у for (x in list) видаляти не можна». Далі з’являється ідея: «гаразд, обходитиму за індексами — я ж усе контролюю!». Контроль справді з’являється, але разом із ним з’являється й нова проблема: видалення зсуває елементи вліво, а ваш індекс продовжує зростати вправо.

Подивімося на приклад, де потрібно видалити всі "remove":

fun main() {
    val items = mutableListOf("keep", "remove", "remove", "keep")

    for (i in 0..items.lastIndex) {
        if (items[i] == "remove") {
            items.removeAt(i) // небезпечно під час руху зліва направо
        }
    }

    println(items)
}

Навіть якщо цей код не впаде через зміну lastIndex (а він легко може впасти, якщо вийти за межі), є тонший ефект. Коли ви видаляєте items[1], колишній items[2] зсувається на позицію 1. А цикл уже готується перейти до i = 2, тож цей «пересунутий» елемент ви просто не перевірите. Підсумок — частина елементів не видалиться, і ви отримаєте баг без винятку. Найулюбленіший тип багів: «програма не падає, але бреше».

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

2. Стратегія: видалення через MutableIterator.remove()

Зараз буде момент, коли колекції раптом «стають добрими». У Kotlin є спеціальний тип ітератора для mutable-колекцій — MutableIterator. Він розширює звичайний Iterator і додає метод remove(), який коректно видаляє «поточний» елемент. Тобто так, щоб це було узгоджено з процесом обходу.

Ключова ідея проста: якщо обхід керується ітератором, то ітератор і має видаляти.

Ось безпечний варіант видалення під час обходу списку:

fun main() {
    val items = mutableListOf("a", "remove", "b")
    val it = items.iterator()

    while (it.hasNext()) {
        val x = it.next()
        if (x == "remove") {
            it.remove()
        }
    }

    println(items) // [a, b]
}

Зверніть увагу на «ритуал»: спочатку ми викликаємо next(). Так ітератор «вказує» на поточний елемент. І лише після цього можна викликати remove(). Саме тому часто кажуть: remove() видаляє останній елемент, який повернув next().

Ітератор одноразовий

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

Приклад із міні застосунку: чистимо порожні рядки

Продовжімо практичним прикладом. Уявімо, що в проєкті є список покупок, і користувач іноді додає сміття (порожні рядки, пробіли). Ми хочемо зробити команду cleanup, яка видалить порожні записи.

fun cleanupBlankItems(items: MutableList<String>) {
    val it = items.iterator()

    while (it.hasNext()) {
        val name = it.next()
        if (name.isBlank()) {
            it.remove()
        }
    }
}

Ця функція маленька, але корисна. Вона показує випадок, коли видалення відбувається за умовою під час обходу, і тут ітератор — найнадійніший інструмент.

Контракт MutableIterator.remove(): як не порушити правила

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

Найчастіша проблема — викликати remove() двічі поспіль, не зробивши нового next(). Покажемо, як не треба:

fun main() {
    val items = mutableListOf("remove", "x")
    val it = items.iterator()

    it.next()
    it.remove()

    // it.remove() // не можна: другого next() не було
    println(items) // [x]
}

Логіка проста: після remove() ітератор уже видалив «останній виданий елемент». Щоб видалити щось іще, він має знову видати елемент через next(). Якщо спробувати видалити повторно, ітератор не розуміє, «що саме ви хочете видалити», і справедливо свариться.

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

3. Стратегія: видалення за індексами справа наліво

Іноді ітератор — не найзручніший варіант. Наприклад, ваша логіка зав’язана на індекс: ви видаляєте «кожен третій елемент», видаляєте діапазон або вам важливо показувати користувачеві номер елемента. У таких випадках простіше мислити індексами. Але тоді видаляти потрібно так, щоб видалення не впливало на ті елементи, які ви ще не перевірили.

Фокус у тому, що в списку індекси йдуть від 0 до lastIndex, де lastIndex == size - 1. Якщо йти з кінця до початку, то видалення елемента не зсуває елементи, що стоять лівіше. Отже, «ще не перевірені» елементи не змінюють індекс.

Ось безпечний приклад:

fun main() {
    val items = mutableListOf("keep", "remove", "remove", "keep")

    for (i in items.lastIndex downTo 0) {
        if (items[i] == "remove") {
            items.removeAt(i)
        }
    }

    println(items) // [keep, keep]
}

Мінісхема: чому справа наліво працює

flowchart TD
    A[Йдемо i зліва направо] --> B["Видаляємо items[i]"]
    B --> C[Елементи праворуч зсуваються вліво]
    C --> D[Наступний i пропускає один елемент]
    D --> E[Логічна помилка]

    A2[Йдемо i справа наліво] --> B2["Видаляємо items[i]"]
    B2 --> C2[Зсуваються лише елементи праворуч, але праворуч уже все перевірено]
    C2 --> D2[Неперевірені елементи ліворуч не змінюють індекс]
    D2 --> E2[Логіка коректна]

4. Як обрати стратегію в реальному коді

На практиці ви обиратимете стратегію не «за красою», а за тим, що потрібно в конкретній операції. Щоб не тримати все в голові на рівні відчуттів, зручно мати невелику таблицю-нагадувалку.

MutableIterator.remove()

list.remove(value)

Зверніть увагу: таблиця не каже «завжди робіть так». Вона каже: «якщо ви вже опинилися в ситуації X — ось найпередбачуваніший шлях».

5. Безпечне видалення з MutableMap під час обходу

Map — не список: за індексами ви по ньому не пройдете. Але видаляти з MutableMap під час обходу інколи теж дуже хочеться. Наприклад, у нашому застосунку може бути MutableMap<String, Int> як «склад»: товар → кількість. І ми хочемо прибрати товари, де кількість стала 0.

Якщо ви спробуєте робити stock.remove(key) усередині for ((k, v) in stock), вийде той самий конфлікт: «обхід через ітератор, видалення напряму». Правильний варіант — ітератор за entries:

fun removeZeroStock(stock: MutableMap<String, Int>) {
    val it = stock.entries.iterator()

    while (it.hasNext()) {
        val entry = it.next()
        if (entry.value == 0) {
            it.remove()
        }
    }
}

Чому саме entries? Тому що Map.Entry одразу дає і ключ, і значення — без повторного пошуку. А ітератор за entries вміє коректно видалити поточну пару. Концептуально це той самий принцип, що й зі списком: видаляти має той, хто обходить.

6. Вбудовуємо в застосунок: операції очищення даних

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

Припустімо, у нашому консольному застосунку список покупок зберігається так: кожна покупка — це Pair<String, Int>, де first — назва товару, а second — кількість. (Класи ми ще не проходили, тому без data class.)

Зробімо функцію, яка видаляє покупки з кількістю <= 0. Це класичний випадок «видаляємо багато елементів за умовою», тож ітератор підходить ідеально:

fun removeNonPositive(items: MutableList<Pair<String, Int>>) {
    val it = items.iterator()

    while (it.hasNext()) {
        val item = it.next()
        if (item.second <= 0) {
            it.remove()
        }
    }
}

А тепер ситуація, де зручніші індекси. Припустімо, ми хочемо видалити всі елементи з назвою "tmp" (користувач додавав тимчасові записи), але нам також потрібно вивести, які саме рядки ми видалили, — з їхнім «номером у списку на момент видалення». Тоді можна йти справа наліво: номери елементів праворуч нас уже не цікавлять.

fun removeAllTmp(items: MutableList<String>) {
    for (i in items.lastIndex downTo 0) {
        if (items[i] == "tmp") {
            items.removeAt(i)
        }
    }
}

Тут важливо не намагатися зробити «красивіше» і не замінювати це на обхід зліва направо. Справа наліво — не примха, а гарантія коректності.

remove(value) і removeAt(index): не переплутайте сенс

Коли ви пишете код, який «видаляє», дуже легко почати плутати: ви видаляєте за значенням чи за позицією? Це особливо помітно в командних застосунках, де користувач вводить remove 3 і очікує «видалити третій елемент», а ви випадково робите «видалити елемент зі значенням "3"».

У MutableList зазвичай є дві різні операції: видалення за значенням і видалення за індексом. У Kotlin це прямо видно з назв: removeAt(i) видаляє за позицією, а remove(x) — за значенням. Коли ви проєктуєте команди, заздалегідь обирайте семантику: або команда remove видаляє за номером (тоді потрібні removeAt і перевірка i in indices), або за значенням (тоді remove(value)), або у вас мають бути дві різні команди.

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

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

Помилка №1: видаляти через колекцію всередині for (x in collection).
Це виглядає природно, але конфліктує з тим, як працює for: «під капотом» він використовує ітератор, а ви змінюєте структуру колекції безпосередньо. Частий підсумок — ConcurrentModificationException, а інколи ще гірше: «просто дивна поведінка». Надійне рішення — видаляти або через MutableIterator.remove(), або взагалі не видаляти під час обходу.

Помилка №2: іти за індексами зліва направо й робити removeAt(i) усередині циклу.
Формально ви «все контролюєте», але видалення зсуває елементи, і ви легко пропускаєте частину колекції або виходите за межі. Якщо вже обрано індексний стиль, правило одне: видаляємо справа наліво через for (i in lastIndex downTo 0).

Помилка №3: викликати it.remove() не за контрактом, наприклад двічі поспіль.
MutableIterator.remove() видаляє елемент, який повернув останній next(). Якщо ви викличете remove() до next() або повторите remove() без нового next(), ітератор не зможе коректно визначити ціль видалення й викине виняток. Дисципліна проста: «next() → перевірка → за потреби remove()».

Помилка №4: намагатися видалити з Map, обходячи keys, і паралельно робити map.remove(key).
Навіть якщо здається, що «я ж видаляю за ключем — логічно», проблема та сама: обхід і видалення використовують різні механізми. Надійний шлях: val it = map.entries.iterator() і видалення через it.remove().

Помилка №5: плутати «індекс» і «номер для користувача».
Користувач думає «перший елемент» і має на увазі 1, а список думає «перший елемент» і має на увазі індекс 0. Якщо ви приймаєте команду видалення за номером, завжди робіть index = number - 1 і перевіряйте index in items.indices, інакше ви отримаєте або видалення не того елемента, або падіння.