Topic 1b - Templates
Before continuing and introducing data structures, we need to introduce the concept of templates in C++.
Consider the problem of finding the largest item in an array of items.
We can do a very simple linear search to find it.
Activity
Do you think that the logic of this algorithm change depending on the type?
Until now, the function were strongly typed. It lacks flexibility, and C++ dev find a way around this problem by creating templates.
There are two types of templates:
Function Templates
Class Templates
If you know Java, it should be very familiar.
Function Templates
It will be very quick, as function templates are very easy to write.
Declaration
We will consider the following function template findMax
:
1/**
2 * Return the maximum item in an array a.
3 * Assumes a.size() > 0
4 * Comparable objects must provide operator< and operator=
5 */
6
7template <typename Comparable>
8const Comparable& findMax(const vector<Comparable>& a){
9 int maxIndex = 0;
10 for (int i = 1; i < a.size(); i++){
11 if (a[maxIndex] < a[i]){
12 maxIndex = i;
13 }
14 }
15 return a[maxIndex];
16}
It is short, but summarize everything.
Before the declaration of the function, we define the template argument Comparable
:
template <typename Comparable>
The type you will use will replace Comparable
if it has the correct properties.
Then in the function declaration, where you would put the type you have Comparable
instead:
const Comparable& findMax(const vector<Comparable>& a){
Using a function template
Once define, it is very simple to use the function template:
1int main()
2{
3 vector<int> v1(37);
4 vector<double> v2(40);
5 vector<string> v3(80);
6 vector<Int> v4(75);
7
8 // Aditional code to fill in the vectors not shown.
9
10 cout << findMax(v1) << endl; // OK: Comparable = int
11 cout << findMax(v2) << endl; // OK: Comparable = double
12 cout << findMax(v3) << endl; // OK: Comparable = string
13 cout << findMax(v4) << endl; // Illegal: operator< undefined
14
15 return 0;
16
17}
During the compilation the compiler will create the function for each type used.
As no operator<
was define for Int
the following line is illegal:
cout << findMax(v4) << endl; // Illegal: operator< undefined
One last thing. Because templates arguments can assume any class type, when deciding on parameter-passing and return-passing conventions, it should be assumed that template arguments are not primitive types.
That is why we have returned by constant reference.
Class Templates
Remember the class Int
that was memorizing a value of type int
, it was very limited as only a value of type int could be stored inside.
We will use this example, to show how we can create class templates.
Similarly to the function template, we need to define the template argument. In this case, I will choose Object
, because I want it to work for any type.
template <typename Object>
The class template will be called MemoryCell
, because we want to store object both primitive and class types.
1template <typename Object>
2class MemoryCell
3{
4 private:
5 Object storedValue;
6};
As you can see we store a type Object
.
Now we can redefine all the methods by replacing the type int
by Object
.
1template <typename Object>
2class MemoryCell
3{
4 public:
5 MemoryCell( const Object & initialValue = Object{ } )
6 : storedValue{ initialValue }
7 {
8
9 }
10 const Object & read( ) const
11 {
12 return storedValue;
13 }
14 void write( const Object & x )
15 {
16 storedValue = x;
17 }
18
19 private:
20 Object storedValue;
21};
It doesn’t change much from the class Int
, except for the constructor.
Indeed, as we can accept any class type, the default constructor create Object
with its zero-parameter constructor.
1 MemoryCell( const Object & initialValue = Object{ } )
2 : storedValue{ initialValue }
3 {
4
5 }
That is basically all that you need to know. After that it is practice, your own research, etc.
Warning
For class templates we don’t separate the interface from the implementation, everything is in the header file .h.
Otherwise it is not working properly; there is a way to avoid this issue, but we will not cover it today.