Nicholas is a software engineer working in the Boston area. His interests include computer graphics, C++, and assembler programming. He can be reached through the DDJ offices.
Templates are one of C++'s most powerful features in that they allow you to define the "shape" of a function or class and leave the implementation specifics to the compiler.
Function templates can be used to describe algorithms defined on a wide variety of types. By using a function template to define a sorting algorithm, for example, the type to sort is left as a parameter. Then, whenever the template is invoked, a sort function for that type is generated by the compiler.
Class templates can be used to define a class's structure in terms of the template arguments. For every different set of template arguments given to a class template, the compiler creates a new class. This is an especially useful feature for container classes; when you define a class template for BinaryTree, for example, it becomes easy to declare BinaryTree of int, float, or a user-defined type.
Compared to the way C++ handles inheritance and polymorphism, templates are relatively simple, especially once you come to grips with their syntax. The examples in this article were developed with Borland C++ 3.0, but with a minimum of effort they should work with other C++ implementations that support templates.
Selection, like sorting, is defined on all ordered types. Selection takes an array of N elements and an index i, and returns the ith element in the sorted order of the array. To compute the median of an N-element input array, for example, you select the element represented by N/2. The minimum is selection of the 0th element; the maximum is selection of the element represented by (N - 1). (Note that arrays are numbered from 0.)
Given the definition of the selection problem and its relation to the sorted order of the array, programmers often make the mistake of performing selection by sorting the array, then returning the ith element. This technique works, but it does more work than needed. It is more efficient to repeatedly partition the array and consider only the partition that contains the ith element. A good discussion of a randomized, expected linear time-selection algorithm is presented in Introduction to Algorithms by Thomas Cormen, Charles Leiserson, and Ronald Rivest (MIT Press, 1990). This algorithm is usually more efficient than one that sorts the input array.
In pretemplate C++, there were two (unattractive) alternatives for implementing selection:
The variety approach is equally unattractive because it involves code duplication. Errors are likely to be introduced during code duplication, and errors in the routine itself get propagated across all the routines.
Templates offer a solution that resolves both concerns. By allowing you to write the function once in a general form, they enforce type safety and avoid source-code duplication.
To declare a function template, you write something like Example 1. Listing One (page 32) shows an implementation of selection that uses templates. Our template-based Select function is defined in Example 2(a). The resulting code looks remarkably similar to the pseudocode found in textbooks on algorithms. Select is a function that returns the ith element of an array of Ts. What are Ts? Ts are anything that can be sorted! They are a parameter of the function template.
template<template parameters>
return value // From here on we define
name (function parameters) { // the function in terms of
function body // the template parameters.
}
(a)
template<class T> T
Select(T *base, int n, int i)
{
// Implementation
}
(b)
int *arr, n;
// ... allocate array and set n
// Set penultimate to the second-largest element in arr.
int penultimate = Select(arr, n, n - 2);
(c)
int
Select(int *x, int n, int i)
{
// Own function definition of Select<int>
}
To use Select, just call it with a pointer to an ordered type. To select the second-largest element in an array of integers, for example, call Select, as shown in Example 2(b). Since Select uses the < operator to determine how to order the array, operator < must be defined for the class passed to Select. Operator < is built in for primitive types such as ints and floats, so we did not need to do anything special to select from an array of integers.
Calling the template-based Select function is like invoking a macro. Earlier, we called Select with a pointer to int. This tells the compiler we need an instance of Select with T set to int. As with a macro invocation, the compiler replaces each mention of T (the name of the template parameter) with int. The resulting instance of Select takes an int* parameter, declares local instances of int, uses the integer < operator to compare elements in the input array, and returns int.
If the user were to call Select with a float* parameter, the compiler would create an instance of Select taking parameters (float*, const int, int) and replace T with float everywhere in the function declaration. This function instance is distinct from the one for integers; the entry point, parameters, and code generated are completely separate. In the executable, the only thing the two functions int Select(int*, const int, int) and float Select(float*, const int, int) have in common is that they both perform selection.
What happens if you define your own Select function with the same parameters as an instance of the Select template? If you were to define, say, Example 2(c), then the Select template would no longer be invoked for integers. Instead, the user-defined Select function will be used.
Select can be used on arrays of user-defined classes (let's call them MyClass), as well as on built-in types. Just pass a pointer to the array of MyClass you want to select from, making sure operator < is defined for MyClass.
Listing Two (page 32) illustrates the use of Select. It has an example of selecting on arrays of a user-defined class, as well as the built-in int type.
You can specify templates for classes as well as functions. The most common use for a class template is a container class such as a linked list or binary heap. Let's take binary trees as an example. A binary tree can contain any ordered type, so you can have binary trees of integers, floating-point numbers, or other objects. In C++ without templates, you have two choices for implementing a binary-tree class: Implement a generalized BinaryTree class that takes a generic representation of the objects to manipulate, or implement a specific BinaryTree class for each type of object you wish to put in a binary tree.
These are the same problems faced by the selection example given earlier. A method that combines the best of both worlds (without templates) is to implement a generalized class, then derive "Binary tree of integer," "Binary tree of float," and so on from the base binary-tree class and make sure the member functions of the derived classes are type-safe.
Templates provide a better approach. By specifying the template for a BinaryTree class, you can define the class in terms of the template parameters. Thus, a parameterized binary tree-node class can be defined, as in Example 3(a). Note that the above definition is not of a class. There is no class called BinaryNode; BinaryNode is merely a template describing a family of classes. This family of classes has names like BinaryNode<int>, BinaryNode<float>, BinaryNode<UserDefinedType>, and so on, and every one of them is distinct. That is why the left and right pointers in the class definition in Example 3(a) are pointers to BinaryNode<T>, rather than pointers to BinaryNode.
(a)
template<class T>
class BinaryNode {
T x; // Contents of node
BinaryNode<T> *left, *right; // Left and right children
//etc.
};
(b)
// Class template for a binary tree node including a
// pointer to the parent.
template<class T>
class BinaryNodeWithParent : public BinaryNode<T> {
BinaryNodeWithParent<T> *parent;
// etc.
};
(c)
template<class T, int Size>
class Vector {
T x[Size]; // Vector contains Size T's.
// etc.
};
Classes generated from templates can be used as base classes; in fact, class templates can inherit from other class templates. By extending the BinaryNode example, we might have Example 3(b). Listing Three (page 32) gives a minimal template-based BinaryTree class. The binary-tree data structure is described in any good algorithms text; it supports a variety of operations on ordered types in logarithmic time on average. Our BinaryTree class supports insertion, traversal, and query. Although many other operations are defined on binary trees, they are omitted for lack of space. It may be instructive to extend our BinaryTree class to support other operations such as minimum, maximum, and deletion.
Listing Four (page 33) is a typical C++ program that uses the BinaryTree class. It simply insert ten random numbers in the range [0,99] into a BinaryTree <int>, then displays the pre-, in-, and post-order traversal orders of the tree.
Unfortunately, we have concentrated on the most common type of template, which takes a single class parameter. There can be multiple template parameters, and they need not be general classes. A vector class might take two parameters: the type to be a vector of and the number of elements in the vector; see Example 3(c).
The class template described here could reuse code for two-element vectors of integer (perhaps for screen coordinates in a graphics program) and three-element vectors of float (perhaps for world coordinates in a three-dimensional sketching program).
Templates open up a whole new world for C++ programmers. They allow for compact and efficient implementation of container classes and other parameterized types. They also allow general, efficient implementation of algorithms with a minimum of code duplication. Look for C++ class libraries to change dramatically as templates become widely supported. Many of the current approaches to flexibility are based on inheritance and have become outmoded with the advent of templates.
_TEMPLATES IN C++_ by Nicholas Wilt[LISTING ONE]
// select.h -- Template-based C++ implementation of the randomized
// selection algorithm from _Introduction to Algorithms_ by Cormen,
// Leiserson and Rivest (pg. 187). Copyright (C) 1992 by Nicholas Wilt.
// All rights reserved.
template<class T> T
Select(T *base, const int n, int inx)
{
int left = 0;
int right = n;
// This while loop terminates when base[left..right]
// defines a 1-element array.
while (right != left + 1) {
// Partition about the q'th element of the array
int q = left + rand() % (right - left);
T t = base[q];
base[q] = base[left];
base[left] = t;
// Partition about base[left]; all elements less than
// base[left] get swapped into the left-hand side of
// the array.
int i = left - 1;
int j = right;
while (j >= i) {
while (j > 0 && t < base[--j]);
while (i < (right-1) && base[++i] < t);
if (i < j) {
T t = base[i];
base[i] = base[j];
base[j] = t;
}
}
// Now focus attention on the partition containing
// the order statistic we're interested in.
if (inx <= j - left)
// Throw away the right-hand partition; we know it
// doesn't contain the i'th order statistic.
right = j + 1;
else {
// Throw away the left-hand partition; we know it
// doesn't contain the i'th order statistic.
// Now we're looking for the inx - j - left + 1'th
// order statistic of the right-hand partition.
inx -= j - left + 1;
left = j + 1;
}
}
// base[left] is the element we want, return it.
return base[left];
}
[LISTING TWO]
// select.cpp -- Demonstrates the use of the Select function template on
// arrays of integers and Point2D's. It generates a random of array of
// integers, then enumerates the order statistics from 0..n-1. This will
// print out the members of the array in sorted order. This isn't a
// suggestion for how to use Select (obviously it's more efficient to sort
// the array if you want to print out the members in sorted order!) but it's
// good to enumerate them all to verify that algorithm is working properly.
// The other class the program deals with is a used-defined Point2D class.
// This is a two-dimensional point defined by two floating-point numbers.
// The ordering chosen, defined by the operator< for the class, is a
// standard topological ordering from computational geometry.
// Copyright (C) 1992 by Nicholas Wilt. All rights reserved.
#include <fstream.h>
#include <iomanip.h>
#include <stdlib.h>
#include "select.h"
// Just for fun, here's a signum template function. Returns -1 if a < b; 1 if
// b < a; 0 if they're equal. I've ensured only operator< is used for
// comparisons, so operator> isn't defined for a user-defined class.
template<class T> int
Signum(T a, T b)
{
if (a < b) return -1;
else if (b < a) return 1;
else return 0;
}
class Point2D {
double x, y;
public:
Point2D() { }
Point2D(double X, double Y): x(X), y(Y) { }
// operator< makes our points sorted in topological order: increasing order
// in x, and increasing order in y if there is a tie in x.
friend int operator<(const Point2D& x, const Point2D& y) {
int ret = Signum(x.x, y.x);
return (ret) ? ret < 0 : Signum(x.y, y.y) < 0;
}
friend ostream& operator<< (ostream& a, Point2D& b) {
a << "(" << b.x << ", " << b.y << ")";
return a;
}
};
// Number of elements to allocate in the test arrays
const int NumInts = 10;
const int NumPts = 5;
int
main()
{
int *x = new int[NumInts];
int i;
for (i = 0; i < NumInts; i++) {
x[i] = rand() % 100;
cout << x[i] << ' ';
}
cout << '\n';
for (i = 0; i < NumInts; i++) {
cout << Select(x, NumInts, i) << ' ';
}
cout << '\n';
delete x;
Point2D *y = new Point2D[NumPts];
cout << setprecision(2);
for (i = 0; i < NumPts; i++) {
y[i] = Point2D( (double) rand() * 10.0 / RAND_MAX,
(double) rand() * 10.0 / RAND_MAX);
cout << y[i] << ' ';
}
cout << '\n';
for (i = 0; i < NumPts; i++) {
cout << Select(y, NumPts, i) << ' ';
}
cout << '\n';
return 0;
}
[LISTING THREE]
// bintree.h -- Header file for simple binary tree class template.
// Copyright (C) 1992 by Nicholas Wilt. All rights reserved.
// BinaryNode is a helper class template for the BinaryTree class template. It
// should be needed only rarely by the end user of the BinaryTree class, if
// ever. BinaryTree<T> is BinaryNode<T>'s friend. The only other classes that
// can access BinaryNode's data are classes for which it is a base class.
template<class T>
class BinaryNode {
protected:
T x;
BinaryNode<T> *left, *right;
public:
BinaryNode(const T& X): x(X) {
left = right = 0;
}
BinaryNode(const T& X, BinaryNode<T> *l, BinaryNode<T> *r): x(X) {
left = l;
right = r;
}
friend class BinaryTree<T>;
}
// BinaryTree manipulates binary trees described by pointers to BinaryNode.
template<class T>
class BinaryTree {
protected:
// Pointer to the root node of the binary tree.
BinaryNode<T> *root;
// Various functions to manipulate collections of binary
// tree nodes. These are the functions that do the real work.
static BinaryNode<T> *InsertNode(BinaryNode<T> *r, T x);
static BinaryNode<T> *DupNode(BinaryNode<T> *r);
static void PostOrderDeletion(BinaryNode<T> *r);
static T *QueryNode(BinaryNode<T> *r, const T& x);
static void PreOrderNode(BinaryNode<T> *r, void (*f)(T *));
static void InOrderNode(BinaryNode<T> *r, void (*f)(T *));
static void PostOrderNode(BinaryNode<T> *r, void (*f)(T *));
public:
// Constructors and assignment operator
BinaryTree() { root = 0; }
// Copy constructor duplicates all the nodes in the tree.
BinaryTree(BinaryTree<T>& x) { root = DupNode(x.root); }
// Assignment operator deletes nodes already there, then
// copies the ones in the tree to be copied.
BinaryTree<T>& operator=(const BinaryTree<T>& x) {
PostOrderDeletion(root);
root = DupNode(x.root);
return *this;
}
// Destructor frees all the nodes in the binary tree.
~BinaryTree() { PostOrderDeletion(root); }
// Inserts a node containing x into the binary tree.
void Insert(const T& x) { root = InsertNode(root, x); }
// Returns a pointer to node equal to x, if in tree.
// If none found Query returns 0.
T *Query(const T& x) { return QueryNode(root, x); }
// Various traversal functions perform the traversal
// in the order given and call f with a pointer to the
// node contents when visiting.
void PreOrder(void (*f)(T *)) { PreOrderNode(root, f); }
void InOrder(void (*f)(T *)) { InOrderNode(root, f); }
void PostOrder(void (*f)(T *)) { PostOrderNode(root, f); }
};
// The following function declarations give examples of how to
// write function templates for member functions.
// Deletes the tree pointed to by r.
template<class T> void
BinaryTree<T>::PostOrderDeletion(BinaryNode<T> *r)
{
if (r) {
PostOrderDeletion(r->left);
PostOrderDeletion(r->right);
delete r;
}
}
// Inserts a node with key x into the binary tree with the
// root given, and returns the new root.
template<class T> BinaryNode<T> *
BinaryTree<T>::InsertNode(BinaryNode<T> *r, T x)
{
if (r) {
if (x < r->x)
r->left = InsertNode(r->left, x);
else
r->right = InsertNode(r->right, x);
}
else
r = new BinaryNode<T>(x);
return r;
}
// Duplicates the binary tree given and returns pointer to the new root.
template<class T> BinaryNode<T> *
BinaryTree<T>::DupNode(BinaryNode<T> *r)
{
if (r)
return new BinaryNode<T>(r->x,
DupNode(r->left),
DupNode(r->right));
else
return 0;
}
// Returns pointer to key given, if found in binary tree. Otherwise returns 0.
template<class T> T *
BinaryTree<T>::QueryNode(BinaryNode<T> *r, const T& x)
{
if (r) {
if (x == r->x)
return &r->x;
if (x < r->x) return QueryNode(r->left, x);
else return QueryNode(r->right, x);
}
else
return 0;
}
// Traversal functions. These three functions traverse the tree and call the
// pointer to function on the node contents when it's time to visit the node.
template<class T> void
BinaryTree<T>::PreOrderNode(BinaryNode<T> *r, void (*f)(T *))
{
if (r) {
(*f)(&r->x);
PreOrderNode(r->left, f);
PreOrderNode(r->right, f);
}
}
template<class T> void
BinaryTree<T>::InOrderNode(BinaryNode<T> *r, void (*f)(T *))
{
if (r) {
InOrderNode(r->left, f);
(*f)(&r->x);
InOrderNode(r->right, f);
}
}
template<class T> void
BinaryTree<T>::PostOrderNode(BinaryNode<T> *r, void (*f)(T *))
{
if (r) {
PostOrderNode(r->left, f);
PostOrderNode(r->right, f);
(*f)(&r->x);
}
}
[LISTING FOUR]
// bintree.cpp -- Demonstration program for BinaryTree class template. Inserts
// 10 random numbers into a BinaryTree<int>, prints them out and then prints
// out the pre-, in- and post-order traversals of the resulting binary tree.
// Copyright (C) 1992 by Nicholas Wilt. All rights reserved.
#include <iostream.h>
#include <stdlib.h>
#include <alloc.h>
#include "bintree.h"
// Passed to BinaryTree<int> traversal functions. This gets called with a
// pointer to the node contents (int in this case, since it's a
// BinaryTree<int>) whenever it's time to visit a node in the tree.
void
PrintInt(int *x)
{
cout << *x << ' ';
}
int
main()
{
int i;
BinaryTree<int> tree;
cout << "Insertion:\t";
for (i = 0; i < 10; i++) {
int insertme = rand() % 100;
tree.Insert(insertme);
cout << insertme << ' ';
}
cout << '\n';
cout << "Pre-order:\t"; tree.PreOrder(PrintInt); cout << '\n';
cout << "In-order:\t"; tree.InOrder(PrintInt); cout << '\n';
cout << "Post-order:\t"; tree.PostOrder(PrintInt); cout << '\n';
return 0;
}
Example 1: Declaring a function template
template<template parameters>
return value // From here on we define
name(function parameters) { // the function in terms of
function body // the template parameters.
}
Example 2: (a) defining a template-based Select function; (b)
calling the Select function
(a)
template<class T> T
Select(T *base, const int n, int i)
{
// Implementation
}
(b)
int *arr, n;
// ... allocate array and set n
// Set penultimate to the second-largest element in arr.
int penultimate = Select(arr, n, n - 2);
(c)
int
Select(int *x, const int n, int i)
{
// Own function definition of Select<int>
}
Example 3
(a)
template<class T>
class BinaryNode {
T x; // Contents of node
BinaryNode<T> *left, *right; // Left and right children
//etc.
};
(b)
// Class template for a binary tree node including a
// pointer to the parent.
template<class T>
class BinaryNodeWithParent : public BinaryNode<T> {
BinaryNodeWithParent<T> *parent;
// etc.
};
(c)
template<class T, int Size>
class Vector {
T x[Size]; // Vector contains Size T's.
// etc.
};
Copyright © 1992, Dr. Dobb's Journal