16 Class Templates

Bhushan Trivedi

epgp books

Introduction

 

Class templates help us define a generic class. This generic class can be used for any type that we can specify when we use the class for defining objects of the class. In this module, we will take a very simple example of a stack to understand how class templates can be defined and used. The stack is a data structure where whatever is inserted last is popped out first. It is used in programming, operating systems and even programs that are used by robots. We will see how class templates are defined, how members can be defined, how class templates are put to use and how specialization of a class template can be defined and used.

 

Class Template

 

Class template is a sketch of what a class look like, containing member functions and data members. The generic type is used whenever necessary. Like function template, the class template describes an outline and no real class. The real class comes into existence when a class is instantiated for a real type, when an object of that class is defined. When a class with a specific type is generated from a class template usually when an object of that class for that specific type is encountered, that process is known as a class instantiation. The class with that type, which comes into existence at that point in time, is known as an instantiated class.

 

Let us learn the process of defining and using a class template by taking an example of Stack class. Here we will define a class template Stack. We can use this template to define many different types of stacks. When we definite an object, we will specify the type; at that point in time, the class with that specific type is instantiated from that template and the object comes into existence as an object of the newly instantiated class. Like function templates, the class

template is only instantiated when the object is defined and not otherwise. Like the function template, the definition itself does not consume any memory, the memory to store the class function members is allocated when the first object of that class is defined and the class is actually instantiated.

 

Let us start discussing the class template stack. The stack is a simple data structure with an ability to return the element which is last inserted. Here is the code for the generic stack class in program 17.1 block 1. The template class definition header resembles the template function definition. It begins with word template and has an <> section where the type is defined like function template. We have chosen a very simple array based implementation of the stack with 10 elements. SP is a stack pointer  stack indicating no elements. The array value 0 indicates that position. When an element is inserted in the stack, the SP value is incremented by 1 while when an element is removed the SP is decremented by 1. We define two operations push and pop on the stack, push inserts the element of specific type while pop removes the topmost element and returns it. This pop is designed to return the element of generic type  eType. We have also provided code for checking if we are popping from an empty stack or pushing into a stack which is already full.

Look at the second block of the program 17.1. it describes the main function of the program where we are defining two different types of stack and using them. Closely observe the following definition.

Stack <int> iStack;

 

At this point in time, the class stack with int type ( that means the stack of int) is instantiated. Additionally, an object iStack is also defined. Later on, when the following statement is encountered, a stack class with character elements is instantiated. Additionally, a new object cStack of type stack <char> or stack with elements of type char is defined as well.

 

Stack <char> cStack;

 

Two functions, push for inserting an element and pop for picking up the topmost element are defined and used. Calling template members is similar to calling normal member functions. If you closely look at the definitions, you can realize that Stack <int> and Stack <char> are classes and thus they are used in the expressions as a class would have been used to define an object in above statements.

 

Like the function templates, the class templates can also be used to define multiple objects. The class is instantiated only when the first object is defined. For example, if we have following two objects defined, only in the case of the iStack1, the class is instantiated and the object is initialized. The second definition of iStack2 only initializes that object.

 

Stack <int> iStack1;

Stack <int> iStack2;

 

It is possible to define the member functions like push and pop outside the class. The next section describes how that can be done.

 

Defining template members outside the class

 

Let us try to define both push and pop outside stack. Here is the program 17.2.

There are two operations to be performed when a member function is defined outside the class. The first is to provide a forward definition.

 

void push(eType );

 

eType pop();

 

Two lines shown above are used in the class stack to indicate that there is two functions pop and push for the class. This is known as a declaration. This is compulsory when a member function is defined outside the class.

The definition outside class contains the same body as in the previous case described in the program 17.1. However, the header has major additions. Like other definitions, when a member function is defined outside a template class, it becomes a template function (as it depends on the type for which the class is to be instantiated, the member function needs to be instantiated with the same type). Thus the member function definition starts with template and <> section with the types to be used defined within. The member function, when defined outside the class, has to be preceded by the name of the class and scope resolution operator. Here the stack is not a name of the class. The class that a push or a pop is a member of is Stack <eType> and thus the member function is defined as

 

