Aliasing pointers: using "weakness" to strengthen your code

In one of my earlier articles introducing programming with Boost libraries, I had demonstrated some simple techniques using boost::shared_ptr to share dynamically allocated object instances across scopes, and manage the life cycle of such objects effectively. This was an important step in the direction of eliminating memory leaks. But this was not a complete answer to all forms of memory leaks. This article helps you distinguish between "owning" and "aliasing" semantics for pointers and introduces another class from Boost's smart pointer stable - the boost::weak_ptr. Although not a smart pointer itself, the weak_ptr adds important capability that is vital in handling memory issues and thread safety of objects.

Imagine that you are building a linked list, and you decide to store the "head" node as a shared_ptr<Node> and encapsulate inside this node, the life cycle management of all the nodes in the entire list. That way, when the "head" node goes out of scope, all the other nodes are automatically deleted. How can you do it? Well, the head pointer stores a shared_ptr<Node> pointing to the first node, the first node stores a shared_ptr<Node> pointing to the second node, and so on.

Here is the code, and it works.

#include <iostream>
#include <boost/shared_ptr.hpp>

using std::cout;
using std::endl;
using boost::shared_ptr;

struct Node {
    int n_;
    shared_ptr<Node> next;

    Node(int n = 0) : n_(n) {
    }

    ~Node() {
        cout << "~Node() invoked for " << n_ << endl;
    }
};

shared_ptr<Node> getList() {
    shared_ptr<Node> head( new Node(0) );
    shared_ptr<Node> next1( new Node(1) );
    shared_ptr<Node> next2( new Node(2) );

    head->next = next1;
    next1->next = next2;

    return head;
}

int main() {
    shared_ptr<Node> head = getList();
    if ( head )
        cout << "Got head" << endl;

    return 0;
}

This works remarkably well, and by now your penchant for using shared_ptr and RAII is seeing you write elegant code and wish away memory leaks. And then you are asked to enhance your linked list to a doubly linked list. With a deft, touch you make the necessary changes - and you are up and running again ...

#include <iostream>
#include <boost/shared_ptr.hpp>

using std::cout;
using std::endl;
using boost::shared_ptr;

struct Node {
    int n_;
    shared_ptr<Node> next;
    shared_ptr<Node> prev;

    Node(int n = 0) : n_(n) {
    }

    ~Node() {
        cout << "~Node() invoked for " << n_ << endl;
    }
};

shared_ptr<Node> getList() {
    shared_ptr<Node> head( new Node(0) );
    shared_ptr<Node> next1( new Node(1) );
    shared_ptr<Node> next2( new Node(2) );

    head->next = next1;
    next1->next = next2;
    next1->prev = head;
    next2->prev = next1;

    return head;
}

int main() {
    shared_ptr<Node> head = getList();
    if ( head )
        cout << "Got head" << endl;

    return 0;
}

... except that you have a memory leak. Believe it or not, what I promised a couple of articles ago was a fib - you can leak memory without even so much as nibbling on a pointer, and in spite of having wrapped all your heap memory in shared_ptr. Run it and you'll not see any of the messages from the destructor of Node. Come to think of it and you'll know the reason.

In the function getList, initially, the nodes head, next1 and next2 each have a reference count of 1 (at line 22, 23 and 24 respectively). Next at line 26, next1 has its ref-count bumped up to 2. In the following line 27, next2 has its ref-count bumped up to 2. So far so good - the real fun starts now. In the next line 28, head has its ref-count bumped to 2, and finally next1 has its ref-count bumped to 3. When this function returns, each of the Smart pointers have their reference counts decreased by 1. But head is copied as a return value - so the decrement nullifies, and when we reach main function at line 35, its reference count remains 2. At this point, the reference count of next1 and next2 are 2 and 1 respectively - but these objects are no longer in scope - completely encapsulated by head. At the end of the main function's scope, the ref-count of head will drop back a notch to 1 - it will not get to 0 - necessary for its internal pointer to get "destructed" and trigger the destruction of its subsequent nodes.

What caused the problem? We only introduced three lines of code - lines 11, 28 and 29 - so the problem would have to be here in these three lines.

Why did all hell break lose? Because, we used the shared_ptr indiscriminately. The shared_ptr implements a "shared ownership" idiom. In this case, head "owns" the next1 node - meaning that before head is completely "destructed", it would have ensured complete "destruction" of next1. But next1 does not own head - it only has an alias to head, in the form of the member prev. But by making it into a shared_ptr<Node>, we have unwittingly made next1 the owner of head. So we hit the chicken-and-egg problem. To reiterate what we just said about ownership semantics - before head is completely "destructed", it should ensure complete "destruction" of next1, and before next1 is completely "destructed", it should ensure complete "destruction" of head. Of course that's an impossible scenario. So we need a different construct for handling the semantics of an aliasing pointer. Here is the code example again with some changes that work reasonably well.

#include <iostream>
#include <boost/shared_ptr.hpp>

using std::cout;
using std::endl;
using boost::shared_ptr;

struct Node {
    int n_;
    shared_ptr<Node> next;
    shared_ptr<Node> *prev;

    Node(int n = 0) : n_(n) {
    }

    ~Node() {
        cout << "~Node() invoked for " << n_ << endl;
    }
};

shared_ptr<Node> getList() {
    shared_ptr<Node> head( new Node(0) );
    shared_ptr<Node> next1( new Node(1) );
    shared_ptr<Node> next2( new Node(2) );

    head->next = next1;
    next1->next = next2;
    next1->prev = &head;
    next2->prev = &next1;

    return head;
}

int main() {
    shared_ptr<Node> head = getList();
    if ( head )
        cout << "Got head" << endl;

    return 0;
}

At this point of time, you decide to remove the first node of the list head. As part of the process, you must do something like this:

int main() {
    shared_ptr<Node> new_head;
    {
        shared_ptr<Node> head = getList();
        new_head = head->next;
        new_head->prev = 0;
    }

    return 0;
}

The statement at line 6, is crucial because if prev is not set to 0 at this point, an accidental dereferencing of new_head->prev at a later point in the code will bomb. At the end of the scope, at line 7, the head goes out of scope and is "destructed". What if this automatically set the prev member pointing to it to be NULL. Then we could afford to forget to write new_head->prev = 0, without facing any dire consquences.

The boost::weak_ptr is tailor-made for the purpose shown here - it models a "non-owning alias" which is automatically set to a null state when the object it points to is destructed. For this, weak_ptr always works in conjunction with a shared_ptr, and always points to an object via the shared_ptr that owns it. The following example should make all this clear:

#include <boost/shared_ptr.hpp>
#include <boost/weak_ptr.hpp>

using std::cout;
using std::endl;
using boost::shared_ptr;
using boost::weak_ptr;

struct Node {
    int n_;
    shared_ptr<Node> next;
    weak_ptr<Node> prev;

    Node(int n = 0) : n_(n) {
    }

    ~Node() {
        cout << "~Node() invoked for " << n_ << endl;
    }
};

shared_ptr<Node> getList() {
    shared_ptr<Node> head( new Node(0) );
    shared_ptr<Node> next1( new Node(1) );
    shared_ptr<Node> next2( new Node(2) );

    head->next = next1;
    next1->next = next2;
    next1->prev = head;
    next2->prev = next1;

    return head;
}

int main() {
    shared_ptr<Node> head = getList();
    if ( head )
        cout << "Got head" << endl;

    return 0;
}

The weak_ptr maintains a reference to a shared_ptr owning the object. But it does not bump the reference count of a shared_ptr - therefore any number of weak_ptr's can point to a shared_ptr, without affecting its life cycle in anyway. If the shared_ptr goes out of scope and the underlying object is destructed - the weak_ptr's are automatically "updated" about this change through the reference to the shared_ptr that it maintains.

In an informal way, weak_ptr's are to shared_ptr's, what soft links are to hard links on a Unix file system.

You can check the state of the underlying object through the weak_ptr, using the weak_ptr::expired() member function. You can also construct an owning reference - a shared_ptr which contributes to the reference count of the original shared_ptr - through the weak_ptr::lock() member function. This can indirectly be used to check the same condition as weak_ptr::expired() does. To understand that - look at the final example here:

#include <iostream>
#include <boost/shared_ptr.hpp>
#include <boost/weak_ptr.hpp>

using std::cout;
using std::endl;
using boost::shared_ptr;
using boost::weak_ptr;

struct Node {
    int n_;
    shared_ptr<Node> next;
    weak_ptr<Node> prev;

    Node(int n = 0) : n_(n) {
    }

    ~Node() {
        cout << "~Node() invoked for " << n_ << endl;
    }
};

shared_ptr<Node> getList() {
    shared_ptr<Node> head( new Node(0) );
    shared_ptr<Node> next1( new Node(1) );
    shared_ptr<Node> next2( new Node(2) );

    head->next = next1;
    next1->next = next2;
    next1->prev = head;
    next2->prev = next1;

    return head;
}

int main() {
    shared_ptr<Node> new_head;
    weak_ptr<Node> alias;
    {
        shared_ptr<Node> head = getList();
        new_head = head->next;
        alias = head;
    }

    assert(alias.expired());

    alias = new_head;
    shared_ptr<Node> new_head2 = alias.lock();
    assert(new_head2.use_count() == 2); // because new_head and new_head2 share ownership

    return 0;
}

The lock method is particularly crucial when sharing an object across threads. Some threads might only have an aliasing reference to the shared object in the form of a weak_ptr. This can be used to great effect. At any time when such a thread needs to share ownership of this object - it can call lock on the weak_ptr. It will get a non-null shared_ptr only if the object is still valid, and otherwise it will get a null shared_ptr.

