The C++ and Boost Code Shop

Return your objects by value (at least sometimes)

2010-11-04T18:35:00.007+05:30

Starting where we left a year and a half back (and I swear I had no time for the blog in this intervening period), we'll look at temporaries again, but in a slightly different light. We saw in that article that it's a great idea to eliminate temporaries of non-POD types (or more correctly, types with non-trivial copy semantics) as far as possible. One big advantage of eliminating temporaries is the elimination of redundant copying from a temporary to a named instance which is how a lot of temporaries inevitably end up. Common ways in which temporaries get created are when objects are returned by value from a function call, and also when a function (say foo) is invoked in-place in the argument list of the invocation of another function (say bar) - and thus the return value of foo() is passed to bar(). Some of these cases are illustrated in the following code:


Fud foo(int i)  // Fud is a copiable class
{
  return Fud(i); // Temporary created
}
void bar(Fud);
...
bar(foo(1));  // Temporary passed to bar
Fud f = foo(2);
...

Now suppose we were to rewrite the above code to eliminate temporaries. There are a few different ways, but let's try a fairly simple approach:


Fud foo(int i)  // Fud is a copiable class
{
  return Fud(i); // Temporary created
}
void bar(const Fud&);
...
bar(foo(1));  // const-reference to temporary, no copying
Fud f = foo(2);
...

In the above code, we have eliminated the pass by value of a Fud object to bar(...) but foo(...) still returns a temporary by value. Here is an enhancement:


void foo(int i, Fud *&f)  // Fud is a copiable class
{
  f = new Fud(i);
}
void bar(const Fud&);
...
Fud *pfud = NULL;
foo(2, pfud);
bar(*pfud);  // const-reference to temporary, no copying
...

This time there don't seem to be any temporaries and consequently no redundant copying. But the code is no longer simple. At the least, you cannot do something like bar(foo(...)) any more - nesting calls is a natural algebraic operation used to compose functions but the elimination of references takes that ability away from us. Strictly speaking, with Boost shared_ptr, we could eliminate this limitation (how? left as an exercise to the reader, an author's exclusive prerogative). But it still means that we have to incur the cost of dynamic memory allocation. Again, dynamic memory allocation is not necessarily evil - sometimes, it is even more welcome than allocating a large stack based object. But the overall readability of code has suffered as well.
What do we do? Well, it depends. A good idea is to start by passing temporaries back by value. Now don't cross your eyes - what you just read is exactly what I said and there is a little something that the C++ standard allows (without mandating) and most standard compilers implement as an optimization, which makes this possible. It is called Copy Elision and in a special form, Return Value Optimization or RVO for short.

Copy Elision

Copy elision simply refers to elimination of redundant copying, if at all possible. For example, consider the following code:


Fud obj = Fud(1);

What's happening there? A Fud instance called obj is initialized from a temporary Fud object created through Fud(1). Normally, we would expect that Fud's constructor will be invoked to create a Fud object with an initialization parameter value of 1. Next, the instance called obj will be created and initialized through a call to its copy-constructor which will copy the state of the temporary object to obj. However, it is not hard to see that the only purpose of the temporary object is to help initialize the obj instance. This code could have been written in a much simpler way as:


Fud obj(1);

There would have been no calls necessary to the copy constructor of obj, nor would there be any temporary instance to destruct. The behaviour of the code would have been exactly the same (unless of course the copy constructor or destructor had side-effects - always a bad idea). Copy elision is the inbuilt optimization in the compiler which causes code like this:


Fud obj = Fud(1);

to generate the equivalent of code like this:


Fud obj(1);

and thus prevent needless copying. An interesting special case is Return Value Optimization (RVO). It is best illustrated with the following example:


#include <vector>
#include <string>
#include <iostream>

using std::vector;
using std::string;
using std::cout;
using std::endl;

struct TestClass
{
    TestClass(int i) : i_(i)
    {}

    TestClass(const TestClass& tc) : i_(tc.i_)
    {
        cout << "Copied." << endl;
    }

private:
    int i_;
};

vector<TestClass> make_vec()
{
    vector<TestClass> vec;
    vec.reserve(20);

    cout << "Starting populating vector." << endl;
    for (int i = 0; i < 10; i++) {
        vec.push_back(TestClass(i));
    }
    cout << "Vector populated." << endl;

    return vec;
}

int main()
{
    vector<TestClass> vec = make_vec();
}

Look at line 40 above. The function make_vec() returns a vector which is copied to the vector vec - what looks like copy initialization. Since the contained type of the vector is TestClass, you'd expect the TestClass instances to be copied, first time when they are enqueued in the vector inside make_vec (line 31) and again when the returned temporary vector from make_vec is used for copy-initialization of vec at line 40. That would be conformant behaviour, but that's often not the behaviour you get. Running on gcc 4.3.2 on OpenSuSE gave me this output:


Starting populating vector.
Copied.
Copied.
Copied.
Copied.
Copied.
Copied.
Copied.
Copied.
Copied.
Copied.
Vector populated.

This clearly shows that there is no copying during copy-initialization of vec - in other words there is no copy-initialization. This is an example of Copy Elision - a special case known as RVO. Internally, the compiler might generate code that arranges for a reference to vec on line 40 to be passed to the function make_vec, and obviate the local vector inside make_vec so that all push_back operations happen on this reference instead. A slight change to the above code can completely disable Copy Elision / RVO, as illustrated below:


    return vec;
}

int main()
{
    vector<TestClass> vec;
    vec = make_vec();
}

I got this:


Starting populating vector.
Copied.
Copied.
Copied.
Copied.
Copied.
Copied.
Copied.
Copied.
Copied.
Copied.
Vector populated.
Copied.
Copied.
Copied.
Copied.
Copied.
Copied.
Copied.
Copied.
Copied.
Copied.

Quite clearly, the copy-initialization takes place and has not been optimized away.

The big advantage of RVO is that the syntax of function calls can be made to match the semantics of the mapping that the function represents. The return value rather than an out-parameter is a return value. This also allows for nested function calls, a natural algebraic expression of functional composition.

Therefore, depending on how the return value of function is going to be used - it might be a good idea to return an object by value.

Jargon Time: L-values, R-values and Temporaries

2009-02-02T01:41:00.030+05:30

As promised here are a few fairly basic examples of C++ jargon, demystified, here in this article. We start looking at basics of C++ expressions: l-values, r-values and temporaries. The concepts are simple, but important, and would be used in later columns of this (Jargon) series.

L-values and R-values

When we write code, we express action and intent through well-formed expressions that conform to a broad syntax. Some of this action involves moving data around, some of it involves carrying out a more complex operation - and most involve both. For example:

Show line numbers

    1 double number = 0.0;
    2 number = 2.0;
    3 double square_root = ::sqrt(number);

The above code involves both moving data around, and carrying out some action. In the second line, the literal double 2.0 is assigned to the double variable number. In this context number is an l-value expression - because it allows modification of the value it holds, when used on the left hand side of an assignment expression.

The expression 2.0 on the other hand can only be used to assign values to expressions such as number - in other words it can only be used on the right hand side of assignment expressions, never on the left hand side. It can also be used in function return statements. Such expressions are called r-values.

At this point we have three small observations to make:
1. An r-value can never be used on the left hand side of an assignment operation.
2. An l-value in very many cases can be used on the right hand side of assignment operations also. In this case, it simply degenerates to the value it contains. For example:

Show line numbers

    1 double number = 0.0;
    2 number = 2.0;
    3 double anotherNumber = number;

