CSE2305/CSC2050 - Object-Oriented Software Engineering
Week 10

Topic 20: C++ Templates

Synopsis

Remember ¤ genericity¤?
Recall the linked list example
A better solution
Creating a C++ template
Using a C++ template
How to design a templated class ¤
What parameters can a template have?
Function templates
Coping with exceptional behaviour ¤
A scary example to finish with
Reading

Remember ¤ genericity¤?

Abstraction¤ of structure
Independent of type
A "slot-in-the-type" template for building structs or functions

Recall the linked list example

A linked-list ADT to store ints:


        	struct NodeRec
        	{
        		int             data;
        		struct NodeRec* next;
        	};
        	typedef struct NodeRec  Node;

        	struct ListOfInt
        	{
        		Node* head;
        		Node* current;
        	};

        	void LOI_Initialize(ListOfInt* list);
        	void LOI_InsertBefore(ListOfInt* list, int data);
        	void LOI_InsertAfter(ListOfInt* list, int data);
        	void LOI_DeleteCurrent(ListOfInt* list);
        	int  LOI_First(ListOfInt* list);
        	int  LOI_Next(ListOfInt* list);

A linked list ADT to store student record structs:


        	struct NodeRec
        	{
        		StudRec         data;
        		struct NodeRec* next;
        	};
        	typedef struct NodeRec  Node;

        	struct ListOfStudec
        	{
        		Node* head;
        		Node* current;
        	};

        	void LOSR_Initialize(ListOfStudRec* list);
        	void LOSR_InsertBefore(ListOfStudRec* list, StudRec data);
        	void LOSR_InsertAfter(ListOfStudRec* list, StudRec data);
        	void LOSR_DeleteCurrent(ListOfStudRec* list);
        	StudRec LOSR_First(ListOfStudRec* list);
        	StudRec LOSR_Next(ListOfStudRec* list);

A linked list #define for "stamping out" variants:


        	#define  DECLARE_LIST_OF(TYPE, PREFIX)			    \
        								    \
        	struct NodeFor##TYPE##Rec				    \
        	{							    \
        		TYPE                       data;		    \
        		struct NodeFor##TYPE##Rec* next;		    \
        	};							    \
        								    \
        	typedef struct NodeFor##TYPE##Rec  NodeFor##Type;           \
        								    \
        	struct ListOf##TYPE					    \
        	{							    \
        		NodeFor##TYPE* head;				    \
        		NodeFor##TYPE* current;				    \
        	};							    \
        			    					    \
        	void PREFIX##_Initialize(ListOf##TYPE* list);		    \
        	void PREFIX##_InsertBefore(ListOf##TYPE* list, TYPE data);  \
        	void PREFIX##_InsertAfter(ListOf##TYPE* list, TYPE data);   \
        	void PREFIX##_DeleteCurrent(ListOf##TYPE* list);	    \
        	TYPE PREFIX##_First(ListOf##TYPE* list);		    \
        	TYPE PREFIX##_Next(ListOf##TYPE* list);

A better solution

The macro version is hard to understand, tedious to use, and easy to mess up
A better solution would be if we had a means of telling the compiler what we want and letting it do the hard work of getting it right
In C++ we have such a means: templates
A template is a piece of code which tells the compiler how to build a class¤ definition (or a function definition - see later) by filling in "generic¤" bits (usually types)

Creating a C++ template

Creating templates is easy
Simply write the class¤ the way you want it, but replace the "generic¤" bits with special identifiers
Then use the template keyword before the class¤ to tell the compiler which identifiers are special
For example, here's an object oriented version of the linked list for ints:


        	class ListOfInt
        	{
        	public:

        		ListOfInt(void);

        		void InsertBefore(int data);
        		void InsertAfter(int data);
        		void DeleteCurrent(void);
        		int  First(void);
        		int  Next(void);

        	private:
        		struct Node
        		{
        			int   data;
        			Node* next;
        		};

        		Node* head;
        		Node* current;
        	};

And an object oriented version of the linked list for StudRec:


        	class ListOfStudRec
        	{
        	public:

        		ListOfStudRec(void);

        		void InsertBefore(StudRec data);
        		void InsertAfter(StudRec data);
        		void DeleteCurrent(void);
        		StudRec First(void);
        		StudRec Next(void);

        	private:
        		struct Node
        		{
        			StudRec data;
        			Node*   next;
        		};

        		Node* head;
        		Node* current;
        	};

Finally, here's an templated version of the linked list (i.e. for any type):


        	template <class TYPE>
        	class ListOf
        	{
        	public:

        		ListOf(void);

        		void InsertBefore(TYPE data);
        		void InsertAfter(TYPE data);
        		void DeleteCurrent(void);
        		TYPE First(void);
        		TYPE Next(void);

        	private:
        		struct Node
        		{
        			TYPE  data;
        			Node* next;
        		};

        		Node* head;
        		Node* current;
        	};

Using a C++ template

Now we can call specific ListOf<...> classes¤ into existence:


        	class ListOf<int>;		// EQUIVALENT TO ListOfInt

        	class ListOf<StudRec>;		// EQUIVALENT TO ListOfStudRec

        	class ListOf<string>		// CLASS TO STORE string OBJECTS

        	class ListOf<Target>		// CLASS TO STORE Target OBJECTS

        	class ListOf<Nominee>;		// IN THE CATEGORY
        					// "Best Template in a Supporting Role"

        	class ListOf<Winner>;		// AND THE WINNER IS...Shirley Template!

        	class ListOf< ListOf<int> >;	// WOW!

