⚙️ C++

Итераторы и генераторы в C++: подробное руководство

Урок 29 / 39 • Полная теория для чтения

Что это такое и зачем? (аналогия из реальной жизни)

Представь, что ты — библиотекарь, а перед тобой стоит огромный стеллаж с книгами. Тебе нужно выписать названия всех книг на листочек. У тебя есть два способа это сделать:

Первый способ (без итератора): Ты снимаешь с полки сразу все книги, складываешь их на стол, и только потом начинаешь переписывать. Но что, если книг 10 000? Стол сломается, руки устанут, да и места не хватит. В программировании это называется "загрузить всё в память".

Второй способ (с итератором): Ты подходишь к стеллажу, смотришь на первую книгу, записываешь её название. Затем переводишь взгляд на вторую, записываешь. И так — книга за книгой, не снимая их с полки. Ты не держишь все книги в руках одновременно, ты просто указываешь пальцем на каждую следующую.

Вот этот "указательный палец" программиста и есть итератор. А процесс, когда палец сам двигается от книги к книге, пока не дойдёт до конца полки — это итерация.

Генератор — это волшебная книга, которая сама пишет свой текст, когда ты её открываешь. Ты просишь: "Дай мне следующую главу", и книга её создаёт прямо на глазах. Ей не нужно хранить все главы в себе — она придумывает их по мере необходимости. В C++ генераторы — это функции, которые могут "засыпать" и "просыпаться", запоминая, на чём остановились.

💡 Главная идея: Итераторы позволяют перебирать элементы, не зная, как они устроены внутри. Генераторы позволяют создавать элементы "на лету", не храня их все в памяти.

Теория: как это работает изнутри

Итераторы: указатели с интеллектом

В C++ итератор — это объект, который ведёт себя как указатель. Но если обычный указатель просто хранит адрес в памяти, то итератор может быть хитрее. Он может перебирать элементы связного списка (где каждый элемент "не знает", где находится следующий), или элементы дерева, или даже строки в файле на диске.

У каждого контейнера (vector, list, map, set) есть свои итераторы. Они знают внутреннюю структуру контейнера и умеют правильно переходить к следующему элементу.

Категории итераторов (от простого к сложному):

Категория	Что умеет	Пример контейнера
Input (входной)	Только читать, только вперёд	Поток ввода (cin)
Output (выходной)	Только писать, только вперёд	Поток вывода (cout)
Forward (прямой)	Читать и писать, только вперёд	forward_list
Bidirectional (двунаправленный)	Читать, писать, вперёд и назад	list, set, map
Random Access (произвольный доступ)	Всё выше + прыгнуть на 5 шагов вперёд или назад за O(1)	vector, deque, array

⚠️ Важно: Чем мощнее итератор, тем быстрее с ним работать. Но не все контейнеры могут дать мощный итератор. Например, у связного списка нет произвольного доступа — чтобы дойти до 5-го элемента, нужно пройти через 4 предыдущих.

Генераторы: функции-долгожители

В C++20 появились корутины (coroutines) — это и есть генераторы. Обычная функция работает так: вызвали — она выполнилась — вернула результат — всё, функция умерла. Корутина работает иначе: она может приостановиться (yield), сохранить своё состояние, а потом продолжить с того же места.

Представь, что ты читаешь книгу. Обычная функция — это когда ты прочитал книгу целиком за один присест и пересказал другу. Корутина — это когда ты читаешь по одной странице и каждый раз, когда друг просит "что дальше?", ты открываешь книгу на том месте, где остановился в прошлый раз.

Внутри корутины компилятор создаёт специальную структуру, которая хранит:

Все локальные переменные функции
Текущую точку выполнения (на какой строке мы остановились)
Счётчик вызовов (сколько раз уже возвращали значение)

Синтаксис в C++: все формы и варианты

Базовые итераторы

