Writing Generic Code with Templates

template <typename T>

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

{

mCells[x][y] = *inElem;

}

template <typename T>

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

{

T* newElem = new T(mCells[x][y]); return (newElem);

}

Emulating Function Partial Specialization with Overloading

The C++ standard does not permit partial template specialization of functions. Instead, you can overload the function with another template. The difference is subtle. Suppose that you want to write a specialization of the Find() function, presented earlier in this chapter, that dereferences the pointers to use operator== directly on the objects pointed to. Following the syntax for class template partical specialization, you might be tempted to write this:

template <typename T>

int Find<T*>(T*& value, T** arr, int size)

{

for (int i = 0; i < size; i++) { if (*arr[i] == *value) {

// Found it; return the index

return (i);

}

}

// Failed to Find it; return -1 return (-1);

}

However, that syntax declares a partial specialization of the function template, which the C++ standard does not allow (although some compilers support it). The standard way to implement the behavior you want is to write a new template for Find():

template <typename T>

int Find(T*& value, T** arr, int size)

{

for (int i = 0; i < size; i++) { if (*arr[i] == *value) {

// Found it; return the index return (i);

}

}

// Failed to Find it; return -1 return (-1);

}

The difference might seem trivial and academic, but it makes the difference between portable, standard, code and code that probably won’t compile.

313

Chapter 11

More on Deduction

You can define in one program the original Find() template, the overloaded Find() for partial specialization on pointer types, the complete specialization for char*s, and the overloaded Find() just for char*s. The compiler will choose the appropriate version to call based on its deduction rules.

The compiler always chooses the “most specific” version of the function, with nontemplate versions being preferred over template versions.

The following code calls the specified versions of Find():

char* word = “two”;

char* arr[4] = {“one”, “two”, “three”, “four”}; int res;

int x = 3, intArr[4] = {1, 2, 3, 4};

double d1 = 5.6, dArr[4] = {1.2, 3.4, 5.7, 7.5};

res = Find(x, intArr, 4); // Calls Find<int> by deduction res = Find<int>(x, intArr, 4); // Call Find<int> explicitly

res = Find(d1, dArr, 4); // Call Find<double> by deduction

res = Find<double>(d1, dArr, 4); // Calls Find<double> explicitly

res = Find<char *>(word, arr, 4); // Calls template specialization for char*s

res = Find(word, arr, 4); // Calls the overloaded Find for char *s

int *px = &x, *pArr[2] = {&x, &x};

res = Find(px, pArr, 2); // Calls the overloaded Find for pointers

SpreadsheetCell c1(10), c2[2] = {SpreadsheetCell(4), SpreadsheetCell(10)};

res = Find(c1, c2, 2); // Calls Find<SpreadsheetCell> by deduction res = Find<SpreadsheetCell>(c1, c2, 2); // Calls Find<SpreadsheetCell>

// explicitly

SpreadsheetCell *pc1 = &c1; SpreadsheetCell *psa[2] = {&c1, &c1};

res = Find(pc1, psa, 2); // Calls the overloaded Find for pointers

Template Recursion

Templates in C++ provide capabilities that go far beyond the simple classes and functions you have seen so far in this chapter. One of these capabilities is template recursion. This section first provides a motivation for template recursion, and then shows how to implement it.

This section employs some operator overloading features discussed in Chapter 16. If you are unfamiliar with the syntax for overloading operator[], consult that chapter before continuing.

314

Writing Generic Code with Templates

An N-Dimensional Grid: First Attempt

The Grid template example earlier in this chapter supports only two dimensions, which limits its usefulness. What if you wanted to write a 3-D Tic-Tac-Toe game or write a math program with four-dimensional matrices? You could, of course, write a template or nontemplate class for each of those dimensions. However, that would repeat a lot of code. Another approach is to write only a single-dimensional grid. Then, you could create a Grid of any dimension by instantiating the Grid with another Grid as its element type. This Grid element type could itself be instantiated with a Grid as its element type, and so on. Here is the implementation of the OneDGrid class template. It’s simply a one-dimensional version of the Grid template from the earlier examples, with the addition of a resize() method, and the substitution of operator[] for setElementAt() and getElementAt(). Production code, of course, would do bounds-checking on the array access, and would throw an exception if something were amiss.

template <typename T> class OneDGrid

{

public:

OneDGrid(int inSize = kDefaultSize); OneDGrid(const OneDGrid<T>& src); ~OneDGrid();

OneDGrid<T> &operator=(const OneDGrid<T>& rhs); void resize(int newSize);

T& operator[](int x);

const T& operator[](int x) const; int getSize() const { return mSize; } static const int kDefaultSize = 10;

protected:

void copyFrom(const OneDGrid<T>& src); T* mElems;

int mSize;

};

template <typename T>

const int OneDGrid<T>::kDefaultSize;

template <typename T>

OneDGrid<T>::OneDGrid(int inSize) : mSize(inSize)

{

mElems = new T[mSize];

}

template <typename T> OneDGrid<T>::OneDGrid(const OneDGrid<T>& src)

{

copyFrom(src);

}

315

Chapter 11

