advertisement

Print

What Is an Iterator in C++, Part 2
Pages: 1, 2, 3, 4, 5

The implementation of SQueue is not important. What is important here is that you want to provide an interface to SQueue whereby client code can examine each of the elements one at a time, in the same way that you might iterate through a list. Since this is a singly linked structure, the only type of iterator you can reasonably provide is a forward iterator.



As I said earlier, there are two good reasons to add an iterator to SQueue. First, a user of SQueue can iterate through elements in the queue in the same way that he could iterate through a standard container. For example, printing out each element in an SQueue might look like this:

SQueue<int> q;
// Fill up q with ints

for (SQueue<int>::Iterator it = q.begin();
     it != q.end(); ++it) {
   cout << "*it = " << *it << endl;
}

Second, you want users of SQueue to be able to use it with standard algorithms, like this:

list<int> lst;
std::copy(q.begin(), q.end(),
   back_inserter (lst));

This example uses the standard library algorithm copy (declared in <algorithm>) to copy each element in the SQueue q into the list named lst. back_inserter is a standard library function template defined in <iterator> that returns an output iterator, which repeatedly calls push_back on its container argument.

A custom iterator will satisfy both of the use cases. At this point, you know which category of iterator you want to support, and therefore you should be aware of all of the member functions you need to implement (see part one of this series for more information about iterator categories). Here is a simple Iterator class that meets the first use case:

class Iterator {
   public:
      Iterator(Node* p) : node_(p) {}
     ~Iterator() {}

      // The assignment and relational operators are straightforward
      Iterator& operator=(const Iterator& other)
      {
         node_ = other.node_;
         return(*this);
      }

      bool operator==(const Iterator& other)
      {
         return(node_ == other.node_);
      }

      bool operator!=(const Iterator& other)
      {
         return(node_ != other.node_);
      }

      // Update my state such that I refer to the next element in the
      // SQueue.
      Iterator& operator++()
      {
         if (node_ != NULL)
         {
            node_ = node_->next_;
         }
         return(*this);
      }

      Iterator& operator++(int)
      {
         Iterator tmp(*this);
         ++(*this);
         return(tmp);
      }

      // Return a reference to the value in the node.  I do this instead
      // of returning by value so a caller can update the value in the
      // node directly.
      T& operator*()
      {
         return(node_->getVal());
      }

      // Return the address of the value referred to.
      T* operator->()
      {
         return(&*(SQueue<T>::Iterator)*this);
      }

   private:
      Node* node_;
   };

The first thing you will probably notice in my Iterator class is that it uses private members of SQueue. It has to, since it needs to be able to advance from one element to the next, which can't be done without knowing SQueue's internal structure. I could make Iterator go through a public interface to SQueue, but that would be a convoluted design, since the only reason for Iterator's existence is to know the details of how SQueue works and to provide an interface to the outside world: creating an interface for the iterator itself to use would be redundant.

I embedded the definition of Iterator within the definition of SQueue to provide it access to SQueue's private members. Doing so gives Iterator access to SQueue's private data. It makes more sense to do it this way than to create a standalone Iterator class and declare it a friend of SQueue, because Iterator is only used by SQueue, so there's no reason to make it a standalone class.

Once you have added the Iterator definition as I just did, you have to provide member functions that return an Iterator so clients can use it. The standard containers' begin and end functions provide a good model for this. Here's how I would implement them:

Iterator begin() {
   return(Iterator(root_));
}

Iterator end() {
   return(Iterator(NULL));
}

The begin member function returns an iterator that refers to the first element in the sequence, which is pointed to by root_. end returns an Iterator that points to nothing, which satisfies the one-past-the-end semantics of the standard containers, since I also implemented the ++ operator such that when the user advances past the end of the sequence, he gets an Iterator that refers to NULL. This allows the equality test of the Iterator returned by end and an Iterator that has been advanced past the last element to return true.

Note that the definition of Iterator in the body of SQueue must come before the begin and end member functions (or you must use a forward declaration of Iterator), since they both refer to the Iterator class. Not to worry: if you refer to Iterator before declaring it, your compiler will be sure to point out your oversight. There are two ways to dereference my iterator, with the * or -> operators. I implemented them like this:

T& operator*()
{
   return(node_->getVal());
}

T* operator->()
{
   return(&*(SQueue<T>::Iterator)*this);
}

The first member function returns a reference to the value referred to by the iterator. This differs from the standard containers, which return copies of the objects they contain, not references to them. You can do it either way, but be aware of the implications of departing from the semantics the standard containers follow, because it can be misleading for users of your classes.

The second member function implements the right-arrow operator for referring to an object's members. There is a lot going on in the return statement, so here's a more explicit version:

T* operator->()
{
   SQueue<T>::Iterator tmp = *this; // *this is an Iterator
   T& theVal = *tmp; // dereference *this to get the value
   return (&theVal); // Return the address of the referent
}

This lets users store objects in your queue, then invoke members on those objects like this:

SQueue<MyClass> q;
// fill up q with MyClass instances
SQueue<MyClass>::Iterator p = q.begin();

// This calls MyClass::foo on the first element in q
p->foo();

Of course, this only works if the type of element in the container is a class or struct and can therefore have its members referred to using the -> operator. Don't sit back and relax just yet. At this point, you are functionally only halfway there, because Iterator as defined above will not work with standard library algorithms. This only requires a subtle change, though, so don't worry.

Pages: 1, 2, 3, 4, 5

Next Pagearrow