Templates allow you to build type-safe collections.  Templates are sometimes considered superior to linked lists
because linked lists can only handle the particular data objects they were created to work with.  You couldn't place a
different object into a linked list without modifying it.  Templates allow you to teach the compiler how to make a list
of any type of thing, rather than creating a set of type-specific lists.  The type of the thing in the list becomes a parameter to the definition of the class.  The Template class concepts we will deal with are the same as the concepts that cover our standard classes.  So therefore, template instantiation is the act of creating a specific type from a template, and template instances are marked by the individual class data types using the template.  Templates allow you to create a GENERAL CLASS and pass "types" as parameters to that class to build specific instances.  Therefore we can say that a Template is a class that is a parameterized List object.  Are we thoroughly confused now?  Fear not, brave one, this too shall pass. :)  You declare a template by writing:

The keyword "template" must be used at the beginning of every declaration AND definition of a template class.  The parameters of the template are written after it - they are the items that will change with each instance.  In the expression "template <class T>", the keyword "class" indicates that this is a parameter type and that the identifier, "T", is used throughout the rest of the template definition to refer to the parameterized type (the class).  One instance of this class will substitute "int" wherever "T" appears, another instance will substitute "Monster".  To declare an "int" and "Monster" instance, we would write:

List<int> IntList;            //would create a List of int objects
List<Monster> MonsterList;    //would create a List of Monster objects

The trick to template design is to get your template working on a single object/class type, then parameterize it, generalizing the template to handle any type of object.  Example:

// File 1 of 2.  This file is a header file called "Template.h"

//  Every class used with the template MUST have a constructor that takes an int, 
//  an "itsSize" data member, and a "GetSize()" accessor.

#include <iostream.h>

class Monster {
        
        public:
 
            Monster() {}
            Monster(int sz) { cout << "Monster created.\n"; }
            ~Monster() { cout << "Monster destroyed.\n"; }

            int GetSize() { return itsSize; }
            void SetSize(int str) { itsSize = str; }

        private:
            int itsSize;
};

/*--------------------------------------------------------------------------------------------*/
template <class T>       // Declare the template and the generic parameter, "T".  T represents
                                 // whatever object we will pass in to the template. Functions like a typedef
                                 // for multiple classes. This must come directly BEFORE the template class below . 
/*--------------------------------------------------------------------------------------------*/
class GenericArrayOfObjectsTemplate            //The class being parameterized
{
public:

	//Constructor For some "odd" reason, Monsters come in sets of 3
	//Remember what the songs says - "3 is a magic number"... :)
	GenericArrayOfObjectsTemplate(int size = 3) { 
            
           itsSize = size;

              //Below we are saying that pType will become a pointer of whatever type of object
              //we pass in to the template and will point to an array of whatever type
              //of object we pass in to the template.  T is declared a pointer in the private member data.

	   pType = new T[size];

	   for (int i = 0; i < size; i++) {
	        pType[i] = 0; }
	} //close constructor

	//Copy constructor
	GenericArrayOfObjectsTemplate(const GenericArrayOfObjectsTemplate & rhs) {
	       
               itsSize = rhs.GetSize();
	       pType = new T[itsSize];

	       for(int i = 0; i < itsSize; i++) {
	       pType[i] = rhs[i]; }
        } //close copy constructor

	//Destructor
	~GenericArrayOfObjectsTemplate() { delete [] pType; }

	// Overloaded Operator =
	GenericArrayOfObjectsTemplate& operator=(const GenericArrayOfObjectsTemplate &) { 
               
               //Just make sure it's not the object itself trying to copy itself
               if (this == & rhs)
	       return *this;

	       delete [] pType;
	       itsSize = rhs.GetSize();
	       pType = new T[itsSize];

	       for (int i = 0; i < itsSize; i++)
	            pType[i] = rhs[i];

               return *this;
         } //close function

	//2 Overloaded Operator [], one constant and one not
	T & operator[](int offSet) 
            { return pType[offSet]; }

	const T & operator[](int offSet) const
	          { return pType[offSet]; }

	//Accessors
	int GetSize() const { return itsSize; }

	//friend function prototype/declaration. Remember that a friend
	//function must be defined outside the class specification.

	friend void Intrude(GenericArrayOfObjectsTemplate<int>);

private:
        //T represents what this will be a class of - the template
	T *pType;
	int  itsSize;
};

