Chapter 20: Advanced Templates

Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

Chapter 20

Advanced Templates

WHAT’S IN THIS CHAPTER?

What the details are of the different kinds of template parameters
How to use partial specialization
How to write recursive templates
How to write type-safe variable arguments functions using variadic templates
What metaprogramming is and how to use it

The previous 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 better understand how the STL works, or perhaps write your own simple classes, you can skip this chapter on advanced templates. However, if templates interest you and you want to uncover their full power, continue reading 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, non-type, and template template (no, you’re not seeing double: that really is the name). You’ve seen examples of type and non-type parameters in the previous chapter, but not template template parameters yet. There are also some tricky aspects to both type and non-type parameters that are not covered in the previous chapter.

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. The standard template library defines several templatized container classes, including vector and deque, which are introduced in Chapter 12. 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(size_t inWidth = kDefaultWidth,
            size_t inHeight = kDefaultHeight);
       Grid(const Grid<T, Container>& src);
        virtual ~Grid();
       Grid<T, Container>& operator=(const Grid<T, Container>& 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, Container>& src);
       Container* mCells;
        size_t mWidth, mHeight;
};

Code snippet from GridTemplateContainerGrid.h

This template now has two parameters: T and Container. Thus, wherever you previously referred to Grid<T> you must now 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:

template <typename T, typename Container>
Grid<T, Container>::Grid(size_t inWidth, size_t inHeight) :
    mWidth(inWidth), mHeight(inHeight)
{
    // Dynamically allocate the array of mWidth containers
    mCells = new Container[mWidth];
    for (size_t i = 0; i < mWidth; i++) {
        // Resize each container so that it can hold mHeight elements.
        mCells[i].resize(mHeight);
    }
}

Code snippet from GridTemplateContainerGrid.h

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;
    mCells = nullptr;
}

Code snippet from GridTemplateContainerGrid.h

The code in copyFrom() assumes that you can access elements in the container by using array [] notation. Chapter 18 explains how to overload the [] operator to implement this feature in your own container classes. Both vector and deque from the STL support this syntax.

template <typename T, typename Container>
void Grid<T, Container>::copyFrom(const Grid<T, Container>& src)
{
    mWidth = src.mWidth;
    mHeight = src.mHeight;
    mCells = new Container[mWidth];
    for (size_t i = 0; i < mWidth; i++) {
       // Resize each element, as in the constructor.
       mCells[i].resize(mHeight);
    }
    for (size_t i = 0; i < mWidth; i++) {
        for (size_t j = 0; j < mHeight; j++) {
            mCells[i][j] = src.mCells[i][j];
        }
    }
}

Code snippet from GridTemplateContainerGrid.h

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;
    mCells = nullptr;
    // Copy the new memory.
    copyFrom(rhs);
    return *this;
}
template <typename T, typename Container>
void Grid<T, Container>::setElementAt(size_t x, size_t y, const T& inElem)
{
    mCells[x][y] = inElem;
}
template <typename T, typename Container>
T& Grid<T, Container>::getElementAt(size_t x, size_t y)
{
    return mCells[x][y];
}
template <typename T, typename Container>
const T& Grid<T, Container>::getElementAt(size_t x, size_t y) const
{
    return mCells[x][y];
}

Code snippet from GridTemplateContainerGrid.h

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;

Code snippet from GridTemplateContainerGridTest.cpp

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 is used in the STL. 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:

template <typename T, typename Container = vector<T>>
class Grid
{
    public:
        // Everything else is the same as before.
};

Code snippet from GridTemplateContainerGridDefault.h

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. In versions of C++ earlier than C++11, there must be a space between the two closing angle brackets. C++11 does not require this space anymore.

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

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;

Code snippet from GridTemplateContainerGridDefaultTest.cpp

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, but, 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 the element type. The Allocator parameter is covered in Chapter 12.

Given the preceding 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
    protected:
        Container<T>* mCells;
        // Omitted code that is the same as before
};

Code snippet from GridTemplateContainerGridTemplateTemplate.h

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 <..., template <TemplateTypeParams> class ParameterName, ...>

