Chapter 7: Iterators

Last updated 06 May 1998

§ 7.1 -- Introduction

It is a rare program which does not involve iterating through some data structure. Tradeoffs between the ease of iteration, the data structure memory required to support iteration, and similar issues, can be critical to the performance of a program. Yet in spite of the fact that such iteration is conceptually trivial, its precise implementation can make a significant difference in the form of the code.

As a result, the abstraction of methods for iterating through data is critical to programming generically. In this chapter we will develop a family of such abstractions, identifying requirements, classifying the useful cases, and formally axiomatizing them.

§ 7.2 -- Positions in a Sequence

Developing abstractions does not proceed axiomatically from first principles, but must begin with concrete examples. The abstractions with which we deal in generic programming emerged after years of studying such examples. Here we will attempt to telescope this process. Necessarily this will be somewhat artificial, but we hope to capture some of the essence of the process by looking at a few key problems.

One of the most important problems both in computer science literature and in programming practice is linear search: given a sequence of values and a test value, we want to find a member of the sequence with value equal to the test value, if such a member exists. Let us look first at a typical solution of this problem. Here the sequence is an array of integers; the test value, naturally, is an integer also. The size of the array is passed as a parameter.

   int find(int a[], int size, int value) {
     int i;
     for (i = 0; i < size; i++)
       if (a[i] == value) return i;
     return -1;
   }

On the other hand, this function is very specifically adapted to arrays. In order to see if we can get at the essential features of the problem, let's try to make a version that works on singly linked lists and see whether a study of the differences will give as a clue to how to write a generic algorithm.

Suppose then that we have a simple "list-of-integer" type declared as

   struct list {
     int value;
     list * next;
   };

Here we have no indices to return. What should the return type be? We want something that will get us to a particular position in the list, and the obvious choice is "list *." Returning a pointer to an element of the list allows us to get to it, and we can return a null pointer if we don't find an element with value equal to the test value. So we might try something like

   struct list {
     int value;
     list * next;
   };

   list * find(list * l, int value) {
     list * p;
     for (p = l; p != NULL; p = p->next)
	if (p->value == value) return p;
     return NULL;
   }

We also do not have an extra variable of different type. (It is of course entirely coincidental that the type of i is the same as the type of the test value in the array version.)

In fact, the trouble with the array version is that arrays are too rich a type to make it easy to see the essentials of the problem. They have a subscript operator, an ordering on indices, and so on.

Suppose we try to make the array example more like the list example. Since our goal is a generic algorithm, eventually we want to have the same code.) The first thing we're going to want to do is to change the return type from int to int *; that is we're going to return a pointer to the array element that's equal to the test value instead of an index into the array.

But if we don't use an index, how are we going to terminate? (The i < size condition). Fortunately, the rules of C and of C++ allow us to refer to the address one past the end of the array, so we can rewrite the function as follows (replacing the complicated "for" construction by the simpler while loop at the same time):

   int * find(int *a, int size, int value) {
      int * p = a;
      while (p != a + size) {
        if (*p == value) return p;
	++p;
      }

      return ???
   }

The size parameter is still awkward. How is it actually used? It's used only in the expression p != a + size, and of course a + size has the same type as p or as a, which suggests the modification

   int * find(int * a, int * b, int value) {
     int * p = a;
     while (p != b) {
       if (*p == value) return p;
       ++p;
    }
    return p;
  }

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

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

Meanwhile, we've moved way ahead of the list version. Let's go back and look at it now.

Suppose we use the exact same code except with "int *" replace by "list". This gives us

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

What we need is not a pointer to list, but something that behaves with respect to a list the way a pointer behaves with respect to an array.

Let's call it a list_iterator. What does it need? We know it needs somehow to encapsulate a pointer to list, and it needs to have an operator* returning an int (we're still just dealing with a list of ints), and an operator++ that makes the encapsulated pointer point to the next item on the list. We might try

struct list_iterator {
  list * current;
  int operator*() {return current->value;}
  void operator++() {current = current->next;}}
};

struct list_iterator {
  list * current;
  list_iterator(list * l): current(l) {}
  int operator*() {return current->value;}
  void operator++() {current->next;}}
};

inline bool operator==(const list_iterator& i1, const list_iterator& i2) {
  return i1.current == i2.current;
}

inline bool operator != const list_iterator& i1, const list_iterator& i2) {
  return !(i1 == i2);
}

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

Furthermore, we are now ready to write this algorithm in generic form and to isolate the assumptions we need to make about iterators in order for it to work.

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

Passing a parameter by value means that a copy is generated to do the call. For an arbitrary type T, a copy may be quite expensive. In our algorithm, value is not modified in the code, so we are probably better off passing it by const reference rather than by value.

