Guidelines to an Iterator Class

Question

I have a Red Black tree implemented in c++. It supports the functionality of a STL map. Tree nodes contain keys and the values mapped. I want to write an iterator class for this, but I'm stuck with how to do it. Should I make it an inner class of the Tree class? Can anyone give me some guidelines on how to write it + some resources??

Thank You!!

Answer 1

Sure, read this nice article on writing STL iterators, it might give you the needed overview:

http://www.drdobbs.com/184401417

In general, yes, an inner class is good, because the iterator needs access to your implementation specific tree nodes:

struct container { ...
public:
  struct iterator {
    // these typedefs are needed if you want to be STL compatible
    typedef std::forward_iterator_tag iterator_category;
    typedef T         value_type;
    typedef T*        pointer;
    typedef T&        reference;
    typedef size_t    size_type;
    typedef ptrdiff_t difference_type;

    // the element points to your implementation node
    iterator( element* init = 0 ) : current(init) {}
    T& operator*() { return current->data; } // dereference
    const T& operator*() const { return current->data; }
    iterator& operator++() { // prefix
      if ( current ) current = current->next;
      return *this;
    }
    iterator operator++(int) { // postfix
      iterator temp = *this;
      ++*this;
      return temp;
    }
    bool operator==(const iterator& x) const { return current == x.current; }
    bool operator!=(const iterator& x) const { return current != x.current; }

  private:
    // the element points to your implementation node
    element* current;
  }
  ...

The good thing here is that while the iterator is public, the element can still stay private :). And yes, the code above is STL compilant too!

Answer 2

I thought I would add my own little batch of advice.

The first thing I'd like to note is that iterator and const_iterator are very likely to have much of their implementation in common. However, even though their code is similar, it's not exactly identical. This begs for templates.

The second thing I'd like to note is that a const_iterator should be constructible from an iterator (implicitly), but not the other way around.

The third thing I'd like to note is that if you wish to have a map-like interface, then you need to provide a reverse_iterator and const_reverse_iterator as well.

From a style point of view, I tend not to put the implementation of the iterator itself right in the class. I find it unreadable when the class implementation is cluttered with so much code that you struggle to see the types and methods available. For this reason I would recommend putting the implementation outside the class.

Finally, I definitely recommend Boost.Iterator. You may not use it, but read the material, it'll notably give you insight on how to write the code once and use it for the 4 kinds!

Quick illustration:

namespace detail {
  template <class Value> class base_iterator;
}

template <class Value>
class container
{
public:
  typedef detail::base_iterator<Value> iterator;
  typedef detail::base_iterator<Value const> const_iterator;

  typedef boost::reverse_iterator<iterator> reverse_iterator;
  typedef boost::reverse_iterator<const_iterator> const_reverse_iterator;
};

I don't know about you, but I feel good when I do only a quarter of the work and leverages a compiler/library to fill in the rest for me :)

Answer 3

The iterator class needs to be either a nested class, or at least a typedef that aliases your_map::iterator to some type that's defined elsewhere. A nested class is usually the cleanest/easiest route though.

As far as resources go, one possible source of help would be the Boost::iterator library, which includes components intended to make iterators easier to implement.