Section 3 - Adding Iterators

2B.3.1 A Nested Iterator Class

Adding iterators to the FHlist class is a delicate and technical feat that is probably a little more than most of you can handle this early in the course. I will demonstrate the technique and you can use it as a basis for any future work you might do. Our goal is to understand what iterators do and have an appreciation for what it takes to get them to do it. You may be called on to engineer your own iterators for some higher level class in the coming weeks. The FHlist.h file is always available for your inspection, and you can come back here to review these notes.

In a manner similar to the FHvector iterator, an FHlist iterator, (say we call such an object iter) will have the following properties:

iter will behave like pointer to a Node, usually some Node in some FHlist.
iter++ and ++iter act to move iter on to the "next" (not the "prev"!) Node in the FHlist.
*iter will produce an Object (not a Node) that we can use in our client. This is counter-intuitive; iter being a "pointer" to a Node makes us expect that *iter is the Node itself, but it's not. We can do this because we are overloading our operators and we can make operator*() do whatever we wish. This is how STL lists work, so it is how FHlists will work.
FHlist's begin() will return an iterator that points to the first real Node (which means that, internally, it points to the same node mHead->next points).
FHlist's end() will return an iterator that points one item beyond the last real Node (which means it points directly at the same node tail points.)
iter can be used to safely access a Node without fear of accidental mutation, by declaring it to be a const_iterator.
iter can be used to mutate that to which it points by declaring it to be a plain iterator.

These requirements will guide and explain our implementation.

2B.3.2 Defining a Nested Template Class

The class iterator is, like Node, a nested class. Because it is substantial, we would like to also prototpye with a single line inside the FHlist prototype and provide the definitions outside/below the FHlist class. I will do that in these lectures to reinforce the syntax needed to do so.

In-Line Implementation in Actual .h Files.

Because some Mac compilers are not capable of handling externally-defined classes, you may find that the .h file in your possession reverts to the notationally-simpler, but somewhat longer, in-line technique. Whether the iterator definitions appear within the FHlist class, or are merely prototyped and defined externally, class iterator is the same nested class.

The syntax is as follows. First, the declaration prototype of iterator within FHlist:

// ---------------------- FHlist Prototype --------------------------
template <class Object>
class FHlist
{
   ... etc. ...

    // iterator prototypes - these nested classes are defined outside
   class const_iterator;
   class iterator;
   
   ... etc. ...
};

As you see, there are actually two iterator classes, one called const_iterator and one called iterator. Further down the Fhlist.h file, after the prototype and definition of all other FHlist functions, we will find the full definitions of the const_iterator and iterator classes with some curious syntax at the top of each class definition. However, once we are inside the braces, it is just like any other class prototype. Here is the const_iterator class definition, minus most of the details. I just want you to see the syntax for this external template class definition.

// definition of nested FHlist<Object>::const_iterator class -------------
template <class Object>
class FHlist<Object>::const_iterator
{
   ... etc. ...

protected:
   // protected member data
   Node *current;

   // protected constructor for use only by derived iterator
   const_iterator(Node *p) : current(p) { }
   
public:
   const_iterator() : current(NULL) { }
   
   ... etc. ...
};

Remember, the particular version of your FHlist.h file may define the iterator class in-line without the extra notation, but lengthening the FHlist class prototype considerably.

From this you can tell we will have public and protected data, and some method definitions. To keep the syntax manageable we will define all const_iterator member methods fully within the const_iterator prototype, obviating the need for further external definitions.

2B.3.3 A Base-Class / Derived Class Relationship

The required flexibility of iterators to be used on const and non-const data requires that we have two types of iterators. The way this will work is that we'll declare a base class const_iterator which has most of the functionality we need. However, this class will not allow mutation through its iterators. Then, we will derive a plain, mutable iterator class from const_iterator. This class will repeat, almost verbatim, a few of the functions of the base const_iterator, minus the const keywords. Because there is so little difference between the definitions, I won't bother explaining the plain iterator definitions, other than to show you how and where we declare them.

2B.3.4 Private Data, Constructors

With this preparation, we start building a const_iterator class. Keep in mind that this is nested within a template class that uses Object as its type parameter.

First off, we want to make sure that our FHlist methods can access all const_iterator (and iterator) methods. It is not true that because const_iterator is nested within FHlist, this will be the case. However, we can make it be true by declaring FHlist to be a friend of const_iterator. So we'll do that up front:

