Take the 2-minute tour ×

I am writing a tree structure where I want to store different data in leaf nodes to branch nodes. The idea is very similar to a dynamic programming method -- with aggregate data being stored in the branches. Hence I have come up with (cut down for simplicity)

template<class L, class B> class node {
    virtual ~node() {}
    // [...] visitor stuff

template<class L, class B> class branch : public node<L,B> {
    template<class It>
    branch(It b, It e) {
        // Do something with the iterators;
        // decide if to create branches or leaves

        // Create the branch data
        b_ = new B(/* Unknown */);
    ~branch() { delete b_; delete child_[0]; delete child_[1]; }

    B* b_;  node<L,B>* child_[2];

template<class L, class B> class leaf : public node<L,B> {
    leaf(L* l) : l_(l) {}
    ~leaf() {}

    L* l_;

With example L and B structures being

struct myleaf   { int x; };
struct mybranch {
    mybranch(/* Unknown */) {
    // Apply a visitor to the child nodes to get sumx
    int sumx;
    // Some other properties

My problem is how I can do this without encountering circular dependencies with B depending on node<L,B>. Alternatively, can I easily re architecture the code to avoid this issue entirely?

share|improve this question
public inheritence models "is-a". Thus you say a branch is a node. I think this is very basic problem in your design that makes it complicated. –  b.buchhold Oct 29 '11 at 12:34

2 Answers 2

up vote 1 down vote accepted

as far as I can see, there is no problem.

It's basically an example of CRTP, a fairly common pattern for template code in C++.

Of course you can trip the compiler up so this won't work, but at the basic level, there is nothing wrong with dependencies of the form class Derived : Base<Derived>

share|improve this answer

I think that you are trying to make the branch deal with walking the tree and obtaining the value. The responsibility of walking the visitor around the tree should be in the tree structure, breaking the dependency with the structure. When the visitor is applied to the leaf nodes it will apply whatever the operation it is designed to do, when applied to the branches, it can both update the value and perform the operation.

To be able to implement this efficiently, you might need to add an interface to the branch/node internal types to provide the information of whether the value is already precached (i.e. no need to walk down the tree)

share|improve this answer

Your Answer


