advertisement

Print

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

Standard algorithms need to know more about the iterators they are using than my Iterator class provides. Specifically, they need to know the category of iterator, the type of the difference between two iterators, and other sorts of things. Usually, this is used by standard library implementations to write function templates that are specific to each kind of template argument, where applicable. This information is packaged up using the standard class iterator_traits. You can create a specialization of iterator_traits explicitly, but it is far easier to let the standard library do it for you by inheriting from the Iterator class in <iterator>. Here's how I did it:

class Iterator : public
   std::iterator<std::forward_iterator_tag, T> {
Now, your iterator will work with the standard algorithms, like this:
list<int> lst;
copy(q.begin(), q.end(),
   back_inserter(lst));

The Iterator class does not provide virtual functions (as you might expect) that you're supposed to override. It is used only to package up information about the iterator so it can be accessed by consumers. All you need to do is inherit from it to get this information for free; once you do, you can operate with the standard algorithms (and other non-standard libraries that do the same thing, such as those in the Boost project) with minimal effort.

I have presented the solution in pieces in the previous examples. See the code at the end of this article for a complete implementation of SQueue with the Iterator class. Adopting the iterator pattern to your data structure is a relatively simple process that gives you a number of benefits. The two most apparent are the familiar interface iterators offer and the interoperability with the standard library. The examples I gave above should get you on your way to implementing iterators effectively.

Example 2. A complete implementation

#ifndef SQUEUE_H__
#define SQUEUE_H__

#include <stdexcept>
#include <iterator>

// A simple queue as a singly-linked list
template<typename T>
class SQueue {

private:
   // The Node class holds the value
   class Node {
   public:
      Node(const T& val) : next_(NULL), val_(val) {}
      T& getVal() {return(val_);}
      Node* next_;
   private:
      T val_;
   };

   Node* root_;
   Node* last_;

public:
   SQueue() : root_(NULL), last_(NULL) {}
  ~SQueue()
   {
      delete root_;
   }

   void pushBack(const T& val)
   {
      if (root_ == NULL)
      {
         root_ = new Node(val);
         last_ = root_;
      }
      else
      {
         Node* p = new Node(val);
         last_->next_ = p;
         last_ = p;
      }
   }

   T popFront()
   {
      if (root_ == NULL)
      {
         throw std::out_of_range("Queue is empty");
      }
      else
      {
         Node* p = root_;
         root_ = root_->next_;
         return(root_->getVal());
      }
   }

   // Here is my custom iterator.  The only kind of iterator this data
   // structure can reasonably support is a forward iterator, so that's
   // what I provide.  I embedded the definition of the iterator within
   // the class it will iterate through for convenience.
   class Iterator :
      public std::iterator<std::forward_iterator_tag, T> {
   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());
      }

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

   private:
      Node* node_;
   };

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

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

#endif // SQUEUE_H__

Ryan Stephens is a software engineer, writer, and student living in Tempe, Arizona. He enjoys programming in virtually any language, especially C++.


Return to the O'Reilly Network