Занурюємося в ітератори

1. Вступ

Коли ви лише починаєте програмувати, здається логічним: «якщо в мене є std::vector<int> v, то нехай функція приймає v і робить усе, що потрібно». І це справді так… доки ви не захочете обробити не весь контейнер, а лише його частину: перші 10 елементів, елементи з 2‑го по 5‑й або все, крім першого. Саме тут і починається магія — хоча насправді це просто математика діапазону.

У стандартній бібліотеці C++ майже всі алгоритми працюють за однаковим принципом: «мені не важливо, який це контейнер; покажи, де початок і де кінець, — і я пройдуся по елементах». Саме тому алгоритми такі універсальні: один і той самий std::find може працювати з vector, string, array і навіть зі «звичайним» масивом.

Щоб це працювало, бібліотеці потрібна спільна мова. Ця мова — ітератори і пара функцій begin() / end().

Ітератор: вказівник із правилами

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

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

#include <iostream>
#include <vector>

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

    for (auto it = v.begin(); it != v.end(); ++it) {
        std::cout << *it << ' ';
    }
    std::cout << '\n'; // 10 20 30
}

Зверніть увагу на деталь: умова it != v.end() — це не «для краси», а правило безпеки. end() — це межа, а не елемент.

2. Діапазон [first, last): включаємо початок, виключаємо кінець

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

Чому це зручно? Тому що порожній діапазон можна записати однаковими ітераторами: first == last. Тому що довжина діапазону природно обчислюється як кількість кроків від first до last. І тому що весь контейнер — це просто begin()…end() без жодних спеціальних випадків.

Намалюймо просту схему діапазону для вектора з трьох елементів:

flowchart LR
    A["begin()"] --> B["елемент 0"]
    B --> C["елемент 1"]
    C --> D["елемент 2"]
    D --> E["end() (за останнім)"]

end() стоїть після останнього елемента, ніби «клітинка за фінішною рискою».

Невеликий приклад: пройдемося не по всьому vector, а лише по «хвосту», починаючи з другого елемента. Ми візьмемо begin(), зробимо ++it один раз і рухатимемося до end().

#include <iostream>
#include <vector>

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

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

    for (; it != v.end(); ++it) {
        std::cout << *it << ' ';
    }
    std::cout << '\n'; // 20 30
}

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

3. Межі діапазону та константні ітератори

Чому end() не можна розіменовувати

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

Якщо ви напишете *v.end(), ви порушите контракт ітераторів. У найкращому разі отримаєте дивні дані, у найгіршому — падіння, а в найвеселішому — «працює на моєму компʼютері».

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

#include <iostream>
#include <vector>

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

    auto it = v.end();
    if (it == v.end()) {
        std::cout << "it is end(), no element here\n";
    }
}

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

begin()/end() і cbegin()/cend(): лише читання

У контейнерів є begin()/end(), а ще часто — cbegin()/cend(). Літера c означає const, тобто: «я обіцяю, що не буду змінювати елементи».

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

Невеликий приклад: друкуємо vector, але одразу показуємо, що це режим «лише читання».

#include <iostream>
#include <vector>

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

    for (auto it = v.cbegin(); it != v.cend(); ++it) {
        std::cout << *it << ' ';
    }
    std::cout << '\n'; // 4 5 6
}

Якби ми спробували зробити *it = 42;, компілятор нас зупинив би. Це приємний момент: компілятор — ваш суворий викладач, який не дає списувати.

4. Алгоритми та ітератор результату: приклад std::find

«Увесь контейнер» як діапазон

Зафіксуймо головну думку лекції: коли STL‑алгоритм каже «дай мені дані», він зазвичай очікує два ітератори: початок і кінець діапазону. А «увесь контейнер» просто задається як c.begin(), c.end() (або cbegin()/cend()).

Ця форма настільки стандартна, що ви бачитимете її постійно:

algo(c.begin(), c.end(), ...);

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

algo(c.cbegin(), c.cend(), ...);

std::find: зразок інтерфейсу

Як приклад такого інтерфейсу розгляньмо std::find. Він шукає значення в діапазоні й повертає ітератор: або «де знайшли», або last (тобто зазвичай end()), якщо нічого не знайшли.

#include <algorithm>
#include <iostream>
#include <vector>

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

    auto it = std::find(v.begin(), v.end(), 7);
    if (it != v.end()) {
        std::cout << "found: " << *it << '\n'; // found: 7
    } else {
        std::cout << "not found\n";
    }
}

Ключовий момент: результат find не можна розіменовувати наосліп. Він може виявитися рівним end().

Ітератор результату: «позиція знайденого» або «маркер не знайдено»

Багато алгоритмів у STL повертають не індекс і не true/false, а саме ітератор результату. Це зручно, бо ітератор — це водночас і позиція, і можливість щось зробити з елементом: прочитати його або змінити, якщо це дозволяє контракт.

