Outline

Problem 1:	(Nearly) identical code
Solution 1:	Generalize functions with parameters for modularity
Problem 2:	Similar functions with different types
Solution 2:	Function templates with type parameters
Problem 3:	Similar classes with different types
Solution 3:	Class templates with type parameters
Using templates:	Putting it into practace

As programmers, we want to maximize the utility of our designs and our code. A common rule of programming is: “If you write the same code in two places, make a function that you can define once and call many times.” (See also the DRY principle.)

We'll see below that C++ allows us to write code that can work for any (or almost any) type. Code that can work for multiple types is called polymorphic. Code that can work for any type at all is universally polymorphic or generic.

Problem 1: (Neary) identical code

If you were working with arrays of 10 integers, you might write the following useful function for printing out the arrays:

void printArray10(int data[])
{
        cout << '[';
        for (int i = 0; i < 10; ++i) {
                cout << data[i];
                if (i != 9)
                        cout << ", ";
        }
        cout << ']';
}
        

After a while, though, you may find you have an array with more than 10 elements. You could write another function for handling, say, arrays of 25 elements:

void printArray25(int data[])
{
        cout << '[';
        for (int i = 0; i < 25; ++i) {
                cout << data[i];
                if (i != 24)
                        cout << ", ";
        }
        cout << ']';
}
        

If you did, you would hopefully realize that you've written almost exactly the same code before. Everything is the same except for the parts marked in red above: the name of the function is different (because we have to give the two functions different names), and the actual number for the array length is different.

Not only that, there is good reason to believe that if you could generalize this function, you could just write it once and then use it on arrays of any size.

Solution 1: Generalize functions with parameters for greater modularity

The solution, as you've already seen many times, is to generalize the function by using a parameter to stand for the parts that vary:

void printArray(int data[], int length)
{
        cout << '[';
        for (int i = 0; i < length; ++i) {
                cout << data[i];
                if (i != length - 1)
                        cout << ", ";
        }
        cout << ']';
}
        

Now you can write the function once and call it for any integer array!

You have certianly done this many, many times, and not just for arrays. In earlier homework, you've written functions that could either use cin or another input file stream. Hopefully, you wrote just one function that took the stream as a parameter rather than write the same function twice.

Problem 2: Similar functions with different types

Now suppose that you have a program that uses arrays of strings. Now you would need to do this:

void printIntArray(int data[], int length)
{
        cout << '[';
        for (int i = 0; i < length; ++i) {
                cout << data[i];
                if (i != length - 1)
                        cout << ", ";
        }
        cout << ']';
}

void printStringArray(string data[], int length)
{
        cout << '[';
        for (int i = 0; i < length; ++i) {
                cout << data[i];
                if (i != length - 1)
                        cout << ", ";
        }
        cout << ']';
}
        

Again, notice the code is virtually identical. The only difference is that the type is different. Otherwise, the function doesn't care what the data type is, as long as the << operator knows how to format elements of that type for printing.

If only there were a way to have a parameter for the type …

Solution 2: Function templates with type parameters

There is! That's what C++ templates are for. They allow you to generalize program code over types. (You can generalize over other things, too, but we're looking at types now.)

Program code that can operate over elements of any type is said to be generic or universally polymorphic. Here's how it works in C++. You make a function template by writing this line before the function:

template <typename TypeVariable>

and then you replace all the types that you want to generalize over with TypeVariable, like this:

template <typename ElemType>
void printArray(ElemType data[], int length)
{
        cout << '[';
        for (int i = 0; i < length; ++i) {
                cout << data[i];
                if (i != length - 1)
                        cout << ", ";
        }
        cout << ']';
}
        

Then you can use the function on arrays of different types, as long as C++ knows how to print them. To use the function, you can specialize the template to a particular type by providing a template argument like this: printArray<int>(intData, length), but, if the type is evident from the parameter types, C++ can figure it out:

