5.8. Sequence Classes

In this section we'll describe the specific sequences provided by the MPL, and discuss how they fit the sequence concepts detailed above.

Before we begin, you should know that all of the MPL sequences have both an unnumbered and a numbered form. The unnumbered forms are the ones you're already familiar with, like mpl::vector<int, long, int>. The corresponding numbered forms include the sequence's length as part of its template name, for example, mpl::vector3<int, long, int>. The length of unnumbered forms is limited to 20 elements by default^[4] to reduce coupling in the library and to limit compilation times. To use the numbered form of a sequence with length N, you must include a corresponding "numbered header" file, named for the sequence whose length is N rounded up to the nearest multiple of ten. For example:

^[4] See the Configuration Macros section of the MPL reference manual for details on how to change this limit.

    #include <boost/mpl/vector/vector30.hpp> // 28 rounded up





    // declare a sequence of 28 elements


    typedef boost::mpl::vector28<


         char, int, long ... 25 more types


    > s;

5.8.1. list

mpl::list is the simplest of the extensible MPL sequences, and it is structurally very similar to a runtime singly-linked list. Since it is a Forward Sequence, it supports begin and end, and, of course, access to the first element via front. It supports O(1) insertion and erasure at the head of the sequence, so it also supports push_front and pop_front.

5.8.2. vector

MPL's vector is almost an exact analogue to the STL vector: it is a Random Access Sequence, so naturally it has Random Access Iterators. Since every Random Access Iterator is a Bidirectional Iterator, and we have access to the vector's end iterator, back is supported in addition to front. Like an STL vector, MPL's vector also supports efficient push_back and pop_back operations.

In addition to the usual compile-time/runtime differences, this sequence may differ from those in the STL in one significant detail: It may have a maximum size that is limited not just by the usual compiler resources, such as memory or template instantiation depth, but also by the way the sequence was implemented. In that case, the sequence can normally be extended only as far as the maximum numbered sequence header included in the translation unit. For example:

    #include <boost/mpl/vector/vector10.hpp>





    typedef boost::mpl::vector9<


         int[1], int[2], int[3], int[4]


       , int[5], int[6], int[7], int[8], int[9]


    > s9;





    typedef mpl::push_back<s9, int[10]>::type s10;  // OK


    typedef mpl::push_back<s10, int[11]>::type s11; // error

To make the code work, we'd have to replace the #include directive with:

    #include <boost/mpl/vector/vector20.hpp>

This limitation is not as serious as it may sound, for two reasons:

We wrote that it may differ in this respect because on compilers that support the typeof language extension, the maximum size limitation vanishes. Chapter 9 describes some of the basic techniques that make that possible.

Operations on mpl::vector tend to compile much more quickly than those on mpl::list, and, due to its random-access capability, mpl::vector is far more flexible. Taken together, these factors should make mpl::vector your first choice when selecting a general-purpose Extensible Sequence. However, if your clients will be using your code for compile-time computation that may require sequences of arbitrary length, it may be better to use mpl::list.

Guideline Reach for mpl::vector first when choosing a general-purpose type sequence.

5.8.3. deque

MPL's deque is almost exactly like its vector in all respects, except that deque allows efficient operations at the head of the sequence with push_front and pop_front. Unlike the corresponding STL components, the efficiency of deque is very close to that of vectorso much so, in fact, that on many C++ compilers, a vector really is a deque under-the-covers.

5.8.4. range_c

range_c is a "lazy" random access sequence that contains consecutive integral constants. That is, mpl::range_c<long, N, M> is roughly equivalent to:

    mpl::vector<


        mpl::integral_c<long,N>


      , mpl::integral_c<long,N+1>


      , mpl::integral_c<long,N+2>


      ...


      , mpl::integral_c<long,M-3>


      , mpl::integral_c<long,M-2>


      , mpl::integral_c<long,M-1> // Note: M-1, not M


    >

By saying range_c is "lazy," we mean that its elements are not explicitly represented: It merely stores the endpoints and produces new integral constants from within the range on demand. When iterating over large sequences of integers, using range_c is not only convenient, but can result in a significant savings in compilation time over the use of a non-lazy alternative like the vector shown above.

The price of this economy is that range_c comes with a limitation not shared by vector and list: It is not extensible. If the library could support insertion of arbitrary elements into range_c, the elements would need to be explicitly represented. Though not extensible, range_c supports pop_front and pop_back, because contracting a range is easy.

5.8.5. map

An MPL map is an Extensible Associative Sequence in which each element supports the interface of mpl::pair.

    template <class T1, class T2>


    struct pair


    {


        typedef pair type;


        typedef T1 first;


        typedef T2 second;


    };

An element's first and second types are treated as its key and value, respectively. To create a map, just list its elements in sequence as template parameters. The following example shows a mapping from built-in integral types to their next "larger" type:

    typedef mpl::map<


        mpl::pair<bool, unsigned char>


      , mpl::pair<unsigned char, unsigned short>


      , mpl::pair<unsigned short, unsigned int>


      , mpl::pair<unsigned int, unsigned long>


      , mpl::pair<signed char, signed short>


      , mpl::pair<signed short, signed int>


      , mpl::pair<signed int, signed long>


    >::type to_larger;

Like mpl::vector, the mpl::map implementation has a bounded maximum size on C++ compilers that don't support the typeof language extension, and the appropriate numbered sequence headers must be included if you're going to grow a map beyond the next multiple of ten elements.

It's not all bad news for users whose compiler doesn't go beyond the standard requirements, though: When map has a bounded maximum size, iterating over all of its elements is O(N) instead of O(N+E), where N is the size of the map and E is the number of erasures that have been applied to it.

5.8.6. set

A set is like a map, except that each element is identical to its key type and value type. The fact that the key and value types are identical means that mpl::at<S,k>::type is a fairly uninteresting operationit just returns k unchanged. The main use for an MPL set is efficient membership testing with mpl::has_key<S,k>::type. A set is never subject to a maximum size bound, and therefore operation is always O(N+E) for complete traversal.

5.8.7. iterator_range

An iterator_range is very similar to range_c in intent. Instead of representing its elements explicitly, an iterator_range stores two iterators that denote the sequence endpoints. Because MPL algorithms operate on sequences instead of iterators, iterator_range can be indispensable when you want to operate on just part of a sequence: Once you've found the sequence endpoints, you can form an iterator_range and pass that to the algorithm, rather than building a modified version of the original sequence.