Standard Template Library Programmer's Guide

Category: iterators

Component type: type

Random_access_iterator is an iterator base class: it is intended that an iterator that is a model of Random Access Iterator, and whose value type and distance type are T and Distance , may be defined by inheriting from random_access_iterator [1]. Random_access_iterator is entirely empty: it has no member functions, member variables, or nested types. It exists solely to simplify the definition of the functions iterator_category , distance_type , and value_type .

class my_random_access_iterator : public random_access_iterator {

…

};

This declares my_random_access_iterator to be a Random Access Iterator whose value type is double and whose distance type is ptrdiff_t . If Iter is an object of class my_random_access_iterator , then iterator_category(Iter) will return random_access_iterator_tag() , value_type(Iter) will return (double*)0 , and distance_type(Iter) will return (ptrdiff_t*)0 .

Defined in the standard header iterator, and in the nonstandard backward-compatibility header iterator.h. This class is no longer part of the C++ standard, although it was present in early drafts of the standard. It is retained in this implementation for backward compatibility.

Assignable

None

The distance type must be a signed integral type.

None.

None.

None.

[1] It is not required that a Random Access Iterator inherit from the base random_access_iterator . It is, however, required that the functions iterator_category , distance_type , and value_type be defined for every Random Access Iterator . (Or, if you are using the iterator_traits mechanism, that iterator_traits is properly specialized for every Random Access Iterator.) Since those functions are defined for the base random_access_iterator , the easiest way to ensure that are defined for a new type is to derive that class from random_access_iterator and rely on the derived-to-base standard conversion of function arguments.

The Iterator Tags overview, iterator_traits , iterator_category , value_type , distance_type , input_iterator , output_iterator , forward_iterator , bidirectional_iterator

Categories: algorithms, iterators

Component type: function

Distance is an overloaded name; there are actually two distance functions.

template

inline iterator_traits::difference_type distance(InputIterator first, InputIterator last);

template

void distance(InputIterator first, InputIterator last, Distance& n);

Finds the distance between first and last , i.e. the number of times that first must be incremented until it is equal to last . [1] The first version of distance , which takes two arguments, simply returns that distance; the second version, which takes three arguments and which has a return type of void , increments n by that distance.

The second version of distance was the one defined in the original STL, and the first version is the one defined in the draft C++ standard; the definition was changed because the older interface was clumsy and error-prone. The older interface required the use of a temporary variable, and it has semantics that are somewhat nonintuitive: it increments n by the distance from first to last , rather than storing that distance in n . [2]

Both interfaces are currently supported [3], for reasons of backward compatibility, but eventually the older version will be removed.

Defined in the standard header iterator, and in the nonstandard backward-compatibility header iterator.h.

For the first version:

• InputIterator is a model of Input Iterator.

For the second version:

• InputIterator is a model of Input Iterator.

• Distance is an integral type that is able to represent a distance between iterators of type InputIterator .

• [first, last) is a valid range , as defined in the Input Iterator requirements.

Constant time if InputIterator is a model of random access iterator, otherwise linear time.

int main() {

list L;

L.push_back(0);

L.push_back(1);

assert(distance(L.begin(), L.end()) == L.size());

}

[1] This is the reason that distance is not defined for output iterators: it is impossible to compare two output iterators for equality.

[2] Forgetting to initialize n to 0 is a common mistake.

[3] The new distance interface uses the iterator_traits class, which relies on a C++ feature known as partial specialization . Many of today's compilers don't implement the complete standard; in particular, many compilers do not support partial specialization. If your compiler does not support partial specialization, then you will not be able to use the newer version of distance , or any other STL components that involve iterator_traits .

distance_type , advance , Input iterator, Random access iterator, Iterator tags, iterator_traits , Iterator overview.

Categories: algorithms, iterators

Component type: function

template

void advance(InputIterator& i, Distance n);

Advance(i, n) increments the iterator i by the distance n . If n > 0 it is equivalent to executing ++i n times, and if n < 0 it is equivalent to executing --i n times. If n == 0 , the call has no effect.