Item 40:  Model "has-a" or "is-implemented-in-terms-of" through layering.

Layering is the process of building one class on top of another class by having the layering class contain an object of the layered class as a data member. For example:

class Address { ... };           // where someone lives

class PhoneNumber { ... };

class Person {
public:
  ...

private:
  string name;                   // layered object
  Address address;               // ditto
  PhoneNumber voiceNumber;       // ditto
  PhoneNumber faxNumber;         // ditto
};

In this example, the Person class is said to be layered on top of the string, Address, and PhoneNumber classes, because it contains data members of those types. The term layering has lots of synonyms. It's also known as composition, containment, and embedding.

Item 35 explains that public inheritance means "isa." In contrast, layering means either "has-a" or "is-implemented-in-terms-of."

The Person class above demonstrates the has-a relationship. A Person object has a name, an address, and telephone numbers for voice and FAX communication. You wouldn't say that a person is a name or that a person is an address. You would say that a person has a name and has an address, etc. Most people have little difficulty with this distinction, so confusion between the roles of isa and has-a is relatively rare.

Somewhat more troublesome is the difference between isa and is-implemented-in-terms-of. For example, suppose you need a template for classes representing sets of arbitrary objects, i.e., collections without duplicates. Because reuse is a wonderful thing, and because you wisely read Item 49's overview of the standard C++ library, your first instinct is to employ the library's set template. After all, why write a new template when you can use an established one written by somebody else?

As you delve into set's documentation, however, you discover a limitation your application can't live with: a set requires that the elements contained within it be totally ordered, i.e., for every pair of objects a and b in the set, it must be possible to determine whether a<b or b<a. For many types, this requirement is easy to satisfy, and having a total ordering among objects allows set to offer certain attractive guarantees regarding its performance. (See Item 49 for more on performance guarantees in the standard library.) Your need, however, is for something more general: a set-like class where objects need not be totally ordered, they need only be what the °C++ standard colorfully terms "EqualityComparable": it's possible to determine whether a==b for objects a and b of the same type. This more modest requirement is better suited to types representing things like colors. Is red less than green or is green less than red? For your application, it seems you'll need to write your own template after all.

Still, reuse is a wonderful thing. Being the data structure maven you are, you know that of the nearly limitless choices for implementing sets, one particularly simple way is to employ linked lists. But guess what? The list template (which generates linked list classes) is just sitting there in the standard library! You decide to (re)use it.

In particular, you decide to have your nascent Set template inherit from list. That is, Set<T> will inherit from list<T>. After all, in your implementation, a Set object will in fact be a list object. You thus declare your Set template like this:

// the wrong way to use list for Set
template<class T>
class Set: public list<T> { ... };

Everything may seem fine and dandy at this point, but in fact there is something quite wrong. As Item 35 explains, if D isa B, everything true of B is also true of D. However, a list object may contain duplicates, so if the value 3051 is inserted into a list<int> twice, that list will contain two copies of 3051. In contrast, a Set may not contain duplicates, so if the value 3051 is inserted into a Set<int> twice, the set contains only one copy of the value. It is thus a vicious lie that a Set isa list, because some of the things that are true for list objects are not true for Set objects.

Because the relationship between these two classes isn't isa, public inheritance is the wrong way to model that relationship. The right way is to realize that a Set object can be implemented in terms of a list object:

// the right way to use list for Set
template<class T>
class Set {
public:
  bool member(const T& item) const;

  void insert(const T& item);
  void remove(const T& item);

  int cardinality() const;

private:
  list<T> rep;                       // representation for a set
};

Set's member functions can lean heavily on functionality already offered by list and other parts of the standard library, so the implementation is neither difficult to write nor thrilling to read:

template<class T>
bool Set<T>::member(const T& item) const
{ return find(rep.begin(), rep.end(), item) != rep.end(); }

template<class T>
void Set<T>::insert(const T& item)
{ if (!member(item)) rep.push_back(item); }

template<class T>
void Set<T>::remove(const T& item)
{
  list<T>::iterator it =
    find(rep.begin(), rep.end(), item);

  if (it != rep.end()) rep.erase(it);
}

template<class T>
int Set<T>::cardinality() const
{ return rep.size(); }

These functions are simple enough that they make reasonable candidates for inlining, though I know you'd want to review the discussion in Item 33 before making any firm inlining decisions. (In the code above, functions like find, begin, end, push_back, etc., are part of the standard library's framework for working with container templates like list. You'll find an overview of this framework in Item 49 and M35.)

It's worth remarking that the Set class interface fails the test of being complete and minimal (see Item 18). In terms of completeness, the primary omission is that of a way to iterate over the contents of a set, something that might well be necessary for many applications (and that is provided by all members of the standard library, including set). An additional drawback is that Set fails to follow the container class conventions embraced by the standard library (see Items 49 and M35), and that makes it more difficult to take advantage of other parts of the library when working with Sets.

Nits about Set's interface, however, shouldn't be allowed to overshadow what Set got indisputably right: the relationship between Set and list. That relationship is not isa (though it initially looked like it might be), it's "is-implemented-in-terms-of," and the use of layering to implement that relationship is something of which any class designer may be justly proud.

Incidentally, when you use layering to relate two classes, you create a compile-time dependency between those classes. For information on why this should concern you, as well as what you can do to allay your worries, turn to Item 34.