Notice that the weak_ptr provides no ways of dereferencing the underlying pointer through it. So there are no overloaded -> or * operators for example. If you need to use these operators - use the lock method to try and get a shared_ptr and then apply these methods on the shared_ptr. In fact - a weak_ptr is not a smart pointer - I call it a "smarter" pointer.
Read more!

Expression Templates Demystified: Part 2

In this article, we would see how the use of templates can simplify and generalize the Expression Functors code, and improve performance by eliminating virtual functions.

In the example from the previous segment of this article, the Expression abstract base class represented the family of all types that could be used to represent different kinds of expressions. Two specific classes, Variable and Constant, represented the leafs of an expression tree - numeric literals and single variable names. These could be combined to form other expressions - generally represented by the ComplexExpression class. All these classes implemented the interface defined by the Expression abstract base class.

We now plan to switch from dynamic polymorphism to template driven static polymorphism. For example, given classes with a common interface but without a common base class, like the ones below:

Hide line numbersShow line numbers

    1 struct Foo {
    2     void bar() {
    3         // implementation
    4     }
    5 };
    6 
    7 struct Foo2 {
    8     void bar() {
    9         // implementation
   10     }
   11 };

we can wrap them using a class template that has a similar interface as these:

Hide line numbersShow line numbers

    1 template<class F>
    2 struct AllFoo {
    3     AllFoo(F& f) : f_(f) {}
    4 
    5     void bar() {
    6         f_.bar();
    7     }
    8 };

This enforces that AllFoo can only be instantiated with such classes which have the bar() method in their public interface. Thus we write the following alternate definitions:

Hide line numbersShow line numbers

    1 template<class E>
    2 struct Expr {
    3     Expr(E& e) : e_(e) {
    4     }
    5 
    6     double operator() (double d) {
    7         return e_(d);
    8     }
    9 
   10     E e_;
   11 };

Here Expr is a class that can encapsulate all expression objects, like the ones of type Constant or Variable below.

Hide line numbersShow line numbers

    1 struct Constant {
    2     Constant(double d) : d_(d) { }
    3     Constant(int d) : d_(d) { }
    4     double operator() (double) {
    5         return d_;
    6     }
    7 
    8     double d_;
    9 };
   10 
   11 
   12 struct Variable {
   13     double operator() (double d) {
   14         return d;
   15     }
   16 };

Finally, a class to represent non-terminal, complex expressions:

Hide line numbersShow line numbers

    1 template<class E1, class E2, class Op>
    2 struct ComplexExpr {
    3     ComplexExpr(Expr<E1> l, Expr<E2> r) : l_(l), r_(r) {
    4     }
    5 
    6     double operator() (double d) {
    7         return Op::apply(l_(d), r_(d));
    8     }
    9 
   10     Expr<E1> l_;
   11     Expr<E2> r_;
   12 };

We have just carried over the definition of the ComplexExpression class from the previous article and made it into a template class. The operator classes like Add, Subtract, Multiply and Divide should continue to work unchanged. Guess what, we just have to define the operator overloads (for +, -, * and /) and we will be done with defining our framework of algebraic expression.

Now, we would want to write expressions such as:

Variable x;
cout << (x+3)(2); // prints 5
cout << ((x*x+3)*(x+3))(2); // prints 35

In the above, x is a Variable, 3 should generate a Constant, x + 3 should result in a ComplexExpr<Variable, Constant>. Further, x*x is a ComplexExpr<Variable, Variable> and (x*x+3)*(x+3) is a ComplexExpr<ComplexExpr< ComplexExpr<Variable, Variable>, Constant>, ComplexExpr<Variable, Constant> >. One can trace the template parameter types as sub-trees of the class template ComplexExpression.

Clearly, to write an expression like x+3, we need an overload of operator+ between a Variable and an integer. To write an expression like (x*x+3)*(x+3) - we need an operator* between two ComplexExpressions. To write something like, x+Constant(3), we need an overload of operator+ between Variable and Constant. Now, just as we defined the basic operators on Expression in the previous article, we could do the same on the Expr class template here, instead of overloading each operator for different combinations of types. For example:

Hide line numbersShow line numbers

    1 template<class E1, class E2>
    2 Expr<ComplexExpr<Expr<E1>, Expr<E2>, Add> > operator+ (E1 e1, E2 e2) {
    3     typedef ComplexExpr<Expr<E1>, Expr<E2>, Add> ExprType;
    4     return Expr<ExprType>( ExprType(Expr<E1>(e1), Expr<E2>(e2)) );
    5 }

The other operators are not very difficult to write, following the above code. However, turns out that while these do take care of operators between complex expressions as well as Variables and Constants, they cannot handle real number or integer literals. To handle real number literals, we define the following overload pairs for each operator.

Hide line numbersShow line numbers

    1 template<class E1>
    2 Expr<ComplexExpr<Expr<E1>, Expr<Constant>, Multiply> > operator* (E1 e1, double d) {
    3     typedef ComplexExpr<Expr<E1>, Expr<Constant>, Multiply> ExprType;
    4     return Expr<ExprType>( ExprType(Expr<E1>(e1), Expr<Constant>(Constant(d))) );
    5 }
    6 
    7 template<class E1>
    8 Expr<ComplexExpr<Expr<Constant>, Expr<E1>, Multiply> > operator* (double d, E1 e1) {
    9     typedef ComplexExpr<Expr<Constant>, Expr<E1>, Multiply> ExprType;
   10     return Expr<ExprType>( ExprType(Expr<Constant>(Constant(d)), Expr<E1>(e1)) );
   11 }

These take care of all cases - except for a small glitch which we can pepare to live with. We can write such expressions as:

Variable x;
cout << (x+3.0)(2); // prints 5
cout << ((x*x+3.0)*(x+3.0))(2); // prints 35

but not ones like:

Variable x;
cout << (x+3)(2); // prints 5
cout << ((x*x+3)*(x+3))(2); // prints 35

If you have to be able to do this, add additional overloads like:

Hide line numbersShow line numbers

    1 template<class E1>
    2 Expr<ComplexExpr<Expr<E1>, Expr<Constant>, Multiply> > operator* (E1 e1, int d) {
    3     typedef ComplexExpr<Expr<E1>, Expr<Constant>, Multiply> ExprType;
    4     return Expr<ExprType>( ExprType(Expr<E1>(e1), Expr<Constant>(Constant(d))) );
    5 }
    6 
    7 template<class E1>
    8 Expr<ComplexExpr<Expr<Constant>, Expr<E1>, Multiply> > operator* (int d, E1 e1) {
    9     typedef ComplexExpr<Expr<Constant>, Expr<E1>, Multiply> ExprType;
   10     return Expr<ExprType>( ExprType(Expr<Constant>(Constant(d)), Expr<E1>(e1)) );
   11 }

As it should be already apparent - there are no objects allocated on free store, no reference counted proxy wrappers, and a fair bit of compile-time type computation and call dispatching - this results in significant savings in the runtime costs of the program, apart from the obvious cut in the number of lines of code. The basic philosophy of the template based program has not changed from the non-template version - it uses functional composition involving the function call operator, and operator overloading to support naturally combining simple expressions into arbitrarily complex expressions. However, the use of templates allows a fair bit of this work to be done at compile time. This is all that is there to Expression templates. You can put together the expression framework using code given here and use the following function to test your code.

Hide line numbersShow line numbers

    1 int main()
    2 {
    3     Variable x;
    4 
    5     cout << ((2.0*x*x + 3.0*x + 3.0)*(2.0*x*x + 3.0*x + 3.0))(2) << endl;
    6     cout << integrate((2.0*x*x + 3.0*x + 3.0), 0, 1) << endl;
    7     cout << integrate((2.0*x*x + 3.0*x + 3.0)*(2.0*x*x + 3.0*x + 3.0), 0, 1) << endl;
    8     cout << integrate((x/(1.0+x)), 0, 1) << endl;
    9     cout << integrate(x*x, 0, 7) << endl;
   10 
   11     return 0;
   12 }
   13 

If you have any trouble understanding and compiling the code, drop me a message.

References

1. Todd Veldhuizen: Expression Templates
   http://ubiety.uwaterloo.ca/~tveldhui/papers/Expression-Templates/exprtmpl.html
   
2. Expression Templates synopsis on More C++ Idioms
   http://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Expression-template
   
3. Angelika Langer: Expression Templates - Introduction
   http://www.angelikalanger.com/Articles/Cuj/ExpressionTemplates/ExpressionTemplates.htm

Read more!

Expression Templates Demystified

Often in course of our programming work, we want to be able to modify or customize part of a function’s logic at the point of invocation. A very simple example is the C++ STL algorithm std::find_if.

template<class InputIterator, class Predicate>
InputIterator find_if (InputIterator first, InputIterator last, Predicate pred)

Here Predicate represents a functor (an object that overloads the function-call operator). In this particular case, the functor should take an element of the container of which first and last are iterators, and return a boolean truth value based on some criteria, possibly as a function of the element passed.

