The Boost Library; Overview, Code, Applications

[Cuchulainn]

An Introduction to the Boost Library

C++ continues to evolve and already STL is part of the official standard. We would like to discuss some new developments that are taking place and in particular we give an overview of the boost library (www.boost.org), a suite of useful C++ libraries containing functionality in the form of template classes:



Multiarray: defines a generic interface to multidimensional containers

Random numbers: contains a number of classes for generators and statistical distributions

Property map: classes that embody key-value pairs and definition of the corresponding access (for example read and write)

Smart pointers: objects that store pointers to dynamically allocated (heap) objects

Graph library: a C++ library implementing graphs, networks and related graph algorithms



The authors (as well as many other software developers) have developed a subset of the functionality contained in these libraries. For example, in Duffy 2004 and Duffy 2006 we have implemented a template Property Map class with properties similar to that in boost; furthermore, we have created classes for two-dimensional matrices and three-dimensional tensors using nested STL classes. If we were to build such classes again, we would choose to use the boost library as underlying substrate.

We give a short description of the functionality in the above libraries. At this stage we avoid dealing with the C++ details on how to use these libraries in an application (they will be discussed later). We summarise each library as a list of features:



Multiarray

Array classes for n-dimensional data

Accessing the elements of array using () and [] operators

Creating views of an array having the same or less dimensions

Determining storage ordering of data (C-style, Fortran-style or user-defined)

Defining or changing array index (zero is default)

Changing an array?s shape

Resizing an array (increasing or decreasing the extent of a dimension in an array)



Random Numbers

Linear congruential generators

Mersenne Twister generator

Lagged Fibonacci generators

Classes for continuous statistical distributions

Classes for discrete statistical distributions



Property Maps

Key-value pair concept

Readable and writable data

Support for built-in C++ data types

Applicability to Boost Graph Library (BGL)



Smart Pointers

Sole ownership to single objects and arrays

Shared ownership of objects and arrays

Shared ownership of objects with embedded reference counting



The gradual introduction of these features in applications will promote the reliability, maintainability and efficiency of your software. We shall see next to use these libraries and to apply them to the Monte Carlo method and other applications in finance.

In the next blogs we shall give some examples in C++ and applications to the Monte Carlo method.

[Cuchulainn]

QUESTION: Is boost used a lot in applications?



I am examining a number of the libraries with a view to using them rather than my own, for example just like 7 years ago we replace home-grown template libraries (yes, we made a template list class at the time ) by the STL.



Due to the dismal lack of decent documentation it takes a while to find out what is going on. On documentation , the big exception is the BGL graph library.



An interesting library is multi-array and the jury is out at the moment; some of its accessing functions are slower than my own libs while I cannot see how they handle big matrices, e.g. 300X300X300X300 in memory, and how it works for paralell programs.



It took STL more than 10 years to be accepted and tested fully, I wonder on which part of the curve boost is?



To answer your Q, the smart ptr is used a lot I believe but am not sure about the others; it's always a case of early adopters then it becomes mainstream and so on.

[Cuchulainn]

400 pages on dates and times!



http://www.crystalclearsoftware.com/lib ... e_time.pdf

[Cuchulainn]

Here is a summary of the main libraries in boost and a short description of what they do. Roadmap for boost library

[Cuchulainn]

This is a short overview of some reasons for using boost. The follow-up posts will discuss each library in turn.



//



Using the boost library offers a number of advantages:



. Functionality: the library has functionality for many of the data structures and algorithms that we can directly use in applications. It is suitable for scientific and engineering applications and in particular it is already popular with quantitative developers. If boost does not have the functionality you need you can consider writing new code yourself or using a (possibly proprietary) third-party software product. Finally, the interfaces are consistent and standardised.

. Usability: boost is easy to install, use and apply in your applications. It uses templates and many of the design techniques and patterns.

. Efficiency: boost uses templates and compile-time structures. This makes it very efficient because all data and object types are known before the program starts (that is, run-time). The concepts in the object-oriented paradigm ? such as subtype polymorphism ? are used sparingly if not at all.

. Maintainability: the burden of maintaining, debugging and extending the boost library has been removed from the user?s shoulders to the developers of the boost library. New improved versions of the library can be downloaded from the boost Web site.

. Portability: the boost library is vendor-independent and operating-system independent. This means that you can port Windows applications to linux applications with minimal effort, for example.

We now give an overview of the features in the boost library; first, we discuss smart pointers in detail because it is vital to use them if you wish to write reliable C++ applications.

[Cuchulainn]

Here is a chapter on an intro to boost (from forthcoming Monte Carlo book).

[Cuchulainn]

