sequences.sgml

boost库提供标准的C++ API 配合dev c++使用,功能更加强大

What we've seen so far were sequences (and algorithms on sequences) of types. It is both possible and easy to manipulate compile-time <emphasis>values</> using the library as well. The only thing to remember is that in &Cxx;, class template non-type template parameters give us one more example of non-polymorphic behavior.  In other words, if one declared a metafunction to take a non-type template parameter (e.g. <literal>long</>) it's not possible to pass anything besides compile-time integral constants to it:
</>

<programlisting>
<![CDATA[
template< long N1, long N2 >
struct equal_to
{
    static bool const value = (N1 == N2);
};

equal_to<5,5>::value; // ok
equal_to<int,int>::value; // error!
]]>
</>

<para>
And of course this doesn't work the other way around either:
</>

<programlisting>
<![CDATA[
typedef mpl::list<1,2,3,4,5> numbers; // error!
]]>
</>

<para>
While this may be an obvious limitation, it imposes yet another dilemma on the library design: on the one hand, we don't want to restrict users to type manipulations only, and on the other hand, full support for integral manipulations would require at least duplication of most of the library facilities 

<footnote id="note.nontype"><para>Ideally, if going this route, all the templates should be re-implemented for every integral type - <literal>char</>, <literal>int</>, <literal>short</>, <literal>long</>, etc.
</></>

- the same situation as we would have if we had chosen to represent metafunctions as ordinary class templates. The solution for this issue is the same as well: we represent integral values by wrapping them in types

<footnote id="note.valuewrapping"><para>
The same technique was suggested by Czarnecki and Eisenecker in <citation><xref linkend="ref.CE00"></>.
</></>

. For example, to create a list of numbers one can write:
</>

<programlisting>
<![CDATA[
typedef mpl::list<
      mpl::int_c<1>
    , mpl::int_c<2>
    , mpl::int_c<3>
    , mpl::int_c<4>
    , mpl::int_c<5>
    > numbers;
]]>
</>

<para>
Wrapping integral constants into types to make them first-class citizens is important well inside metaprograms, 
where one often doesn't know (and doesn't care) if the metafunctions she is using operate on types, integral values, other metafunctions, or something else, like fixed-point or rational numbers (<literal>mpl::fixed_c</> and <literal>mpl::rational_c</>).
</>

<para>
But, from the user's perspective, the above example is much more verbose than the shorter, incorrect one. Thus, for the purpose of convenience, the library does provide users with a template that takes non-type template parameters, but offers a more compact notation:
</>

<programlisting>
<![CDATA[
typedef mpl::list_c<long,1,2,3,4,5> numbers;
]]></>

<para>
There is a similar <literal>vector</> counterpart as well:
</>

<programlisting>
<![CDATA[
typedef mpl::vector_c<long,1,2,3,4,5> numbers;
]]>
</>
</section>

<!-- ||||||||||||||||||||||||||||| subsection -->
<section id="sequences.variety">
<title>A variety of sequences</>

<para>
Previous efforts to provide generalized metaprogramming facilities for &Cxx; have always concentrated on <literal>cons</>-style type lists and a few core algorithms like <literal>size</> and <literal>at</>, which are tied to the specific sequence implementation. Such systems have an elegant simplicity reminiscent of the analogous functionality in pure functional Lisp. It is much more time-consuming to implement even a basic set of the sequence algorithms provided by equivalent run-time libraries (the STL in particular), but if we have learned anything from the STL, it is that tying those algorithms' implementations to a specific sequence implementation is a misguided effort!
</>

<para>
The truth is that there is no single <quote>best</> type sequence implementation for the same reasons that there will never be a single <quote>best</> runtime sequence implementation. Furthermore, there are <emphasis>already</> quite a number of type list implementations in use today; and just as the STL algorithms can operate on sequences which don't come from STL containers, so the MPL algorithms are designed to work with foreign type sequences.
</>

<para>
It may be an eye-opening fact for some that type lists are not the only useful compile-time sequence. Again, the need for a variety of compile-time containers arises for the same reasons that we have lists, vectors, deques, and sets in the &Cxx; standard library &mdash; different containers have different functional and performance characteristics which determine not only applicability and efficiency of particular algorithms, but also the expressiveness or verbosity of the code that uses them. While runtime performance is not an issue for &Cxx; metaprograms, compilation speed is often a significant bottleneck to advanced &Cxx; software development <citation><xref linkend="ref.Abr01"></>.
</>

<para>
The &MPL; provides five built-in sequences: <literal>list</>, <literal>list_c</> (really just a <literal>list</> of value wrappers), <literal>vector</>, a randomly-accessible sequence of fixed maximum size, <literal>vector_c</>, and <literal>range_c</>, a randomly-accessible sequence of consecutive integral values. More important, however, is its ability to adapt to arbitrary sequence types. The only core operations that a sequence is required to provide in order to be used with the library algorithms are <literal>begin&lt;&gt;</> and <literal>end&lt;&gt;</> metafunctions which "return" iterators into the sequence. As with the STL, it is the iterators which are used to implement most of the general-purpose sequence algorithms the library provides. Also, as with the STL, algorithm specialization is used to take advantage of implementation knowledge about particular sequences: many of the "basic" sequence operations such as <literal>back&lt;&gt;</>, <literal>front&lt;&gt;</>, <literal>size&lt;&gt;</>, and <literal>at&lt;&gt;</> are specialized on sequence type to provide a more efficient implementation than the fully generic version.
</>
</section>

