Книга: Standard Template Library Programmer

Iterators

Iterators

In the example of reversing a C array, the arguments to reverse are clearly of type double*. What are the arguments to reverse if you are reversing a vector, though, or a list? That is, what exactly does reverse declare its arguments to be, and what exactly do v.begin() and v.end() return?

The answer is that the arguments to reverse are iterators , which are a generalization of pointers. Pointers themselves are iterators, which is why it is possible to reverse the elements of a C array. Similarly, vector declares the nested types iterator and const_iterator. In the example above, the type returned by v.begin() and v.end() is vector<int>::iterator. There are also some iterators, such as istream_iterator and ostream_iterator, that aren't associated with containers at all.

Iterators are the mechanism that makes it possible to decouple algorithms from containers: algorithms are templates, and are parameterized by the type of iterator, so they are not restricted to a single type of container. Consider, for example, how to write an algorithm that performs linear search through a range. This is the STL's find algorithm.

template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& value) {
 while (first != last && *first != value) ++first;
 return first;
}

Find takes three arguments: two iterators that define a range, and a value to search for in that range. It examines each iterator in the range [first, last), proceeding from the beginning to the end, and stops either when it finds an iterator that points to value or when it reaches the end of the range.

First and last are declared to be of type InputIterator , and InputIterator is a template parameter. That is, there isn't actually any type called InputIterator: when you call find, the compiler substitutes the actual type of the arguments for the formal type parameters InputIterator and T. If the first two arguments to find are of type int* and the third is of type int , then it is as if you had called the following function.

int* find(int* first, int* last, const int& value) {
 while (first != last && *first != value) ++first;
 return first;
}

Оглавление книги