Chapter 19

Writing Generic Code with Templates

WHAT’S IN THIS CHAPTER?

• How to write template classes
• How the compiler processes templates
• How to organize template source code
• How to use non-type template parameters
• How to write templates of individual class methods
• How to write customizations of your class templates for specific types
• How to combine templates and inheritance
• How to write function templates
• How to make template functions friends of template classes
• How to write template aliases

C++ provides language support not only for object-oriented programming, but also for generic programming. As discussed in Chapter 4, the goal of generic programming is to write reusable code. The fundamental tools for generic programming in C++ are templates. Although not strictly an object-oriented feature, templates can be combined with object-oriented programming for powerful results. Many programmers consider templates to be the most difficult part of C++ and, for that reason, tend to avoid them.

This chapter provides the code details for fulfilling the design principle of generality discussed in Chapter 4 and used during the discussion of the standard template library in Chapters 11 through 17.

The next chapter delves into some of the more advanced template features, including:

• The three kinds of template parameters and their subtleties
• Partial specialization
• Function template deduction
• How to exploit template recursion
• Variadic templates
• Metaprogramming

OVERVIEW OF TEMPLATES

The main programming unit in the procedural paradigm is the procedure or function. Functions are useful primarily because they allow you to write algorithms that are independent of specific values and can thus be reused for many different values. For example, the sqrt() function in C and C++ calculates the square root of a value supplied by the caller. A square root function that calculated only the square root of one number, like four, would not be particularly useful! The sqrt() function is written in terms of a parameter, which is a stand-in for whatever value the caller passes. Computer scientists say that functions parameterize values.

The object-oriented programming paradigm adds the concept of objects, which group related data and behaviors, but does not change the way functions and methods parameterize values.

Templates take the concept of parameterization a step further to allow you to parameterize on types as well as values. Types in C++ include primitives such as int and double, as well as user-defined classes such as SpreadsheetCell and CherryTree. With templates you can write code that is independent not only of the values it will be given, but also of the types of those values. For example, instead of writing separate stack classes to store ints, Cars, and SpreadsheetCells, you can write one stack class definition that can be used for any of those types.

Although templates are an amazing language feature, templates in C++ are syntactically confusing, and many programmers overlook or avoid them.

This chapter will teach you about template support in C++ with an emphasis on the aspects that arise in the STL. Along the way, you will learn about some nifty features that you can employ in your programs aside from using the standard library.

CLASS TEMPLATES

Class templates define a class where the types of some of the variables, methods and/or parameters to the methods are specified as parameters. Class templates are useful primarily for containers, or data structures, that store objects. This section uses a running example of a Grid container. In order to keep the examples reasonable in length and simple enough to illustrate specific points, different sections of the chapter will add features to the Grid container that are not used in subsequent sections.

Writing a Class Template

Suppose that you want a generic game board class that you can use as a chessboard, checkers board, Tic-Tac-Toe board, or any other two-dimensional game board. In order to make it general-purpose, you should be able to store chess pieces, checkers pieces, Tic-Tac-Toe pieces, or any type of game piece.

Coding without Templates

Without templates, the best approach to build a generic game board is to employ polymorphism to store generic GamePiece objects. Then, you could subclass the pieces for each game from the GamePiece class. For example, in the chess game, the ChessPiece would be a subclass of GamePiece. Through polymorphism, the GameBoard, written to store GamePieces, can also store ChessPieces. Your class definition might look similar to the Spreadsheet class from Chapter 7, which used a dynamically allocated two-dimensional array as the underlying grid structure:

class GameBoard
{
    public:
        // The general-purpose GameBoard allows the user to specify its dimensions
        GameBoard(size_t inWidth = kDefaultWidth,
                  size_t inHeight = kDefaultHeight);
        GameBoard(const GameBoard& src); // Copy constructor
        virtual ~GameBoard();
        GameBoard& operator=(const GameBoard& rhs); // Assignment operator
        void setPieceAt(size_t x, size_t y, const GamePiece& inPiece);
        GamePiece& getPieceAt(size_t x, size_t y);
        const GamePiece& getPieceAt(size_t x, size_t y) const;
        size_t getHeight() const { return mHeight; }
        size_t getWidth() const { return mWidth; }
        static const size_t kDefaultWidth = 10;
        static const size_t kDefaultHeight = 10;
    protected:
        void copyFrom(const GameBoard& src);
        // Objects dynamically allocate space for the game pieces.
        GamePiece** mCells;
        size_t mWidth, mHeight;
};

Code snippet from GameBoardGameBoard.h

getPieceAt() returns a reference to the piece at a specified spot instead of a copy of the piece. The GameBoard serves as an abstraction of a two-dimensional array, so it should provide array access semantics by giving the actual object at an index, not a copy of the object. Returning a reference from getPieceAt() works perfectly in this example. However, you should be careful when you write a method that returns something by reference, to make sure the reference stays valid. For example, if the GameBoard class would support a resize() method, this method would reallocate memory for mCells. By doing this, all references previously returned from getPieceAt() would become invalid. So, client code should not store such a reference for future use, but should call getPieceAt() right before using the returned reference.

This implementation of the class provides two versions of getPieceAt(), one of which returns a reference and one of which returns a const reference.

Here are the method definitions. The implementation is almost identical to the Spreadsheet class from Chapter 7. Production code would, of course, perform bounds checking in setPieceAt() and getPieceAt(). That code is omitted because it is not the point of this chapter:

GameBoard::GameBoard(size_t inWidth, size_t inHeight) :
    mWidth(inWidth), mHeight(inHeight)
{
    mCells = new GamePiece* [mWidth];
    for (size_t i = 0; i < mWidth; i++) {
        mCells[i] = new GamePiece[mHeight];
    }
}
GameBoard::GameBoard(const GameBoard& src)
{
    copyFrom(src);
}
GameBoard::~GameBoard()
{
    // Free the old memory
    for (size_t i = 0; i < mWidth; i++) {
        delete [] mCells[i];
    }
    delete [] mCells;
    mCells = nullptr;
}
void GameBoard::copyFrom(const GameBoard& src)
{
    mWidth = src.mWidth;
    mHeight = src.mHeight;
    mCells = new GamePiece* [mWidth];
    for (size_t i = 0; i < mWidth; i++) {
        mCells[i] = new GamePiece[mHeight];
    }
    for (size_t i = 0; i < mWidth; i++) {
        for (size_t j = 0; j < mHeight; j++) {
            mCells[i][j] = src.mCells[i][j];
        }
    }
}
GameBoard& GameBoard::operator=(const GameBoard& rhs)
{
    // Check for self-assignment
    if (this == &rhs) {
        return *this;
    }
    // Free the old memory
    for (size_t i = 0; i < mWidth; i++) {
        delete [] mCells[i];
    }
    delete [] mCells;
    mCells = nullptr;
    // Copy the new memory
    copyFrom(rhs);
    return *this;
}
void GameBoard::setPieceAt(size_t x, size_t y, const GamePiece& inElem)
{
    mCells[x][y] = inElem;
}
GamePiece& GameBoard::getPieceAt(size_t x, size_t y)
{
    return mCells[x][y];
}
const GamePiece& GameBoard::getPieceAt(size_t x, size_t y) const
{
    return mCells[x][y];
}

