|
|
5.11. Writing Your Own SequenceIn this section we'll show you how to write a simple sequence. You might be wondering at this point why you'd ever want to do that; after all, the built-in facilities provided by MPL are pretty complete. Usually it's a matter of efficiency. While the MPL sequences are well-optimized for general-purpose use, you may have a specialized application for which it's possible to do better. For example, it's possible to write a wrapper that presents the argument types of a function pointer as a sequence [Nas03]. If you happen to already have the function pointer type in hand for other reasons, iterating over the wrapper directly rather than assembling another sequence containing those types could save quite a few template instantiations. For this example, we'll write a limited-capacity Random Access Sequence called tiny with up to three elements. This sequence will be very much like MPL's implementation of vector for compilers that are merely conforming but do not supply typeof. 5.11.1. Building Tiny SequenceThe first step is to choose a representation. Not much more is required of the representation than to encode the (up to three) types it can contain in the sequence type itself:
struct none {}; // tag type to denote no element
template <class T0 = none, class T1 = none, class T2 = none>
struct tiny
{
typedef tiny type;
typedef T0 t0;
typedef T1 t1;
typedef T2 t2;
...
};
As you can see, we've jumped the gun and filled in some of the implementation: tiny's nested ::type refers back to the sequence itself, which makes tiny a sort of "self-returning metafunction." All of the MPL sequences do something similar, and it turns out to be terribly convenient. For example, to return sequence results from a metafunction, you can just derive the metafunction from the sequence you want to return. Also, when one branch of an eval_if needs to return a sequence, you don't have to wrap it in the identity metafunction described in Chapter 4. That is, given a tiny sequence S, the following two forms are equivalent:
// pop the front element off S, unless it is empty
typedef mpl::eval_if<
mpl::empty<S>
, mpl::identity<S>
, mpl::pop_front<S>
>::type r1;
// likewise
typedef mpl::eval_if<
mpl::empty<S>
, S // when invoked, S returns S
, mpl::pop_front<S>
>::type r2;
The other three nested typedefs, t0, t1, and t2, make it easy for any metafunction to access a tiny sequence's elements:[6]
template <class Tiny>
struct manipulate_tiny
{
// what's T0?
typedef typename Tiny::t0 t0;
};
As long as we can all agree not to use none for any other purpose than to mark the beginning of tiny's empty elements, we now have a convenient interface for holding up to three elements. It's not an MPL sequence yet, though. Looking back at the most basic sequence requirements, we find that every sequence has to return iterators from MPL's begin and end metafunctions. Right away it's clear we'll need an iterator representation. Because Random Access Iterators can move in both directions, they must have access to all the elements of the sequence. The simplest way to handle that is to embed the entire sequence in the iterator representation. In fact, it's typical that MPL iterators embed all or part of the sequence they traverse (since list iterators only move forward, they only hold the part of the list that's accessible to them). 5.11.2. The Iterator RepresentationOnce our iterator has access to the sequence, we just need to represent the position somehow. An integral constant wrapper (Pos in the example below) will do:
#include <boost/mpl/iterator_tag.hpp>
template <class Tiny, class Pos>
struct tiny_iterator
{
typedef mpl::random_access_iterator_tag category;
};
The most basic operations on any iterator are dereferencing, via mpl::deref, and forward traversal, via mpl::next. In this case, we can handle incremental traversal in either direction by building a new tiny_iterator with an incremented (or decremented) position:[7]
namespace boost { namespace mpl {
// forward iterator requirement
template <class Tiny, class Pos>
struct next<tiny_iterator<Tiny,Pos> >
{
typedef tiny_iterator<
Tiny
, typename mpl::next<Pos>::type
> type;
};
// bidirectional iterator requirement
template <class Tiny, class Pos>
struct prior<tiny_iterator<Tiny,Pos> >
{
typedef tiny_iterator<
Tiny
, typename mpl::prior<Pos>::type
> type;
};
}}
Dereferencing our tiny_iterator is a bit more involved: We need some way to index our tiny sequence with the iterator's position. If you're thinking, "Hang on, to do that you'd need to implement the at operation," you're right: It's time to leave our iterators alone for a while. 5.11.3. Implementing at for tinyOne reasonable way to implement at is to use partial specialization. First we'll write a template that selects an element of the sequence based on a numerical argument:
template <class Tiny, int N> struct tiny_at;
// partially specialized accessors for each index
template <class Tiny>
struct tiny_at<Tiny,0>
{
typedef typename Tiny::t0 type;
};
template <class Tiny>
struct tiny_at<Tiny,1>
{
typedef typename Tiny::t1 type;
};
template <class Tiny>
struct tiny_at<Tiny,2>
{
typedef typename Tiny::t2 type;
};
Note that if you try to access tiny_at's nested ::type when the second argument is a number outside the range 0...2, you'll get an error: The unspecialized (or "primary") template is not defined. Next, we could simply partially specialize mpl::at for tiny instances:
namespace boost { namespace mpl {
template <class T0, class T1, class T2, class Pos>
struct at<tiny<T0,T1,T2>, Pos>
: tiny_at<tiny<T0,T1,T2>,Pos::value>
{
};
}}
On the face of it, there's nothing wrong with using partial specialization, but let's see how we could get the unspecialized version of mpl::at to work for tiny. This is what the at supplied by MPL looks like:
template<class Sequence, class N>
struct at
: at_impl<typename Sequence::tag>
::template apply<Sequence,N>
{
};
By default, at forwards its implementation to at_impl<Sequence::tag>, a metafunction class that knows how to perform the at function for all sequences with that tag type. So we could add a ::tag to tiny (call it tiny_tag), and write an explicit (full) specialization of mpl::at_impl:
struct tiny_tag {};
template <class T0 = none, class T1 = none, class T2 = none>
struct tiny
{
typedef tiny_tag tag;
typedef tiny type;
typedef T0 t0;
typedef T1 t1;
typedef T2 t2;
};
namespace boost { namespace mpl {
template <>
struct at_impl<tiny_tag>
{
template <class Tiny, class N>
struct apply : tiny_at<Tiny, N::value>
{};
};
}}
This might not seem to be a big improvement over the results of partially specializing at for tiny sequences, but it is. In general, writing partial specializations that will match all the forms taken by a particular sequence family can be impractical. It's very common for equivalent sequence forms not to be instances of the same template, so normally at least one partial specialization for each form would be required: You can't write a partial template specialization that matches both mpl::vector<int> and mpl::vector1<int>, for example. For the same reasons, specializing at limits the ability of third parties to quickly build new members of the sequence family through derivation.
5.11.4. Finishing the tiny_iterator ImplementationWith our implementation of at in hand, we're ready to implement our tiny_iterator's dereference operation:
namespace boost { namespace mpl {
template <class Tiny, class Pos>
struct deref< tiny_iterator<Tiny,Pos> >
: at<Tiny,Pos>
{
};
}}
The only thing missing now are constant-time specializations of mpl::advance and mpl:: distance metafunctions:
namespace boost { namespace mpl {
// random access iterator requirements
template <class Tiny, class Pos, class N>
struct advance<tiny_iterator<Tiny,Pos>,N>
{
typedef tiny_iterator<
Tiny
, typename mpl::plus<Pos,N>::type
> type;
};
template <class Tiny, class Pos1, class Pos2>
struct distance<
tiny_iterator<Tiny,Pos1>
, tiny_iterator<Tiny,Pos2>
>
: mpl::minus<Pos2,Pos1>
{};
}}
Note that we've left the job of checking for usage errors to you in exercise 5-0. 5.11.5. begin and endFinally, we're ready to make tiny into a real sequence; all that remains is to supply begin and end. Like mpl::at, mpl::begin and mpl::end use traits to isolate the implementation for a particular family of sequences. Writing our begin, then, is straightforward:
namespace boost { namespace mpl {
template <>
struct begin_impl<tiny_tag>
{
template <class Tiny>
struct apply
{
typedef tiny_iterator<Tiny,int_<0> > type;
};
};
}}
Writing end is a little more complicated than writing begin was, since we'll need to deduce the sequence length based on the number of none elements. One straightforward approach might be:
namespace boost { namespace mpl {
template <>
struct end_impl<tiny_tag>
{
template <class Tiny>
struct apply
: eval_if<
is_same<none,typename Tiny::t0>
, int_<0>
, eval_if<
is_same<none,typename Tiny::t1>
, int_<1>
, eval_if<
is_same<none,typename Tiny::t2>
, int_<2>
, int_<3>
>
>
>
{};
};
}}
Unfortunately, that code doesn't satisfy the O(1) complexity requirements of end: It costs O(N) template instantiations for a sequence of length N, since eval_if/is_same pairs will be instantiated until a none element is found. To find the size of the sequence in constant time, we need only write a few partial specializations:
template <class T0, class T1, class T2>
struct tiny_size
: mpl::int_<3> {};
template <class T0, class T1>
struct tiny_size<T0,T1,none>
: mpl::int_<2> {};
template <class T0>
struct tiny_size<T0,none,none>
: mpl::int_<1> {};
template <>
struct tiny_size<none,none,none>
: mpl::int_<0> {};
namespace boost { namespace mpl {
template <>
struct end_impl<tiny_tag>
{
template <class Tiny>
struct apply
{
typedef tiny_iterator<
Tiny
, typename tiny_size<
typename Tiny::t0
, typename Tiny::t1
, typename Tiny::t2
>::type
>
type;
};
};
}}
Here, each successive specialization of tiny_size is "more specialized" than the previous one, and only the appropriate version will be instantiated for any given tiny sequence. The best-matching tiny_size specialization will always correspond directly to the length of the sequence. If you're a little uncomfortable (or even peeved) at the amount of boilerplate code repetition here, we can't blame you. After all, didn't we promise that metaprogramming would help save us from all that? Well, yes we did. We have two answers for you. First, metaprogramming libraries save their users from repeating themselves, but once you start writing new sequences you're now working at the level of a library designer.[8] Your users will thank you for going to the trouble (even if they're just you!). Second, as we hinted earlier, there are other ways to automate code generation. You'll see how even the library designer can be spared the embarrassment of repeating herself in Appendix A.
It's so easy to do at this point, that we may as well implement a specialized mpl::size. It's entirely optional; MPL's default implementation of size just measures the distance between our begin and end iterators, but since we are going for efficiency, we can save a few more template instantiations by writing our own:
namespace boost { namespace mpl {
template <>
struct size_impl<tiny_tag>
{
template <class Tiny>
struct apply
: tiny_size<
typename Tiny::t0
, typename Tiny::t1
, typename Tiny::t2
>
{};
};
}}
You've probably caught on by now that the same tag-dispatching technique keeps cropping up over and over. In fact, it's used for all of the MPL's intrinsic sequence operations, so you can always take advantage of it to customize any of them for your own sequence types. 5.11.6. Adding ExtensibilityIn this section we'll write some of the operations required for tiny to fulfill the Extensible Sequence requirements. We won't show you all of them because they are so similar in spirit. Besides, we need to leave something for the exercises at the end of the chapter! First let's tackle clear and push_front. It's illegal to call push_front on a full tiny, because our tiny sequence has a fixed capacity. Therefore, any valid tiny<T0, T1, T2> passed as a first argument to push_front must always have length <= 2 and T2 = none, and it's okay to just drop T2 off the end of the sequence:[9]
namespace boost { namespace mpl {
template <>
struct clear_impl<tiny_tag>
{
template <class Tiny>
struct apply : tiny<>
{};
};
template <>
struct push_front_impl<tiny_tag>
{
template <class Tiny, class T>
struct apply
: tiny<T, typename Tiny::t0, typename Tiny::t1>
{};
};
}}
That was easy! Note that because every tiny sequence is a metafunction returning itself, we were able to take advantage of metafunction forwarding in the body of apply.
Writing push_back isn't going to be such a cakewalk: The transformation we apply depends on the length of the input sequence. Not to worry; we've already written one operation whose implementation depended on the length of the input sequence: end. Since we have the length computation conveniently at hand, all we need is a tiny_push_back template, specialized for each sequence length:
template <class Tiny, class T, int N>
struct tiny_push_back;
template <class Tiny, class T>
struct tiny_push_back<Tiny,T,0>
: tiny<T,none,none>
{};
template <class Tiny, class T>
struct tiny_push_back<Tiny,T,1>
: tiny<typename Tiny::t0,T,none>
{};
template <class Tiny, class T>
struct tiny_push_back<Tiny,T,2>
: tiny<typename Tiny::t0,typename Tiny::t1,T>
{};
namespace boost { namespace mpl {
template <>
struct push_back_impl<tiny_tag>
{
template <class Tiny, class T>
struct apply
: tiny_push_back<
Tiny, T, size<Tiny>::value
>
{};
};
}}
Note that what is missing here is just as important as what is present. By not defining a tiny_push_back specialization for sequences of length 3, we made it a compile-time error to push_back into a full sequence. |
|
|