6.3. Inserters

There's another important difference between MPL and STL algorithms that is also a consequence of the functional nature of template metaprogramming. The family of "sequence-building" STL algorithms such as copy, transform, and replace_copy_if all accept an output iterator into which a result sequence is written. The whole point of output iterators is to create a stateful changefor example, to modify an existing sequence or extend a filebut there is no state in functional programming. How would you write into an MPL iterator? Where would the result go? None of our examples have used anything that looks remotely like an output iteratorinstead, they have simply constructed a new sequence of the same type as some input sequence.

Each of the STL's mutating algorithms can write output into a sequence whose type differs from that of any input sequence or, when passed an appropriate output iterator, it can do something completely unrelated to sequences, like printing to the console. The MPL aims to make the same kind of thing possible at compile time, allowing us to arbitrarily customize the way algorithm results are handled, by using inserters.^[4]

^[4] The name "inserter" is inspired by the STL's family of output-iterator-creating function adaptors that includes std::front_inserter and std::back_inserter.

An inserter is nothing more than a type with two type members:

• ::state, a representation of information being carried through the algorithm, and

• ::operation, a binary operation used to build a new ::state from an output sequence element and the existing ::state.

For example, an inserter that builds a new vector might look like:

    mpl::inserter<mpl::vector<>, mpl::push_back<_,_> >

where mpl::inserter is defined to be:

    template <class State, class Operation>


    struct inserter


    {


        typedef State state;


        typedef Operation operation;


    };

In fact, inserters built on push_back and push_front are so useful that they've been given familiar names: back_inserter and front_inserter. Here's another, more evocative way to spell the vector-building inserter:

    mpl::back_inserter<mpl::vector<> >

When passed to an MPL algorithm such as copy, it functions similarly to std:: back_inserter in the following STL code:

    std::vector<any> v; // start with empty vector


    std::copy(start, finish, std::back_inserter(v));

Now let's see how an inserter actually works by using mpl::copy to copy the elements of a list into a vector. Naturally, mpl::copy takes an input sequence in place of std::copy's input iterator pair, and an inserter in place of std::copy's output iterator, so the invocation looks like this:

    typedef mpl::copy<


        mpl::list<A, B, C>


      , mpl::back_inserter<mpl::vector<> >


    >::type result_vec;

At each step of the algorithm, the inserter's binary operation is invoked with the result from the previous step (or, in the first step, the inserter's initial type) as its first argument, and the element that would normally be written into the output iterator as its second argument. The algorithm returns the result of the final step, so the above is equivalent to:

    typedef





      mpl::push_back<           // >----------------+


                                //                  |


          mpl::push_back<       // >--------------+ |


                                //                | |


              mpl::push_back<   // >------------+ | |


                  mpl::vector<> //              | | |


                , A             //              | | |


              >::type           // first step <-+ | |


            , B                 //                | |


          >::type               // second step <--+ |


        , C                     //                  |


      >::type                   // third step <-----+





    result_vec;

Because it's very common to want to build the same kind of sequence you're operating on, MPL supplies default inserters for all of its sequence-building algorithms. That's why we were able to use transform so effectively without specifying an inserter.

Note that an inserter need not do anything that looks like insertion. The following example uses an inserter to sum the initial elements of each element in a sequence of sequences:

    typedef mpl::vector<


        mpl::vector_c<int, 1, 2, 3>


      , mpl::vector_c<int, 4, 5, 6>


      , mpl::vector_c<int, 7, 8, 9>


    > S;





    typedef mpl::transform<


        S                   // input sequence


      , mpl::front<_>       // transformation selects front element





      , mpl::inserter<


            mpl::int_<0>    // result starts with 0


          , mpl::plus<_,_>  // and adds each output element


        >


    >::type sum; // 0 + 1 + 4 + 7 == 12

Without the inserter, transform would build a vector consisting of the initial elements of each sequence in S; with the inserter, those initial elements are fed into mpl::plus<_,_>, starting with the initial value of mpl::int_<0>.