Code snippet from GameBoardGameBoard.cpp

This GameBoard class works pretty well. Assuming that you wrote a ChessPiece class, you can create GameBoard objects and use them like this:

GameBoard chessBoard(8, 8);
ChessPiece pawn;
chessBoard.setPieceAt(0, 0, pawn);

A Template Grid Class

The GameBoard class in the previous section is nice, but insufficient. For example, it’s quite similar to the Spreadsheet class from Chapter 7, but the only way you could use it as a spreadsheet would be to make the SpreadsheetCell class a subclass of GamePiece. That doesn’t make sense because it doesn’t fulfill the is-a principle of inheritance: A SpreadsheetCell is not a GamePiece. It would be nice if you could write a generic Grid class that you could use for purposes as diverse as a Spreadsheet or a ChessBoard. In C++, you can do this by writing a class template, which allows you to write a class without specifying one or more types. Clients then instantiate the template by specifying the types they want to use.

The Grid Class Definition

In order to understand class templates, it is helpful to examine the syntax. The following example shows how you can tweak your GameBoard class slightly to make a templatized Grid class. Don’t let the syntax scare you — it’s all explained following the code. Note that the class name has changed from GameBoard to Grid, and setPieceAt() and getPieceAt() have changed to setElementAt() and getElementAt() to reflect the class’ more generic nature:

template <typename T>
class Grid
{
    public:
        Grid(size_t inWidth = kDefaultWidth, size_t inHeight = kDefaultHeight);
       Grid(const Grid<T>& src);
        virtual ~Grid();
       Grid<T>& operator=(const Grid<T>& rhs);
       void setElementAt(size_t x, size_t y, const T& inElem);
       T& getElementAt(size_t x, size_t y);
       const T& getElementAt(size_t x, size_t y) const;
        size_t getHeight() const { return mHeight; }
        size_t getWidth() const { return mWidth; }
        static const size_t kDefaultWidth = 10;
        static const size_t kDefaultHeight = 10;
    protected:
       void copyFrom(const Grid<T>& src);
       T** mCells;
        size_t mWidth, mHeight;
};

Code snippet from GridGrid.h

Now that you’ve seen the full class definition, take another look at it, one line at a time:

template <typename T>

This first line says that the following class definition is a template on one type. Both template and typename are keywords in C++. As discussed earlier, templates “parameterize” types the same way that functions “parameterize” values. Just as you use parameter names in functions to represent the arguments that the caller will pass, you use type names (such as T) in templates to represent the types that the caller will specify. There’s nothing special about the name T — you can use whatever name you want. Traditionally, when a single type is used, it is called T, but that’s just a historical convention, like calling the integer that indexes an array i or j.

For historical reasons, you can use the keyword class instead of typename to specify template type parameters. Thus, many books and existing programs use syntax like this: template <class T>. However, the use of the word “class” in this context is confusing because it implies that the type must be a class, which is not true. The type can be a class, a struct, a union, a primitive type of the language like int or double, and so on.

The template specifier holds for the entire statement, which in this case is the class definition.

Several lines further, the copy constructor looks like this:

Grid(const Grid<T>& src);

As you can see, the type of the src parameter is no longer a const Grid&, but a const Grid<T>&. When you write a class template, what you used to think of as the class name (Grid) is actually the template name. When you want to talk about actual Grid classes or types, you discuss them as instantiations of the Grid class template for a certain type, such as int, SpreadsheetCell, or ChessPiece. At the point where you define the template, you haven’t specified the type it will be instantiated for, so you must use a stand-in template parameter, T, for whatever type might be used later. Thus, when you need to refer to a type for a Grid object as a parameter to, or return value from, a method you must use Grid<T>. You can also see this change with the parameter to, and return value from, the assignment operator, and the parameter to the copyFrom() method.

Within a class definition, the compiler will interpret Grid as Grid<T> where needed. However, it’s best to get in the habit of specifying Grid<T> explicitly because that’s the syntax you use outside the class to refer to types generated from the template. Only for constructors and the destructor, you should use Grid and not Grid<T>.

The final change to the class is that methods such as setElementAt() and getElementAt() now take and return parameters and values of type T instead of type GamePiece:

void setElementAt(size_t x, size_t y, const T& inElem);
T& getElementAt(size_t x, size_t y);
const T& getElementAt(size_t x, size_t y) const;

This type T is a placeholder for whatever type the user specifies. mCells is now a T** instead of a GamePiece** because it will point to a dynamically allocated two-dimensional array of Ts, for whatever type T the user specifies.

The Grid Class Method Definitions

The template <typename T> specifier must precede each method definition for the Grid template. The constructor looks like this:

template <typename T>
Grid<T>::Grid(size_t inWidth, size_t inHeight) : mWidth(inWidth), mHeight(inHeight)
{
    mCells = new T* [mWidth];
    for (size_t i = 0; i < mWidth; i++) {
        mCells[i] = new T[mHeight];
    }
}

Code snippet from GridGrid.h

Templates require you to put the implementation of the methods in the header file itself, because the compiler needs to know the complete definition including the definition of methods before it can create an instance of the template. This is discussed in more details later in this chapter.

Note that the class name before the :: is Grid<T>, not Grid. You must specify Grid<T> as the class name in all your methods and static data member definitions. The body of the constructor is identical to the GameBoard constructor except that the placeholder type T replaces the GamePiece type.

The rest of the method definitions are also similar to their equivalents in the GameBoard class with the exception of the appropriate template and Grid<T> syntax changes:

template <typename T>
Grid<T>::Grid(const Grid<T>& src)
{
    copyFrom(src);
}
template <typename T>
Grid<T>::~Grid()
{
    // Free the old memory.
    for (size_t i = 0; i < mWidth; i++) {
        delete [] mCells[i];
    }
    delete [] mCells;
    mCells = nullptr;
}
template <typename T>
void Grid<T>::copyFrom(const Grid<T>& src)
{
    mWidth = src.mWidth;
    mHeight = src.mHeight;
    mCells = new T* [mWidth];
    for (size_t i = 0; i < mWidth; i++) {
        mCells[i] = new T[mHeight];
    }
    for (size_t i = 0; i < mWidth; i++) {
        for (size_t j = 0; j < mHeight; j++) {
            mCells[i][j] = src.mCells[i][j];
        }
    }
}
template <typename T>
Grid<T>& Grid<T>::operator=(const Grid<T>& rhs)
{
    // Check for self-assignment.
    if (this == &rhs) {
        return *this;
    }
    // Free the old memory.
    for (size_t i = 0; i < mWidth; i++) {
        delete [] mCells[i];
    }
    delete [] mCells;
    mCells = nullptr;
    // Copy the new memory.
    copyFrom(rhs);
    return *this;
}
template <typename T>
void Grid<T>::setElementAt(size_t x, size_t y, const T& inElem)
{
    mCells[x][y] = inElem;
}
template <typename T>
T& Grid<T>::getElementAt(size_t x, size_t y)
{
    return mCells[x][y];
}
template <typename T>
const T& Grid<T>::getElementAt(size_t x, size_t y) const
{
  return mCells[x][y];
}

