David, who is chief technologist at Terasoft Technology (Milford, MA), is the author of Inside the Object Model: The Sensible Use of C++ (SIGS Books, 1995). David can be contacted on CompuServe at 75310,1621.
Most elements of the object model have parallel C++ language counterparts: The class mechanism maps to abstract data type, const and reference types enforce immutability, inheritance implements generalization, virtual functions correspond to polymorphism, and templates realize metatype. But association, a fundamental component of the object model, has no direct C++ language counterpart. Consequently, you have to implement this capability yourself.
In this article, I'll describe and compare several unidirectional and bidirectional pointer-based alternatives for implementing one-to-one associations: a direct, handwritten implementation; a modular approach that exploits inheritance; and a template-based implementation that eliminates replication of programming steps and corresponds to association implementation by declaration.
My examples implement an analysis model of a one-to-one association between type Inventor (playing the role of creator) and type Contraption (playing the role of invention); see Figure 1. (All figures in this article follow the Object Modeling Technique, or OMT, notation described by Rumbaugh et al. in Object-Oriented Modeling and Design, Prentice-Hall, 1991.) Figure 1 indicates that exactly one Contraption object participates (or links) with every Inventor object, and vice versa.
The first implementation of the Inventor/Contraption one-to-one association is unidirectional. Only one class (Inventor) contains a pointer to the other (Contraption); no reverse pointer is present. Figure 2 shows the design model for the uni-directional implementation using pointer-design notation. Class definitions and implementations appear in Listing One.
In the unidirectional implementation, association traversal is convenient in the forward direction only, from Inventor to Contraption. The benefits of this implementation include simplicity, minimal storage, and minimal link-update cost (link creation and termination overhead). The class without a pointer is decoupled from the class with a pointer, and maintenance of the reverse pointer is unnecessary.
Backward traversal is complex and inefficient: It requires maintaining and searching a list all Inventor objects. If backward traversal never occurs, of course, the Inventor list is unnecessary.
In the bidirectional implementation of the Inventor/Contraption one-to-one association, each class contains a pointer to the other participant, making traversal convenient and efficient in either direction; see Figure 3. No artifactual object list must be maintained or searched. Class definitions and implementations appear in Listing Two.
Despite the necessary data members, the association's functional interface is poorly designed; simply shielding association-implementation member pointers will not preserve referential integrity: When an Inventor's pointer addresses a Contraption, there's no mechanism to ensure the Contraption's pointer addresses that Inventor and no other. Any benefits of bidirectional implementation pale compared with the complexity of link management and the near certainty of incorrect link termination, dangling pointers, and corrupt programs.
These problems can, however, be minimized by adhering to the following criteria:
The third implementation of the Inventor/Contraption one-to-one association is bidirectional with link-management functions. Each class contains a pointer to the other, but functions guaranteed to maintain referential integrity manipulate the pointers.
The design model of this managed implementation is identical to that of the unmanaged implementation in Figure 3; language features not easily expressed by the graphical notation realize the aforementioned design criteria. Class definitions and member-function implementations appear in Listing Three with link-management interface-function prototypes. Pointer set() functions are private, so they are inaccessible to users, but the friend link-management functions link() and unlink() manage the pointers and create and terminate links. Pointer get() functions are public, enabling tests for link existence and traversal. Constructors initialize objects as unlinked, and destructors call unlink(), so preserve referential integrity upon object termination. Example 1 illustrates creating, traversing, and terminating a link.
Link-management function implementation. If, at entry, both argument objects are unlinked, link() sets pointers; if the argument is linked, the two unlink() functions reset pointers; see Listing Four. All three link-management functions are written in terms of Inventor and Contraption member functions and do not manipulate pointers directly. This convention enhances order and minimizes the costs of an implementation change.
Copy functions. Generated copy functions violate the inverse-mapping constraint. Copy functions can be overridden three different ways. The simplest is to make copy functions private and not write implementations; see Listing Five. If an object participates in associations, it may be appropriate to eliminate assignment, pass by value, and return by value.
Example 2 shows that a multiplicity of one prevents copy target and source from linking to the same object. Consequently, the second approach implements public copy functions that do not disturb links; see Listing Six. The functions copy other source-object information--besides the link--to the target.
In the third method, copy functions copy an entire constellation of linked objects; for example, copying an Inventor also copies its linked Contraption. (This strategy incorporates "deep copy," a topic beyond the scope of the present discussion. See Data Abstraction and Object-Oriented Programming in C++, by Gorlen, Orlow, and Plexico; John Wiley & Sons, 1990.)
These methods of overriding copy functions for one-to-one associations hold true for any multiplicity association: No matter what the association multiplicity, participating classes can prohibit object copy, implement copy so that links are undisturbed, or copy an entire constellation of linked objects.
Benefits and costs. A managed, bidirectional implementation maintains referential integrity by eliminating the possiblity of incorrect pointer manipulation. Traversal is efficient in both directions. Of course, bidirectional implementation has higher storage and link-update costs than unidirectional implementation, but it is more powerful.
In general, isolating functionally distinct parts of a program engenders a modular, well-organized program. In this case, it also prepares for type parameterization, a more powerful association-implementation technique described later.
Because an association is independent of the functionality in its associated classes, its implementation can usually be separate, as well. I do this via public inheritance. Normally, the separation is introduced during design: Derived classes and allied friends implement only the association, and base classes implement all other functionality.
In Figure 4, the attributes name and title demonstrate placement of non-association-related functionality in the analysis model. In Figure 5, the analysis-model characteristics are distributed over base and derived classes, and the association is implemented bidirectionally with link-management functions. All non-association-related characteristics (here, name and title) go in base classes. Pointers and association functionality are immediate members and friends of derived classes.
Base functionality. Base classes IOther and COther ("Inventor Other" and "Contraption Other"), which implement non-association-related functionality, appear in Listing Seven, along with a simple class String containing get() and set() access functions. These classes implement name() and title() attributes. Any functionality, including participation in other associations, is possible in classes IOther and COther.
The objective is to engage IOther and COther in an association without disturbing them, while preserving access to IOther and COther functionality.
Derived classes. The derived classes Inventor and Contraption appear in Listing Eight with link-management, interface-function prototypes. Pointer set() functions are private, so they are inaccessible to users. But friends link() and unlink() manage the pointers and create and terminate links. Pointer follow() functions are public, enabling tests for link existence and traversal. Constructors initialize objects as unlinked, and destructors unlink() objects at termination, before embedded-base-class-object deinitialization.
Derived classes store (and member functions set() and follow() take and return) derived-class pointers, not base-class pointers. Public inheritance enables the selection of base-class members through derived-class pointers, so base-class and derived-class functionality is accessible upon link traversal. For example, Inventor::follow() yields a Contraption *, through which both COther and Contraption member functions can be called.
Base-class constructor arguments propagate and become derived-class constructor arguments. Derived-class constructors simply pass the propagated arguments to base-class constructors in the initialization list.
Link-management-function implementation. Link-management-function implementations appear in Listing Nine. If, at entry, both argument objects are unlinked, link() sets pointers; if the argument is linked, the two unlink() functions reset pointers. All three link-management functions are written in terms of Inventor and Contraption member functions; they do not manipulate pointers directly.
Use. Example 3 demonstrates the Inventor/Contraption one-to-one association-independent implementation. Function print() in Example 3(a) calls base class IOther and derived class Inventor member functions on derived class Inventor reference argument I. I.name() executes IOther::name(). I.follow() executes Inventor::follow(), and yields a Contraption* derived-class pointer. Base class COther member function title() is called through this pointer. Function main() in Example 3(b) builds a constellation of objects and calls print(). The program generates the output in Example 3(c).
The scheme described here can append a one-to-one association onto any pair of classes, without disturbing existing classes, while maintaining access to existing functionality. Similar schemes can implement other multiplicity and typed associations.
An even more modular and reusable method of association implementation incorporates templates. As in the previous approach, association implementation is separated from other functionality during design. But, whereas previously, each association implementation was written by hand, here, association functionality is written once in cooperating templates and instantiated later.
This powerful method enables association implementation by declaration. Once preserved in modules of cooperating templates, an association can be implemented as simply as other object-model components that have direct language support, like generalization or polymorphism, for example.
Figure 6 shows analysis-model characteristics distributed over base and derived classes. All Inventor/Contraption characteristics except the association go in base classes. Pointers and association functionality are immediate members and friends of derived classes. Here, Inventor and Contraption are instances of the Left and Right association templates, as well as derived classes.
Base functionality. Revised base classes IOther and COther, which implement non-association-related functionality, appear in Listing Ten. Except for the required default constructors (discussed later), these classes are identical to Listing Seven. Again, any functionality is possible in classes IOther and COther.
The objective is to engage IOther and COther in an association by the two-line declaration in Example 4(a), without disturbing IOther and COther, while preserving access to IOther and COther functionality. In the code, Inventor and Contraption are typedefs of cooperating template instances.
Parameterized derived-class templates. Cooperating class templates L1to1 and R1to1 (short for left and right one-to-one) and link-management interface-function template prototypes appear in Listing Eleven. L1to1, R1to1, link(), and unlink() are parameterized versions of the nontemplates in Listing Eight. Besides parameterization, the templates work like the nontemplates.
Declarations that bind actual types to formal parameters LB and RB (short for left and right base class) instantiate the class templates. An actual class L1to1<LB,RB> inherits from the actual class bound to LB. Similarly, R1to1<LB,RB> inherits from RB. L1to1<LB,RB> contains a pointer member to R1to1<LB,RB>, and vice versa. Derived-class pointers enable access to derived- and base-class functionality.
The class templates constrain the actual types that can bind to formals LB and RB: LB and RB must be class types and have default constructors and destructors. Since the class templates are written separately from any base class eventually used for instantiation, base-class constructor arguments cannot be propagated into derived-class constructor signatures.
Parameterized link-management-function implementation. Implementations of link-management interface-function templates appear in Listing Twelve. If, at entry, both argument objects are unlinked, function template link() sets pointers; if the argument is linked, the two unlink() function templates reset pointers.
Use. Any pair of classes bound to formals LB and RB that have default constructors and destructors can instantiate L1to1 and R1to1. Thus, typedefs like those in Example 4(a) can create an association between an arbitrary pair of classes. Since Inventor is an alternate name for actual class L1to1<IOther,COther>, it inherits from IOther and implements one side of the Inventor/Contraption association. Similarly, Contraption inherits from COther, and implements the other side of the association.
The print() function in Example 4(b) executes base class IOther functionality on derived class Inventor reference argument I. The function tests I.follow() and traverses the link. The member function title() of the base class COther is called through the derived class Contraption * pointer returned from I.follow(). The main() function in Example 4(c) builds a constellation of objects and calls print(). The program generates the output in Example 4(d).
Template-based associations yield well-designed, declaration-generated bidirectional implementations. Once a template module is written, the templates can implement an arbitrary number of associations between arbitrary classes. The scheme can even append multiple associations onto a single class.
On the downside, the actual types that bind to template formal parameters are constrained: Any base class to which an association is appended must have a default constructor, and type-specific base-class constructor arguments cannot be propagated into derived-class constructor signatures. This, in turn, forces separate "initialization" after associated-object creation, reducing the utility of constructors and effectively returning the responsibility of object initialization to the programmer.
The scheme I've described here can append a one-to-one typed association onto arbitrary classes. Other multiplicity and style associations can be implemented similarly. The approach is useful for quickly solving many programming problems in a variety of contexts.
Figure 1: Analysis model of sample one-to-one association for demonstrating association implementation.
Figure 2: Design model of Inventor/Contraption one-to-one association unidirectional implementation.
Figure 3: Design model of Inventor/Contraption one-to-one association bidirectional implementation.
Figure 4: Analysis model of Inventor/Contraption one-to-one association for demonstrating independent association implementation.
Figure 5: Design model of Inventor/Contraption one-to-one association-independent implementation.
Figure 6: Design model of Inventor/Contraption one-to-one association implementation by declaration.
Example 1: Sample code demonstrating link creation, traversal, and termination. Invention: Protective Device Inventor: Aaron Invention: None!
Copyright © 1995, Dr. Dobb's Journal
int main()
{
Inventor edison; // unlinked
Contraption lightbulb; // unlinked
link( edison, lightbulb ); // create
Contraption * p = edison.invention();
// traverse
. . .
unlink( edison ); // terminate
return 0;
}
Example 2: Sample code illustrating that copy target and source cannot link to the same object.
Inventor edison;
Contraption lightbulb;
link( edison, lightbulb );
Inventor bell = edison;
// bell and edison cannot both link to
// lightbulb after copy construction
Inventor salk;
Contraption polioVaccine;
link( salk, polioVaccine );
salk = edison;
// salk and edison cannot both link to
// lightbulb after assignment
Example 3: Sample code demonstrating use of inheritance-based association.
(a)
void print( Inventor & I )
{
cout <<"Inventor: "
<< I.name() // Base class member
<< '\n'
<< "Invention: ";
if ( I.follow() )
{
cout << I.follow()->title();
// Base class member function
// title() called through pointer
}
else
{
cout <<"None!";
}
cout << "\n\n";
}
(b)
int main()
{
Inventor i( "Aaron" );
Inventor j( "Dave" );
Contraption c( "Measurement Device" );
link( i, c );
print( i );
print( j );
return 0;
}
(c)
Inventor: Aaron
Invention: Measurement Device
Inventor: Dave
Invention: None!
Example 4: Sample code demonstrating use of template-based association.
(a)
typedef L1to1<IOther,COther> Inventor;
typedef R1to1<IOther,COther> Contraption;
(b)
void print( Inventor & I )
{
cout <<"Inventor: "
<< I.name() // Base class member
<<'\n'
<<"Invention: ";
if ( I.follow() )
{
cout << I.follow()->title();
// Base class member function
// title() called through pointer
}
else
{
cout << "None!";
}
cout << "\n\n";
}
(c)
int main()
{
Inventor i, j;
i.name( "Dave" );
j.name( "Aaron" );
Contraption c;
c.title( "Protective Device" );
link( i, c );
print( i );
print( j );
return 0;
}
(d)
Inventor: DaveListing One
// *****************************************
// Unidirectional association implementation
// *****************************************
class Contraption;
class Inventor
{
Contraption * c;
public:
Inventor( Contraption * cr ) : c(cr) {}
// Forward traversal
Contraption * invention() { return c; }
void invention(Contraption * cr) { c=cr; }
};
class Contraption
{
. . .
public:
Contraption();
// Reverse traversal difficult
// Inventor * creator();
// void creator( Inventor * );
};
Listing Two
// ****************************************
// Bidirectional association implementation
// ****************************************
class Contraption;
class Inventor
{
Contraption * c;
public:
Inventor() : c(0) {}
// Forward traversal
Contraption * invention() { return c; }
void invention(Contraption * cr) { c=cr; }
};
class Contraption
{
Inventor * i;
public:
Contraption() : i(0) {}
// Reverse traversal
Inventor * creator() { return i; }
void creator( Inventor * ir ) { i = ir; }
};
Listing Three
// *************************************************************
// Bidirectional association implementation with link management
// *************************************************************
class Contraption;
class Inventor
{
Contraption * c;
void invention(Contraption * cr) { c=cr; }
public:
Inventor() : c(0) {}
~Inventor() { unlink(*this); }
Contraption * invention() { return c; }
// link management interface
friend void link( Inventor &, Contraption & );
friend void unlink( Inventor & );
friend void unlink( Contraption & );
};
class Contraption
{
Inventor * i;
void creator( Inventor * ir ) { i = ir; }
public:
Contraption() : i(0) {}
~Contraption() { unlink(*this); }
Inventor * creator() { return i; }
// link management interface
friend void link( Inventor &, Contraption & );
friend void unlink( Inventor & );
friend void unlink( Contraption & );
};
Listing Four
// ****************************************
// Link management function implementations
// ****************************************
void link( Inventor & I, Contraption & C )
{
if( !I.invention() && !C.creator() )
{
I.invention( &C );
C.creator( &I );
}
}
void unlink( Inventor & I )
{
if ( I.invention() )
{
I.invention()->creator(0);
I.invention(0);
}
}
void unlink( Contraption & C )
{
if ( C.creator() )
{
C.creator()->invention(0);
C.creator(0);
}
}
Listing Five
// *****************************
// Prohibition of copy functions
// *****************************
class Inventor
{
private:
Inventor( const Inventor & );
Inventor & operator=( const Inventor & );
// COPY FUNCTIONS NOT IMPLEMENTED!
. . .
};
Listing Six
// *******************************************
// Copy functions that leave links undisturbed
// *******************************************
Inventor::Inventor( const Inventor & r )
: c(0)
// Initialize other members
{}
Inventor & Inventor::operator=( const Inventor & r )
{
if ( this != &r )
{
// Do not call link(), or unlink(), or otherwise disturb c or r.c.
//
// Assign other members
}
return *this;
}
Listing Seven
// *******************************************************************
// Base functionality for inheritance based association implementation
// *******************************************************************
class String
{
. . .
public:
String( char * );
~String();
char * get();
void set( char * );
};
class IOther // Inventor Other functionality
{
String nm;
. . .
public:
IOther(char * p) : nm(p) {}
~IOther() {}
char * name() { return nm.get(); }
void name(char * p) { nm.set(p); }
. . .
};
class COther // Contraption Other functionality
{
String tl;
. . .
public:
COther(char * p) : tl(p) {}
~COther() {}
char * title() { return tl.get(); }
void title(char * p) { tl.set(p); }
. . .
};
Listing Eight
// ******************************************************
// Derived classes implementing association functionality
// ******************************************************
class Contraption;
class Inventor : public IOther
{
Contraption * c;
void set(Contraption * cr) { c = cr; }
public:
// Base class constructor arguments
// propagate to derived class constructor
Inventor(char * p)
: IOther(p),
c(0)
{}
~Inventor() { unlink(*this); }
Contraption * follow() { return c; }
// link management interface
friend void link( Inventor &, Contraption & );
friend void unlink( Inventor & );
friend void unlink( Contraption & );
};
class Contraption : public COther
{
Inventor * i;
void set( Inventor * ir ) { i = ir; }
public:
Contraption(char * p)
: COther(p),
i(0)
{}
~Contraption() { unlink(*this); }
Inventor * follow() { return i; }
// link management interface
friend void link( Inventor &, Contraption & );
friend void unlink( Inventor & );
friend void unlink( Contraption & );
};
Listing Nine
// ********************************************
// Link management function implementations for
// inheritance based association implementation
// ********************************************
void link( Inventor & I, Contraption & C )
{
// link only if both arguments are
// unlinked at entry
if( !I.follow() && !C.follow() )
{
I.set( &C );
C.set( &I );
}
}
void unlink( Inventor & I )
{
// unlink only if linked
if ( I.follow() )
{
I.follow()->set(0);
I.set(0);
}
}
void unlink( Contraption & C )
{
// unlink only if linked
if ( C.follow() )
{
C.follow()->set(0);
C.set(0);
}
}
Listing Ten
// ****************************************************************
// Base functionality for template-based association implementation
// ****************************************************************
class IOther // Inventor Other functionality
{
String nm;
. . .
public:
IOther(char * p = "") : nm(p) {}
~IOther() {}
char * name() { return nm.get(); }
void name(char * p) { nm.set(p); }
. . .
};
class COther // Contraption Other functionality
{
String tl;
. . .
public:
COther(char * p = "") : tl(p) {}
~COther() {}
char * title() { return tl.get(); }
void title(char * p) { tl.set(p); }
. . .
};
Listing Eleven
// **************************************************************
// Derived class templates implementing association functionality
// **************************************************************
template <class LB, class RB> class L1to1;
template <class LB, class RB> class R1to1;
// Forward declarations
template <class LB, class RB>
void link(L1to1<LB,RB> & L,R1to1<LB,RB> & R);
template <class LB, class RB>
void unlink( L1to1<LB,RB> & L );
template <class LB, class RB>
void unlink( R1to1<LB,RB> & R );
// Function template prototypes
template <class LB, class RB>
class L1to1 : public LB
{
R1to1<LB,RB> * r;
void set( R1to1<LB,RB> * p ) { r = p; }
public:
L1to1() : LB(), r(0) {}
~L1to1() { unlink(*this); }
R1to1<LB,RB> * follow() { return r; }
friend void link( L1to1<LB,RB> &, R1to1<LB,RB> & );
friend void unlink( L1to1<LB,RB> & );
friend void unlink( R1to1<LB,RB> & );
};
template <class LB, class RB>
class R1to1 : public RB
{
L1to1<LB,RB> * l;
void set( L1to1<LB,RB> * p ) { l = p; }
public:
R1to1() : RB(), l(0) {}
~R1to1() { unlink(*this); }
L1to1<LB,RB> * follow() { return l; }
friend void link( L1to1<LB,RB> &, R1to1<LB,RB> & );
friend void unlink( L1to1<LB,RB> & );
friend void unlink( R1to1<LB,RB> & );
};
Listing Twelve
// ******************************************************
// Parameterized link management function implementations
// for template based association implementation
// ******************************************************
template <class LB, class RB>
void link(L1to1<LB,RB> & L, R1to1<LB,RB> & R)
{
// link only if both objects are unlinked at entry
if( !L.follow() && !R.follow() )
{
L.set( &R );
R.set( &L );
}
}
template <class LB, class RB>
void unlink( L1to1<LB,RB> & L )
{
// unlink only if linked at entry
if ( L.follow() )
{
L.follow()->set(0);
L.set(0);
}
}
template <class LB, class RB>
void unlink( R1to1<LB,RB> & R )
{
// unlink only if linked at entry
if ( R.follow() )
{
R.follow()->set(0);
R.set(0);
}
}