Is multiple inheritance acceptable for nodes in a tree?

Question

I was wondering:

With a tree, the root can have multiple children and no id. All nodes (except the root) have an id and the leaf nodes can not have children. It is fixed what type must be used for each depth. So the leaves are always of the same type and so are the parents of the leaves.

Since the root and the nodes can have children and only the nodes have an id I was wondering if the following use of multiple inheritance is acceptable:

class NodeWithId
{
    private:
        std::string m_id;
};

template<typename T>
class NodeWithChildren
{
    private:
        std::vector<T> m_nodes;
};

class Network: public NodeWithChildren<Subnet>
{
};

class Subnet: public NodeWithChildren<Machine>, 
                     public NodeWithId
{
};

class Machine: public NodeWithChildren<Application>, 
               public NodeWithId
{
};

class Application: public NodeWithId
{
};

Or is there a better way to implement this?

edit:

• removed virtual
• changed classnames

Answer 1

First of all, there is no need for virtual inheritance, based on the sample code you posted, there is no 'dreaded diamond'

But I don't really get your design at all, there's no common base class for anything representing your tree, why are you using inheritance at all? It looks like everything could be achieved using composition.

Is this simply a slimmed down version of your hierarchy made for this question?

Answer 2

You could do it with single inheritance:

class NodeWithId
{
    private:
        std::string m_id;
};

template<typename T>
class NodeWithChildren : public NodeWithId
{
    private:
        std::vector<T> m_nodes;
};

class Root: public NodeWithChildren<Level1Node>
{
};

class Level1Node: public NodeWithChildren<Level2Node>
{
};

class Level2Node: public NodeWithChildren<LeafNode>
{
};

class LeafNode: public NodeWithId
{
};

You would only need multiple inheritance in the case that you can have a NodeWithChildren that DOESN'T have an ID. In your design above every NodeWithChildren also has a NodeWithId so you may as well derive NodeWithChildren from NodeWithId and totally bypass any potential multiple inheritance problems.

Seems like a "better" design to me ...

Answer 3

Or is there a better way to implement this?

IMHO, your design creates classes for stuff that are best treated as object instances. At a class level I do not see the need to differentiate between Level1 nodes and Level2 nodes.

Use a design that is simple. Ask yourself, if this design has any potential benefits or not than the naive approach of having a single Node class and creating a tree structure out of Node instances (which you create at runtime).

Answer 4

Your performance will be unbearable, and your code unbelievably convoluted.

First you use a template, which has a vector in it, for each node.

The vector alone will dramatically slow things. Having to cast things would make your traversal code very very slow, and the code itself would be hard to comprehend for anyone else.

Also, since you have different classes, how is the vector able to deal with that? Answer, it can't. That means it has to be a vector of pointers to a base class. Then you have to figure out what the proper type is at runtime to get any use out of them.

If this added some sort of benefit then it might be worth it for some uses, but it's really the opposite of what you want from a structure like a tree, which should be as simple as possible to use and comprehend and have as few memory allocations as possible and ideally good performance.