Generators in C++
Generators are iterators over things made up on runtime. For example if you ask me about the Fibonacci sequence, I can generate an infinite amount of them by only remembering the two numbers before:
Generators are quite useful for programming. Python has them, Haskell is basically build around them (I think they call them infinite lists). Generating the Fibonacci sequence up to a maximum number maxn looks like this in Python:
def fib(maxn):
n, ln = 1, 1
while n < maxn:
yield n
n, ln = ln, n + ln
for i in fib(1000):
print i,
After my last blog post about C++0x features, I was intrigued to write something similar in C++. The corresponding main function also looks very nice with the new container iterate feature:
#include <iostream>
int main(int, char argv**)
{
FibonacciGenerator k(1000);
for(auto i : k)
std::cout << i << " ";
std::cout << std::endl;
return 0;
}
So basically, we have a container here called FibonacciGenerator and we iterate over it with the new container iterate feature. For this to work, we have to implement the begin() and end() functions in the container and the values those functions return must implement operator++, operator* and operator!=. This goes something like this:
class FibonacciGenerator {
private:
struct generator {
generator(int n) : _n {n}, _ln{0} {}
int & operator*() {
return _n;
}
bool operator!=(const generator & other) const {
return _n <= other._n;
}
generator& operator++() {
int temp = _ln + _n;
_ln = _n;
_n = temp;
return *this;
}
private:
int _n, _ln;
};
public:
FibonacciGenerator(int maxn) : _maxn{maxn} {}
generator begin() const {
return generator(1);
}
generator end() const {
return generator(_maxn);
}
private:
int _maxn;
};
The implementation is quite straightforward: All the (not very heavy) lifting is done in the generator. The inequality compare checks if the current number is bigger than the one of the other iterator. If this becomes true, the loop in main will terminate. The dereference operator returns the current number and the increment operator calculates the next. The container itself only contains the begin and end function which are called by the container iterate syntactic sugar.
Note that generators are nothing new. You can write them in exactly the same way in C++03. But somehow, the new Pythonic container iterate feature triggered me for the first time to think about them in C++.