Class Templates

Function templates allow very general code to be written that will work for different kinds of types. Class templates do the same for classes; all the class data and member functions become parameterized by type parameters. Class templates are machines for generating families of related classes.

A Parameterized Class

When you are designing classes, you need to make choices. In some cases, such as when either choice seems perfectly valid, it is irritating to have to choose. For example, consider a Point class that represents a two-dimensional coordinate. Should it contain integers, floats, or doubles? There are good arguments for all three choices. Using typedefs is helpful, as in the following example:

typedef double coord_t;
struct Point {
   coord_t x,y;
};

In this example, there is only one place where the explicit type is mentioned (this is particularly useful for numerical code, where the choice of float or double can give you valuable clues about the precision of the algorithms). However, sometimes you want floating-point coordinates, and other times you want integer coordinates. Once again, macro magic such as the following used to be applied:

#define POINT(T) Point_#T
#define DEF_POINT(T) struct POINT(T) {  T x,y; }
DEF_POINT(int);    // => struct Point_int {  int x,y; };
DEF_POINT(float);  // => struct Point_float {  float x,y; };
POINT(int) p1,p2;  // => Point_int p1,p2;

This magic is fine, to a point, but it scales badly. Imagine taking the Vector class mentioned in Chapter 9, “Copying, Initialization, and Assignment,” and making a huge 200-line #define statement. If there were an error, you would have virtually no idea where it occurred, and you wouldn't be able to debug any runtime problems. The template solution is much more elegant:

template <class T>
  struct Point {
    T x,y;
  };
;> Point<int> ip;
;> Point<double> dp;
						

It is important to note that Point<int> and Point<double> are also completely independent classes. It is true that they are both types of Point and that int can convert to double. But these facts don't mean that a Point<int> can automatically convert into a Point<double>. You can easily write functions to do the conversion, as in the following example:

Point<double> point(Point<int> p) {
   Point<double> pd;
   pd.x = p.x;  pd.y = p.y;
   return pd;
}

Point<int> point(Point<double> pd) {
   Point<int> p;
   p.x = pd.x;  p.y = pd.y;
   return p;
}

;> Point<int> p; p.x = 10; p.y = 20;
(int) 10
(int) 20
;> Point<double> pd = point(p);
;> p.x; p.y;
(double) 10
(double) 10

Observe that the Point<int> and Point<double> functions are quite distinct from one another because their argument types are different classes. Later in this chapter, the case study shows how you can build such relationships between template classes.

The template type parameters can be ordinary types as well. Consider the following Buffer class, which has two type parameters; the first can be any C++ type, and the second has to be an int:

// buffer.cpp
// C++ By Example, Chapter 10, Steve Donovan
#include <iostream>
using namespace std;

template <class T, int N>
  class Buffer {
   T m_arr[N];
  public:
   Buffer()
   {  for(int i = 0; i < N; i++) m_arr[i] = 0; }

   int size()
   {  return N; }

   T& operator[] (int i)
   {  return m_arr[i]; }
 };

template <class T, int N>
 ostream& operator<< (ostream& os, Buffer<T,N>& p)
 {
  for(int i = 0; i < p.size(); i++) cout << p[i] << ' ';
  return os;
 }

int main()
{
 int vals[] = { 23,43,56,22,22};
 Buffer<int,10> buff;
 for(int i = 0; i < 5; i++) buff[i] = vals[i];
 cout << buff << endl;
}

The Buffer class template is meant to be an efficient array-like class. The parameter N is a constant, so a C++ array can be used as the representation. Note how Buffer template classes are written: Buffer<int,10>. The template class Buffer<int,12> would be completely different class.

It is often not difficult to convert existing classes into template classes. Generally, it's a good idea to develop code for some particular type, iron out the troubles, and only then make the code into a template. You can turn the Vector class from Chapter 9 into a class template by adding a few extra lines. Here is the first forty-odd lines of a Vector class template; the rest of the code is absolutely identical, and you can see the whole class in chap10vector.h. There are three changes from the original version: template <class T> has been added before the class declaration (see (a)), typedef int T is commented out (see (b)), and the exception type RangeError has been moved out of the class body. This conversion to a template was easy because the original Vector uses typedef to define T to mean int.

// C++ By Example, Chapter 10
// A simple vector template
#include "ref_count.h"
const int NGROW = 10;

struct RangeError {  // *moved outside
     int idx;
     RangeError(int i) {  idx = i; }
     int where() {  return idx; }
};

template class<T>   // *added (a)
class Vector: public RefCount {
 public:
//  typedef int   T;   // *removed (b)
 private:
   T *m_begin;
   T *m_end;
   int m_size;
   int m_cap;
 public:
   typedef T *       iterator;
   typedef const T * const_iterator;
   typedef T         value_type;

   iterator begin()  {  return m_begin; }
   iterator end()    {  return m_end;   }
   int size()        {  return m_size; }
   int capacity()    {  return m_cap;  }

   T& operator[] (int i)
   {  return m_begin[i]; }

