Категорії ітераторів: input / forward / bidirectional / random-access

1. Навіщо потрібні категорії ітераторів

Якщо досі ви сприймали ітератор як «майже вказівник», ви не самотні: у перші дні знайомства з C++ я теж думав саме так. Але в STL ітератор — це не «адреса в памʼяті», а контракт можливостей: що саме з ним гарантовано можна робити, а чого очікувати не варто.

Категорії ітераторів потрібні саме для того, щоб стандартизувати ці можливості. Тоді STL-алгоритм може чесно сказати: «мені достатньо вміти робити ++it і читати *it» — або, навпаки: «ні, друзі, без it + n і it2 - it1 я сортувати не буду».

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

Ітератор і діапазон [first, last)

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

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

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

int main() {
    std::vector<std::string> tasks{"Read", "Code", "Sleep"};

    for (auto it = tasks.begin(); it != tasks.end(); ++it) {
        std::cout << *it << '\n';
    }
}
// Read
// Code
// Sleep

Тут ви бачите базові операції, які найчастіше асоціюються з ітераторами: порівняння !=, розіменування *it і просування ++it. А далі починається найцікавіше: не кожен ітератор підтримує «просунуті» операції, як-от it + 5 або --it.

Драбина можливостей ітераторів

Категорія ітератора — це, по суті, відповідь на запитання: які операції гарантовано працюють і що саме вони означають. У стандарті це не просто справа смаку, а вимоги до коректності, на які спираються алгоритми стандартної бібліотеки.

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

input

forward

bidirectional

random-access

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

2. Категорії ітераторів на практиці

input

: читання під час руху й однопрохідність

Input-ітератори зазвичай трапляються там, де дані не лежать у контейнері цілком, а надходять послідовно — як вода з крана. Ви можете підставити склянку, тобто прочитати поточне значення, потім повернути кран на наступний крок, тобто зробити ++it, — але «повернутися до минулої краплі води» вже не можна. Тому input-ітератори часто однопрохідні: ви не можете надійно зробити другий прохід тими самими даними.

Найтиповіший приклад — std::istream_iterator<T>, який читає значення з потоку. Він зручний тим, що робить «потік» схожим на контейнер, але водночас лишається потоком: щойно ви щось прочитали, повернутися назад уже не вийде.

#include <iostream>
#include <iterator>
#include <sstream>

int main() {
    std::istringstream in("10 20 30");

    std::istream_iterator<int> it(in);
    std::istream_iterator<int> end;

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

Зверніть увагу на важливий інтуїтивний момент: istream_iterator виглядає як звичайний ітератор, але за природою він ближчий до «сканера». Ви не кажете: «дай мені елемент № 5» — ви кажете: «дай наступний».

Якщо ви спробуєте мислити input-ітераторами як random-access, тобто в стилі «а давай я стрибну на 100 уперед», компілятор цілком чесно відповість: «цього ніхто не обіцяв».

forward

: лише вперед, але можна кілька проходів

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

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

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

У цій лекції ми не будемо привʼязувати forward-ітератори до конкретного нового контейнера, щоб не забігати наперед до теми наступного заняття, тому зафіксуємо головне: forward = multi-pass + лише ++. Це категорія «чесний крокомір»: уперед рухатися вміє, назад — ні, але маршрут не зникає після першого проходу.

bidirectional

: крок назад --it

Bidirectional-ітератори — це наступний рівень комфорту: до ++it додається --it. Простими словами, це «ітератор, який уміє рухатися назад», але за цим стоїть цілком практичний сенс: деякі алгоритми потребують руху в обидва боки, наприклад коли ми «йдемо з початку й з кінця назустріч».

Типові представники bidirectional-ітераторів — ітератори std::map і std::set. Це логічно: дерево, на якому зазвичай побудований map, дає змогу переходити до наступного й попереднього елемента за порядком, але «стрибнути на +100» усе одно не можна: дерево — не масив.

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<int, std::string> users{{1, "Ann"}, {3, "Bob"}, {5, "Cat"}};

    auto it = users.end();
    --it; // крок назад: тепер це останній елемент
    std::cout << it->first << " " << it->second << '\n'; // 5 Cat
}

Зауважте, як тут добре видно різницю в підході: у vector «останній елемент» часто беруть через індекси або back(), а у map ми природно рухаємося ітератором, бо це контейнер, з яким зручно працювати через обхід, а не через індекси.

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

random-access

: стрибки, індексація та різниця

Random-access — це, можна сказати, «преміум-версія» ітераторів. Тут зʼявляється все, що нагадує масив: можна швидко стрибнути на n уперед (it + n), можна взяти it[n], можна порівнювати, хто розташований раніше за порядком, і навіть обчислювати відстань як різницю ітераторів.

Класичні random-access-ітератори ви бачите постійно, навіть якщо не називаєте їх так: std::vector<T>::iterator та ітератори std::string.

#include <iostream>
#include <vector>

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

    auto it = scores.begin();
    std::cout << it[2] << '\n';     // 30
    std::cout << *(it + 3) << '\n'; // 40
}