In the above code snippet, on the third line, the expression number is used as an r-value and degenerates to the value contained in the l-value expression number.
Some l-values cannot be used as r-values. For example, in the above code snippet, the expression double anotherNumber is an l-value expression, but we cannot write code like:

double aThirdNumber = (double anotherNumber = 2.0);

Language rules do not allow this. So you have an example of an l-value expression that cannot degenerate to an r-value expression.
3. l-values can also be used in function return statements. However, whether it is treated as an l-value or simply degenerates to an r-value depends on the return type of the function. If a function returns a non-const reference or pointer to an object, the function call can be considered as an l-value expression. That's essentially because the return value of the function is an l-value. For example:

Show line numbers


template<int size>
struct CheckedIntArray {
  int& operator[](int index) {
   if (index >=0 && index < size) {
    return array_[index];
   }
   throw IndexOutOfBoundsException; // some exception
  }
 private:
  int array_[size];
};

In the above CheckedIntArray class, operator[](int) can actually be used as an l-value expression because it returns a reference to an element in the underlying array. This enables use to write code like this:
Show line numbers

    1 CheckedIntArray<16> my_array;
    2 my_array[0] = 15;

In the above, the expression my_array[0] = 15; is equivalent to my_array.operator[](0) = 15;.

Many complex expressions are r-values. As well as a few simple ones:

Show line numbers

    1 int i = 0;
    2 ++i; // r-value expression

Arrays are r-values although individual elements in an array are not. Of course this does not apply to a pointer being used with an array syntax. Thus:

Show line numbers

    1 int arr[32] = {0};
    2 int arr2[32] = {1};
    3 arr[0] = 5;  // arr[0] is an l-value
    4 // the following is illegal
    5 // arr = arr2; // arr is an r-value
    6 
    7

Finally, let it be said that all expressions in C++ are either l-value or r-value expressions.

Temporaries

Related to the concept of r-values is the concept of temporaries. In fact temporaries are r-values (without all r-values being temporaries). Consider the following example:

Show line numbers

    1 int m = 4;
    2 int n = 5 + 8/m;

Here the expression 5 + 8/m is a temporary. This is a relatively simple temporary - possibly one that would only exist in the registers of the CPU. However, it is possible, and quite common, to have temporaries on the stack. The important thing to understand is that temporaries are unnamed values, which are created in the context of an expression and whose life time is limited to the period of evaluation of that expression. Consider the following expression:

string str = string("Hola amigos!");

The right hand side expression creates a temporary string object, and it is then copied to a local variable called str. Once the control of the executing program reaches past the semi-colon terminating this line of code, the temporary object is gone. Only str, containing a copy of it, exists.

There is one exception to this rule and it deals with references. In the last expression, if instead of a string variable on the left, we had a string reference, things would be a little different:

const string& str = string("Hola amigos!");

First of all, if you see we've had to add a const to the reference. We could not have had a non-const reference to a temporary. This is always the case, as you can see below:

Show line numbers

    1 const int& r = 5;
    2 const double& s = 2.0;

Since all temporaries are r-values, it is clear a non-const reference cannot refer to them. But, the exception that I referred to is in the life time of the temporary when a (const) reference refers to it. In this case, the temporary persists till the reference is in scope, and not just till the end of the statement that created the reference.

References are often created for function return values, although most optimizing compilers would eliminate the creation of these temporaries if the return value of the function was not assigned to any specific object. In general, reducing the number of temporaries that is created by a program is a good strategy for optimization, and to some extent, the compiler already does it.

Since all temporaries are r-values, it is clear a non-const reference cannot refer to them. But, the exception that I referred to is in the life time of the temporary when a (const) reference refers to it. In this case, the temporary persists till the reference is in scope, and not just till the end of the statement that created the reference.

References are often created for function return values, although most optimizing compilers would eliminate the creation of these temporaries if the return value of the function was not assigned to any specific object. In general, reducing the number of temporaries that is created by a program is a good strategy for optimization, and to some extent, the compiler already does it.

As a final example of how temporaries are generated, and where we can run into trouble with them if we are not careful, I present a piece of code I have seen written in several places (including products I have worked on).
Show line numbers

    1 using std::string;
    2 using std::stringstream;
    3 using std::cout;
    4 using std::endl;
    5 
    6 ...
    7 
    8 int x = 0;
    9 double f = 1.6;
   10 stringstream sout;
   11 sout << "Some data values streamed: " << x << "|" << f;
   12 const char *str = sout.str().c_str();
   13 cout << str << endl;  // this will likely print garbage

Can you spot the trouble with the above code. The trouble is that the member function std::string str() const of the std::stringstream class returns a temporary string. But in the expression sout.str().c_str(), we get a reference to the const char* pointer member of the returned temporary string and we copy it to the variable called str. As soon as this statement is executed, the temporary that was created as a result of the call to sout.str() is destroyed. But we still have a dangling pointer referring to its internal char * string, which is invalid for all good money. Needless to say, the last line above can even crash the program itself.

In the next edition of the Jargon column, we'll look at Namespace lookups and the Interface Principle. Keep watching, for more jargons demystified.

Parlez vous le C++?

2009-02-01T13:02:00.003+05:30

Recently I was thinking back on my days of trying to learn C++ by reading the Usenet groups comp.lang.c++.moderated and comp.std.c++. If someone asks me the best source to learn C++ from, I would always refer to these two places (and perhaps the Boost mailing list even though it is a little more Boost-focussed). Note that I said the best source to "learn" C++ - not merely "read" it (for which here are the books).

I'll explain what I mean by that (and as usual, I'll get a bit philosophical before cutting to the chase). I read C++ on my own, almost every written word of it that I read, alone - not a soul around even to discuss, not a teacher around to cast an impression. And yet no learning is complete unless an impression of that knowledge has been cast on us - this is true for every field of learning - even learning to memorize the English alphabet. The reason must be that this impression is cast on us through multiple senses - sight and sound, if not more. On the other hand, reading a tome is one dimensional - sight. It is here that the Usenet discussion boards and other mailing lists step in. While you still only read, you read direct discussions, arguments, brain-storms, doubts, misgivings, biases - it is a lot more real than reading a chapter on C++ polymorphism. It is what eggs you on to introspect - identify with the views expressed, or refute them; in other words, your C++ perspective is built here and that is what I meant when I said "learning".

Usenet in particular provided this motivation - I have seen posts by Bjarne Stroustrup, Scott Meyers, Andrei Alexandrescu, Herb Sutter, Jim Coplien, Steve Dewhurst, Andrew König, you name one, I'd have read his posts. The debates would go on for days together, even weeks, in lists that grew deep and wide with time. I was a mere reader - my occasional two-pence in the middle of debates would be politely answered but I had not the knowledge or understanding of the language to make a serious impact. Half the time, I groped through the standard or Stroustrup's book trying to figure out what is a "temporary" or where are "incomplete types" allowed, what is the meaning of "SFINAE" or what is the "Liskov Substitution Principle". You could be excused for wondering "Is this a programming language we are reading or a Theory of Banach algebras?". I certainly did - but it was part of C++'s charm (oh! geek) - for a wannabe-mathematician-turned-nobody, this was a nice feel-good aberration in a language I wanted to "speak". But coming back to the point - this meant I had to have a basic vocabulary ready, and a familiarity with a C++ alphabet soup before I could start communicating effectively in real C++ terms. C++ is tough and exacting, it requires discipline and knowledge - and it was not defined by a Sun or a Microsoft. I plan to put up a set of articles that would help build the awareness and concepts around the C++ jargons. Happy reading!