   T& at(int i)
   {
    if (i < 0 || i >= m_size) throw RangeError(i);
    return m_begin[i];
   }
  . . . (rest unchanged) . . .

A template class can inherit from an ordinary class. This can be very useful from both design and implementation perspectives. From the design perspective, it means that all the classes Vector<T>, (for all T) are related to each other by derivation; they are all RefCount objects. The class template Vector becomes a machine for breeding subclasses of RefCount. In implementation terms, the benefit is that you do not have to carry the extra reference-counting code in each instance of Vector<T>. With large classes, factoring out the common, non-type-specific code and moving it up into a base class can make a noticeable difference.

Moving out RangeError is necessary because you want one exception class to represent out-of-range errors for all instances of Vector. If RangeError were left inside, Vector<int> would throw Vector<int>::RangeError and Vector<double> would throw Vector<double>::RangeError; these are quite distinct types (unless you needed to make the exceptions distinct). So, in fact, nested classes are implicitly template classes.

The rest of the code for Vector<T> is completely the same as for Vector, but the meaning is different. For example, look at the copy assignment operator for Vector<T>:

Vector& operator= (const Vector& v)
{
     _alloc_copy(v);
     return *this;
}

Within the class body is the one place you can get away with just using the class template name to mean the template class; in this case, it is assumed that Vector means Vector<T>. However, it would not be an error to spell it out in full.

The Standard Containers as Class Templates

It is clear from the Vector<T> example in the preceding section how std::vector<T> can be implemented. But before we move on, we need to review how things were 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 that the is operator can always work. Of course, this strategy works in C++ as well; the ultimate base class Object needs 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.

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. 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.

Template Functions That Generate Template Classes

One big difference between class and function templates is that the type parameter is not deduced from the arguments for class templates. That is, you always have to follow the template name with <type> when constructing a template class. At first this seems irritating, compared to template functions that work so transparently. The reason is contained in the question: What arguments can be used to deduce the type? You would have to use the constructor arguments, but there will always be more than one constructor in a non-trivial class and so practically it's impossible to deduce type parameters for a class template. However, it's not difficult to write function templates that deduce the type and use it to instantiate a template class.

For instance, an interesting part of the standard C++ library is back_inserter(), which makes copying into containers easy. Here is an example:

;> list<int> ls;
;> int arr[] = { 20,30,50};
;> copy(arr,arr+3,back_inserter(ls));
						

back_inserter() is necessary because originally the list has no elements; using ls.begin() as the output iterator will not work, since there simply aren't any elements in the list. Something is needed that looks like an output iterator and does the pushing at the list's end.

To do this, you create a class such as the following that imitates an output iterator—that is, it defines operator* and operator++. This class keeps one member, which is a reference to the container m_container, and another member, which is the same type as the container element m_val. operator*. This class also returns a reference to m_val, so it will get modified by expressions like *pi = val. operator++ and then push m_val onto the end of m_container:

template <class C>
 class BackInserter {
 private:
    C& m_container;
    typename C::value_type m_val;
  public:
   typedef C::value_type value_type;
   BackInserter (C& c)
    : m_container
    {  }

   value_type&
   operator*()
   {  return m_val; }

  BackInserter&
   operator++()  {
     m_container.push_back(m_val);
     return *this;
   }
 };
;> BackInserter<list<int> > bi(ls);   // watch out for '> >' !
;> *bi = 10;      // sets the value...
(int&) 10
;> ++bi;          // actually does the push!
						

This example probably isn't the fastest way to handle the situation, but it does the job. This class depends on two reliable things: A standard container makes its element type known as value_type, and it has a push_back() method. But this kind of class is not intended for direct use. Declaring it is a bit painful because it is itself parameterized by a template class. (Notice the extra space between the last angle brackets (> >)—this is one of the few places in C++ where a little whitespace is necessary; the symbol >> is something else altogether). Therefore, back_inserter() is defined as a simple function template:

template <class C>
   BackInserter<C>
   back_inserter(C& c)
   {
      return BackInserter<C>;
   }

This is a common technique for generating template classes. The function template back_inserter() deduces the type parameter and uses it to construct the BackInserter object. Again, using back_inserter() is going to be just as fast as writing the loop out fully.

Separating the Template Interface from the Implementation

As with regular classes, with class templates, it is possible to separate the interface from the implementation. Here is a simple Point template class, separated into interface and implementation:

// point.h
template <class X>
  struct Point {
   X x,y;

   Point(int _x, int _y);
   void set(int _x, int _y);
  };

// point.cpp
template <class X>
  Point<X>:: Point(int _x, int _y)
   {  set(_x,_y); }

template <class X>
  void Point<X>::set(int _x, int _y)
  {  x = _x; y = _y; }

The member function definitions are templates, as you would expect, except that the class type (Point<X>) contains the dummy type. As with ordinary classes, the class body must have previously declared the method. However, currently most compilers have difficulty with the separate compilation of templates. So in practice, the definitions of the methods must be included directly as well.

Member Templates

Member templates are an interesting and occaisionally very useful feature of modern C++. Member functions can themselves be defined as function templates. This example is an updated version of the Buffer class template defined earlier. Note that the assign() method is itself a template:

...
template <class T, int N>
  class Buffer {
   T m_arr[N];
  public:
   template <class In>
     void assign(In start, In finish) {
       int i = 0;
       for(; start != finish; ++start) m_arr[i++] = *start;
     }
   Buffer()
   {  for(int i = 0; i < N; i++) m_arr[i] = 0; }

   int size()
   {  return N; }
   T& operator[] (int i)
   {  return m_arr[i]; }
 };
...
int main()
{
 int vals[] = { 23,43,56,22,22};
 Buffer<int,10> buff;
 buff.assign(vals,vals+5);
 cout << buff << endl;
// standard list<int> defines assign() as a member template!
list<int> ls;
 ls.assign(vals,vals+5);
 dump(ls);
}

23 43 56 22 22 0 0 0 0 0
23 43 56 22 22

The assign() method in fact looks rather like the standard algorithm copy(). It is also parameterized by some input iterator type; in the example it's used to copy an array of integers into the buffer, so the iterator type is int *. But you could use assign() with any valid input sequence.

The standard containers all have a method assign(), which is defined as a member template.