template <typename T> OneDGrid<T>::~OneDGrid()

{

delete [] mElems;

}

template <typename T>

void OneDGrid<T>::copyFrom(const OneDGrid<T>& src)

{

mSize = src.mSize; mElems = new T[mSize];

for (int i = 0; i < mSize; i++) { mElems[i] = src.mElems[i];

}

}

template <typename T>

OneDGrid<T>& OneDGrid<T>::operator=(const OneDGrid<T>& rhs)

{

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

return (*this);

}

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

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

return (*this);

}

template <typename T>

void OneDGrid<T>::resize(int newSize)

{

T* newElems = new T[newSize]; // Allocate the new array of the new size

// Handle the new size being smaller or bigger than the old size. for (int i = 0; i < newSize && i < mSize; i++) {

// Copy the elements from the old array to the new one. newElems[i] = mElems[i];

}

mSize = newSize; // Store the new size.

delete [] mElems; // Free the memory for the old array. mElems = newElems; // Store the pointer to the new array.

}

template <typename T>

T& OneDGrid<T>::operator[](int x)

{

return (mElems[x]);

}

316

Writing Generic Code with Templates

template <typename T>

const T& OneDGrid<T>::operator[](int x) const

{

return (mElems[x]);

}

With this implementation of the OneDGrid, you can create multidimensional grids like this:

OneDGrid<int> singleDGrid;

OneDGrid<OneDGrid<int> > twoDGrid;

OneDGrid<OneDGrid<OneDGrid<int> > > threeDGrid;

singleDGrid[3] = 5; twoDGrid[3][3] = 5; threeDGrid[3][3][3] = 5;

This code works fine, but the declarations are messy. We can do better.

A Real N-Dimensional Grid

You can use template recursion to write a “real” N-dimensional grid because dimensionality of grids is essentially recursive. You can see that in this declaration:

OneDGrid<OneDGrid<OneDGrid<int> > > threeDGrid;

You can think of each nesting OneDGrid as a recursive step, with the OneDGrid of int as the base case. In other words, a three-dimensional grid is a single-dimensional grid of single-dimensional grids of single-dimensional grids of ints. Instead of requiring the user to do this recursion, you can write a template class that does it for you. Then, you can create N-dimensional grids like this:

NDGrid<int, 1> singleDGrid;

NDGrid<int, 2> twoDGrid;

NDGrid<int, 3> threeDGrid;

The NDGrid template class takes a type for its element and an integer specifying its “dimensionality.” The key insight here is that the element type of the NDGrid is not the element type specified in the template parameter list, but is in fact another NDGrid of dimensionality one less than the current. In other words, a three-dimensional grid is an array of two-dimensional grids; the two-dimensional grids are each arrays of one-dimensional grids.

With recursion, you need a base case. You can write a partial specialization of the NDGrid for dimensionality of 1, in which the element type is not another NDGrid, but is in fact the element type specified by the template parameter.

Here is the general NDGrid template definition, with highlights showing where it differs from the OneDGrid shown above:

template <typename T, int N>

class NDGrid

{

public:

317

Chapter 11

NDGrid(); NDGrid(int inSize);

NDGrid(const NDGrid<T, N>& src); ~NDGrid();

NDGrid<T, N>& operator=(const NDGrid<T, N>& rhs); void resize(int newSize);

NDGrid<T, N-1>& operator[](int x);

const NDGrid<T, N-1>& operator[](int x) const; int getSize() const { return mSize; }

static const int kDefaultSize = 10; protected:

void copyFrom(const NDGrid<T, N>& src);

NDGrid<T, N-1>* mElems; int mSize;

};

Note that mElems is a pointer to an NDGrid<T, N-1>: this is the recursive step. Also, operator[] returns a reference to the element type, which is again NDGrid<T, N-1>, not T.

Here is the template definition for the base case:

template <typename T>

class NDGrid<T, 1>

{

public:

NDGrid(int inSize = kDefaultSize); NDGrid(const NDGrid<T, 1>& src); ~NDGrid();

NDGrid<T, 1>& operator=(const NDGrid<T, 1>& rhs); void resize(int newSize);

T& operator[](int x);

const T& operator[](int x) const; int getSize() const { return mSize; } static const int kDefaultSize = 10;

protected:

void copyFrom(const NDGrid<T, 1>& src);

T* mElems; int mSize;

};

Here the recursion ends: the element type is T, not another template instantiation.

The trickiest aspect of the implementations, other than the template recursion itself, is appropriately sizing each dimension of the array. This implementation creates the N-dimensional array with every dimension of equal size. It’s significantly more difficult to specify a separate size for each dimension. However, even with this simplification, there is still a problem: the user should have the ability to create the array with a specified size, such as 20 or 50. Thus, one constructor takes an integer size parameter. However, when you dynamically allocate the nested array of grids, you cannot pass this size value on to the grids because arrays create objects using their default constructor. Thus, you must explicitly call resize() on each grid element of the array. That code follows, with the default and one-argument constructors separated for clarity.

318

Writing Generic Code with Templates

The base case doesn’t need to resize its elements because the elements are Ts, not grids.

