7.1. A Few Examples

In the following sections we'll explore a few problems that are particularly well-suited to the use of views, which should give you a better feeling for what views are all about. We hope to show you that the idea of views is worth its conceptual overhead, and that these cases are either more efficient or more natural to code using views.

7.1.1. Comparing Values Computed from Sequence Elements

Let's start with a simple problem that will give you a taste of how views work:

Write a metafunction padded_size that, given an integer MinSize and a sequence Seq of types ordered by increasing size, returns the size of the first element e of Seq for which sizeof(e) >= MinSize.

7.1.1.1 A First Solution

Now let's try to solve the problem with the tools we've covered so far. The fact that we're searching in a sorted sequence is a clue we'll want to use one of the binary searching algorithms upper_bound or lower_bound at the core of our solution. The fact that we're looking for a property of the first element satisfying the property narrows the choice to lower_bound, and allows us to sketch an outline of the solution:

    template<class Seq, class MinSize>


    struct padded_size


      : mpl::sizeof_<                      // the size of


            typename mpl::deref<           // the element at


                typename mpl::lower_bound< // the first position


                    Seq


                  , MinSize


                  , comparison predicate   // satisfying...


                >::type


            >::type


        >


    {};

In English, this means "return the size of the result of the element at the first position satisfying some condition," where some condition is determined by the comparison predicate passed to lower_bound.

The condition we want to satisfy is sizeof(e) >=MinSize. If you look up lower_bound in the MPL reference manual you'll see that its simple description doesn't really apply to this situation:

Returns the first position in the sorted Sequence [i.e. Seq] where T [i.e., MinSize] could be inserted without violating the ordering.

After all, Seq is ordered on element size, and we don't care about the size of the integral constant wrapper MinSize; we're not planning to insert it. The problem with this simple description of lower_bound is that it's geared towards homogeneous comparison predicates, where T is a potential sequence element. Now, if you read a bit further in the lower_bound reference you'll find this entry:

    typedef lower_bound< Sequence, T, Pred >::type i;

Return type: A model of Forward Iterator

Semantics: i is the furthermost iterator in Sequence such that, for every iterator j in

    [begin<Sequence>::type, i),


    apply<Pred, deref<j>::type, T >::type::value

is true.

In English, this means that the result of lower_bound will be the last position in Sequence such that the predicate, applied to any element at a prior position and T, yields true. This more precise description seems as though it may work for us: We want the last position such that, for all elements e at prior positions, sizeof(e) <MinSize::value. Therefore, the predicate will be:

    mpl::less<mpl::sizeof_<_1>, _2>

Inserting the predicate into our complete metafunction, we are left with:

    template<class Seq, class MinSize>


    struct padded_size


      : mpl::sizeof_<


            typename mpl::deref<


                typename mpl::lower_bound<


                    Seq


                  , MinSize


                  , mpl::less<mpl::sizeof_<_1>, _2>


                >::type


            >::type


        >


    {};

7.1.1.2 Analysis

Now let's take a step back and look at what we just did. If you're like us, your code-quality spider sense has started tingling.

First of all, writing such a simple metafunction probably shouldn't require us to spend so much time with the MPL reference manual. In general, if you had a tough time writing a piece of code, you can expect maintainers to have an even harder time trying to read it. After all, the code's author at least has the advantage of knowing her own intention. In this case, the way that lower_bound deals with heterogeneous comparisons and the order of arguments to its predicate demanded significant study, and it probably won't be easy to remember; it seems unfair to ask those who come after us to pore through the manual so they can understand what we've written. After all, those who come after may be us!

Secondly, even if we set aside the need to consult the reference manual, there's something odd about the fact that we're computing the size of sequence elements within the lower_bound invocation, and then we're again asking for the size of the element at the position lower_bound returns to us. Having to repeat oneself is irksome, to say the least.

7.1.1.3 A Simplification

Fortunately, that repetition actually provides a clue as to how we might improve things. We're searching in a sequence of elements ordered by size, comparing the size of each one with a given value and returning the size of the element we found. Ultimately, we're not at all interested in the sequence elements themselves: we only care about their sizes. Furthermore, if we could do the search over a sequence of sizes, we could use a homogeneous comparison predicate:

    template<class Seq, class MinSize>


    struct padded_size


      : mpl::deref<


            typename mpl::lower_bound<


                typename mpl::transform<


                    Seq, mpl::sizeof_<_>


                 >::type


              , MinSize


              , mpl::less<_,_>


            >::type


        >


    {};

In fact, mpl::less<_,_> is already lower_bound's default predicate, so we can simplify the implementation even further:

    template<class Seq, class MinSize>


    struct padded_size


      : mpl::deref<


            typename mpl::lower_bound<


                typename mpl::transform<


                    Seq, mpl::sizeof_<_>


               >::type


              , MinSize


            >::type


     >


    {};