// definition of nested FHlist<Object>::const_iterator class -------------
template <class Object>
class FHlist<Object>::const_iterator
{
   friend class FHlist;

Next, we declare the private data of an const_iterator to be nothing other than a Node* which will be called current. We'll have a public default constructor which sets current to NULL, and a protected 1-parameter constructor (usable only by the derived non-const iterator class and the FHlist friend class). Here is all that, again assumed to be defined inside the iterator prototype:

protected:
   // protected member data
   Node *current;

   // protected constructor for use only by derived iterator
   const_iterator(Node *p) : current(p) { }

public:
   const_iterator() : current(NULL) { }

Both constructors use the special initialization syntax to place data into the current member. All the remaining methods will fall within this public section.

2B.3.5 The Operators and an Exception

Because we want our iterators to be safer than their STL counterparts, we will declare an exception which we can throw if the client tries to dereference an empty iterator. We did this with FHvector.

   // for exception throwing
   class NullIteratorException { };

Our exceptions, of which NullIteratorException is only one, will be declared in the FHlist class, not the nested iterator subclasses, for a variety of reasons. In short, it's easier for both the programmer and the client if we do it that way. You will see the exceptions thrown in the following code fragments. To see the declaration of the exceptions find your downloaded header files and look at the FHlist class template in FHlist.h.

We will throw a NullIteratorException in the * operator method. The * operator will be defined to return the actual Object & within the Node to which the iterator "points".

   const Object &operator*() const
   {
      if (!current)
         throw NullIteratorException();
      return current->data;
   }

So, we will be able to do things like cout << *iter, or, if our Object is an iTunesEntry, then we can do (*iter).getSArtist(). (We can't use -> notation with this pseudo pointer).

The prefix (++iter) and postfix (iter++) operators are defined simply. The key detail and curiosity is the unexpected appearance of int as a parameter in the postfix signature! This int does nothing other than disambiguate the signatures, so the compiler can distinguish the prefix and postfix operators. It is the usual C++ way to distinguish which ++ you mean. operator++(int) always means postfix. This is a nice little tid-bit of C++ trivia that may make you seem like a genius at the next programmers' picnic.

   const_iterator & operator++()
   {
      if (current->next != NULL)
         current = current->next;
      return *this;
   }
   
   const_iterator & operator++(int)
   {
      const_iterator old;
      old = *this;
      if (current->next != NULL)
         current = current->next;
      return old;
   }

A note about the keyword static in the postfix definition: Returning local objects is frowned upon by the compiler since they go out of scope after the function ends. This is only a warning, not an error, because usually the returned value is available (on the return stack) long enough to copy or use it in the client. However, to make the warning disappear, you can declare the return variable static which, specifically, causes its value to survive between function calls.

The operator--() and operator--(int) can be defined similarly. I'll leave that as an exercise for the reader. Finally, we define operator==() and operator!=().

   bool operator==(const const_iterator &rhs) const 
   {
      return current == rhs.current;
   }
   bool operator!=(const const_iterator &rhs) const
   {
      return !(*this == rhs);
   }

2B.3.6 The Non-Const iterator

I said I would not explain the plain iterator, because the same explanations for const_iterator work. However, I will present the entire definition here . Of course, this is all in your FHlist.h file.

// definition of nested FHlist<Object>::iterator class ---------------------
template <class Object>
class FHlist<Object>::iterator : public FHlist<Object>::const_iterator
{
   friend class FHlist;

protected:
   // chain to base class 
   iterator(Node *p, const FHlist<Object> & lst) : const_iterator(p, lst) { }

public:
   iterator() { }
   const Object &operator*() const { return const_iterator::operator*(); }
   Object &operator*()
   {
      if (!this->current)
         throw NullIteratorException();
      return this->current->data;
   }
   iterator & operator++()
   {
      if (this->current->next != NULL)
         this->current = this->current->next;
      return *this;
   }
   iterator & operator++(int)
   {
      static iterator old = *this;
      if (this->current->next != NULL)
         this->current = this->current->next;
      return old;
   }

   iterator & operator--()
   {
      if (this->current->prev != NULL)
         this->current = this->current->prev;
      return *this;
   }
   iterator & operator--(int)
   {
      static iterator old = *this;
      if (this->current->prev != NULL)
         this->current = this->current->prev;
      return old;
   }
};

The insistence on this-> in front of the member current, is a curiosity of

the template being a subclass, and
some special properties of C++ syntax.

Just know that it is needed in certain compilers and not in others.

This completes the declaration and definition of our const_iterator and iterator classes nested within the FHlist template class. You could add this to what we had and it will compile (if you defined the exception, mentioned above, in FHlist). Of course, without the FHlist methods begin() and end() that have yet to be written, we won't be able to really construct any useful iterators, and that's the subject of the next, and final, episode in our FHlist class template, coming up.