Writing Generic Code with Templates

template <typename T> class Grid

{

public:

// Omitted for brevity

friend ostream& operator<< <T>(ostream& ostr, const Grid<T>& grid); // Omitted for brevity

};

This friend declaration is tricky: you’re saying that, for an instance of the template with type T, the T instantiation of operator<< is a friend. In other words, there is a one-to-one mapping of friends

between the class instantiations and the function instantiations. Note particularly the explicit template specification <T> on operator<< (the space after operator<< is optional). This syntax tells the compiler that operator<< is itself a template. Some compilers fail to support this syntax, but it’s legal C++, and works on most new compilers.

Advanced Templates

The first half of this chapter covered the most widely used features of class and function templates. If you are interested in only a basic knowledge of templates so that you can use the STL or perhaps write your own simple classes, you can stop here. However, if templates interest you and you want to uncover their full power, read the second half of this chapter to learn about some of the more obscure, but fascinating, details.

More about Template Parameters

There are actually three kinds of template parameters: type, nontype and template template (no, you’re not seeing double: that really is the name!) You’ve seen examples of type and nontype parameters above, but not template template parameters yet. There are also some tricky aspects to both template and nontype parameters that were not covered above.

More about Template Type Parameters

Type parameters to templates are the main purpose of templates. You can declare as many type parameters as you want. For example, you could add to the grid template a second type parameter specifying another templatized class container on which to build the grid. Recall from Chapter 4 that the standard template library defines several templatized container classes, including vector and deque. In your original grid class you might want to have an array of vectors or an array of deques instead of just an array of arrays. With another template type parameter, you can allow the user to specify whether she wants the underlying container to be a vector or a deque. Here is the class definition with the additional template parameter:

template <typename T, typename Container> class Grid

{

public:

Grid(int inWidth = kDefaultWidth, int inHeight = kDefaultHeight); Grid(const Grid<T, Container>& src);

~Grid();

299

Chapter 11

Grid<T, Container>& operator=(const Grid<T, Container>& rhs); void setElementAt(int x, int y, const T& inElem);

T& getElementAt(int x, int y);

const T& getElementAt(int x, int y) const; int getHeight() const { return mHeight; } int getWidth() const { return mWidth; } static const int kDefaultWidth = 10; static const int kDefaultHeight = 10;

protected:

void copyFrom(const Grid<T, Container>& src);

Container* mCells; int mWidth, mHeight;

};

This template now has two parameters: T and Container. Thus, wherever you previously referred to Grid<T> you must refer to Grid<T, Container> to specify both template parameters. The only other change is that mCells is now a pointer to a dynamically allocated array of Containers instead of a pointer to a dynamically allocated two-dimensional array of T elements.

Here is the constructor definition. It assumes that the Container type has a resize() method. If you try to instantiate this template by specifying a type that has no resize() method, the compiler will generate an error, as described below.

template <typename T, typename Container>

Grid<T, Container>::Grid(int inWidth, int inHeight) : mWidth(inWidth), mHeight(inHeight)

{

// Dynamically allocate the array of mWidth containers mCells = new Container[mWidth];

for (int i = 0; i < mWidth; i++) {

// Resize each container so that it can hold mHeight elements. mCells[i].resize(mHeight);

}

}

Here is the destructor definition. There’s only one call to new in the constructor, so only one call to delete in the destructor.

template <typename T, typename Container> Grid<T, Container>::~Grid()

{

delete [] mCells;

}

The code in copyFrom() assumes that you can access elements in the container using array [] notation. Chapter 16 explains how to overload the [] operator to implement this feature in your own container classes, but for now, it’s enough to know that the vector and deque from the STL both support this syntax.

template <typename T, typename Container>

void Grid<T, Container>::copyFrom(const Grid<T, Container>& src)

{

int i, j;

mWidth = src.mWidth; mHeight = src.mHeight;

300

Writing Generic Code with Templates

mCells = new Container[mWidth]; for (i = 0; i < mWidth; i++) {

// Resize each element, as in the constructor. mCells[i].resize(mHeight);

}

for (i = 0; i < mWidth; i++) {

for (j = 0; j < mHeight; j++) { mCells[i][j] = src.mCells[i][j];

}

}

}

Here are the implementations of the remaining methods.

template <typename T, typename Container>

Grid<T, Container>::Grid(const Grid<T, Container>& src)

{

copyFrom(src);

}

template <typename T, typename Container>

Grid<T, Container>& Grid<T, Container>::operator=(const Grid<T, Container>& rhs)

{

//Check for self-assignment. if (this == &rhs) {

return (*this);

}

