5

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.

Niklas
  • 3,753
  • 4
  • 21
  • 29

1 Answers1

3

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().
Steve Jessop
  • 273,490
  • 39
  • 460
  • 699
  • Thank you, this fits perfectly! Should I also specify operator!= or is this inferred from operator== anyway? – Niklas Dec 22 '14 at 17:11
  • @Niklas: you should, I forgot it. Been a while since I've done one. – Steve Jessop Dec 22 '14 at 18:08
  • I think `forward_iterator_tag` should be `input_iterator_tag` since copies of iterators aren't valid after incrementing another copy; though the "lastval" is correctly repeatable, and subsequently incrementing both does yield "equivalent" iterators, their dereferenced values are not the same – sehe Dec 22 '14 at 21:15
  • @Sehe: I think my remark about `Generator` being copyable addresses this. Naturally it would be *possible* to implement a type `MyGenerator` such that it behaves like you say -- calling `GetNext()` on a copy gives a different result from calling `GetNext()` on the original -- but I don't see why you say this necessarily is what happens. Since the questioner explicitly wants a `forward_iterator`, not merely an `input_iterator`, my hope is that they won't do that. The requirements on the `Generator` template argument would have to make explicit how copies behave. – Steve Jessop Dec 24 '14 at 11:19
  • @SteveJessop You got my point reversed (I never meant to imply that copies should return different values at all). However, since the iterators _do_ diverge after copying/incrementing they are not a model of forward iterators. (The code and descriptions suggests that to me it is intended to be. This is why I commented) – sehe Dec 24 '14 at 12:01
  • @sehe: "since the iterators do diverge after copying/incrementing" - what makes you say this? For example using a generator such as `struct MyGenerator { int count; MyGenerator() : count(0) {} bool HasNext() { return count != INT_MAX; } int Next() { return count++; }};` what would be the problem? I don't think it behaves as you say it does, what am I missing? – Steve Jessop Dec 26 '14 at 17:12
  • @SteveJessop that's a stateful, deterministic, copyable generator. How about one that would semantically yield an InputTraversal range: **[demo](http://coliru.stacked-crooked.com/a/5b027a5dd089098c)** (note two unrelated fixes that prevent side-effects on end-iterator construction and avoids comparing freshly constructed iterators as equivalent regards of of their `is_end` flag). The point is that it's too much to promise `forward_iterator_tag` semantics, because it depends on the semantics of the source generator. – sehe Dec 26 '14 at 20:53
  • @sehe: if you want to dispute the behavior of `Generator` then I think those points really belong on the question rather than this answer, since you're telling the questioner to ask a different question. If you can think of a clear way to state the required properties of `Generator`, though, then I'd add that to the answer, since that documentation is part of the class template `generator_iterator` :-) – Steve Jessop Dec 27 '14 at 18:56