carroll@cbnewsm.att.com (martin.d.carroll) (01/01/91)
Dear net people,
A little while back, Bjarne posted a request for people to submit
real examples of multiple inheritance (MI) in C++. Tom Cargill
has been making the same request for a while. Here is my contribution.
The following code implements an abstract Map interface via an underlying
Skiplist data structure. The use of MI appears in the following:
template <class T, class U>
class Map_via_skiplist : private Skiplist<T>, public Map<T,U> { /* ... */ };
Now, before you scream, "But one of those inheritances is private, and
so could just as well have been implemented using composition!" let me
explain. There are two reasons why I use private inheritance instead
of composition:
1. The Map-via-Skiplist class has to have access to more than
the public interface of the Skiplist class. (That is, it has
to have access to more than what I wish to provide "direct"
public clients of Skiplist.)
Typically, when a data structure is intended to be used as the
underlying data structure for other types, it is convenient/natural
to make the protected interface of that data structure available
for private inheritance.
2. The Skiplist class defines a "virtual constructor" which the
Map_via_skiplist class must override. Thus, this example satisfies
Bjarne's and Tom's criterion that each of the inheritances must
override a virtual function.
Notice, incidentally, that the private inheritance method is no less
inefficient than the composition method: only a single extra virtual
function call per insert operation, which is more than overshadowed
by the cost of actually doing the insertion.
Here is the code. I've included the definitions of only those functions
which are of interest for the example. The following actually compiles
under 3.0 cfront! Enjoy, and have a happy new year,
martin carroll
carroll@mozart.att.com
////////////////////////////////////////////////////////////////////
// Real example of multiple inheritance in C++.
// Here is the overall class hierarchy:
//
//template <class T>
//class Skiplist_node { /* ... */ };
//
//template <class T>
//class Skiplist { /* ... */ };
//
//template <class T, class U>
//class Map { /* ... */ };
//
//template <class T, class U>
//class Map_via_skiplist_node : public Skiplist_node<T> { /* ... */ };
//
//template <class T, class U>
//class Map_via_skiplist : private Skiplist<T>, public Map<T,U> { /* ... */ };
//
////////////////////////////////////////////////////////////////////
// Defined below.
template <class T>
class Skiplist;
// The type of node in a Skiplist.
template <class T>
class Skiplist_node {
friend Skiplist<T>;
protected:
// This node's key.
T key;
// Construct a Skiplist node with the given number of levels and key.
Skiplist_node(int nlevels, const T& key);
// Destructor must be virtual, since constructor below is virtual.
virtual ~Skiplist_node();
// ... more stuff
};
template <class T>
class Skiplist {
public:
// Insert a key into the Skiplist. Return true if the key was present.
// Side-effect: sets the_node to the inserted or present node.
int insert(const T& key);
// Return true if the key is present.
// Side-effect: sets the_node to the node containing the key, or 0 if
// the key not is present.
int contains(const T& key) const;
// Construct a Skiplist that can hold at most maxsize keys.
Skiplist(int maxsize);
// Destructor.
~Skiplist();
protected:
// Virtual constructor. Should return a new instance of the
// type of node for this Skiplist.
virtual Skiplist_node<T>* newnode(int nlevels, const T& key) const;
// Used by derived class. Holds pointer to node inserted or located
// by most recent insert or contains operation.
Skiplist_node<T> *the_node;
// ... more stuff
};
template <class T>
Skiplist_node<T>*
Skiplist<T>::newnode(int nlevels, const T& key) const {
// The type of node for Skiplist is Skiplist_node.
return new Skiplist_node<T>(nlevels, key);
}
template <class T, class U>
class Map {
public:
// Insert the given <key,value> pair into the Map.
// Return true if the key was present (in which case
// its value is updated).
virtual int insert(const T& key, const U& value) = 0;
// Return true if there is a <key,value> pair with
// the given key.
virtual int contains(const T& key) const = 0;
// If the given key is present, return true and set
// value to the associated value, otherwise return
// false without changing value.
virtual int valueof(const T& key, U& value) const = 0;
};
// Defined below.
template <class T, class U>
class Map_via_skiplist;
// The type of node in a Map implemented via a Skiplist.
template <class T, class U>
class Map_via_skiplist_node :
public Skiplist_node<T> {
friend Map_via_skiplist<T,U>;
protected:
// The value associated with this node's key.
U value;
// Construct a Skiplist node with nlevels and the given <key,value>
// pair.
Map_via_skiplist_node(int nlevels, const T& key, const U& value_);
// Override the virtual destructor.
~Map_via_skiplist_node();
// ... more stuff
};
template <class T, class U>
Map_via_skiplist_node<T,U>::Map_via_skiplist_node(int nlevels, const T& key, const U& value_) :
// Construct the Skiplist_node, then initialize the value.
Skiplist_node<T>(nlevels, key), value(value_) {
}
template <class T, class U>
Map_via_skiplist_node<T,U>::~Map_via_skiplist_node() {
// ... anything necessary to destroy a Map_via_skiplist_node.
}
// An implementation of the Map protocol using Skiplists.
template <class T, class U>
class Map_via_skiplist :
private Skiplist<T>,
public Map<T,U> {
public:
// Construct a Map that can hold at most maxsize <key,value> pairs.
Map_via_skiplist(int maxsize);
// Implement the Map protocol.
int insert(const T& key, const U& value);
int contains(const T& key) const;
int valueof(const T& key, U& value) const;
private:
// Cast Skiplist::the_node to the appropriate type for derived class.
Map_via_skiplist_node<T,U> *The_node() const {
return (Map_via_skiplist_node<T,U>*)the_node;
}
// Override the virtual constructor.
Skiplist_node<T>* newnode(int nlevels, const T& key) const;
// See the implementation of insert below.
const U* pvalue;
// ... more stuff
};
template <class T, class U>
int
Map_via_skiplist<T,U>::contains(const T& key) const {
// To see if a key is in the Map, simply look in the Skiplist.
return Skiplist<T>::contains(key);
}
template <class T, class U>
int
Map_via_skiplist<T,U>::insert(const T& key, const U& value) {
// To insert a <key,value> pair into the Map,
// do the following:
// 1. Squirrel away the given value for the virtual constructor.
// 2. Insert the key into the Skiplist.
// 3. If the key was present, update its value.
pvalue = &value; // squirrel away value
if (Skiplist<T>::insert(key)) { // if key was already there
The_node()->value = value; // update its value
return 1;
}
return 0;
}
template <class T, class U>
Skiplist_node<T>*
Map_via_skiplist<T,U>::newnode(int nlevels, const T& key) const {
// Construct a Map_via_skiplist_node with the given key,
// and the value just squirreled away by insert.
return new Map_via_skiplist_node<T,U>(nlevels, key, *pvalue);
}
template <class T, class U>
int
Map_via_skiplist<T,U>::valueof(const T& key, U& value) {
// To find the value associated with a given key, do the following:
// 1. Look in the Skiplist for the key.
// 2. If the key was present, look in the node for the value.
if (Skiplist<T>::contains(key)) {
value = The_node()->value;
return 1;
}
return 0;
}mat@mole-end.UUCP (Mark A Terribile) (01/02/91)
In article <1990Dec31.182239.23486@cbnewsm.att.com>, carroll@cbnewsm.att.com (martin.d.carroll) writes: > A little while back, Bjarne posted a request for people to submit > real examples of multiple inheritance (MI) in C++. Tom Cargill > has been making the same request for a while. Here is my contribution. > > The following code implements an abstract Map interface via an underlying > Skiplist data structure. The use of MI appears in the following: > > template <class T, class U> > class Map_via_skiplist : private Skiplist<T>, public Map<T,U> { /* ... */ }; I encourage EVERYONE to look this over very, very carefully. Templates and MI work together here in a particularly potent way. If the algorithms for the Skiplist are particularly interesting and involve data structures of their own, it might even make sense to derive Skiplist<T> from a Skiplist_manager whose algorithms can be shared instead of being recompiled for every template-type expansion. (A sufficiently smart compiler might be able to determine what member functions can be common to all Skiplist<T> , but it would have to be a VERY smart compiler). There is something of a problem here: > template <class T, class U> > class Map_via_skiplist_node : > public Skiplist_node<T> { > friend Map_via_skiplist<T,U>; > protected: > // The value associated with this node's key. > U value; > > // Construct a Skiplist node with nlevels and the given <key,value> > // pair. > Map_via_skiplist_node(int nlevels, const T& key, const U& value); The problem is that we have to provide an already-constructed U to the constructor, and we have to have a default constructor for the U that is a member, or this code will not work. There's no way to say `substitute here the parameters to the constructors for U .' I suspect that doing this using C++'s present constructor syntax would be a horrific problem, especially as regards ambiguities. All is not lost; we can write typedef Map_via_skiplist_node< Name, Widget > mvns_Widget; new mvns_Widget( levs, Name( name_arg_1, name_arg_2 ), Widget( Widget_arg_1, Widget_arg_2 ) ); but that seems a bit clumsy, as if we can do better. Finally, if this is compiled using 3.0, wouldn't it be possible to make some (or all but one) of these templates for classes internal to just one of them, so that the program namespace is kept a bit cleaner? If I wore a hat I would take it off to anyone who can debug a compiler with all these different levels of names expanding to names with various, sundry, and generally sundered meanings! In the feral and furry world of templates, we are asking an awful lot of the compiler. -- (This man's opinions are his own.) From mole-end Mark Terribile