The Standard Containers as Class Templates
by Steve Donovan, from the Book C++ by Example: "UnderC" Learning Edition
MAR 22, 2002
Why do generic classes make excellent containers? This excerpt from C++ by Example (Que, 2001) by Steve Donovan shows some of the consequences of not having them.
This article is provided courtesy of Que.
This article is excerpted from C++ by Example (Que, 2001, ISBN: 0789726769), by Steve Donovan.
How were things handled before templates were available? The first problem with creating containers without templates is that they are not type safe. Imagine if you had only list<void *>; any pointer could be put in such a list. You would need to write code like this:
typedef list<void *> List; // the one & only list...
void draw_shapes(TG& tg, const List& ls)
{
List::iterator li;
for(li = ls.begin(); li != ls.end(); ++li)
static_cast<Shape *>(*li)->draw(tg);
}
This looks nasty, and it is nasty. There is no guarantee at runtime that this list contains only pointers to Shape. A program would inevitably decide to put something odd in the list when it was being used for some crucial operation on the other side of the planet (or, indeed, another planet altogether). It is not possible to check all the possibilities in even a moderate-sized application. Type safety is a guarantee that no surprises with odd types can happen—that they will be caught by the compiler, not the customer.
Traditional object-oriented languages rely on runtime-type information. Every class derives from some polymorphic base class, usually called Object. In Delphi, for instance, deriving from Object is implicit, so the is operator can always work. Of course, this strategy works in C++ as well, as long as the ultimate base class Object has at least one virtual method. The class Shape will have to be derived from Object in some way. Then dynamic_cast() will work. The previous example becomes this:
typedef list<Object *> List; // the one & only list...
void draw_shapes(TG& tg, const List& ls)
{
List::iterator li;
for(li = ls.begin(); li != ls.end(); ++li) {
Shape *ps = dynamic_cast<Shape *>(*li)
if (ps != NULL) ps->draw(tg);
}
}
There is now a proper runtime guarantee, at the cost of continuous checking. But what should you do if the object isn't a Shape pointer? Surely you should raise an alarm or make a note somewhere. Although this code is safe, it could be masking an error somewhere else. There should only be Shape pointers in this list; it isn't considered particularly clever to keep different kinds of objects together.
NOTE
Java tends to do things like this. Because there are no parameterized types; typically, code needs plenty of typecasts, which are all dynamic.
So far, we have only talked about pointers. Languages such as Java and Delphi really deal only with references to objects, but they also have to deal with the common case of just wanting a list of integers or doubles. You can either get a whole number of extra container classes or wrap the simple types themselves as objects, which is what Java does (Delphi programmers have a horrible habit of trying to stuff integers into lists of pointers). This is the second problem related to life without templates.
C++ must deal with value-oriented types such as std::string. These types do not fit very well into a pointer-list scheme. There is an object-oriented approach to containers of such types, but it isn't pretty. You define a special base class—which you could call Linkable—that contains a pointer to another Linkable object. Any class that you inherit from Linkable therefore has the ability to link to another Linkable object, rather like the parade of circus elephants holding the tails of their fellows. You can then run through the list by following pointers, until some stopping condition (in the case of a circular list, the elephants keep going around the ring). But this is awkward; it means that you have to decide, as part of your design, that your objects are going to be kept in a list. There would need to be auxiliary types such as linkable strings.
The design of the C++ standard containers answers these two problems, as well as another: C++ standard containers present a very similar interface to the world. With some care, code can switch from using list<T> to vector<T> by changing a single typedef.1 Say you have found that a time-consuming task is iterating through containers; in this case, switching to a vector makes perfect sense. The philosophy is that whether you put widgets in a list, vector, deque, map, or set, it should not be a high-level design decision.
Note an important property of class templates; not every method is compiled when a template class is instantiated; only methods that are referenced in the code, or are needed to implement those methods, are compiled. This can obviously save a lot of dead code (although smart linkers can strip out such baggage). But this is crucial to the design of classes like list<T>. For example, the standard list has a method remove() that is given a specific element value to take out, but not every type has defined what it means to be equal. Similarly, the method sort() assumes that e1 < e2 makes sense. So instantiating only code that is directly needed makes it possible to generate lists of simple structs, which don't define equality or ordering.
The downside of using template containers is that a program might end up containing many different instances of a particular template type. It is common to keep lists of many different kinds of objects, and it is unfortunate if the program has to keep that many (practically identical) copies of the list code. This is often solved by specialization: You can define list<T *> in terms of list<void *>. The specialized template for pointer types becomes a thin "type-safe" wrapper around list<void *>. The code would look something like this:
typedef list<void *> ListP;
template <class T>
class list<T *>: private ListP {
...
void push_back(T *p)
{ ListP::push_back((void *)p); }
T * back()
{ return (T *) ListP::back(); }
...
};
The basic pointer list type ListP is used as a private base class because list<T *> redefines every public member anyway—it is pure "implementation inheritance." This is not the most exciting code to write, but such specializations are fast because they are so easy to inline.
