Click here to Skip to main content
Click here to Skip to main content
Go to top

Generators in C++

, 20 Sep 2008
Rate this:
Please Sign up or sign in to vote.
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:

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:

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:

#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

struct _generator
{
  int _line;
  _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

Share

About the Author

c-smile
Founder Terra Informatica Software
Canada 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

Comments and Discussions

 
GeneralMy vote of 5 Pinmemberenobayram11-Nov-12 23:13 
QuestionWhat's the use? PinmemberRoland Pibinger21-Sep-08 1:32 
AnswerRe: What's the use? Pinmemberc-smile21-Sep-08 7:47 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

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

| Advertise | Privacy | Mobile
Web03 | 2.8.140916.1 | Last Updated 21 Sep 2008
Article Copyright 2008 by c-smile
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid