FAQ > Using templates to solve problems


Match word(s).

If you have any questions or comments,
please visit us on the Forums.

FAQ > How do I... (Level 3) > Using templates to solve problems

This item was added on: 2003/09/01

Templates are very flexible things. They're easily one of the more complex ideas in C++, and as a result they sometimes become buggy. But they're also very useful.

NOTE: Templates must be defined either in a header file, or in every c++ source file you use them in. You can't define them like normal functions and classes are.

Templates for generalization

Say you wanted to contain an array of objects in a structure:


struct vector 
{
  Object a[500];
};


But now you needed an array of doubles


struct vector_d 
{
  double a[500];
};


Or an array of some other type. Templates allow you to use a wildcard in place of an actual type.

template <typename T>
struct vector 
{
  T a[500];
};


Anyone wanting to use your vector template class could say vector<int> or vector<Object> or even vector<void*>. That's the magic behind templates.

Templates are completely compile-time. That means using templates may mean a longer compile time, but they will not hurt you in terms of speed during your program's execution. When the program is being compiled, the template is instantiated. An instance of that template for some specific object (or any type) is created.


template<typename T>
struct vector 
{
  T f();
};

struct Abstract_Base 
{
  virtual void func() = 0;
};

struct Derived 
{
  virtual void func() {}
};

int main() 
{
  vector<Derived> vector_of_deriveds;
}


This code is changed to this by the compiler: (Note: this isn't exactly what happens, but the general idea is followed)


struct vector<Derived> 
{ 
  Derived f();
};
struct Abstract_Base .... and on like normal


For every specific type you instantiate in a template object, a separate class will be created to accomodate it. If you used no vector<> objects, no vector<> classes would be created.


int main() 
{
  vector<Abstract_Base> vector_of_abstract;
}


An abstract base class (ABC) can't be created because of the rules of C++. It has undefined functions, and C++ can't easily guarantee that the ABC won't call them. (A pointer could hide the ABC's true identity).

As a typename, an ABC can be used as long as it follows the rules for any other object. However, there's a problem here. This class would be created:


struct vector<Abstract_Base> 
{
  Abstract_Base a[500];
};


This violates the rules of C++ and it will cause a compile-time error.

Templates can also be derived from like normal classes:


template <typename T>
class Base 
{
  virtual T* clone() const;
};

template<typename T>
class Derived : public Base<T>  //note the syntax
{  
  virtual T* clone() const;
};


This is legal code. T* clone() is overwritten for the Derived<T> class.

NOTE: Some compilers, like some versions of gcc (none which are modern, mainstream versions), give an error for template derived classes if they call parent object member functions without parameters. Just attach a this-> in front of it, and you should be ok.

Templates are also useful when specialized.


template <typename T>
class Object 
{
  protected:
    T x;
  public:
    T* other_func();
};

class Derived : public Object <int> 
{
  public:
    int some_func() 
    {
      return x;  //legal
    }
};
template<>
class Object<bool> 
{
  public:
    void func() {}  //does not have to exist in any other instantiation.
    //this could become a totally different class from Object<int>
    //nothing is borrowed from Object<> once you specialize it
};

int main() {
  
  Derived o_i;
  Object<bool> o_b;
  o_b.func();
  Object<Object<double> > o_o;
  return o_i.some_func();
}


This is also valid code. Object<bool> doesn't have to be the same as Object<anything else>

Templates may also have multiple arguments (or none at all):


template<typename F, typename L>
struct cons 
{
  F first;
  L last;
};
int main() 
{
  cons<int,double> zebra;
  return zebra.first;
}


Functions may also be templated:


template<typename T> //note: you can use 'class' in place of 'typename' here
T* clone(const T& t) 
{
  return new T(t);
}


The compiler will detect what T is by the type of the first parameter of the function. It will not promote that type unless you do it yourself:


int main() 
{
  std::string* temp;
  temp = clone<std::string>("string-thang"); //this casts from a char* to a std::string
  return 0;
}


Templates may also be used in a thing called metaprogramming. (ie: Making your compiler work like a dog.) You can unroll loops, create large, compile-time lists, and a whole bunch of other stuff I don't have time to get into; all without a run-time penalty. (And sometimes even a time bonus.)

Here's an example of a compile-time linked list:


template<typename F, typename L>
struct cons 
{
  F first;
  L last;
};
struct nil {}; //empty
class Console 
{
  private:
    typedef  //here's the magic
      cons < int,
        cons < double,
          cons < vector < int >,
            nil > > > list_of_types;
    list_of_types l_o_s;
  public:
    Console();
};


The significance here is you can deal with your list of objects during compile-time. You can also make complicated things simple.

Have you ever dealt with a bunch of objects which just existed in your class, which you needed to access later on? One way was to give each object a unique name, like OBJ_1, OBJ_2, ... OBJ_31. It makes sense to the programmer, but you can't easily modify each member of the set.


Console::Console() 
{
  parse(l_o_s);
}
typename <typename F, typename L>
void parse(cons<F,L>& listing) 
{
  add_pointer(&listing.first);
  parse(listing.last);
}

void parse(nil&) {}


Templates can also do compile_time computations:


template <unsigned int x>
struct factorial 
{
  static const unsigned int result = factorial<x-1>::result * x;
};
template<>
struct factorial<0> 
{
  static const unsigned int result = 1;
};
int main () 
{
  return factorial<3>::result;  //exactly the same as return 6;
}


Hopefully you've seen what templates can do. They can save a lot of time and hassle when used properly.

Credit: ygfperson.

Script provided by SmartCGIs