I have a tree-like data structure that I've set up like this:

class Root; // forward declaration

class Tree {
public:
    void addChildren(Root &r, ...) { childA = r.nodeSpace.allocate(); ... }
    // tons of useful recursive functions here
private:
    Tree *childA, *childB, *childC;
    Tree *parent;
    int usefulInt;
};

class Root : public Tree {
    friend class Tree; // so it can access our storage
public:

private:
    MemoryPool<Tree> nodeSpace;
};

I really like this structure, because

  1. I can call all the recursive functions defined on Tree on Root as well, without having to copy-paste them over.
  2. Root owns the storage, so whenever it passes out of scope, that's how I define the tree as no longer being valid.

But then I realized a problem. Someone might inadvertently call

Tree *root = new Root();

delete root; // memory leak! Tree has no virtual destructor...

This is not an intended usage (any ordinary usage should have Root on the stack). But I am open to alternatives. Right now, to solve this, I have three proposals:

  • Add virtual destructor to Tree. I would prefer not doing this because of the overhead as the tree can have many, many nodes.
  • Do not let Root inherit from Tree but instead have it define its own Tree member. Creates a little indirection, not too terrible, can still call the tons of useful recursive functions in Tree by doing root.tree().recursive().
  • Forbid assignments like Tree *root = new Root();. I have no idea if this is even possible or discouraged or encouraged. Are there compiler constructs?
  • Something else?

Which one of these should I prefer? Thank you very much!

1 Answers

0
Potatoswatter On

The root node class (or any other node class) should not be an interface class. Keep it private and then inheritance without dynamic polymorphism (virtual) is not dangerous because the user will never see it.

Forbid assignments like Tree *root = new Root();. I have no idea if this is even possible or discouraged or encouraged. Are there compiler constructs?

This would be done by having Root inherit from Tree as a private base class.