Generators in C++

c-smile

Rate me:

3.90/5 (20 votes)

17 Aug 2015BSD2 min read

98.2K

The way to add generators with yield to C++

Introduction

As we know, iterators in C++ is a good but not a perfect abstraction. The concept of foreach() (D, Python, Ruby, etc.) appears as a more generic solution. At least, foreach() does not require an artificial iterator::end() to be defined for the collection.

The foreach() abstraction can be imagined as some function/object that returns the next value of collection/sequence each time it gets invoked. Such functions are known as generators.

The proposed implementation of the generator/yield feature is provided below in full.

Background

This version of generator() for C++ is based on the bright idea of Simon Tatham - "coroutines in C". In particular, on the idea of using switch/case for this implementation.

Declaring a Generator

To declare a generator, you will use $generator, $yield, $emit, and $stop "keywords" that are macro definitions in fact.

And here is a typical implementation of a generator that emits numbers from 10 to 1 in descending order:

C++

include "generator.h"

$generator(descent)
{
   // place for all variables used in the generator
   int i; // our counter

   // place the constructor of our generator, e.g. 
   // descent(int minv, int maxv) {...}
   
   // from $emit to $stop is a body of our generator:
    
   $emit(int) // will emit int values. Start of body of the generator.
      for (i = 10; i > 0; --i)
         $yield(i); // a.k.a. yield in Python,
                    // returns next number in [1..10], reversed.
   $stop; // stop, end of sequence. End of body of the generator.
};

Having such a descending generator declared, we will use it as:

C++

int main(int argc, char* argv[])
{
  descent gen;
  for(int n; gen(n);) // "get next" generator invocation
    printf("next number is %d\n", n);
  return 0;
}

The gen(n) thing is in fact an invocation of the bool operator()(int& v) method defined "under the hood" of our generator object. It returns true if the parameter v was set, and false if our generator cannot provide more elements - was stopped.

As you may see, for(int n; gen(n);) looks close enough to the construction for(var n in gen) used in JavaScript for exactly the same purpose. Expressiveness is the beauty of the approach.

generator.h

And here is the source code of the generator implementation:

C++

#ifndef __generator_h__
#define __generator_h__

// generator/continuation for C++
// author: Andrew Fedoniouk @ terrainformatica.com
// idea borrowed from: "coroutines in C" Simon Tatham,
//   http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html

class _generator
{
protected:
  int _line;
public:
  _generator():_line(0) {}
};

#define $generator(NAME) struct NAME : public _generator

#define $emit(T) bool operator()(T& _rv) { \
                    switch(_line) { case 0:;

#define $stop  } _line = 0; return false; }

#define $yield(V)     \
        do {\
            _line=__LINE__;\
            _rv = (V); return true; case __LINE__:;\
        } while (0)
#endif

That is a bit cryptic, but if you would read the original article of Simon Tatham, then you will get an idea of what is going on here.

Limitations of the Approach

One obvious limitation - $yield cannot be placed inside a switch as $emit() declares a switch by itself.

History

This approach of making generators in C++ was originally published in two articles in my blog:

License

This article, along with any associated source code and files, is licensed under The BSD License

Written By

c-smile

Founder Terra Informatica Software

Canada

Andrew Fedoniouk.

MS in Physics and Applied Mathematics.
Designing software applications and systems since 1991.

W3C HTML5 Working Group, Invited Expert.

Terra Informatica Software, Inc.
http://terrainformatica.com

// Headers necessary for this example #include <iostream> #include <string> // My generator base class #include <type_traits> #include <iterator> template <typename T> class Generator { public: class Result: public std::iterator<std::forward_iterator_tag,T> { public: Result( Generator* g): m_g(g) {} T& operator *() { return m_g->m_t;} Result& operator++() { m_g->Proceed(); return *this;} static Result& End() { static Result r(0); return r;} bool operator!= (const Result& rhs) { return m_g->NotDone();} private: Generator* m_g; }; friend class Result; Generator(const T& t) : m_t(t), m_r(this) {} virtual Result& begin() { return m_r;} Result& end() { return m_r.End();} protected: virtual void Proceed() = 0; virtual bool NotDone() = 0; typename std::remove_const<T>::type m_t; Result m_r; }; // An inheritor generating numerics // (similar to the original article) class MyGenI :public Generator<int> { public: MyGenI( int i) : Generator<int>(i) {} virtual void Proceed() { --m_t;} virtual bool NotDone() { return m_t>-5;} }; // An inheritor modifying a string class MyGenS :public Generator<std::string> { public: MyGenS(const std::string& s) : Generator<std::string>(s) {} virtual void Proceed() { m_t += m_t[cntr]+1; ++cntr;} virtual bool NotDone() { return cntr < 10;} private: int cntr = 0; }; // An inheritor generating a string from console input class MyGenC :public Generator<std::string> { public: MyGenC(std::string s) : Generator<std::string>(s) {} virtual void Proceed() { std::cin >> m_c; m_t += m_c; } virtual bool NotDone() { return !std::cin.fail();} virtual Result& begin() { if ( m_t.empty()) { std::cin >> m_c; m_t += m_c; } return m_r; } private: char m_c; }; // The test int main(int argc, char* argv[]) { std::cout << "numeric\n"; auto genI = MyGenI{5}; for(auto i: genI) std::cout << "next value is " << i << std::endl; std::cout << "\nstring\n"; auto genS = MyGenS{"a"}; for(auto s: genS) std::cout << "next value is " << s << std::endl; std::cout << "\nconsole\n"; auto genC = MyGenC{""}; for(auto s: genC) std::cout << "next value is " << s << std::endl; return 0; }

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.