Code snippet from GridGrid.h

Using the Grid Template

When you want to create grid objects, you cannot use Grid alone as a type; you must specify the type that will be stored in that Grid. Creating an object of a template class for a specific type is called instantiating the template. Here is an example:

Grid<int> myIntGrid; // declares a grid that stores ints,
                     // using default parameters for the constructor
Grid<double> myDoubleGrid(11, 11); // declares an 11x11 Grid of doubles myIntGrid.setElementAt(0, 0, 10);
int x = myIntGrid.getElementAt(0, 0);
Grid<int> grid2(myIntGrid);
Grid<int> anotherIntGrid = grid2;

Code snippet from GridGridTest.cpp

Note that the type of myIntGrid, grid2, and anotherIntGrid is Grid<int>. You cannot store SpreadsheetCells or ChessPieces in these grids; the compiler will generate an error if you try to do so.

The type specification is important; neither of the following two lines compiles:

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

The first causes your compiler to complain with something like, “use of class template requires template argument list.” The second causes it to say something like, “wrong number of template arguments.”

If you want to declare a function or method that takes a Grid object, you must specify the type stored in that grid as part of the Grid type:

void processIntGrid(Grid<int>& inGrid)
{
   // Body omitted for brevity
}

Code snippet from GridGridTest.cpp

Instead of writing the full Grid type everytime, for example Grid<int>, you can use a typedef to give it an easier name:

typedef Grid<int> IntGrid;

Now you can write code as follows:

void processIntGrid(IntGrid& inGrid) { }

The Grid template can store more than just ints. For example, you can instantiate a Grid that stores SpreadsheetCells:

Grid<SpreadsheetCell> mySpreadsheet;
SpreadsheetCell myCell;
mySpreadsheet.setElementAt(3, 4, myCell);

Code snippet from GridGridTest.cpp

You can store pointer types as well:

Grid<char*> myStringGrid;
myStringGrid.setElementAt(2, 2, "hello");

Code snippet from GridGridTest.cpp

The type specified can even be another template type. The following example uses the vector template from the standard template library (introduced in Chapter 1):

Grid<vector<int>> gridOfVectors;
vector<int> myVector;
gridOfVectors.setElementAt(5, 6, myVector);

Code snippet from GridGridTest.cpp

You can also dynamically allocate Grid template instantiations on the heap:

Grid<int>* myGridp = new Grid<int>(); // creates Grid with default width/ height
myGridp->setElementAt(0, 0, 10);
int x = myGridp->getElementAt(0, 0);
delete myGridp;

Code snippet from GridGridTest.cpp

How the Compiler Processes Templates

In order to understand the intricacies of templates, you need to learn how the compiler processes template code. When the compiler encounters template method definitions, it performs syntax checking, but doesn’t actually compile the templates. It can’t compile template definitions because it doesn’t know for which types they will be used. It’s impossible for a compiler to generate code for something like x = y without knowing the types of x and y.

When the compiler encounters an instantiation of the template, such as Grid<int> myIntGrid, it writes code for an int version of the Grid template by replacing each T in the template class definition with int. When the compiler encounters a different instantiation of the template, such as Grid<SpreadsheetCell> mySpreadsheet, it writes another version of the Grid class for SpreadsheetCells. The compiler just writes the code that you would write if you didn’t have template support in the language and had to write separate classes for each element type. There’s no magic here; templates just automate an annoying process. If you don’t instantiate a class template for any types in your program, then the class method definitions are never compiled.

This instantiation process explains why you need to use the Grid<T> syntax in various places in your definition. When the compiler instantiates the template for a particular type, such as int, it replaces T with int, so that Grid<int> is the type.

Selective Instantiation

The compiler generates code only for the class methods that you actually call for a particular type. For example, given the preceding Grid template class, suppose that you write this code (and only this code) in main():

Grid<int> myIntGrid;
myIntGrid.setElementAt(0, 0, 10);

The compiler generates only the 0-argument constructor, the destructor, and the setElementAt() method for an int version of the Grid. It does not generate other methods like the copy constructor, the assignment operator, or getHeight().

Template Requirements on Types

When you write code that is independent of types, you must assume certain things about those types. For example, in the Grid template, you assume that the element type (represented by T) will have an assignment operator because of this line: mCells[x][y] = inElem. Similarly, you assume it will have a default constructor to allow you to create an array of elements.

If you attempt to instantiate a template with a type that does not support all the operations used by the template in your particular program, the code will not compile, and the error messages will almost always be quite obscure. However, even if the type you want to use doesn’t support the operations required by all the template code, you can exploit selective instantiation to use some methods but not others. For example, if you try to create a grid for an object that has no assignment operator, but you never call setElementAt() on that grid, your code will work fine. As soon as you try to call setElementAt(), however, you will receive a compilation error.

Distributing Template Code between Files

Normally you put class definitions in a header file and method definitions in a source file. Code that creates or uses objects of the class #includes the header file and obtains access to the method code via the linker. Templates don’t work that way. Because they are “templates” for the compiler to generate the actual methods for the instantiated types, both template class definitions and method definitions must be available to the compiler in any source file that uses them. There are several mechanisms to obtain this inclusion.

Template Definitions in Header Files

You can place the method definitions directly in the same header file where you define the class itself. When you #include this file in a source file where you use the template, the compiler will have access to all the code it needs.

Alternatively, you can place the template method definitions in a separate header file that you #include in the header file with the class definitions. Make sure the #include for the method definitions follows the class definition; otherwise the code won’t compile.

template <typename T>
class Grid
{
    // Class definition omitted for brevity
};
#include "GridDefinitions.h"

Code snippet from GridMethodsInSeparateHeaderGrid.h

Any client that wants to use the Grid template needs only to include the Grid.h header file. This division helps keep the distinction between class definitions and method definitions.

Template Definitions in Source Files

Method implementations look strange in header files. If that syntax annoys you, there is a way that you can place the method definitions in a source file. However, you still need to make the definitions available to the code that uses the templates, which you can do by #includeing the method implementation source file in the template class definition header file. That sounds odd if you’ve never seen it before, but it’s legal in C++. The header file looks like this:

template <typename T>
class Grid
{
    // Class definition omitted for brevity
};
#include "Grid.cpp"

Code snippet from GridMethodsInSourceGrid.h

When using this technique, make sure you don’t add the Grid.cpp file to your project, because it is not supposed to be, and cannot be compiled separately; it should only be #included in a header file.

You can actually call your file with method implementations anything you want. Some programmers like to give source files that are included an .inl extension, for example Grid.inl.

The pre-C++11 standard actually defined a way for template method definitions to exist in a source file, which does not need to be #included in a header file. You use the export keyword to specify that the template definitions should be available in all translation units (source files). However, this is not allowed anymore in C++11.

