Generic Programming

Part III: Algorithms on Sequential Structures

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; } ```
This algorithm returns the first value of i for which a[i] is equal to the test value if there is such value, and returns -1 otherwise. This is not too bad; we can distinguish between found and not found, for example, and we return a useful value rather than a bool, so we can tell where we found the value in case we want to do something with the location: we didn't just return "true" or "false."

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; }; ```
(This is far from being a satisfactory definition, but it suffices for our immediate purpose.)

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 notice that in some ways this is more attractive than the array version. For example, the test value for termination is the same as the return value for failure, which thus loses some of its arbitrary character.

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 ??? } ```
What should we return? a - 1 is NOT guaranteed to be a valid pointer value. But p is! If it's a + size, then the search failed; otherwise it succeeded.

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; } ```
Or, just using a instead of p and renaming the parameters for mnemonic value:
 ``` int * find(int * first, int * last, int value) { while (first != last) { if (*first == value) return first; ++first; } return first; } ```
And now, we're going to return first in any case, so we may simplify further to
 ``` int * find(int * first, int * last, int value) { while (first != last && *first != value) ++first; return first; } ```
Note that in passing to this improved version, besides simplifying the code, we have made it more general, since it can be used to search in any part of an array: it doesn't have to be the whole array.

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; } ```
But this won't do at all, because *first is not an int but a struct, and ++first does not get us a pointer to the next element in the list, but an address sizeof(list) beyond 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;}} }; ```
This is on the right track, but it is not quite adequate. One problem is that our algorthm uses not just '*' and '++' but also '!=', and C and C++ do not define equality and inequality for structs. Therefore we are going to need to supply these operations. (For find we need only inequality, but we certainly expect in general to have to use both, and moreover to have them related in the obvious way: more on this later.) A second problem is that our definition provides no way to attach a list_iterator to a list. For this purpose we need a constructor for list_iterator taking a list* parameter. So let's supply the deficiencies:
 ``` 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); } ```
Finally, we rewrite the algorithm as
 ``` list_iterator find(list_iterator first, list_iterator list, int value) { while (first != last && *first != value) ++first; return first; } ```
And this now actually works, as you can easily verify.

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 Iterator find(Iterator first, Iterator list, T value) { while (first != last && *first != value) ++first; return first; } ```
This looks plausible, but is it quite right? The code looks good, but what about the interface? One decision that we need to make in writing generic algorithms in C++ is how to declare the parameters? Should we pass by value? by reference? by const reference? In this algorithm all the parameters are being passed by value. Is this right? How do we decide?

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 Iterator find(Iterator first, Iterator list, const T& value) { while (first != last && *first != value) ++first; return first; } ```
This function template has two template parameters, Iterator and T. We have a pretty good idea by now what requirements we expect of the template arguments that will get substituted for these parameters. We give a hint of what we are expecting of the first parameter by giving it the name "Iterator," but of course the compiler does not understand anything by this name. We are trying to compensate for a deficiency in the language by the use of a mnemonic name, that's all.

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 Iterator copy(Iterator first, Iterator last, Iterator out) { while (first != last) *out++ = *first++; return out; } ```
using the kind of cryptic and powerful single-instruction loop so beloved of C programmers.

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 Iterator2 copy(Iterator1 first, Iterator1 last, Iterator2 out) { while (first != last) *out++ = *first++; return out; } ```
Note that the code was OK; it was the interface that was wrong.

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