Better still, we don't actually ever need to "call them into existence"!
We can just use them as if they had been "called into existence", and the compiler will automatically fill in the details for us:


        	int main(void)
        	{
        		ListOf<double> marks;      // COMPILER CREATES THIS TYPE
        		ListOf<int>    ids;        // AND THIS TYPE 
        		double         nextmark;
        		int            nextid;

        		while (cin >> nextid >> nextmark)
        		{
        			ids.InsertAfter(nextid);
        			marks.InsertAfter(nextmark);
        		}

        		// ETC...
        	};

Best of all, only the bits of the class¤ that we actually use ever get created

How to design a templated class ¤

Don't!
Design an ordinary class¤ (or two or three) which does the job for specific types (e.g. ListOfInt and ListOfStudRec)...
...then study the commonalities...
...and replace them with generic¤ identifiers (e.g. TYPE)...
...and finally a template keyword and a type parameter list in front.

What parameters can a template have?

One or more types, each introduced by the class keyword
For example:


        	template <class KEYTYPE, class DATATYPE>
        	class AssociativeArray
        	{
        	public:
        		AssociativeArray(void);
        		~AssociativeArray(void);

        		DATATYPE& operator[](const KEYTYPE& key);

        		ListOf<KEYTYPE>  Keys(void);
        		ListOf<DATATYPE> Values(void);

        	private:
        		// MAGIC CODE TO MAKE IT ALL WORK :-)
        	};

        	// AND LATER

        	int main(void)
        	{
        		AssociativeArray<string, double> result;

        		result["Damian"]  = 100.0;	// SET THE EXAM
        		result["Boris"]   = 49.9;	// WAS DRUNK
        		result["Ai Joo"]  = 77.7	// GOOD STUDENT
        		result["Damien"]  = 66.6	// EVIL STUDENT

        		string name;
        		while (cin >> name)
        		{
        			cout << result[name] << endl;
        		}
        	}

One or more integral values, each introduced by the actual type used:
For example:


        	template <int MAXSCORE, int PASSMARK>
        	class ExamResults
        	{
        	public:
        		ExamResults(ListOf<ints> ids, ListOf<double> scores);
        		~ExamResults(void);

        		void PrintPasses(void)
        		{
        			double nextmark;
        			int    nextid;
        			while (GetNextMark(nextid,nextmark))
        			{
        				if (nextmark>=PASSMARK)
        				{
        					cout << nextid << ": "
        					     << nextmark/MAXSCORE*100
        					     << endl;
        				}
        			}
        		}

        	private:
        		// MAGIC CODE TO MAKE IT ALL WORK :-)

        		bool GetNextResult(int& id, double& mark);
        	};

        	// AND LATER

        	int main(int argc, char* argv[])
        	{
        		ListOf<int>    idlist   = getIDList($argv[0]);
        		ListOf<double> marklist = getMarkList($argv[0]);

        		ExamResults<100,50> passHalf(idlist, marklist);
        		ExamResults<100,90> passReal(idlist, marklist);

        		cout << "Normally pass at 50%..." << endl;
        		passHalf.PrintPasses();

        		cout << "But today pass at 90%..." << endl;
        		passReal.PrintPasses();
        	}

Function templates

Can also specify a template for the compiler to use to build functions
Once again, specify the "generic¤" bits as special identifiers, listed after the template keyword at the start:


        	template <class DATATYPE>
        	DATATYPE max(const DATATYPE& d1, const DATATYPE& d2)
        	{
        		return (d1>d2) ? d1 : d2;
        	}

        	// AND LATER...

        	int main(void)
        	{
        		string s1 = "cat";
        		string s2 = "dog";

        		cout << max(1,2) << endl;
        		cout << max(1.1,2.2) << endl;
        		cout << max(s1,s2) << endl;

        		cout << max("cat","dog") << endl;
        		cout << max(1,2.2) << endl;
        	}

Coping with exceptional behaviour ¤

The call to max("cat","dog") causes the template to instantiate a function: char* max(char*, char*):


        	char* max(const char*& d1, const char*& d2)
        	{
        		return (d1>d2) ? d1 : d2;
        	}

The syntax is okay, but the semantics are deceptive
Hence we need to be able to create a special version of the function to be called instead
This special version is called a "specialization¤"
For example:


        	template <>
        	char* max(const char*& d1, const char*& d2)
        	{
        		return (strcmp(d1,d2)>0) ? d1 : d2;
        	}

A scary example to finish with


        	template <long N>
        	class Factorial
        	{
        	public:
        		long Value(void) { return N * fn_1.Value(); }

        	private:
        		Factorial<N-1> fn_1;
        	};

        	template <>
        	class Factorial<0>
        	{
        	public:
        		long Value(void) { return 1; }
        	};

        	int main(void)
        	{
        		Factorial<15> f15;

        		cout << f15.Value() << endl;
        	}

Reading

Winston: Chapter 49

Stroustrup: Chapter 13

Lippman/Lajoie: Chapters 10 & 16

Last updated: Tue Jul 6 11:34:12 1999

Topic 20: C++ Templates

Synopsis

Remember¤ genericity¤?

Remember ¤ genericity¤?