James Thornton logo
James Thornton
Google
Web jamesthornton.com
Internet Business Consultant
Home Blog Bio Projects Contact Latest Blog (new site): How to Get to Genius
JamesThornton.com -> Archive -> Bruce Eckel Books -> TICPP-2nd-ed-Vol-two -> One Page

MindView Inc.
[ Viewing Hints ] [ Revision History ] [ Free Newsletter ]
[ Seminars ] [ Seminars on CD ROM ] [ Consulting ]

Thinking in C++, 2nd ed., Volume 2, Revision 3

©2000 by Bruce Eckel

[ Previous Chapter ] [ Short TOC ] [ Table of Contents ] [ Index ] [ Next Chapter ]

3: Templates in depth


Nontype template arguments

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.

Default template arguments

The typename keyword

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:

  1. Is a qualified name, one that is nested within another type.
  2. Depends on a template argument. That is, a template argument is somehow involved in the name. The template argument causes the ambiguity when the compiler makes the simplest assumption: that the name refers to something other than a type.

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.

Typedefing a 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;


Using typename instead of class

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.

Function templates

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.[11] 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.

A string conversion system

 
//: 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)


A memory allocation system

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.

Type induction in function templates

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.

Taking the address of a generated function template

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[12]:

//: 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.

Local classes in templates

Applying a function to an STL sequence

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[13] 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

Template-templates

 
//: 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);

} ///:~


Member function templates

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.[14]

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);

} ///:~

Conceptually, it reads more sensibly to say that you’re calling apply( ) for the dogs container.

Why virtual member template functions are disallowed

Nested template classes

Template specializations

Full specialization

Partial Specialization

A practical example

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.

Pointer specialization

Partial ordering of function templates

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

  1. Get the class interfaces correct.
  2. Create an accurate implementation as rapidly as possible so you can:
  3. 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 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; 
  }

} ///:~

Explicit instantiation

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.

Explicit specification of template functions

Controlling template instantiation

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.

The inclusion vs. separation models

The export keyword

Template programming idioms

The “curiously-recurring template”

Traits

Summary

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.

[11] See C++ Inside & Out (Osborne/McGraw-Hill, 1993) by the author, Chapter 10.

[12] I am indebted to Nathan Myers for this example.

[13] A reference to the British animated short The Wrong Trousers by Nick Park.

[14] Check your compiler version information to see if it supports member function templates.

[ Previous Chapter ] [ Short TOC ] [ Table of Contents ] [ Index ] [ Next Chapter ]
Last Update:05/23/2000
Follow espeed on Twitter

James Thornton,<james@jamesthornton.com>
Services: Web Developer Ecommerce Web Site 		Electric Speed: Internet Consultant