Template Parameters

In the Grid example, the Grid template has one template parameter: the type that is stored in the grid. When you write the class template, you specify the parameter list inside the angle brackets, like this:

template <typename T>

This parameter list is similar to the parameter list in a function or method. As in functions and methods, you can write a class with as many template parameters as you want. Additionally, these parameters don’t have to be types, and they can have default values.

Non-Type Template Parameters

Non-type parameters are “normal” parameters such as ints and pointers: the kind of parameters with which you’re familiar from functions and methods. However, non-type template parameters can only be integral types (char, int, long...), enumeration types, pointers and references.

In the Grid template class, you could use non-type template parameters to specify the height and width of the grid instead of specifying them in the constructor. The principle advantage to specifying non-type parameters in the template list instead of in the constructor is that the values are known before the code is compiled. Recall that the compiler generates code for templatized methods by substituting in the template parameters before compiling. Thus, you can use a normal two-dimensional array in your implementation instead of dynamically allocating it. Here is the new class definition:

template <typename T, size_t WIDTH, size_t HEIGHT>
class Grid
{
    public:
        void setElementAt(size_t x, size_t y, const T& inElem);
        T& getElementAt(size_t x, size_t y);
        const T& getElementAt(size_t x, size_t y) const;
       size_t getHeight() const { return HEIGHT; }
       size_t getWidth() const { return WIDTH; }
    protected:
       T mCells[WIDTH][HEIGHT];
};

Code snippet from GridNonTypeGrid.h

This class is significantly simpler than the old version. Note that the template parameter list requires three parameters: the type of objects stored in the grid and the width and height of the grid. The width and height are used to create a two-dimensional array to store the objects. There is no dynamically allocated memory in the class, so it no longer needs a user-defined copy constructor, destructor, or assignment operator. In fact, you don’t even need to write a default constructor; the compiler generated one is just fine. Here are the class method definitions:

template <typename T, size_t WIDTH, size_t HEIGHT>
void Grid<T, WIDTH, HEIGHT>::setElementAt(size_t x, size_t y, const T& inElem)
{
    mCells[x][y] = inElem;
}
template <typename T, size_t WIDTH, size_t HEIGHT>
T& Grid<T, WIDTH, HEIGHT>::getElementAt(size_t x, size_t y)
{
    return mCells[x][y];
}
template <typename T, size_t WIDTH, size_t HEIGHT>
const T& Grid<T, WIDTH, HEIGHT>::getElementAt(size_t x, size_t y) const
{
    return mCells[x][y];
}

Code snippet from GridNonTypeGrid.h

Note that wherever you previously specified Grid<T> you must now specify Grid<T, WIDTH, HEIGHT> to represent the three template parameters.

You can instantiate this template and use it like this:

Grid<int, 10, 10> myGrid;
Grid<int, 10, 10> anotherGrid;
myGrid.setElementAt(2, 3, 45);
anotherGrid = myGrid;
cout << anotherGrid.getElementAt(2, 3);

Code snippet from GridNonTypeGridTest.cpp

This code seems great. Despite the slightly messy syntax for declaring a Grid, the actual Grid code is a lot simpler. Unfortunately, there are more restrictions than you might think at first. First, you can’t use a non-constant integer to specify the height or width. The following code doesn’t compile:

size_t height = 10;
Grid<int, 10, height> testGrid; // DOES NOT COMPILE

However, if you make height const, it compiles:

const size_t height = 10;
Grid<int, 10, height> testGrid; // compiles and works

A second restriction might be more significant. Now that the width and height are template parameters, they are part of the type of each grid. That means that Grid<int, 10, 10> and Grid<int, 10, 11> are two different types. You can’t assign an object of one type to an object of the other, and variables of one type can’t be passed to functions or methods that expect variables of another type.

Non-type template parameters become part of the type specification of instantiated objects.

Default Values for Non-Type Parameters

If you continue the approach of making height and width template parameters, you might want to be able to provide defaults for the height and width just as you did previously in the constructor of the Grid<T> class. C++ allows you to provide defaults for template parameters with a similar syntax. Here is the class definition:

template <typename T, size_t WIDTH = 10, size_t HEIGHT = 10>
class Grid
{
    // Remainder is identical to the previous version
};

Code snippet from GridNonTypeDefaultGrid.h

You do not need to specify the default values for WIDTH and HEIGHT in the template specification for the method definitions. For example, here is the implementation of setElementAt():

template <typename T, size_t WIDTH, size_t HEIGHT>
void Grid<T, WIDTH, HEIGHT>::setElementAt(size_t x, size_t y, const T& inElem)
{
    mCells[x][y] = inElem;
}

Code snippet from GridNonTypeDefaultGrid.h

Now, you can instantiate a Grid with only the element type, the element type and the width, or the element type, width, and height:

Grid<int> myGrid;
Grid<int, 10> anotherGrid;
Grid<int, 10, 10> aThirdGrid;

Code snippet from GridNonTypeDefaultGridTest.cpp

The rules for default parameters in template parameter lists are the same as for functions or methods: You can provide defaults for parameters in order starting from the right.

Method Templates

C++ allows you to templatize individual methods of a class. These methods can be inside a class template or in a non-templatized class. When you write a templatized class method, you are actually writing many different versions of that method for many different types. Method templates come in useful for assignment operators and copy constructors in class templates.

Virtual methods and destructors cannot be method templates.

Consider the original Grid template with only one parameter: the element type. You can instantiate grids of many different types, such as ints and doubles:

Grid<int> myIntGrid;
Grid<double> myDoubleGrid;

Code snippet from MethodTemplatesGridTest.cpp

However, Grid<int> and Grid<double> are two different types. If you write a function that takes an object of type Grid<double>, you cannot pass a Grid<int>. Even though you know that the elements of an int grid could be copied to the elements of a double grid, because the ints could be coerced into doubles, you cannot assign an object of type Grid<int> to one of type Grid<double> or construct a Grid<double> from a Grid<int>. Neither of the following two lines compiles:

myDoubleGrid = myIntGrid;              // DOES NOT COMPILE
Grid<double> newDoubleGrid(myIntGrid); // DOES NOT COMPILE

The problem is that the Grid template copy constructor and operator= prototypes look like this:

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

The Grid copy constructor and operator= both take a reference to a const Grid<T>. When you instantiate a Grid<double> and try to call the copy constructor and operator=, the compiler generates methods with these prototypes:

Grid(const Grid<double>& src);
Grid<double>& operator=(const Grid<double>& rhs);

Note that there are no constructors or operator= that take a Grid<int> within the generated Grid<double> class. However, you can rectify this oversight by adding templatized versions of the copy constructor and operator= to the Grid class to generate routines that will convert from one grid type to another. Here is the new Grid class definition:

