CODEWITHSUNDEEP
c++templatestreecircular-dependency
Freddie Witherden
Freddie Witherden

Reputation: 2426

C++ Avoiding Circular Dependencies with a Tree

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 {
public:
    virtual ~node() {}
    // [...] visitor stuff
};

template<class L, class B> class branch : public node<L,B> {
public:
    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]; }

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

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

private:
    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?

Upvotes: 0

Views: 737

Answers (2)

David Rodr&#237;guez - dribeas
David Rodr&#237;guez - dribeas

Reputation: 208456

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)

Upvotes: 0

Stack Overflow is garbage
Stack Overflow is garbage

Reputation: 248269

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>

Upvotes: 1

Related Questions