# The Boost MPL Library

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

- A. Gurtovoy, D. Abrahams, The Boost C++ Metaprogramming Library, March 2002 | [as single .html]
- Reference documentation
  1. Sequences
  2. Iterators
  3. Algorithms
  4. Metafunctions
  5. Categorized index

## 2. Sources

The latest library sources are available from:

- The boost CVS, `mpl_v2` branch (`cvs update -P -rmpl_v2 boost/mpl boost/type_traits libs/mpl`)
- From here - http://www.mywikinet.com/mpl/mpl_23_jul_02.zip

The library also requires the latest version of Boost Preprocessor library, that can be also obtained from boost CVS or from here - http://www.mywikinet.com/mpl/preprocessor_19_jul_02.zip.

A full archive that contains the library itself + all its dependencies - and therefore can be installed over a clean Boost 1.28 distribution - is available from here - http://www.mywikinet.com/mpl/mpl_23_jul_02_full.zip.

## 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/

[SAL] Boost Static Assert library, http://www.boost.org/libs/static_assert/static_assert.htm

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