Using find_if, one can find all elements in a container, that meet a particular criteria. What’s remarkable is that, what find_if identifies as matching elements in the container is entirely dependent on the logic encoded in the Predicate functor – not on find_if’s implementation. This makes the functionality of find_if open-ended. What we are able to achieve in the process is a form of polymorphism with a very high degree of type-safety and performance. There is a specific name for such idioms – functional composition. In fact, by combining an arbitrary number of Functors with varied functionality, we can construct a fairly complex piece of functionality. This has a very useful application in developing mini-languages (also called DSELs or Domain Specific Embedded Languages - expressions with a syntactic form alien to C++ syntax, being embedded inside C++ programs as valid code. In this article and the next in this series, we look at the powerful technique called Expression Templates which helps solve these classes of problems.

We have all learned in high school Calculus course about such functions of single variable as:

F(x) = x^3 + 3x - 7

or

G(x) = x.sin x + 6

Representing such simple algebraic functions using functors is not a big hassle. For example, to represent G(x), one could write a functor like the one below:

Hide line numbersShow line numbers

    1 Struct FuncG {
    2     double operator(double x) {
    3         return (x*sin(x) + 6) ;
    4     }
    5 }

Imagine you have a Calculus library written in C++ and you have a function called integrate, that is defined as follows:

Hide line numbersShow line numbers

    1 template<class Func>
    2 double integrate(Func f, double low, double high, double epsilon = 0.001) {
    3     assert(low <= high );
    4     double auc1 = 0, auc2 = 0;
    5     double running_x = low;
    6     while ( running_x < high ) {
    7         auc1 += f(running_x) * epsilon;
    8         running_x += epsilon;
    9         auc2 += f(running_x) * epsilon;
   10     }
   11
   12     return (auc1 + auc2)/2;
   13 }

This is essentially an area under the curve calculation that takes the average of upper bound and lower bound sums.

Now here is the deal: in course of a mathematical programming one could need to integrate dozens of such mathematical expressions. If there are 50 different expressions to be integrated, a program needs to define 50 different functors – and this is where the efficiency and ease of the system breaks down.

Imagine being able to define function objects that can evaluate arbitrary mathematical expressions and being able to pass such expressions to functions like integrate. Something like the following:

Hide line numbersShow line numbers

    1 MathFunction f = x*x + 2*x + 3;
    2 double d = integrate(f, 0, 2);
    3 f = x*x*sin*sin + 2*x*cos*sin + cos*cos;
    4 const double PI = 3.1415926535897;
    5 d = f(PI/2);

This almost looks like magic, doesn’t it – but it isn’t. The complex algebraic expression can, in each case, be engineered to give a functor which evaluates the expression for different values of the function argument. The standard technique or idiom used for enabling such expression building is known as Expression Templates and it is the focus area of this article. But, Expression Templates have a notorious reputation of being difficult to understand and learn and turned off many a learner. Therefore, we would try to build the logic of constructing such expressions intuitively, bit by bit. We will start off with a completely non-template version of the code – an idiom that I discovered for myself and which I call Expression Functor. We would then ‘deduce’ the Expression Template idiom as a special case of this idiom which achieves phenomenal performance improvements and code improvement, using templates.

So here we go.

Breaking down the problem

Let us first break the problem into its basic elements. We begin with a simple polynomial expression:

f(x) = x + 3

Such an expression has two kinds of entities – a variable (x) and a constant (the literal 3). Both these entities are valid expressions by themselves. For example, the straight line going parallel to the x-axis at a distance of 3 units above x-axis is represented by the function f(x) = 3. Similarly, the straight line going through the origin at an angle of 45 degrees to both x and y axes is represented by the function f(x) = x. Modelling these most trivial functions will be our building blocks for non-trivial expression building.

Consider the case of the horizontal line – f(x) = 3. We want to model a function which takes any value of x and always returns 3. The basic function would be:

Hide line numbersShow line numbers

    1 double f(double x) {
    2     return 3;
    3 }

We want this to become an applicative functor like this:

Hide line numbersShow line numbers

    1 struct C3 {
    2     double operator() (double) {
    3         return 3;
    4     }
    5 };

C3 above represents the function f(x) = 3. Now we want to generalize this function to represent any real number – this is fairly straight-forward:

Hide line numbersShow line numbers

    1 struct Constant {
    2     Constant(const double& d) : d_(d) {
    3     }
    4
    5     double operator() (double) {
    6         return d_;
    7     }
    8
    9     const double d_;
   10 };

Such a functor can be used to model any constant expression. C3 would now be equivalent to Constant(3).

Next, let’s try to model the 45 degree straight line through the origin – f(x) = x. Turns out that this is even easier – "given any value x, return that very value" should summarize our function. In short:

Hide line numbersShow line numbers

    1 struct Variable {
    2     double operator() (double x) {
    3         return x;
    4     }
    5 };

These two classes are remarkable on their own, but what happens when we try to model a function like:

f(x) = x+3

What type will be x + 3 – it is not Constant, and it is not an independent variable like Variable either. So we possibly need another class to represent more complex expressions. Come to think of it. Both a Constant and a Variable are each, in themselves, an expression, and so is a more generic expression like x+3. So it would seem logical that we should have an Expression base class of which, Constant, Variable and other Expression classes can be derived classes. We define it like this:

Hide line numbersShow line numbers

    1 struct Expression {
    2     virtual double operator() (double) = 0;
    3     virtual Expression* clone() = 0;
    4     virtual ~Expression() {
    5     }
    6 };

There is a reason for the curious looking Expression* clone() virtual function. I have included this with the benefit of contrived foresight - having implemented this whole solution already. Without getting ahead of the story, let me tell you that it plays a small but important role in the life cycle management of Expressions. It is used to copy Expressions where needed.

Hide line numbersShow line numbers

    1 struct Constant : Expression {
    2     ...
    3     Expression* clone() {
    4         return new Constant(*this);
    5     }
    6 };
    7
    8 struct Variable : Expression {
    9     ...
   10     Expression* clone() {
   11         return new Variable(*this);
   12     }
   13 };

We would refer to Expressions like Constant and variable as simple expressions. We also need to define a sub-type of Expression to represent all non-trivial (i.e. other than simple) expressions. But before that can happen, we need to understand how multiple expressions can be combined using arithmetic operators. For example, we want to be able to write such expressions as:

Hide line numbersShow line numbers

    1 Variable x;
    2 Expression& e = x*x + 2*x + 1;
    3 double d = e(5);                  // d == 36
    4 double d2 = integrate(e, 0, 1);   // d2 == 2.33

Clearly, we need to overload operators like * and + between Variables (x*x), between Constants and Variables (2*x), and between multiple ComplexExpressions (x*x and 2*x). Moreover, the literals like 1 and 2 are not Constant objects, they are doubles that need to be converted to Constant objects. So, these operators should also be overloaded for double arguments. Clearly, given the fact that all of these (Variable, Constant, ComplexExpression) are different sub-types of Expression, it will be easier if we just overload these operators between Expressions, and between Expressions and doubles.

Now any complex expression can be represented as:

f(x) = u(x) OP v(x)

OP is a binary arithmetic operator. For example:

f(x) = c is a degenerate case where, u(x) = 1, v(x) = c and OP = *. Or perhaps u(x) = 0, v(x) = c and OP = +. Assuming that we have such an operation available for each appropriate arithmetic operation, we write the class for complex expressions as a template class - the template parameter being the Binary Operation.

Hide line numbersShow line numbers

    1 template<class Op>
    2 struct ComplexExpression : Expression {
    3     Expression* l_;
    4     Expression* r_;
    5
    6     ComplexExpression(Expression& l, Expression& r) : l_(l.clone()), r_(r.clone()) {
    7     }
    8
    9     ~ComplexExpression() {
   10         delete l_;
   11         delete r_;
   12     }
   13
   14     double operator() (double d) {
   15         return Op::apply( (*l_)(d), (*r_)(d) );
   16     }
   17
   18     Expression* clone() {
   19         return new ComplexExpression(*l_, *r_);
   20     }
   21 };

The binary operators can be easily defined using simple functors like the following:

Hide line numbersShow line numbers

    1 struct Add {
    2     static double apply(double l, double r) {
    3         return l+r;
    4     }
    5 };
    6
    7 struct Subtract {
    8     static double apply(double l, double r) {
    9         return l-r;
   10     }
   11 };
   12
   13 struct Multiply {
   14     static double apply(double l, double r) {
   15         return l*r;
   16     }
   17 };
   18
   19 struct Divide {
   20     static double apply(double l, double r) {
   21         return l/r;
   22     }
   23 };

Finally, when we combine two simple Expressions, we get a complex expression. For example, x might be a simple expression, but x*x is a complex expression. We want to be able to cascade the operators to any degree, thus:

x*x*x

should be a valid expression. Clearly x*x must return an object of such type that can be combined with x using a * operator. x*x must return a reference or pointer to Expression - because Expression is an abstract class so it cannot be returned by value, and besides it is not much point returning it by value because we want to treat it polymorphically (virtual function calls to operator() and clone() in ComplexExpression). Something like the following:


Hide line numbersShow line numbers

    1 Expression* operator * (Expression& l, Expression& r) {
    2     return new ComplexExpression<Multiply>(l, r);
    3 }

The above does not work because operator* returns a pointer to an Expression object - x*x returns a pointer. Consider an expression like x*x*2. x*x*2 is equivalent to (x*x)*2 - since x*x returns an Expression*, we need an operator* which takes a pointer (Expression*) and a double (2). The Standard does not allow an operator to be overloaded on arguments of integer types alone. Thus, operator * can only return a reference.


Hide line numbersShow line numbers

    1 Expression* operator * (Expression& l, Expression& r) {
    2     return new ComplexExpression<Multiply>(l, r);
    3 }

The above works but no one takes the responsibility of deallocating object referred to be the returned reference - we are left with a memory leak.

What about the following:

Hide line numbersShow line numbers

    1 Expression& operator * (Expression& l, Expression& r) {
    2     return ComplexExpression<Multiply>(l, r);
    3 }

The above does not even work - because we are passing a reference to a local object created in the function. It has undefined behaviour. What do we do - well, a bit of inevitable complexity creeps in here. We need to return a pointer wrapped in smart wrappers, which can take care of the life-cycles of the underlying pointer and act as proxy objects when participating in mathematical expressions.

Consider the following definition of a reference counted wrapper cum Proxy for heap allocated Expression pointers:

Hide line numbersShow line numbers

    1 struct ExpressionRef {
    2     ExpressionRef(Expression* ptr) : sp_(ptr), ref_cnt_(1) {
    3     }
    4
    5     ~ExpressionRef() {
    6         if (--ref_cnt_ == 0) {
    7             delete sp_;
    8             sp_ = 0;
    9         }
   10     }
   11
   12     ExpressionRef(const ExpressionRef& source) : sp_(source.sp_) {
   13         ++ref_cnt_;
   14     }
   15
   16     inline ExpressionRef& operator = (const ExpressionRef& rhs) {
   17         if ( this != &rhs ) {
   18             if ( --ref_cnt_ <= 0 ) {
   19                 delete sp_;
   20                 sp_ = 0;
   21             }
   22
   23             sp_ = rhs.sp_;
   24             ++ref_cnt_;
   25         }
   26
   27         return *this;
   28     }
   29
   30     double operator() (double d) {
   31         return (*sp_)(d);
   32     }
   33
   34     ExpressionRef clone() {
   35         ExpressionRef copy(sp_->clone());
   36         return copy;
   37     }
   38
   39     inline Expression* get() {
   40         return sp_;
   41     }
   42
   43     inline Expression& getref() {
   44         return *sp_;
   45     }
   46
   47     inline operator void*() {
   48         return sp_;
   49     }
   50
   51 private:
   52     Expression *sp_;
   53     int ref_cnt_;
   54 };

Using this class, we can rewrite operator* like below:

Hide line numbersShow line numbers

    1 ExpressionRef operator * (Expression& l, Expression& r) {
    2     return ExpressionRef(new ComplexExpression<Multiply>(l, r));
    3 }
    4

Thus, the return value of x*x is of type ExpressionRef, and at least it wraps a polymorphic reference to Expression, and ensure that there would be no memory leaks. The only problem now is to make expressions such as x*x*x valid. x*x*x translates to (x*x)*x - whereby x*x returns ExpressionRef and x is some sub-type Expression. This is not such a big deal - we define operator * (ExpressionRef&, Expression&). We also need the alternative permutations: operator * (Expression&, ExpressionRef&). In fact, to allow expressions such as (x*x)*(x*x), one must also allow operators like: operator * (ExpressionRef&, ExpressionRef&).

At this point, all the issues with our solution are resolved - and we need to take stock of the final set of operator overloads we need to make the expressions work naturally. Here is a summary:



Expression& Op Expression&
ExpressionRef& Op ExpressionRef&
Expression& Op double - and reverse permutation
ExpressionRef& Op double - and reverse permutation
ExpressionRef& Op Expression& - and reverse permutation

That makes it 8 types of signatures. For each type, if we plan to implement +, -, * and /, then we will have a total of 32 operators. One set of operators can have real implementations and the rest can be defined in terms of the first set. Here are the definitions for the + operators.

Hide line numbersShow line numbers

    1 ExpressionRef operator + (Expression& l, Expression& r) {
    2     return ExpressionRef(new ComplexExpression<Add>(l, r));
    3 }
    4
    5 ExpressionRef operator + (ExpressionRef& l, ExpressionRef& r) {
    6     return l.getref() + r.getref();
    7 }
    8
    9 ///////////////
   10
   11 ExpressionRef operator + (Expression& l, const double d) {
   12     return l + Constant(d);
   13 }
   14
   15 ExpressionRef operator + (const double d, Expression& l) {
   16     return Constant(d) + l;
   17 }
   18
   19 //////////////
   20
   21 ExpressionRef operator + (ExpressionRef& l, Expression& r) {
   22     return l.getref() + r;
   23 }
   24
   25 ExpressionRef operator + (Expression& l, ExpressionRef& r) {
   26     return l + r.getref();
   27 }
   28
   29 //////////////
   30
   31 ExpressionRef operator + (ExpressionRef& l, double d) {
   32     return l.getref() + Constant(d);
   33 }
   34
   35 ExpressionRef operator + (double d, ExpressionRef& r) {
   36     return Constant(d) + r.getref();
   37 }

To test this solution, use the following functions:

Hide line numbersShow line numbers

    1 double integrate(Expression& e, double low=0, double high = 1, double epsilon = 0.001) {
    2     assert(low <= high );
    3     double auc1 = 0, auc2 = 0;
    4     double running_x = low;
    5     while ( running_x < high ) {
    6         auc1 += e(running_x) * epsilon;
    7         running_x += epsilon;
    8         auc2 += e(running_x) * epsilon;
    9     }
   10
   11     return (auc1 + auc2)/2;
   12 }
   13
   14 double integrate(ExpressionRef& er, double low=0, double high = 1, double epsilon = 0.001) {
   15     return integrate(er.getref(), low, high, epsilon);
   16 }
   17
   18 int main()
   19 {
   20     Variable x;
   21
   22     cout << ((2*x*x + 3*x + 3)*(2*x*x + 3*x + 3))(2) << endl;
   23     cout << integrate((2*x*x + 3*x + 3), 0, 1) << endl;
   24     cout << integrate((2*x*x + 3*x + 3)*(2*x*x + 3*x + 3), 0, 1) << endl;
   25     cout << integrate((x/(1+x)), 0, 1) << endl;
   26     cout << integrate(Exp(), 0, 1) << endl;
   27     cout << integrate(x*x, 0, 7) << endl;
   28
   29     return 0;
   30 }

Having come thus far, you may have made two observations. One we have written code which is nifty, and works well but is repetitive in some parts and not very extensible. Second, although this article is about Expression Templates, we have hardly used any templates (except for the ComplexExpression class).

What are the key concepts in this code which enabled creating the Expression Functors?
1. Nesting function objects and operator() of outer objects calling operator()'s of inner objects - for example ComplexExpression::operator(). The ormal term for these idioms is Functional Composition.
2. Overloading operators on Expression types.

What we've done so far was laying the foundation for our understanding of Expression Templates. The real deal should not take a lot of time after this. We will now head into investigating how this model of functional composition can be retained and generalized, performance of the Expressions phenomenally improved, and the lines of code drastically cut - by using Templates. This is the topic of the next part of this article.

References

1. Todd Veldhuizen: Expression Templates
   
   http://ubiety.uwaterloo.ca/~tveldhui/papers/Expression-Templates/exprtmpl.html
   

Read more!

Getting Started with Boost

Ten nifty tricks to incorporate into your armoury in your first week of using Boost

Boost has a wide array of libraries, and they often differ in complexity, expanse and sometimes power, but not in usefulness. Obviously a utility to convert strings to integers will not have the same complexity or power as a library for functional compositions. But both are useful in their own right. Today, Boost has close to 40 libraries (may be more) and this large number, along with the wide variety therein, sometimes serves to overawe the new learner. This article has a specific purpose - to get you started with a few, relatively easy, nifty tricks that you can employ in many general cases to add value and usability to your code, without having to be a Boost expert. Such head-starts serve to increase our motivation to use a tool, exposing us to the first hand benefits of a tool at the expense of a little effort. So without further ado, let me cut to the chase.

1. Time measurements and thermometer bars

The following piece of code illustrates how to use the Boost.Timer library to measure elapsed time between two points in code. Using this facility, you can easily measure the time taken to execute a certain section of code. To view the sorce code with numbered lines, click "Show line numbers".

Hide line numbersShow line numbers

    1 #include <iostream>
    2 #include <sstream>
    3 #include <boost/progress.hpp>
    4 #include <windows.h>
    5 using boost::progress_timer;
    6 using std::cout;
    7 using std::stringstream;
    8 using std::endl;
    9
   10 int main()
   11 {
   12     stringstream os;
   13     double elapsed_time = 0.0;
   14     {
   15         progress_timer t(os);
   16         int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
   17         const int arr_elems = sizeof(arr)/sizeof(int);
   18
   19         for ( int i=0; i<arr_elems; i++ ) {
   20             Sleep(3000);
   21         }
   22     }
   23
   24     if ( os >> elapsed_time ) {
   25         cout << "Net elapsed time: " << elapsed_time << endl;
   26     } else {
   27         cout << "Net elapsed time: " << os.str() << endl;
   28     }
   29
   30     return 0;
   31 }

The Boost header we used for our purpose is progress.hpp. We create an array of 16 integers and simulate some processing on this array by iterating through the elements of the array and pausing for 3 seconds for each element to simulate a period of processing (line 20). We intend to find the time taken to set up the array and then perform this dummy operation. To do this, we enclose the relevant part of the code (lines 14 through 22) in braces to define a scope. At the start of the scope, we declare an object of boost::progress_timer and initialize it with a stream object which can be written to. At the end of the scope, the progress timer object will write the total time elapsed to the stream object. Thereafter we either extract the double precision floating point value of the time elapsed in seconds from the stream (line 24) or directly write the stream's contents to the standard output (line 27).

2. Tokenizing strings and seamless value conversions

Suppose you are working on a banking back-office system and are scrubbing the summary data from your bank's daily closing report. Now this report is in some delimited format which your report rendering software understands, but which is not XML or something. Your requirement is simple - you want to extract all the data from the report and do some processing on it. In other words, you need to parse the report data. Second, there are numeric items in the list as well and you want to do quick comparisons of some of those - like the age of the account holder and the net balance in her account. All these quantities will be read as strings from the input so we will also need an effective and consistent way to convert these to numeric values. Parsing data of even moderate complexity can be a tough job and while the standard library containers and string classes provide adequate tools for doing this job, the code you'd end up with often tends to be long and not very readable. And converting string to numeric types isn't always straightforward either. On the other hand you don't want to spend more than half-hour in writing the code. What do you do. Well, you use the Boost.Tokenizer and Boost.Conversion libraries and you are through.

Suppose the data comes to you in the form of several records delimited inside braces ( { and } ). Within each record, several fields are delimited by semi-colons (;) and each field is a name-value pair of the form name=value or name:value. You don't want to be bothered about verifying the correctness of the grammar - you could assume that the document is well-formed and you then want to extract the data. Here is some sample data.

{name:Chaim Rabinowitz;acc:5629311372;bank:Citibank N.A.;branch:Tel-Aviv;age:69;balance:100000.00}{name:Mordechai Silberman;acc:46268675539;bank:Carmel Bank;branch:Haifa;age:43;balance:20000.00}{name:Amir Belleli;acc:5538639473;bank:Carmel Bank;branch:Nahariyya;age:54;balance:64000.00}{name:Liat Gershgoren;acc:5538639473;bank:The Hebrew Bank;branch:K'far Etzion;age:27;balance:28000.00}

And here is the code.

Hide line numbersShow line numbers

    1 #include <iostream>
    2 #include <boost/tokenizer.hpp>
    3 #include <boost/algorithm/string.hpp>
    4 #include <boost/lexical_cast.hpp>
    5 #include <string>
    6 #include <vector>
    7 using std::cout;
    8 using std::endl;
    9 using std::string;
   10 using std::vector;
   11 using boost::char_separator;
   12 using boost::split;
   13 using boost::lexical_cast;
   14
   15 struct AccountSummary {
   16     string name;
   17     int age;
   18     string bank;
   19     string branch;
   20     string account_number;
   21     double balance;
   22
   23     AccountSummary() : age(0), balance(0.0) {
   24     }
   25 };
   26
   27 int main()
   28 {
   29     string str = "{name:Chaim Rabinowitz;acc:5629311372;bank:Citibank N.A.;branch:Tel-Aviv;age:69;balance:100000.00}"
   30                  "{name:Mordechai Silberman;acc:46268675539;bank:Carmel Bank;branch:Haifa;age:43;balance:20000.00}";
   31
   32     typedef boost::tokenizer<char_separator<char> > tokenizer;
   33     char_separator<char> sep("{}");
   34     tokenizer records(str, sep);
   35     vector<AccountSummary> account_data;
   36     bool bad_data = false;
   37
   38     for (tokenizer::iterator tok_iter = records.begin(); tok_iter != records.end(); ++tok_iter) {
   39         string next_record = *tok_iter;
   40         AccountSummary next_acc_data;
   41         char_separator<char> sep2(";");
   42         tokenizer fields(next_record, sep2);
   43
   44         try {
   45             for (tokenizer::iterator fld_iter = fields.begin(); fld_iter != fields.end(); ++fld_iter) {
   46                 string next_field = *fld_iter;
   47                 vector<string> key_val;
   48                 split(key_val, next_field, boost::is_any_of(":="));
   49
   50                 if ( key_val.size() >= 2 ) {
   51                     const string& key = key_val[0];
   52                     const string& value = key_val[1];
   53
   54                     if (key == "name") {
   55                         next_acc_data.name = value;
   56                     } else if (key == "acc") {
   57                         next_acc_data.account_number = value;
   58                     } else if (key == "bank") {
   59                         next_acc_data.bank = value;
   60                     } else if (key == "branch") {
   61                         next_acc_data.branch = value;
   62                     } else if (key == "age") {
   63                         next_acc_data.age = lexical_cast<int>(value);
   64                     } else if (key == "balance") {
   65                         next_acc_data.balance = lexical_cast<double>(value);
   66                     } else { // Do nothing
   67                     }
   68                 }
   69             }
   70         }  catch(boost::bad_lexical_cast& be) {
   71             bad_data = true;
   72         }
   73
   74         if ( bad_data ) {
   75             bad_data = false;
   76             continue;
   77         }
   78         account_data.push_back(next_acc_data);
   79     }
   80
   81     return EXIT_SUCCESS;
   82 }

Obviously, this code does a few things with the data, but certainly does not print it. For a nice way to print this data in a suitable format, look at section 4 below.

3. Expressive code with zero resource-leaks

In an ideal world, all libraries and APIs you work with will have perfect semantics and you will never need to make compromises of any kind in your code. In such a world, you would only need to work with first class C++ objects which take care of their own initialization and clean-up in the C++ tradition of construction and destruction. In the real world however, you would be writing C++ applications to talk to legacy systems using a C API that is less than ideal. In that real world, you will have strdup-style C APIs that return dynamically allocated storage to you and expect you to take care of the life cycle of the pointer, remembering to call free on the pointer once you are done. As a real life programmer you would surely face such dilemmas several times, in several forms - and that's where the family of Smart pointers comes into the picture.

Smart pointers are simple classes which can "wrap" pointers to objects of different kinds, and in some cases arrays of objects. The primary advantage in the use of such wrappers is the seamless life-cycle management of these pointers (through the RAII idiom) and exception-safety. In fact the Smart Pointer collection from Boost is so good that you no more have an excuse to write C++ code that has memory leaks. I am not about to start a discussion on either the RAII-idiom or exception-safety - primarily because of lack of space in this column, and sites that handle the topics with more focus. Here we will see how the use of Boost's smart pointers provide power, simplicity and correct, reliable behaviour to your code.

Consider the following piece of code - let me tell you, it does not compile.

Hide line numbersShow line numbers

    1 #include <iostream>
    2 #include <string>
    3 #include <cctype>
    4
    5 using std::cout;
    6 using std::endl;
    7 using std::string;
    8
    9 extern "C" int strucase(char *str);
   10
   11 int strucase(char *str) {
   12     int count = 0;
   13     if ( str ) {
   14         do {
   15             (islower(*str)) ? (*str=toupper(*str), count++) : 0;
   16         } while(*str++);
   17     }
   18
   19     return count;
   20 }
   21
   22 string new_api() {
   23     return "Eddie Cochran";
   24 }
   25
   26 int main()
   28 {
   29     string str = new_api();
   30     strucase(str.c_str());
   31
   32     return 0;
   33 }

Given a C++ string, if you want to pass it's contents as a char* to a function that takes a (non-const) char* rather than a const char* (like strucase above), you have to make a copy of the string's underlying character array into a new array, and pass the base address of the array instead. It's a bit of a fib when I say you have to - what good is const_cast for after all? But then, what guarantee do you have that this strucase function that takes a non-const char* does not write to the string you passed. In fact, in this case strucase does write to the string, converting it in place to an all upper-case ASCII string. So the call at line 30 above fails (click Show line numbers to see line numbers). The string returned by new_api can be of arbitrary length (not exceeding platform specific limits, still) so you cannot create an array, with a size known at compile time, to hold the copy of the string. In other words, you have to allocate memory dynamically, and whenever you do that there is the hassle of correctly deallocating the allocated memory once every part of your code is done with using it. The following code addresses the issue with a smart array from Boost.

Hide line numbersShow line numbers

    1 #include <iostream>
    2 #include <string>
    3 #include <cstring>
    4 #include <boost/scoped_array.hpp>
    5 #include <cctype>
    6
    7 using std::cout;
    8 using std::endl;
    9 using std::string;
   10 using boost::scoped_array;
   11
   12 extern "C" int strucase(char *str);
   13
   14 int strucase(char *str) {
   15     int count = 0;
   16     if ( str ) {
   17         do {
   18             (islower(*str)) ? (*str=toupper(*str), count++) : 0;
   19         } while(*str++);
   20     }
   21
   22     return count;
   23 }
   24
   25 string new_api() {
   26     return "Eddie Cochran";
   27 }
   28
   29 int main() {
   30     string str = new_api();
   31     scoped_array sa( new char[str.length()+1] );
   32     char *copied_str = sa.get();
   33     strncpy(copied_str, str.c_str(), str.length());
   34     copied_str[str.length()] = 0;
   35     strucase(copied_str);
   36
   37     return 0;
   38 }

The first good thing about the above code is that it ensures there is no memory leak - the array allocated on line 31 is wrapped inside the scoped array object sa and at the end of the enclosing scope (in this case the main function), the destructor of scoped array kicks in and deallocates the entire array by calling delete[] on it.

Now imagine that instead of all this code being written inside the main() function, it was a different function which carried out these operations returned the allocated character array. Something like the following will obviously crash your code:

Hide line numbersShow line numbers

    1 char* my_new_string() {
    2     string str = new_api();
    3     scoped_array sa( new char[str.length()+1] );
    4     char *copied_str = sa.get();
    5     strncpy(copied_str, str.c_str(), str.length());
    6     copied_str[str.length()] = 0;
    7     strucase(copied_str);
    8
    9     return copied_str;
   10 }
   11
   12 int main() {
   13     char * new_str = my_new_string();
   14     cout << new_str << endl;
   15     char c='a';
   16     new_str[0] = c;
   17 }

Lines 14 and 16 are recipes for disaster because new_str is a copy of the pointer copied_str that the my_new_string() function passes back to you. And both these are aliases or copies of the underlying pointer in the scoped_array in my_new_string(). As soon as my_new_string() returns, scoped_array makes sure that the memory pointed to by its underlying pointer is deallocated. So in the main() function, you are dealing with an invalid memory reference - new_str.

What do we do? Pass back a copy of the scoped_array object itself? For one, scoped_array cannot be copied. Even if it could be, whether that would work or not would depend on whether or not scoped_array detects copying and such replication operations and keeps a count of the places in the code that have valid references to the object. This is called reference counting and scoped_array does not do it. Boost shared_array does. All you need to change in the above code is this:

Hide line numbersShow line numbers

    1 shared_array<char> my_new_string() {
    2     string str = new_api();
    3     shared_array sa( new char[str.length()+1] );
    4     char *copied_str = sa.get();
    5     strncpy(copied_str, str.c_str(), str.length());
    6     copied_str[str.length()] = 0;
    7     strucase(copied_str);
    8
    9     return sa;
   10 }
   11
   12 int main() {
   13     shared_array<char> sa = my_new_string();
   14     char *new_str = sa.get();
   15     cout << new_str << endl;
   16     char c='a';
   17     new_str[0] = c;
   18 }

Now, whenever you need to pass around a dynamically allocated array, just pass around the shared_array wrapper for it. It takes care of everything else.

There are more goodies in the Boost Smart Pointer library, including its work-horse - shared_ptr. In fact having already shown scoped_array and shared_array, it is not much work now to get up and running with scoped_ptr and shared_ptr. Both scoped_ptr and shared_ptr are capable of encapsulating a pointer to a single object on dynamically allocated storage. scoped_ptr is, of course, not copiable and not reference counted - suitable for operations limited in a single scope. shared_ptr on the other hand is a remarkable mobile smart pointer - you can freely copy and pass it around, it is fully reference counted. These classes overload the -> and * operators and therefore working with them is a breeze. Here is a short example to wrap up this section.

Hide line numbersShow line numbers

    1 #include <iostream>
    2 #include <string>
    3 #include <boost/shared_ptr.hpp>
    4
    5 using std::cout;
    6 using std::endl;
    7 using std::string;
    8 using boost::shared_ptr;
    9
   10 struct Foo {
   11     void bar() {}  
   12 };
   13
   14 typedef shared_ptr<Foo> FooPtr;
   15
   16 FooPtr createFoo() {
   17     FooPtr sp(new Foo);
   18     return sp;
   19 }
   20
   21 int main() {
   22     FooPtr sp = createFoo();
   23     sp->bar();
   24 }

Imagine how you would have handled the case where you could need to create arbitrary objects on the free-store with new and pass them around in the program, across scopes, sharing between multiple owning objects and scopes. Without the shared_ptr, such brevity was impossible.

In reality, shared_ptr models a "shared ownership" idiom that concerns managing the life cycle of the underlying heap-object. Sometimes, this is precisely what we want to avoid - ownership. In such cases, shared_ptr fails to prevent memory leaks and we need other alternatives. For more details, see weak_ptr's.

4. Using reference wrappers to write efficient code

Suppose you are dealing with objects of a class which cannot be copied, and perhaps not be assigned either. May be you are modelling humans in a social group and one of the assumptions / constraints is that humans cannot be replicated or cloned. So a Human object would essentially be a non-assignable, non-copiable object. And yet, for the purposes of effectively managing large groups of humans, you have to use different kinds of containers. May be you are modelling the behaviour of humans in a queue and you choose an std::list here - because the Humans have the liberty to leave the queue at any point. A list perhaps also makes sense, because a Human might opportunistically join a queue at the middle rather than at the end where he is actually supposed to join - to reduce his personal wait time. Whatever the social engineering issue here, we have a bigger computer programming issue to beat. Humans are not copiable or assignable - but an std::list container requires its elements to be both. You have no choice - either make the Humans copiable (an untenable model) or roll out your own containers which can store object references - or so you sulk. Enter Boost reference wrappers - a feature that should actually make it to the next release of the C++ Language and Standard Library (C++0x) - and you have reason to cheer.

The idea behind reference wrappers is simple. Create a trivial wrapper around a reference to an object and make this wrapper copiable and assignable. This wrapper object stores a reference or pointer to the real object. The wrapper object can be easily copied and assigned - without the underlying object getting replicated. Finally, the wrapper object should transparently degrade to the underlying type in contexts where an object of the underlying type is needed. This makes a reference wrapped object very easy to store in STL containers and easy to use in STL algorithms. The boost::reference_wrapper<T> template conforms to all these requirements and does a great job of it. Consider the following code.

Hide line numbersShow line numbers

    1 #include <iostream>
    2 #include <vector>
    3 #include <algorithm>
    4 #include <boost/ref.hpp>
    5 using std::cout;
    6 using std::endl;
    7
    8 struct Human {
    9     Human() : id_(++count) {
   10     }
   11
   12     const int id() const {
   13         return id_;
   14     }
   15
   16 private:
   17     const int id_;
   18     Human(const Human& srt);
   19     Human& operator = (const Human& srt);
   20     static int count;
   21 };
   22
   23 int Human::count = 0;
   24
   25 template<class T>
   26 struct PrintId {
   27     int operator()(T t) {
   28         cout << t.id() << endl;
   29         return 0;
   30     }
   31 };
   32
   33
   34 int main() {
   35     using std::vector;
   36     Human h1, h2, h3, h4;
   37
   38     vector< boost::reference_wrapper<Human const> > people;
   39     people.reserve(4);
   40     people.push_back(boost::cref(h1));
   41     people.push_back(boost::cref(h2));
   42     people.push_back(boost::cref(h3));
   43     people.push_back(boost::cref(h4));
   44
   45     std::for_each(people.begin(), people.end(), PrintId<Human const&>());
   46 }

The above code defines the Human class, and each object of the class gets a unique id at the time it is created - which distinguishes it as a unique individual, distinct from others of the same kind (Humans).

Four humans are created and they are stored in a fixed order in a vector of reference wrapped Humans. This is necessary because we could not have had a vector<Human> since Human is not a copiable class. Since boost::reference_wrapper<T> is copiable, we can create a vector<boost::reference_wrapper<T> >.

Finally, we print the unique id of each Human in the people vector. If you notice, we actually reference wrapped and stored const Human, and we created such reference wrapped objects from regular objects using the call boost::cref(...). You could have used boost::ref(...) instead to create non-const references. Most importantly, the functor PrintId does not need to know anything about reference wrappers. It's overloaded operator() takes a normal reference to a const Human, and when the for_each algorithm is used, the reference wrapper elements from the vector gracefully degrade to const Human&. This is huge convenience if you consider how brief the code is.

But if you thought this is the limit of reference_wrapper's applicability, you have been deceived. The reference_wrapper class is not only an idiom-enabling construct (allowing you to store references in STL containers), it is also an optimization-enabling construct and in many cases, changing existing code to use reference_wrappers can actually reap tremendous performance benefits. Consider the following piece of STL code:

Hide line numbersShow line numbers

    1 #include <iostream>
    2 #include <vector>
    3 #include <algorithm>
    4 using std::cout;
    5 using std::endl;
    6
    7 struct Foo {
    8     Foo() : id_(++count) {
    9         cout << "Object constructed: id = " << id_ << endl;
   10     }
   11
   12     const int id() const {
   13         return id_;
   14     }
   15
   16     Foo(const Foo& srt) : id_(++count) {
   17         cout << "Object constructed: id = " << id_
   18              << ", copied from Object[ id = " << srt.id() << " ]" << endl;
   19     }
   20
   21     Foo& operator = (const Foo& srt) {
   22         return *this;
   23     }
   24
   25 private:
   26     const int id_;
   27     static int count;
   28 };
   29
   30 int Foo::count = 0;
   31
   32 template<class T>
   33 struct Bar {
   34     int operator()(T t) {
   35         cout << "Object[ id = " << t.id() << " ]" << endl;
   36         return 0;
   37     }
   38 };
   39
   40
   41 int main() {
   42     using std::vector;
   43     Foo f1, f2, f3, f4;
   44
   45     vector< Foo > foos;
   46     foos.reserve(4);
   47     foos.push_back(f1);
   48     foos.push_back(f2);
   49     foos.push_back(f3);
   50     foos.push_back(f4);
   51
   52     std::for_each(foos.begin(), foos.end(), Bar<Foo const&>());
   53 }

This shows a regular class Foo, which retains a unique id (from the Human example) being stored in a vector< Foo > and then the functor Bar<Foo const&> being invoked on each element of the vector. The Foo object is copiable and assignable, although on copy-construction the new object gets its own unique id, and even on assignment, this unique id is retained and not overwritten. Whenever a new object is created through the default constructor, a message of the form:

Object constructed: id = <object_id>

is printed. Whenever a new object is created through the copy constructor, a similar message of the form:

Object constructed: id = <object_id>, copied from Object[ id = <source_object_id> ]

is printed. On my system, this prints the following messages.

Object constructed: id = 1
Object constructed: id = 2
Object constructed: id = 3
Object constructed: id = 4
Object constructed: id = 5, copied from Object[ id = 1 ]
Object constructed: id = 6, copied from Object[ id = 2 ]
Object constructed: id = 7, copied from Object[ id = 3 ]
Object constructed: id = 8, copied from Object[ id = 4 ]
Object[ id = 5 ]
Object[ id = 6 ]
Object[ id = 7 ]
Object[ id = 8 ]

If I remove the call to the reserve method of the vector at line 46, you might see a few more copies of the Foo objects being done as the vector initially expands upon each push_back. On my system (MSVC 9), with line 46 commented, the output looks like:

Object constructed: id = 1
Object constructed: id = 2
Object constructed: id = 3
Object constructed: id = 4
Object constructed: id = 5, copied from Object[ id = 1 ]
Object constructed: id = 6, copied from Object[ id = 5 ]
Object constructed: id = 7, copied from Object[ id = 2 ]
Object constructed: id = 8, copied from Object[ id = 6 ]
Object constructed: id = 9, copied from Object[ id = 7 ]
Object constructed: id = 10, copied from Object[ id = 3 ]
Object constructed: id = 11, copied from Object[ id = 8 ]
Object constructed: id = 12, copied from Object[ id = 9 ]
Object constructed: id = 13, copied from Object[ id = 10 ]
Object constructed: id = 14, copied from Object[ id = 4 ]
Object[ id = 11 ]
Object[ id = 12 ]
Object[ id = 13 ]
Object[ id = 14 ]

Things look only marginally better with gcc 4.1. This copying is at its peak initially when the vector starts to grow because the vector's storage is repeatedly reallocated. It becomes much less pronounced when the vector becomes larger. This should be a good enough reason to use the reserve method to optimize on unnecessary reallocation and copying.

If you now notice, in this piece of code, we are not retaining using the vector after any of the Foo objects f1, f2, f3 or f4 go out of scope. So, if we could store references to the Foo objects in the vector, it would have been a lot more efficient - with almost no copying needed. Here is the code for it. You can compare its output with that of the code above.

Hide line numbersShow line numbers

    1 #include <iostream>
    2 #include <vector>
    3 #include <algorithm>
    4 #include <boost/ref.hpp>
    5 using std::cout;
    6 using std::endl;
    7
    8 struct Foo {
    9     Foo() : id_(++count) {
   10         cout << "Object constructed: id = " << id_ << endl;
   11     }
   12
   13     const int id() const {
   14         return id_;
   15     }
   16
   17     Foo(const Foo& srt) : id_(++count) {
   18         cout << "Object constructed: id = " << id_
   19              << ", copied from Object[ id = " << srt.id() << " ]" << endl;
   20     }
   21
   22     Foo& operator = (const Foo& srt) {
   23         return *this;
   24     }
   25
   26 private:
   27     const int id_;
   28     static int count;
   29 };
   30
   31 int Foo::count = 0;
   32
   33 template<class T>
   34 struct Bar {
   35     int operator()(T t) {
   36         cout << "Object[ id = " << t.id() << " ]" << endl;
   37         return 0;
   38     }
   39 };
   40
   41
   42 int main() {
   43     using std::vector;
   44     Foo f1, f2, f3, f4;
   45
   46     vector< boost::reference_wrapper<Foo const> > foos;
   47     foos.reserve(4);
   48     foos.push_back(boost::cref(f1));
   49     foos.push_back(boost::cref(f2));
   50     foos.push_back(boost::cref(f3));
   51     foos.push_back(boost::cref(f4));
   52
   53     std::for_each(foos.begin(), foos.end(), Bar<Foo const&>());
   54 }

You'd see the following output - indicating that absolutely no copies needed to be made.

Object constructed: id = 1
Object constructed: id = 2
Object constructed: id = 3
Object constructed: id = 4
Object[ id = 1 ]
Object[ id = 2 ]
Object[ id = 3 ]
Object[ id = 4 ]

This is an important optimization - the kind there is a lot of scope for, and so you should always look out in your code for an opportunity to do such optimizations, using boost::ref and boost::cref.

5. Expressive use of STL algorithms with lambda functions

This short section is the least trivial of all the "week 1" techniques we are going to discuss here, because here I will whet your appetite for the enormous amounts of functional programming that Boost supports. We will take a look at the Lambda library - a library for creating unnamed functions, based on expression templates.

The beauty and power of the Lambda library lies in the fact that one can create specialized functions (or rather functors or function objects) on the fly and invoke them by various means. These functions don't need a name and have an implicit prototype that can easily change.

In the example in the section 2 (on string algorithms) above, we extracted the AccountSummary data for each individual from the delimited text stream. The data is now present in the form of a vector. What if we want to write this data in a suitable format to the standard output. Say, we want to output each record in a block, like:

Chaim Rabinowitz
-----------------
age: 69
bank: Citibank N.A.
branch: Tel-Aviv
account_number: 5629311372
balance: 100000
-----------------

Mordechai Silberman
-----------------
age: 43
bank: Carmel Bank
branch: Haifa
account_number: 46268675539
balance: 20000
-----------------
...

We could write a function object and pass it to the std::for_each algorithm as the applicative functor to do the job for us - for_each iterates over each element in the vector and prints it in the format supported by the functor. But following this, you discover that you also need to put this data in a different delimited format like:

Chaim Rabinowitz|age: 69|bank: Citibank N.A.|branch: Tel-Aviv|account_number: 5629311372|balance: 100000
Mordechai Silberman|age: 43|bank: Carmel Bank|branch: Haifa|account_number: 46268675539|balance: 20000

What do you do - fire up your C++ editor and add another piece of functor. The number of formats you want your data to be printed in is really open-ended - may be you just want to summarize the name and age of the individuals - yet another functor? You must be thinking by now that you want an easier way to do this. After all you might be defining all these functors in some other source or header file, while you might be using them somewhere completely removed from the place they are defined in. Your operative call would probably just look like:

for_each(account_data.begin(), account_data.end(), PrintBlocks());
for_each(account_data.begin(), account_data.end(), PrintPipeDelimited());
for_each(account_data.begin(), account_data.end(), PrintSummary());

There is nothing wrong with such code provided we have reasonable names for the functor classes like PrintBlocks, PrintPipeDelimited or PrintSummary (all of which are assumed to have a trivial default constructor here). But can you look beyond the PrintBlocks name and figure out the format in which the data is actually printed by it - or figure out what constitutes a summary in PrintSummary. You cannot - and you don't want to depend on an aspect of programming that depends on appropriateness of naming identifiers. Besides, such formatting detail is not worth encapsulating in functors and storing away - how much reusable are these functors really going to be. This is where Boost Lambda helps you in being expressive. Below is the slightly curious looking rewrite of the above code using Boost Lambda, and with all the formatting logic spelled out in-place. The code essentially extends whats's already there, so only the newer parts of the code are provided, with only a bit of the old code for context. Please don't be exasperated by syntactic unfamiliarity - try to get the big picture of what's being done.

Hide line numbersShow line numbers

  1-4//...
    5 #include <boost/lambda/lambda.hpp>
    6 #include <boost/lambda/bind.hpp>
    7 #include <algorithm>
 8-16//...
   17 using std::for_each;
   18 using boost::lambda::bind;
   19 using boost::lambda::constant;
   20 using boost::lambda::_1;
   21
   22 struct AccountSummary {
   23     string name;
   24     int age;
   25     string bank;
   26     string branch;
   27     string account_number;
   28     double balance;
   29
   30     AccountSummary() : age(0), balance(0.0) {
   31     }
   32 };
   33
   34 int main()
   35 {
   36     string str = "{name:Chaim Rabinowitz;acc:5629311372;bank:Citibank N.A.;branch:Tel-Aviv;age:69;balance:100000.00}"
   37                  "{name:Mordechai Silberman;acc:46268675539;bank:Carmel Bank;branch:Haifa;age:43;balance:20000.00}";
   38
39-44//...
   45     for (tokenizer::iterator tok_iter = records.begin(); tok_iter != records.end(); ++tok_iter) {
46-85//...
   85         account_data.push_back(next_acc_data);
   86     }
   87
   88     typedef vector<AccountSummary>::value_type elem_type;
   89     for_each(account_data.begin(), account_data.end(),
   90                cout << '\n' << "Block:" << '\n'
   91                     << "--------------------" << '\n'
   92                     << bind(&elem_type::name, _1) << constant('\n')
   93                     << constant("-----------------") << constant('\n')
   94                     << constant("age: ") << bind(&elem_type::age, _1) << constant('\n')
   95                     << constant("bank: ") << bind(&elem_type::bank, _1) << constant('\n')
   96                     << constant("branch: ") << bind(&elem_type::branch, _1) << constant('\n')
   97                     << constant("account_number: ") << bind(&elem_type::account_number, _1) << constant('\n')
   98                     << constant("balance: ") << bind(&elem_type::balance, _1) << constant('\n')
   99                     << constant("-----------------") << constant("\n\n")
  100            );
  101
  102     for_each(account_data.begin(), account_data.end(),
  103                cout << '\n' << "Delimited:" << '\n'
  104                     << "--------------------" << '\n'
  105                     << bind(&elem_type::name, _1) << constant('')
  106                     << constant("age: ") << bind(&elem_type::age, _1) << constant('')
  107                     << constant("bank: ") << bind(&elem_type::bank, _1) << constant('')
  108                     << constant("branch: ") << bind(&elem_type::branch, _1) << constant('')
  109                     << constant("account_number: ") << bind(&elem_type::account_number, _1) << constant('')
  110                     << constant("balance: ") << bind(&elem_type::balance, _1) << constant('\n')
  111            );
  112
  113     for_each(account_data.begin(), account_data.end(),
  114                cout << '\n' << "Summary Information:" << "\n\n"
  115                     << "--------------------" << '\n'
  116                     << constant("name: ") << bind(&elem_type::name, _1) << constant(", ")
  117                     << constant("age: ") << bind(&elem_type::age, _1) << constant('\n')
  118            );
  119
  120     return EXIT_SUCCESS;
  121 }

The output of this code is of the following form:

Block:
--------------------
Chaim Rabinowitz
-----------------
age: 69
bank: Citibank N.A.
branch: Tel-Aviv
account_number: 5629311372
balance: 100000
-----------------

Mordechai Silberman
-----------------
age: 43
bank: Carmel Bank
branch: Haifa
account_number: 46268675539
balance: 20000
-----------------


Delimited:
--------------------
Chaim Rabinowitzage: 69bank: Citibank N.A.branch: Tel-Avivaccount_number: 5629311372balance: 100000
Mordechai Silbermanage: 43bank: Carmel Bankbranch: Haifaaccount_number: 46268675539balance: 20000


Summary Information:
--------------------
name: Chaim Rabinowitz, age: 69
name: Mordechai Silberman, age: 43

If you see, we have printed the data in the AccountSummary records present in the vector in three different formats - Blocked, Delimited and Summary information. We didn't use a for-loop but rather the for_each algorithm to iterate through the records in each vector. The for_each algorithm takes three arguments - the two iterators that define the range of records to be handled, and a function pointer or functor which takes a single element of the container (in this case an AccountSummary object) and does some processing on it. The for_each statements for the three different cases (Blocked, Delimited and Summary) appear at lines 89, 102 and 113 respectively. In each case, the first two arguments are the iterators marking the beginning and past-the-end location of the AccountSummary vector. But for the third argument - we have a Lambda expression or an unnamed function that evaluates to a function object.

A Lambda expression is really just an expression, whose value is a function object. Just as 5+3 is an expression which results in an integer object, the Lambda expression is an expression which generates a callable entity - a functor object. The type of this functor object is a derived type which is of no consequence here. The Lambda expression is really a way of composing smaller function objects into a more complex function object, using overloaded operators to string together the smaller function objects. Thus expressions such as bind(...), constant(...) and _1 are all function objects with overloaded operators between them. Indeed, a Lambda expression is an excellent example of functional composition - the core idea in functional programming. More explanation follows.

• In each of these Lambda expressions, the curious looking _1 represents a "placeholder" for the first argument to the function. Because a Lambda expression evaluates to a functor of some sort and this functor has a signature of its own - it is but natural that we need a way to reference the arguments to this functor inside the Lambda expression. Boost's Lambda expressions support upto 9 arguments - by default represented by the placeholders _1 through _9. They are just normal C++ objects (of some type, not important here) and intelligently named using the fact that any valid C identifier can start with an underscore. In this case, there is only one argument to deal with - the current element in the vector - so we only need _1. But we need to get at its members.
  


• An expression like bind(&elem_type::name, _1) creates a functor which returns the value of the data member name of the object represented by _1, whose type is elem_type. Here elem_type is typedef'd to mean the value_type of the vector (i.e. AccountSummary). For example, if you were to use for_each to iterate over a map of string keys and double values, then at each step you'd be getting elements whose type is std::map<string, double>::value_type. This is essentially an std::pair<string, double> with members first (string) and second (double). Then, in order to construct a functor which returns the string key, we would use a bind expression like this:
  
  bind(std::map<string, double>::value_type::first, _1);
  
  We can almost always abridge these expressions by using suitable typedefs. For example:
  
  typedef std::map<string, double>::value_type map_elem;
  bind(map_elem::first, _1);
  
  Typically, we should try to use a single typedef'd name, corresponding to the type of _1 (or whichever argument placeholder).
  


• Expressions like constant("name: ") or constant('\n') represent functors which return a constant value. We don't want literals in the lambda expression - rather function objects which return such literals. That's because they need to be invoked for each iteration - not just printed once. However, you would have noticed that "Delimited:" or "Block:" are not enclosed in constant(...). In the output, you should see that name: or age: are repeated for each record - these were enclosed in constant(...) - but "Delimited:" or "Block:" were printed only once - because these were not enclosed in constant(...).
  


• In the same way as constant, there is another construct - var, which can wrap non-literal object instances. We haven't used it here but we could.
  

When all of these are combined into a single Lambda expression, it represents a callable entity - essentially a generated super-function, built from the above individual functional units. By now, you should have a gut feel of how Lambda expressions work - but I will leave you with another example to squint your eyes at.

The real power of Lambda expressions is the ability to define a callable entity at the site of invocation in a fairly intuitive and succinct manner. There is a syntactic baggage associated - and I feel that's the only factor that weighs against Lambda expressions. But it requires a bit of mastering, and you'd be on your way to leveraging the full power of Lambda expressions.

In order to get a hang of how functional composition works, read the two part article Expression Templates demystified.

6. Platform-independent code to manipulate files on the disk

7. Quick and easy threads

8. An extensible way to handle command-line arguments

9. Matching patterns and replacing text using Regular Expressions

Regular expressions are an important programming tool and is extensively used in applications for filtering and parsing text, and matching names of objects against name patterns. Every language used for application programming owes itself a regular expression facility, and with the slick and fast Boost.Regex, C++ gets its first standard Regular Expression library.

This section cannot serve as an introduction to the theory and syntax of regular expressions. Assuming that you have a working knowledge of Regular expression syntax as used by grep and egrep on Unix, or the Perl language, we get started here with a few short examples of how to use the Boost.Regex library.

To use the Boost.Regex library, you should know its basic object model - the main classes whose objects you need to define and use for your Regex work.

1. A regular expression is encapsulated by an instance of the class boost::regex. In fact, boost::regex is a typedef for boost::basic_regex<char>. There is a wide character version available - boost::wregex, which is a typedef for boost::basic_regex<wchar_t>.


2. The result of trying to search for a regular expression in an input can result in matches at several levels - including matches for sub-expressions within regular expressions. All such details of matches are reported back in an object of type match_results. Once again, match_results is a class template, and there are concrete instantiations like cmatch, smatch and their wide character variants (wcmatch and wsmatch) which correspond to specializations for C-strings (char*), C++ strings and wchar_t* strings.


3. The iterator regex_iterator which helps you run through the input sequence identifying all matches for a particular regular expression. This is a really handy tool.


4. Finally, the regex_token_iterator iterator adaptor - which makes splitting input based on delimiters (like split in Perl) as easy as it gets in C++.

In our first example of this section, we will write a simple egrep like utility which looks for regular expression patterns in a text stream, and prints out lines matching the pattern. It also prints the line number, and the segment of the line that matched the regular expression (in brackets). The program is invoked with a regular expression and one or more input file names as command-line arguments.
Hide line numbersShow line numbers

    1 #include <boost/regex.hpp>
    2 #include <iostream>
    3 #include <fstream>
    4 #include <string>
    5 #include <algorithm>
    6 #include <exception>
    7 
    8 using std::cout;
    9 using std::cerr;
   10 using std::endl;
   11 using std::ifstream;
   12 using std::string;
   13 using std::exception;
   14 
   15 int main(int argc, char *argv[])
   16 {
   17     if ( argc <= 2 ) {
   18         cerr << "Usage: " << argv[0] << " <regex> <file-list>"<< endl;
   19         return EXIT_FAILURE;
   20     }
   21 
   22     string str;
   23     ifstream in;
   24     const char * file_name = 0;
   25 
   26     try {
   27         boost::regex reg(argv[1]);
   28         while ( ( file_name = argv[--argc] )
   29                 && argc > 1 )
   30         {
   31             in.open(file_name, std::ios::in|std::ios::beg);
   32
   33             if ( in ) {
   34                 cout << file_name << endl << "==================="<< endl;
   35                 boost::smatch m;
   36                 int line_no = 0;
   37                 while( getline(in, str) ) {
   38                     ++line_no;
   39                     if ( boost::regex_search(str, m, reg) ) {
   40                         cout << line_no << ": " << str << "  [matches: " << string(m[0].first, m[0].second) << "]" << endl;
   41                     }
   42                 }
   43             } else {
   44                 cerr << file_name << ": Could not read." << endl << "==================="<< endl;
   45                 if ( !in ) in.clear();
   46             }
   47         }
   48     } catch(exception& e) {
   49         cerr << "Exception caught: " << e.what() << endl;
   50         return EXIT_FAILURE;
   51     } catch(...) {
   52         cerr << "Exception caught." << endl;
   53         return EXIT_FAILURE;
   54     }
   55 }

If you notice, the above example has a small issue. It picks up each line, searches for a match for the regular expression, and as soon as the first match is found, it prints the line number, line and the matching segment (in brackets). It then moves to the next line. If there are multiple segments in a single line matching the given regular expression, we miss all of those segments except the first one.

While it is possible to use the same regex_search function in a loop and using string iterators to run through all matches per line of text, the code doesn't look very good. In case you have to run through all distinct segments within an input sequence that match a regular expression, use the regex_iterator. A regex_iterator "points to" a match_result object. A match_result object represents a segment of input that matches a regular expression (as well as sub-expression matches, etc.). Thus, using regex_iterator, we loop over all matches in an input sequence. Here is the slightly altered code ... only the changed lines are highlighted.

Hide line numbersShow line numbers

   37 while( getline(in, str) ) {
   38     ++line_no;
   39     boost::sregex_iterator it(str.begin(), str.end(), reg), end;
   40     string matchlist;
   41     while ( it != end ) {
   42         matchlist += (*it++)[0].str() + " ";
   43     }
   44     if ( matchlist.length() ) {
   45         cout << line_no << ": " << str << "  [matches: " << matchlist << "]" << endl;
   46     }
   47 }

There are just three things to note in the above example. On line 39, we instantiate two objects of sregex_iterator - this is a typedef for regex_iterator. The second of these objects (end)is default constructed and serves as an end-marker or null-marker. Finally, on line 42, (*it) is an smatch (match_result) object and (*it)[0] represents the part of input that matched the whole Regular Expression. If there are N sub-expressions within the regular expression, (*it)[1] through (*it)[N] represent parts matching those sub-expressions. The str() member function gives the matching part as a C++ string.

10. Easy date and time measurements

Having come thus far, I must clarify that these ten libraries are in no way the ten most important libraries to know in Boost. There are many others which find no mention in this article - Boost.Interprocess, Boost.Asio, Boost.IoStream, Boost.Graph and the seminal Boost.MPL (The Boost Template Metaprogramming Library) among many others. The reason for not having covered these is that these are more involved libraries and we need to devote more space and time to each one to leverage their power. Therefore, they don't belong to a '10 nifty tricks' list. I'll be back soon with some of these topics.
Read more!