Templates
& inheritance
There’s
nothing to prevent you from using a class template in any way you’d use
an ordinary class. For example, you can easily inherit from a template, and you
can create a new template that instantiates and inherits from an existing
template. If the
TStash
class does everything you want, but you’d also like it to sort itself,
you can easily reuse the code and add value to it:
//: C16:Sorted.h
// Template inheritance
#ifndef SORTED_H
#define SORTED_H
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <vector>
#include "TStash.h"
template<class T>
class Sorted : public TStash<T> {
void bubblesort();
public:
int add(T* element) {
TStash<T>::add(element);
bubblesort();
return 0; // Sort moves the element
}
};
template<class T>
void Sorted<T>::bubblesort() {
for(int i = count(); i > 0; i--)
for(int j = 1; j < i; j++)
if(*storage[j-1] > *storage[j]) {
// Swap the two elements:
T* t = storage[j-1];
storage[j-1] = storage[j];
storage[j] = t;
}
}
// Unique random number generator:
template<int upper_bound>
class Urand {
int map[upper_bound];
int recycle;
public:
Urand(int recycle = 0);
int operator()();
};
template<int upper_bound>
Urand<upper_bound>::Urand(int recyc)
: recycle(recyc) {
memset(map, 0, upper_bound * sizeof(int));
srand(time(0)); // Seed random number generator
}
template<int upper_bound>
int Urand<upper_bound>::operator()() {
if(!memchr(map, 0, upper_bound)) {
if(recycle)
memset(map, 0,
sizeof(map) * sizeof(int));
else
return -1; // No more spaces left
}
int newval;
while(map[newval = rand() % upper_bound])
; // Until unique value is found
map[newval]++; // Set flag
return newval;
}
#endif // SORTED_H ///:~ This
example also contains a random number generator class that always produces a
unique number and overloads
operator( )
to produce a familiar function-call syntax. The uniqueness of
Urand
is produced by keeping a map of all the numbers possible in the random space
(the upper bound is set with the template argument) and marking each one off as
it’s used. The optional second constructor argument allows you to reuse
the numbers once they’re all used up. Notice that this implementation is
optimized for speed by allocating the entire map, regardless of how many
numbers you’re going to need. If you want to optimize for size, you can
change the underlying implementation so it allocates storage for the map
dynamically and puts the random numbers themselves in the map rather than
flags. Notice that this change in implementation will not affect any client code.
The
Sorted
template imposes a restriction on all classes it is instantiated for: They must
contain a
>
operator. In
SString
this is added explicitly, but in
Integer
the automatic type conversion
operator
int
provides a path to the built-in
>
operator. When a template provides
more functionality for you, the trade-off is usually that it puts more
requirements on your class. Sometimes you’ll have to inherit the
contained class to add the required functionality. Notice the value of using an
overloaded operator here – the
Integer
class can rely on its underlying implementation to provide the functionality.
In
this example you can see the usefulness of making the underlying
storage
in
TStash
protected
rather than
private.
It
is
an important thing for the
Sorted
class to know, a true dependency: If you were to change the underlying
implementation of
TStash
to be something other than an array, like a linked list, the
“swapping” of elements would be completely different, so the
dependent class
Sorted
would need to be changed. However, a preferable alternative (if possible) to
making the implementation of
TStash
protected
is to provide enough
protected
interface functions so that access and swapping can take place in a derived
class without directly manipulating the underlying implementation. That way you
can still change the underlying implementation without propagating modifications.
Here’s
a test for
Sorted.h:
//: C16:Sorted.cpp
// Testing template inheritance
#include <iostream>
#include <string>
#include "Sorted.h"
#include "Integer.h"
using namespace std;
char* words[] = {
"is", "running", "big", "dog", "a",
};
const int wordsz = sizeof words / sizeof *words;
int main() {
Sorted<string> ss;
for(int i = 0; i < wordsz; i++)
ss.add(new string(words[i]));
for(int j = 0; j < ss.count(); j++)
std::cout << ss[j]->c_str() << endl;
Sorted<Integer> is;
Urand<47> rand1;
for(int k = 0; k < 15; k++)
is.add(new Integer(rand1()));
for(int l = 0; l < is.count(); l++)
std::cout << *is[l] << endl;
} ///:~ This
tests both the
SString
and
Integer
classes by creating a
Sorted
array for each.
Design
& efficiency
In
Sorted,
every time you call
add( )
the element is inserted and the array is resorted. Here, the horribly
inefficient and greatly deprecated (but easy to understand and code) bubble sort is
used. This is perfectly appropriate, because it’s part of the
private
implementation. During program development, your priorities are to
- Get
the class interfaces correct.
- Create
an accurate implementation as rapidly as possible so you can:
- Prove
your design.
Very
often, you will discover problems with the class interface only when you
assemble your initial “rough draft” of the working system. You may
also discover the need for “helper” classes like containers and
iterators during system assembly and during your first-pass implementation.
Sometimes it’s very difficult to discover these kinds of issues during
analysis – your goal in analysis should be to get a big-picture design
that can be rapidly implemented
and tested. Only after the design has been proven should you spend the time to
flesh it out completely and worry about performance issues. If the design
fails, or if performance is not a problem, the bubble sort is good enough, and
you haven’t wasted any time. (Of course, the ideal solution is to use
someone else’s sorted container; the Standard C++ template library is the
first place to look.)
Preventing
template bloat
Each
time you instantiate a template, the code in the template is generated anew
(except for
inline
functions). If some of the functionality of a template does not depend on type,
it can be put in a common base class to prevent needless reproduction of that
code. For example, in Chapter 12 in
Inhstak.cpp
inheritance was used to specify the types that a
Stack
could accept and produce. Here’s the templatized version of that code:
//: C16:Nobloat.h
// Templatized INHSTAK.CPP
#ifndef NOBLOAT_H
#define NOBLOAT_H
#include "Stack11.h"
template<class T>
class NBStack : public Stack {
public:
void push(T* str) {
Stack::push(str);
}
T* peek() const {
return (T*)Stack::peek();
}
T* pop() {
return (T*)Stack::pop();
}
~NBStack();
};
// Defaults to heap objects & ownership:
template<class T>
NBStack<T>::~NBStack() {
T* top = pop();
while(top) {
delete top;
top = pop();
}
}
#endif // NOBLOAT_H ///:~ As
before, the inline functions generate no code and are thus “free.”
The functionality is provided by creating the base-class code only once.
However, the ownership problem has been solved here by adding a destructor
(which
is
type-dependent, and thus must be created by the template). Here, it defaults to
ownership. Notice that when the base-class destructor is called, the stack will
be empty so no duplicate releases will occur.
Go to CodeGuru.com
Contact: webmaster@codeguru.com
© Copyright 1997-1999 CodeGuru