Aliasing pointers: using "weakness" to strengthen your code

2008-08-13T02:47:00.018+05:30

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.

Expression Templates Demystified: Part 2

2008-08-03T00:02:00.008+05:30

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:

Show 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:

Show 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:

Show 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.

Show 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:

Show 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:

Show 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.

Show 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:

Show 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.

Show 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

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

Expression Templates Demystified

2008-07-31T02:31:00.029+05:30

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:

Show 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:

Show 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:

Show 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:

Show line numbers

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

We want this to become an applicative functor like this:

Show 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:

Show 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:

Show 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:

Show 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.

Show 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:

Show 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.

Show 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:

Show 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:

Show 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.

Show 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:

Show 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:

Show 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:

Show 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.

Show 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:

Show 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

Todd Veldhuizen: Expression Templates

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

Getting Started with Boost

2008-07-12T18:54:00.081+05:30

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".

Show 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.

Show 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.

Show 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.

Show 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:

Show 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:

Show 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.

Show 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.

Show 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:

Show 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.

Show 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.

Show 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.

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>.

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.

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.

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.
Show 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.

Show 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.

C++ Challenge of the Month: July 2008

2008-07-12T15:02:00.014+05:30

Starting this month, I would be posting a C++ programming problem, and it's solution every month in a series called C++ Challenge of the Month (CCOM). The solution will be posted a couple of weeks after the problem and in the meanwhile, I hope to see a few readers try their hand at the problem. So here we go.

CCOM #1: Write the outline of a smart pointer class capable of managing pointers to classes from hierarchies which don't have a virtual destructor

Need a smart pointer, which can be used like:

smart_ptr<base> p = new derived;

When p goes out of scope, the object must be deleted and the destructor of derived must be called, irrespective of whether ~base() is virtual or not.

Courtesy, Syam Krishnan, Thiruvananthapuram, Kerala.

Book mania

2008-07-09T01:12:00.009+05:30

This list includes almost all books that have been published on C++ and that are of any relevance today. More importantly, I have tried to exclude books which you really don't need to read at all - for example Robert Lafore's introductory book on C++. These may not be bad books - just that there are better, more readable books already available.

List 1: For the beginner in programming, choose any one of the following. Even if you have some experience in other programming languages, the following books will provide you a robust foundation in C++.

1. Programming: Principles and Practice using C++ - Bjarne Strostrup
2. C++ Primer - Stan Lippman, Joseé Lajoie
3. Thinking in C++ (vol 1 & 2) - Bruce Eckel
4. Big C++ - Cay Horstmann, Timothy Budd

List 2: If you have a fair bit of programming experience but need a quick introduction to C++, read through the following texts one by one, work through their exercises and grow from strength to strength.

1. Accelerated C++ - Andrew König, Barbara Moo
2. Effective C++ 3/e - Scott Meyers
3. The C++ Programming Language - Bjarne Stroustrup
4. The STL Tutorial and Reference Guide - Dave Musser, Atul Saini (the ANSI standard edition)
5. C++ Templates - Nicolai M Josuttis, David Vandevoorde
6. Essential C++ - Stan Lippman

List 3: For the practising C++ programmer, these are the books you should be referring to every now and then as you write serious C++ code. In fact, you would often need to refer to some books from List 2 above.

1. The C++ Standard Library: Tutorial and Reference Guide - Nicolai M Josuttis
2. More Effective C++ - Scott Meyers
3. Effective STL - Scott Meyers
4. More C++ Gems - ed Robert Martin
5. C++ Cookbook - D Ryan Stephens, Christopher Diggins, Jonathan Turkanis, Jeff Cogswell
6. Generic Programming with STL: ... - Matt Austern
7. Exceptional C++ - Herb Sutter
8. The C++ Standard Library Extensions: A tutorial and reference - Pete Becker
9. More Exceptional C++ - Herb Sutter
10. C++ Common Knowledge - Steve Dewhurst
11. Beyond the C++ Standard Library: An Introduction to Boost - Björn Karlsson
12. C++ Coding Standards: 101 guidelines ... - Herb Sutter, Andrei Alexandrescu

List 4: For the wannabe OO-guru, library writer and C++ evangelist:

1. Design Patterns: Elements of Reusable object Oriented Software - Erich Gamma, Richard Helm, John Vlissides, Ralph Hodgson
2. Modern C++ Design - Andrei Alexandrescu
3. Exceptional C++ Style - Herb Sutter
4. Template Metaprogramming: ... - Dave Abrahams, Aleksey Gurtovoy
5. Imperfect C++ - Matt Wilson
6. Pattern Hatching - John Vlissides
7. Extended STL (Vol 1 & 2) - Matt Wilson

List 5:For the language and standard junkie:

1. The Design and Evolution of C++ - Bjarne Stroustrup
2. Inside the C++ Object Model - Stan Lippman

List 6: Books on specific libraries outside C++ and Boost have not been mentioned. A separate list can be created for those. Advanced books on specific topics:

1. Boost Graph Library - Jeremy Siek, Lie-Quan Lee, Andrew Lumsdaine
2. Standard C++ IoStreams and Locales: ... - Angelika Langer, Klaus Kreft

List 7: Older books still worth a read.

1. C++ Gems - ed Stan Lippman(especially the part on Templates - includes original articles from Todd Veldhuizen)
2. The Annotated C++ Reference Manual - Stroustrup, Margaret Ellis
3. C++ Gotchas - Stephen Dewhurst
4. C++ Programming Style - Tom Cargill
5. Advanced C++ Programming Styles and Idioms - James Coplien
6. Large Scale C++ Software Design - John Lakos

List 8: A few books that don't focus on C++ at all but general programming and design, and perhaps use other high-level programming languages. But these are very good read for every serious C++ programmer.

1. Emergent Design - Scott L. Bain
2. Working Effectively with Legacy Code - Michael Feathers
3. Refactoring - Martin Fowler, Kent Beck, John Brant

Getting Started with Boost

2008-07-04T04:39:00.070+05:30

Getting Started with Boost

Table of Contents

1.	Introduction
2.	Purpose & Motivation
3.	Building Boost
	3.1	The Boost Build Process
	3.2	Building Boost on Windows
	3.3	Building Boost on Linux
	3.4	Boost Binaries
4.	Using the Boost Libraries
	4.1	Linking to Boost libraries on Windows
	4.2	Linking to Boost libraries on Unix-like system

1. Introduction

