5.12. Details

By now you should have a fairly clear understanding of what goes into an MPL sequenceand what comes out of it! In upcoming chapters you can expect to get more exposure to type sequences and their practical applications, but for now we'll just review a few of this chapter's core concepts.

Sequence concepts

MPL sequences fall into three traversal concept categories (forward, bidirectional, and random access) corresponding to the capabilities of their iterators. A sequence may also be front-extensible, meaning that it supports push_front and pop_front, or back-extensible, meaning that it supports push_back and pop_back. An Associative Sequence represents a mapping from type to type with O(1) lookup.

Iterator concepts

MPL iterators model one of three traversal concepts: Forward Iterator, Bidirectional Iterator, and Random Access Iterator. Each iterator concept refines the previous one, so that all bidirectional iterators are also forward iterators, and all random access iterators are also bidirectional iterators. A Forward Iterator x can be incrementable and dereferenceable, meaning that next<x>::type and deref<x>::type are well-defined, or it can be past-the-end of its sequence. A Bidirectional Iterator may be decrementable, or it may refer to the beginning of its sequence.

Sequence algorithms

The purely functional nature of C++ template metaprogramming really dictates that MPL algorithms operate on sequences rather than on iterator pairs. Otherwise, passing the result of one algorithm to another one would be unreasonably difficult. Some people feel that the same logic applies to STL algorithms, and several algorithm libraries for operating on whole runtime sequences have cropped up. Look for one in an upcoming Boost release.

Intrinsic sequence operations

Not all sequence operations can be written generically; some, such as begin and end, need to be written specifically to work with particular sequences. These MPL metafunctions all use a tag dispatching technique to allow for easy customization.