C++, Implementing a custom iterator for binary trees (long)

Question

Please be nice- this is my first question. =P

Basically as a summer project I've been going through the list of Data Structures on the wikipedia page and trying to implement them. I took a C++ course last semester and found it to be great fun, as a final project I implemented a Binomial Heap- this was also very fun. Maybe I'm nerdy but I love data structures.

Anyway, enough back story. The project is going well, I'm starting with Binary Trees. To go much further though I need to create iterators to traverse the trees. I've already decided I'll create two types of iterators for each traversal method (regular iterator and const iterator), I just have no idea how to do this. I've heard of inheriting from stl's iterator stuff, or even using boosts iterator_facade (which seems like a good option)

I have not even attempted to write the iterator code yet as I do not know where to start, but I do have my current code up on github. You can check it out here.

In case you're opposed to github, I'm pasting the relevant class definitions. The implementations of these functions wouldn't really be of any help, but if you need them for some reason let me know. Also, the node class has a parent pointer for iteration purposes.

#ifndef __TREES_HXX
#define __TREES_HXX
#include <cstdlib>  // For NULL
#include <algorithm> // for std::max

// Node class definition. These nodes are to be used for any
// tree where the structure is
//    node
//     /\
// left  right
//  /\    /\
//
// etc., basically two children.
template <typename T>
class Node
{
  public:
    T data_;
    Node<T>* left_;
    Node<T>* right_;
    Node<T>* parent_; // Needed for iterators

    explicit Node(T const&);
    Node(Node<T> const&);
};

template <typename T>
class BinaryTree
{
  protected:
    typedef Node<T>* node_t;
    size_t tree_size;

  public:
    typedef T value_type;

    explicit BinaryTree();
    explicit BinaryTree(T const&);
    ~BinaryTree();

    virtual node_t insert(node_t&, T) = 0;
    virtual T& lookup(node_t const&, T const&) const = 0;
    inline virtual size_t size() const;
    inline virtual size_t depth(node_t const&) const;
    inline bool empty() const;
    inline void clear(node_t);

    node_t root;
};

This is the basic Binary Tree extension of our abstract class, basically it (will be) a BST. For an example of why I need iterators, look at the definition of the lookup function. It should be returning an iterator to the node where the stuff is found.

/* Implementation of our Binary Tree is in
 * this file. The node class is in Trees.hxx
 * because it's intended to be a general class.
 */

 #ifndef __BINARY_TREE_HXX
 #define __BINARY_TREE_HXX

 #include "Trees.hxx"


 template <typename T>
 class BiTree : public BinaryTree<T>
 {
   private:
     typedef typename BinaryTree<T>::node_t node_t;

   public:
     typedef typename BinaryTree<T>::value_type value_type;

     BiTree() : BinaryTree<T>()
     {
     }

     BiTree(T const& data) : BinaryTree<T>(data)
     {
     }

     node_t insert(node_t&, T);
     T& lookup(node_t const&, T const&) const; // Note: This should return an iterator to the node where the stuff is found
 };

I think that's it- thanks for your time! If you need additional info let me know.

Answer 1

1. Fat Iterators vs Lean Iterators

There are two possible ways to implement the traversal of a tree. You may either:

• have nodes that simply points to their "children", and iterators that keep a stack (thus, fat iterators)
• have nodes that have a parent pointer (like yours), and iterators that are just pointers to a given node (lean iterators)

It's a design trade-off, the STL implementors usually go the lean way because iterators (in the STL) are supposed to be cheap to copy.

2. Easy Iterators vs From scratch iterators

There are also several ways to implement iterators:

• From Scratch: you do everything yourself, which includes defining typedef, all operator overloads etc...
• Easy: you use Boost.Iterator to implement as few code as possible by yourself

I basically count inheriting from std::iterator as a "from scratch" situation, since it provides a mere 5 typedef...

Whether to choose one or the other really depends on your situation:

• For learning purpose, I would recommend going the "From Scratch" way a few times
• For production purpose, I would recommend going the "From Scratch" way (inheriting from Boost does not save much, but it does complicate debug session / memory dumps, at least with gdb, because gdb exposes base classes)
• For quick testing, I would recommend going the "Easy" way

Note that you may be in a bizarre situation where your iterator cannot really be built on top of Boost.Iterator, in which case you'll have no choice but to build it by yourself.

3. Const and non-const iterators

This is, perhaps, the main point.

If only for this, it's worth looking at Boost.Iterator, because they expose the technique to implement one iterator (templated) that will cover both cases.

Look at the Tutorial Example section in the Iterator Adaptor:

template <class Value>
class node_iter
  : public boost::iterator_adaptor<
        node_iter<Value>                // Derived
      , Value*                          // Base
      , boost::use_default              // Value
      , boost::forward_traversal_tag    // CategoryOrTraversal
    >
{
 private:
    struct enabler {};  // a private type avoids misuse

 public:
    node_iter()
      : node_iter::iterator_adaptor_(0) {}

    explicit node_iter(Value* p)
      : node_iter::iterator_adaptor_(p) {}

    /// !!! Highlight !!!
    template <class OtherValue>
    node_iter(
        node_iter<OtherValue> const& other
      , typename boost::enable_if<
            boost::is_convertible<OtherValue*,Value*>
          , enabler
        >::type = enabler()
    )
      : node_iter::iterator_adaptor_(other.base()) {}

 private:
    friend class boost::iterator_core_access;
    void increment() { this->base_reference() = this->base()->next(); }
};

The 3rd constructor is the key point to get a pair of const and non-const iterators with automatic conversion from const to non-const without the reverse conversion being possible.

Whatever you do, reuse the same trick: templatize a BaseIterator on Value, and the provide the two typedefs: typedef BaseIterator<Value> iterator and typedef BaseIterator<Value const> const_iterator.

Answer 2

One way to implement this is to have a stack in your iterator that keeps track of parent nodes. Each time you arrive at a node, it's it's not a leaf, push it onto the stack and go on to the next node in the search order. Once you hit a leaf, process it, then return to the node on top of the stack. Repeat ad nausium until you've visited everything.