C++ Programming
Templates
03 April 2002
by Scott Robert Ladd
An algorithm is defined by what it does as opposed to what it acts upon. Conceptually, algorithms are a lot like wrenches: If I have a fixed-size crescent wrench, it may be stronger and simpler than my adjustable wrench; the adjustable wrench, however, is useful in more situations and with a wider variety of nuts.
In terms of software, writing a custom QuickSort for longs will result in a very tight, efficient tool -- but it is an inflexible tool that must be modified by hand for every other data type. The QuickSort algorithm orders data; the nature of the data-strings, numbers, database records is unimportant to how QuickSort works. By implementing an "adjustable" QuickSort, a programmer builds a single tool that is useful in many situations. Templates let you define flexible and generic algorithms, the adjustable wrenches of software development.
To see the power of templates, review the Standard C++ library: nearly every class is implemented as a template, from strings to containers to data streams. Flexiblity and power, however, come with complexity; templates are perhaps the most confusing and misunderstood concept in Standard C++.
Function Templates
If you want to create a set of C++ functions for performing an operation on a variety of data types, the obvious solution is to use function overloading. If I need functions to calculate the squares of int and float values, I could define these two functions:
int Square(int x) { return x * x; };
float Square(float x) { return x * x; }
For each data type that I want to square, I create a new Square function. The C++ compiler determines which function to call based on the argument passed to Square.
int i = 2; float f = 12.53; int isq = Square(i); // call Square(int) float fsq = Square(f); // call Square(float)
What's bothersome is the similarity of these functions. The actual code doesn't change; the only difference between the Square functions is their header. I could use a C-type macro function
#define Square(x) (x * x)
But function macros have their drawbacks. To begin with, a macro doesn't check the type of its arguments; type-checking is a fundamental component of object-oriented programming. Also, macros always generate inline code; for a complex calculation, having a callable function for each data type reduces program size significantly. Wouldn't it be nice if I could just create one function that says "square any type of number", and leave it to the compiler to generate appropriate code for the data types I use? Not only would it be nice, it is nice, for C++ offers just such a facility in function templates.
A function template describes a type of function rather than a specific function. Instead of creating a Square function for every numeric data type, I can create a function template like this:
template <class T> T Square(T x) { return x * x; };
A function template describes a set of similar functions to the compiler. The template above tells the compiler, "Here's a template for a function named Square. It has a single argument of class T, and returns a class T value. When a statement calling Square is encountered, generate a Square function that replaces T with the class of the argument." With a simple definition like this, we might want the code compiled inline -- and templates, unlike macros, give us a choice in the matter. Add the inline keyword to the definition of Square, and the compiler will generate inline code as it sees fit
The inline keyword is a suggestion to the compiler, and not an absolute directive. A simple function like Square is almost certainly going to be inlined by any competent compiler; more complex functions may, however, be generated as functions at the compiler's whim.
A template treats the intrinsic types (float, int, etc.) as classes. For example, this code
int i1 = 2; int i2 = Square(i1);
causes the compiler to generate a function like this
int Square(int x) { return x * x; }
The compiler only generates code for those data types used in calls to the template function. If you add a new class -- perhaps for complex or rational numbers -- those types will automatically be supported by the template for Square. The only stipulation is that the data type used in calling a template function support the operations performed in the function body. For example, this code would generate a compile-time error
char * x = "Dance"; char * y = Square(x);
Unless you've defined the binary * operator for char *'s, this piece of code will not compile.
A template may have more than one generic argument, and it can have additional arguments with a specific type.
template <class A, class B>
void MyFunc(A arga, B argb, int i)
{
// do something with the three arguments
};
The first two arguments in a call to MyFunc may have the same or different types. The third argument is always treated as an int.
Templates generate inline functions if the function header is prefaced with the inline keyword. It's also possible to overload a template-generated function with a non-template function. The compiler begins resolving an overload by attempting to match a function call's arguments with those of existing (non-template) functions; if the compiler doesn't find a match, it generates a new function from the template.
Class Templates
A class template tells the compiler how to construct a series of similar classes. I view class templates as forms, with the compiler filling in the blanks based on the template arguments.
Class templates excel as tools for defining containers. Here's an example of a flexible record type that contains both a key value and data:
template <class K, class D>
class Record
{
public:
Record(K kx, D dx)
{
Key = kx;
Data = dx;
}
K GetKey()
{
return Key;
}
D GetData()
{
return Data;
}
private:
K Key;
D Data;
};
When the compiler encounters a template, it creates a general definition from which it can build specific types, as required. The compiler generates type-specific versions of Record only when it needs to; as with function templates, a class template does not produce any code until it is used for a specific type. For instance, the declaration
Record<int, String> recis;
causes the compiler to generate a Record<int, String> class equivalent to
class Record
{
public:
Record(int kx, String dx)
{
Key = kx;
Data = dx;
}
int GetKey()
{
return Key;
}
String GetData()
{
return Data;
}
private:
int Key;
String Data;
};
If I also declare a Record<long,double> object, the compiler generates another class definition. I can create a Record class for any types K and D, all based on a single common template.
Each class created from a template has its own static members, functions, and data members; the more classes you create from templates, the larger your programs will become. Most of your templates will be defined in header files, to be included into each source module in which you use that class. Even with precompiled headers, instantiating numerous template types can increase compile times significantly.
Specializations
In Standard C++, you can define a specialization of a class template, which will then create compile-time code for later linking. Above, I define a Record function template; once that definition exists, I can specialize it for int keys and long data with another template
class Record<int, long>
{
public:
Record(int kx, long dx)
{
Key = kx;
Data = dx;
}
int GetKey()
{
return Key;
}
long GetData()
{
return Data;
}
private:
int Key;
long Data;
};
In the compiler's eyes, Record<int,long> is a specific implementation of the Record class template, to be used when any Record<int,long> object is encountered in the program. The Standard C++ library defines several specializations, including complex<float>, complex<double> and complex<long double> for the complex<class T> class template. Rules for specializations include:
template <class T = int> class Thingy { // ... };
// this specialization is invalid
class Thingy<int> { // ... };
A specialization must provide constructors, destructors, copy constructors, assignment operators, and other methods equivalent to those defined by the primary class template.
Scoping Issues
Members defined outside of the class template definition need to be templates themselves, and class scope identifiers must contain template arguments. If I were to move the Record contructor outside its class definition, I would define it like this:
template <class K, class D>
Record<K,D>::Record(K kx, D dx)
{
Key = kx;
Data = dx;
}
References to the class type inside the template do not need to be qualified with template arguments, since they are implied by the template.
Templates can be derived from other templates. For example, an Object class template can be based upon a Record class template
template <class D> class Object : Record<int, D> { . . . };
A typedef statement can define an alias for a template type, thus eliminating the need to specify arguments in angle brackets. typedef StdRecord Record<int,int>; It's also possible to define a template type using another template type as an argument.
Record< long,Object<String,double> > rec;
Note the extra spaces used to keep the compiler from seeing >> as the right shift operator.
Template Parameters
Template arguments need not be class names; template parameters may provide values. For example, most buffer implementations look something like this:
class Buffer
{
public:
Buffer(size_t len);
private:
char * data;
};
Buffer::Buffer(size_t len)
{
data = new char[len];
}
A template could provide the size of the buffer as part of the class definition, allowing the buffer to be statically allocated rather than requiring a call to new.
template <size_t Len>
class Buffer
{
public:
Buffer();
private:
char data[Len];
};
This definition enables you to allocate a specific-size buffer like this
Buffer<128> buf;
Default values for template arguments let you create a default version of a class:
template <size_t Len = 128>
class Buffer
{
public:
Buffer();
private:
char data[Len];
};
Now, you can allocate a default-size buffer like this
Buffer buf; // equivalent to: Buffer<128> buf;
Advanced Template Techniques
Andrei Alexandrescu written an interesting book, Modern C++ Design, that demonstrates complex uses for templates in pattern-based software development. I urge you to read his book, just to see the true creativity and power of the template mechanism; he's taken templates where the language's designers never meant them to go.
E-mail
LinkedIn
Facebook
•• HIRE SCOTT ••
Computer Books
Fiction
Articles
Reviews
FAQ
Bibliography
© 2010
Scott Robert Ladd
All rights reserved.
Established 1996
The grey-and-purple dragon logo, the blue coyote logo, Coyote Gulch Productions, Itzam, Evocosm, and Acovea are all Trademarks of Scott Robert Ladd.
Privacy Policy
Legal Stuff