Containing Heterogeneous Types

A few years ago, when most people thought that "object oriented" meant "whatever Smalltalk does," it was fairly common for new C++ programmers to ask how to implement heterogeneous containers, that is, containers that could hold any type of item. When pressed for details on what such a thing could be used for, one common response was that it would be just like a pencil holder on your desk -- even though it’s called a pencil holder, you can put anything you want into it. The problem with this reasoning, as with all analogies when they are pushed too far, is that it omits an important factor: If your pencil holder is filled with things that aren’t pencils, you have to rummage through its contents when you need a pencil. In software this means that objects that you put into a container cannot be arbitrary types, because at a minimum you have to know something about their types in order to do anything useful with them. In Smalltalk, type information is entwined deep in the structure of every object. You don’t have to do anything special to support runtime type queries, so you don’t have to write any extra code to keep track of the types of the objects that you put into a container. In C++ you don’t pay for what you don’t need, so if you want to be able to ask about the type of an object at runtime you have to write some code to support runtime type inquiries.

C++ doesn’t have a universal mechanism for runtime type inquiries. The closest thing is typeid¹, but the compiler must know a little bit about the actual type of the object in order for you to use it. If you have only a pointer to void, typeid can’t tell you anything about the actual type of the object that the pointer points to. If you have a pointer to a type that has no virtual functions, typeid can tell you the type that the pointer is declared to point to, but it cannot tell you whether the type of an object that such a pointer points to is actually a type derived from the declared type of the pointer. In order to fully use runtime type queries you must use pointers to types that have virtual functions. That’s not a significant limitation, however. In order to get runtime type checking like that in Smalltalk, you need only derive all of your classes from a single base type that has at least one virtual function. Once you’ve done that, you can write heterogeneous containers that are pretty much like the ones in Smalltalk.

In general, though, having a common base class for all the classes in a C++ application is a symptom of overdesign. It’s a result of trying too hard to generalize, without taking into account the cost in size and speed that generality imposes. In languages like Smalltalk and Java, where the common base is imposed by the language, the compiler and runtime system can be tuned to minimize the overhead that results from this requirement. Still, the ability to identify all types at runtime is not free. In the kinds of applications that Smalltalk is designed for the cost is usually acceptable. In the kinds of applications that C++ is designed for the cost may well be prohibitive.

On the other hand, C++ offers several lower cost alternatives to universal type queries. By carefully choosing a technique that’s appropriate to the problem at hand, we can minimize the cost of writing code that handles different data types. These techniques aren’t as convenient as universal type identification -- they have to be planned, and incorporated into your application’s design. But by focusing on the areas where type identification is actually needed we can produce solutions that are smaller and faster than the approaches taken by languages like Smalltalk where type identification is available for every object, whether it’s needed or not.

For most C++ programmers, their first brush with heterogeneous containers occurs through the use of polymorphism. One of the most common beginner’s examples of polymorphism involves a base class with a name like screen_object, a member function to set its position on the screen, and a virtual member function to draw it. Derived classes such as circle, rectangle, and triangle override the draw function in obvious ways to provide behavior appropriate to their type. Once we’ve decided on the design of the class screen_object, we can create a container that holds pointers to objects whose types are derived from screen_object, and know that we can draw all of the objects held in our container. We can also go one step further, and make our container a drawable object. We’d do this by deriving it from screen_object, and giving our container a member function that overrides draw and iterates through all of the items that it holds, calling draw on each of them. Like this:


class screen_object
{
public:
    virtual void draw() = 0;
};

class figure : public screen_object
{
public:
    figure() : num(0) {}
    void add(screen_object *obj) { items[num++] = obj; }
    void draw();
private:
    int num;
    screen_object *items[10];
};

void figure::draw()
    {
    for (int i = 0; i < num; ++i)
        items[i]->draw();
    }

I’ve left out many details of the classes screen_object and figure: there’s no screen position stored anywhere in these objects; items should be a pointer to screen_object rather than a hard-coded array, so that it can be dynamically resized; there should be a mechanism to draw the contained objects at positions relative to the position of figure; and so on. Those are important details when you are writing the application, but for our purposes here they aren’t important. The key to understanding this type of container is that it holds objects whose types are derived from screen_object. This lets us rely on polymorphism without any need for runtime type checking.

Compare this with a similar class, written in Java, that uses a heterogeneous container:


interface ScreenObject
{
public abstract void draw();
}

class Figure
    extends ScreenObject
{
public void add(ScreenObject o) { items.add(o); }
public void draw()
    {
    for (int i = 0; i < items.length(); ++i)
        ((ScreenObject)items.elementAt(i)).draw();
    }
private Vector items;
}