template <typename T>
class Grid
{
    public:
        Grid(size_t inWidth = kDefaultWidth, size_t inHeight = kDefaultHeight);
        Grid(const Grid<T>& src);
       template <typename E>
       Grid(const Grid<E>& src);
        virtual ~Grid();
        Grid<T>& operator=(const Grid<T>& rhs);
       template <typename E>
       Grid<T>& operator=(const Grid<E>& rhs);
        // Omitted for brevity
    protected:
        void copyFrom(const Grid<T>& src);
       template <typename E>
       void copyFrom(const Grid<E>& src);
        T** mCells;
        size_t mWidth, mHeight;
};

Code snippet from MethodTemplatesGrid.h

Member templates do not replace non-template members with the same name. This rule leads to problems with the copy constructor and operator= because of the compiler-generated versions. If you write templatized versions of the copy constructor and operator= and omit non-templatized versions, the compiler will not call these new templatized versions for assignments of grids with the same type. Instead, it will generate a copy constructor and operator= for creating and assigning two grids of the same type, which will not do what you want! Thus, you must keep the old non-templatized copy constructor and operator= as well.

Examine the new templatized copy constructor first:

template <typename E>
Grid(const Grid<E>& src);

You can see that there is another template declaration with a different typename, E (short for “element”). The class is templatized on one type, T, and the new copy constructor is also templatized on a different type, E. This twofold templatization allows you to copy grids of one type to another.

Here is the definition of the new copy constructor:

template <typename T>
template <typename E>
Grid<T>::Grid(const Grid<E>& src)
{
    copyFrom(src);
}

Code snippet from MethodTemplatesGrid.h

As you can see, you must declare the class template line (with the T parameter) before the member template line (with the E parameter). You can’t combine them like this:

template <typename T, typename E> // Incorrect for nested template constructor!
Grid<T>::Grid(const Grid<E>& src)

The copy constructor uses the protected copyFrom() method, so the class needs a templatized version of copyFrom() as well:

template <typename T>
template <typename E>
void Grid<T>::copyFrom(const Grid<E>& src)
{
    mWidth = src.getWidth();
    mHeight = src.getHeight();
    mCells = new T* [mWidth];
    for (size_t i = 0; i < mWidth; i++) {
        mCells[i] = new T[mHeight];
    }
    for (size_t i = 0; i < mWidth; i++) {
        for (size_t j = 0; j < mHeight; j++) {
            mCells[i][j] = src.getElementAt(i, j);
        }
    }
}

Code snippet from MethodTemplatesGrid.h

In addition to the extra template parameter line before the copyFrom() method definition, note that you must use public accessor methods getWidth(), getHeight(), and getElementAt() to access the elements of src. That’s because the object you’re copying to is of type Grid<T>, and the object you’re copying from is of type Grid<E>. They will not be the same type, so you must use public methods.

The final templatized method is the assignment operator. Note that it takes a const Grid<E>& but returns a Grid<T>&:

template <typename T>
template <typename E>
Grid<T>& Grid<T>::operator=(const Grid<E>& rhs)
{
    // Free the old memory.
    for (size_t i = 0; i < mWidth; i++) {
        delete [] mCells[i];
    }
    delete [] mCells;
    mCells = nullptr;
    // Copy the new memory.
    copyFrom(rhs);
    return *this;
}

Code snippet from MethodTemplatesGrid.h

You do not need to check for self-assignment in the templatized assignment operator, because assignment of the same types still happens in the old, non-templatized, version of operator=, so there’s no way you can get self-assignment here.

Method Templates with Non-Type Parameters

In the earlier example with integer template parameters for HEIGHT and WIDTH, you see that a major problem is that the height and width become part of the types. This restriction prevents you from assigning a grid with one height and width to a grid with a different height and width. In some cases, however, it’s desirable to assign or copy a grid of one size to a grid of a different size. Instead of making the destination object a perfect clone of the source object, you would copy only those elements from the source array that fit in the destination array, padding the destination array with default values if the source array is smaller in either dimension. With method templates for the assignment operator and copy constructor, you can do exactly that, thus allow assignment and copying of different sized grids. Here is the class definition:

template <typename T, size_t WIDTH = 10, size_t HEIGHT = 10>
class Grid
{
    public:
       Grid() {}
       template <typename E, size_t WIDTH2, size_t HEIGHT2>
       Grid(const Grid<E, WIDTH2, HEIGHT2>& src);
       template <typename E, size_t WIDTH2, size_t HEIGHT2>
       Grid<T, WIDTH, HEIGHT>& operator=(const Grid<E, WIDTH2, HEIGHT2>& rhs);
        void setElementAt(size_t x, size_t y, const T& inElem);
        T& getElementAt(size_t x, size_t y);
        const T& getElementAt(size_t x, size_t y) const;
        size_t getHeight() const { return HEIGHT; }
        size_t getWidth() const { return WIDTH; }
    protected:
       template <typename E, size_t WIDTH2, size_t HEIGHT2>
       void copyFrom(const Grid<E, WIDTH2, HEIGHT2>& src);
        T mCells[WIDTH][HEIGHT];
};

Code snippet from MethodTemplatesNonTypeGrid.h

This new definition includes method templates for the copy constructor and assignment operator, plus a helper method copyFrom(). When you write a copy constructor, the compiler stops generating a default constructor for you (details can be found in Chapter 6), so you have to add a default constructor as well. Note, however, that you do not need to write non-templatized copy constructor and assignment operator methods because the compiler-generated ones continue to be generated. They simply copy or assign mCells from the source to the destination, which is exactly the semantics you want for two grids of the same size.

When you templatize the copy constructor, assignment operator, and copyFrom(), you must specify all three template parameters. Here is the templatized copy constructor:

template <typename T, size_t WIDTH, size_t HEIGHT>
template <typename E, size_t WIDTH2, size_t HEIGHT2>
Grid<T, WIDTH, HEIGHT>::Grid(const Grid<E, WIDTH2, HEIGHT2>& src)
{
    copyFrom(src);
}

Code snippet from MethodTemplatesNonTypeGrid.h

Here are the implementations of copyFrom() and operator=. Note that copyFrom() copies only WIDTH and HEIGHT elements in the x and y dimensions, respectively, from src, even if src is bigger than that. If src is smaller in either dimension, copyFrom() pads the extra spots with zero-initialized values. T() calls the default constructor for the object if T is a class type, or generates 0 if T is a simple type. This syntax is called the zero-initialization syntax. It’s a good way to provide a reasonable default value for a variable whose type you don’t yet know:

template <typename T, size_t WIDTH, size_t HEIGHT>
template <typename E, size_t WIDTH2, size_t HEIGHT2>
void Grid<T, WIDTH, HEIGHT>::copyFrom(const Grid<E, WIDTH2, HEIGHT2>& src)
{
    for (size_t i = 0; i < WIDTH; i++) {
        for (size_t j = 0; j < HEIGHT; j++) {
            if (i < WIDTH2 && j < HEIGHT2) {
                mCells[i][j] = src.getElementAt(i, j);
            } else {
                mCells[i][j] = T();
            }
        }
    }
}
template <typename T, size_t WIDTH, size_t HEIGHT>
template <typename E, size_t WIDTH2, size_t HEIGHT2>
Grid<T, WIDTH, HEIGHT>& Grid<T, WIDTH, HEIGHT>::operator=(
    const Grid<E, WIDTH2, HEIGHT2>& rhs)
{
    // No need to check for self-assignment because this version of
    // assignment is never called when T and E are the same
    // No need to free any memory first
    // Copy the new memory.
    copyFrom(rhs);
    return *this;
}

