Templates are a relatively new addition to C++. They allow you to write generic classes and functions that work for several different data types. The result is that you can write generic code once and then use it over and over again for many different uses. In fact, C++ comes with something called the Standard Template Library (STL), which makes extensive use of templates to provide powerful data-processing tools to the C++ user.

There are some problems with templates, however. Working out the implementation details was very difficult for the people on the C++ Standards Committee. There was a lot of hard fighting involving tanks, mortars, and heavy artillery (or the academic equivalent, which is a tartly worded memo). As a result, template implementation details were one of the last items in the C++ Standard to be agreed upon. Later in this chapter, we’ll discuss some of the implementation problems with templates.

Suppose we want to define a function max to return the maximum of two items. Actually, we don’t want to define just one max function, but a family of functions: one to find the maximum of two ints, one for floats, one for chars, and so on.

We start by defining a parameterized macro to generate the code for the function. This is called the definition stage . The macro looks like this:

#define define_max(type) type max(type d1, type d2) { 
    if (d1 > d2)                                      
        return (d1);                                  
    return (d2);                                      
}

This macro generates no code. It merely provides the definition that is used in the next phase to generate the functions we want. This is called the generation phase. The following three statements use the define_max macro to generate three versions of the max function:

define_max(int);
define_max(float);
define_max(char);

Finally, somewhere in the code we use the functions we’ve just defined. (This is called the use phase, of course.)

