Bidirectional Iterator


Category: iterators	Component type: concept

Description

A Bidirectional Iterator is an iterator that can be both incremented and decremented. The requirement that a Bidirectional Iterator can be decremented is the only thing that distinguishes Bidirectional Iterators from Forward Iterators.

Refinement of

Forward Iterator

Associated types

The same as for Forward Iterator.

Notation

`X`	A type that is a model of Bidirectional Iterator
`T`	The value type of `X`
`i`, `j`	Object of type `X`
`t`	Object of type `T`

Definitions

Valid expressions

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

Name	Expression	Type requirements	Return type
Predecrement	`--i`		`X&`
Postdecrement	`i--`		`X`

Expression Semantics

Semantics of an expression is defined only where it is not defined in Forward Iterator.

Name	Expression	Precondition	Semantics	Postcondition
Predecrement	`--i`	`i` is dereferenceable or past-the-end. There exists a dereferenceable iterator `j` such that `i == ++j`.	`i` is modified to point to the previous element.	`i` is dereferenceable. `&i = &--i`. If `i == j`, then `--i == --j`. If `j` is dereferenceable and `i == ++j`, then `--i == j`.
Postdecrement	`i--`	`i` is dereferenceable or past-the-end. There exists a dereferenceable iterator `j` such that `i == ++j`.	Equivalent to { X tmp = i; --i; return tmp; }

Complexity guarantees

The complexity of operations on bidirectional iterators is guaranteed to be amortized constant time.

Invariants

Symmetry of increment and decrement If i is dereferenceable, then ++i; --i; is a null operation. Similarly, --i; ++i; is a null operation.

Models

T*
list<T>::iterator