The parameter first is modified in the code, so we cannot very well pass it by reference; presumably the user of find wants to retain the value passed in and not have it modified. So first should definitely be passed by value.

The case of last is less clear-cut. It is not modified by the code, so it could be passed by const reference. This would, however, make the interface awkwardly asymmetrical. Also, there is a cost associated with passing by reference, since it means passing a pointer instead of a value, and necessitates an extra indirection. So we need to ask ourselves whether the copy of an iterator is likely to be expensive. In our two examples, the iterator copy is cheap: in the array case, the iterator is just a pointer; in the list case, the iterator is an encapsulated pointer: its only data member is just a pointer. And in general we expect an iterator not to have a lot of parts. So in almost all the generic algorithms we will study, and in the STL in general, iterator parameters are generally passed by value, not by reference.

The above discussion suggests that we should make just one change to our find algorithm: changing the declaration of the value parameter so that it is passed by const reference rather than by value. This change gives us

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

The type that we have called "Iterator" must satisfy certain requirements in order for our "find" algorithm to work. C++ does not provide any mechanism within the language for specifying such requirements on the parameters to a template, so such specifications will belong to documentation, which is a very important part of generic programming in C++.

We're not going to get all the requirements right immediately. We'll make a start and refine our definitions as we progress. We're going to have to look at a few algorithms, not just find before we really see what is going on.

We can see immediately from the code for the find algorithm that Iterator must support three operations, '*', '++' and '!='. What are the requirements on these operations?

First of all, when we say the iterator type supports '*' for example, we do not mean that '*' can be applied to everything of that type. If we think of iterators as a generalization of pointers, we see this immediately: we cannot dereference a null pointer, for example. Similarly, we cannot always legitimately increment a pointer. Indeed, if we look at find, we are careful to check that first != last before we try to dereference first. But if we find that first != last, then we can dereference first and also increment it.

Let us see what we can make of these rambling remarks. First of all, it seems useful to distinguish between valid and invalid values of an iterator. A valid value of an iterator can always be dereferenced, but a value may be valid even thought it cannot be dereferenced. Such a value we call past-the-end. We need to be able to compare to a past-the-end value to make find work. Furthermore, if i is dereferenceable, then ++i is valid, and vice versa. Valid values of an iterator can always be compared for equality (or inequality). Furthermore if i and j are iterators with i == j, and i is dereferenceable, the j is dereferenceable, and *i and * j are not just equal, they are the same object; that is &*i == &*j. (This holds even if no equality is defined on objects of the type of *i!).

Note that the systematizing impulse has taken on a life of its own here. We get some hints from our algorithm (quit a lot of hints for such a simple algorithm); some from the given properties of C and C++ pointers. But we also need to appeal to common sense, mathematical general principles, and a little imagination. We hope we're getting things more or less right: if our axioms are too restrictive we'll miss some important applications; if they're too general we won't be able to do anything with them. Getting things right may require a few rounds of refinement as we look at more algorithms.

§ 7.3 -- Varieties of Iterators

It's time to try another algorithm. Another thing we do all the time is copy: reading a list of numbers into an array, copying one array to another, and printing a list of numbers from an array are all examples of a problem that seems to cry out for a generic algorithm.

By now we should have a good idea of how to start:

template<class Iterator>
Iterator copy(Iterator first, Iterator last, Iterator out) {
  while (first != last)
    *out++ = *first++;
  return out;
}

Hey, that was easy! Unfortunately, it's not quite right. Looking at the examples in the opening paragraph, it's clear we can use this to copy one array to another, but not to read numbers into an array or print numbers from an array, because we only have one iterator type here. What we need is one type for input (what we copy from) and one type for output (what we copy to). With this correction, we get

template <class Iterator1, class Iterator2>
Iterator2 copy(Iterator1 first, Iterator1 last, Iterator2 out) {
  while (first != last)
    *out++ = *first++;
  return out;
}

Now this is really quite nice. Note the convenience of the return value. It points just beyond the last item copied. So if we want to copy something else at the end, we're all set to do so.

Another nice thing is that our algorithms work well together. Here, for example, is a function to copy the values between the first and second zero in a sequence:

template <class Iterator1, class Iterator2>
Iterator2 copy_between_zeros(Iterator1 first, 
			     Iterator1 last, 
		 	     Iterator2 out) {
  first = find(first, last, 0);
  if (first == last) return out;
  return copy(++first, find(first, last, 0), out);
}

Section: Iterator Axioms and Models

Present Peano axioms and modify.

Section: Iterator Categories

Section: Iterator Traits and Compile-time Dispatch

Section: Iterator Adapters

Reverse iterators and stride iterators are the key examples here.

Send comments about this page to John Wilkinson, Jim Dehnert or Alex Stepanov.