int    intData[]    = {1, 2, 3, 4, 5};
string stringData[] = {"a", "b"};
        ⋮
printArray(intData, 5);
cout << endl;
printArray(stringData, 2);
cout << endl;
        

Try the code yourself!

A template, as the name implies, is not actually a function definition. It's a pattern that can be used to make a function definition. When you use (specialize) a template, C++ will instantiate the template for whatever type(s) you're using it for. In the above examples, C++ will put in two different function definitions, one with ElemType replaced with int, and the other with ElemType replaced with string.

Notes:

• The keyword typename can be replaced with the keyword class, which I'm told is the more standard keyword. C++ treats them as synonyms. Either way, as our example shows, a template variable (ElemTepe above), can be replaced with either a primitive type, a class name, a struct, enum, union — any type is accepted.
• A template can be instantiated for any types that “make sense.” That is, the code is just copied. If << doesn't know how to print the type, then you'll get a compile-time error. Similarly if you compare types or use assignment on a type for which the operation is not defined, you'll get an error.
• A template is not limited to just one type parameter. You can have any number of type parameters separated by commas: template <typename A, typename B> will start a template with two type parameters.

Exercises:

1. Write a template function named minimum that will return the smaller (minimum) of two elements of any type, provided the type allows elements to be compared with <.
2. Write a templated selection sort function that can sort an array of elements of any type, as long as elements of that type can be compared. You may define a (template) helper function if you like.
3. True or false: Type variables must be instantiated with the name of a class.

Problem 3: Similar classes with different types

You've already seen examples in which you've implemented a class that is a container for some type of element, only to implement the class again for some other type. You've done integer sequences, pirate sequences, string sequences. You've seen linked lists, stacks, queues, trees, etc., and all of these containers can, in principle, be used with any type of data.