Code snippet from MethodTemplatesNonTypeGrid.h

Template Class Specialization

You can provide alternate implementations of class templates for specific types. For example, you might decide that the Grid behavior for char*s (C-style strings) doesn’t make sense. The grid currently stores shallow copies of pointer types. For char*’s, it might make sense to do a deep copy of the string.

Alternate implementations of templates are called template specializations. Again, the syntax is a little weird. When you write a template class specialization, you must specify that it’s a template, and that you are writing the version of the template for that particular type. Here is the syntax for specializing the original version of the Grid for char*s:

// When the template specialization is used, the original template must be
// visible too. #including it here ensures that it will always be visible
// when this specialization is visible.
#include "Grid.h"
template <>
class Grid<char*>
{
    public:
        Grid(size_t inWidth = kDefaultWidth, size_t inHeight = kDefaultHeight);
       Grid(const Grid<char*>& src);
        virtual ~Grid();
       Grid<char*>& operator=(const Grid<char*>& rhs);
       void setElementAt(size_t x, size_t y, const char* inElem);
       char* getElementAt(size_t x, size_t y) const;
        size_t getHeight() const { return mHeight; }
        size_t getWidth() const { return mWidth; }
        static const size_t kDefaultWidth = 10;
        static const size_t kDefaultHeight = 10;
    protected:
       void copyFrom(const Grid<char*>& src);
       char*** mCells;
        size_t mWidth, mHeight;
};

Code snippet from GridSpecializationGridString.h

Note that you don’t refer to any type variable, such as T, in the specialization: You work directly with char*s. One obvious question at this point is why this class is still a template. That is, what good is the following syntax?

template <>
class Grid<char*>

This syntax tells the compiler that this class is a char* specialization of the Grid class. Suppose that you didn’t use that syntax and just tried to write this:

class Grid

The compiler wouldn’t let you do that because there is already a class named Grid (the original template class). Only by specializing it can you reuse the name. The main benefit of specializations is that they can be invisible to the user. When a user creates a Grid of ints or SpreadsheetCells, the compiler generates code from the original Grid template. When the user creates a Grid of char*s, the compiler uses the char* specialization. This can all be “behind the scenes.”

Grid<int> myIntGrid;           // Uses original Grid template
Grid<char*> stringGrid1(2, 2); // Uses char* specialization
string dummy = "dummy";
stringGrid1.setElementAt(0, 0, "hello");
stringGrid1.setElementAt(0, 1, dummy.c_str());
stringGrid1.setElementAt(1, 0, dummy.c_str());
stringGrid1.setElementAt(1, 1, "there");
Grid<char*> stringGrid2(stringGrid1);

Code snippet from GridSpecializationGridTest.cpp

When you specialize a template, you don’t “inherit” any code: Specializations are not like subclasses. You must rewrite the entire implementation of the class. There is no requirement that you provide methods with the same names or behavior. In fact, you could write a completely different class with no relation to the original. Of course, that would abuse the template specialization ability, and you shouldn’t do it without good reason. Here are the implementations for the methods of the char* specialization. Unlike in the template definitions, you do not repeat the template<> syntax before each method or static member definition:

Grid<char*>::Grid(size_t inWidth, size_t inHeight) :
    mWidth(inWidth), mHeight(inHeight)
{
   mCells = new char** [mWidth];
    for (size_t i = 0; i < mWidth; i++) {
        mCells[i] = new char* [mHeight];
        for (size_t j = 0; j < mHeight; j++) {
            mCells[i][j] = nullptr;
        }
    }
}
Grid<char*>::Grid(const Grid<char*>& src)
{
    copyFrom(src);
}
Grid<char*>::~Grid()
{
    // Free the old memory.
    for (size_t i = 0; i < mWidth; i++) {
        for (size_t j = 0; j < mHeight; j++) {
            delete [] mCells[i][j];
        }
        delete [] mCells[i];
    }
    delete [] mCells;
    mCells = nullptr;
}
void Grid<char*>::copyFrom(const Grid<char*>& src)
{
    mWidth = src.mWidth;
    mHeight = src.mHeight;
   mCells = new char** [mWidth];
    for (size_t i = 0; i < mWidth; i++) {
        mCells[i] = new char* [mHeight];
    }
    for (size_t i = 0; i < mWidth; i++) {
        for (size_t j = 0; j < mHeight; j++) {
            if (src.mCells[i][j] == nullptr) {
                mCells[i][j] = nullptr;
            } else {
                size_t len = strlen(src.mCells[i][j]) + 1;
                mCells[i][j] = new char[len];
                strncpy(mCells[i][j], src.mCells[i][j], len);
            }
        }
    }
}
Grid<char*>& Grid<char*>::operator=(const Grid<char*>& rhs)
{
    // Check for self-assignment.
    if (this == &rhs) {
        return *this;
    }
    // Free the old memory.
    for (size_t i = 0; i < mWidth; i++) {
        for (size_t j = 0; j < mHeight; j++) {
            delete [] mCells[i][j];
        }
        delete [] mCells[i];
    }
    delete [] mCells;
    mCells = nullptr;
    // Copy the new memory.
    copyFrom(rhs);
    return *this;
}
void Grid<char*>::setElementAt(size_t x, size_t y, const char* inElem)
{
    delete [] mCells[x][y];   
    if (inElem == nullptr) {
        mCells[x][y] = nullptr;
    } else {
        size_t len = strlen(inElem) + 1;
        mCells[x][y] = new char[len];
        strncpy(mCells[x][y], inElem, len);
    }
}
char* Grid<char*>::getElementAt(size_t x, size_t y) const
{
    if (mCells[x][y] == nullptr) {
        return nullptr;
    }
    size_t len = strlen(mCells[x][y]) + 1;
    char* ret = new char[len];
    strncpy(ret, mCells[x][y], len);
    return ret;
}

Code snippet from GridSpecializationGridString.h

getElementAt() returns a deep copy of the string, so you don’t need an overload that returns a const char*. However, since it does return a deep copy, the caller is responsible to free the memory returned by getElementAt() with delete[].

This section discussed how to use template class specialization. It allows you to write a special implementation for a template with the template types replaced by specific types. The next chapter continues the discussion of specialization with a more advanced feature called partial specialization.

Subclassing Template Classes

You can write subclasses of template classes. If the subclass inherits from the template itself, it must be a template as well. Alternatively, you can write a subclass to inherit from a specific instantiation of the template class, in which case your subclass does not need to be a template. As an example of the former, suppose you decide that the generic Grid class doesn’t provide enough functionality to use as a game board. Specifically, you would like to add a move() method to the game board that moves a piece from one location on the board to another. Here is the class definition for the GameBoard template:

