May 4, 2011, 8:44 a.m.
posted by technodev
Sequence ConceptsThe 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. Sequence Traversal ConceptsFor 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. 1.1 Forward SequencesAny MPL sequence (for example, mpl::list, which we'll cover later in this chapter) is a Forward Sequence. In Figure, S represents a Forward Sequence.
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 1.2 Bidirectional SequencesIn Figure, S is any Bidirectional Sequence.
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 1.3 Random Access Sequencesmpl::vector is an example of a Random Access Sequence. In Figure, S is any Random Access Sequence.
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 ExtensibilityAn 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 Figure return a new sequence that models the same sequence concept that S does:
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. Associative SequencesAn 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.
In Figure and 5.9, k and k2 can be any type and pos1 and pos2 are iterators into 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. Extensible Associative SequencesLike 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. |
- Comment