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

This is the documentation for an old version of Boost. Click here to view this page for the latest version.
PrevUpHomeNext

Traversal

Incrementable Iterator Concept
Single Pass Iterator Concept
Forward Traversal Concept
Bidirectional Traversal Concept
Random Access Traversal 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


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 tosingle_pass_traversal_tag


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


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


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



PrevUpHomeNext