Чому це важливо саме для STL? Тому що деякі алгоритми, наприклад std::sort, історично вимагають random-access-ітератори в класичній версії STL. Тобто якщо контейнер не має random-access-ітератора, відсортувати його через std::sort напряму ви не зможете. Не через чиюсь шкідливість, а тому, що алгоритму потрібна швидка адресація.

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

5. Зсуви та вимоги алгоритмів

Приклад: чому it + n не працює для map

Дуже типовий сценарій: ви написали гарний код на vector, потім вирішили замінити контейнер на map — бо «там же ключі» — і раптом половина операцій перестала існувати. Це не тому, що map «поганий», а тому, що в нього інша категорія ітераторів.

Ось приклад, який працює для vector, але не зобовʼязаний працювати для map. Я спеціально залишу «поганий рядок» закоментованим, щоб код компілювався:

#include <map>
#include <string>

int main() {
    std::map<int, std::string> m{{1, "one"}, {2, "two"}, {3, "three"}};

    auto it = m.begin();
    // it = it + 1; // не можна: ітератор map не random-access
    (void)it;
}

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

std::advance(it, n) і вартість операції

std::advance виглядає як просто зручна функція, але насправді вона виражає правильну думку: я хочу зсунути ітератор на n, але не хочу припускати, що цей ітератор — random-access. Тоді компілятор і стандартна бібліотека самі виберуть коректний спосіб.

На random-access-ітераторі це зазвичай буде швидкий стрибок. Для слабших категорій це перетвориться на n кроків ++it, і це нормально — просто потрібно памʼятати про вартість.

#include <iostream>
#include <iterator>
#include <map>
#include <string>

int main() {
    std::map<int, std::string> m{{1, "one"}, {2, "two"}, {3, "three"}};

    auto it = m.begin();
    std::advance(it, 2);
    std::cout << it->second << '\n'; // three
}

З погляду алгоритмічного мислення це дуже корисно: ви не привʼязуєте код до одного контейнера. Але з погляду продуктивності є чесна ціна: якщо ви зсуваєте ітератор на 1_000_000 елементів у дереві за допомогою std::advance, ви справді зробите мільйон кроків. Тож універсальність не скасовує здорового глузду — вона просто не дає вам писати некоректний код.

Схема вибору операцій за категорією

Щоб не тримати все це в голові як набір «магічних правил», мисліть так: спочатку зʼясуйте, який у вас контейнер і яка категорія ітератора, а вже потім обирайте допустимі операції. Нижче — схема-нагадувалка.

flowchart TD
    A["Є контейнер та ітератори begin/end"] --> B["Яка категорія ітератора?"]
    B --> C["input: читаю, ++"]
    B --> D["forward: читаю/пишу, ++, можна пройти кілька разів"]
    B --> E["bidirectional: ++ і --"]
    B --> F["random-access: ++/--, it+n, it[n], it2-it1"]
    F --> G["Можна застосовувати алгоритми, що вимагають random-access, наприклад sort"]
    E --> H["Можна будувати алгоритми, яким потрібен крок назад, наприклад reverse"]
    C --> I["Схоже на потік: прочитав і пішов далі"]

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

6. Типові помилки під час роботи з категоріями ітераторів

Помилка № 1: сприймати будь-який ітератор як vector::iterator і очікувати it + n усюди.
Це найпоширеніша пастка: ви пишете код так, ніби перед вами масив, а потім переносите його на map/set і дивуєтеся, що «оператори зникли». Правильна модель така: категорія визначає гарантії. Якщо потрібен універсальний зсув, використовуйте std::advance, а якщо потрібен швидкий доступ за індексом — чесно обирайте контейнер із random-access-ітераторами.

Помилка № 2: плутати «універсально» і «швидко».
Після знайомства зі std::advance легко подумати: «О! Отже, можна всюди спокійно стрибати на 10 000 елементів». Можна, але ціна буде різною. На random-access це ближче до it += 10000, а на слабших категоріях усе перетворюється на багаторазовий ++it. У результаті код лишається коректним, але може стати несподівано повільним.

Помилка № 3: намагатися робити кілька проходів по input-ітератору, ніби це контейнер.
std::istream_iterator і схожі ітератори часто читають дані з потоку: це «одноразове» джерело. Якщо ви «пройшли вперед», то вже змінили стан потоку. Тому другий прохід тими самими даними може бути неможливим або дати порожній результат. Якщо потрібен повторний обхід, спочатку збережіть дані в контейнері, наприклад у std::vector, а потім проходьте його стільки разів, скільки потрібно.

Помилка № 4: розіменовувати end() або робити кроки за межі.
end() — це не «останній елемент», а «позиція після останнього». Її не можна розіменовувати. Так само --begin() і ++(--end()) у невідповідному місці легко перетворюються на вихід за межі. Це не та помилка, яка «завжди падає одразу»: інколи вона проявляється дивними симптомами, і ви потім довго думаєте, чому програма друкує «памʼять динозаврів».

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