The Boost C++ Libraries ( http://boost.org/ ) are an open source peer reviewed collection of C++ libraries, aimed at extending and complementing the functionality of the Standard C++ Libraries in several different directions. These libraries are available under the Boost Software License, which is one of the most liberal of open source licenses, and unlike GPL, allows free use of the Boost libraries in both Open Source and proprietary (closed-source) projects.

Boost represents a collection of libraries some of which are as simple as conversion utilities and some of which are as complex as recursive decent parsers of context-free grammars. A significant number of these libraries are the sort you would like to use everyday - file system manipulation, graph algorithms, heap memory life cycle management, variant data types, regular expressions, conversion utilities, zip and bzip2 file streams, signals and slots mechanisms, etc. Some have compelling features use of which gives your code a level of readability and edge that only C++ can - template driven lambda functions and expression construction. Finally, a good number of these libraries will make their appearance in the upcoming C++ standard (codenamed C++0x). In short, if you are a serious C++ programmer, you cannot afford to stay ignorant about Boost.

2. Purpose & Motivation

Purpose of this short tutorial introduction to Boost is to show the C++ programmer new to Boost, how to download, build and install the Boost libraries on Windows or Linux developer machines, and then get started with writing programs using these libraries.

For building I have chosen Windows and Linux as two representative platforms. I would only be showing how to use the "first-choice" compilers on these platforms - Microsoft C++ (14.0 or above) and GNU g++ (4.1 or above), both of which happen to be free. The reader should, in principle, be able to extrapolate the details to other platforms and compilers.

For the introduction to using the Boost Libraries, the intention is to cover basic use cases of as many Boost libraries as possible - limiting the size of the individual illustrative programs, but giving enough insight into their non-trivial use. The emphasis will be on those libraries that have made it to C++ standard already. But in due course, we will try to cover all the Boost libraries.

Finally, the sections on Building Boost and Using the Boost Libraries are fairly independent. Therefore the interested reader can read either section ahead of the other.

3. Building Boost

Boost distributions are available for download in both source and binary distribution formats. However, just as the best Linux kernel for your box is the one you can build by tweaking the default configuration, similarly the best Boost distribution for your box is the one you build on your box with your preferred compiler. Building Boost involves a fair number of configuration steps, and there are several optional features that you can turn off turn on in the description below. The optional features are normally described in gray boxes so that they stand-out. This section is a step-by-step, hands-on guide to building the Boost library from source.

3.1 The Boost build process

3.1.1 Basic Ingredients

The boost sources are available in the form of a compressed tar ball or a zip archive. Download the Boost sources, [ Latest version 1.35.0 ], from http://boost.org/ (or http://sourceforge.net/projects/boost). The size of the download is around 22 MB. Download one of the zip, tar.gz/tgz, or tar.bz2 source archives. On Windows, if you are downloading a tar.gz or tar.bz2 archive, this could get downloaded as boost_<version>.tar.tar and you will need to rename it to boost_<version>.tar.gz or boost_<version>.tar.bz2 as the case may be.

The Boost source does not require any external configuration before building on a specific platform - so there are no make config or configure scripts to run. In fact, there is no make. Instead, Boost uses a build system that uses Boost-Jam or bjam, a spin-off from the Perforce Jam build utility. Bjam reads jam files just as make reads Makefiles. However, we are not about to go into the details of the syntax of the Jam files.

3.1.2 Build configuration

The Boost libraries can be built as a vast number of variants, all in one go or separately. We can have debug and release variants of the same library. For each such library, we can have static or shared libraries. For each such combination we can have threading-challenged or thread-aware libraries. And finally, for each such combination, we can have libraries which link statically or dynamically with the C++ Standard and Runtime Libraries of the platform, libraries which link with the debug versions of the C++ Standard and Runtime Libraries of the platform, libraries which have no optimization and inlining (even release libraries), etc. That's a mind-boggling array of combinations. We will stick to a simple set of rules:

Build only thread-aware libraries - not threading-challenged ones.
Build only shared libraries - not static ones.
Build both debug and release versions of each library.

The build system defaults automatically take care of certain things:

The libraries always link dynamically if the C++ Standard and Runtime libraries are available as shared libraries or DLLs.
The libraries always link with the debug versions of the C++ Standard and Runtime libraries for debug builds and release versions of the C++ Standard and Runtime libraries for release builds.
Optimization, inlining, etc is turned off for debug builds and done for release builds.

In addition, some features of some of the Boost Libraries, and the Boost.Python library itself are not built into the libraries by default but require additional third party libraries. We do not attempt to build the Boost.Python and Boost.MPI libraries in this tutorial, but we do attempt to build all the remaining third-party libraries and use them for the build. All sections which deal with these libraries have a gray background to indicate that these are optional steps and can be skipped for a basic functional build.

3.1.3 Optional enhancements

Hide

The following third-party, free libraries can be downloaded optionally, in order to support certain features of the Boost libraries which are by default not built. They are platform-agnostic downloads - so a single downloaded archive can be used on both Windows and Linux. If you don't need a particular feature from among these, you need not download the library required for it.

zlib - [latest version 1.2.3] from http://www.zlib.net/. Small download of around 500 K. Download one of the zip, tar.gz/tgz, or tar.bz2 source archives. On Windows, if you are downloading a tar.gz or tar.bz2 archive, this could get dowloaded as zlib-<version>.tar.tar and you will have to rename it to zlib-<version>.tar.bz2. Needed to support reading from / writing to zipped streams in Boost.IOStreams.
Download libbz2 [latest version 1.0.5] - from http://www.bzip.org/downloads.html. Small download of around 850 K. Download one of the zip, tar.gz/tgz, or tar.bz2 source archives. On Windows, if you are downloading a tar.gz or tar.bz2 archive, this could get dowloaded as bzip2-<version>.tar.tar and you will have to rename it to bzip2-<version>.tar.gz. Needed to support reading from / writing to bzip2-compressed streams in Boost.IOStreams.
Download ICU C++ library [latest stable version 4.0] - from http://www.icu-project.org/download/ or ftp://ftp.software.ibm.com/software/globalization/icu (supports anonymous logins). Download the zipped version for Windows. It is a moderately large download - about 12 MB. Needed to support Unicode regular expressions in Boost.Regex.

3.2 Building Boost on Windows

In order to build Boost 1.35 on Microsoft Windows, you need to have the following software installed.

Microsoft C++ compiler version 12.00.8168 or above. Version 12 was shipped with Visual C++ 6. The recommended version is Microsoft C++ compiler version 15.00. Version 15 ships with Visual C++ 9.0 (2008) and is available for free download in the form of the Microsoft Visual Studio 2008 Xpress Edition and Microsoft Visual C++ 2008 Xpress Edition.
Boost Jam v3.1.12 or above. This is a build utility like make based on Perforce Jam. Download the ntx86 version. It's a small download of about 120 KB. Latest version 3.1.16, can be downloaded from [ http://sourceforge.net/projects/boost ].

Hide

The following third-party, free libraries can be downloaded optionally, in order to support certain features of the Boost libraries that are not built by default. If you don't need a particular feature from among these, you need not download the library required for it.

Download Expat for Windows [latest version 2.0.1] - from http://sourceforge.net/projects/expat. Small download of around 535 K. This is a binary which needs to be installed on your build box. Needed to support GraphML vocabulary used by Boost Graph Library.

3.2.1 Build Procedure

Open a cmd shell.
Create a suitable directory for holding all the sources of individual libraries (Boost and others, if any). Make sure you don't have any spaces in its path name. This directory will henceforth be referred to as BOOST_BUILD_ROOT. On my system, I have chosen C:\src as the BOOST_BUILD_ROOT.

Set the following environment variable:
C:\src> set BOOST_BUILD_ROOT=C:\src
Change your current directory to BOOST_BUILD_ROOT, copy the source archive for Boost into BOOST_BUILD_ROOT and extract it in the current directory, doing the equivalent of "Extract here ...". If everything is successful, you should have the following directory:

%BOOST_BUILD_ROOT%\boost_<version>
HideOptional steps
Copy each of the source archives for zlib, libbz2 and icu into BOOST_BUILD_ROOT and extract each of them in the current directory, doing the equivalent of "Extract here ..." on each of the archives. If everything is successful, you should have the following directories:

%BOOST_BUILD_ROOT%\bzip2-<version>
%BOOST_BUILD_ROOT%\zlib-<version>
%BOOST_BUILD_ROOT%\icu

Copy the boost-jam Windows binary archive into BOOST_BUILD_ROOT and extract it in the current directory, doing the equivalent of "Extract here ...". If everything is successful, you should have the following directory.

%BOOST_BUILD_ROOT%\boost-jam-<version>-1-ntx86

For simplicity, rename %BOOST_BUILD_ROOT%\boost-jam-<version>-1-ntx86 to %BOOST_BUILD_ROOT%\bjam. Add this directory to your PATH environment variable.

C:\src> set PATH=%PATH%:%BOOST_BUILD_ROOT%\bjam
HideOptional steps
Double click expat-win32bin-<version>.exe to install Expat. During installation, modify the default installation path so that the files are installed at:
%BOOST_BUILD_ROOT%\Expat-<version>

Make sure there are no spaces in the directory name as in "Expat 2.0.1", and rename it to "Expat-2.0.1".
- After installation, the %BOOST_BUILD_ROOT%\Expat-<version>\Bin directory will contain the pre-built binaries. However, a better idea will be to build everything with the compiler of your choice - the one you will use for building Boost. For this, open the expat.dsw VC6 workspace under %BOOST_BUILD_ROOT%\Expat-<version>\Source. Depending on which compiler you intend to use to build Boost, could either open it in VC6 or in a more recent version of Visual C++.
HideOptional steps
Build the ICU library inside Visual Studio using the solution file allinone.sln present under %BOOST_BUILD_ROOT%\icu\allinone. Make sure that you build in both Debug and Release configurations.
The built binaries will be available under %BOOST_BUILD_ROOT%\icu\bin, and the static and import libraries will be available under %BOOST_BUILD_ROOT%\icu\lib. If you are using ICU version 3 or later, in order to build with Boost, you will need to rename a couple of libraries - icuin.lib to icui18n.lib, icuind.lib to icui18nd.lib, icudtd.lib to icudatad.lib, icuind.pdb to icui18nd.pdb and icudtd.pdb to icudatad.pdb.

Determine your toolset name, based on the compiler you're using. For Visual Studio, it is msvc. For GNU g++, it is, you guessed it - gcc.

If you have only one version of Microsoft Visual Studio installed, you could just specify msvc for the toolset. If you have multiple versions, then depending on which version you want to use for the build, you should try one of the following as the toolset name:

msvc-9.0 (for Visual Studio .NET 2008)
msvc-8.0 (for Visual Studio .NET 2005)
msvc-7.1 (for Visual Studio .NET 2003)
msvc-7.0 (for Visual Studio .NET 2002)
msvc-6.0 (for Visual Studio 6)

Define the following environment variables:
- set BOOST_BIN_ROOT=%BOOST_BUILD_ROOT%\boost-binary
Set the MS VC++ environment variables.
- For VC++ 6.0, run the batch file vcvars32.bat under <MSVC_Install_Dir>\Microsoft Visual Studio\VC98\Bin. <MSVC_Install_Dir> is typically C:\Program Files.
- For VC++ 7.0 and 7.1, run the batch file vcvarsall.bat under <MSVCS_Install_Dir>\Microsoft Visual Studio .NET 2002\VC or <MSVCS_Install_Dir>\Microsoft Visual Studio .NET 2003\VC.
- For VC++ 8.0 onwards, run the batch file vcvarsall.bat under <MSVCS_Install_Dir>\Microsoft Visual Studio <version>\VC where <version> is 8 or 9.0.
Change current directory to: %BOOST_BUILD_ROOT%\boost_1_35_0. Make sure that the environment variables you set earlier ((BZIP2_SOURCE, ZLIB_SOURCE, EXPAT_LIBPATH, EXPAT_INCLUDE, HAVE_ICU, ICU_PATH and BOOST_BIN_ROOT) are available in the cmd shell from where you fire the above command.

Make sure that the EXPAT_LIBPATH points to the release version of the Expat library.

set EXPAT_LIBPATH=%BOOST_BUILD_ROOT%\Expat-<version>\Source\win32-vc<VCversion>\Release

Fix your installation directory. Say C:\Program Files\Boost. To be on the safe side, figure out the DOS name of any directory which contains spaces, like Program Files. On all my systems it is PROGRA~1 and it may or may not be so on your systems. Set the following environment variable with something like:

set BOOST_INSTALL_DIR=C:\PROGRA~1\Boost

Finally, fire the following command to build the "release" variant:
bjam threading=multi variant=release link=shared toolset=msvc-9.0 --build-dir="%BOOST_BUILD_ROOT%\boost-binary" --prefix="%BOOST_INSTALL_DIR%" --without-python --without-mpi install

Reset any environment variables, like EXPAT_LIBPATH appropriately to the debug variant:
set EXPAT_LIBPATH=%BOOST_BUILD_ROOT%\Expat-<version>\Source\win32-vc<VCversion>\Debug

If you are using Boost 1.45 or later, there is one additional step that needs to be undertaken. You should not use a global bjam, instead build one from the Boost sources using a single script that's also provided with the sources. Do this:

dosprompt> cd %BOOST_BUILD_ROOT%
dosprompt> bootstrap.bat
dosprompt> .\bjam.exe <options above as explained>

Fire the following command to build the "debug" variant:
bjam threading=multi variant=debug link=shared toolset=msvc-9.0 --build-dir="%BOOST_BUILD_ROOT%\boost-binary" --prefix="%BOOST_INSTALL_DIR%" --without-python --without-mpi install

After the build, the build area can be cleaned of the intermediate files for each class of variants by replacing the "install" target with "clean" in the above commands.

We did not show the way to build static Boost libraries, and Boost libraries which link statically with the runtime. To create static libraries, simply replace link=shared with link=static in the above commands.

To build Boost libraries that link statically with the VC runtime, you have to just introduce an additional directive: runtime-link=static. Note that these libraries themselves can be either static or shared - but they always link statically with the VC Runtime libraries. Because Regex with ICU support necessarily links with ICU's runtime DLLs, the Regex library that links statically to the VC runtime cannot also link with the ICU DLLs. So ICU support is not available for Boost Regex which is statically linked to the VC Runtime. To account for this, you have to set HAVE_ICU and ICU_PATH environment variables to blank before you start the build - otherwise the build fails at the outset.

3.3 Building Boost on Linux (x86)

In order to build Boost 1.35 on GNU/Linux (on x86), you need to have the following software installed.

GNU gcc (g++) compiler version 3.4.x or above. The build exercise for this tutorial was done with GNU gcc (g++) compiler version 4.1.2 on OpenSUSE 10.2.
Boost Jam v3.1.12 or above. This is a build utility like make based on Perforce Jam. Download the version for linuxx86. It's a small download of about 65 KB. Latest version 3.1.16, can be downloaded from [ http://sourceforge.net/projects/boost ].

Hide

The following third-party, free libraries can be downloaded optionally, in order to support certain features of the Boost libraries. If you don't need a particular feature from among these, you need not download the library required for it.

Download Expat source archive [latest version 2.0.1] - from http://sourceforge.net/projects/expat. Small download of around 450 K. Needed to support GraphML vocabulary used by Boost Graph Library.

3.2.1 Build Procedure

Log on with a non-root account. The build should be done with a non-root account.
From the command prompt, create a suitable directory for holding all the sources of individual libraries (Boost and others, if any). Make sure you don't have any spaces in its path name. This directory will henceforth be referred to as BOOST_BUILD_ROOT. On my system, I have chosen ~/boost as the BOOST_BUILD_ROOT.

Set the following environment variable:

$ BOOST_BUILD_ROOT=~/boost # or whatever directory your created
$ export BOOST_BUILD_ROOT
Change your current directory to BOOST_BUILD_ROOT, copy the source archive for Boost into BOOST_BUILD_ROOT and extract it in the current directory. If everything is successful, you should have the following directory:

$BOOST_BUILD_ROOT/boost_<version>

On my system, this is how the extraction commands looked:
$ bzip2 -cd boost_1_35_0.tar.bz2 tar xf -
HideOptional steps
Copy each of the source archives for zlib, libbz2, icu and expat into $BOOST_BUILD_ROOT, change your current directory to $BOOST_BUILD_ROOT and extract each of them in the current directory. If everything is successful, you should have the following directories:

$BOOST_BUILD_ROOT/bzip2-<version>
$BOOST_BUILD_ROOT/zlib-<version>
$BOOST_BUILD_ROOT/icu
$BOOST_BUILD_ROOT/expat-<version>

On my system, this is how the extraction commands looked:

$ bzip2 -cd zlib-1.2.3.tar.bz2 tar xf -
$ gzip -cd bzip2-1.0.5.tar.gz tar xf -
$ unzip -o icu4c-4_0-src.zip -d .

Copy the boost-jam Linux binary archive into BOOST_BUILD_ROOT and extract it in the current directory. If everything is successful, you should have the following directory.

$BOOST_BUILD_ROOT/boost-jam-<version>-1-linuxx86

I extracted it this way:
$ gzip -cd boost-jam-3.1.16-1-linuxx86.tgz tar xf -

For simplicity, rename $BOOST_BUILD_ROOT/boost-jam-<version>-linuxx86 to $BOOST_BUILD_ROOT/bjam. Add this directory to your PATH environment variable.

$ PATH=$PATH:$BOOST_BUILD_ROOT/bjam
$ export PATH
HideOptional steps
Building expat:
- Change your current directory to $BOOST_BUILD_ROOT/expat-<version> directory and look for a file called configure. If it does not exist, run the following command:
  
  $ ./buildconf.sh
- Run the following commands to configure the build:
  $ ./configure --prefix=$BOOST_BUILD_ROOT/expat
  
  The argument --prefix=$BOOST_BUILD_ROOT/expat indicates that after building, the libraries, executables, include files, man pages, etc. should be installed under the directory $BOOST_BUILD_ROOT/expat. If you have write access to other standard directories for third-party installation like /opt, or you know the root password, then you could also do the following:
  
  $ ./configure --prefix=/opt/expat
- If the above step (configure) is successful, run the following commands to build and install the eXpat library.
  
  $ make
  $ make install
  
  If you overrode the prefix option during the configure step with a path which requires root access to write to, then run the following command to do the install itself:
  
  $ su -c "make install"
  
  This requires you to know the root password.
  
  This will build expat and install it to the designated directory ($BOOST_BUILD_ROOT/expat or /opt/expat).
HideOptional steps
Building ICU:
- Change your current directory to $BOOST_BUILD_ROOT/icu/source.
- Add execute permissions to a couple of scripts:
  $ chmod +x install-sh runConfigureICU configure config.sub mkinstalldir \
  config.guess config.status
  $ dox2unix install-sh runConfigureICU configure config.sub mkinstalldir \
  config.guess config.status
- Run the following command:
  
  $ ./runConfigureICU Linux --prefix=/opt/icu # if you have the root password, or write access to /opt
  or
  $ ./runConfigureICU Linux --prefix=$BOOST_BUILD_ROOT/icu # if you neither have the root password, nor write access to /opt
- Upon successful conclusion of runConfigureICU, run the following command:
  $ make
  $ make install
  or
  $ su -c "make install" # in case the installation target directory, set as prefix above, requires root access to write to

Determine your toolset name, based on the compiler you're using. For GNU g++, it is gcc.
Define the following environment variables:
- BOOST_BIN_ROOT=$BOOST_BUILD_ROOT/boost-binary
Change current directory to: $BOOST_BUILD_ROOT/boost_1_35_0.
Make sure that the environment variables you set earlier (BZIP2_SOURCE, ZLIB_SOURCE, EXPAT_LIBPATH, EXPAT_INCLUDE, HAVE_ICU, ICU_PATH and BOOST_BIN_ROOT) are available in the shell you are in.

Identify a location where you'd like to install the Boost libraries on your system. On my system, I chose /opt/boost, and because I have root access to this box, I could do the following, which is necessary:
```
$ su -c "mkdir /opt/boost"
$ su -c "chown arindam:devuser /opt/boost"
```
If you are using Boost 1.45 or later, there is one additional step that needs to be undertaken. You should not use a global bjam, instead build one from the Boost sources using a single script that's also provided with the sources. Do this:

$ cd $BOOST_BUILD_ROOT
$ ./bootstrap.sh
$ ./bjam <options above as explained>

Finally, fire the following command to build the "release" variant:
./bjam threading=multi variant=release link=shared toolset=gcc --build-dir=$BOOST_BIN_ROOT --prefix=/opt/boost --without-python --without-mpi install

Fire the following command to build the "debug" variant:
./bjam threading=multi variant=debug link=shared toolset=gcc --build-dir=$BOOST_BIN_ROOT --prefix=/opt/boost --without-python --without-mpi install

If you have python-devel and python-tk installed, then you need not add the --without-python directive. Th build process would then generate Boost.Python libraries as well.

After the build, the object files for each kind of variant can be cleaned by replacing the "stage" target with "clean" in the above commands.

3.4 Boost Binaries: What's in a name

If your build was successful, you should now have a set of DLLs and import libraries built from the source code. If you used the install target as in the examples above, then the libraries (DLLs, shared objects, import libraries, etc) should all be copied to some convenient location (like /opt/boost/lib or D:\Boost\lib). But the Boost libraries are created in an elaborate directory structure under $BOOST_BIN_ROOT/boost/bin.v2/libs, that needs some scrutiny.

A large number of the Boost libraries are source-only - in other words all the code in the library is in header files which get included in your own source code directly or through other headers. Needless to say, some of these are typically entirely template code. But a smaller yet significant number of Boost libraries are actually built as shared or static libraries, and need to be linked to your code if you want to use them. For each such library there is a directory created under $BOOST_BIN_ROOT/boost/bin.v2/libs, which goes by the name of the library. You will at least get the following directories:

date_time
filesystem
graph
iostreams
program_options
regex
serialization
signals
system
test
thread
wave

Since we did not choose to build Boost.Python and Boost.MPI, directories for these libraries will not be present. The directory structure under each of these directories looks a bit like this:

<library>/
---- build/
      ---- <toolset>/
            -------- <variant>/
                      -------- <threading-model>

- Assuming that we have used the Microsoft Visual Studio 9, the toolset will be msvc-9.0.
- We have built both debug and release variants.
- We have only built thread-aware libraries. So for the date_time library, based on the above structure, you will get the following directories.

date_time/
---- build/
      ---- msvc-9.0/
            ------- debug/
                     ------ threading-multi/
            ------- release/
                     ------ threading-multi/

Since we specified "link" as "shared", only DLLs (Windows) or .so.* (Linux) will be build. Of course on Windows, along with each DLL, and Import Library (.lib) for linking is also creared. The dlls, libs and so files are created under the <threading-model> directory which in the above case is threading-multi.

Each .dll, .lib or .so file that is created has a naming convention as well, that needs to be understood:

On Unix, each library name starts with "lib". On Windows only static libraries have a name starting with lib, while the import libraries for DLLs and DLLs themselves miss the lib prefix. Barring this, and the file extension, the rest of the naming convention is same on both Windows and Unix.

<library_name>-<toolset-tag>-<threading-tag>-<abi-tag>-<version>
- On Windows, this takes the form:
  
  <library_name>-<toolset-tag>[-<threading-tag>][-<abi-tag>]-<version>.dll
  or <library_name>-<toolset-tag>[-<threading-tag>][-<abi-tag>]-<version>.lib
  
  The parts within brackets [...] represent optional segments that need not be present in all cases.
- On Unix, this takes the form:
  
  lib<library_name>-<toolset-tag>-<threading-tag>-<abi-tag>-<version>.so[.<version>]

<library_name> - All library names start with boost_. Thus we have boost_date_time, boost_filesystem, etc.
<toolset-tag> need not be same as <toolset-name> - for the toolsets we have considered, it would be gcc (not g++) on Linux, or vc60, vc71, vc80, vc90, etc. on Windows.
<threading-tag> - For multi-threaded builds, it will be mt. For single threaded builds, this part does not appear in the name.
<abi-tag> - This is a string of one or more characters. For us, the characters of interest are s, g, d.
s - indicates that the library is statically linked to the C++ Standard Library and Runtime Library.
g - indicates that the debug versions of the standard and runtime support libraries are linked against. On a typical Windows installation you will get a debug version of the runtime libraries to link against, but this need not be the case on Unix boxes.
d - indicates all debug symbols are available in the library, no inlining and optimization has been done while building the code.

So the Debug version of the Boost.Regex library on Windows should be called: boost_regex-vc90-mt-gd-1_35.dll and it should be located under %BOOST_BIN_ROOT%\boost\bin.v2\libs\regex\build\msvc-9.0\debug\threading-multi.
The corresponding import library should be called boost_regex-vc90-mt-gd-1_35.lib.

On Linux, the Boost.Regex shared library should be called libboost_regex-gcc-mt-d-1_35.so.1.35.0 and should be located under $BOOST_BIN_ROOT/boost/bin.v2/libs/regex/build/gcc/debug/threading-multi.

On Windows, the Release version of the Boost.Date_Time library should be called boost_date_time-vc90-mt-1_35.dll and it should be located under %BOOST_BIN_ROOT%\boost\bin.v2\libs\date_time\build\msvc-9.0\release\threading-multi. The corresponding import library should be called boost_date_time-vc90-mt-1_35.lib.

On Linux, the Boost.Date_Time shared library should be called libboost_date_time-gcc-mt-1_35.so.1.35.0 and should be located under $BOOST_BIN_ROOT/boost/bin.v2/libs/date_time/build/gcc/release/threading-multi.

4. Using the Boost Libraries

This is a brief section which discusses the way you should set your development environment up to use the Boost headers and link to the libraries effectively. There are several issues that have to be handled - and primarily the fact that there are so many variants of these libraries often causes some confusion. Moreover, there are different issues on Windows and non-Windows systems, so we have separate sections below, addressing these issues.

4.1. Linking to Boost libraries on Windows

On Windows, auto-linking is supported by most compilers, and by default Boost config headers arrange for Boost libraries to be linked automatically to your code. This is very convenient and you should not override it and try to do manual linking (which is possible but inordinately tedious). However, you still have to understand how your linker options affect which libraries actually get linked.

On all supported versions of Visual Studio (which is 7.0 onwards), we use one of the following switches to indicate the kind of linkage we want:

/MD - Link dynamically with the multi-threaded C Runtime.

/MDd - Link dynamically with the debug version of the multi-threaded C Runtime.

/MT - Link statically with multi-threaded C Runtime.

/MTd - Link statically with the debug version of the multi-threaded C Runtime.

Depending on which option from the above is chosen during compilation - a different version of a particular Boost library will be chosen for linking automatically. Let us take the example of Boost.Regex. If you check your installation directory, you will see the following DLLs/libs:

boost_regex-vc90-mt-1_35.dll
boost_regex-vc90-mt-1_35.lib
boost_regex-vc90-mt-gd-1_35.dll
boost_regex-vc90-mt-gd-1_35.lib

If you actually chose to build static variants of the Boost libraries (unlike what we did), you'd also see the following:

libboost_regex-vc90-mt-1_35.lib
libboost_regex-vc90-mt-gd-1_35.lib

Note that while the above are static libraries, they still link to the DLL versions of the MSVC Runtime libraries. Had they linked to the static versions, these would have been named:

libboost_regex-vc90-mt-s-1_35.lib
libboost_regex-vc90-mt-sgd-1_35.lib

These are static variants with static runtime-linking - yet another variant. We did not build these either.

4.1.2. Static linking

Now by default, all Boost libraries will link statically with your code. If you have built static libraries, that's fine. So by default, you'd end up linking to libboost_regex-vc90-mt-gd-1_35.lib in Debug builds and libboost_regex-vc90-mt-1_35.lib in Release builds.

4.1.2. Dynamic linking

But say, like we've done, you have chosen not to build any static linking variants of Boost. What do you do then? Simple - use a preprocessor define to indicate that you want to link dynamically to a particular library. In this case, you would define the symbol BOOST_REGEX_DYN_LINK using the construct:

/DBOOST_REGEX_DYN_LINK

on the command-line. If you want to use Dynamic linking exclusively, simple define BOOST_ALL_DYN_LINK instead. Beyond that, if you are linking to the Debug version of the VC Runtime, through the use of /MDd, you would link to boost_regex-vc90-mt-gd-1_35.dll via the Import Library boost_regex-vc90-mt-gd-1_35.lib. If you link to the Release / Retail vrsion of the VC Runtime, through the use of /MD, you would link to boost_regex-vc90-mt-1_35.dll via the Import Library boost_regex-vc90-mt-1_35.lib.

There is a notable exception to this rule - the Boost.Thread library. To link to the boost_thread DLL, define the preprocessor symbol BOOST_THREAD_USE_DLL on the command-line.

/DBOOST_THREAD_USE_DLL

To statically link, define the preprocessor symbol BOOST_THREAD_USE_LIB on the command-line.

/DBOOST_THREAD_USE_LIB

4.1.2. Static linking plus statically-linked runtime

If you use the /MT or /MTd switches, you are saying you want to link statically to the MSVC Runtime libraries. So in this case, you will by default link to libboost_regex-vc90-mt-sgd-1_35.dll (Debug) and libboost_regex-vc90-mt-s-1_35.dll (Release/Retail). Although not prohibited, linking dynamically to the Boost libraries under such circumstances is strictly discouraged. So never define BOOST_REGEX_DYN_LINK while using /MT or /MTd compiler directives.

[In pre-8.0 VC++, that is, upto Visual C++.NET 2003, the Microsoft C++ compiler actually accepted a set of switches - /ML and /MLd - to indicate static linking with a single-threaded runtime environment. On such environments, if you try to link your code with /ML, Boost library would try to link your code to boost_regex-vc90-sgd-1_35.dll or boost_regex-vc90-s-1_35.dll as the case may be. As of Visual C++ 2005 (version 8.0), these variants don't get built any longer.]

4.2. Linking to Boost libraries on Unix-like systems

On Unix, there is no auto-linking and there are no such high level distinctions as Debug and Release builds. The rough equivalent of a Debug build is a build with minimal to no compiler optimization, which includes debugging symbols in binaries. A rough equivalent of Release builds is a build with at least some compiler optimizations and no debugging symbols. Static linking with runtime is rarely used so the -s- and -sgd- variants of the Boost libraries are all but rarely useful.

An additional complexity to take into account is that on Windows, the Boost libraries silently link a lot of Windows standard libraries for you using Auto-linking. On Unices, you must link these manually and you have to know which ones to link. For all applications that use the multi-threaded variants of the Boost libraries, you have to link with libpthread. Similarly, if you are using Boost.Asio, you need to link with libsocket, (and on Sun Solaris, possibly libnsl, libresolv, etc). You will need to work these out and it's not difficult to do - at least after the first time you get a linker error. Also, unlike on Windows, the base name of a static and a shared library can be same on Unix, barring the extension (.a for static libraries and .so.* for shared libraries).

Based on the above facts and using gcc as a compiler, one could consider the following cases - once again using the regex library:

Shared linking with Boost debug libraries:

g++ -g regextest.cpp -o regextest -Ipath_to_boost_includes -Lpath_to_boost_libraries -lboost_regex-gcc41-mt-d -lpthread -licuuc -licudata -licui18n

Shared linking with Boost release libraries:

g++ -O2 regextest.cpp -o regextest -Ipath_to_boost_includes -Lpath_to_boost_libraries -lboost_regex-gcc41-mt -lpthread -licuuc -licudata -licui18n

Static linking with Boost debug libraries:
Here you really have two options. You could choose to link to the static Boost Regex library with static runtime links in which case you can have no ICU support:

g++ -g regextest.cpp -o regextest -Ipath_to_boost_includes -Lpath_to_boost_libraries -static -lboost_regex-gcc41-mt-sd -lpthread

The above links libpthread statically - which is usually not what you want - so fix that, we have to do this:

g++ -g regextest.cpp -o regextest -Ipath_to_boost_includes -Lpath_to_boost_libraries -Wl,-Bstatic -lboost_regex-gcc41-mt-sd -Wl,-Bdynamic -lpthread

Or you could choose to link to the static Boost Regex library with dynamic runtime links - in which case you can have ICU support:

g++ -g regextest.cpp -o regextest -Ipath_to_boost_includes -Lpath_to_boost_libraries -Wl,-Bstatic -lboost_regex-gcc41-mt-d -Wl,-Bdynamic -lpthread -licudata -licui18n -licuuc

Static linking with Boost release libraries:

g++ -O2 regextest.cpp -o regextest -Ipath_to_boost_includes -Lpath_to_boost_libraries -Wl,-Bstatic -lboost_regex-gcc41-mt -Wl,-Bdynamic -lpthread -licudata -licui18n -licuuc

If you notice above, the library names are not different between the shared and static linking cases. We do not need to define BOOST_REGEX_DYN_LINK or BOOST_ALL_DYN_LINK. The only differentiator is the -static directive. The specifics vary from one Unix to another, and even more between different compilers.

Of Indian authorship: pseudo-intellectual pretentiousness and plagiarism

2008-06-09T03:08:00.011+05:30

An interesting story on code theft.
While on Indian authorship, plagiarism and stuff, I'd love to share with you a couple of experiences I have had in the recent past.

I recently came across a book called "Encryption: Protecting your Data" by Whiz Kid Ankit Fadia. Now this kid might have been good, at least popular prejudices teach you to think he is - because he is at Stanford. But, I got the impression that his co-author, one babe called Jaya Bhattacharya, did most of the pages for this book - and at the beginning of the book, there is a section on this lass that showers lavish praises on her with lines like - "the constant guidance of Ankit Fadia made her one of the few successful candidates ... This course aroused her interest immensely in the field of Encryption ...". Interesting choice of words, one would have to say.

Here is a piece of code for base64 encoding, which appears in the book. Well actually the book does not say so, but this is the source from which they copied the code verbatim into the third chapter of their book (pages 28 - 33) - except for the header comments crediting the original author which were left out in the book. Apparently, this code is written only for Macs, and some of the headers like <appletdefs.h> and <iac.h> are for Mac too - coming from FrontierSDK - some framework exclusively for Macs. Nowhere in the book is anything about Macintosh's and Frontier SDK mentioned and it is not normal to sell a book on Mac programming in India (apart from some Objective C and Cocoa books) - let alone have one by an Indian author. Needless to say, they did not try to compile it even once - or else they would have seen the issues themselves. Otherwise, if we give the authors the benefit of the doubt that they did all their coding on a Mac, then at least that needs to be mentioned in the book.

Here is another specimen:

This is from the back cover of a book called Enterprise JavaBeans by Ivan Bayross (and family and friends). The above text should tell you everything - there is not much to read between the lines here.

So really, this is what it takes to write a book on computing in India.

Shalom !!!

2006-05-04T14:29:00.001+05:30

It was just before dawn that the El Al Boeing 767 finished its brief hover over the Mediterranean shoreline of Tel Aviv awaiting its turn on the Ben-Gurion tarmac. As it turned around and headed east, flying over apparently the tallest skyscraper in town, the flight first officer announced in Hebrew and English, that we would touch down at Ben Gurion Airport in about ten minutes. I looked at my watch, it showed 6-20 AM and momentarily, my mind went back into thinking what the folks back in India would be doing at this hour. That's a rather boring ponderable, and surely most would be in bed. But my early riser parents would by now have started their day and anxiously awaiting the phone call that I had promised to make "as soon as I land". It was my first international trip, and to Israel, of all places. It was to last more than a month, and for many a fellow Indian traveler, brought here by business, it was foreseeably going to be an anxious time in a land whose only palpable images were of war and conflict, suicide bombings and ambushes - all our pre-travel briefings and assurances notwithstanding. For me, honestly, it was a lot different than that.

In my growing years, on numerous occasions, my father spoke to me about the history of the Middle East, with real and anecdotal stories, including his own brush with a piece of Middle Eastern history (the Six-Day War of 1967). He seemed to have a passion for the Near East and Semitic history. Each time I heard him on this subject, I felt awed. It would be difficult to put down my finger on what inspired that awe - was it those images of the Intifada telecast by a Friday night weekly world news when Shyam Bhatia used to report for NDTV from the hot-bed of Semitic conflict. Or was it the story of the Jews building a nation against all odds and fortifying it like no other people have. Was it that a small sliver of land had, on the shoulders of a great and capable people, stood up to be a technology and military super-power. It was perhaps all of these to a certain extent and a lot more. Whatever it was, I could not help the excitement that rose in me as the plane landed on the runway and pulled up on the tarmac. As I stepped onto the aerobridge, I could feel it - I am in a new and alien land - and it could be a lot of fun.

After the obligatory and thankfully short immigration rituals, it was our turn to pickup the baggage and look for our escorts. Not even a day earlier, I had spoken to one Mr Bachar over phone, and he had promised he'd bring down his taxi for me and my two companions on that trip. As we waited for someone to appear with a placard carrying our names, so we could know it was Mr Bachar, I got 500 dollars changed to NIS (the New Israeli Shekel) and then looked on at the crowds of young people on the lounge. It didn't matter if it was 4-30 in the morning (by now I had swung the hands of my watch back by two-and-a-half hours) - the Israelis seemed to be having all the fun all the time. As I watched the crowd of young Israeli men and women mingling and embracing each other, celebrating their return to their cherished land from what ostensibly had been a trip to my homeland, I kind of got my first glimpse into Israeli life. They seemed to be the kind who'd have used all their alibis to have fun, at any hour. I was happy for them, and I felt a little more assured to be among a happy people.