| Home | Libraries | People | FAQ | More

#### Bidirectional Iterator

##### Description

A Bidirectional Iterator traverses a Sequence allowing movement in either direction one element at a time.

Notation

`i`

  A Bidirectional Iterator

`I`

  A Bidirectional Iterator type

`M`

  An MPL integral constant

`N`

  An integral constant

##### Refinement of

Forward Iterator

##### Expression requirements

In addition to the requirements defined in Forward Iterator, the following expressions must be valid:

Expression | Return type | Runtime Complexity
--- | --- | ---
``next`(i)` | Bidirectional Iterator | Constant
``prior`(i)` | Bidirectional Iterator | Constant
``advance_c`<N>(i)` | Bidirectional Iterator | Constant
``advance`<M>(i)` | Bidirectional Iterator | Constant

##### Meta Expressions

Expression | Compile Time Complexity
--- | ---
``result_of::prior`<I>::type` | Amortized constant time

##### Expression Semantics

The semantics of an expression are defined only where they differ from, or are not defined in Forward Iterator

Expression | Semantics
--- | ---
``prior`(i)` | An iterator to the element preceding `i`

##### Invariants

In addition to the invariants of Forward Iterator, the following invariants always hold:

- ``prior`(`next`(i)) == i && `prior`(`next`(i)) == `next`(`prior`(i))`
- ``prior`(i) == `advance_c`<-1>(i)`
- Using ``prior`` to traverse a sequence will never return a previously seen position

##### Models

- `std::pair` iterator
- `boost::array` iterator
- `vector` iterator
- `iterator_range` (where adapted sequence is a Bidirectional Sequence)
- `transform_view` (where adapted sequence is a Bidirectional Sequence)
- `reverse_view`