Now that you’ve suffered through the 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(size_t inWidth, size_t inHeight) :
    mWidth(inWidth), mHeight(inHeight)
{
    mCells = new Container<T>[mWidth];
    for (size_t i = 0; i < mWidth; i++) {
        mCells[i].resize(mHeight);
    }
}

Code snippet from GridTemplateContainerGridTemplateTemplate.h

After implementing all the methods, you can use the template as follows:

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

Code snippet from GridTemplateContainerGridTemplateTemplateTest.cpp

This C++ syntax is a bit convoluted because it is trying to allow for maximum flexibility. 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.

More about Non-Type 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(size_t inWidth = kDefaultWidth,
            size_t inHeight = kDefaultHeight);
       Grid(const Grid<T, EMPTY>& src);
        virtual ~Grid();
       Grid<T, EMPTY>& operator=(const Grid<T, EMPTY>& rhs);
        // Omitted for brevity
    protected:
        void copyFrom(const Grid<T, EMPTY>& src);
        T** mCells;
        size_t mWidth, mHeight;
};

Code snippet from GridEmptyGrid.h

This definition is legal. You can use the type T from the first parameter as the type for the second parameter, and non-type 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(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];
        for (size_t j = 0; j < mHeight; j++) {
            mCells[i][j] = EMPTY;
        }
    }
}

Code snippet from GridEmptyGrid.h

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;

Code snippet from GridEmptyGridTest.cpp

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

Code snippet from GridEmptyGridTest.cpp

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

Non-type parameters cannot be objects, or even doubles or floats. They are restricted to integral types, 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 Non-Type 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 non-type 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.
};

Code snippet from GridEmptyGridRefNonType.h

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. Chapter 9 discusses external linkage, which 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. 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 program that declares int and SpreadsheetCell grids with initialization parameters:

extern const int emptyInt = 0;
extern const SpreadsheetCell emptyCell(0);
int main()
{
    Grid<int, emptyInt> myIntGrid;
    Grid<SpreadsheetCell, emptyCell> mySpreadsheet;
    Grid<int, emptyInt> myIntGrid2(myIntGrid);
    return 0;
}

Code snippet from GridEmptyGridTestRefNonType.cpp

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.

Using Zero-Initialization of Template Types

Neither of the options presented so far for providing an initial empty value for the cells is very attractive. Instead, you may simply want to initialize each cell to a reasonable default value that you choose (instead of allowing the user to specify). Of course, the immediate question is: What’s a reasonable value for any possible type? For objects, a reasonable value is an object created with the default constructor. In fact, that’s exactly what you’re already getting when you create an array of objects. However, for simple data types like integral types (int, short, ...), a reasonable initial value is 0; for floating point types, a reasonable initial value is 0.0; and for pointers, a reasonable initial value is nullptr. Therefore, what you really want to be able to do is assign this initial value to non-objects and use the default constructor on objects. You actually saw the syntax for this behavior in the section on “Method Templates with Non-Type Parameters” in the previous chapter. Here is the implementation of the Grid template constructor using the zero-initialization syntax:

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];
        for (size_t j = 0; j < mHeight; j++) {
            mCells[i][j] = T();
        }
    }
}

Code snippet from GridEmptyGridZeroInitialized.h

Given this ability, you can revert to the original Grid class (without an EMPTY non-type parameter) and just initialize each cell element to its zero-initialized “reasonable value.”

TEMPLATE CLASS PARTIAL SPECIALIZATION

The char* class specialization shown in the previous chapter is called full template class specialization because it specializes the Grid template for every template parameter. There are no template parameters left in the specialization. That’s not the only way you can specialize a class; you can also write a partial class specialization, in which you specialize some template parameters but not others. For example, recall the basic version of the Grid template with width and height non-type parameters:

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

You could specialize this template class for char* C-style strings like this:

#include "Grid.h" // The file containing the Grid template definition
template <size_t WIDTH, size_t HEIGHT>
class Grid<char*, WIDTH, HEIGHT>
{
    public:
        Grid();
       Grid(const Grid<char*, WIDTH, HEIGHT>& src);
        virtual ~Grid();
       Grid<char*, WIDTH, HEIGHT>& operator=(
            const Grid<char*, WIDTH, HEIGHT>& 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 HEIGHT; }
        size_t getWidth() const { return WIDTH; }
    protected:
       void copyFrom(const Grid<char*, WIDTH, HEIGHT>& src);
       char* mCells[WIDTH][HEIGHT];
};