template <typename T>
class GameBoard : public Grid<T>
{
    public:
        GameBoard(size_t inWidth = Grid<T>::kDefaultWidth,
            size_t inHeight = Grid<T>::kDefaultHeight);
        void move(size_t xSrc, size_t ySrc, size_t xDest, size_t yDest);
};

Code snippet from GridSubclassGameBoard.h

This GameBoard template subclasses the Grid template, and thereby inherits all its functionality. You don’t need to rewrite setElementAt(), getElementAt(), or any of the other methods. You also don’t need to add a copy constructor, operator=, or destructor, because you don’t have any dynamically allocated memory in the GameBoard. The dynamically allocated memory in the Grid superclass will be taken care of by the Grid copy constructor, operator=, and destructor.

The inheritance syntax looks normal, except that the superclass is Grid<T>, not Grid. The reason for this syntax is that the GameBoard template doesn’t really subclass the generic Grid template. Rather, each instantiation of the GameBoard template for a specific type subclasses the Grid instantiation for that type. For example, if you instantiate a GameBoard with a ChessPiece type, then the compiler generates code for a Grid<ChessPiece> as well. The “: public Grid<T>” syntax says that this class subclasses from whatever Grid instantiation makes sense for the T type parameter. Note that the C++ name lookup rules for template inheritance require you to specify that kDefaultWidth and kDefaultHeight are declared in, and thus dependent on, the Grid<T> superclass.

Here are the implementations of the constructor and the move() method. Again, note the use of Grid<T> in the call to the superclass constructor. Additionally, although many compilers don’t enforce it, the name lookup rules require you to use the this pointer to refer to data members and methods in the superclass:

template <typename T>
GameBoard<T>::GameBoard(size_t inWidth, size_t inHeight) :
    Grid<T>(inWidth, inHeight)
{
}
template <typename T>
void GameBoard<T>::move(size_t xSrc, size_t ySrc, size_t xDest, size_t yDest)
{
    this->mCells[xDest][yDest] = this->mCells[xSrc][ySrc];
    this->mCells[xSrc][ySrc] = T(); // default construct the src cell
}

Code snippet from GridSubclassGameBoard.h

As you can see, move() uses the syntax T() described in the section on “Method Templates with Non-Type Parameters.”

You can use the GameBoard template as follows:

GameBoard<ChessPiece> chessBoard;
ChessPiece pawn;
chessBoard.setElementAt(0, 0, pawn);
chessBoard.move(0, 0, 0, 1);

Code snippet from GridSubclassGameBoardTest.cpp

Inheritance versus Specialization

Some programmers find the distinction between template inheritance and template specialization confusing. The following table summarizes the differences:

Use inheritance for extending implementations and for polymorphism. Use specialization for customizing implementations for particular types.

Template Aliases

Chapter 9 introduces the concept of a typedef. It allows you to give another name to specific types. For example you could write the following typedef:

typedef int MyInt;

With the preceding typedef you have given another name to type int allowing you to define integers by using type MyInt instead of int as follows:

MyInt i = 123;

Of course, the original type int still exists and can still be used as type specification. Similarly, you could use a typedef to give another name to a templatized class. However, C++ requires you to specify concrete types for each template type. An example will make it clearer. Suppose you have the following class using templates:

template<typename T1, typename T2>
class MyTemplateClass {/* ... */};

If you want to use a typedef to define another name for MyTemplateClass, you have to give concrete types for T1 and T2. For example:

typedef MyTemplateClass<int, double> OtherName;

Specifying only one of the types, like the following example, is not valid in C++:

template<typename T1>
typedef MyTemplateClass<T1, double> OtherName;  // Error

C++11 removes this limitation by introducing template aliases, which can be used as follows:

template<typename T1>
using OtherName = MyTemplateClass<T1, double>;

Pay special attention to the syntax. The new type name OtherName should be at the beginning with the template alias syntax, while it should be at the end for the typedef syntax. This template/type alias syntax can be used to replace the earlier typedef syntax, whether a template is involved or not. For example:

using MyInt = int;

This is exactly the same as:

typedef int MyInt;

Alternative Function Syntax

The alternative function syntax is discussed in Chapter 9 and is mentioned again here because it is a very useful C++11 feature in combination with templates. The problem solved with the alternative function syntax is that you don’t always know the exact return type at the beginning of your function prototype. Take the following templatized function as example:

template<typename Type1, typename Type2>
RetType myFunc(const Type1& t1, const Type2& t2) {return t1 + t2;}

In this example, RetType should be the type of the expression t1+t2, which isn’t known yet at the beginning of the prototype line. t1 and t2 become known once the semantic analyzer reaches the end of the parameter list. Chapter 1 introduces the C++11 decltype feature. decltype(T) returns the type of its argument T. With this knowledge, you might try to solve the previous return type issue by using the decltype feature as follows:

template<typename Type1, typename Type2>
decltype(t1+t2) myFunc(const Type1& t1, const Type2& t2) {return t1 + t2;} 

Unfortunately, this is also not valid in C++11 because t1 and t2 are still not yet defined when the compiler is parsing decltype(t1+t2).

C++11 solves this problem with the alternative function syntax as follows. Note that in the new syntax, the return type is specified after the parameter list, hence the names of the parameters (and their types, and consequently the type t1+t2) are known:

template<typename Type1, typename Type2>
auto myFunc(const Type1& t1, const Type2& t2) -> decltype(t1+t2)
     {return t1 + t2;}

Code snippet from AlternativeFunctionSyntaxAlternativeFunctionSyntax.cpp

The auto keyword here instructs the compiler that the prototype is using the alternative function syntax, which is a completely different meaning than the auto keyword that is introduced in Chapter 1 to let the compiler automatically deduce the type of an expression.

FUNCTION TEMPLATES

You can also write templates for stand-alone functions. For example, you could write a generic function to find a value in an array and return its index:

static const size_t NOT_FOUND = (size_t)(-1);
template <typename T>
size_t Find(T& value, T* arr, size_t size)
{
    for (size_t i = 0; i < size; i++) {
        if (arr[i] == value) {
            return i; // Found it; return the index
        }
    }
    return NOT_FOUND; // Failed to find it; return NOT_FOUND
}

Code snippet from FunctionTemplateFindTemplate.cpp

The Find() function template can work on arrays of any type. For example, you could use it to find the index of an int in an array of ints or a SpreadsheetCell in an array of SpreadsheetCells.

You can call the function in two ways: explicitly specifying the type with angle brackets or omitting the type and letting the compiler deduce it from the arguments. Here are some examples:

int x = 3, intArr[] = {1, 2, 3, 4};
size_t sizeIntArr = sizeof(intArr) / sizeof(int);
size_t res;
res = Find(x, intArr, sizeIntArr);       // calls Find<int> by deduction
res = Find<int>(x, intArr, sizeIntArr);  // calls Find<int> explicitly
if (res != NOT_FOUND)
    cout << res << endl;