template <typename eType>

void Stack<eType> ::push(eType value)

 

Please note that using an expression like Stack:: push will be an error because there is no class as Stack. We must use Stack <eType> to describe a typical class. Stack is a template and Stack<eType> is an instantiated class Stack of type eType.

 

You may wonder why one should define a function outside the class and provide this seemingly clumsy syntax. The idea is to give a clear visualization of the class. If one needs to look at the function in detail, it is defined outside. Another case is when we have a circular definition of classes where class 1 uses class 2 and class 2 is using class 1. The member functions of one class cannot be defined before the definition of the other class and the best place is to define them after the definition of both classes gets over. You can refer reference-1 for some examples of the similar type.

 

Safe Array

 

Let us take an interesting example of how a template class can be put to use to define an array where boundary checks are made. Like C, normal array access does not deploy any boundary checks and if ever an array element with an incorrect index is accessed, it results in a logical and not physical error. For example, if we have defined an array of int values as follows.

 

int A[10];

in above case, if we try to write following statements

int val = A[12];

int item = A[-1];

 

Both the statements possibly are compiled without any indication of something being wrong, (there might be a warning but no error). Not only that, they will run without showing any error as well. However, the consequences are serious as we are referring to and writing to unknown locations1.

  • 1 Usually such array calls are replaced by formulae. For example, A[12] is A + 11 where A is a pointer pointing to the first element. Whatever is stored at that address is picked up and used. It may be another variable defined just next to the array definition. A programmer hardly wants such behavior!

The problem appears becasue when a C or C++ code contains a statement where an array element is accessed, it does not check for array boundary related errors. The idea is to save instructions. The C designers assumed that the C language will be used by top flight programmers and they hardly make a mistake of accessing an array with an invalid index. Though this is more or less true that we do not generally find a case where a programmer accessing an array with an invalid index, it is sometimes done with disastrous consequences. We have no alternative in C but while working with C++ we have an option of using a safe array. How that array can be defined and used is the theme of next section. Obviously, we need to use a class template for defining this safe array. Let us see how we can do it with a simple example.

 

Class template for safe array

 

Let us write a class template where we are going to have an array where if a user tries to access an element outside the range, the program won’t compile.

 

Here is the code described in program 17.2, block 1 and 2. The first block describes the template class while the second block describes the main function, and how that safe array is put to use. Look at block 1.

 

In the regular template definition of type, you can see two things which are different than the previous program. First, a new argument Size which is a non-generic type argument which we have studied during the discussion  of  function templates The second, we can provide default arguments to a class template. The following statement  indicates  that  the type value, if unspecified assumed to be an int and if the size value is unspecified, assumed to be 10.

 

// SafeArray.cpp Program 17.2 block 1
#include <iostream>
using namespace std;
template <typename Type = int, int Size = 10>
class SafeArray
{
Type Array[Size];
public:
Type & operator [](int Index)
{
if ((Index < 0) || (Index > Size – 1))
{
cout << “invalid subscript !”;
exit(1);
}
else return Array[Index];
}
};

 

template <typename Type = int, int Size = 10>

class Safe Array

template arguments2. Default arguments are now possible with function templates but not

 

very useful.

  • 2 You may kindly note that there was no equivalent default argument for a function template for a long time. The reason is surprising; the standardization committee had realized that the function template is missing a feature which the class template has (the default arguments) at a much later stage where it was not possible to change the standard. The later version of ANSI C+ has added a default argument in function templates and

Another interesting point is how an array subscript operator is overloaded. You can refer to Reference-1 for further understanding how such an operator is overloaded and used. Look at how the second block uses the SafeArray objects. We are using the same notations we have used in the previous module. s_i_A is a safe array of int values while s_c_A is a character array which is boundary safe.

 

  • // cpp Program 17.2 block 2 int main()

