distance



Categories: algorithms, iterators	Component type: function

Prototype

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

template <class InputIterator>
inline iterator_traits<InputIterator>::difference_type
distance(InputIterator first, InputIterator last);

template <class InputIterator, class Distance>
void distance(InputIterator first, InputIterator last, Distance& n);

Description

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.

Definition

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

Requirements on types

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.

Preconditions

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

Complexity

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

Example

int main() {
  list<int> L;
  L.push_back(0);
  L.push_back(1);

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

Notes

[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.