Implement lazy generator as forward_iterator in C++

Question

MyGenerator represents a (possibly) finite sequence of integers, that is expensive to compute. So I don't want to generate them all upfront and put them into a container.

struct MyGenerator{
  bool HasNext();
  int Next();
}

To print them all:

MyGenerator generator;
while (generator.HasNext()) {
  std::cout << generator.Next() << std::endl;
}

How to implement a similar generator that follows the protocol of a forward_iterator?

boost::function_input_iterator comes close, but I do not know the number of elements upfront.

Answer 1

First off, look at the implementation of boost::function_input_iterator, since what you want is the same except that testing the equality of iterators must be modified to cope with the fact you don't know whether it's infinite and if not how many items there are. Once you get used to the style, the authors of Boost will give you better advice via their code than I will :-)

That said, something along these lines (untested):

template <typename Generator>
struct generator_iterator : iterator<forward_iterator_tag, int> {
    generator_iterator(const Generator &gen, end = false) : count(0), gen(gen), last_val(0), is_end(end) {
        if (!end) advance();
    }
    void advance() {
        if (gen.HasNext()) {
            lastval = gen.Next();
        } else {
            is_end = True;
        }
        count += 1;
    }
    int operator *() {
        return lastval;
    }
    generator_iterator &operator++() {
        advance();
        return *this;
    }
    generator_iterator operator++(int) {
        generator_iterator result = *this;
        advance();
        return result;
    }
    bool operator==(const generator_iterator &rhs) {
        return (is_end && rhs.is_end) || (count == rhs.count);
    }
    bool operator!=(const generator_iterator &rhs) {
        return !(*this == rhs);
   }

    size_t count;
    Generator gen;
    int lastval;
    bool is_end; 
};

• In principle the count can wrap, although you only need to worry about that on implementations with a small size_t, since 64 bits will never wrap in practice. To be safe you could use a different type to keep count: uint64_t or if all else falls a user-defined large integer type. Consult the std::iterator documentation though, because once your iterator runs longer than size_t you want to give it a non-default difference_type.
• The type Generator must be copyable (and the copy must have equal state with the original, and the two must thereafter advance independently) or else you have no chance of implementing a forward_iterator other than by storing a potentially unbounded amount of output from the generator. If you only need an input_iterator then you could refer to the Generator by reference.
• If you don't need to wrap a previous MyGenerator, rather you just want to know how to write a possibly-infinite iterator, then you can get rid of the template parameter, store whatever state you like in the iterator, and just put the code to advance the state in advance().