else
    cout << "Not found" << endl;
 
double d1 = 5.6, dArr[] = {1.2, 3.4, 5.7, 7.5};
size_t sizeDoubleArr = sizeof(dArr) / sizeof(double);
res = Find(d1, dArr, sizeDoubleArr);         // calls Find<double> by deduction
res = Find<double>(d1, dArr, sizeDoubleArr); // calls Find<double> explicitly
if (res != NOT_FOUND)
    cout << res << endl;
else
    cout << "Not found" << endl;
//res = Find(x, dArr, sizeDoubleArr); // DOES NOT COMPILE!
                                      // Arguments are different types.
 
SpreadsheetCell c1(10), c2Arr[2] =
        {SpreadsheetCell(4), SpreadsheetCell(10)};
size_t sizeC2Arr = sizeof(c2Arr) / sizeof(SpreadsheetCell);
res = Find(c1, c2Arr, sizeC2Arr);
res = Find<SpreadsheetCell>(c1, c2Arr, sizeC2Arr);

Code snippet from FunctionTemplateFindTemplate.cpp

Like class templates, function templates can take non-type parameters. For brevity, only an example of a type parameter for function templates is shown.

The C++ standard library provides a templatized find() function that is much more powerful than the one above. See Chapter 13 for details.

Function Template Specialization

Just as you can specialize class templates, you can specialize function templates. For example, you might want to write a Find() function for char* C-style strings that compares them with strcmp() instead of operator==. Here is a specialization of the Find() function to do this:

template<>
size_t Find<char*>(char*& value, char** arr, size_t size)
{
    cout << "Specialization" << endl;
    for (size_t i = 0; i < size; i++) {
        if (strcmp(arr[i], value) == 0) {
            return i; // Found it; return the index
        }
    }
    return NOT_FOUND; // Failed to find it; return NOT_FOUND
}

Code snippet from FunctionTemplateFindTemplateSpecialization.cpp

You can omit the <char*> in the function name when the parameter type can be deduced from the arguments, making your prototype look like this:

template<>
size_t Find(char*& value, char** arr, size_t size)

However, the deduction rules are tricky when you involve overloading as well (see next section), so, in order to avoid mistakes, it’s better to note the type explicitly.

Although the specialized find() function could take just char* instead of char*& as its first parameter, it’s best to keep the arguments parallel to the non-specialized version of the function for the deduction rules to function properly.

You can use the specialization as follows:

char* word = "two";
char* arr[] = {"one", "two", "three", "four"};
size_t sizeArr = sizeof(arr) / sizeof(arr[0]);
size_t res;
res = Find<char*>(word, arr, sizeArr); // Calls the char* specialization
res = Find(word, arr, sizeArr);        // Calls the char* specialization

Code snippet from FunctionTemplateFindTemplateSpecialization.cpp

Function Template Overloading

You can also overload template functions with non-template functions. For example, instead of writing a Find() template specialization for char*, you could write a non-template Find() function that works on char*s:

size_t Find(char*& value, char** arr, size_t size)
{
    cout << "overload" << endl;
    for (size_t i = 0; i < size; i++) {
        if (strcmp(arr[i], value) == 0) {
            return i; // Found it; return the index
        }
    }
    return NOT_FOUND; // Failed to find it; return NOT_FOUND
}

Code snippet from FunctionTemplateFindTemplateOverload.cpp

This function is identical in behavior to the specialized version in the previous section. However, the rules for when it is called are different:

char* word = "two";
char* arr[] = {"one", "two", "three", "four"};
size_t sizeArr = sizeof(arr) / sizeof(arr[0]);
size_t res;
res = Find<char*>(word, arr, sizeArr); // Calls the Find template with T=char*
res = Find(word, arr, sizeArr);        // Calls the Find non-template function!

Code snippet from FunctionTemplateFindTemplateOverload.cpp

Thus, if you want your function to work both when char* is explicitly specified and via deduction when it is not, you should write a specialized template version instead of a non-template, overloaded version.

Like template class method definitions, function template definitions (not just the prototypes) must be available to all source files that use them. Thus, you should put the definitions in header files if more than one source file uses them.

Function Template Overloading and Specialization Together

It’s possible to write both a specialized Find() template for char*s and a stand-alone Find() function for char*s. The compiler always prefers the non-template function to a templatized version. However, if you specify the template instantiation explicitly, the compiler will be forced to use the template version:

char* word = "two";
char* arr[] = {"one", "two", "three", "four"};
size_t sizeArr = sizeof(arr) / sizeof(arr[0]);
size_t res;
res = Find<char*>(word, arr, sizeArr); // Calls the char* specialization of                                        // the template
res = Find(word, arr, sizeArr);        // Calls the Find non-template function

Code snippet from FunctionTemplateFindTemplateSpecialOverload.cpp

Friend Function Templates of Class Templates

Function templates are useful when you want to overload operators in a class template. For example, you might want to overload the insertion operator (operator<<) for the Grid class template to stream a grid.

If you are unfamiliar with the mechanics for overloading operator<<, consult Chapter 18 for details.

As discussed in Chapter 18, you can’t make operator<< a member of the Grid class: It must be a stand-alone function template. The definition, which should go directly in Grid.h, looks as follows:

template <typename T>
ostream& operator<<(ostream& ostr, const Grid<T>& grid)
{
    for (size_t i = 0; i < grid.mHeight; i++) {
        for (size_t j = 0; j < grid.mWidth; j++) {
            // Add a tab between each element of a row.
            ostr << grid.mCells[j][i] << "	";
        }
        ostr << std::endl; // Add a newline between each row.
    }
    return ostr;
}

Code snippet from FriendFunctionTemplatesGrid.h

This function template will work on any Grid, as long as there is an insertion operator for the elements of the grid. The only problem is that operator<< accesses protected members of the Grid class. Therefore, it must be a friend of the Grid class. However, both the Grid class and the operator<< are templates. What you really want is for each instantiation of operator<< for a particular type T to be a friend of the Grid template instantiation for that type. The syntax looks like this:

// Forward declare Grid template.
template <typename T> class Grid;
 
// Prototype for templatized operator<<.
template<typename T>
ostream& operator<<(ostream& ostr, const Grid<T>& grid);
 
template <typename T>
class Grid
{
    public:
        // Omitted for brevity
       friend ostream& operator<< <T>(ostream& ostr, const Grid<T>& grid);
        // Omitted for brevity
};

Code snippet from FriendFunctionTemplatesGrid.h

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, but in the interest of readability it should always be there). This syntax tells the compiler that operator<< is itself a template.

SUMMARY

This chapter started a discussion on using templates for generic programming. You saw the syntax on how to write templates and examples where templates are really useful. It explained how to write class templates, how to organize your code in different files, how to use template parameters, and how to templatize methods of a class. It further discussed how to use template class specialization to write special implementations of a template where the template types are replaced with specific types. The chapter finished with an explanation of function templates.

The next chapter continues the discussion on templates with some more advanced features such as variadic templates and metaprogramming.