[ Team LiB ] Previous Section Next Section

Gotcha #90: Improper Container Substitutability

The STL containers are the default containers of choice for C++ programmers. However, STL containers don't answer all needs, in part because their strengths also imply some limitations. One of the nice things about the STL containers is that, because they're implemented with templates, most of the decisions about their structure and behavior are made at compile time. This results in small and efficient implementations precisely tuned to the static context of their use.

However, all relevant information may not be present at compile time. For example, consider a simplified framework-oriented structure that supports the "open-closed principle," in that it may be modified and extended without recompilation of the framework. This simple framework contains a hierarchy of containers and a parallel hierarchy of iterators:

gotcha90/container.h



template <typename T> 


class Container {


 public:


   virtual ~Container();


   virtual Iter<T> *genIter() const = 0; // Factory Method


   virtual void insert( const T & ) = 0;


   // . . .


};


template <typename T>


class Iter {


 public:


   virtual ~Iter();


   virtual void reset() = 0;


   virtual void next() = 0;


   virtual bool done() const = 0;


   virtual T &get() const = 0;


};


We can write code in terms of these abstract base classes, compile it, and later augment it by adding new derived container and iterator classes:

gotcha90/main.cpp



template <typename T> 


void print( Container<T> &c ) {


   auto_ptr< Iter<T> > i( c.genIter() );


   for( i->reset(); !i->done(); i->next() )


       cout << i->get() << endl;


}


The use of parallel hierarchies in a design is, in general, problematic, because a change to one hierarchy requires coordinated change in the other. We would prefer to be able to have a single point of change. However, use of the Factory Method pattern in the implementation of Container helps mitigate this problem in our Container/Iter parallel hierarchy.

A Factory Method provides a mechanism for the user of an abstract base class interface to generate an object appropriate to the actual type of the derived object while remaining ignorant of the object's type. In the case of the Container abstract base class, a user of Container's genIter Factory Method is saying, "Generate an Iter of the appropriate type to yourself, but spare me the details." Often, use of a Factory Method is an alternative to the ill-advised use of type-based conditional code (see Gotcha #96). In other words, we never want to write code that says, essentially, "Container, if you're actually an Array, give me an ArrayIter. Otherwise, if you're a Set, give me a SetIter. Otherwise …"

It's fairly easy to design substitutable derived Container types. A Set<T> would then be substitutable for a Container<T>, and the usual conversions from Set<T> * to Container<T> * would hold. The presence of the pure virtual genIter Factory Method in the Container base class is an explicit reminder for the designer of a concrete container type to perform the corresponding maintenance on the Iter hierarchy:



template <typename T> 


SetIter<T> *Set<T>::genIter() const


   { return new SetIter<T>( *this ); } // better write SetIter!


However, there is an unfortunate and common tendency to assume that substitutability of container elements implies substitutability of the containers of these elements. We know that this relationship doesn't hold for arrays, C++'s predefined container. An array of derived class objects may not be reliably substituted for an array of base class objects (see Gotcha #89). The same warning applies to user-defined containers of substitutable elements. Consider the following simple container hierarchy in support of a financial-instrument-pricing framework:

gotcha90/bondlist.h



class Object 


   { public: virtual ~Object(); };


class Instrument : public Object


   { public: virtual double pv() const = 0; };


class Bond : public Instrument


   { public: double pv() const; };


class ObjectList {


 public:


   void insert( Object * );


   Object *get();


   // . . .


};


class BondList : public ObjectList { // bad idea!!!


 public:


   void insert( Bond *b )


       { ObjectList::insert( b ); }


   Bond *get()


       { return static_cast<Bond *>(ObjectList::get()); }


   // . . .


};


gotcha90/bondlist.cpp



double bondPortfolioPV( BondList &bonds ) { 


       double sumpv = 0.0;


       for( each bond in list ) {


              Bond *b = current bond;


              sumpv += b->pv();


       }


       return sumpv;


}


Now, nothing is wrong with implementing a list of Bond pointers with a list of Object pointers (although a better design would have employed a list of void * and drop-kicked the entire notion of an Object class into the bit bucket; see Gotcha #97). The error is in using public inheritance, rather than private inheritance or membership, to force an is-a relationship on types that are not substitutable. In essence, when we wrapped access to our substitutable pointers in a container, we rendered them unsubstitutable. However, unlike the case in which we have a pointer to a pointer (or an array of pointers) the compiler can no longer warn us of our folly (see Gotcha #33):

gotcha90/bondlist.cpp



class UnderpaidMinion : public Object { 


 public:


   virtual double pay()


       { /* deposit $1M in minion's account */ }


};


void sneaky( ObjectList &list )


   { list.insert( new UnderpaidMinion ); }


void victimize() {


   BondList &blist = getBondList();


   sneaky( blist );


   bondPortfolioPV( blist ); //done!


}


Here, we've managed to substitute one sibling class object for another; we've plugged in an UnderpaidMinion where the pricing framework is expecting a Bond. Under most environments, the result will be an invocation of UnderpaidMinion::pay rather than Bond::pv; an undetectable runtime type error. Just as an array of substitutable derived objects is not substitutable for an array of base objects or pointers, a user-defined container of substitutable derived objects or pointers is not substitutable for a user-defined container of base objects or pointers.

Container substitutability, if present at all, should focus on the structure of the container and not that of the contained elements.

    [ Team LiB ] Previous Section Next Section