Iterator for traversing a tree [v2]

Question

this is an update of the implementation after I followed the feedback from Iterator for traversing a tree. After that I did changed quite a bit on the design and decided to ask for another round of review. Hope this is allowed.

First is on what I want to achieve and the tests I made to ensure it is correct. For this, please help review to see if the test cases are good.

main.cpp

#include "tree.h"

#include <cassert>
#include <exception>
#include <iostream>

void traverse(Tree<std::string> root) {
  for (auto cur : root) {
    auto parent = cur.GetParent();
    std::cout << "traversed from " << (parent ? parent->val : "NULL") << " to " << cur.val <<  std::endl;
  }  
}

int main() {

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

  traverse(tA);

  try {
    std::next(std::next(tF.begin()));
  } catch (std::exception& e) {
    std::cout << e.what() << std::endl;
  }

  auto it = tA.begin();
  assert(it->val == "A");

  ++it;
  assert(it->val == "C");

  auto it2 = it++;
  assert(it->val == "B");
  assert(it2->val == "C");

  assert(it == tB.begin());
  assert(it2 == tC.begin());
  assert(it != it2);

  auto newNode = Tree<std::string>("A");
  assert(newNode != tA);

  return 0;
}

What this iterator does is to iterate through its subtree. I hope to get a critical review of the design of the interface.

tree.h

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

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>* root);

    Tree<T>& operator*() const;

    Tree<T>* operator->() const;

    iterator& operator++();

    iterator const operator++(int);

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

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

    Tree<T>* cur;

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

 public:
  explicit Tree(T const& val, Tree<T>* parent = nullptr);

  Tree<T>* GetParent() const;

  std::vector<Tree<T>*> const GetChildren() const;

  iterator begin();

  iterator end();

  bool operator==(Tree<T> const& root) const;

  bool operator!=(Tree<T> const& root) const;

  T val;

 private:
  Tree<T>* parent_ = nullptr;

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

If you have little time, you can skip the review on the implementation, but I will attach it here as well.

Also tree.h, under the snippet above.

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

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

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 == nullptr) {
    throw std::out_of_range("No more nodes for traversal");
  }

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

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

  return *this;
}

template <typename T>
typename Tree<T>::iterator const Tree<T>::iterator::operator++(int) {
  Tree<T>::iterator tmp(*this);
  ++*this;

  return tmp;
}

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

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>
Tree<T>* Tree<T>::GetParent() const {
  return parent_;
}

template <typename T>
std::vector<Tree<T>*> const Tree<T>::GetChildren() const {
  return children_;
}

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();
}

template <typename T>
bool Tree<T>::operator==(Tree<T> const& other) const {
  return val == other.val && 
         parent_ == other.parent_ &&
         children_ == other.children_;
}

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

This is compiled using

g++ main.cc -o tree -std=c++17 -Wall -static -O3 -m64 -lm

Finally, even if you don't have the answer to the design, I still hope you can throw me some questions such that I can ponder them.

Answer 1

My problem with this iterator is that it is very expensive to copy; as you have to copy a stack when you copy the iterator.

The main point of iterator is that it should be "cheap" to make copies. All algorithms that use iterators pass them by value (and all the advice you see on these pages that we give is to pass iterators by value) as a result iterators are copied a lot and as a result need to be "cheap" to copy.

The reason you need the stack is that your tree has no internal structure (yes it's a tree, but there is no relationship between parents parent and child), because there is no internal structure you need to maintain extra state to keep your position.

If we look at trees that exist in the standard library (std::set). This is an ordered binary tree (probably (the standard does not exactly specify but let's assume it is for the sake of argument. It is also probably balanced but let's not over complicate things for this analysis)).

Lets: Look at a set with the values: 12, 25, 37, 50, 75, 62, 85

Sorry for the bad drawing of a tree. Hope it is understandable:

                          50
                         /  \
                        /    \
                       /      \
                     25        75
                    /  \      /  \
                  12    37  62    85

Each Node needs three pointers. Left/Right/Parent (the parent is only required to help iterators). The rules for creating an iterator are then trivial.

 1. begin()    => Always return the left most node.   Iterator(12)
 2. ++
        1. If you have right pointer go down right then find the left most child.
        2. If you have no children. Go Up.
             a: If you just came from the left child stop.
             b: otherwise recursively up until you were a left child.
             c: When you are null you are out.

The rules are simple enough that you don't need to keep extra state in the iterator.

So from Iterator(12) no children so go up and get Iterator(25) next it has a right child Iterator(37) next it has no children go up (but I was the child so go up again now we are Iterator(50) etc.

Answer 2

Martin York already has a very good point about the iterator, so I'll not comment on that.

Avoid writing types twice

In main.cpp you are writing statements like:

Tree<std::string> tA = Tree<std::string>("A");

You are needlessly repeating the type. Also, it might cause errors if you wanted the same type on both sides, but made a mistake, and if one type is implicitly convertible to the other. Write one of the following lines instead:

Tree<std::string> tA("A"); // or:
auto tA = Tree<std::string>("A");

Trees are made of nodes, and a node is not a tree

A tree structure is a collection of nodes with certain relationships between the nodes. However, in your code a Tree<> is just one node. This is very confusing. It would be much nicer to have two types to distinguish between those concepts. For example:

class Tree {
    public:
    class Node {
        ...
    };

    class Iterator {
        ...
    };

    Iterator begin();
    Iterator end();
    ...

    private:
    Node *root;
};

Once you have that in place, you can starting thinking about having the Tree manage the lifetime of the nodes.

No need to repeat <T> inside the template

Inside a class template you don't have to repeat the <T> for every time you reference the class itself. So for example:

template <typename T>
class Tree {
    ...
    std::vector<Tree *> children;
    ...
};

Lifetime of tree nodes

Your node class references other nodes via raw pointers. That is very fragile. Take for example this bit of code:

Tree<int> tA(1);

if (some_condition) {
  // add a second item
  Tree<int> tB(1, &tA);
}

traverse(tA);

At this point, tA has a reference to tB, but the latter has gone out of scope, so the reference is no longer valid, leading to a crash at best.

Instead of storing references to child nodes in the children_ member variable, you could perhaps make that variable hold actual nodes, like so:

template <typename T>
class TreeNode {
    public:
    void addChild(T t) {
        children.push_back(t);
    }

    T val;

    private:
    std::vector<TreeNode> children_;
}

And use it like so:

TreeNode<int> tA(1);
tA.addChild(2);

Of course, the above is simplified, and you'd want to avoid making copies by using move semantics. But explicit ownership is the safest thing to implement.

Another option would be to use shared_ptr<> to manage the lifetime of nodes.