diamond inheritance - Passing leaf class object as parameter in place of root class

Question

i have a program with the following inheritance structure

                       List
                   /         \
          DoublyLinkedList   CircularlyLinkedList
                   \          /
                CircularlyDoublyLinkedList

In the List class (which is fully abstract) I have a pure virtual function

     int virtual insert(List **head, int position) = 0;

which I have overridden in the DoublyLinkedList and CircularlyLinkedList classes.
In order to resolve ambiguity in the CircularlyDoublyLinkedList class, I explicitly specify which version of the insert() function to inherit using the scope resolution operator ::, for example: DoublyLinkedList::insert(..)

My problem is that this statement

    List *cdll_head = new CircularlyDoublyLinkedList();

throws an error

    "cannot convert CircularlyDoublyLinkedList* to  List*"

when I change the statement as

    CircularlyDoublyLinkedList *cdll_head = new CircularlyDoublyLinkedList();

I get another error as insert(...) accepts a parameter of type List**

How do I resolve this problem without a cast?

Answer 1

When using multiple inheritance with diamond-shaped structures, you should use virtual inheritance.

I assume your code looks a bit like this:

class List {
...
};

class DoublyLinkedList: public List {
...
};

class CircularlyLinkedList: public List {
...
};

class CircularlyDoublyLinkedList: public DoublyLinkedList, public CircularlyLinkedList {
...
};

void doStuff() {
    List* aList = new CircularlyDoublyLinkedList();
    ...
}

which produces the following error:

ambiguous conversion from derived class 'CircularlyDoublyLinkedList' to base class 'List':
    class CircularlyDoublyLinkedList -> class DoublyLinkedList -> class List
    class CircularlyDoublyLinkedList -> class CircularlyLinkedList -> class List

If you change the inheritance of DoublyLinkedList and CircularlyLinkedList to virtual public like follows:

class DoublyLinkedList: virtual public List {
...
};

class CircularlyLinkedList: virtual public List {
...
};

class CircularlyDoublyLinkedList: public DoublyLinkedList, public CircularlyLinkedList {
...
};

everything should compile properly. However, there is an additional performance cost. I would suggest using a fully abstract list interface that would be inherited by all your list classes, and composition to allow implementation reuse.