Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Click here to view the latest version of this page.

THE BOOST MPL LIBRARY

Table of Contents

1. Preface
2. Sources
3. Mini-tutorial
3.1. Conventions used
3.2. Metafunctions
3.3. Compile-time if
3.4. apply_if
3.5. apply_if, part 2
4. Technical details
4.1. Physical structure
4.2. Dependencies
4.3. Portability
5. Acknowledgements
Bibliography

1. Preface

The MPL library is a C++ template metaprogramming framework of compile-time algorithms, sequences and metafunction classes. The two main documentation sources for the library is “the MPL paper”, and the library's reference documentation. If you haven't heard about the MPL before, we suggest you to start with the paper, and then move on to the reference documentation and the information in this document.

2. Sources

The latest library sources are available from the main trunk of the Boost CVS. Boost 1.30.0 distribution contains a stable version of the library as per March 12, 2003.

3. Mini-tutorial

3.1. Conventions used

The examples used through this tutorial use fully qualified names, e.g. std::vector instead of plain vector. Any unqualified name refers to a local entity defined in the example itself. The names from boost::mpl namespace are referred to using mpl namespace alias (e.g. mpl::apply instead of boost::mpl::apply), as if the following namespace alias definition were in effect:

namespace mpl = boost::mpl;

Note that the library offers a special header, boost/mpl/alias.hpp, including which gives you a rough equivalent of the above. Alternatively, you can always spell the namespace alias definition manually in each translation unit as needed (if you choose to use the shorter namespace notation at all).

3.2. Metafunctions

In MPL, the metaprogramming equivalent of a function is a class template containing a nested typedef member aptly named “type”:

// on the face of it, not very useful
template< typename T >
struct identity 
{
    typedef T type;
};

// perhaps more useful
template< typename T >
struct result_type 
{
    typedef typename T::result_type type;
};

“Invoking” a metafunction is as simple as instantiating the class template with particular template parameters (metafunction “arguments”) and accessing the result through the nested type member:

typedef identity<int>::type t1; // t1 == int
typedef result_type< std::unary_function<int,bool> >::type t2; // t2 == bool

3.3. Compile-time if

The most interesting template metaprograms often contain a lot of decision-making code. Some of conditional decisions/behavior can be handled directly by (partial) class template specialization or function overloading [Vel95a], [Ale00], but in general there is a need for a standalone library primitive that would allow one to choose between two types basing on a compile-time expression. In boost::mpl such primitive is called if_:

template< typename T >
struct heap_holder
{
 // ... 
 private:
    boost::scoped_ptr<T> m_object;
};

template< typename T >
struct stack_holder
{
 // ... 
 private:
    T m_object;
};

template< typename T >
struct can_be_on_stack
    : mpl::bool_c< (sizeof(T) <= sizeof(double)) >
{
};

// use 'if_' to choose where to store 'T' member
template< typename T >
struct lightweight
   : private mpl::if_<
          can_be_on_stack<T>
        , stack_holder<T>
        , heap_holder<T>
        >::type
{
   // ...
};

Note that the first template parameter of the if_ template is a type that should be a model of Integral Constant concept. The library also provides a less generic but sometimes more convenient form that accepts a condition in form of non-type bool template parameter:

template< typename T >
struct lightweight
   : private mpl::if_c<
          (sizeof(T) <= sizeof(double))
        , stack_holder<T>
        , heap_holder<T>
        >::type
{
   // ...
};

3.4. apply_if

In run-time C++, it is guaranteed that when we reach an if statement, only one branch will be executed. Executing the branch for which the result is not required would be unnecessary and inefficient. More importantly, frequently the non-required branch is invalid, and executing it would cause an error. For instance, the following code would be badly broken if both branches of the statement were evaluated:

void fun(giraffe* g)
{
    if (g)
        cout << g->name();
    else
        cout << "no giraffe";
}

In compile-time world, things are different. Which parameters to if_ template are instantiated is determined by the form of each template parameter and the corresponding language rules ([ISO98], section 14.7.1), not by the value of the compile-time expression being switched on. That means that if, in attempt to process a particular if_ construct, the compiler determines that one of its “branch” template parameters is ill-formed, it will issue a diagnostics even if the value of compile-time expression would lead to “choosing” the other, valid parameter type.

To clarify what we just said, here is a broken first attempt at writing a pointed_type metafunction, that when instantiated for a T that is either a plain pointer or a smart pointer, “returns” the pointed type:

template< typename T >
struct pointed_type
{
    typedef typename mpl::if_<
          boost::is_pointer<T>
        , typename boost::remove_pointer<T>::type
        , typename T::element_type // #1
        >::type type;
};

typedef pointed_type< std::auto_ptr<int> >::type int_ptr; // ok
typedef pointed_type<char*>::type char_ptr; // error in line #1!

If we try to compile the above, we will get something like this:

Error: name followed by "::" must be a class or namespace name

because the expression typename T::element_type is not valid in case of T == char*.

Here's what we need to do to make pointed_type work for plain pointers: 1 instead of instantiating our two potential results before passing them to if_, we need to write metafunctions that can be used to instantiate the results; then we can use if_ to choose a metafunction, and only then should we use that function to get the result.

boost::remove_pointer already is a metafunction. We just need to write an auxiliary function to return the element_type of a pointer type:

namespace aux {
template< typename T >
struct element_type
{
     typedef typename T::element_type type;
};
}

Now we can select the metafunction to call based on the result of boost::is_pointer, and then apply it to form the result:

template< typename T >
struct pointed_type
{
 private:
    // pick a metafunction
    typedef typename mpl::if_<
          boost::is_pointer<T>
        , boost::remove_pointer<T>
        , aux::element_type<T>
        >::type func_; // #1

 public:
    // apply the metafunction
    typedef typename func_::type type;
};

The key knowledge that makes the above viable is that in line #1 the compiler is guaranteed not to instantiate boost::remove_pointer<T> and aux::element_type<T> templates, - even although they are passed as actual arguments to the if_.

The described technique is so common in template metaprograms, that it makes sense to facilitate the selection of the nested type member by introducing a high level equivalent to if_ that will do func_::type operation as a part of its invocation. The MPL provides such a template - it's called apply_if. Using it, we can re-write the above code as simply as:

[
template< typename T >
struct pointed_type
{
    typedef typename mpl::apply_if<
          boost::is_pointer<T>
        , boost::remove_pointer<T>
        , aux::element_type<T>
        >::type type;
};

3.5. apply_if, part 2

Besides solving the “making the code compile” problem, the apply_if technique we've just learned can be also used to improve metaprogram efficiency.

Suppose we want to define a high-level wrapper around boost::remove_pointer traits template, which will strip the pointer qualification conditionally. We will call it remove_pointer_if:

template<
      typename Condition
    , typename T
    >
struct remove_pointer_if
{
    typedef typename mpl::if_<
          Condition
        , typename boost::remove_pointer<T>::type
        , T
        >::type type;
};

The above works the first time, but it's not the most optimal implementation. Similar to our previous examples, boost::remove_pointer<T> gets instantiated even if its result is never used. In the metaprogramming world compilation time is an important resource [Abr01], and it is wasted by unnecessary template instantiations.

Let's see what we need to substitute if_ by apply_if here. We already have one metafunction to pass to apply_if - boost::remove_pointer<T>, but we need a second one, - let's call it f, - such as f<T>::type == T. We could write this one ourselves, but fortunately MPL already provides us with a template that matches this exact definition - it's called identity. Applying this knowledge, we get:

template<
      typename Condition
    , typename T
    >
struct remove_pointer_if
{
    typedef typename mpl::apply_if<
          Condition
        , boost::remove_pointer<T>
        , mpl::identity<T>
        >::type type;
};

4. Technical details

4.1. Physical structure

The library provides you with a fine-grained header structure with one header per public component (class/function template), with the header named after the component; for example, boost::mpl::apply<> template is defined in the header boost/mpl/apply.hpp. This scheme both ensures that you don't pay for what you don't use in terms of compilation time/header dependencies, and frees you from memorizing/looking up header/component correspondence. Several composite headers for the entities that are likely to be used together (e.g. logical operations - logical_or, logical_and, etc.) are also provided. It allows one to avoid the burden of spelling many #include directives in programs that make an intensive use of the library facilities. 2

4.2. Dependencies

Besides boost/config.hpp header, the MPL heavily depends on two other Boost libraries - the Boost Preprocessor library [PRE], and the Type Traits library [TTL]. These dependencies are essential and cannot be eliminated. In addition to those, the boost/mpl/assert_is_same.hpp header depends on Boost Static Assert library [SAL]. The library tests and examples may depend on some additional Boost libraries, e.g. Boost Bind [BBL]; you don't have to have those unless you are interested in actually compiling the tests/examples (probably you are, though).

4.3. Portability

Below is the list of compilers the library has been tested with:

  • Microsoft Visual C++ 6.0, SP 5
  • Microsoft Visual C++ .NET (7.0)
  • Metrowerks CodeWariror 7.2/8.1
  • Intel C++ Compiler 5.0, 6.0
  • GCC 2.95.3-5
  • GCC 3.1
  • Comeau C/C++ 4.2.45/4.3.0
  • Borland C++ 5.5.1

An incomplete matrix of recent test compilation results is available from here - http://www.mywikinet.com/mpl/log.html.

5. Acknowledgements

Following is a list of people who in one or another way contributed to the library development. The list is work in progress!

David Abrahams, Emily Winch, Eric Friedman, Vesa Karvonen, Peter Dimov, Mat Marcus, Fernando Cacciola, Paul Mensonides, David B. Held, John Bandela, Arnaldur Gylfason, Hamish Mackenzie.

Copyright on this document. Copyright © 2002 Aleksey Gurtovoy, David Abrahams and Emily Winch.

Bibliography

[Abr01] David Abrahams and Carlos Pinto Coelho, Effects of Metaprogramming Style on Compilation Time, 2001

[Ale00] Andrei Alexandrescu, On Conversions between Types and Values, C/C++ Users Journal, October 2000

[BBL] Boost Bind library, http://www.boost.org/libs/bind/bind.html

[ISO98] ISO/IEC 14882:1998(E), Programming languages — C++, ISO/IEC, 1998

[PRE] Vesa Karvonen, Boost Preprocessor Metaprogramming library, http://www.boost.org/libs/preprocessor/doc/

[TTL] Boost Type Traits library, http://www.boost.org/libs/type_traits/

[Vel95a] Todd Veldhuizen, Using C++ template metaprograms, C++ Report, SIGS Publications Inc., ISSN 1040-6042, Vol. 7, No. 4, pp. 36-43, May 1995



1 It would be easy to implement pointed_type using partial specialization to distinguish the case where T is a pointer. if_ is used here to avoid creating a complicated example.

2 The Boost Preprocessor library [PRE] exposes a very similar physical organization; in fact, the libraries even share the common subdirectory naming (mpl/arithmetic <-> preprocessor/arithmetic, mpl/comparison <-> preprocessor/comparison, etc.).