[ Seminars ] [ Seminars on CD ROM ] [ Consulting ]
Here is a random number generator class that always produces a
unique number and overloads operator( ) to produce a familiar
function-call syntax:
//: C03:Urand.h
// Unique random number generator
#ifndef URAND_H
#define URAND_H
#include <cstdlib>
#include <ctime>
template<int upperBound>
class Urand {
int used[upperBound];
bool recycle;
public:
Urand(bool recycle = false);
int operator()(); // The "generator" function
};
template<int upperBound>
Urand<upperBound>::Urand(bool recyc)
: recycle(recyc) {
memset(used, 0, upperBound * sizeof(int));
srand(time(0)); // Seed random number generator
}
template<int upperBound>
int Urand<upperBound>::operator()() {
if(!memchr(used, 0, upperBound)) {
if(recycle)
memset(used,0,sizeof(used) * sizeof(int));
else
return -1; // No more spaces left
}
int newval;
while(used[newval = rand() % upperBound])
; // Until unique value is found
used[newval]++; // Set flag
return newval;
}
#endif // URAND_H ///:~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
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.
Consider the following:
//: C03:TypenamedID.cpp
// Using 'typename' to say it's a type,
// and not something other than a type
template<class T> class X {
// Without typename, you should get an error:
typename T::id i;
public:
void f() { i.g(); }
};
class Y {
public:
class id {
public:
void g() {}
};
};
int main() {
Y y;
X<Y> xy;
xy.f();
} ///:~The template definition assumes that the class T that
you hand it must have a nested identifier of some kind called id. But
id could be a member object of T, in which case you can perform
operations on id directly, but you couldn’t “create an
object” of “the type id.” However, that’s exactly
what is happening here: the identifier id is being treated as if it were
actually a nested type inside T. In the case of class Y, id
is in fact a nested type, but (without the typename keyword) the compiler
can’t know that when it’s compiling X.
If, when it sees an identifier in a template, the compiler has
the option of treating that identifier as a type or as something other than a
type, then it will assume that the identifier refers to something other than a
type. That is, it will assume that the identifier refers to an object (including
variables of primitive types), an enumeration or something similar. However, it
will not – cannot – just assume that it is a type. Thus, the
compiler gets confused when we pretend it’s a type.
The typename keyword tells the compiler to interpret a
particular name as a type. It must be used for a name that:
Because the default behavior of the compiler is to
assume that a name that fits the above two points is not a type, you must use
typename even in places where you think that the compiler ought to be
able to figure out the right way to interpret the name on its own. In the above
example, when the compiler sees T::id, it knows (because of the
typename keyword) that id refers to a nested type and thus it can
create an object of that type.
The short version of the rule is: if your type is a qualified
name that involves a template argument, you must use
typename.
The typename keyword does not automatically create a
typedef. A line which reads:
typename Seq::iterator It;
causes a variable to be declared of type Seq::iterator.
If you mean to make a typedef, you must say:
typedef typename Seq::iterator It;
With the introduction of the typename keyword, you now
have the option of using typename instead of class in the template
argument list of a template definition. This may produce code which is
clearer:
//: C03:UsingTypename.cpp
// Using 'typename' in the template argument list
template<typename T> class X { };
int main() {
X<int> x;
} ///:~You’ll probably see a great deal of code which does not
use typename in this fashion, since the keyword was added to the language
a relatively long time after templates were
introduced.
A class template describes an infinite set of classes, and the
most common place you’ll see templates is with classes. However, C++ also
supports the concept of an infinite set of functions, which is sometimes useful.
The syntax is virtually identical, except that you create a function instead of
a class.
The clue that you should create a function template is, as you
might suspect, if you find you’re creating a number of functions that look
identical except that they are dealing with different types. The classic example
of a function template is a sorting
function.[12] However, a function template is
useful in all sorts of places, as demonstrated in the first example that
follows. The second example shows a function template used with containers and
iterators.
//: C03:stringConv.h
// Chuck Allison's string converter
#ifndef STRINGCONV_H
#define STRINGCONV_H
#include <string>
#include <sstream>
template<typename T>
T fromString(const std::string& s) {
std::istringstream is(s);
T t;
is >> t;
return t;
}
template<typename T>
std::string toString(const T& t) {
std::ostringstream s;
s << t;
return s.str();
}
#endif // STRINGCONV_H ///:~Here’s a test program, that includes the use of the
Standard Library complex number type:
//: C03:stringConvTest.cpp
#include "stringConv.h"
#include <iostream>
#include <complex>
using namespace std;
int main() {
int i = 1234;
cout << "i == \"" << toString(i) << "\"\n";
float x = 567.89;
cout << "x == \"" << toString(x) << "\"\n";
complex<float> c(1.0, 2.0);
cout << "c == \"" << toString(c) << "\"\n";
cout << endl;
i = fromString<int>(string("1234"));
cout << "i == " << i << endl;
x = fromString<float>(string("567.89"));
cout << "x == " << x << endl;
c = fromString< complex<float> >(string("(1.0,2.0)"));
cout << "c == " << c << endl;
} ///:~The output is what you’d expect:
i == "1234" x == "567.89" c == "(1,2)" i == 1234 x == 567.89 c == (1,2)
There are a few things you can do to make the raw memory
allocation routines malloc( ),
calloc( ) and
realloc( ) safer. The following function
template produces one function getmem( ) that either allocates a new
piece of memory or resizes an existing piece (like realloc( )). In
addition, it zeroes only the new memory, and it checks to see that the memory is
successfully allocated. Also, you only tell it the number of elements of the
type you want, not the number of bytes, so the possibility of a programmer error
is reduced. Here’s the header file:
//: C03:Getmem.h
// Function template for memory
#ifndef GETMEM_H
#define GETMEM_H
#include "../require.h"
#include <cstdlib>
#include <cstring>
template<class T>
void getmem(T*& oldmem, int elems) {
typedef int cntr; // Type of element counter
const int csz = sizeof(cntr); // And size
const int tsz = sizeof(T);
if(elems == 0) {
free(&(((cntr*)oldmem)[-1]));
return;
}
T* p = oldmem;
cntr oldcount = 0;
if(p) { // Previously allocated memory
// Old style:
// ((cntr*)p)--; // Back up by one cntr
// New style:
cntr* tmp = reinterpret_cast<cntr*>(p);
p = reinterpret_cast<T*>(--tmp);
oldcount = *(cntr*)p; // Previous # elems
}
T* m = (T*)realloc(p, elems * tsz + csz);
require(m != 0);
*((cntr*)m) = elems; // Keep track of count
const cntr increment = elems - oldcount;
if(increment > 0) {
// Starting address of data:
long startadr = (long)&(m[oldcount]);
startadr += csz;
// Zero the additional new memory:
memset((void*)startadr, 0, increment * tsz);
}
// Return the address beyond the count:
oldmem = (T*)&(((cntr*)m)[1]);
}
template<class T>
inline void freemem(T * m) { getmem(m, 0); }
#endif // GETMEM_H ///:~To be able to zero only the new memory, a counter indicating
the number of elements allocated is attached to the beginning of each block of
memory. The typedef cntr is the type of this counter; it allows you to
change from int to long if you need to handle larger chunks (other
issues come up when using long, however – these are seen in
compiler warnings).
A pointer reference is used for the argument oldmem
because the outside variable (a pointer) must be changed to point to the new
block of memory. oldmem must point to zero (to allocate new memory) or to
an existing block of memory that was created with getmem( ).
This function assumes you’re using it properly, but for debugging you
could add an additional tag next to the counter containing an identifier, and
check that identifier in getmem( ) to help discover incorrect
calls.
If the number of elements requested is zero, the storage is
freed. There’s an additional function template freemem( ) that
aliases this behavior.
You’ll notice that getmem( ) is very
low-level – there are lots of casts and byte manipulations. For example,
the oldmem pointer doesn’t point to the true beginning of the
memory block, but just past the beginning to allow for the counter. So to
free( ) the memory block, getmem( ) must back up the
pointer by the amount of space occupied by cntr. Because oldmem is
a T*, it must first be cast to a cntr*, then indexed backwards one
place. Finally the address of that location is produced for free( )
in the expression:
free(&(((cntr*)oldmem)[-1]));
Similarly, if this is previously allocated memory,
getmem( ) must back up by one cntr size to get the true
starting address of the memory, and then extract the previous number of
elements. The true starting address is required inside realloc( ).
If the storage size is being increased, then the difference between the new
number of elements and the old number is used to calculate the starting address
and the amount of memory to zero in memset( ). Finally, the address
beyond the count is produced to assign to oldmem in the
statement:
oldmem = (T*)&(((cntr*)m)[1]);
Again, because oldmem is a reference to a pointer, this
has the effect of changing the outside argument passed to
getmem( ).
Here’s a program to test getmem( ). It
allocates storage and fills it up with values, then increases that amount of
storage:
//: C03:Getmem.cpp
// Test memory function template
#include "Getmem.h"
#include <iostream>
using namespace std;
int main() {
int* p = 0;
getmem(p, 10);
for(int i = 0; i < 10; i++) {
cout << p[i] << ' ';
p[i] = i;
}
cout << '\n';
getmem(p, 20);
for(int j = 0; j < 20; j++) {
cout << p[j] << ' ';
p[j] = j;
}
cout << '\n';
getmem(p, 25);
for(int k = 0; k < 25; k++)
cout << p[k] << ' ';
freemem(p);
cout << '\n';
float* f = 0;
getmem(f, 3);
for(int u = 0; u < 3; u++) {
cout << f[u] << ' ';
f[u] = u + 3.14159;
}
cout << '\n';
getmem(f, 6);
for(int v = 0; v < 6; v++)
cout << f[v] << ' ';
freemem(f);
} ///:~After each getmem( ), the values in memory are
printed out to show that the new ones have been zeroed.
Notice that a different version of getmem( ) is
instantiated for the int and float pointers. You might think that
because all the manipulations are so low-level you could get away with a single
non-template function and pass a void*& as oldmem. This
doesn’t work because then the compiler must do a conversion from your type
to a void*. To take the reference, it makes a temporary. This produces an
error because then you’re modifying the temporary pointer, not the pointer
you want to change. So the function template is necessary to produce the exact
type for the argument.
As a simple but very useful example, consider the
following:
//: :arraySize.h
// Uses template type induction to
// discover the size of an array
#ifndef ARRAYSIZE_H
#define ARRAYSIZE_H
template<typename T, int size>
int asz(T (&)[size]) { return size; }
#endif // ARRAYSIZE_H ///:~This actually figures out the size of an array as a
compile-time constant value, without using any sizeof( ) operations!
Thus you can have a much more succinct way to calculate the size of an array at
compile time:
//: C03:ArraySize.cpp
// The return value of the template function
// asz() is a compile-time constant
#include "../arraySize.h"
int main() {
int a[12], b[20];
const int sz1 = asz(a);
const int sz2 = asz(b);
int c[sz1], d[sz2];
} ///:~Of course, just making a variable of a built-in type a
const does not guarantee it’s actually a compile-time constant, but
if it’s used to define the size of an array (as it is in the last line of
main( )), then it must be a compile-time
constant.
There are a number of situations where you need to take the
address of a function. For example, you may have a function that takes an
argument of a pointer to another function. Of course it’s possible that
this other function might be generated from a template function so you need some
way to take that kind of address[13]:
//: C03:TemplateFunctionAddress.cpp
// Taking the address of a function generated
// from a template.
template <typename T> void f(T*) {}
void h(void (*pf)(int*)) {}
template <class T>
void g(void (*pf)(T*)) {}
int main() {
// Full type exposition:
h(&f<int>);
// Type induction:
h(&f);
// Full type exposition:
g<int>(&f<int>);
// Type inductions:
g(&f<int>);
g<int>(&f);
} ///:~This example demonstrates a number of different issues. First,
even though you’re using templates, the signatures must match – the
function h( ) takes a pointer to a function that takes an
int* and returns void, and that’s what the template f
produces. Second, the function that wants the function pointer as an argument
can itself be a template, as in the case of the template g.
In main( ) you can see that type induction works
here, too. The first call to h( ) explicitly gives the template
argument for f, but since h( ) says that it will only take
the address of a function that takes an int*, that part can be induced by
the compiler. With g( ) the situation is even more interesting
because there are two templates involved. The compiler cannot induce the type
with nothing to go on, but if either f or g is given int,
then the rest can be
induced.
Suppose you want to take an STL sequence container (which
you’ll learn more about in subsequent chapters; for now we can just use
the familiar vector) and apply a function to all the objects it contains.
Because a vector can contain any type of object, you need a function that
works with any type of vector and any type of object it
contains:
//: C03:applySequence.h
// Apply a function to an STL sequence container
// 0 arguments, any type of return value:
template<class Seq, class T, class R>
void apply(Seq& sq, R (T::*f)()) {
typename Seq::iterator it = sq.begin();
while(it != sq.end()) {
((*it)->*f)();
it++;
}
}
// 1 argument, any type of return value:
template<class Seq, class T, class R, class A>
void apply(Seq& sq, R(T::*f)(A), A a) {
typename Seq::iterator it = sq.begin();
while(it != sq.end()) {
((*it)->*f)(a);
it++;
}
}
// 2 arguments, any type of return value:
template<class Seq, class T, class R,
class A1, class A2>
void apply(Seq& sq, R(T::*f)(A1, A2),
A1 a1, A2 a2) {
typename Seq::iterator it = sq.begin();
while(it != sq.end()) {
((*it)->*f)(a1, a2);
it++;
}
}
// Etc., to handle maximum likely arguments ///:~The apply( ) function template takes a reference
to the container class and a pointer-to-member for a member function of the
objects contained in the class. It uses an iterator to move through the
Stack and apply the function to every object. If you’ve
(understandably) forgotten the pointer-to-member syntax,
you can refresh your memory at the end of Chapter XX.
Notice that there are no STL header files (or any header
files, for that matter) included in applySequence.h, so it is actually
not limited to use with an STL sequence. However, it does make assumptions
(primarily, the name and behavior of the iterator) that apply to STL
sequences.
You can see there is more than one version of
apply( ), so it’s possible to overload function templates.
Although they all take any type of return value (which is ignored, but the type
information is required to match the pointer-to-member), each version takes a
different number of arguments, and because it’s a template, those
arguments can be of any type. The only limitation here is that there’s no
“super template” to create templates for you; thus you must decide
how many arguments will ever be required.
To test the various overloaded versions of
apply( ), the class
Gromit[14] is
created containing functions with different numbers of arguments:
//: C03:Gromit.h
// The techno-dog. Has member functions
// with various numbers of arguments.
#include <iostream>
class Gromit {
int arf;
public:
Gromit(int arf = 1) : arf(arf + 1) {}
void speak(int) {
for(int i = 0; i < arf; i++)
std::cout << "arf! ";
std::cout << std::endl;
}
char eat(float) {
std::cout << "chomp!" << std::endl;
return 'z';
}
int sleep(char, double) {
std::cout << "zzz..." << std::endl;
return 0;
}
void sit(void) {}
}; ///:~Now the apply( ) template functions can be
combined with a vector<Gromit*> to make a container that will call
member functions of the contained objects, like this:
//: C03:applyGromit.cpp
// Test applySequence.h
#include "Gromit.h"
#include "applySequence.h"
#include <vector>
#include <iostream>
using namespace std;
int main() {
vector<Gromit*> dogs;
for(int i = 0; i < 5; i++)
dogs.push_back(new Gromit(i));
apply(dogs, &Gromit::speak, 1);
apply(dogs, &Gromit::eat, 2.0f);
apply(dogs, &Gromit::sleep, 'z', 3.0);
apply(dogs, &Gromit::sit);
} ///:~Although the definition of apply( ) is somewhat
complex and not something you’d ever expect a novice to understand, its
use is remarkably clean and simple, and a novice could easily use it knowing
only what it is intended to accomplish, not how. This is the type
of division you should strive for in all of your program components: The tough
details are all isolated on the designer’s side of the wall, and users are
concerned only with accomplishing their goals, and don’t see, know about,
or depend on details of the underlying
implementation
//: C03:TemplateTemplate.cpp
#include <vector>
#include <iostream>
#include <string>
using namespace std;
// As long as things are simple,
// this approach works fine:
template<typename C>
void print1(C& c) {
typename C::iterator it;
for(it = c.begin(); it != c.end(); it++)
cout << *it << " ";
cout << endl;
}
// Template-template argument must
// be a class; cannot use typename:
template<typename T, template<typename> class C>
void print2(C<T>& c) {
copy(c.begin(), c.end(),
ostream_iterator<T>(cout, " "));
cout << endl;
}
int main() {
vector<string> v(5, "Yow!");
print1(v);
print2(v);
} ///:~It’s also possible to make apply( ) a
member function
template
of the class. That is, a separate template definition from the class’
template, and yet a member of the class. This may produce a cleaner
syntax:
dogs.apply(&Gromit::sit);
This is analogous to the act (in Chapter XX) of bringing
ordinary functions inside a
class.[15]
The definition of the apply( ) functions turn out
to be cleaner, as well, because they are members of the container. To accomplish
this, a new container is inherited from one of the existing STL sequence
containers and the member function templates are added to the new type. However,
for maximum flexibility we’d like to be able to use any of the STL
sequence containers, and for this to work a template-template must be
used, to tell the compiler that a template argument is actually a template,
itself, and can thus take a type argument and be instantiated. Here is what it
looks like after bringing the apply( ) functions into the new type
as member functions:
//: C03:applyMember.h
// applySequence.h modified to use
// member function templates
template<class T, template<typename> class Seq>
class SequenceWithApply : public Seq<T*> {
public:
// 0 arguments, any type of return value:
template<class R>
void apply(R (T::*f)()) {
iterator it = begin();
while(it != end()) {
((*it)->*f)();
it++;
}
}
// 1 argument, any type of return value:
template<class R, class A>
void apply(R(T::*f)(A), A a) {
iterator it = begin();
while(it != end()) {
((*it)->*f)(a);
it++;
}
}
// 2 arguments, any type of return value:
template<class R, class A1, class A2>
void apply(R(T::*f)(A1, A2),
A1 a1, A2 a2) {
iterator it = begin();
while(it != end()) {
((*it)->*f)(a1, a2);
it++;
}
}
}; ///:~Because they are members, the apply( ) functions
don’t need as many arguments, and the iterator class doesn’t
need to be qualified. Also, begin( ) and end( ) are now
member functions of the new type and so look cleaner as well. However, the basic
code is still the same.
You can see how the function calls are also simpler for the
client programmer:
//: C03:applyGromit2.cpp
// Test applyMember.h
#include "Gromit.h"
#include "applyMember.h"
#include <vector>
#include <iostream>
using namespace std;
int main() {
SequenceWithApply<Gromit, vector> dogs;
for(int i = 0; i < 5; i++)
dogs.push_back(new Gromit(i));
dogs.apply(&Gromit::speak, 1);
dogs.apply(&Gromit::eat, 2.0f);
dogs.apply(&Gromit::sleep, 'z', 3.0);
dogs.apply(&Gromit::sit);
} ///:~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 vector 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:
//: C03:Sorted.h
// Template specialization
#ifndef SORTED_H
#define SORTED_H
#include <vector>
template<class T>
class Sorted : public std::vector<T> {
public:
void sort();
};
template<class T>
void Sorted<T>::sort() { // A bubble sort
for(int i = size(); i > 0; i--)
for(int j = 1; j < i; j++)
if(at(j-1) > at(j)) {
// Swap the two elements:
T t = at(j-1);
at(j-1) = at(j);
at(j) = t;
}
}
// Partial specialization for pointers:
template<class T>
class Sorted<T*> : public std::vector<T*> {
public:
void sort();
};
template<class T>
void Sorted<T*>::sort() {
for(int i = size(); i > 0; i--)
for(int j = 1; j < i; j++)
if(*at(j-1) > *at(j)) {
// Swap the two elements:
T* t = at(j-1);
at(j-1) = at(j);
at(j) = t;
}
}
// Full specialization for char*:
template<>
void Sorted<char*>::sort() {
for(int i = size(); i > 0; i--)
for(int j = 1; j < i; j++)
if(strcmp(at(j-1), at(j)) > 0) {
// Swap the two elements:
char* t = at(j-1);
at(j-1) = at(j);
at(j) = t;
}
}
#endif // SORTED_H ///:~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.
The default Sorted template only works with objects
(including objects of built-in types). However, it won’t sort pointers to
objects so the partial specialization is necessary. Even then, the code
generated by the partial specialization won’t sort an array of
char*. To solve this, the full specialization compares the char*
elements using strcmp( ) to produce the proper behavior.
Here’s a test for Sorted.h that uses the unique
random number generator introduced earlier in the chapter:
//: C03:Sorted.cpp
// Testing template specialization
#include "Sorted.h"
#include "Urand.h"
#include "../arraySize.h"
#include <iostream>
#include <string>
using namespace std;
char* words[] = {
"is", "running", "big", "dog", "a",
};
char* words2[] = {
"this", "that", "theother",
};
int main() {
Sorted<int> is;
Urand<47> rand;
for(int i = 0; i < 15; i++)
is.push_back(rand());
for(int l = 0; l < is.size(); l++)
cout << is[l] << ' ';
cout << endl;
is.sort();
for(int l = 0; l < is.size(); l++)
cout << is[l] << ' ';
cout << endl;
// Uses the template partial specialization:
Sorted<string*> ss;
for(int i = 0; i < asz(words); i++)
ss.push_back(new string(words[i]));
for(int i = 0; i < ss.size(); i++)
cout << *ss[i] << ' ';
cout << endl;
ss.sort();
for(int i = 0; i < ss.size(); i++)
cout << *ss[i] << ' ';
cout << endl;
// Uses the full char* specialization:
Sorted<char*> scp;
for(int i = 0; i < asz(words2); i++)
scp.push_back(words2[i]);
for(int i = 0; i < scp.size(); i++)
cout << scp[i] << ' ';
cout << endl;
scp.sort();
for(int i = 0; i < scp.size(); i++)
cout << scp[i] << ' ';
cout << endl;
} ///:~Each of the template instantiations uses a different version
of the template. Sorted<int> uses the “ordinary,”
non-specialized template. Sorted<string*> uses the partial
specialization for pointers. Lastly, Sorted<char*> uses the full
specialization for char*. Note that without this full specialization, you
could be fooled into thinking that things were working correctly because the
words array would still sort out to “a big dog is running”
since the partial specialization would end up comparing the first character of
each array. However, words2 would not sort out correctly, and for the
desired behavior the full specialization is necessary.
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
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.)
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 XX in InheritStack.cpp inheritance was used to specify the types
that a Stack could accept and produce. Here’s the templatized
version of that code:
//: C03:Nobloat.h
// Templatized InheritStack.cpp
#ifndef NOBLOAT_H
#define NOBLOAT_H
#include "../C0A/Stack4.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.
//: C03:NobloatTest.cpp
#include "Nobloat.h"
#include "../require.h"
#include <fstream>
#include <iostream>
#include <string>
using namespace std;
int main(int argc, char* argv[]) {
requireArgs(argc, 1); // File name is argument
ifstream in(argv[1]);
assure(in, argv[1]);
NBStack<string> textlines;
string line;
// Read file and store lines in the stack:
while(getline(in, line))
textlines.push(new string(line));
// Pop the lines from the stack and print them:
string* s;
while((s = (string*)textlines.pop()) != 0) {
cout << *s << endl;
delete s;
}
} ///:~At times it is useful to explicitly instantiate a template;
that is, to tell the compiler to lay down the code for a specific version of
that template even though you’re not creating an object at that point. To
do this, you reuse the template keyword as follows:
template class Bobbin<thread>; template void sort<char>(char*[]);
Here’s a
version of the Sorted.cpp example that explicitly instantiates a template
before using it:
//: C03:ExplicitInstantiation.cpp
#include "Urand.h"
#include "Sorted.h"
#include <iostream>
using namespace std;
// Explicit instantiation:
template class Sorted<int>;
int main() {
Sorted<int> is;
Urand<47> rand1;
for(int k = 0; k < 15; k++)
is.push_back(rand1());
is.sort();
for(int l = 0; l < is.size(); l++)
cout << is[l] << endl;
} ///:~In this example, the explicit instantiation doesn’t
really accomplish anything; the program would work the same without it. Explicit
instantiation is only for special cases where extra control is
needed.
Normally templates are not instantiated until they are needed.
For function templates this just means the point at which you call the function,
but for class templates it’s more granular than that: each individual
member function of the template is not instantiated until the first point of
use. This means that only the member functions you actually use will be
instantiated, which is quite important since it allows greater freedom in what
the template can be used with. For example:
//: C03:DelayedInstantiation.cpp
// Member functions of class templates are not
// instantiated until they're needed.
class X {
public:
void f() {}
};
class Y {
public:
void g() {}
};
template <typename T> class Z {
T t;
public:
void a() { t.f(); }
void b() { t.g(); }
};
int main() {
Z<X> zx;
zx.a(); // Doesn't create Z<X>::b()
Z<Y> zy;
zy.b(); // Doesn't create Z<Y>::a()
} ///:~Here, even though the template purports to use both
f( ) and g( ) member functions of T, the fact
that the program compiles shows you that it only generates
Z<X>::a( ) when it is explicitly called for zx (if
Z<X>::b( ) were also generated at the same time, a
compile-time error message would be generated). Similarly, the call to
zy.b( ) doesn’t generate Z<Y>::a( ). As a
result, the Z template can be used with X and Y, whereas if
all the member functions were generated when the class was first created it
would significantly limit the use of many
templates.
One of the greatest weaknesses of C++ templates will be shown
to you when you try to write code that uses templates, especially STL code
(introduced in the next two chapters), and start getting compile-time error
messages. When you’re not used to it, the quantity of inscrutable text
that will be spewed at you by the compiler will be quite overwhelming. After a
while you’ll adapt (although it always feels a bit barbaric), and if
it’s any consolation, C++ compilers have actually gotten a lot
better about this – previously they would only give the line where
you tried to instantiate the template, and most of them now go to the line in
the template definition that caused the problem.
The issue is that a template implies an interface. That
is, even though the template keyword says “I’ll take any
type,” the code in a template definition actually requires that certain
operators and member functions be supported – that’s the interface.
So in reality, a template definition is saying “I’ll take any type
that supports this interface.” Things would be much nicer if the compiler
could simply say “hey, this type that you’re trying to instantiate
the template with doesn’t support that interface – can’t do
it.” The Java language has a feature called interface that would be
a perfect match for this (Java, however, has no parameterized type mechanism),
but it will be many years, if ever, before you will see such a thing in C++ (at
this writing the C++ Standard has only just been accepted and it will be a while
before all the compilers even achieve compliance). Compilers can only get so
good at reporting template instantiation errors, so you’ll have to grit
your teeth, go to the first line reported as an error and figure it
out.
[12] See C++
Inside & Out (Osborne/McGraw-Hill, 1993) by the author, Chapter
10.
[13] I am
indebted to Nathan Myers for this example.
[14] A reference
to the British animated short The Wrong Trousers by Nick
Park.
[15] Check your
compiler version information to see if it supports member function
templates.