For example, we might want a simple queue implementation that uses a circular buffer. If we wanted to store integers in the queue, we could use the implementation on the left. If we had a struct or class called Dog that we wanted to put into a queue, we could use the implementation on the right. (Please note: To keep the example brief, the queues don't expand and don't do any error checking! They also don't implement copy constructors or assignment operators.)

class IntQueue { public: IntQueue(int the_capacity = 10); ~IntQueue(); void enqueue(int value); int dequeue(); bool is_full(); bool is_empty(); private: int capacity, size; int front, back; int *queue; int next_index(int idx); }; IntQueue::IntQueue(int the_capacity) { capacity = the_capacity; size = 0; front = 0; back = 0; queue = new int[capacity]; } IntQueue::~IntQueue() { delete [] queue; queue = nullptr; capacity = size = front = back = 0; } void IntQueue::enqueue(int value) { enforce(not is_full(), "enqueue on full queue"); queue[back] = value; back = next_index(back); size += 1; } int IntQueue::dequeue() { enforce(not is_empty(), "dequeue from empty queue"); int result_idx = front; front = next_index(front); size -= 1; return queue[result_idx]; } bool IntQueue::is_full() { return size == capacity; } bool IntQueue::is_empty() { return size == 0; } int IntQueue::next_index(int n) { return (n + 1) % capacity; } static void enforce(bool condition, string message) { if (not condition) throw runtime_error(message); }

class DogQueue { public: DogQueue(int the_capacity = 10); ~DogQueue(); void enqueue(Dog value); Dog dequeue(); bool is_full(); bool is_empty(); private: int capacity, size; int front, back; Dog *queue; int next_index(int idx); }; DogQueue::DogQueue(int the_capacity) { capacity = the_capacity; size = 0; front = 0; back = 0; queue = new Dog[capacity]; } DogQueue::~DogQueue() { delete [] queue; queue = nullptr; capacity = size = front = back = 0; } void DogQueue::enqueue(Dog value) { enforce(not is_full(), "enqueue on full queue"); queue[back] = value; back = next_index(back); size += 1; } Dog DogQueue::dequeue() { enforce(not is_empty(), "dequeue from empty queue"); int result_idx = front; front = next_index(front); size -= 1; return queue[result_idx]; } bool DogQueue::is_full() { return size == capacity; } bool DogQueue::is_empty() { return size == 0; } int DogQueue::next_index(int n) { return (n + 1) % capacity; } static void enforce(bool condition, string message) { if (not condition) throw runtime_error(message); }

Notice again that the only differences between these two classes are the those highlighted in red above. The implemenations don't rely on any essential properties of the type of item in the queue.

They do assume that, if the type is a struct/class, it has a nullary constructor (called on array allocation), it can be copied for call and return by value, and that it can be assigned when stored in the array.

Any type with these properties can be supported.

Solution 3: Class templates with type parameters

We can generalize the code above to make one class definition that can be used for types (that meet the assumptions given above) using templates!

The idea is exactly the same as before: Pick a name for the thing that varies, and wrap the definitions in a template. We have to do this for both the class definition and for all of the member functions. The syntax can be a bit ugly, but it works:

Queue.h

Notice how the member functions have Queue<ElemType>:: attached. C++ will instantiate the entire class and any member functions that get used at every type the client code uses it for.

How can we use such a class? Just as you've seen with the STL, you say what type you want the element type to be whenever you declare an instance of the type. For example, we could define the following variables:

#include<Queue.h>

        ⋮
        Queue<int> integer_queue;
        Queue<Dog> dog_queue;
        ⋮
        

You can seen an entire program that uses this queue implementation on integers and dogs in testQueue.cpp.

You can compile the above file like this:

clang++ -Wall -Wextra -g    testQueue.cpp   -o testQueue
        

Note that you can have more than one type name defined in a template:

template<typename FirstType, typename SecondType>
struct Pair
{
        FirstType  first;
        SecondType second;
};
        

The above is a template for a heterogeneous pair.

Using templates: Putting it into practice

This is where the bad news is.

Because C++ needs the full template definition so it can instantiate it at any specific type, you can't actually separately compile your function or class template implementations. Sad.

The horror: You have to put everything in the include file. That's right, the declarations and implementations all go in the .h file. Notice that our whole queue implementation above is in Queue.h and that it therefore is copied, in its entirety, into testQueue.cpp.

Another downside to using templates is that error messages will reference tons of things in the templates. If, for example, you try to make a binary search tree: BST<Kangaroo> and Kangaroos can't be compared with <, etc., then you'll get tons of messages about the templated code lines that compare kangaroos. The result is an avalanche of messages all about code you've never seen before (except, perhaps, in other error message disasters). You've seen some of these from the I/O facilities and from the STL, because their include files include all their templated definitions.

It's important to document any assumptions your template code makes for this reason, and don't forget that you can't just assume that copying and assignment work — if you need that to work, then you must document it!

But templates do give us a powerful way to write more modular code!

Key items:

• I strongly recommend that, if you want to make a templated class, you first write and thorougly test a non-template version for some particular type. Perhaps one version for a base type (like int) and one for a struct. Error messages involving templates are pretty nasty, and uninstantiated code won't actually be type checked. So have at least one working monomorphic (works only for one type) version before you go to templates.
• You can make the above easier to transition to templates if you use a type definition:

  typedef Dog ElemType;

  will make ElemType be another name for Dog. You can test your code like that, then switch the type definition to another type, like int. If that works, then you're in good shape to make templates.
• Put the entire implementation in the .h file. For namespace control reasons, I often move non-class helper functions into the class (as with the enforce function above). Again, do that with a monomorphic (untemplated) version before you use templates.

  You will sometimes see include files for templates use the .hpp suffix to make it clear it has all the code.

• Once you have a templated version, you need to document what requirements you have placed on the types. Do you compare elements with ==, for example? Do you assume the type is printable? Do you pass or return elements by value (requires a copy constructor for class types)? List all these constraints in the documentation so clients have a checklist.