Code snippet from GridPartialStringGridString.h

In this case, you are not specializing all the template parameters. Therefore, your template line looks like this:

template <size_t WIDTH, size_t HEIGHT>
class Grid<char*, WIDTH, HEIGHT>

Note that the template has only two parameters: WIDTH and HEIGHT. However, you’re writing a Grid class for three arguments: T, WIDTH, and HEIGHT. Thus, your template parameter list contains two parameters, and the explicit Grid<char*, WIDTH, HEIGHT> contains three arguments. When you instantiate the template, you must still specify three parameters. You can’t instantiate the template with only height and width:

Grid<int, 2, 2> myIntGrid;      // Uses the original Grid
Grid<char*, 2, 2> myStringGrid; // Uses the partial specialization for char *s
Grid<2, 3> test;                // DOES NOT COMPILE! No type specified.

Code snippet from GridPartialStringGridTestString.cpp

Yes, the syntax is confusing. And it gets worse. In partial specializations, unlike in full specializations, you include the template line in front of every method definition:

template <size_t WIDTH, size_t HEIGHT>
Grid<char*, WIDTH, HEIGHT>::Grid()
{
    for (size_t i = 0; i < WIDTH; i++) {
        for (size_t j = 0; j < HEIGHT; j++) {
            mCells[i][j] = nullptr; // Initialize each element to nullptr.
        }
    }
}

Code snippet from GridPartialStringGridString.h

You need this template line with two parameters to show that this method is parameterized on those two parameters. Note that wherever you refer to the full class name, you must use Grid<char*, WIDTH, HEIGHT>.

You can find the rest of the method definitions in the downloadable source code archive for this book on www.wrox.com.

Another Form of Partial Specialization

The previous example does not show the true power of partial specialization. You can write specialized implementations for a subset of possible types without specializing individual types. For example, you can write a specialization of the Grid class for all pointer types. This specialization might perform deep copies of objects to which pointers point instead of storing shallow copies of the pointers in the grid.

Here is the class definition, assuming that you’re specializing the initial version of the Grid with only one parameter:

#include "Grid.h"
template <typename T>
class Grid<T*>
{
    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, T* inElem);
        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 GridPartialPtrGridPtr.h

As usual, these two lines are the crux of the matter:

template <typename T>
class Grid<T*>

The syntax says that this class is a specialization of the Grid template for all pointer types. At least that’s what it’s telling the compiler. What it’s telling you and me is that the C++ standards committee should have come up with a better syntax. Unless you’ve been working with it for a long time, it’s quite jarring.

You are providing the implementation only in cases where T is a pointer type. Note that if you instantiate a grid like this: Grid<int*> myIntGrid, then T will actually be int, not int*. That’s a bit unintuitive, but unfortunately, the way it works. Here is a code example:

Grid<int> myIntGrid;     // Uses the non-specialized grid
Grid<int*> psGrid(2, 2); // Uses the partial specialization for pointer types
 
int x = 3, y = 4;
psGrid.setElementAt(0, 0, &x);
psGrid.setElementAt(0, 1, &y);
psGrid.setElementAt(1, 0, &y);
psGrid.setElementAt(1, 1, &x);
 
Grid<int*> psGrid2(psGrid);
Grid<int*> psGrid3;
psGrid3 = psGrid2;
 
const Grid<int*>& psGrid4 = psGrid2;
cout << *(psGrid4.getElementAt(1, 1)) << endl;
x=6;
cout << *(psGrid4.getElementAt(1, 1)) << endl;

Code snippet from GridPartialPtrGridPtrTest.cpp

The psGrid4 grid is storing pointers, so psGrid4.getElementAt(1, 1) will return a pointer to x. Changing the value of the variable x will change the result of dereferencing the pointer returned by getElementAt(1, 1). The output of the above code should be as follows:

3
6