Naturallysince this chapter is building a case for viewsthere's a problem with this simplified implementation too: it's inefficient. While our first implementation invoked mpl::sizeof_ only on the O(log N) elements visited by lower_bound during its binary search, this one uses transform to greedily compute the size of every type in the sequence.

7.1.1.4 Fast and Simple

Fortunately, we can have the best of both worlds by turning the greedy size computation into a lazy one with transform_view:

    template<class Seq, class MinSize>


    struct first_size_larger_than


      : mpl::deref>


            typename mpl::lower_bound<


                mpl::transform_view<Seq, mpl::sizeof_<_> >


              , MinSize


            >::type


        >


    {};

TRansform_view<S,P> is a sequence whose elements are identical to the elements of transform<S,P>, but with two important differences:

If the approach we've taken seems a little unfamiliar, it's probably because people don't usually code this way in runtime C++. However, once exposed to the virtues of laziness, you quickly discover that there is a whole category of algorithmic problems similar to this one, and that solving them using views is only natural, even at runtime.^[2]

^[2] See the History section at the end of this chapter for some references to runtime views libraries.

7.1.2. Combining Multiple Sequences

Only one compile-time sequence building algorithm, TRansform, has direct support for operating on pairs of elements from two input sequences. If not for its usefulness, this nonuniformity in the library design could almost be called an aesthetic wart: It's merely a concession to convenience and consistency with the STL. For other kinds of operations on multiple sequences, or to transform three or more input sequences, we need a different strategy.

You could code any new multi-sequence algorithm variant "by hand," but as you can probably guess, we'd rather encourage you to reuse some MPL tools for that purpose. There's actually a component that lets you use your trusty single-sequence tools to solve any parallel N-sequence problem. MPL's zip_view transforms a sequence of N input sequences into a sequence of N-element sequences composed of elements selected from the input sequences. So, if S is [s₁, s₂, s₃ ...], T is [t₁, t₂, t₃ ...], and U is [u₁, u₂, u₃ ...], then the elements of zip_view<vector<S,T,U> > are [[s₁, t₁, u₁ ...], [s₂, t₂, u₂ ...], [s₃, t₃, u₃ ...] ...].

For example, the elementwise sum of three vectors might be written:

    mpl::transform_view<


        mpl::zip_view<mpl::vector<V1,V2,V3> >


      , mpl::plus<


            mpl::at<_, mpl::int_<0> >


          , mpl::at<_, mpl::int_<1> >


          , mpl::at<_, mpl::int_<2> >


        >


    >

That isn't too bad, but we have to admit that unpacking vector elements with mpl::at is both cumbersome and ugly. We can clean the code up using MPL's unpack_args wrapper, which transforms an N-argument lambda expression like mpl::plus<_,_,_> into a unary lambda expression. When applied to a sequence of N elements,

    mpl::unpack_args<lambda-expression>

extracts each of the sequence's N elements and passes them as consecutive arguments to lambda-expression.

Whew! That description is a bit twisty, but fortunately a little code is usually worth 1,000 words. This equivalent rewrite of our elementwise sum uses unpack_args to achieve a significant improvement in readability:

    mpl::transform_view<


        mpl::zip_view<mpl::vector<V1,V2,V3> >


      , mpl::unpack_args<mpl::plus<_,_,_> >


    >

7.1.3. Avoiding Unnecessary Computation

Even if views don't appeal to you conceptually, you should still use them to solve problems that can benefit from their lazy nature. Real-world examples are numerous, so we'll just supply a few here:

    // does seq contain int, int&, int const&, int volatile&,


    // or int const volatile&?


    typedef mpl::contains<


        mpl::transform_view<


            seq


          , boost::remove_cv< boost::remove_reference<_> >


        >


      , int


    >::type found;





    // find the position of the least integer whose factorial is >= n


    typedef mpl::lower_bound<


        mpl::transform_view< mpl::range_c<int,0,13>, factorial<_1> >


      , n


    >::type::base number_iter;





    // return a sorted vector of all the elements from seq1 and seq2


    typedef mpl::sort<


        mpl::copy<


            mpl::joint_view<seq1,seq2>


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


        >::type


    >::type result;

The last example above uses joint_view, a sequence consisting of the elements of its arguments "laid end-to-end." In each of these cases, the use of lazy techniques (views) saves a significant number of template instantiations over the corresponding eager approach.

7.1.4. Selective Element Processing

With filter_view, a lazy version of the filter algorithm, we can process a subset of a sequence's elements without building an intermediate sequence. When a filter_view's iterators are incremented, an underlying iterator into the sequence "being viewed" is advanced until the filter function is satisfied:

    // a sequence of the pointees of all pointer elements in Seq


    mpl::transform_view<


        mpl::filter_view< Seq, boost::is_pointer<_1> >


      , boost::remove_pointer<_1>


    >