Expression-based callbacks

Introduction

In most cases where collections are used, the need to iterate over a collection, do a computation, and collect the results in a variable, arises often. This article shows an easy way to do this in C++, different from the most common approach, using containers together with expression templates. The article will use STL, but the technique can be applied to any container.

The common approach

The most usual approach to iteration over a collection is to use a for-loop. Writing for loops becomes tedious after a while, therefore many languages offer a 'for-each' statement that allows iteration over a collection. While C++ does not offer such a statement, it is very easy to implement it in various ways. The most common approach is to make a for-loop in a function that accepts a callback, like this:

template <class C> void forEach(C &c, 
            void (*callback)(C::value_type)) {
    for(C::iterator it = c.begin(); 
                    it != c.end(); ++it) {
        callback(*it);
    }
}

But this approach has some disadvantages; it interrupts the thought process of the programmer by making him/her think about where to place the callback, and also how to access the local data from inside the callback.

Expression templates

Expression templates come as a rescue: by using operator overloading, classes that represent an expression bound to local arguments can be used as a callback to a for-each loop. Before explaining how to code such classes, let's see an example of usage:

#include <list>
#include <iostream>
using namespace std;

int main()
{
    list<int> l;
    
    l.push_back(1);
    l.push_back(2);
    l.push_back(3);
    
    int i = 0;
    Expr< int > x;
    forEach(l, i, x += i);
    cout << x;
    getchar();
    return 0;
}

As you can see, it is much easier to sum a list of numbers using the above code!

How it works

Here is the important line of code; let's focus on it:

forEach(l, i, x += i);

C++ does not have lambda functions or closures, but it has operator overloading. So in the above code, x is an object that when operator += is applied to it, it does not actually add anything, but it creates a function object that encapsulates the variables x and i, and when invoked, it will perform the action.

The class Expr that x is an instance of is:

template <class T> class Expr {
public:
    Expr() : m_v(T()) {
    }

    ExprAddAssign<T> operator += (T &i) {
        return ExprAddAssign<T>(m_v, i);
    }
    
    operator T () const {
        return m_v;
    }
    
private:
    T m_v;    
};

We can see that it encapsulates a value of type T. We also see that operator += returns an instance of class ExprAddAssign, which is this class:

template <class T> class ExprAddAssign {
public:
    ExprAddAssign(T &lv, const T &rv) : 
                  m_lv(lv), m_rv(rv) {
    }
    
    void operator ()() const {
        m_lv += m_rv;
    }

private:
    T &m_lv;
    const T &m_rv;
};

The above class contains two bindings: one for the rvalue and one for the lvalue. The lvalue is assigned the value of rvalue. The code for the function 'forEach' becomes:

template <class C, class T, class F> 
         void forEach(const C &c, T &v, F &obj) {
    for(C::const_iterator it = c.begin(); 
                          it != c.end(); ++it) {
        v = *it;
        obj();
    }
}

Conclusion

A wide variety of expression templates can be programmed. Even constructs like if-then-else can be coded using a Smalltalk like syntax. Example:

forEach(l, (i > 2).ifTrue(x += i));

I actually accidentally came up with this solution, searching for a way to make lambda functions in C++. I realized that one does not need lambda functions, as long as lambda parameters can be declared as local variables.

I am surprised that the STL library does not contain such a set of classes. It would offer great power to C++...