The best-known use of templates to date has been the Standard Template Library, or STL. The STL uses templates to separate containers (such as vectors and lists) from algorithms (such as finding, merging, and sorting). The two are connected through the use of iterators, which are classes that know how to read or write particular containers, without exposing the actual type of those containers.
For example, consider the following code fragment, which finds the first occurrence of a particular value in a vector of floating-point numbers:
void findValue(vector<double> & values, double target) { vector<double>::iterator loc = find(values.begin(), values.end(), target); assert(*loc == target); }
The STL class vector<> declares another class called iterator, whose job it is to traverse a vector<>. The two methods begin() and end() return instances of vector<>::iterator marking the beginning and end of the vector. STL's find() function iterates from the first of its arguments to the second, looking for a value that matches the one specified. Finally, dereferencing (operator*) is overloaded for vector<>::iterator, so that *loc returns the value at the location specified by loc.
If we decide later to store our values in a list instead of in a vector, only the declaration of the container type needs to change, since list<> defines a nested iterator class, and begin() and end() methods, in exactly the same way as vector<>:
void findValue(list<double> & values, double target) { list<double>::iterator loc = find(values.begin(), values.end(), target); assert(*loc == target); }
If we go one step further, and use a typedef to label our container type, then nothing in findValue() needs to change at all:
typedef vector<double> Storage; // typedef list<double> Storage; void findValue(Storage & values, double target) { Storage::iterator loc = find(values.begin(), values.end(), target); assert(*loc == target); }
The performance of this code will change as the storage mechanism
changes, but that's the point: STL-based code can often be tuned using
only minor, non-algorithmic changes.
[Prev] | [Home] | [Next] |