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.