{

SafeArray<int,9> s_i_A1;

SafeArray<char> s_c_A1;// Size = 10 SafeArray<> s_i_A2;

  • // Type = int and Size = 10

SafeArray<char,7> s_c_A2;

//SafeArray s_i_A;

s_i_A1[0] = 12;

s_c_A1[7] = ‘a’;

s_i_A2[9] = 34;

s_c_A2[2] = ‘x’;

}

Following statement defines a safe array s_i_A1 of type int and size 9.

 

SafeArray<int,9> s_i_A1;

Following statement defines a safe array s_i_A1 of type int and size is default to 10.

 

SafeArray<char> s_c_A1;// Size = 10

 

Following statement defines a safe array s_i_A1 of type default to int and size is default to 10.

 

SafeArray<> s_i_A2; // Type = int and Size = 10

 

Following statement defines a safe array s_c_A2 of type char and size to 7.

 

SafeArray<char,7> s_c_A2;

 

Kindly note that unlike function templates, we cannot write following statement. It won’t compile as there is no argument deduction process in class templates.

 

//SafeArray s_i_A

 

 

The compiler accepts all versions of the SafeArray definitions when we use default arguments, with no argument, one argument or both arguments. The compiler supplies the missing arguments based on the default argument specified in the class definition.

 

Let us recap, a template function can have a default argument containing a specific type. Whenever a function is called without specifying the type, those default types are assumed in place. The Safe array is an array where if the user access array using the out of bound  disparity was removed. We can write the code with default arguments in function template as well in later compilers. If you are using an old compiler, it will not compile. However, a default type argument is of little use in function templates. indexes, the program does not compile. It is an array where the array boundaries are checked before an access to an element is allowed, unlike conventional C and C++ array access.

 

Static members

//Program 17.3 Block 1

//StaticDataMembers.cpp

#include <iostream>

#include <string>

using namespace std;

template <typename eType>

class Stack

{

private:

int SP;

eType sArray[10];

public:

static int sTotal;

Stack(): SP(0)

{

sTotal++;

}

void push(eType );

eType pop();

};

template <typename eType>

int Stack<eType>::sTotal;

 

template <typename eType>

void Stack<eType> ::push(eType value)

{

 

if (SP > 9)

cout << “Overflow!”;

else

sArray[SP++]= value;

}

template <typename eType> eType Stack <eType>:: pop() {

if (SP == 0)

cout << “Underflow”;

else

return sArray[–SP];

}

Like normal classes, we can use static data and function members for storing information class-wise in template classes; for example, counting number of elements of a typical type of stack.

 

Let us see how that can be done based on the program described in 17.3 block-1 and 2. The block-1 describes the class stack that we have already seen in the previous program but with an additional static int member, sTotal defined inside the public section using the following statement.

static int sTotal;

 

Another change that you can notice is as follows in the default constructor of the Stack template. The sTotal value is incremented in the default constructor itself.

 

Stack(): SP(0)

{

 

sTotal++;

}

 

The idea is to increment a total number of stacks when a new stack object is defined. sTotal, being a static member, is available even when there is no object of the class defined and thus we can address the static member sTotal in such a case. We also initialize the SP to zero.

 

Before we proceed further, let us remind ourselves that static members of the class are not like data members and they only have a single copy to be shared by all objects of the class. Thus when we define a static member, that member’s single copy is stored with the class. For example, if we encounter following statements, where sInt is a static int member of SomeClass.

 

SomeClass SC,SC1,SC2;

 

SC.sInt = 5;

cout << SC1.sInt << SC2.sInt // this will print 5 twice.

cout << SomeClass::sInt         // this will also print 5

 

 

You can see that the sTotal is defined like the member functions that we have defined before; having a template keyword defining the type and the definition of sTotal preceded by the scope resolution operator, which in turn is preceded by the type of stack that we are planning to generate.

 

cout << Stack<int>::sTotal<<“\t”;

cout << Stack<char>::sTotal<<“\n”;

 

You can see that the use of the static member is like normal class static members. The only difference is the section with <>.

 

Class specialization

 

