# distance_type

Category: iterators | Component type: function

### Prototype

`Distance_type` is overloaded; it is in fact five different functions.

    template <class T, class Distance>
    inline Distance* distance_type(const input_iterator<T, Distance>&);

    template <class T, class Distance>
    inline Distance* distance_type(const forward_iterator<T, Distance>&);

    template <class T, class Distance>
    inline Distance* distance_type(const bidirectional_iterator<T, Distance>&);

    template <class T, class Distance>
    inline Distance* distance_type(const random_access_iterator<T, Distance>&);

    template <class T> inline ptrdiff_t* distance_type(const T*);

### Description

`Distance_type` is an iterator tag function: it is used to determine the distance type associated with an iterator. An Input Iterator, Forward Iterator, Bidirectional Iterator, or Random Access Iterator [1] must have associated with it some signed integral type that is used to represent the distance between two iterators of that type. In some cases (such as an algorithm that must declare a local variable that represents the size of a range), it is necessary to find out an iterator's distance type. Accordingly, `distance_type(Iter)` returns `(Distance*) 0`, where `Distance` is `Iter`'s distance type.

Although `distance_type` looks like a single function whose return type depends on its argument type, in reality it is a set of functions; the name `distance_type` is overloaded. The function `distance_type` must be overloaded for every iterator type [1].

In practice, ensuring that `distance_type` is defined requires essentially no work at all. It is already defined for pointers, and for the base classes `input_iterator`, `forward_iterator`, `bidirectional_iterator`, and `random_access_iterator`. If you are implementing a new type of forward iterator, for example, you can simply derive it from the base class `forward_iterator`; this means that `distance_type` (along with `iterator_category` and `value_type`) will automatically be defined for your iterator. These base classes are empty: they contain no member functions or member variables, but only type information. Using them should therefore incur no overhead.

Note that, while the function `distance_type` was present in the original STL, it is no longer present in the most recent draft C++ standard: it has been replaced by the `iterator_traits` class. At present both mechanisms are supported [2], but eventually `distance_type` will be removed.

### Definition

Defined in the standard header iterator, and in the nonstandard backward-compatibility header iterator.h. This function 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.

### Requirements on types

The argument of `distance_type` must be an Input Iterator, Forward Iterator, Bidirectional Iterator, or Random Access Iterator. [1]

### Preconditions

None. `Distance_type`'s argument is even permitted to be a singular iterator.

### Complexity

At most amortized constant time. In many cases, a compiler should be able to optimize away `distance_type` entirely.

### Example

    template <class RandomAccessIterator, class LessThanComparable,
              class Distance>
    RandomAccessIterator __lower_bound(RandomAccessIterator first,
                                       RandomAccessIterator last,
                                       const LessThanComparable& value,
                                       Distance*)
        Distance len = last - first;
        Distance half;
        RandomAccessIterator middle;

        while (len > 0) {
            half = len / 2;
            middle = first + half;
            if (*middle < value) {
                first = middle + 1;
                len = len - half - 1;
            } else
                len = half;
        }
        return first;
    }

    template <class RandomAccessIterator, class LessThanComparable>
    inline RandomAccessIterator lower_bound(RandomAccessIterator first,
                                            RandomAccessIterator last,
                                            const LessThanComparable& value) {
        return __lower_bound(first, last, value, distance_type(first));
    }

The algorithm `lower_bound` (a type of binary search) takes a range of iterators, and must declare a local variable whose type is the iterators' distance type. It uses `distance type`, and an auxiliary function, so that it can declare that variable. [3] Note: this is a simplified example. The actual algorithm `lower_bound` can operate on a range of Random Access Iterators or a range of Forward Iterators. It uses both `distance_type` and `iterator_category`.

### Notes

[1] Note that `distance_type` is not defined for Output Iterators or for Trivial Iterators. There is no meaningful definition of a distance for either of those concepts, so there is no need for a distance type.

[2] The `iterator_traits` class 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 `iterator_traits`, and you will have to continue using the functions `iterator_category`, `distance_type`, and `value_type`. This is one reason that those functions have not yet been removed.

[3] This use of an auxiliary function is an extremely common idiom: `distance_type` is almost always used with auxiliary functions, simply because it returns type information in a form that is hard to use in any other way. This is one of the reasons that `distance_type` is so much less convenient than `iterator_traits`.

### See also

The Iterator Tags overview, `iterator_traits`, `iterator_category`, `value_type`, `output_iterator_tag`, `input_iterator_tag`, `forward_iterator_tag`, `bidirectional_iterator_tag`, `random_access_iterator_tag`

Copyright © 1999 Silicon Graphics, Inc. All Rights Reserved. TrademarkInformation