Superficially this looks very much like the C++ code. The one critical design difference is revealed by the cast that’s used in order to be able to call draw on objects held by the container. That cast does a runtime type check, and will throw an exception if the type of the item that we’re calling it on is not derived from ScreenObject. That runtime type check takes time, slowing down the code that uses this container².

The next form of heterogeneous container that C++ programmers are exposed to is the container template. Of course, a container template is heterogeneous only in the sense that the same template code can be used to create different containers that hold different types. The container’s source code, properly written, is heterogeneous; the container itself, instantiated from the template, is not. Still, a template is often the right answer when we need a general-purpose container. Since the type of the elements in a container template is specified at compile time, we don’t have to incur the overhead of runtime type checks.

When we write a container template it helps to start conservatively. C++ programmers often get themselves into trouble when they first start writing container templates because they try to do everything at once, writing the implementation code for the container while simultaneously trying to generalize it. That can be difficult. It’s usually better to write container templates in two steps: first write the container, then turn it into a template.

For example, we’ve already written a container that can hold pointers to objects of type screen_object. That’s a good starting point for a container template that can hold pointers to an arbitrary type. First let’s remove screen_object as a base and add an index operator so that we can look at the pointers in the container:


class container
{
public:
    container() : num(0) {}
    void add(screen_object *obj)
        { if (num != 10) items[num++] = obj; }
    screen_object *operator[](int pos)
        { return num <= pos ? 0 : items[pos]; }
private:
    int num;
    screen_object *items[10];
};

Of course, in an actual application the code for this container would check whether there is enough room to add a pointer, and the container would probably also have code to remove a pointer.

The limit of ten items is in some ways artificial: I used it to make the code simpler. In most applications we’d want to be able to change the size of the array automatically when an add would run off the end. On the other hand, there are also situations where a fixed-size array is appropriate, so we’ll stick with a fixed-size array.

Once we have all the code working correctly we can think about how to generalize the code. One obvious generalization is to allow the user to determine the size of the array. Instead of hard-coding its size as 10 we can turn the class into a template and specify the size as a template argument:


template<size_t sz> class container1
{
public:
    container1() : num(0) {}
    void add(screen_object *obj)
        { if (num != sz) items[num++] = obj; }
    screen_object *operator[](int pos)
        { return num <= pos ? 0 : items[pos]; }
private:
    int num;
    screen_object *items[sz];
};

typedef container1<10> container;

If we replace our original definition of container with this code, any other code that we’ve written that used container should continue to work, and new code can take advantage of the possibility of using a larger array.

The obvious next step in generalizing this template is to allow the user to specify the type of object that will be put into the container. This is a simple change, too:


template<class T, size_t sz> class container2
{
public:
    container2() : num(0) {}
    void add(T *obj)
        { if (num != sz) items[num++] = obj; }
    T *operator[](int pos)
        { return num <= pos ? 0 : items[pos]; }
private:
    int num;
    T *items[sz];
};

typedef container2<screen_object, 10> container;

Here, too, if we replace our original definition of container with this code, any other code that used container will still work. If we were thinking ahead we didn’t release the code for container1 to anyone, so we don’t have to maintain compatibility with it. If we do have to provide support for users of container1 we’ve got a bit more work to do -- we need to provide a template named container1 that takes only a size argument and uses our new code. There’s no simple way to do this: we have to write a wrapper template. That’s easy to do in this case:


template<class sz> class container1
    : public container2<screen_object, sz>
{
};

Now users of our old version won’t have to change any of their code to upgrade to our new version³.

We’re still not done, though. Much of the code that the compiler produces for containers that hold different types will actually be identical. Although you often hear that this is merely an optimization issue and that compilers will soon be smart enough to reuse code that doesn’t change when you create a different template instance, there is no compiler that I know of that actually does that. If overall code size is important in our application we’ve got to handle code merging ourselves. In the case of a container that holds pointers, it’s easy: go back to a template like our container1, and modify it to only handle pointers to void. Use that to implement each of our type-specific template instances.


template<size_t sz> class void_array
{
protected:
    void_array() : num(0) {}
    void add(void *obj)
        { if (num != sz) items[num++] = obj; }
    void *operator[](int pos)
        { return num <= pos ? 0 : items[pos]; }
private:
    int num;
    void *items[sz];
};

template<class T, size_t sz> class container3
    : private void_array<sz>
{
public:
    void add(T *obj) { return void_array<sz>::add(obj); }
    T *operator[](int pos)
        { return static_cast<T*>(
            void_array<sz>::operator[](pos)); }
};

