5.5. Sequence Concepts

The MPL has a taxonomy of sequence concepts similar to those in the STL. Each level of concept refinement introduces a new set of capabilities and interfaces. In this section we'll walk through each of the concepts in turn.

5.5.1. Sequence Traversal Concepts

For each of the three iterator traversal categoriesforward, bidirectional, and random accessthere is a corresponding sequence concept. A sequence whose iterators are forward iterators is called a Forward Sequence, and so forth.

If the sequence traversal concepts detailed below seem a bit thin, it's because (apart from extensibility, which we'll get to in a moment), a sequence is not much more than a pair of iterators into its elements. Most of what's needed to make a sequence work is provided by its iterators.

5.5.1.1 Forward Sequences

Any MPL sequence (for example, mpl::list, which we'll cover later in this chapter) is a Forward Sequence.

In Table 5.4, S represents a Forward Sequence.

Table 5.4. Forward Sequence Requirements

Expression	Result	Assertion
mpl::begin<S>::type	A Forward Iterator.
mpl::end<S>::type	A Forward Iterator.	Reachable from mpl::begin<S>::type.

Because we can access any sequence's begin iterator, we can trivially get its first element. Accordingly, every nonempty MPL sequence also supports the expression

    mpl::front<S>::type

which is equivalent to

    mpl::deref<


         mpl::begin<S>::type


    >::type

5.5.1.2 Bidirectional Sequences

In Table 5.5, S is any Bidirectional Sequence.

Table 5.5. Additional Requirements for Bidirectional Sequences

Expression	Result
mpl::begin<S>::type	A Bidirectional Iterator.
mpl::end<S>::type	A Bidirectional Iterator.

Because we can access any sequence's end iterator, we can trivially get to its last element if its iterators are bidirectional. Accordingly, every nonempty Bidirectional Sequence also supports the expression

    mpl::back<S>::type

which is equivalent to

    mpl::deref<


        mpl::prior<


            mpl::end<S>::type


        >::type


    >::type

5.5.1.3 Random Access Sequences

mpl::vector is an example of a Random Access Sequence. In Table 5.6, S is any Random Access Sequence.

Table 5.6. Additional Requirements for Random Access Sequences

Expression	Result
mpl::begin<S>::type	A Random Access Iterator.
mpl::end<S>::type	A Random Access Iterator.

Because a Random Access Sequence has random access iterators, we can trivially get to any element of the sequence in one step. Accordingly, every Random Access Sequence also supports the expression

    mpl::at<S,N>::type

which is equivalent to

    mpl::deref<


        mpl::advance<


           mpl::begin<S>::type


         , N


        >::type


    >::type

5.5.2. Extensibility

An Extensible Sequence is one that supports insert, erase, and clear operations. Naturally, since metadata is immutable, none of these operations can modify the original sequence. Instead, they all return a modified copy of the original sequence.

Given that S is an Extensible Sequence, pos is some iterator into S, finish is an iterator reachable from pos, and X is any type, the expressions in Table 5.7 return a new sequence that models the same sequence concept that S does:

Table 5.7. Extensible Sequence Requirements

Expression	Elements of Result
mpl::insert<S,pos,X>::type	[mpl::begin<S>::type, pos), X, [pos, mpl::end<S>::type)
mpl::erase<S,pos>::type	[mpl::begin<S>::type, pos), [mpl::next<pos>::type, mpl::end<S>::type)
mpl::erase<     S, pos, finish >::type	[mpl::begin<S>::type, pos), [finish, mpl::end<S>::type)
mpl::clear<S>::type	None.

Many of the MPL sequences are extensible, but with different complexity for the different operations. For example, insertion and erasure at the head of an mpl::list is O(1) (i.e., takes constant time and compiler resources), while making a list that differs only at the tail is O(N), meaning that the cost is proportional to the original list's length. Insertion and erasure at the back of an mpl::vector is O(1), though modifications at other positions are only guaranteed to be O(N).

MPL also supplies push_front and pop_front metafunctions, which insert and erase a single element at the head of a sequence respectively, and also push_back and pop_back, which do the same at the tail of a sequence. Each of these operations is only available for sequences that can support it with O(1) complexity.

5.5.3. Associative Sequences

An Associative Sequence is a mapping whose set of unique key types is mapped to one or more of its value types. Each of the sequence's element typesthose accessible through its iteratorsis associated with a single (key, value) pair.^[3] In addition to supporting begin<S>::type and end<S>::type as required for any Forward Sequence, an Associative Sequence supports the following operations.

^[3] For some concrete examples, see section 5.8, which covers mpl::map and mpl::set.

In Tables 5.8 and 5.9, k and k2 can be any type and pos1 and pos2 are iterators into S.

Table 5.8. Associative Sequences Requirements

Expression	Result	Precondition/Assertion
mpl::has_key<   S, k >::value	true if k is in S's set of keys; false otherwise.
mpl::at<   S, k >::type	The value type associated with k.	Precondition: k is in S's set of keys
mpl::order<   S, k >::type	An unsigned integral constant wrapper.	If    mpl::order<S,k>::type::value    == mpl::order<S,k2>::type::value then k is identical to k2. Precondition: k is in S's set of keys.
mpl::key_type<   S, t >::type	The key type that S would use for an element type t.	If    mpl::key_type<      S, mpl::deref<pos1>::type    >::type is identical to    mpl::key_type<      S, mpl::deref<pos2>::type    >::type then pos1 is identical to pos2.
mpl::value_type<   S, t >::type	The value type that S would use for an element type t.

Table 5.9. Extensible Associative Sequence

Expression	Result	Note
mpl::insert<     S, pos1, t >::type mpl::insert<   S, t >::type	S' equivalent to S except that mpl::at<     S'   , mpl::key_type<S,t>::type >::type is mpl::value_type<S,t>::type.	May incur an erasure penalty if mpl::has_key<     S,     mpl::key_type<       S, t     >::type >::value is true.
mpl::erase<     S, pos1 >::type	S' equivalent to S except that mpl::has_key<     S'   , mpl::key_type<         S       , mpl::deref<pos1>::type     >::type >::value is false.
mpl::erase_key<   S, k >::type	S' equivalent to S except that mpl::has_key<S' , k>::value is false.
mpl::clear<     S >::type	An empty sequence with the same properties as S.

Note that there are no guarantees about the values returned by the order metafunction other than that each key will be associated with a unique value. In particular, order values are not required to have any relationship to iterator traversal order. Also note that unlike an STL associative container, which always has an associated ordering relation (it defaults to std::less<KeyType>), an associative meta-sequence has no such ordering relation: The order that elements will be traversed during iteration is entirely up to the sequence implementation.

5.5.4. Extensible Associative Sequences

Like an ordinary Extensible Sequence, an Extensible Associative Sequence supports insert, erase, and clear operations, each of which produces a new sequence as a result. Since the ordering of elements in an Associative Sequence is arbitrary, an inserted element won't necessarily end up in the position indicated by the iterator passed to the insert metafunction. In this respect, associative meta-sequences resemble STL associative containers such as std::map and std::set, but in some ways they are quite different. For example, while an STL sequence can use an iterator as a "hint" to improve the performance of insertion from O(log(N)) to O(1), an associative meta-sequence ignores the iterator argument to insert altogether: In fact, insertion is always O(1). While it is convenienteven crucialfor authors of generic sequence algorithms to have a uniform insert metafunction that always takes an iterator argument, it is equally inconvenient to come up with an iterator every time you want to insert a new element in a set. Therefore, in addition to mpl::insert<S,pos,t>, an Extensible Associative Sequence must also support the equivalent mpl::insert<S,t> form.

Another difference from runtime associative containers is that erasures actually have an effect on the efficiency of iteration: A complete traversal of an associative meta-sequence has a worst-case complexity of O(N+E), where N is the number of elements in the sequence and E is the number of elements that have been erased. When an element is erased from an Associative Sequence, the library adds a special marker element that causes the erased element to be skipped during iteration. Note that applying clear to an Associative Sequence does not come with a similar penalty: The result is a brand new sequence.

The following expressions have constant complexity and return a new sequence that models all the same MPL sequence concepts as S does.

Because erasure anywhere in an Extensible Associative Sequence is O(1), pop_front and pop_back are both available. Since insertion is also O(1), mpl::push_front<S,t> and mpl::push_back<S,t> are also supported, but are both equivalent to mpl::insert<S,t> because the iterator argument in mpl::insert<S,pos,t> is ignored.