How do you implement Coroutines in C++

Yes it can be done without a problem. All you need is a little assembly code to move the call stack to a newly allocated stack on the heap.

I would look at the boost::coroutine library.

The one thing that you should watch out for is a stack overflow. On most operating systems overflowing the stack will cause a segfault because virtual memory page is not mapped. However if you allocate the stack on the heap you don't get any guarantee. Just keep that in mind.

On POSIX, you can use makecontext()/swapcontext() routines to portably switch execution contexts. On Windows, you can use the fiber API. Otherwise, all you need is a bit of glue assembly code that switches the machine context. I have implemented coroutines both with ASM (for AMD64) and with swapcontext(); neither is very hard.

You might be better off with an iterator than a coroutine if possible. That way you can keep calling next() to get the next value, but you can keep your state as member variables instead of local variables.

It might make things more maintainable. Another C++ developer might not immediately understand the coroutine whereas they might be more familiar with an iterator.

Does COROUTINE a portable C++ library for coroutine sequencing point you in the right direction? It seems like an elegant solution that has lasted the test of time.....it's 9 years old!

In the DOC folder is a pdf of the paper A Portable C++ Library for Coroutine Sequencing by Keld Helsgaun which describes the library and provides short examples using it.

[update] I'm actually making successful use of it myself. Curiosity got the better of me, so I looked into this solution, and found it was a good fit for a problem I've been working on for some time!

I dont think there are many full-blown, clean implementations in C++. One try that I like is Adam Dunkels' protothread library.

See also Protothreads: simplifying event-driven programming of memory-constrained embedded systems in the ACM Digital Library and discussion in Wikipedia topic Protothread,

Based on macros as well (Duff's device, fully portable, see http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html ) and inspired by the link posted by Mark, the following emulates co-processes collaborating using events as synchronization mechanism (slightly different model than the traditional co-routines/generator style)

// Coprocess.h
#pragma once
#include <vector>

class Coprocess {
  public:
    Coprocess() : line_(0) {}
    void start() { line_ =  0; run(); }
    void end()   { line_ = -1; on_end(); }
    virtual void run() = 0;
    virtual void on_end() {}; 
  protected:
    int line_;
};

class Event {
  public:
    Event() : curr_(0) {}

    void wait(Coprocess* p) { waiters_[curr_].push_back(p); }

    void notify() {
        Waiters& old = waiters_[curr_];
        curr_ = 1 - curr_; // move to next ping/pong set of waiters
        waiters_[curr_].clear();
        for (Waiters::const_iterator I=old.begin(), E=old.end(); I != E; ++I)
            (*I)->run();
    }   
  private:
    typedef std::vector<Coprocess*> Waiters;
    int curr_;
    Waiters waiters_[2];
};

#define corun()   run() { switch(line_) { case 0:
#define cowait(e) line_=__LINE__; e.wait(this); return; case __LINE__:
#define coend     default:; }} void on_end()

An example of use:

// main.cpp
#include "Coprocess.h"
#include <iostream>

Event e;
long sum=0;

struct Fa : public Coprocess {
    int n, i;
    Fa(int x=1) : n(x) {}
    void corun() {
        std::cout << i << " starts\n";
        for (i=0; ; i+=n) {
            cowait(e);
            sum += i;
        }
    } coend {
        std::cout << n << " ended " << i << std::endl;
    }   
};

int main() {
    // create 2 collaborating processes
    Fa f1(5);
    Fa f2(10);

    // start them
    f1.start();
    f2.start();
    for (int k=0; k<=100; k++) { 
        e.notify();
    }   
    // optional (only if need to restart them)
    f1.end();
    f2.end();

    f1.start(); // coprocesses can be restarted
    std::cout << "sum " << sum << "\n";
    return 0;
}

WvCont is a part of WvStreams that implements so-called semi-coroutines. These are a little easier to handle than full-on coroutines: you call into it, and it yields back to the person who called it.

It's implemented using the more flexible WvTask, which supports full-on coroutines; you can find it in the same library.

Works on win32 and Linux, at least, and probably any other Unix system.

You should always consider using threads instead; especially in modern hardware. If you have work that can be logically separated in Co-routines, using threads means the work might actually be done concurrently, by separate execution units (processor cores).

But, maybe you do want to use coroutines, perhaps because you have an well tested algorithm that has already been written and tested that way, or because you are porting code written that way.

If you work within Windows, you should take a look at fibers. Fibers will give you a coroutine-like framework with support from the OS.

I am not familiar with other OS's to recommend alternatives there.