Section 6.6. Sequence Building Algorithms

6.6. Sequence Building Algorithms

All of MPL's sequence building algorithms follow the same pattern. It's a little bit elaborate, but as a result the algorithms are extremely easy to use. The pattern is as follows, for any sequence building algorithm xxxx.

There is a corresponding algorithm, reverse_xxxx, which accepts the same arguments but operates on input sequence elements in reverse order. We call xxxx and reverse_xxxx counterpart algorithms.
The algorithm's last argument is an optional inserter.
If the inserter is not specified:
If the first sequence argument Seq is back-extensible, the result is as if
```
    mpl::back_inserter<mpl::clear<Seq>::type>
```
had been passed as the inserter.
Otherwise, the result is as if the counterpart algorithm had been invoked with
```
    mpl::front_inserter<mpl::clear<Seq>::type>
```
as the inserter.

Let's see how this plays out in practice. In the following examples, v123 indicates a type with "vector properties" equivalent to mpl::vector_c<int, 1,2,3>. Similarly, 1876 indicates a type equivalent to mpl::list_c<int, 8,7,6>.



    // starting sequences


    typedef mpl::vector_c<int, 1, 2, 3> v123;


    typedef mpl::list_c<int, 1, 2, 3>   l123;





    // transformation


    typedef mpl::plus<_1,mpl::int_<5> > add5;





    // using the default inserters


    typedef mpl::transform<v123, add5>::type          v678;


    typedef mpl::transform<l123, add5>::type          l678;


    typedef mpl::reverse_transform<v123, add5>::type  v876;


    typedef mpl::reverse_transform<l123, add5>::type  l876;

Thus, the simple no-inserter forms produce the expected result for both front-extensible and back-extensible sequences. In order to use the versions with inserters, though, we have to be aware of both the algorithm's traversal direction and the properties of the sequence we're building:



    // this inserter is equivalent to the default


    typedef mpl::transform<


        v123, add5, mpl::back_inserter<mpl::vector<> >


    >::type                                            v678;





    // also equivalent to the default


    typedef mpl::reverse_transform<


        l123, add5, mpl::front_inserter<mpl::list<> >


    >::type                                            l678;





    // properties of input sequence don't affect the result


    typedef mpl::reverse_transform<


        v123, add5, mpl::front_inserter<mpl::list<> >


    >::type                                            l678;

The inserter used in building a new sequence should always be determined by the front- or back-extensibility of the result sequence. The library's default inserter selection follows the same rule; it just happens that the properties of the result sequence when there is no user-supplied inserter are the same as those of the input sequence.

Table 6.2 summarizes the sequence building algorithms. Note that neither the reverse_ forms nor those with the optional inserter arguments are listed, but it should be possible to deduce their existence and behavior from the description above. They are also covered in detail in the MPL reference manual. We should note that copy and reverse are exceptions to the naming rule: They are reversed versions of one another, and there is neither a reverse_copy nor a reverse_reverse algorithm in the library.

Table 6.2. Sequence Building Algorithms
Metafunction
Result::type
mpl::copy<seq>
The elements of seq.
mpl::copy_if<seq, pred>
The elements of seq that satisfy predicate pred.
mpl::remove<seq, T>
A sequence equivalent to seq, but without any elements identical to T.
mpl::remove_if<seq, pred>
Equivalent to seq, but without any elements that satisfy predicate pred.
mpl::replace<seq, old, new>
Equivalent to seq, but with all occurrences of old replaced by new.
mpl::replace_if<seq, pred, new>
Equivalent to seq, but with all elements satisfying pred replaced by new.
mpl::reverse<seq>
The elements of seq in reverse order.
mpl::transform<seq, unaryOp>
mpl::transform<seq1, seq2, binaryOp>
The results of invoking unaryOp with consecutive elements of seq, or of invoking binaryOp with consecutive pairs of elements from seq1 and seq2.
mpl::unique<seq>
mpl::unique<seq, equiv>
The sequence composed of the initial elements of every subrange of seq whose elements are all the same. If the equivalence relation equiv is supplied, it is used to determine sameness.

The sequence building algorithms all have linear complexity, and all return a sequence of the same type as their first input sequence by default, but using an appropriate inserter you can produce any kind of result you like.

Functional Algorithms Under Aliases

Many of these sequence building algorithms, whose names are taken from similar STL algorithms, actually originated in the functional programming world. For example, the two-argument version of transform is known to functional programmers as "map," the three-argument TRansform is sometimes called "zip_with," and copy_if is also known as "filter."

Because we've left the reverse_ algorithms out of Table 6.2 it's only fair that we point out that the form of unique that accepts an equivalence relation is, well, unique among all of the sequence building algorithms. The reverse_ forms of most algorithms produce the same elements as the normal forms do (in reverse order), but the elements of sequences produced by unique and reverse_unique for the same arguments may differ. For example:



    typedef mpl::equal_to<


        mpl::shift_right<_1, mpl::int_<1> >


      , mpl::shift_right<_2, mpl::int_<1> >


    > same_except_last_bit;                    // predicate





    typedef mpl::vector_c<int, 0,1,2,3,4,5> v;





    typedef unique<


         v, same_except_last_bit


    >::type                      v024;          // 0, 2, 4





    typedef reverse_unique<


         v, same_except_last_bit


    >::type                      v531;          // 5, 3, 1