Like function templates, the template class can also have specializations. a class specialization is a class template which acts as a special case of originally defined class template. In this case the originally defined class template has a specific type of which the specialization type is a subset. The specialization begins with an empty declaration section as template <>. Let us take a simple example to understand. We will be discussing a specialization of a class Stack now. We will have an example of a special Stack for Emp class objects. The difference is, we do not insert the entire emp object in the stack while pushing. We only insert the employee number inside. When we pop the element, we also get the employee number from the array. This will make the stack lightweight, especially in the case of employee object being too heavy. The overhead is the additional access to the object from the array. This  solution saves memory at the cost of performance.

 

//Program 17.4 Block 1 //ClassSpecialization.cpp //initialization part

 

class Emp

 

{

//other definitions

friend Stack <Emp>;

 

};

Emp dummyEmp (0,””,””,””);

// overloaded << for cout

Emp EmpList[]=

{//same EmpList

};     

Let us look at the code of the program block after block. Let us look at the first block. That block defines a class Emp which we have already seen in the previous module. A typical dummyEmp is defined which is returned when the search fails at later stages. That employee is special with empNo is zero. We also define a list of employees next using the same EmpList which we have seen in the previous module In the second block, we define a generic search function for searching in the employee array and return the index of the item. When we define a specialization of Stack for storing Emp objects in it, we will

 

only insert the empNo inside. When we pop that empNo, we will search in the array and get the complete Emp object based on that index value and that will be returned back.

 

 //Program 17.4 Block-2 //ClassSpecialization.cpp template <typename Type>   

int gSearch(Type t_g_A[], Type

for (int i=0 ; i < 10;)

    if (eSearch == t_g_A[i]) return i;

 

The second block defines that function, named as gSearch. It uses an array t_g_A and searches an element of generic type eSearch. The search is a linear search, checking each of the objects of the array and returns the index. If the element is not found it will return -1. Now, it is the time to look at the most critical component of the program, the block 3 which defines the template class Stack (like earlier programs) and a template specialization. The template specialization begins with the following indicator.

 

 

template <> class Stack <Emp>

 

 

The empty braces <> indicates the specialization and the definition class Stack <Emp> indicates that the specialization is about the type Emp. That means it describes the class structure when objects of insertion are Emp objects.

 

Now you may be able to understand the need for the statement found in the Emp class earlier.

friend Stack <Emp>;

 

This statement is needed because the private member EmpNo is accessed by this class. Without this friend definitions, statements like the following result into an error.

 

enoArray[SP++]= tEmp.EmpNo;

 

Now it is the time to look at the detail description of the specialization

The SP is initialized like before to zero. Push function

 

works little differently now, instead of inserting an element of Emp object, it only inserts the EmpNo using the statement which we have just seen. Similarly, the pop() function is changed accordingly. It extracts the topmost employee number (not the object but number only). Once we get the number, we invoke the generic search using the following statement.

 

int sIndex = gSearch(EmpList, Emp(tEmpNo,””,””,””));

 

 

It searches the array and returns the index where the element is stored in the array. If the value returned is -1 (employee is not present in the array), we return the dummy employee object that we have already defined in a global fashion, otherwise, we will return a typical employee object from the array. The final block that we are going to see describes the main function itself. It calls the push and the pop with the employee list values that we have seen.  The  output  is  displayed  in  exactly reverse order of the definition of the array, why? Because the last element inserted in the stack is popped out first. If the statement cout << EmpStack.pop(); sounds interesting, it is because we are using an employee object as an output. This statement won’t work if we have not returned employee reference (Emp &) from pop(). The original stack used the value parameter passing and here we use an Emp &. So when the pop() function is called, it returns the reference of the object which we can use in the overloaded operator function << on the left-hand side. If it does not return a reference, it could not do so.

 

Summary

 

We have seen how class templates can be defined and used in this module. We have seen how class templates’ member functions can be defined outside the class, how static members can be defined and used in the class template and how one can define and use the specialization of a class template.

 

you can view video on Class Templates

References

 

  1. Programming with ANSI C++, Bhushan Trivedi, Oxford University Press
  2. www.stroustrup.com, homepage of Bjarne Stroustrup, the creator of C++