Такий результат зазвичай читають так: «ось місце, де знайдено». А якщо не знайдено — «місце дорівнює last».

Подивімося на це на простому прикладі з рядком. Для std::string теж є ітератори, і алгоритми працюють із рядком майже так само, як і з vector.

#include <algorithm>
#include <iostream>
#include <string>

int main() {
    std::string s = "cat";

    auto it = std::find(s.begin(), s.end(), 'a');
    if (it != s.end()) {
        std::cout << "letter: " << *it << '\n'; // letter: a
    }
}

Тут it — це «вказівник» на символ усередині рядка. І якщо рядок не константний, ми теоретично могли б замінити знайдену літеру, наприклад перетворити "cat" на "cut". Але зробимо це трохи пізніше, коли перейдемо до моделі задач.

5. Мініпроєкт: TaskTracker і пошук за id через ітератори

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

Почнемо з моделі Task. Тут усе максимально просто: id, текст і прапорець done.

#include <string>

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

Тепер додамо виведення задач. Важливо: ми приймаємо const std::vector<Task>&, тому що друк не має змінювати список.

#include <iostream>
#include <vector>

void print_tasks(const std::vector<Task>& tasks) {
    for (auto it = tasks.cbegin(); it != tasks.cend(); ++it) {
        std::cout << it->id << ". " << it->title << " done=" << it->done << '\n';
    }
}

Зверніть увагу на it->id. Це зручніший запис замість (*it).id. Коли ітератор поводиться як вказівник, -> стає особливо зручним.

Пошук задачі за id: повертаємо ітератор

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

Це дуже схоже на поведінку стандартних алгоритмів: «ось ітератор результату, а далі вирішуйте самі».

#include <vector>

std::vector<Task>::iterator find_task_by_id(std::vector<Task>& tasks, int id) {
    for (auto it = tasks.begin(); it != tasks.end(); ++it) {
        if (it->id == id) return it;
    }
    return tasks.end();
}

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

Використання: спочатку перевіряємо, потім користуємося

Покажемо, як безпечно користуватися цією функцією: спочатку перевіряємо it != end(), і лише потім змінюємо задачу.

#include <iostream>
#include <vector>

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

    auto it = find_task_by_id(tasks, 2);
    if (it != tasks.end()) {
        it->done = true;
    }

    print_tasks(tasks);
    // 1. Learn C++ done=0
    // 2. Sleep done=1
}

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

Константний пошук: const_iterator і cend()

Іноді вам потрібна версія пошуку «лише для читання». Тоді повертаємо const_iterator і використовуємо cbegin()/cend().

#include <vector>

std::vector<Task>::const_iterator find_task_by_id(const std::vector<Task>& tasks, int id) {
    for (auto it = tasks.cbegin(); it != tasks.cend(); ++it) {
        if (it->id == id) return it;
    }
    return tasks.cend();
}

Це той самий зміст, але контракт стає чіткішим: «я не збираюся змінювати задачі». І компілятор це контролюватиме.

6. Індекс і ітератор: коли що обирати

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

Щоб закріпити загальну картину, погляньмо на таблицю порівняння. Її не треба завчати, але вона допомагає не плутати «позицію» та «ітератор».

STL обрала ітератори, тому що вони дають змогу будувати універсальні алгоритми. А begin()/end() — це спосіб підʼєднати контейнер до цього підходу.

7. Типові помилки під час роботи з begin()/end() та ітераторами

Помилка № 1: розіменування end() наосліп.
Найчастіша проблема виглядає так: «я викликав find, отримав it і одразу пишу *it». Якщо елемент не знайдено, it буде рівним end(), а розіменування end() — це вихід за межі контракту. Виправлення просте: спочатку if (it != end()), а вже потім — доступ до елемента.

Помилка № 2: порівняння ітераторів із різних контейнерів.
Іноді через неуважність пишуть щось на кшталт if (it == other.end()). Ітератори можна порівнювати лише в межах одного контейнера або одного діапазону. У найкращому разі код не скомпілюється, у найгіршому — ви отримаєте дуже дивну логіку. Запамʼятайте правило: «ітератор знає, звідки він».

Помилка № 3: плутанина «ітератор — це індекс».
Ітератор — не число. Його не можна просто надрукувати як позицію. У загальному випадку до нього не можна довільно щось додавати, і не варто очікувати, що він поводиться як int. Якщо вам потрібна саме позиція, це окремий крок логіки. Але в алгоритмічному стилі вона часто й не потрібна: ітератора вже достатньо, щоб читати або змінювати елемент.

Помилка № 4: використання begin()/end() там, де ви обіцяли «лише читання».
Якщо функція має лише друкувати або перевіряти, а ви берете begin() (неконстантний ітератор), код стає менш захищеним: хтось потім «випадково» додасть зміну елемента — і компілятор промовчить. Звичка писати cbegin()/cend() у функціях читання робить код надійнішим, особливо у великих проєктах.

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