Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. — Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

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