The boost.uBLAS library supports vector and matrix data structures and basic linear operations on these structures. The syntax closely reflects mathematical notation because operator overloading is used to implement these operations. Furthermore, the library uses expression templates to generate efficient code. The library has been influenced by a number of other libraries such as BLAS, Blitz++, POOMA and MTL and the main design goals are:



Use mathematical notation whenever appropriate

Efficiency (time and resource management)

Functionality (provide features that appeal to a wide range of application areas)

Compatibility (array-like indexing and use of STL allocators for storage allocation)



The two most important data structures represent vectors and matrices. A vector is a one-dimensional structure while a matrix is a two-dimensional structure. We can define various vector and (especially) matrix patterns that describe how their elements are arranged in memory; examples are dense, sparse, banded, triangular, symmetric and Hermitian. These patterned matrices are needed in many kinds of applications and the can be used directly in code without you having to create them yourself. Furthermore, we can apply primitive operations on vectors and matrices:



Addition of vectors and matrices

Scalar multiplication

Computed assignments

Transformations

Norms of vectors and matrices

Inner and outer products



We can use these operations in code and applications. Finally, we can define subvectors and submatrices as well as ranges and slices of vectors and matrices.

Vectors and matrices are fundamental to scientific and engineering applications and having a well-developed library such as boost.Tuple with ready-to-use modules will free up developer time. Seeing that matrix algebra consumes much of the effort in an application we expect that the productivity gains will be appreciable in general.



Here ia a '101' example:



// Lower and upper triangular matrices

signed n = 3;

triangular_matrix<double> mL (n, n);

for (unsigned i = 0; i < mL.size1 (); ++i)

{

for (unsigned j = 0; j <= i; ++j)

{

mL (i, j) = double(i);

}

}

std::cout << mL << std::endl;





// Dense matrix

long M = 10;

long N = 20;

matrix<double> mDense(M, N);

for (unsigned i = 0; i < mDense.size1 (); ++i)

{

for (unsigned j = 0; j < mDense.size2 (); ++ j)

{

mDense(i, j) = double(i + j);

}

}



There are many applications of this library to computational finance, for example PDE/FDM, Monte Carto and calibration/optimisation problems.

[bojan]

Boost.Foreach is a library that makes the syntax of iterating over elements in a sequence simpler and more readable. Even though it offers no functionality over and above a simple ``for`` loop it significantly reduces the need for repetitive code and improves the clarity of the remaining code.



HTMLized article http://www.bnikolic.co.uk/boostqf/foreach.html



or below as plain text

Code: Select all


Boost.Foreach

-------------



Boost.Foreach is a library that makes the syntax of iterating over

elements in a sequence simpler and more readable. Even though it

offers no functionality over and above a simple ``for`` loop it

significantly reduces the need for repetitive code and improves the

clarity of the remaining code. The simplest example of usage is:

 

.. sourcecode:: cpp

 

  /// Define a vector of 10 elements all with value 1.0

  std::vector<double> v(10,1.0);

  /// Add 3.0 to each element

  BOOST_FOREACH(double &x, v)

  {

    x+= 3.0;

  }



The key features of the library are:



* Easy iteration over most types of sequences, including all STL

  containers, strings, and objects that define ``begin()`` and

  ``end()`` methods



* The variable to which the elements of the sequence are bound can be

  a reference, allowing modification of the elements



* Negligible overheads due to careful design:



  * No virtual calls



  * No function pointers



  * No unnecessary copies of variables



The usage of this library is recommended where normally you would have

created a ``for`` loop with an iterator that then proceeds through a

sequence and processes the elements. More precisely, where you would

have used code of the form:



.. sourcecode:: cpp

   

   for(std::vector<myT>::iterator i= m.begin();

       i != m.end();

       ++i)

   {

       // operate on i

   }



You can use:



.. sourcecode:: cpp

   

      BOOST_FOREACH(myT  &i, m)

      {

        // operate on i

      }



Small overheads mean ``BOOST_FOREACH`` may be used throughout an

application and only might need to be avoided in the sections which

are identified as the most performance critical.





Here is a complete example, illustrating a potential simple

application in QF, namely generating a sequence of values iid from the

chi-squared distribution with one degree of freedom:



.. sourcecode:: cpp



    #include <vector>

    #include <cmath>



    #include <boost/random/normal_distribution.hpp>

    #include <boost/random/mersenne_twister.hpp>

    #include <boost/random/variate_generator.hpp>

    #include <boost/foreach.hpp>





    int main(void)

    {

      // Define a generator of Gaussian random numbers

      boost::variate_generator<boost::mt19937, boost::normal_distribution<> >

        generator(boost::mt19937(43),

                  boost::normal_distribution<>());



      // Define a vector of 10 elements

      std::vector<double> v(10);



      // Assign each element iid from chi-squared distribution with 1 dof

      BOOST_FOREACH(double &x, v)

      {

        x=std::pow(generator(),2);

      }



      // Print each element

      BOOST_FOREACH(double x, v)

      {

        std::cout<<x<<", ";

      }

    }

                 



