Summary: A scheme for streamlining virtual inheritence is proposed which
eliminates extranious pointers, and allows casting from base to derived.

Keywords: Virtual inheritance, template


INTRODUCTION

The purpose of this note is to point out what appears to be a deficiency
in the current C++ specification, and to suggest a solution.  The
problem is to define elaborate data structures, without including "extra
baggage".  The following discussion assumes the memory layout described
in Ellis & Stroustrup [1], section 10, commentary.

STATEMENT OF PROBLEM

There are two ways for extra memory allocation to get attached to each
instance of a class:

1.  Virtual functions.  When a class contains (or inherits) a virtual
function, each instance of the class contains a pointer to the virtual
function table (vtable) of that class.

2.  Virtual inheritance.  When a class is virtually derived, each
instance of the class contains a pointer to its location in the memory
layout.

Sometimes, when defining a class, it is important not to augment the
size of each instance beyond that needed to contain the explicitly
defined data members.  For example, nodes of a linked list or a binary
tree are replicated many times, and so would be each instance's extra
memory allocation.

It is reasonable to eliminate virtual functions from a class hierarchy
-- in fact, this is the only way, and appropriately so, to eliminate the
vtable pointers.

It is not reasonable to eliminate virtual inheritance, as the natural
class hierarchy should be a fact of life, and not a design choice.  A
related problem described in [1], is that if class B is virtually
derived from class A, then it is not permitted to cast from A* to B*.

In the next section, a solution is proposed which eliminates the extra
pointers of derived inheritance, and allows casting from a base class to
a virtually derived subclass, when the classes involved are
appropriately restricted.  This generality is sufficient for
constructing the "lean and mean" data structures which are mentioned
earlier, and do generalize the compact C struct.

PROPOSED SOLUTION

For convenience, make two definitions:

1. A class is 'restricted' if all its constructors are private, and its
only friends are the constructors of its immediately derived classes.

A restricted class may only ever be constructed when some non-restricted
descendent is constructed.

2. A class is 'simple' if all its ancestors are restricted.

We will consider a class hierarchy consisting only of restricted and
simple classes.  Although this situation is overly restrictive, it is
the simplest to consider, and does illustrate the relevant ideas.  It is
similar to a hierarchy where only the leaves are not abstract.

When instantiating a simple class, we will see that it is possible to
both eliminate the extra pointers of virtual inheritance, and to cast
from a base class to a virtually derived subclass.

For concreteness, consider the class hierarchy in the the following
diagram.  Classes B and C are virtually derived from A.   The three

   A
        v/ \v
                      /   \
       B     C
                    / \   /
                   /   \ /
                  D     E

classes A, B and C are restricted, so that classes D and E are simple.
There are only two possible instantiation subgraphs (one for D and one
for E):

         A     and             A
               /                    v/ \v
              /                     /   \
             B                     B     C
            /                       \   /
           /                         \ /
          D             E

The derivation of A to B in the D instantiation is no longer denoted as
virtual, as that is meaningless in this case.  As long as a compiler is
able to differentiate between the instances of B in the 2 situations,
there is no need to have each instance of B carry around a pointer to
where it is located in the memory layout.

View D and E in a way similar to template parameters.  For example,

 class B : virtual A
 {
  void f(A *ap){ cout << (B*) ap; }
 };

The code for B::f might well be different in the D instantiation than in
the E instantiation.  However, the cast form A* to B* is now legal.  A
possible syntax is that B<<D>>* denote a pointer to B in the D
instantiation.

CONCLUSIONS

It is not intended that the solution offered here replace the method
described in [1].  In fact, the method in [1] is preferred when the
classes involved are inherently heavy, especially when there is a lot of
code associated to the methods.  However, in order that C++ be
acceptable as a low level language, comparable to C, without sacrificing
the advantages of the C++ expressiveness, some solution is needed to
relieve virtual inheritance of the extra pointers.

[1] "The annotated C++ reference manual".  Margaret A. Ellis and Bjarne
Stroustrup.  Addison-Wesley 1990.

NAME  Norman Goldstein
EMAIL norman@mda.ca
SNAIL 13800 Commerce Parkway, Richmond BC, Canada V6V 2J3
PHONE (604) 278-3411 ext 2779 (Voice); (604) 278-2936 (FAX)
--
NAME  Norman Goldstein
EMAIL norman@mda.ca
SNAIL 13800 Commerce Parkway, Richmond BC, Canada V6V 2J3
PHONE (604) 278-3411 ext 2779 (Voice); (604) 278-2936 (FAX)