advertisement

Print

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

Homemade Iterators

Since a C++ iterator provides a familiar, standard interface, at some point you will no doubt want to add one to your own classes. This is a good idea, because it allows you to plug-and-play with standard library algorithms and it lets consumers of your data structure use the same iterator interface they're probably already familiar with. Thankfully, writing your own iterators is a straightforward process, with only a couple of subtleties you need to be aware of.



Before you begin implementing your own iterator, you should decide which category you can support. Use the same design parameter as the standard library and only support an iterator category that you can implement efficiently. "Efficiently" means different things to different people, but typically this means logarithmic complexity or better. For example, among the standard containers, vector provides random access iterators, while list offers only bidirectional iterators. A list is often implemented as a doubly linked list, so you know it's possible to implement random access iterators (by advancing forward and backward to support array-style indexing of elements or iterator arithmetic), so why not provide them? Because doing so would provide linear complexity at best, and that would result in terrible performance for clients who use the random access capability to navigate back and forth.

A forward iterator is a good start. In most cases, a forward iterator suffices, and its requirements are, uh, straightforward. At a high level, a forward iterator supports assignment, tests for equality, forward advancement using the prefix and postfix forms of the ++ operator, and dereferencing that returns an rvalue or an lvalue, meaning the caller of the dereference operator can assign from the value returned or assign to it.

To use a simple example, let's say you've implemented a queue as a singly linked list, where consumers can add elements to the back with a pushBack member function, or remove elements from the front with the popFront member function. Example 1 presents some code for this class, named SQueue.

Example 1. A singly linked queue

#ifndef SQUEUE_H__
#define SQUEUE_H__

#include <stdexcept>
#include <iterator>

// A simple queue as a singly-linked list
// 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());
      }
   }
};

Pages: 1, 2, 3, 4, 5

Next Pagearrow