[bojan]

The Boost.Variant library provides an easy mechanism to write algorithms that process objects that can be one of several types without using object-orientated design and a potentially complex polymorphic inheritance. The mechanism consists of a container (``boost::variant``) that stores an object that has one of a number of pre-determined types and a *visitor* pattern that allows the user to specify how these objects should be processed depending on actual type that is encountered.



HTMLized article http://www.bnikolic.co.uk/boostqf/variant.html



Or as plain text:

Code: Select all


Boost.Variant

-------------



The Boost.Variant_ library provides an easy mechanism to write

algorithms that process objects that can be one of several types

without using object-orientated design and a potentially complex

polymorphic inheritance. The mechanism consists of a container

(``boost::variant``) that stores an object that has one of a number of

pre-determined types and a *visitor* pattern that allows the user to

specify how these objects should be processed depending on actual type

that is encountered.



For example:



.. sourcecode:: cpp



   double sum(boost::variant<int,

                             const std::vector<int> &,

              const std::list<int> & > v)

   {

   ...

   }



declares a function that returns either the parameter passed (in case

it is of type ``int``) or the sum of the elements of a sequence that

is either a ``std::vector`` or a ``std::list``.





The key features of this library are:



* The actual type of object stored in the variant is determined at

  run-time, e.g.,:



  .. sourcecode:: cpp

 

     // ...

     boost::variant< std::vector<int> ,

                     std::list<int> > v;

     if (n > 10000)

        v=std::vector();

     else

        v=std::list();



  allows the use of either a ``vector`` or a ``list`` depending on the

  number of elements in the sequence which will only be known at

  run-time.





* The type of the variant object is guaranteed to be one of the types

  supplied as parameters. For example, in:

 

  .. sourcecode:: cpp

 

     boost::variant<int, std::vector<int> > v;

 

  the object contained in ``v`` is guaranteed to be either of a type

  ``int`` or of the type ``std::vector<int>``



* Implementation uses no virtual calls and usually the objects are

  placed on the stack, ensuring high efficiency.



* An object of ``boost::variant`` type is best processed using the

  *visitor* concept, for which the library defines a class

  ``boost::static_visitor<>``. For example:



  .. sourcecode:: cpp 



     class sumv :

       public boost::static_visitor<double>

     {

     public:

       template<class T>

       double operator()(const T &v) const

       {

         typename T::value_type t=0;

         for(typename T::const_iterator i(v.begin());

             i != v.end();

             ++i)

         {

           t+=*i;

         }

         return t;

       }

     };

 

  defines a visitor that returns the sum of a standard-library

  compliant container object.

 

* Visitor classes are checked at *compile-time* to ensure that they

  can process all of the types present in the ``variant`` objects on

  which they are used.



Decision on when it is optimal to use the Boost.Variant library

instead of alternatives is somewhat subjective and depends on, amongst

other things, the anticipated future use of the code. However some

useful rules-of-thumb can be provided:



* If the type of object that will be stored can be determined at

  *compile-time* then you **should not** use ``variant`` but rather

  plain templates



* If it is necessary to be able to add further possible types to be

  stored in the object after compilation and/or without modification

  of the code than you can not use ``variant`` and must use

  polymorphic inheritance -- this is what it is designed to do



* Conversely, if a code is not part of the public interface and only a

  small number of possible types is required, use of ``variant`` is

  both concise and efficient





Here is a complete example showing run-time selection of container to

be used in a program:



.. sourcecode:: cpp 



   #include <vector>

   #include <list>

   #include <iostream>

   #include <boost/variant.hpp>

   #include <boost/lexical_cast.hpp>



   class sumv :

     public boost::static_visitor<double>

   {

   public:

     template<class T>

     double operator()(const T &v) const

     {

       typename T::value_type t=0;

       for(typename T::const_iterator i(v.begin());

           i != v.end();

           ++i)

       {

         t+=*i;

       }

       return t;

     }

   };





   int main(int argc, char **argv)

   {

     const size_t nelements = boost::lexical_cast<size_t>(argv[1]);



     boost::variant<std::vector<double>, std::list<double>  > v;

     

     if (nelements > 100)

     {

       v=std::vector<double>(nelements);

     }

     else

     {

       v=std::list<double>(nelements);

     }



     // Enter some elements into v according to application

     // ....

     //

     

     std::cout<<boost::apply_visitor( sumv(), v )

              <<std::endl;

   }





     

.. _Boost.Variant: http://www.boost.org/doc/libs/1_38_0/doc/html/variant.html       

   





           









