This chapter is from the book
This chapter is from the book
This chapter is from the book
2.7 Generic Programming
Someone who wants a stack is unlikely always to want a stack of characters. A stack is a general concept, independent of the notion of a character. Consequently, it ought to be represented independently.
More generally, if an algorithm can be expressed independently of representation details and if it can be done so affordably and without logical contortions, it ought to be done so.
This is the revised programming paradigm:
Decide which algorithms you want; parameterize them so that they work for a variety of suitable types and data structures.
2.7.1 Containers
We can generalize a stack-of-characters type to a stack-of-anything type by making it a template and replacing the specific type char with a template parameter. For example:
template<class T> class Stack {
T* v;
int max_size;
int top;
public:
class Underflow { };
class Overflow { };
Stack(int s); // constructor
~Stack(); // destructor
void push(T);
T pop();
};
The template<class T> prefix makes T a parameter of the declaration it prefixes.
The member functions might be defined similarly:
template<class T> void Stack<T>::push(T c)
{
if (top == max_size) throw Overflow();
v[top] = c;
top = top + 1;
}
template<class T> T Stack<T>::pop()
{
if (top == 0) throw Underflow();
top = top - 1;
return v[top];
}
Given these definitions, we can use stacks like this:
Stack<char> sc(200); // stack of 200 characters
Stack<complex> scplx(30); // stack of 30 complex numbers
Stack< list<int> > sli(45); // stack of 45 lists of integer
void f()
{
sc.push('c');
if (sc.pop() != 'c') throw Bad_pop();
scplx.push(complex(1,2));
if (scplx.pop() != complex(1,2)) throw Bad_pop();
}
Similarly, we can define lists, vectors, maps (that is, associative arrays), etc., as templates. A class holding a collection of elements of some type is commonly called a container class, or simply a container.
Templates are a compile-time mechanism so that their use incurs no run-time overhead compared to "hand-written code."
2.7.2 Generic Algorithms
The C++ standard library provides a variety of containers, and users can write their own. Thus, we find that we can apply the generic programming paradigm once more to parameterize algorithms by containers. For example, we want to sort, copy, and search vectors, lists, and arrays without having to write sort(), copy(), and search() functions for each container. We also don't want to convert to a specific data structure accepted by a single sort function. Therefore, we must find a generalized way of defining our containers that allows us to manipulate one without knowing exactly which kind of container it is.
One approach, the approach taken for the containers and non-numerical algorithms in the C++ standard library is to focus on the notion of a sequence and manipulate sequences through iterators.
Here is a graphical representation of the notion of a sequence:
A sequence has a beginning and an end. An iterator refers to an element, and provides an operation that makes the iterator refer to the next element of the sequence. The end of a sequence is an iterator that refers one beyond the last element of the sequence. The physical representation of "the end" may be a sentinel element, but it doesn't have to be. In fact, the point is that this notion of sequences covers a wide variety of representations, including lists and arrays.
We need some standard notation for operations such as "access an element through an iterator" and "make the iterator refer to the next element." The obvious choices (once you get the idea) are to use the dereference operator * to mean "access an element through an iterator" and the increment operator ++ to mean "make the iterator refer to the next element."
Given that, we can write code like this:
template<class In, class Out> void copy(In from, In too_far, Out to)
{
while (from != too_far) {
*to = *from; // copy element pointed to
++to; // next output
++from; // next input
}
}
This copies any container for which we can define iterators with the right syntax and semantics.
C++'s built-in, low-level array and pointer types have the right operations for that, so we can write
char vc1[200]; // array of 200 characters
char vc2[500]; // array of 500 characters
void f()
{
copy(&vc1[0] ,&vc1[200] ,&vc2[0]);
}
This copies vc1 from its first element until its last into vc2 starting at vc2's first element.
All standard library containers support this notion of iterators and sequences.
Two template parameters In and Out are used to indicate the types of the source and the target instead of a single argument. This was done because we often want to copy from one kind of container into another. For example:
complex ac[200];
void g(vector<complex>& vc, list<complex>& lc)
{
copy(&ac[0] ,&ac[200] ,lc.begin());
copy(lc.begin() ,lc.end() ,vc.begin());
}
This copies the array to the list and the list to the vector. For a standard container, begin() is an iterator pointing to the first element.