//Free the old memory. delete [] mCells;

//Copy the new memory. copyFrom(rhs);

return (*this);

}

template <typename T, typename Container>

void Grid<T, Container>::setElementAt(int x, int y, const T& inElem)

{

mCells[x][y] = inElem;

}

template <typename T, typename Container>

T& Grid<T, Container>::getElementAt(int x, int y)

{

return (mCells[x][y]);

}

template <typename T, typename Container>

const T& Grid<T, Container>::getElementAt(int x, int y) const

{

return (mCells[x][y]);

}

301

Chapter 11

Now you can instantiate and use grid objects like this:

Grid<int, vector<int> > myIntGrid;

Grid<int, deque<int> > myIntGrid2;

myIntGrid.setElementAt(3, 4, 5);

cout << myIntGrid.getElementAt(3, 4);

Grid<int, vector<int> > grid2(myIntGrid); grid2 = myIntGrid;

The use of the word Container for the parameter name doesn’t mean that the type really must be a container. You could try to instantiate the Grid class with an int instead:

Grid<int, int> test; // WILL NOT COMPILE

This line will not compile, but it might not give you the error you expect. It won’t complain that the second type argument is an int instead of a container. Instead it will tell you that left of ‘.resize’ must have class/struct/union type. That’s because the compiler attempts to generate a Grid class with int as the Container. Everything works fine until it tries to compile this line:

mCells[i].resize(mHeight);

At that point, the compiler realizes that mCells[i] is an int, so you can’t call the resize() method on it!

This approach may seem convoluted and useless to you. However, it arises in the standard template library. The stack, queue, and priority_queue class templates all take a template type parameter specifying the underlying container, which can be a vector, deque, or list.

Default Values for Template Type Parameters

You can give template parameters default values. For example, you might want to say that the default container for your Grid is a vector. The template class definition would look like this:

#include <vector> using std::vector;

template <typename T, typename Container = vector<T> > class Grid

{

public:

// Everything else is the same as before.

};

You can use the type T from the first template parameter as the argument to the vector template in the default value for the second template parameter. Note also that you must leave a space between the two closing angle brackets to avoid the parsing problem discussed earlier in the chapter.

C++ syntax requires that you do not repeat the default value in the template header line for method definitions.

302

Writing Generic Code with Templates

With this default parameter, clients can now instantiate a grid with or without specifying an underlying container:

Grid<int, vector<int> > myIntGrid;

Grid<int> myIntGrid2;

Introducing Template Template Parameters

There is one problem with the Container parameter in the previous section. When you instantiate the class template, you write something like this:

Grid<int, vector<int> > myIntGrid;

Note the repetition of the int type. You must specify that it’s the element type both of the Grid and of the vector. What if you wrote this instead?

Grid<int, vector<SpreadsheetCell> > myIntGrid;

That wouldn’t work very well! It would be nice to be able to write the following, so that you couldn’t make that mistake:

Grid<int, vector> myIntGrid;

The Grid class should be able to figure out that it wants a vector of ints. The compiler won’t allow you to pass that argument to a normal type parameter, though, because vector by itself is not a type, but a template.

If you want to take a template as a template parameter, you must use a special kind of parameter called a template template parameter. The syntax is crazy, and some compilers don’t yet support it. However, if you’re still interested, read on.

Specifying a template template parameter is sort of like specifying a function pointer parameter in a normal function. Function pointer types include the return type and parameter types of a function. Similarly, when you specify a template template parameter, the full specification of the template template parameter includes the parameters to that template.

Containers in the STL have a template parameter list that looks something like this:

template <typename E, typename Allocator = allocator<E> > class vector

{

// Vector definition

};

The E parameter is simply the element type. Don’t worry about the Allocator for now — it’s covered in Chapter 21.

303

Chapter 11

Given the above template specification, here is the template class definition for the Grid class that takes a container template as its second template parameter:

template <typename T, template <typename E, typename Allocator = allocator<E> >

class Container = vector > class Grid

{

public:

//Omitted code that is the same as before Container<T>* mCells;

//Omitted code that is the same as before

};

What is going on here? The first template parameter is the same as before: the element type T. The second template parameter is now a template itself for a container such as vector or deque. As you saw earlier, this “template type” must take two parameters: an element type E and an allocator Allocator. Note the repetition of the word class after the nested template parameter list. The name of this parameter in the Grid template is Container (as before). The default value is now vector, instead of vector<T>, because the Container is a template instead of an actual type.

The syntax rule for a template template parameter more generically is this:

template <other params, ..., template <TemplateTypeParams> class ParameterName,

other params, ...>

Now that you’ve suffered through the above syntax to declare the template, the rest is easy. Instead of using Container by itself in the code, you must specify Container<T> as the container type you use. For example, the constructor now looks like this (you don’t repeat the default template template parameter argument in the template specification for the method definition):

template <typename T, template <typename E, typename Allocator = allocator<E> >

class Container>

Grid<T, Container>::Grid(int inWidth, int inHeight) : mWidth(inWidth), mHeight(inHeight)

{

mCells = new Container<T>[mWidth]; for (int i = 0; i < mWidth; i++) { mCells[i].resize(mHeight);

}

}

After implementing all the methods, you can use the template like this:

Grid<int, vector> myGrid;

myGrid.setElementAt(1, 2, 3); myGrid.getElementAt(1,2); Grid<int, vector> myGrid2(myGrid);

If you haven’t skipped this section entirely, you’re surely thinking at this point that C++ deserves every criticism that’s ever been thrown at it. Try not to bog down in the syntax here, and keep the main concept in mind: you can pass templates as parameters to other templates.

304

Writing Generic Code with Templates

More about Nontype Template Parameters

You might want to allow the user to specify an empty(not in the literal sense) element that is used to initialize each cell in the grid. Here is a perfectly reasonable approach to implement this goal:

template <typename T, const T EMPTY> class Grid

{

public:

Grid(int inWidth = kDefaultWidth, int inHeight = kDefaultHeight); Grid(const Grid<T, EMPTY>& src);

~Grid();

Grid<T, EMPTY>& operator=(const Grid<T, EMPTY>& rhs);

// Omitted for brevity

protected:

void copyFrom(const Grid<T, EMPTY>& src); T** mCells;

int mWidth, mHeight;

};

This definition is legal. You can use the type T from the first parameter as the type for the second parameter and nontype parameters can be const just like function parameters. You can use this initial value for T to initialize each cell in the grid:

template <typename T, const T EMPTY>

Grid<T, EMPTY>::Grid(int inWidth, int inHeight) : mWidth(inWidth), mHeight(inHeight)

{

mCells = new T* [mWidth];

for (int i = 0; i < mWidth; i++) { mCells[i] = new T[mHeight];

for (int j = 0; j < mHeight; j++) { mCells[i][j] = EMPTY;

}

}

}

The other method definitions stay the same, except that you must add the second type parameter to the template lines, and all the instances of Grid<T> become Grid<T, EMPTY>. After making those changes, you can then instantiate an int Grid with an initial value for all the elements:

Grid<int, 0> myIntGrid;

Grid<int, 10> myIntGrid2;

The initial value can be any integer you want. However, suppose that you try to create a

SpreasheetCell Grid:

SpreadsheetCell emptyCell;

Grid<SpreadsheetCell, emptyCell> mySpreadsheet; // WILL NOT COMPILE

That line leads to a compiler error because you cannot pass objects as arguments to nontype parameters.

305

Chapter 11

Nontype parameters cannot be objects, or even doubles or floats. They are restricted only to ints, enums, pointers, and references.

This example illustrates one of the vagaries of template classes: they can work correctly on one type but fail to compile for another type.

Reference and Pointer Nontype Template Parameters

A more comprehensive way of allowing the user to specify an initial empty element for the grid uses a reference to a T as the nontype template parameter. Here is the new class definition:

template <typename T, const T& EMPTY> class Grid

{

//Everything else is the same as the previous example, except the

//template lines in the method definitions specify const T& EMPTY

//instead of const T EMPTY.

};

Now you can instantiate this template class for any type. However, the reference you pass as the second template argument must refer to a global variable with external linkage. External linkage can be thought of as the opposite of static linkage, and just means that the variable is available in source files outside the one in which it is defined. See Chapter 12 for more details. For now, it suffices to know that you can declare that a variable has external linkage with the extern keyword:

extern const int x = 0;

Note that this line occurs outside of any function or method body. Here is a full program that declares int and SpreadsheetCell grids with initialization parameters:

#include “GridRefNonType.h” #include “SpreadsheetCell.h”

extern const int emptyInt = 0;

extern const SpreadsheetCell emptyCell(0);

int main(int argc, char** argv)

{

Grid<int, emptyInt> myIntGrid; Grid<SpreadsheetCell, emptyCell> mySpreadsheet;

Grid<int, emptyInt> myIntGrid2(myIntGrid);

return (0);

}

Reference and pointer template arguments must refer to global variables that are available from all translation units. The technical term for these types of variables is data with external linkage.

306