Traversal

Incrementable Iterator Concept

A class or built-in type X models the Incrementable Iterator concept if, in addition to X being Assignable and Copy Constructible, the following expressions are valid and respect the stated semantics.

Table 1.5. Incrementable Iterator Requirements (in addition to Assignable, Copy Constructible)

Expression	Return Type	Assertion/Semantics
`++r`	`X&`	`&r == &++r`
`r++`	`X`	{ X tmp = r; ++r; return tmp; }
`iterator_traversal<X>::type`	Convertible to `incrementable_traversal_tag`

Single Pass Iterator Concept

A class or built-in type X models the Single Pass Iterator concept if the following expressions are valid and respect the stated semantics.

Table 1.6. Single Pass Iterator Requirements (in addition to Incrementable Iterator and Equality Comparable)

Expression	Return Type	Assertion/Semantics / Pre-/Post-condition
`++r`	`X&`	pre: `r` is dereferenceable; post: `r` is dereferenceable or `r` is past-the-end
`a == b`	convertible to `bool`	`==` is an equivalence relation over its domain
`a != b`	convertible to `bool`	`!(a == b)`
`iterator_traits<X>::difference_type`	A signed integral type representing the distance between iterators
`iterator_traversal<X>::type`	Convertible to`single_pass_traversal_tag`

Forward Traversal Concept

A class or built-in type X models the Forward Traversal concept if, in addition to X meeting the requirements of Default Constructible and Single Pass Iterator, the following expressions are valid and respect the stated semantics.

Table 1.7. Forward Traversal Iterator Requirements (in addition to Default Constructible and Single Pass Iterator)

Expression	Return Type	Assertion/Note
`X u;`	`X&`	note: `u` may have a singular value.
`++r`	`X&`	`r == s` and `r` is dereferenceable implies `++r == ++s.`
`iterator_traversal<X>::type`	Convertible to `forward_traversal_tag`

Bidirectional Traversal Concept

A class or built-in type X models the Bidirectional Traversal concept if, in addition to X meeting the requirements of Forward Traversal Iterator, the following expressions are valid and respect the stated semantics.

Table 1.8. Bidirectional Traversal Iterator Requirements (in addition to Forward Traversal Iterator)

Expression	Return Type	Assertion/Semantics/Pre-/Post-condition
`--r`	`X&`	pre: there exists `s` such that `r == ++s`. post: `s` is dereferenceable. `--(++r) == r`. `--r == --s` implies `r == s`. `&r == &--r`.
`r--`	convertible to `const X&`	{ X tmp = r; --r; return tmp; }
`iterator_traversal<X>::type`	Convertible to `bidirectional_traversal_tag`

Random Access Traversal Concept

A class or built-in type X models the Random Access Traversal concept if the following expressions are valid and respect the stated semantics. In the table below, Distance is iterator_traits<X>::difference_type and n represents a constant object of type Distance.

Table 1.9. Random Access Traversal Iterator Requirements (in addition to Bidirectional Traversal)

Expression	Return Type	Operational Semantics	Assertion/Precondition
`r += n`	`X&`	{ Distance m = n; if (m >= 0) while (m--) ++r; else while (m++) --r; return r; }
`a + n`, `n + a`	`X`	{ X tmp = a; return tmp+= n; }
`r -= n`	`X&`	`return r += -n`
`a - n`	`X`	{ X tmp = a; return tmp-= n; }
`b - a`	`Distance`	`a < b ? distance(a,b) : -distance(b,a)`	pre: there exists a value `n` of `Distance` such that `a + n == b`. `b == a + (b - a)`.
`a[n]`	convertible to T	`*(a + n)`	pre: a is a Readable Iterator
`a[n] = v`	convertible to T	`*(a + n) = v`	pre: a is a Writable iterator
`a < b`	convertible to `bool`	`b - a > 0`	`<` is a total ordering relation
`a > b`	convertible to `bool`	`b < a`	`>` is a total ordering relation
`a >= b`	convertible to `bool`	`!(a < b)`
`a <= b`	convertible to `bool`	`!(a > b)`
`iterator_traversal<X>::type`	convertible to `random_access_traversal_tag`