/*--------------------------------------------------------------------------------------------*/

// Friend Function - Intrude  Declared type <int>, can only be used
// with int arrays!   No OTHER data type.  Intrudes into private data.

void Intrude(GenericArrayOfObjectsTemplate<int> theGenericArrayOfObjectsTemplate) {

	cout << "\n*** Intrude <int> Template***\n";

	for(int i = 0; i < theGenericArrayOfObjectsTemplate.itsSize; i++) {
	    cout << "i: " <<    theGenericArrayOfObjectsTemplate.pType[i] << endl;  }

	cout << "\n";
     }

In the example above, we set up a template class to allow us to create an array of whatever type of objects we pass into it.  In main(), six different objects and class instances are created.  The first five objects are instantiated from built-in types.  The last object is created from our own user-defined class, Monster.  In effect, it is as if we had created six different classes, though we did it with one declared template class, the GenericArrayOfObjectsTemplate.  Also notice that  template <class T> has to come just before the template class itself.  Position and placement of the template declaration keyword matters when declaring and defining template classes.  We made the function, Intrude(), a friend function so that it could be accessed by objects that were not of the class itself.  Remember that a friend function, in addition to using the keyword "friend", must be defined outside the class.  This enables them to circumnavigate restrictions on data members that would otherwise be private or inaccessible to objects that were not of that class or that did not derive from it.  In addition to class templates, we can create function templates:

Let's combine a template class and a linked list to handle three different kinds of objects:

In the template in linked list combination above, the same list can handle three different objects since the Node (ADT), Internal Node, TailNode and HeadNode have been declared as template classes.  Note that each class declaration and method is preceded with "template class <T>".  This tells the compiler that you are parameterizing this list on a type that you will define later when you instantiate the list.  So the declaration of the Node class must now become:

template <class T>
class Node

This says that Node will not exist as a class in and of itself, but rather that you will instantiate Nodes of Monsters, Nodes of Cats and Nodes of Data objects.  The actual type you will pass in is represented by "T".  The InternalNode will now become "InternalNode<T>".  The InternalNode<T> points to a "T" (whatever type of object is passed to it) and a Node<T>, not to a hard-coded Data object and another Node.

The Insert() has been re-defined.  Where there used to be a specific type of object, Data, now there is "T", representing whatever object is passed in.  The parameter is a pointer to "T".  Later, when specific lists are instantiated, the compiler will replace "T" with the corresponding instances of Monster, Data and Cat.  In this way, the InternalNode can continue working indifferent to the actual data type used.  It only asks the objects to compare themselves.  For this reason, each object passed into the template must support two methods:  Show() and Compare().  Depending on the nature of the object's data members, these methods will differ from class to class.  But as long as they are provided, this List can sort any number of generic objects.

You can treat template items just as any other type.  You can pass them as parameters by reference/pointer or by value, and you can return them as return values to functions, also by value or by reference.  Below is a rewrite of main() using the above example, to demonstrate passing template objects by reference and using them in functions.  You will need to include all of the code in the table above up to the main() function.

Like previous code, but this time LinkedLists are passed by reference to their respective functions for processing.  This can be powerful.  Once lists are instantiated, they can be treated as fully defined types, passed into functions and returned as values.  Each instance of the template is an actual object, and can be used like any other object, as though it were a separate class instance.

STL - The Standard Template Library is offered with most compilers as part of their headers and libraries.  It is a library of template-based container classes, including vectors, lists, queues and stacks.   These group together some common algorithms for sorting and searching.  The essential goal of the STL is to give you an alternative to reinventing the wheel.  You can stand on the shoulders of the programming giants who have come before you.  You can plug STLs into all your programs for specific functions for easier and faster development than if you had to code everything from scratch.  Yes - it is now time to pay homage to our venerable, unappreciated, overworked coding ancestors.  :)  We must send them a "thank you" out across the ether every now and then, as we grimace at their horror stories of misplaced punch cards, Fortran and iron core memory.  To all coding veterans who sailed the murky seas and brackish waters of the dark ages before cheap computers and GUIs to spare,  - we salute you!  Now, back to the STL.  Some of the most useful STL classes and algorithms are listed below with links:

• The string class
• The vector container template
• The sort algorithm
• The list container template
• The iterator classes
• The find algorithm

©2004 C. Germany