Here are the implementations of the main NDGrid template, with highlights showing the differences from the OneDGrid:

template <typename T, int N>

const int NDGrid<T, N>::kDefaultSize;

template <typename T, int N>

NDGrid<T, N>::NDGrid(int inSize) : mSize(inSize)

{

mElems = new NDGrid<T, N-1>[mSize];

//Allocating the array above calls the 0-argument

//constructor for the NDGrid<T, N-1>, which constructs

//it with the default size. Thus, we must explicitly call

//resize() on each of the elements.

for (int i = 0; i < mSize; i++) { mElems[i].resize(inSize);

}

}

template <typename T, int N>

NDGrid<T, N>::NDGrid() : mSize(kDefaultSize)

{

mElems = new NDGrid<T, N-1>[mSize];

}

template <typename T, int N>

NDGrid<T, N>::NDGrid(const NDGrid<T, N>& src)

{

copyFrom(src);

}

template <typename T, int N>

NDGrid<T, N>::~NDGrid()

{

delete [] mElems;

}

template <typename T, int N>

void NDGrid<T, N>::copyFrom(const NDGrid<T, N>& src)

{

mSize = src.mSize;

mElems = new NDGrid<T, N-1>[mSize]; for (int i = 0; i < mSize; i++) { mElems[i] = src.mElems[i];

}

}

template <typename T, int N>

NDGrid<T, N>& NDGrid<T, N>::operator=(const NDGrid<T, N>& rhs)

319

Chapter 11

{

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

return (*this);

}

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

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

return (*this);

}

template <typename T, int N>

void NDGrid<T, N>::resize(int newSize)

{

// Allocate the new array with the new size.

NDGrid<T, N - 1>* newElems = new NDGrid<T, N - 1>[newSize];

//Copy all the elements, handling the cases where newSize is

//larger than mSize and smaller than mSize.

for (int i = 0; i < newSize && i < mSize; i++) { newElems[i] = mElems[i];

// Resize the nested Grid elements recursively.

newElems[i].resize(newSize);

}

//Store the new size and pointer to the new array.

//Free the memory for the old array first.

mSize = newSize; delete [] mElems; mElems = newElems;

}

template <typename T, int N>

NDGrid<T, N-1>& NDGrid<T, N>::operator[](int x)

{

return (mElems[x]);

}

template <typename T, int N>

const NDGrid<T, N-1>& NDGrid<T, N>::operator[](int x) const

{

return (mElems[x]);

}

Here are the implementations of the partial specialization (base case). Note that you must rewrite a lot of the code because you don’t inherit any implementations with specializations. Highlights show the differences from the nonspecialized NDGrid.

template <typename T>

const int NDGrid<T, 1>::kDefaultSize;

template <typename T>

NDGrid<T, 1>::NDGrid(int inSize) : mSize(inSize)

{

mElems = new T[mSize];

}

320

Writing Generic Code with Templates

template <typename T>

NDGrid<T, 1>::NDGrid(const NDGrid<T, 1>& src)

{

copyFrom(src);

}

template <typename T>

NDGrid<T, 1>::~NDGrid()

{

delete [] mElems;

}

template <typename T>

void NDGrid<T, 1>::copyFrom(const NDGrid<T, 1>& src)

{

mSize = src.mSize; mElems = new T[mSize];

for (int i = 0; i < mSize; i++) { mElems[i] = src.mElems[i];

}

}

template <typename T>

NDGrid<T, 1>& NDGrid<T, 1>::operator=(const NDGrid<T, 1>& rhs)

{

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

return (*this);

}

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

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

return (*this);

}

template <typename T>

void NDGrid<T, 1>::resize(int newSize)

{

T* newElems = new T[newSize];

for (int i = 0;	i	< newSize	&& i < mSize; i++) {
newElems[i]	=	mElems[i];
// Don’t need		to resize	recursively, because this is the base case.

}

mSize = newSize; delete [] mElems; mElems = newElems;

}

template <typename T>

T& NDGrid<T, 1>::operator[](int x)

{

return (mElems[x]);

}

321

Chapter 11

template <typename T>

const T& NDGrid<T, 1>::operator[](int x) const

{

return (mElems[x]);

}

Now, you can write code like this:

NDGrid<int, 3> my3DGrid; my3DGrid[2][1][2] = 5; my3DGrid[1][1][1] = 5;

cout << my3DGrid[2][1][2] << endl;

Summar y

This chapter taught you how to use templates for generic programming. We hope that you gained an appreciation for the power and capabilities of these features, and an idea of how you could apply these concepts to your own code. Don’t worry if you didn’t understand all the syntax, or follow all the examples, on your first reading. The concepts can be difficult to grasp when you are first exposed to them, and the syntax is so tricky that the authors of this book consult a reference whenever they want to write templates. When you actually sit down to write a template class or function, you can consult this chapter for a reference on the proper syntax.

This chapter is the main preparation for Chapters 21, 22, and 23 on the standard template library. You can skip straight to Chapters 21 to 23 if you want to read about the STL immediately, but we recommend reading the rest of the chapters in Parts II and III first.

322