How is C++'s multiple inheritance implemented?

Question

Single inheritance is easy to implement. For example, in C, the inheritance can be simulated as:

struct Base { int a; }
struct Descendant { Base parent; int b; }

But with multiple inheritance, the compiler has to arrange multiple parents inside newly constructed class. How is it done?

The problem I see arising is: should the parents be arranged in AB or BA, or maybe even other way? And then, if I do a cast:

SecondBase * base = (SecondBase *) &object_with_base1_and_base2_parents;

The compiler must consider whether to alter or not the original pointer. Similar tricky things are required with virtuals.

Shaquitashara

en.wikipedia.org/wiki/Diamond_problem – Ronrona

You C simulation forgets the VTable (implementation detail) pointer. – Anemic

@Dario: This article deals with the overload problems in multiple inheritance but doesn't contain anything about the object layout and casting of objects in C++. – Presley

@Martin York: If there are no virtual methods in the classes, there is no v-table pointer. – Presley

Answer 1

The following paper from the creator of C++ describes a possible implementation of multiple inheritance:

Multiple Inheritance for C++ - Bjarne Stroustrup

Doormat

Alternate link: citeseerx.ist.psu.edu/viewdoc/… – Chary

After reading both, depending on what you're after. This (Stroustrup's one) is quite detailed and covers the theory. The one proposed by Nemanja below (MSDN's one) is simpler and covers a real implementation. – Inellineloquent

Both links are dead now, but usenix.org/publications/compsystems/1989/fall_stroustrup.pdf works for me. – Marcoux

Answer 2

There was this pretty old MSDN article on how it was implemented in VC++.

Banter

Answer 3

And then, if I do a cast:

SecondBase base = (SecondBase *) object_with_base1_and_base2_parents;

The compiler must consider whether to alter or not the original pointer. Similar tricky things with virtuals.

With non-virutal inheritance this is less tricky than you might think - at the point where the cast is compiled, the compiler knows the exact layout of the derived class (after all, the compiler did the layout). Usually all that happens is a fixed offset (which may be zero for one of the base classes) is added/subtracted from the derived class pointer.

With virutal inheritance it is maybe a bit more complex - it may involve grabbing an offset from a vtbl (or similar).

Stan Lippman's book, "Inside the C++ Object Model" has very good descriptions of how this stuff might (and often actually does) work.

Marlow

Answer 4

Parents are arranged in the order that they're specified:

class Derived : A, B {} // A comes first, then B

class Derived : B, A {} // B comes first, then A

Your second case is handled in a compiler-specific manner. One common method is using pointers that are larger than the platform's pointer size, to store extra data.

Anticipation

This is probably common, but I don't think it's required. – Marlow

I have seen it the other way. It all depends on the implementation. – Anemic

The order only has an effect on the order of constructor invocations. But the layout is unspecified. I did tests a while ago, and GCC puts empty bases first in memory, to make use of the empty base class optimization. – Camisole

Answer 5

This is an interesting issue that really isn't C++ specific. Things get more complex also when you have a language with multiple dispatch as well as multiple inheritance (e.g. CLOS).

People have already noted that there are different ways to approach the problem. You might find reading a bit about Meta-Object Protocols (MOPs) interesting in this context...

Equities

I think it is much easier to implement if the language does not support "raw" pointers to refernce objects and no POD backwards compatibility. Because if they do the casting of pointers to objects is very tricky. A language could add as much meta information into the reference class and the class instance as it want. In C++ this could not be done very easily. – Presley

Answer 6

Its entirely down to the compiler how it is done, but I beleive its generally done througha heirarchical structure of vtables.

Still

Answer 7

I have performed simple experiment:

class BaseA { int a; };
class BaseB { int b; };
class Descendant : public BaseA, BaseB {};
int main() {
        Descendant d;
        BaseB * b = (BaseB*) &d;
        Descendant *d2 = (Descendant *) b;
        printf("Descendant: %p, casted BaseB: %p, casted back Descendant: %p\n", &d, b, d2);
}

Output is:

Descendant: 0xbfc0e3e0, casted BaseB: 0xbfc0e3e4, casted back Descendant: 0xbfc0e3e0

It's good to realise that static casting does not always mean "change the type without touching the content". (Well, when data types do not fit each other, then there will be also an interference into content, but it's different situation IMO).

Shaquitashara