int main(  ) {
    float f = max(3.5, 8.7);
    int   i = max(100, 800);
    char ch = max('A', 'Q'),

Figure 24-1 shows the source code for the #define style templates and the code generated by them.

Figure 24-1. Code generated by #define style templates

This method works adequately for simple functions like max. It doesn’t work well for larger functions. One drawback to this system is that we must invoke the macro define_max for each data type we want to use. It would be nice if C++ called define_max automatically.

Templates allow you to define a generic function. C++ then uses this template to generate a specific instance of the function as needed. For example, to define the function max as a template, we write:

template<typename kind>
kind max(kind d1, kind d2) {
    if (d1 > d2)                                    
        return (d1);                                
    return (d2);                                    
}

This template declaration corresponds to the definition of the parameterized macro. Like the parameterized macro, it generates no code; it merely provides a definition for the next phase.

Now we can use the template much like we used the functions defined by the parameterized macro:

int main(  ) {
    float f = max(3.5, 8.7);
    int   i = max(100, 800);
    char ch = max('A', 'Q'),
    int  i2 = max(600, 200);

You may have noticed that we skipped the generation phase. That’s because C++ automatically performs the generation for us. In other words, C++ looks at the line:

    float f = max(3.5, 8.7);

and sees that it uses the function max (float, float). It then checks to see whether the code for this function has been generated and generates it if necessary. In other words, everything is automatic. (There are practical limits to what can be done automatically, as you will see in the implementation details section.)

Figure 24-2 shows the code generated by the template implementation of max. From this you can see that the first time max is used for a float it generates the floating-point version of max. Next we use max for int, and the int version of max is created. Note that the last line:

    int  i2 = max(600, 200);

does not generate any function. This is because we’ve already generated the integer version max and don’t need to do so again.

Figure 24-2. Template code generation

Templates go a bit further than simple code generation. They can handle special cases as well. Suppose we want to use the function max to compare C style strings as well:

const char *name1 = "Able";
const char *name2 = "Baker";

std::cout << max(name1, name2) << '
';

We have a problem, because C Style strings are represented by a character pointer (char *). The comparison:

if (d1 > d2)

compares the value of the pointers, not the data that’s pointed to. What we want to do is tell C++: “Use the normal comparison except when the data type is a C style string, and then use strcmp.”

This is done through a process called specialization . We declare a special version of the max function just for strings:

char *max(const char *const d1, const char *const d2) {
    if (std::strcmp(d1, d2) > 0)
        return (d1);
    return (d2);
}

When C++ first sees the use of the function max, it looks through the list of simple functions before it looks through its list of templates. Thus when we have:

std::cout << max(name1, name2) << '
';

C++ will find the simple function:

max(const char *const, const char *const)

before trying to expand the template max(kind d1, kind d2).

Example 24-1 illustrates the use of template functions.

#include <iostream>
#include <cstring>

// A template for the "max" function

template<typename kind> 
kind max(kind d1, kind d2) {
    if (d1 > d2)
        return (d1);
    return (d2);
}

// A specialization for the "max" function 
//   because we handle char * a little differently
const char *const max(const char *const d1, const char *const d2) {
    if (std::strcmp(d1, d2) > 0)
        return (d1);
    return (d2);
}

int main(  )
{
    // Let's test out max
    std::cout << "max(1,2) " << max(1,2) << '
';
    std::cout << "max(2,1) " << max(2,1) << '
';

    std::cout << "max("able", "baker") " << 
                  max("able", "baker") << '
';

    std::cout << "max("baker", "able") " << 
                  max("baker", "able") << '
';
    return (0);
}

Class templates are a little more complex than function templates. Declaring them is easy; they are defined just like function templates. Example 24-2 shows the stack class from Chapter 13, written as a template.

#include <cstdlib>
#include <iostream>
#include <cassert>

const int STACK_SIZE = 100;     // Maximum size of a stack

/********************************************************
 * Stack class                                          *
 *                                                      *
 * Member functions                                     *
 *      stack -- initalize the stack.                   *
 *      push -- put an item on the stack.               *
 *      pop -- remove an item from the stack.           *
 ********************************************************/
// The stack itself
template<typename kind>
class stack {
    private:
        int count;              // Number of items in the stack
        kind data[STACK_SIZE];  // The items themselves
    public:
        // Initialize the stack
        stack(  ) {
            count = 0;  // Zero the stack
        }

        // Push an item on the stack
        void push(const kind item) {
            assert(count >= 0);
            assert(count < sizeof(data)/sizeof(data[0]));

            data[count] = item;
            ++count;
        }

        // Pop an item from the stack
        kind pop(  ) {
            // Stack goes down by one
            --count;

            assert(count >= 0);
            assert(count < sizeof(data)/sizeof(data[0]));

            // Then we return the top value
            return (data[count]);
        }
};

There is a problem, however. To use this class we need to declare an instance of it. In the past, we’ve been able to declare a stack with the statement:

stack a_stack;    // This won't work

The problem is that stack is now a generic template. The stack can now contain anything. When C++ sees this declaration, it’s going to ask, “A stack of what?” We must specify the type of data we are storing. The new declaration is:

stack<int> a_stack;    // A stack of integers

The <int> tells C++ to use int for kind throughout the stack. We can now use the new class variable:

a_stack.push(1);
x = a_stack.pop(  );

In the stack class, we defined all the member functions inside the class definition. We could just as well have specified the procedures outside the class. To do so, we must put the template clause template<class kind> in front of each procedure and put the template parameter (<kind>) in the name of the class. For example, the push routine would look like this:

/********************************************************
 * stack::push -- push an item on the stack             *
 *                                                      *
 * Warning: We do not check for overflow                *
 *                                                      *
 * Parameters                                           *
 *      item -- item to put on the stack                *
 ********************************************************/
template<typename kind>
inline void stack<kind>::push(const kind item)
{
    assert(count >= 0);
    assert(count < sizeof(data)/sizeof(data[0]));

    data[count] = item;
    ++count;
}

You can think of a class template such as this:

template <typename kind>stack { ...

as instructions that tell C++ how to generate a set of classes named stack<int>, stack<double>, stack<float>, and so on. C++ will also generate automatically the member functions: stack<int>::push, stack<double>::push, and stack<float>::push.

However, if you explicitly declare a member function yourself, C++ will use your definition before generating its own. Suppose we want to have a stack store C-style strings (char *). We don’t want to store the pointers; we want to store the actual strings. To do this, we need a special version of the push function that duplicates the string before pushing it onto the stack:

inline void stack<char *>::push(const char *const item)
{
    data[count] = std::strdup(item);
    ++count;
}

Note that we didn’t use template<typename kind> at the beginning of the function. The template keyword tells C++, “This is a generic class. Generate specific versions from it.” With no template, we are telling C++, “This is the real thing. Use it directly.”

Now we come to a problem that has vexed most compiler makers, the details of the compilation process. Consider the files that make up Example 24-3. The program defines the following files listed in Examples Example 24-3 through Example 24-6.

class integer 
{
    public:
        int value;

        integer(int i_value): value(i_value) {};

        integer operator * (const integer i2)
        {
            integer result(value * i2.value);
            return (result);
        }
};

template<class integer> extern integer square(const integer value);

#include "square.h"
#include "integer.h"

int main(  )
{
    integer test(5);

    integer test2 = square(test);
    return (0);
}

#include "square.h"

export 
template<class integer> integer square(const interger i)
{
    return (i.value * i.value);
}

Now consider what must happen when we compile these files. We’ll start with file main.cpp. When this file is compiled, the compiler sees that the template function square is used with the class integer. Normally, this would cause it to generate the code for square<integer>. But there is a problem: the body of this function is defined in the file square.cpp, which we are not compiling at this time. The result is that the compiler doesn’t have enough information to generate the template.

But when we compile square.cpp, the compiler knows nothing about the class integer, so it can’t generate the code for square<integer> either.

The C++ Standard has a solution to this problem. The solution is to put the keyword export in front of the definition of the function square in the file square.cpp. This tells the C++ compiler, “This template definition may be used in other files so keep its code around to be expanded in later compilations.”

So the first thing we do is to compile square.cpp. The export directive tells the compiler to save a definition of the function somewhere. Next we compile main.cpp. The compiler sees that we want to generate code for square<integer>, goes to its library of exported templates, looks for the definition square, and uses it to generate the code.

#include "integer.h"

template integer square<integer>(const integer value);

#include "square.h"
#include "integer.h"

template integer square<integer>(const integer i);

template<class number> number square(const number i)
{
    return (i.value * i.value);
}

There are a few advanced template features that are beyond the scope of this book. These include default parameters and partial specialization.

// Half designed
template<class address> class address_list { ... }

// Closer
template<class address, class list> class address_list { .... }

// Closer
template<class address, class list = in_memory_class> 
class address_list { .... }

template<local_address, in_memory_class> small_local_addresses;
template<local_address> small_local_addresses;

// Template definition
template<typename container, typename item> class store {...};

// Partial specilization
template<typename container> class store<container, char *> {...}

template<typename T1, typename T2> class example {....};

template<typename T1> class example<T1, T1> {....};

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

Templates provide a convenient way of writing generic classes and functions. Many compiler makers have not completely implemented this feature, however. As a result, you’ll probably have to play with the compilation switches and some #pragma directives to get things to work.

When you do get templates working, the result can be some very powerful code. An example of this is the Standard Template Library (see Chapter 25).

Exercise 24-1: Write a template min that returns the minimum of two values. Make sure you handle C-style strings correctly.

Exercise 24-2: Write a template class to implement an array with bounds checking.

Exercise 24-3: Define a template class that implements a set. The class allows you to set, clear, and test elements. (An integer version of this class was presented in Exercise 13-4.)