boost.png (6897 bytes) Home Libraries People FAQ More

PrevUpHomeNext

Concept RandomAccessIterator

RandomAccessIterator

Description

A random access iterator is an iterator that can read through a sequence of values. It can move in either direction through the sequence (by any amount in constant time), and can be either mutable (data pointed to by it can be changed) or not mutable.

An iterator represents a position in a sequence. Therefore, the iterator can point into the sequence (returning a value when dereferenced and being incrementable), or be off-the-end (and not dereferenceable or incrementable).

Refinement of

Associated types

  • value_type

    std::iterator_traits<Iter>::value_type

    The value type of the iterator

  • category

    std::iterator_traits<Iter>::iterator_category

    The category of the iterator

  • difference_type

    std::iterator_traits<Iter>::difference_type

    The difference type of the iterator (measure of the number of steps between two iterators)

Notation

Iter
A type playing the role of iterator-type in the RandomAccessIterator concept.
i, j
Objects of type Iter
x
Object of type value_type
n
Object of type difference_type
int_off
Object of type int

Type expressions

Category tag

category must be derived from std::random_access_iterator_tag.

Valid expressions

Name Expression Type Semantics

Motion

i += n

Iter &

Equivalent to applying i++n times if n is positive, applying i---n times if n is negative, and to a null operation if n is zero.

Motion (with integer offset)

i += int_off

Iter &

Equivalent to applying i++n times if n is positive, applying i---n times if n is negative, and to a null operation if n is zero.

Subtractive motion

i -= n

Iter &

Equivalent to i+=(-n)

Subtractive motion (with integer offset)

i -= int_off

Iter &

Equivalent to i+=(-n)

Addition

i + n

Iter

Equivalent to {Iter j = i; j += n; return j;}

Addition with integer

i + int_off

Iter

Equivalent to {Iter j = i; j += n; return j;}

Addition (count first)

n + i

Iter

Equivalent to i + n

Addition with integer (count first)

int_off + i

Iter

Equivalent to i + n

Subtraction

i - n

Iter

Equivalent to i + (-n)

Subtraction with integer

i - int_off

Iter

Equivalent to i + (-n)

Distance

i - j

difference_type

The number of times i must be incremented (or decremented if the result is negative) to reach j. Not defined if j is not reachable from i.

Element access

i[n]

const-if-not-mutable value_type &

Equivalent to *(i + n)

Element access with integer index

i[int_off]

const-if-not-mutable value_type &

Equivalent to *(i + n)

Complexity

All iterator operations must take amortized constant time.

Models

  • T *
  • std::vector<T>::iterator
  • std::vector<T>::const_iterator
  • std::deque<T>::iterator
  • std::deque<T>::const_iterator

See also

Copyright © 2001, 2002 Indiana University
Copyright © 2000, 2001 University of Notre Dame du Lac
Copyright © 2000 Jeremy Siek, Lie-Quan Lee, Andrew Lumsdaine
Copyright © 1996-1999 Silicon Graphics Computer Systems, Inc.
Copyright © 1994 Hewlett-Packard Company

PrevUpHomeNext