At this point, you’re probably wondering whether this really works. We sympathize with your skepticism. One of the authors was so surprised by this syntax when he first read about it that he didn’t believe it actually worked until he was able to try it out. If you don’t believe us, try it out yourself. Here are the method implementations. Pay close attention to the template line syntax before each method:

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];
    }
}
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, T* inElem)
{
    mCells[x][y] = inElem;
}
template <typename T>
T* Grid<T*>::getElementAt(size_t x, size_t y) const
{
    return mCells[x][y];
}

Code snippet from GridPartialPtrGridPtr.h

For brevity, this example is not implementing any deep copying of the pointers. This would be a good exercise for the reader.

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 in the previous chapter, that dereferences the pointers to use operator== directly on the objects pointed to. Following the syntax for class template partial specialization, you might be tempted to write this:

template <typename T>
size_t Find<T*>(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 FunctionTemplatePtrFindTemplatePtr.cpp

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

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

The difference might seem trivial and academic, but it makes the difference between portable standard code and code that is not standard compliant.

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 non-template versions being preferred over template versions.

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

size_t res = NOT_FOUND;
 
int x = 3, intArr[] = {1, 2, 3, 4};
size_t sizeArr = sizeof(intArr) / sizeof(int);
res = Find(x, intArr, sizeArr);      // calls Find<int> by deduction
res = Find<int>(x, intArr, sizeArr); // calls Find<int> explicitly
 
double d1 = 5.6, dArr[] = {1.2, 3.4, 5.7, 7.5};
sizeArr = sizeof(dArr) / sizeof(double);
res = Find(d1, dArr, sizeArr);         // calls Find<double> by deduction
res = Find<double>(d1, dArr, sizeArr); // calls Find<double> explicitly
 
char* word = "two";
char* arr[] = {"one", "two", "three", "four"};
sizeArr = sizeof(arr) / sizeof(arr[0]);
res = Find<char*>(word, arr, sizeArr);// calls template specialization for char*s
res = Find(word, arr, sizeArr);       // calls overloaded Find for char*s
 
int *px = &x, *pArr[] = {&x, &x};
sizeArr = sizeof(pArr) / sizeof(pArr[0]);
res = Find(px, pArr, sizeArr);    // calls the overloaded Find for pointers
 
SpreadsheetCell c1(10), c2[] = {SpreadsheetCell(4), SpreadsheetCell(10)};
sizeArr = sizeof(c2) / sizeof(c2[0]);
res = Find(c1, c2, sizeArr);    // calls Find<SpreadsheetCell> by deduction
// calls Find<SpreadsheetCell> explicitly
res = Find<SpreadsheetCell>(c1, c2, sizeArr);
 
SpreadsheetCell *pc1 = &c1;
SpreadsheetCell *psa[] = {&c1, &c1};
sizeArr = sizeof(psa) / sizeof(psa[0]);
res = Find(pc1, psa, sizeArr);    // Calls the overloaded Find for pointers

Code snippet from FunctionTemplatePtrFindTemplatePtr.cpp

TEMPLATE RECURSION

Templates in C++ provide capabilities that go far beyond the simple classes and functions you have seen so far in this and the previous 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 which are discussed in Chapter 18. If you skipped that chapter or are unfamiliar with the syntax for overloading operator[], consult Chapter 18 before continuing.

An N-Dimensional Grid: First Attempt

The Grid template example up to now 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 non-template 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(size_t inSize = kDefaultSize);
        OneDGrid(const OneDGrid<T>& src);
        virtual ~OneDGrid();
        OneDGrid<T>& operator(const OneDGrid<T>& rhs);
        void resize(size_t newSize);
        T& operator[](size_t x);
        const T& operator[](size_t x) const;
        size_t getSize() const { return mSize; }
        static const size_t kDefaultSize = 10;
    protected:
        void copyFrom(const OneDGrid<T>& src);
        T* mElems;
        size_t mSize;
};
template <typename T>
OneDGrid<T>::OneDGrid(size_t inSize) : mSize(inSize)
{
    mElems = new T[mSize];
}
template <typename T>
OneDGrid<T>::OneDGrid(const OneDGrid<T>& src)
{
    copyFrom(src);
}
template <typename T>
OneDGrid<T>::~OneDGrid()
{
    delete [] mElems;
    mElems = nullptr;
}
template <typename T>
void OneDGrid<T>::copyFrom(const OneDGrid<T>& src)
{
    mSize = src.mSize;
    mElems = new T[mSize];
    for (size_t 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;
    mElems = nullptr;
    // Copy the new memory.
    copyFrom(rhs);
    return *this;
}
template <typename T>
void OneDGrid<T>::resize(size_t 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 (size_t 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[](size_t x)
{
    return mElems[x];
}
template <typename T>
const T& OneDGrid<T>::operator[](size_t x) const
{
    return mElems[x];
}

Code snippet from OneDGridOneDGrid.h

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;

Code snippet from OneDGridOneDGridTest.cpp

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 in the previous section:

template <typename T, size_t N>
class NDGrid
{
    public:
       NDGrid();
       NDGrid(size_t inSize);
       NDGrid(const NDGrid<T, N>& src);
       virtual ~NDGrid();
       NDGrid<T, N>& operator=(const NDGrid<T, N>& rhs);
        void resize(size_t newSize);
       NDGrid<T, N-1>& operator[](size_t x);
       const NDGrid<T, N-1>& operator[](size_t x) const;
        size_t getSize() const { return mSize; }
        static const size_t kDefaultSize = 10;
    protected:
       void copyFrom(const NDGrid<T, N>& src);
       NDGrid<T, N-1>* mElems;
        size_t mSize;
};

Code snippet from NDGridNDGrid.h

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(size_t inSize = kDefaultSize);
       NDGrid(const NDGrid<T, 1>& src);
        virtual ~NDGrid();
       NDGrid<T, 1>& operator=(const NDGrid<T, 1>& rhs);
        void resize(size_t newSize);
       T& operator[](size_t x);
       const T& operator[](size_t x) const;
        size_t getSize() const { return mSize; }
        static const size_t kDefaultSize = 10;
    protected:
       void copyFrom(const NDGrid<T, 1>& src);
       T* mElems;
        size_t mSize;
};

Code snippet from NDGridNDGrid.h

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.

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, size_t N>
NDGrid<T, N>::NDGrid(size_t 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 (size_t i = 0; i < mSize; i++) {
        mElems[i].resize(inSize);
    }
}
template <typename T, size_t N>
NDGrid<T, N>::NDGrid() : mSize(kDefaultSize)
{
    mElems = new NDGrid<T, N-1>[mSize];
}
template <typename T, size_t N>
NDGrid<T, N>::NDGrid(const NDGrid<T, N>& src)
{
    copyFrom(src);
}
template <typename T, size_t N>
NDGrid<T, N>::~NDGrid()
{
    delete [] mElems;
    mElems = nullptr;
}
template <typename T, size_t N>
void NDGrid<T, N>::copyFrom(const NDGrid<T, N>& src)
{
    mSize = src.mSize;
    mElems = new NDGrid<T, N-1>[mSize];
    for (size_t i = 0; i < mSize; i++) {
        mElems[i] = src.mElems[i];
    }
}
template <typename T, size_t N>
NDGrid<T, N>& NDGrid<T, N>::operator=(const NDGrid<T, N>& rhs)
{
    // Check for self-assignment.
    if (this == &rhs) {
        return *this;
    }
    // Free the old memory.
    delete [] mElems;
    mElems = nullptr;
    // Copy the new memory.
    copyFrom(rhs);
    return *this;
}
template <typename T, size_t N>
void NDGrid<T, N>::resize(size_t 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 (size_t 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, size_t N>
NDGrid<T, N-1>& NDGrid<T, N>::operator[](size_t x)
{
    return mElems[x];
}
template <typename T, size_t N>
const NDGrid<T, N-1>& NDGrid<T, N>::operator[](size_t x) const
{
    return mElems[x];
}

Code snippet from NDGridNDGrid.h

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 non-specialized NDGrid:

template <typename T>
NDGrid<T, 1>::NDGrid(size_t inSize) : mSize(inSize)
{
    mElems = new T[mSize];
}
template <typename T>
NDGrid<T, 1>::NDGrid(const NDGrid<T, 1>& src)
{
    copyFrom(src);
}
template <typename T>
NDGrid<T, 1>::~NDGrid()
{
    delete [] mElems;
    mElems = nullptr;
}
template <typename T>
void NDGrid<T, 1>::copyFrom(const NDGrid<T, 1>& src)
{
    mSize = src.mSize;
    mElems = new T[mSize];
    for (size_t 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;
    mElems = nullptr;
    // Copy the new memory.
    copyFrom(rhs);
    return *this;
}
template <typename T>
void NDGrid<T, 1>::resize(size_t newSize)
{
    T* newElems = new T[newSize];
    for (size_t 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[](size_t x)
{
    return mElems[x];
}
template <typename T>
const T& NDGrid<T, 1>::operator[](size_t x) const
{
    return mElems[x];
}

Code snippet from NDGridNDGrid.h

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;

Code snippet from NDGridNDGridTest.cpp

TYPE INFERENCE

Type inference is new in C++11 and allows the compiler to automatically deduce the exact type of an expression. There are two new keywords for type inference: auto and decltype. Type inference turns out to be very useful in combination with templates. This section goes into more detail on their use in a template context.

The auto Keyword

The new auto keyword has two completely different meanings. The first meaning is to tell the compiler to automatically deduce the type of a variable at compile time. The following line shows the simplest use of the auto keyword in that context:

auto x = 123;    // x will be of type int

In this example you don’t win much by typing auto instead of int; however, it becomes useful for more complicated types. Suppose you have a map that maps an int to a vector of strings:

std::map<int, std::vector<std::string>> m;

Before C++11, if you wanted a constant iterator to the beginning of this map, you had to type the following:

std::map<int, std::vector<std::string>>::const_iterator citer = m.begin();

With the auto keyword it becomes:

auto citer = m.cbegin();

The second use of the auto keyword is when using the new C++11 alternative function syntax, which is mentioned in Chapter 9. Basically, it allows you to put the return type at the end of the function prototype instead of at the beginning. For example, take the following function:

int func(int i)
{
    return i + 2;
}

This can be rewritten by using the alternative function syntax as follows:

auto func(int i) -> int
{
    return i + 2;
}

The auto keyword here has a completely different meaning. It states that this function prototype is using the alternative function syntax. If you look at the preceding example you might think that this alternative function syntax doesn’t really add any new value to the language. However, the new syntax becomes important in the context of templates together with the new decltype keyword, as you will see in the next sections.

The decltype Keyword

The decltype keyword takes an expression as argument, and computes the type of that expression. For example:

int x = 123;
decltype(x) y = 456;

In this example, the compiler will make y of type int because that’s the type of x. Just like the auto keyword for the alternative function syntax, the decltype keyword doesn’t seem to add much value on first sight. However, in the context of templates, auto and decltype become pretty powerful.

auto and decltype with Templates

The use of the auto and decltype keywords in combination with templates is best illustrated with an example. The following example defines two classes: MyInt and MyString. These are simple wrappers for an int and a std::string, respectively. Their constructors accept a single value used for initialization. Both classes also have an operator+ as member method. Here is the header file:

#include <string>
// Forward class declarations
class MyInt;
class MyString;
 
class MyInt
{
    public:
        MyInt(int i) : m_i(i) {}
        MyInt operator+(const MyString& rhs) const;
        int getInt() const { return m_i; }
    protected:
        int m_i;
};
 
class MyString
{
    public:
        MyString(std::string str) : m_str(str) {}
        MyString operator+(const MyInt& rhs) const;
        const std::string& getString() const { return m_str; }
    protected:
        std::string m_str;
};

Code snippet from TypeInferenceTypeInference.h

The implementation is as follows. This code uses two other new features of C++11: stoi() and to_string(), both of them are discussed in the “Numeric Conversions” section in Chapter 14:

MyInt MyInt::operator+(const MyString& rhs) const
{
    return m_i + stoi(rhs.getString());
}
MyString MyString::operator+(const MyInt& rhs) const
{
    string str = m_str;
    str.append(to_string(rhs.getInt()));
    return str;
}