Каждый контейнер предоставляет методы begin() и end(). begin() указывает на первый элемент, end() — на элемент "за последним" (не на последний!).

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = {10, 20, 30, 40, 50};
    
    // Получаем итератор на начало
    std::vector<int>::iterator it = numbers.begin();
    
    // Разыменовываем итератор (получаем значение)
    std::cout << *it << std::endl;  // Выведет 10
    
    // Переходим к следующему элементу
    it++;
    std::cout << *it << std::endl;  // Выведет 20
    
    return 0;
}

Range-based for (цикл по диапазону)

С C++11 появился удобный синтаксис, который скрывает работу с итераторами:

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    
    // Этот цикл внутри использует итераторы, но мы их не видим
    for (int x : vec) {
        std::cout << x << " ";
    }
    // Выведет: 1 2 3 4 5
    
    // Если нужно менять элементы, используем ссылку
    for (int& x : vec) {
        x = x * 2;
    }
    
    // Теперь vec = {2, 4, 6, 8, 10}
    
    return 0;
}

Константные и обратные итераторы

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    
    // const_iterator — нельзя менять элементы
    std::vector<int>::const_iterator cit = vec.cbegin();
    // *cit = 10;  // Ошибка! Нельзя изменить
    
    // reverse_iterator — перебор в обратном порядке
    std::vector<int>::reverse_iterator rit = vec.rbegin();
    std::cout << *rit << std::endl;  // Выведет 5 (последний элемент)
    
    // Удобный цикл в обратном порядке
    for (auto it = vec.rbegin(); it != vec.rend(); ++it) {
        std::cout << *it << " ";
    }
    // Выведет: 5 4 3 2 1
    
    return 0;
}

Генераторы (корутины) в C++20

Для работы с генераторами нужно подключить заголовок <generator> (доступен с C++23) или использовать библиотеку <experimental/generator>. Пока стандарт ещё не до конца устоялся, но принцип такой:

#include <iostream>
#include <generator>  // C++23

// Генератор, который выдаёт числа Фибоначчи
std::generator<int> fibonacci() {
    int a = 0, b = 1;
    while (true) {
        co_yield a;  // Приостанавливаемся и возвращаем значение
        int next = a + b;
        a = b;
        b = next;
    }
}

int main() {
    for (int value : fibonacci()) {
        if (value > 100) break;  // Останавливаемся, когда число превысит 100
        std::cout << value << " ";
    }
    // Выведет: 0 1 1 2 3 5 8 13 21 34 55 89
    
    return 0;
}

Примеры кода — от простого к сложному

Пример 1: Ручной перебор вектора

#include <iostream>
#include <vector>

int main() {
    // Создаём вектор с оценками учеников
    std::vector<int> grades = {85, 92, 78, 95, 88};
    
    // Получаем итератор на начало
    std::vector<int>::iterator it = grades.begin();
    
    // Пока не дошли до конца
    while (it != grades.end()) {
        // Разыменовываем итератор, чтобы получить значение
        std::cout << "Оценка: " << *it << std::endl;
        // Переходим к следующему элементу
        ++it;
    }
    
    return 0;
}

Пример 2: Поиск элемента с помощью итератора

#include <iostream>
#include <vector>
#include <algorithm>  // для std::find

int main() {
    std::vector<std::string> fruits = {"яблоко", "банан", "апельсин", "груша"};
    
    // Ищем "апельсин"
    auto it = std::find(fruits.begin(), fruits.end(), "апельсин");
    
    // Проверяем, нашли ли
    if (it != fruits.end()) {
        std::cout << "Нашли: " << *it << std::endl;
        
        // Можем изменить найденный элемент
        *it = "мандарин";
    } else {
        std::cout << "Не нашли" << std::endl;
    }
    
    // Выведем все фрукты после изменения
    for (const auto& fruit : fruits) {
        std::cout << fruit << " ";
    }
    // Выведет: яблоко банан мандарин груша
    
    return 0;
}

Пример 3: Итераторы для map (словаря)

#include <iostream>
#include <map>

