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

Question

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

Basically, as a summer project, I looked at the list of data structures on the wikipedia page and tried to implement them. Last semester, I took a C ++ course and found it to be a lot of fun, as a final project I implemented the Binomial Heap - it was also a lot of fun. I may be stubborn, but I like data structures.

In any case, enough background. The project is going well, I am starting with Binary Trees. To go much further, although I need to create iterators to traverse the trees. I already decided that I’ll create two types of iterators for each traversal method (regular iterator and constant iterator), I just don’t know how to do it. I heard about inheritance from stl iterator files or even using boosts iterator_facade (which seems like a good option)

I have not even tried to write the iterator code until I know where to start, but I have the current code on github. You can check here .

If you are against github, I am inserting the appropriate class definitions. Implementations of these functions would not really help, but if for some reason they let you know. In addition, 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 main binary tree extension of our abstract class, basically it is (will be) BST. For an example of why I need iterators, look at the definition of a search function. It should return an iterator to the node where the material is found.

 /* Implementation of our Binary Tree is in * this file. The node class is in Trees.hxx * because it 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 this is - thanks for your time! If you need more information, let me know.

Answer 1

1. Fat Iterators vs. Ion Iterators

There are two possible ways to implement tree traversal. You can:

• have nodes that simply point to their “children,” and iterators that store the stack (thus fat iterators).
• have nodes that have a parent pointer (like yours) and iterators that just point to the given node (worst iterators)

This is a design compromise, STL developers usually go a casual way, because iterators (in STL) must be cheap to copy.

2. Lightweight iterators versus zero with iterators

There are also several ways to implement iterators:

• From Scratch: you do everything yourself, including defining a typedef, all operator overloads, etc.
• Simple: you use Boost.Iterator to implement as little code yourself

I basically consider the inheritance from std::iterator be from scratch, as it provides only 5 typedef ...

Regardless of whether you choose one or the other, it really depends on your situation:

• For training purposes, I would recommend switching to "From scratches" several times.
• For production purposes, I would recommend moving from the “From scratch” path (inheriting from Boost will not save much, but it complicates debugging sessions / memory dumps, at least with gdb, since gdb provides base classes)
• For quick testing, I would recommend going Easy.

Please note that you may find yourself in a strange situation when your iterator cannot be built on top of Boost.Iterator, in which case you will have no choice but to create it yourself.

3. Constants and non-constant iterators

This is perhaps the main thing.

If only for this it is worth looking at Boost.Iterator, because they reveal a technique for implementing one iterator, which will cover both cases.

See the Case Study section in Iterator Adapter :

 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 to getting a pair of const and non const iterators with automatic conversion from const to not const without the possibility of inverse conversion.

Whatever you do, use the same trick: templatize a BaseIterator on Value and specify two types of typedef: 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 tracks the parent nodes. Each time you come to a node, this is not a leaf, push it onto the stack and move on to the next node in the search order. Once you click on the sheet, process it, and then go back to node on top of the stack. Repeat the announcement until you have visited everything.