[bojan]

The ``boost::lexical_cast<>`` is a small convenience library whichallows easy conversion between objects and their string representations. The typical use of this library is for conversion of numerical values encoded as character strings to their binary form.



HTMLized article: http://www.bnikolic.co.uk/boostqf/lexical_cast.html



Or plain text version:

Code: Select all


The ``boost::lexical_cast<>`` utility library

---------------------------------------------



The ``boost::lexical_cast<>`` is a small convenience library which

allows easy conversion between objects and their string

representations. The typical use of this library is for conversion of

numerical values encoded as character strings to their binary

form. The simplest example of usage is:



.. sourcecode:: cpp



    const char * inputstringvol = "0.05";

    const double vol = boost::lexical_cast<double>(inputstringvol);



The key features of this library are:



* Clear and convenient syntax



* Type-safety



* Conversion of user-defined types



* Exceptions are thrown if problems in the conversion are encountered



Here is a minimal program illustrating the key features:



.. sourcecode:: cpp



   #include <iostream>

   #include <boost/lexical_cast.hpp>



   void printTimesTwo(double x)

   {

     std::cout<<(2*x)

         <<std::endl;

   }



   int main(int argc, char **argv)

   {

     // Convert parameter 1 of the program and print double its value

     printTimesTwo(boost::lexical_cast<double>(argv[1]));



     // The following line would *not* compile because of the type

     // checking

     // std::string s=boost::lexical_cast<double>(argv[1]);



     // Demonstrate the exception mechanism

     try

     {

       // Try to conver parameter 0 which is program name

       printTimesTwo(boost::lexical_cast<double>(argv[0]));   

     }

     catch (const boost::bad_lexical_cast &bc)

     {

       std::cout<<"Caught an exception as expected: "

           <<std::endl

           <<"    "<<bc.what()

           <<std::endl;

     }

   }

     



The usage of this library is recommended in following cases:



* Whenever you would have used the ``C``-library functions ``ato{i,f,d}``



* When using the ``C++`` standard library routines would have made for

  longer and/or more obscure code. For example:



.. sourcecode:: cpp



    #include <iostream>

    #include <sstream>

    #include <boost/lexical_cast.hpp>



    double twice(const char * i)

    {

      return 2*boost::lexical_cast<double>(i);

    }



    double twice_old(const char * i)

    {

      std::stringstream s(i);

      double temp;

      s>>temp;

      return 2*temp;

    }



    int main(void)

    {

      std::cout<<twice("4.0")<<std::endl

          <<twice_old("5.0")<<std::endl;



    }

       



* When parsing input parameters to a program or input data files



Within the QF field a typical usage would be to convert a character

string passed from a cell within a spreadsheet into a numerical value.



[zeta]

folks; I'm porting chunks of octave/matlab to c++, boost will feature prominently.



any figures you know of that benchmark matrix algebra in boost vs x? I'm curious to see how it compares; if poorly I may roll my own class(es) and/or keep using TBCI -> http://plasimo.phys.tue.nl/TBCI/online- ... index.html

[Cuchulainn]

I am porting some of my linear algebra by using boost.uBlAS for the internal datastructures. See my previous post on this.



A few days ago I developed an early version of conjugate gradient method (improved by Bojan). It might be used as a test.



It's a v 0.51 version at the moment. But a start.





OO languages however have a bad reputation for their performance. The problem is that the straightforward implementation of operators for large dynamically allocated objects such as Vectors or Matrices results in lots of unecessary copying around of data in copy constructors and assignment operators.

Well, you don't do this 'straightforward'; use BLAS and expresssion templates. This is a NON-issue these days in my experience.

See how uBLAS does it.

[zeta]

thanks cuch, will start playing with boost.uBLAS...

[Cuchulainn]

In this chapter we discuss pattern-matching in text-processing applications. In particular, we discuss how boost supports regular expressions. A regular expression is a particular set of words or pattern of characters and we show how such patterns can be matched by regular expression parsers. In general terms we can state that this chapter concerns several issues related to text processing.

Some of the applications of the Regex library are:



Input validation (for example, requiring that input is numeric)

Pattern matching in text (determine if a regular expression matches a character sequence)

Searching (find a substring that matches a regular expression)

Text replacing (search for matches of a string and replace it by another string)

Parsing textual data into more structured forms (for example, extracting data from a HTML page for storage in a database)



Traditionally, C++ has limited support for manipulating regular expressions. The Regex library fills this gap. We also give an introduction to the boost String Algorithms Library which we see as complementing Regex.

[zeta]

this is great...



are there any examples of converting awk to boost.regex? For instance, one of the benefits of awk is the ability to change the field/record separator from

space/CR, is this possible in boost??