| Home | Libraries | People | FAQ | More

#### Forward Iterator

##### Description

A Forward Iterator traverses a Sequence allowing movement in only one direction through it's elements, one element at a time.

Notation

`i`, `j`

  Forward Iterators

`I`, `J`

  Forward Iterator types

`M`

  An MPL integral constant

`N`

  An integral constant

##### Expression requirements

A type models Forward Iterator if, in addition to being CopyConstructable, the following expressions are valid:

Expression | Return type | Runtime Complexity
--- | --- | ---
``next`(i)` | Forward Iterator | Constant
`i == j` | Convertible to bool | Constant
`i != j` | Convertible to bool | Constant
``advance_c`<N>(i)` | Forward Iterator | Constant
``advance`<M>(i)` | Forward Iterator | Constant
``distance`(i, j)` | ``result_of::distance`<I, J>::type` | Constant
``deref`(i)` | ``result_of::deref`<I>::type` | Constant
`*i` | ``result_of::deref`<I>::type` | Constant

##### Meta Expressions

Expression | Compile Time Complexity
--- | ---
``result_of::next`<I>::type` | Amortized constant time
``result_of::equal_to`<I, J>::type` | Amortized constant time
``result_of::advance_c`<I, N>::type` | Linear
``result_of::advance`<I ,M>::type` | Linear
``result_of::distance`<I ,J>::type` | Linear
``result_of::deref`<I>::type` | Amortized constant time
``result_of::value_of`<I>::type` | Amortized constant time

##### Expression Semantics

Expression | Semantics
--- | ---
``next`(i)` | An iterator to the element following `i`
`i == j` | Iterator equality comparison
`i != j` | Iterator inequality comparison
``advance_c`<N>(i)` | An iterator n elements after `i` in the sequence
``advance`<M>(i)` | Equivalent to `advance_c<M::value>(i)`
``distance`(i, j)` | The number of elements between `i` and `j`
``deref`(i)` | The element at position`i`
`*i` | Equivalent to `deref(i)`

##### Invariants

The following invariants always hold:

- `!(i == j) == (i != j)`
- ``next`(i) == `advance_c`<1>(i)`
- ``distance`(i, `advance_c`<N>(i)) == N`
- Using ``next`` to traverse the sequence will never return to a previously seen position
- ``deref`(i)` is equivalent to `*i`
- If `i == j` then `*i` is equivalent to `*j`

##### Models

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