C++ Primer Plus

There are more things an iterator could do, but nothing more it need do—at least, not for the purposes of a find function. Actually, the STL defines several levels of iterators of increasing capabilities, and we’ll return to that matter later. Note, by the way, that an ordinary pointer meets the requirements of an iterator. Hence, you can rewrite the find_arr() function like this:

typedef double * iterator;

iterator find_ar(iterator ar, int n, const double & val)

{

    for (int i = 0; i < n; i++, ar++)

        if (*ar == val)

            return ar;

    return 0;

}

Then you can alter the function parameter list so that it takes a pointer to the beginning of the array and a pointer to one past-the-end of the array as arguments to indicate a range. (Listing 7.8 in Chapter 7, “Functions: C++’s Programming Modules,” does something similar.) And the function can return the end pointer as a sign the value was not found. The following version of find_ar() makes these changes:

typedef double * iterator;

iterator find_ar(iterator begin, iterator end, const double & val)

{

    iterator ar;

    for (ar = begin; ar != end;  ar++)

        if (*ar == val)

            return ar;

    return end;   // indicates val not found

}

For the find_ll() function, you can define an iterator class that defines the * and ++ operators:

struct Node

{

    double item;

    Node * p_next;

};

class iterator

{

    Node * pt;

public:

    iterator() : pt(0) {}

    iterator (Node * pn) : pt(pn) {}

    double operator*() { return pt->item;}

    iterator& operator++()     // for ++it

    {

        pt = pt->p_next;

        return *this;

    }

    iterator operator++(int)  // for it++

    {

        iterator tmp = *this;

        pt = pt->p_next;

        return tmp;

    }

// ... operator==(), operator!=(), etc.

};

(To distinguish between the prefix and postfix versions of the ++ operator, C++ adopted the convention of letting operator++() be the prefix version and operator++(int) be the suffix version; the argument is never used and hence needn’t be given a name.)

The main point here is not how, in detail, to define the iterator class, but that with such a class, the second find function can be written like this:

iterator find_ll(iterator head, const double & val)

{

    iterator start;

    for (start = head; start!= 0; ++start)

        if (*start == val)

            return start;

    return 0;

}

This is very nearly the same as find_ar(). The point of difference is in how the two functions determine whether they’ve reached the end of the values being searched. The find_ar() function uses an iterator to one-past-the-end, whereas find_ll() uses a null value stored in the final node. Remove that difference, and you can make the two functions identical. For example, you could require that the linked list have one additional element after the last official element. That is, you could have both the array and the linked list have a past-the-end element, and you could end the search when the iterator reaches the past-the-end position. Then find_ar() and find_ll() would have the same way of detecting the end of data and become identical algorithms. Note that requiring a past-the-end element moves from making requirements on iterators to making requirements on the container class.

The STL follows the approach just outlined. First, each container class (vector, list, deque, and so on) defines an iterator type appropriate to the class. For one class, the iterator might be a pointer; for another, it might be an object. Whatever the implementation, the iterator will provide the needed operations, such as * and ++. (Some classes may need more operations than others.) Next, each container class will have a past-the-end marker, which is the value assigned to an iterator when it has been incremented one past the last value in the container. Each container class will have begin() and end() methods that return iterators to the first element in a container and to the past-the-end position. And each container class will have the ++ operation take an iterator from the first element to past-the-end, visiting every container element en route.

To use a container class, you don’t need to know how its iterators are implemented nor how past-the-end is implemented. It’s enough to know that it does have iterators, that begin() returns an iterator to the first element, and that end() returns an iterator to past-the-end. For example, suppose you want to print the values in a vector object. In that case, you can use this:

vector::iterator pr;

for (pr = scores.begin(); pr != scores.end(); pr++)

    cout << *pr << endl;

Here the following line identifies pr as the iterator type defined for the vector class:

vector::iterator pr;

If you used the list class template instead to store scores, you could use this code:

list::iterator pr;

for (pr = scores.begin(); pr != scores.end(); pr++)

    cout << *pr << endl;