Iterator for traversing a tree

Question

What I want to achieve is the following:

#include "tree.h"

#include <iostream>

int main() {

  Tree<std::string>* tA = new Tree<std::string>("A");
  Tree<std::string>* tB = new Tree<std::string>("B", tA);
  Tree<std::string>* tC = new Tree<std::string>("C", tA);
  Tree<std::string>* tD = new Tree<std::string>("D", tB);
  Tree<std::string>* tE = new Tree<std::string>("E", tB);
  Tree<std::string>* tF = new Tree<std::string>("F", tB);

  for (auto cur : *tA) {
    std::cout << "traversed from " << (cur->parent ? cur->parent->val : "NULL") << " to " << cur->val <<  std::endl;
  }

  // std::next(std::next(tF->begin()));

  return 0;
}

And here is my implementation.

#ifndef TREE_H
#define TREE_H

#include <iterator>
#include <stack>
#include <vector>

#include <iostream>

template <typename T>
class Tree {
 public:
  class iterator {
   public:
    using iterator_category = std::forward_iterator_tag;
    using value_type = T;
    using difference_type = std::ptrdiff_t;
    using pointer = T*;
    using reference = T&;

   public:
    iterator() = default;

    iterator(Tree<T>* const root);

    Tree<T>* operator*() const;

    iterator& operator++();

    bool operator!=(iterator const& other) const;

    Tree<T>* cur;

   private:
    std::stack<Tree<T>*> s_;
  };

 public:
  Tree() = default;

  Tree(T const& val, Tree<T>* parent = NULL);

  void* operator new(size_t size);

  iterator begin();

  iterator end();

  T val;

  Tree<T>* const parent = NULL;

 private:
  std::vector<Tree<T>*> children_;
};


template <typename T>
Tree<T>::iterator::iterator(Tree<T>* const root)
    : cur(root) {}

template <typename T>
Tree<T>* Tree<T>::iterator::operator*() const {
  return cur;
}

template <typename T>
typename Tree<T>::iterator& Tree<T>::iterator::operator++() {
  if (cur == NULL) {
    throw std::out_of_range("No more nodes for traversal");
  }

  for (auto& child : cur->children_) {
    s_.push(child);
  }

  if (s_.empty()) {
    cur = NULL;
  } else {
    cur = s_.top(); s_.pop();
  }

  return *this;
}

template <typename T>
bool Tree<T>::iterator::operator!=(Tree<T>::iterator const& other) const {
  return cur != other.cur;
}

template <typename T>
Tree<T>::Tree(T const& val, Tree<T>* const parent)
    : val(val), parent(parent) {
  if (parent) {
    parent->children_.push_back(this);
  }
}

template <typename T>
void* Tree<T>::operator new(size_t size) {
  void* p = ::new Tree<T>();
  return p;
}

template <typename T>
typename Tree<T>::iterator Tree<T>::begin() {
  return iterator(this);
}

template <typename T>
typename Tree<T>::iterator Tree<T>::end() {
  return iterator();
}

#endif

User should be able to directly modify val (hence it is public). However, they shouldn't be able to modify any parent/children relationship. Therefore I try to make parent a const pointer, but I cannot make children a list of const pointers because anything inside a std::vector must be assignable. I am considering exposing a GetChildren() method which returns a const std::vector, but that would be inconsistent with how I dealt with parent. Can anyone show a good way to resolve this?

General reviews are welcome. More specifically, I want to know

1. Is this a good and correct use of pointers?
2. Is the interface well designed?
3. Are there any const that I missed?

Answer 1

• Clean up allocated memory (everything newed should be deleted), or use smart pointers to do it for you. (Perhaps each tree node should own its children, and store them in unique_ptrs, and the parent should be a raw pointer).

• There doesn't seem to be any benefit to overloading operator new for the Tree class.

• Currently, the iterator is more of a sub-tree iterator, as it never returns to the parent. e.g. for a tree with edges: A->B->C and A->D if you start iterating at B, you will only iterate from B to C, and never reach D.

• Iterators are normally defined outside of the corresponding container class. We can use an iterator typedef in the container to refer to the iterator class.

• operator* should return a reference, not a pointer (operator-> should return a pointer).

• We have !=, but no ==.

• We have a pre-increment operator++, but not post-increment operator++.

• It would probably be best to write unit tests for things that are expected to work, e.g.: *i (returns a modifiable reference), *i++ (returns a modifiable reference and then increments i to point at the next value), etc. This can be tedious, but is really the only way to ensure correctness.

• The full requirements for a forward iterator are listed here (and in the linked pages), and many of them could be translated into tests cases. This iterator should arguably be a bidirectional iterator.

• Standard containers also supply a const_iterator version (and reverse iterators, though that's usually simple to add).

To be honest, I'd suggest starting with something a bit simpler like an array class, and corresponding iterators.

---

Note that we can traverse a tree in many different ways (depth-first in-order, depth-first pre-order, depth-first post-order, breadth-first). For a full-featured implementation of this sort of thing, see the ASL Forest class.

Since we're iterating nodes, not values, we don't have to worry about "order", but we should still call the class something like tree_depth_first_iterator, to distinguish it from the alternative(s).

---