| Home | Libraries | People | FAQ | More

#### Forward Sequence

##### Description

A Forward Sequence is a Sequence whose elements are arranged in a definite order. The ordering is guaranteed not to change from iteration to iteration. The requirement of a definite ordering allows the definition of element-by-element equality (if the container's element type is Equality Comparable) and of lexicographical ordering (if the container's element type is LessThan Comparable).

Notation

`s`

  A Forward Sequence

`S`

  A Forward Sequence type

`o`

  An arbitrary object

`e`

  A Sequence element

##### Valid Expressions

For any Forward Sequence the following expressions must be valid:

Expression | Return type | Type Requirements | Runtime Complexity
--- | --- | --- | ---
``begin`(s)` | Forward Iterator |  | Constant
``end`(s)` | Forward Iterator |  | Constant
``size`(s)` | MPL Integral Constant. Convertible to int. |  | Constant
``empty`(s)` | MPL Boolean Constant. Convertible to bool. |  | Constant
``front`(s)` | Any type |  | Constant
``front`(s) = o` | Any type | `s` is mutable and `e = o`, where `e` is the first element in the sequence, is a valid expression. | Constant

##### Result Type Expressions

Expression | Compile Time Complexity
--- | ---
``result_of::begin`<S>::type` | Amortized constant time
``result_of::end`<S>::type` | Amortized constant time
``result_of::size`<S>::type` | Unspecified
``result_of::empty`<S>::type` | Constant time
``result_of::front`<S>::type` | Amortized constant time

##### Expression Semantics

Expression | Semantics
--- | ---
``begin`(s)` | An iterator to the first element of the sequence; see `begin`.
``end`(s)` | A past-the-end iterator to the sequence; see `end`.
``size`(s)` | The size of the sequence; see `size`.
``empty`(s)` | A boolean Integral Constant `c` such that `c::value == true` if and only if the sequence is empty; see `empty`.
``front`(s)` | The first element in the sequence; see `front`.

##### Invariants

For any Forward Sequence s the following invariants always hold:

- `[`begin`(s), `end`(s))` is always a valid range.
- An Algorithm that iterates through the range `[`begin`(s), `end`(s))` will pass through every element of `s` exactly once.
- ``begin`(s)` is identical to ``end`(s))` if and only if `s` is empty.
- Two different iterations through `s` will access its elements in the same order.

##### Models

- `std::pair`
- `boost::array`
- `vector`
- `cons`
- `list`
- `set`
- `map`
- `single_view`
- `filter_view`
- `iterator_range`
- `joint_view`
- `transform_view`
- `reverse_view`
- `zip_view`