Noah Watkins Noah Watkins - 4 months ago 15
C++ Question

Equivalent C++ to Python generator pattern

I've got some example Python code that I need to mimic in C++. I do not require any specific solution (such as co-routine based yield solutions, although they would be acceptable answers as well), I simply need to reproduce the semantics in some manner.

Python



This is a basic sequence generator, clearly too large to store a materialized version.

def pair_sequence():
for i in range(2**32):
for j in range(2**32):
yield (i, j)


The goal is to maintain two instances of the sequence above, and iterate over them in semi-lockstep, but in chunks. In the example below the
first_pass
uses the sequence of pairs to initialize the buffer, and the
second_pass
regenerates the same exact sequence and processes the buffer again.

def run():
seq1 = pair_sequence()
seq2 = pair_sequence()

buffer = [0] * 1000
first_pass(seq1, buffer)
second_pass(seq2, buffer)
... repeat ...


C++



The only thing I can find for a solution in C++ is to mimic
yield
with C++ coroutines, but I haven't found any good reference on how to do this. I'm also interested in alternative (non general) solutions for this problem. I do not have enough memory budget to keep a copy of the sequence between passes.

Answer

Generators exist in C++, just under another name: Input Iterators. For example, reading from std::cin is similar to having a generator of char.

You simply need to understand what a generator does:

  • there is a blob of data: the local variables define a state
  • there is an init method
  • there is a "next" method
  • there is a way to signal termination

In your trivial example, it's easy enough. Conceptually:

struct State { unsigned i, j; };

State make();

void next(State&);

bool isDone(State const&);

Of course, we wrap this as a proper class:

class PairSequence {
  typedef void (PairSequence::*BoolLike)();
  void non_comparable();
public:
  typedef std::input_iterator_tag iterator_category;
  typedef std::pair<unsigned, unsigned> value_type;
  typedef value_type const& reference;
  typedef value_type const* pointer;
  typedef ptrdiff_t difference_type;

  PairSequence(): done(false) {}

  // Safe Bool idiom
  operator BoolLike() const {
    return done ? nullptr : &PairSequence::non_comparable;
  }

  reference operator*() const { return ij; }
  pointer operator->() const { return &ij; }

  PairSequence& operator++() {
    static unsigned const Max = std::numeric_limts<unsigned>::max();

    assert(!done);

    if (ij.second != Max) { ++ij.second; return *this; }
    if (ij.first != Max) { ij.second = 0; ++ij.first; return *this; }

    done = true;
    return *this;
  }

  PairSequence operator++(int) {
    PairSequence const tmp(*this);
    ++*this;
    return tmp;
  }

private:
  bool done;
  value_type ij;
};

So hum yeah... might be that C++ is a tad more verbose :)