<!-- ||||||||||||||||||||||||||||| subsection -->
<section id="sequences.unrolling">
<title>Loop/recursion unrolling</>

<para>
Almost coincidentally, loop unrolling can be as important to compile-time iterative algorithms as it is to runtime algorithms. To see why, one must first remember that all "loops" in &Cxx; metaprograms, are in fact, implemented with recursion, and that the template instantiation depth can be a valuable resource in a compiler implementation. In fact, Annex B of the &Cxx; standard (<citation><xref linkend="ref.ISO98"></>, annex B [limits]) <emphasis>recommends</> a minimum depth of 17 recursively nested template instantiations; but this is far too low for many serious metaprograms, some of which easily exceed the hard-coded instantiation limits of some otherwise excellent compilers. To see how this works in action, let's examine a straightforward implementation of the <literal>fold</> metafunction, which combines some algorithm state with each element of a sequence:
</>

<programlisting>
<![CDATA[
namespace aux {

// unspecialized version combines the initial state and first element
// and recurses to process the rest
template<
      typename Start
    , typename Finish
    , typename State
    , typename BinaryFunction
    >
struct fold_impl
  : fold_impl<
        typename Start::next
      , Finish
      , typename apply<
              BinaryFunction
            , State
            , typename Start::type
            >::type
      , BinaryFunction
      >
{
};

// specialization for loop termination
template<
      typename Finish
    , typename State
    , typename BinaryFunction
    >
struct fold_impl<Finish,Finish,State,BinaryFunction>
{
    typedef State type;
};

} // namespace aux

// public interface
template<
      typename Sequence
    , typename State
    , typename ForwardOp
    >
struct fold
    : aux::fold_impl<
        , typename begin<Sequence>::type
        , typename end<Sequence>::type
        , State
        , typename lambda<ForwardOp>::type
        >
{
};

]]>
</>

<para>
Although simple and elegant, this implementation will always incur at least as many levels of recursive template instantiation as there are elements in the input sequence.

<footnote id="note.unrolling1"><para>It could be much more, depending on the complexity of the <literal>apply&lt;...&gt;</> expression, whose depth is added to the overall recursion depth.
</></>

The library addresses this problem by explicitly "unrolling" the recursion. To apply the technique to our <literal>fold</> example, we begin by factoring out a single step of the algorithm. Our <literal>fold_impl_step</> metafunction has two results: <literal>type</> (the next state), and <literal>iterator</> (the next sequence position).
</>

<programlisting>
<![CDATA[
template<
      typename BinaryFunction
    , typename State
    , typename Start
    , typename Finish
    >
struct fold_impl_step
{
    typedef typename apply<
          BinaryFunction
        , State
        , typename Start::type
        >::type type;

    typedef typename Start::next iterator;
};
]]>
</>

<para>
As with our main algorithm implementation, we specialize for the loop termination condition so that the step becomes a no-op:
</>

<programlisting>
<![CDATA[
template<
      typename BinaryFunction
    , typename State
    , typename Finish
    >
struct fold_impl_step<BinaryFunction,State,Finish,Finish>
{
    typedef State type;
    typedef Finish iterator;
};
]]>
</>

<para>
Now we can now reduce <literal>fold</>'s instantiation depth by any constant factor N simply by inserting N invocations of <literal>fold_impl_step</>. Here we've chosen a factor of 4:
</>

<programlisting>
<![CDATA[
template<
      typename Start
    , typename Finish
    , typename State
    , typename BinaryFunction
    >
struct fold_impl
{
 private:
    typedef fold_impl_step<
        BinaryFunction
      , State
      , Start
      , Finish
      > next1;
    
    typedef fold_impl_step<
        BinaryFunction
      , typename next1::type
      , typename next1::iterator
      , Finish
      > next2;
    
    typedef fold_impl_step<
        BinaryFunction
      , typename next2::type
      , typename next2::iterator
      , Finish
      > next3;
    
    typedef fold_impl_step<
        BinaryFunction
      , typename next3::type
      , typename next3::iterator
      , Finish
      > next4;
    
    typedef fold_impl_step<
          typename next4::iterator
        , Finish
        , typename next4::type
        , BinaryFunction
        > recursion;

 public:
    typedef typename recursion::type type;
};
]]>
</>

<para>
The &MPL; applies this unrolling technique across all algorithms with an unrolling factor tuned according to the demands of the &Cxx; implementation in use, and with an option for the user to override the value.

<footnote id="note.unrolling2"><para>
This implementation detail is made relatively painless through heavy reliance on the Boost Preprocessor Library, so only one copy of the code needs to be maintained.
</></>

This fact enables users to push beyond the metaprogramming limits they would usually encounter with more naive algorithm implementations. Experiments also show a small (up to 10%) increase in metaprogram instantiation speed on some compilers when loop unrolling is used.
</>
</section>

</section>