5.4. Iterator Concepts

In this section we'll define the MPL iterator concepts. If you're familiar with STL iterators, you'll probably notice similarities between these and the STL categories of the same name. There are also a few differences, which are a direct consequence of the immutable nature of C++ metadata. For example, there are no separate categories for input iterators and output iterators in the MPL. We'll point out these similarities and differences as we encounter them, along with a few key properties of all iterators, which we'll introduce in bold text.

Just as the fundamental iterator operations of the STL are O(1) at runtime, all the fundamental MPL iterator operations detailed in this chapter are O(1) at compile time.^[2]

^[2] In this book we measure compile-time complexity of an operation in terms of the number of template instantiations required. There are of course other factors that will determine the time it takes to compile any program. See Appendix C for more details.

5.4.1. Forward Iterators

Forward Iterator is the simplest MPL iterator category; it has only three operations: forward traversal, element access, and category detection. An MPL iterator can either be both incrementable and dereferenceable, or it can be past-the-end of its sequence. These two states are mutually exclusive: None of the Forward Iterator operations are allowed on a past-the-end iterator.

Since MPL iterators are immutable, we can't increment them "in place" the way we can with STL iterators. Instead, we pass them to mpl::next, which yields the next position in the sequence. The author of an incrementable iterator can either specialize mpl::next to support her iterator type, or she can simply leverage its default implementation, which reaches in to access the iterator's ::next member:

    namespace boost { namespace mpl {


       template <class It> struct next


       {


          typedef typename It::next type;


       };


    }}

A dereferenceable iterator supports element access through the mpl::deref metafunction, whose default implementation similarly accesses the iterator's nested ::type:

    namespace boost { namespace mpl {


       template <class It> struct deref


       {


          typedef typename It::type type;


       };


    }}

To check for equivalence of iterators, use the boost::is_same metafunction from the Boost Type Traits library. Two iterators are equivalent only if they have the same type. Since is_same works on any type, this applies equally well to past-the-end iterators. An iterator j is said to be reachable from an iterator i if they are equivalent, or if there exists some sequence:

    typedef mpl::next<i>::type i1;


    typedef mpl::next<i1>::type i2;


    .


    .


    .


    typedef mpl::next<in-1>::type in;

such that i_n is equivalent to j. We'll use the "half-open range" notation [i,j) to denote a range of sequence elements starting with mpl::deref<i>::type and ending with mpl:: deref<i_n-1>::type.

Table 5.1 details the requirements for MPL forward iterators, where i is a model of Forward Iterator.

Table 5.1. Forward Iterator Requirements

Expression	Result	Precondition
mpl::next<i>::type	A Forward Iterator.	i is incrementable.
mpl::deref<i>::type	Any type.	i is dereferenceable.
i::category	Convertible to mpl:: forward_iterator_tag.

5.4.2. Bidirectional Iterators

A Bidirectional Iterator is a Forward Iterator with the additional ability to traverse a sequence in reverse. A Bidirectional Iterator is either decrementable or it refers to the beginning of its sequence.

Given a decrementable iterator, the mpl::prior metafunction yields the previous position in the sequence. The author of an decrementable iterator can either specialize mpl::prior to support her iterator type, or she can simply leverage its default implementation, which reaches in to access the iterator's ::prior member:

    namespace boost { namespace mpl {


       template <class It> struct prior


       {


          typedef typename It::prior type;


       };


    }}

Table 5.2 details the additional requirements for MPL bidirectional iterators, where i is a model of Bidirectional Iterator.

Table 5.2. Additional Requirements for Bidirectional Iterators

Expression	Result	Assertion/Precondition
mpl:: next<i>::type	A Bidirectional Iterator.	mpl::prior<     mpl::next<i>::type >::type is equivalent to i. Precondition: i is incrementable.
mpl:: prior<i>::type	A Bidirectional Iterator.	Precondition: i is decrementable.
i::category	Convertible to mpl:: bidirectional_iterator_tag.

5.4.3. Random Access Iterators

A Random Access Iterator is a Bidirectional Iterator that also provides movement by an arbitrary number of positions forward or backward, and distance measurement between iterators in the same sequence, all in constant time.

Random access traversal is achieved using the mpl::advance metafunction, which, given a random access iterator i and an integral constant type n, returns an advanced iterator in the same sequence. Distance measurement is available through the mpl::distance metafunction, which, given random access iterators i and j into the same sequence, returns the number of positions between i and j. Note that these two operations have an intimate relationship:

    mpl::advance<i, mpl::distance<i,j>::type>::type

is identical to j, and both operations have constant complexity.

As with the STL functions of the same names, advance and distance are in fact available for bidirectional and forward iterators as well, though only with linear complexity: The default implementations simply go through as many invocations of mpl::next or mpl::prior as necessary to get the job done. Consequently, the author of a random access iterator must specialize advance and distance for her iterator to work in constant time, or she won't have met the random access iterator requirements.

Table 5.3 details the additional requirements for MPL Random Access Iterators. The names i and j represent iterators into the same sequence, N represents an integral constant type, and n is N::value.

Table 5.3. Additional Requirements for Random Access Iterators

Expression	Result	Assertion/Precondition
mpl::next<i>::type	A Random Access Iterator.	Precondition: i is incrementable.
mpl::prior<i>::type	A Random Access Iterator.	Precondition: i is decrementable.
mpl::advance<   i, N >::type	If n>0 , equivalent to n applications of mpl::next to i. Otherwise, equivalent to -n applications of mpl::prior to i.	Constant time. mpl::advance<     i   , mpl::distance<        i,j     >::type >::type is equivalent to j.
mpl::distance<   i, j >::type	An integral constant wrapper.	Constant time.
i::category	Convertible to mpl::random_ access_iterator_tag.