The member functions in the template container3 handle the pointer type conversions needed to go to and from the implementation of the container as a container of pointers to void. These conversions have no overhead, so there is no runtime cost involved in implementing a typesafe container in this way.

Java, of course, does not have templates, so we can’t use the same approach there. What we can do, as we saw earlier, is to write a single container that will hold objects of any type, and use that to implement a container that holds objects of a more restrictive type, by cutting, pasting and editing the definition of that container as needed.


class Container4
{
public void add(MyType obj) { vec.add(obj); }
public MyType elementAt(int pos)
    { return (MyType)vec.elementAt(pos); }
private Vector vec;
};

However, Java has nothing that’s analogous to C++’s static_cast, so there’s no way to say in the source code that we know that the cast in Container4.elementAt is always safe. The compiler will always check that the conversion is valid.

As I said earlier, if you really need to create a heterogeneous container in C++ you can write a base class with a virtual function, so that you can use typeid, and derive your classes from it. Like this:


class ident
{
public:
    virtual ~ident() {}
};

class int_val : public ident
{
public:
    int_val(int i) : val(i) {}
    int get() { return val; }
private:
    int val;
};

class long_val : public ident
{
public:
    long_val(long i) : val(i) {}
    long get() { return val; }
private:
    long val;
};

Now you can write a container that holds objects of type int_val and long_val, and can determine which is which:


class values
{
public:
    void add(int_val *iv) { data.add(iv); }
    void add(long_val *lv) { data.add(lv); }
    int_val *operator[](int pos)
        { return dynamic_cast<int_val*>(data[pos]); }
    long_val *operator[](int pos);
        { return dynamic_cast<long_val*>(data[pos]); }
private:
    container3<ident, 10> data;
};

Since objects of type ident have a virtual function, we can use dynamic_cast to do a checked conversion on the pointers that we get from data. With the minimal interface that I’ve given here, you can ask for an int_val pointer or a long_val pointer stored at any location, and if the pointer in that location points to an object of some other type you’ll get back a null pointer.

Finally, although it’s not strictly speaking a container at all, you can use a variable argument list to pass around objects of distinct types. Just as in all our previous examples, you have to be able to figure out the actual type of the object that you’re dealing with. If you’ve ever used printf you’re familiar with one way of passing type information around, by putting a type marker into an array. We’ll use the same technique here:


typedef enum
{
end,        /* end-of-data marker   */
b_int,  /* built-in int type    */
b_long, /* built-in long type   */
u_int,  /* user-defined int type    */
u_long  /* user-defined long type   */
} arg_type;

We can store these type information values in an array, and pass that array to a function that will use it to interpret the types of the elements in our variable argument list:


#include <stdio.h>
#include <stdarg.h>

void show(arg_type *types, ...)
{
va_list ap;
va_start(ap, types);
for (;;)
    switch(*types++)
        {
        case end:
            va_end(ap);
            return;
        case b_int:
            printf("%d\n", va_arg(ap, int));
            break;
        case b_long:
            printf("%ld\n", va_arg(ap, long));
            break;
        case u_int:
            printf("%d\n", va_arg(ap, int_val).get());
            break;
        case u_long:
            printf("%ld\n", va_arg(ap, long_val).get());
            break;
        }
}

To see this code in action, try something like this:


int main()
    {
    int i = 1;
    long l = 2;
    int_val iv(3);
    long_val lv(4);
    arg_type types[] = { b_int, b_long, u_int, u_long, end };
    show(types, i, l, iv, lv);
    return 0;
    }

Now, I’ll admit that that’s a somewhat facetious example. It’s primary point, though, is one that I’ve made throughout this column: you have to know what type of object you’re dealing with. There are no truly heterogeneous containers, just containers with varying degrees of homogeneity.

In C++, the two primary mechanisms for writing code that handles different types of objects are templates and polymorphism. When you use a template you specify the type that it handles at the time that you compile your code. When you use polymorphism you specify a limited set of types that can be used interchangeably, and the compiler generates efficient code that masks the differences. I haven’t yet run into a programming problem involving containers that couldn’t be solved efficiently with one of these two techniques. If you’re tempted to write a universal base class so that you can have a single type of container for all of your objects, think carefully about the overhead. Those dynamic casts are expensive, and they may well make the difference between an application that works well and an application that is too slow to use. Object oriented programming is much more than what Smalltalk does, and containers are much less.

Containing Heterogeneous Types

The C/C++ Users Journal, December, 1999