int main() {
    // Словарь: имя -> возраст
    std::map<std::string, int> ages;
    ages["Анна"] = 25;
    ages["Борис"] = 30;
    ages["Виктор"] = 28;
    
    // Итератор для map указывает на пару (ключ, значение)
    for (auto it = ages.begin(); it != ages.end(); ++it) {
        // it->first — это ключ (имя)
        // it->second — это значение (возраст)
        std::cout << it->first << ": " << it->second << " лет" << std::endl;
    }
    
    // Можно использовать structured binding (C++17)
    for (const auto& [name, age] : ages) {
        std::cout << name << ": " << age << " лет" << std::endl;
    }
    
    return 0;
}

Пример 4: Удаление элементов во время итерации

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    // Удаляем все чётные числа
    auto it = numbers.begin();
    while (it != numbers.end()) {
        if (*it % 2 == 0) {
            // erase возвращает итератор на следующий элемент
            it = numbers.erase(it);
        } else {
            ++it;
        }
    }
    
    for (int n : numbers) {
        std::cout << n << " ";
    }
    // Выведет: 1 3 5 7 9
    
    return 0;
}

⚠️ Опасная ошибка: Если после erase не обновить итератор, он станет недействительным (invalid). Использовать его дальше нельзя!

Пример 5: Свой итератор для своего класса

#include <iostream>
#include <vector>

// Простой класс "Колода карт"
class Deck {
private:
    std::vector<std::string> cards;
    
public:
    Deck() {
        cards = {"Туз", "Король", "Дама", "Валет", "10"};
    }
    
    // Внутренний класс-итератор
    class Iterator {
    private:
        std::vector<std::string>::iterator current;
        
    public:
        Iterator(std::vector<std::string>::iterator it) : current(it) {}
        
        std::string& operator*() { return *current; }
        Iterator& operator++() { ++current; return *this; }
        bool operator!=(const Iterator& other) { return current != other.current; }
    };
    
    Iterator begin() { return Iterator(cards.begin()); }
    Iterator end() { return Iterator(cards.end()); }
};

int main() {
    Deck deck;
    
    // Теперь можно использовать range-based for
    for (auto card : deck) {
        std::cout << card << " ";
    }
    // Выведет: Туз Король Дама Валет 10
    
    return 0;
}

Пример 6: Генератор бесконечной последовательности

#include <iostream>
#include <generator>  // C++23

// Генератор, который выдаёт квадраты чисел
std::generator<int> squares() {
    int n = 0;
    while (true) {
        co_yield n * n;
        ++n;
    }
}

int main() {
    int count = 0;
    for (int sq : squares()) {
        if (count >= 10) break;  // Возьмём только первые 10
        std::cout << sq << " ";
        ++count;
    }
    // Выведет: 0 1 4 9 16 25 36 49 64 81
    
    return 0;
}

Пример 7: Генератор с фильтрацией

#include <iostream>
#include <generator>

// Генератор простых чисел (решето Эратосфена на лету)
std::generator<int> prime_numbers() {
    co_yield 2;  // Первое простое число
    
    int n = 3;
    while (true) {
        bool is_prime = true;
        // Проверяем, делится ли n на нечётные числа до sqrt(n)
        for (int d = 3; d * d <= n; d += 2) {
            if (n % d == 0) {
                is_prime = false;
                break;
            }
        }
        if (is_prime) {
            co_yield n;
        }
        n += 2;  // Проверяем только нечётные числа
    }
}

int main() {
    int count = 0;
    for (int prime : prime_numbers()) {
        if (count >= 15) break;
        std::cout << prime << " ";
        ++count;
    }
    // Выведет: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
    
    return 0;
}

Сравнение с Python: чем похоже и чем отличается

