|
Page 1 of 9 Introduction to Templates Inheritance and composition provide a way to reuse object code. The template feature in C++ provides a way to reuse source code.Although C++ templates are a general-purpose programming tool, when they were introduced in the language, they seemed to discourage the use of object-based container-class hierarchies (demonstrated at the end of Chapter 15). For example, the Standard C++ containers and algorithms (explained in two chapters of Volume 2 of this book, downloadable from www.BruceEckel.com) are built exclusively with templates and are relatively easy for the programmer to use. This chapter not only demonstrates the basics of templates, it is also an introduction to containers, which are fundamental components of object-oriented programming and are almost completely realized through the containers in the Standard C++ Library. You&rsquoll see that this book has been using container examples &ndash the Stash and Stack &ndash throughout, precisely to get you comfortable with containers; in this chapter the concept of the iterator will also be added. Although containers are ideal examples for use with templates, in Volume 2 (which has an advanced templates chapter) you&rsquoll learn that there are many other uses for templates as well.
Containers
Suppose you want to create a stack, as we have been doing throughout the book. This stack class will hold ints, to keep it simple:
//: C16:IntStack.cpp // Simple integer stack //{L} fibonacci #include "fibonacci.h" #include "../require.h" #include <iostream>
using namespace std;class IntStack { enum { ssize = 100 };
int stack[ssize];
int top;
public:
IntStack() : top(0) {}
void push(int i) {
require(top < ssize, "Too many push()es");
stack[top++] = i;
}
int pop() {
require(top > 0, "Too many pop()s");
return stack[--top];
}
};
int main() {
IntStack is;
// Add some Fibonacci numbers, for interest: for(int i = 0; i < 20; i++)
is.push(fibonacci(i));
// Pop & print them: for(int k = 0; k < 20; k++)
cout << is.pop() << endl;
} ///:~ The class IntStack is a trivial example of a push-down stack. For simplicity it has been created here with a fixed size, but you can also modify it to automatically expand by allocating memory off the heap, as in the Stack class that has been examined throughout the book. main( ) adds some integers to the stack, and pops them off again. To make the example more interesting, the integers are created with the fibonacci( ) function, which generates the traditional rabbit-reproduction numbers. Here is the header file that declares the function:> //: C16:fibonacci.h
// Fibonacci number generator
int fibonacci(int n); ///:~ Here&rsquos the implementation:
//: C16:fibonacci.cpp {O}
#include "../require.h"
int fibonacci(int n) {
const int sz = 100;
require(n < sz);
static int f[sz]; // Initialized to zero f[0] = f[1] = 1;
// Scan for unfilled array elements: int i;
for(i = 0; i < sz; i++)
if(f[i] == 0) break;
while(i <= n) {
f[i] = f[i-1] + f[i-2];
i++;
}
return f[n];
} ///:~ This is a fairly efficient implementation, because it never generates the numbers more than once. It uses a static array of int, and relies on the fact that the compiler will initialize a static array to zero. The first for loop moves the index i to where the first array element is zero, then a while loop adds Fibonacci numbers to the array until the desired element is reached. But notice that if the Fibonacci numbers through element n are already initialized, it skips the while loop altogether. The need for containers Obviously, an integer stack isn&rsquot a crucial tool. The real need for containers comes when you start making objects on the heap using new and destroying them with delete. In the general programming problem, you don&rsquot know how many objects you&rsquore going to need while you&rsquore writing the program. For example, in an air-traffic control system you don&rsquot want to limit the number of planes your system can handle. You don&rsquot want the program to abort just because you exceed some number. In a computer-aided design system, you&rsquore dealing with lots of shapes, but only the user determines (at runtime) exactly how many shapes you&rsquore going to need. Once you notice this tendency, you&rsquoll discover lots of examples in your own programming situations.
C programmers who rely on virtual memory to handle their &ldquomemory management&rdquo often find the idea of new, delete, and container classes disturbing. Apparently, one practice in C is to create a huge global array, larger than anything the program would appear to need. This may not require much thought (or awareness of malloc( ) and free( )), but it produces programs that don&rsquot port well and that hide subtle bugs.
In addition, if you create a huge global array of objects in C++, the constructor and destructor overhead can slow things down significantly. The C++ approach works much better: When you need an object, create it with new, and put its pointer in a container. Later on, fish it out and do something to it. This way, you create only the objects you absolutely need. And usually you don&rsquot have all the initialization conditions available at the start-up of the program. new allows you to wait until something happens in the environment before you can actually create the object.
So in the most common situation, you&rsquoll make a container that holds pointers to some objects of interest. You will create those objects using new and put the resulting pointer in the container (potentially upcasting it in the process), pulling it out later when you want to do something with the object. This technique produces the most flexible, general sort of program.
|
C++ Programming 
