🧦 Итераторы: фундамент диапазонов

Прежде чем строить проекции и алгоритмы поверх диапазонов, стоит вспомнить, на чём диапазон стоит. А стоит он на итераторе — объекте, который умеет всего три вещи: разыменовываться (*it), двигаться вперёд (++it) и сравниваться с концом. Всё остальное — надстройки.


🍟 Итератор без контейнера

Итератору не обязательно указывать в память — он может генерировать значения на лету. Напишем итератор, выдающий числа Фибоначчи:

struct FibIterator {
    using value_type        = long long;
    using difference_type   = std::ptrdiff_t;
    using iterator_category = std::input_iterator_tag;

    long long a = 0, b = 1;
    int count = 0;
    int max_count;

    FibIterator(int n) : max_count(n) {}
    FibIterator() : max_count(-1) {} // sentinel (конец)

    long long operator*() const { return a; }

    FibIterator& operator++() {
        auto next = a + b;
        a = b;
        b = next;
        ++count;
        return *this;
    }

    FibIterator operator++(int) {
        auto tmp = *this;
        ++(*this);
        return tmp;
    }

    bool operator==(const FibIterator& other) const {
        if (other.max_count == -1) return count >= max_count;
        return count == other.count;
    }
};

Никакого массива за спиной нет: текущее состояние — пара a, b — живёт прямо в итераторе, а operator++ вычисляет следующее число. Разыменование лишь возвращает уже готовое значение, поэтому оно const и дешёвое.


🍔 Сентинел: конец, который не элемент

Обратите внимание на operator==: итератор, созданный по умолчанию, играет роль сентинела — маркера конца. Он не хранит «последнее число Фибоначчи» (его и не существует), а просто отвечает на вопрос «мы уже нагенерировали max_count элементов?».

Это ключевая идея ranges: end() не обязан быть «настоящим» итератором, указывающим за последний элемент. Ему достаточно уметь сравниваться с begin(). Здесь сентинел того же типа, что и итератор, — но в C++20 это может быть и отдельный тип (как std::unreachable_sentinel для бесконечных последовательностей).

‼️ Заметьте: operator!= мы не писали — начиная с C++20 компилятор сам выведет его из operator==. Одной перегрузкой меньше.


🍒 Диапазон — это просто begin() + end()

struct FibRange {
    int n;

    FibIterator begin() const { return FibIterator{n}; }
    FibIterator end()   const { return FibIterator{};  }
};

for (long long f : FibRange{10}) {
    std::cout << f << " "; // 0 1 1 2 3 5 8 13 21 34
}

Всё, что нужно range-based for и алгоритмам из std::ranges, — пара методов begin()/end(). Никакого наследования, никаких базовых классов: диапазон — это концепт, а не иерархия. Наш FibRange весит один int и генерирует значения лениво — ровно тот же принцип, на котором построены std::views::iota, filter и остальные адаптеры.

‼️ Тег input_iterator_tag здесь честный: пройти последовательность можно только один раз вперёд, ведь каждое разыменование опирается на накопленное состояние. Если бы мы хранили индекс и пересчитывали значение с нуля, можно было бы замахнуться и на forward_iterator — но для генератора это редко нужно.


📍Навигация: Вакансии • Задачи • Собесы

Библиотека C/C++ разработчика

#константная_правильностьx