Step 4 of 5

A lazy range

An iterator doesn't have to point at stored data at all. It can compute each value when asked. Such a range is lazy: it takes no memory for its elements, however many there are. That's how std::views::iota works, and it's how Python's range() is built: range(0, 1'000'000'000) costs nothing until you loop over it.

#include <iostream>

// Powers of two up to a limit: 1, 2, 4, 8, ...
class Powers {
public:
    explicit Powers(long limit) : limit_(limit) {}

    class Iterator {
    public:
        Iterator(long v, long limit) : v_(v), limit_(limit) {}
        long operator*() const { return v_; }
        Iterator& operator++() { v_ *= 2; return *this; }
        // "Done" means the value passed the limit, not that it equals some exact number.
        bool operator==(const Iterator& o) const { return done() == o.done(); }

    private:
        bool done() const { return v_ > limit_; }
        long v_, limit_;
    };

    Iterator begin() const { return Iterator(1, limit_); }
    Iterator end() const { return Iterator(limit_ + 1, limit_); }   // any "done" position

private:
    long limit_;
};

int main() {
    for (long p : Powers(100)) std::cout << p << " ";
    std::cout << "\n";
    int count = 0;
    for (long p : Powers(1'000'000'000)) { (void)p; count++; }
    std::cout << count << " powers of two up to a billion\n";
}

1 2 4 8 16 32 64 
30 powers of two up to a billion

The end condition is the tricky part

The values here jump 1, 2, 4, ... 64, 128. None of them is exactly 100, so an end() iterator holding the value 100, compared with plain v_ == o.v_, would never match, and the loop would run forever (and overflow). The fix is to compare states: two iterators are equal when both are "done" or both are at the same live position. The example keeps it simple by comparing only the done flag, which is all a range-for loop needs, since it only ever compares against end().

Your Range has the same problem: with a step of 3, 0, 3, 6, 9 jumps past a stop of 10. One clean fix is to compare "am I done?" (v_ >= stop_) as above. Another is to compute the number of steps up front and compare a step counter.

Your turn: write class Range for for (int i : Range(start, stop, step)) with a positive step, like Python: it yields start, start + step, ... while the value is < stop. Careful: with a step of 3, the values may jump past stop without ever equalling it, so the end condition can't be a plain == on the current value.

Previous: Iterator concepts and algorithms Next: Challenge: a ring buffer