Характеристика	C++	Python
Синтаксис итерации	`for (auto x : vec)` или ручные итераторы	`for x in vec:` — всегда через итераторы
Создание итератора	`vec.begin()`, `vec.end()`	`iter(vec)`, `next(iter)`
Генераторы	Корутины с `co_yield` (C++20/23)	Функции с `yield` (с Python 2.5)
Ленивые вычисления	Нужно писать вручную или использовать ranges (C++20)	Встроенные: range, map, filter — ленивые
Бесконечные последовательности	Можно через генераторы, но нужно быть осторожным	Легко: `itertools.count()`
Производительность	Очень высокая, нет накладных расходов на итерацию	Есть накладные расходы на каждый шаг итерации
Сложность для новичка	Высокая (нужно понимать типы, указатели, шаблоны)	Низкая (всё скрыто, просто работает)

💡 Главное отличие: В Python всё — итератор. Даже строка — это итератор по символам. В C++ итератор — это отдельная сущность, которую нужно явно запрашивать у контейнера. Python жертвует производительностью ради простоты, C++ — наоборот.

Типичные ошибки и подводные камни

1. Итератор после изменения контейнера

std::vector<int> vec = {1, 2, 3, 4, 5};
auto it = vec.begin();  // Итератор указывает на первый элемент

vec.push_back(6);  // Добавили элемент — вектор мог перевыделить память!
// it теперь может быть недействительным!
std::cout << *it;  // ОПАСНО! Может быть краш или мусор

⚠️ Правило: После любой операции, которая может изменить размер контейнера (push_back, insert, erase, resize), все старые итераторы становятся недействительными. Нужно получать их заново.

2. Сравнение итераторов из разных контейнеров

std::vector<int> v1 = {1, 2, 3};
std::vector<int> v2 = {4, 5, 6};

auto it1 = v1.begin();
auto it2 = v2.begin();

// if (it1 == it2) { ... }  // Ошибка компиляции! Нельзя сравнивать итераторы разных контейнеров

3. Забыли разыменовать итератор

std::vector<int> vec = {10, 20, 30};
auto it = vec.begin();

// std::cout << it;  // Ошибка! Выведется адрес, а не значение
std::cout << *it;  // Правильно: 10

4. Выход за пределы

std::vector<int> vec = {1, 2, 3};
auto it = vec.end();
// *it;  // Ошибка! end() указывает на элемент "за последним", его нельзя разыменовывать

5. Бесконечный цикл с генератором

// Если забыть break в бесконечном генераторе
for (int x : fibonacci()) {  // fibonacci() никогда не заканчивается
    std::cout << x << " ";  // Будет печатать вечно!
}

Лучшие практики и советы профессионалов

1. Используйте auto для итераторов

Вместо того чтобы писать длинные типы:

// Плохо: длинно и сложно
std::map<std::string, std::vector<int>>::const_iterator it = my_map.begin();

// Хорошо: auto делает код чище
auto it = my_map.begin();

2. Предпочитайте range-based for ручным итераторам

Если вам не нужен доступ к позиции элемента, используйте for (auto x : container). Это безопаснее и читаемее.

3. Для удаления элементов используйте идиому erase-remove

std::vector<int> vec = {1, 2, 3, 2, 4, 2, 5};

// Удаляем все двойки
auto new_end = std::remove(vec.begin(), vec.end(), 2);
vec.erase(new_end, vec.end());

// Теперь vec = {1, 3, 4, 5}

4. Используйте const_iterator, если не собираетесь менять данные

void print_vector(const std::vector<int>& vec) {
    // cbegin() и cend() возвращают const_iterator
    for (auto it = vec.cbegin(); it != vec.cend(); ++it) {
        std::cout << *it << " ";
    }
}

5. Для генераторов используйте ограничение на количество

// Всегда предусматривайте выход из бесконечного генератора
int limit = 100;
for (int value : fibonacci()) {
    if (value > limit) break;
    // работаем с value
}

6. Проверяйте итераторы на валидность

auto it = std::find(vec.begin(), vec.end(), target);
if (it != vec.end()) {
    // Итератор валиден, можно использовать
    std::cout << *it;
} else {
    // Элемент не найден, it == vec.end()
    std::cout << "Не найдено";
}

Вопросы для самопроверки

Вопрос: Что такое итератор простыми словами?
Ответ: Это объект, который указывает на элемент контейнера и умеет переходить к следующему. Как курсор в текстовом редакторе.
Вопрос: Чем отличается begin() от end()?
Ответ: begin() указывает на первый элемент, end() — на элемент "за последним". end() нельзя разыменовывать.
Вопрос: Почему после push_back старые итераторы могут стать недействительными?
Ответ: Потому что вектор может перевыделить память, если старый буфер заполнен. Итераторы хранят адреса, которые после перевыделения становятся неверными.
Вопрос: В чём разница между итератором и указателем?
Ответ: Указатель — это просто адрес памяти. Итератор — это объект, который может быть сложнее: он знает структуру контейнера и умеет правильно переходить к следующему элементу даже в списке или дереве.
Вопрос: Что такое генератор (корутина)?
Ответ: Функция, которая может приостанавливать своё выполнение и возвращать промежуточные результаты, а потом продолжать с того же места.
Вопрос: Какой итератор у std::list?
Ответ: Двунаправленный (Bidirectional). Можно двигаться вперёд и назад, но нельзя прыгнуть сразу на 5 элементов вперёд.
Вопрос: Можно ли использовать range-based for с map?
Ответ: Да. Каждый элемент — это пара (ключ, значение). Можно использовать structured binding: for (const auto& [key, value] : my_map).
Вопрос: Что будет, если разыменовать end()?
Ответ: Неопределённое поведение. Программа может упасть, выдать мусор или "случайно" работать, но доверять этому нельзя.
Вопрос: В чём преимущество генераторов перед обычными функциями?
Ответ: Генераторы не хранят все результаты в памяти, а выдают их по одному. Это позволяет работать с бесконечными последовательностями и экономить память.
Вопрос: Как удалить элемент из вектора во время итерации?
Ответ: Использовать it = vec.erase(it), который возвращает итератор на следующий элемент. Не забыть обновить итератор!

Итог и что изучить дальше

Мы прошли большой путь. Ты узнал, что:

Итераторы — это "указательные пальцы" для перебора элементов контейнера. Они бывают разных видов: от простых (только вперёд) до мощных (прыжки на любое расстояние).
Генераторы — это "ленивые фабрики", которые производят элементы по требованию, не занимая память.
В C++ нужно быть аккуратным с итераторами: они "ломаются" при изменении контейнера, их нельзя сравнивать между разными контейнерами, и нельзя разыменовывать end().
Range-based for — твой друг. Используй его, когда не нужен доступ к позиции элемента.

Что изучать дальше:

Библиотека ranges (C++20) — позволяет писать цепочки преобразований над контейнерами без создания промежуточных копий. Например: vec | std::views::filter(...) | std::views::transform(...).
Алгоритмы STL — std::sort, std::find, std::copy, std::accumulate и другие. Они работают с итераторами и часто эффективнее ручных циклов.
Пользовательские контейнеры — попробуй написать свой класс с поддержкой итераторов. Это отличная практика для понимания, как работают стандартные контейнеры.
Асинхронные корутины — генераторы — это только вершина айсберга. Корутины в C++20 позволяют писать асинхронный код, который выглядит как синхронный.

🎯 Главный совет: Не бойся итераторов. Они — один из самых мощных инструментов C++. Когда ты привыкнешь к ним, ты будешь писать код, который работает быстро и эффективно, а главное — красиво и понятно.

Помни: программирование — это искусство объяснять компьютеру, что делать. Итераторы и генераторы — это твой способ сказать: "Перебери это, но не всё сразу, а по одному, и сделай это быстро". Удачи в изучении!

← Предыдущая Дженерики и параметрические типы в C++: подробное Вперёд → Модули, пакеты и импорт в C++: подробное руководст