Lesson 6. Templates and STL

Lesson 6. Templates


The best code is reusable in as many situations as possible. That’s why we use loops to repeatedly execute code, it’s why we use functions so we can use the same code on many parameters, it’s why we use structs and classes to roll many variables and functions into one, and in a broader sense, it’s why we programmers learn other programming languages that work for situations where one programming language is inefficient!

However, while we have been learning all of these cool new data structures lately, one thing that you may have noticed is that many of our functions and data structures rely on specific data types, meaning that if, for example, we wanted to make a linked list for ints and a linked list for strings, we would have to make a class for int nodes and a class for string nodes. Is there any way to fix that and make a more generic and reusable data structure? Well of course there is. Why else would I be writing this big long introduction? Get ready to meet the template!

With templates, you can make a function more generic so you can pass ANY data type to the function and make a class with ANY data type to be used.

In this example, we will take a function reverseArray. Right now it takes in an int array, which means it won’t work on arrays of strings, doubles, or any other type. You don’t need to pay too much attention to the code for any of the examples; the point I am trying to make here is about the versatility of the code, so in this tutorial in the actual code other than the template itself, you will be seeing me using un-professional programming practices.

void reverseArray(int x[], int size)

{
    for(int i = 0; i < size/2; i++)
    {
        int temp = x[i];
        x[i] = x[size - 1 - i];
        x[size - 1 - i] = temp;
    }
}

Very basic, but intuitively it seems like something you should be able to use on arrays with elements of any type. To do that, we give the function a template.


The basic format of the template is

template

function definition

in which you replace insertYourTypeNameHere with a type name you want to use.


For example, reverseArray has this templated version, with the use of anyType bolded:

void reverseArray(anyType x[], int size)

{
    for(int i = 0; i < size/2; i++)
    {
        anyType temp = x[i];
        x[i] = x[size - 1 - i];
        x[size - 1 - i] = temp;
    }
}

The thing I would like you to notice here is first of all that int is still used in this function even though one int parameter is replaced with the templated anyType. This is because only one parameter was replaced with anyType. The int, size, is still an int because its parameter is specified as an int.


Now, the other thing I would like you to notice is the fact that anyType can be any type and it makes sense that it would work on any type. Swapping an int does the same thing that swapping a char does. However, you don’t want to template every type. For example, take a look at this function!

template

int square(anyType x)
{
    return x * x;
}

This function squares the number passed to the function, but yet there’s a problem. Square takes in anyType, so what if you pass a string? You will probably get something weird since you don’t multiply strings by strings. In this case, you will want to keep this function un-templated.


You also can template multiple paramaters of a function. This is the format for a multi-templated paramater function:

template

function definition

For example, let’s make a multi-templated function printTwo, which prints the two parameters:
 
template

void printTwo(typeA firstItem, typeB secondItem)
{
    cout<< firstItem << " " << secondItem << endl;
}

This function will work for most data types, with the exception of struct and class-defined data types, which aren’t printed with cout, so you will probably want to make an invariant for this function that it will not be used on struct and class-defined data types.




Speaking of classes, you can also template a class. For example, let’s look at a templated version of a 100-space array stack.

Note: For simplicity, we will have evertyhing in the class in the class declaration, which normally is considered sloppy and un-professional code. You’ve already seen

template
class stack100

{
    private:
        int top;
        item stack[100];
    public:
    stack100()
    {
        top = 0;
    }
    void push(item x)
    {
        stack[top] = x;
        top++;
    }
    item pop()
    {
        top--;
        return stack[top];
    }
    item topItem()
    {
        return stack[top-1];
    }
    int size()
    {
        return top;
    }
    bool isEmpty()
    {
        return (top == 0);
    }
};

Now you have an array stack that can store up to 100 of any data type. Now to show you how to make one and specify the type of item it will store. Let’s try it with chars for example.

stack100 letters;

You can then use it on chars!


Let’s try it on ints!

stack100 numbers;
 
Basically the format for specifying the type for a templated class to work on is:
 
templatedClass name;
 
However, there are some data types that still won’t work. You need to be careful whenever you are templating something to be used with a string because strings are not primitive data types, and you also need to be careful using templated code on struct and class data!




Now, there is one last thing I will show you in this tutorial, and it’s that all those data structures you have learned so far, like linked lists, queues, stacks, and some structures you haven’t learned yet are all accessible in one library called the standard template library, or STL.

To get an STL data type into your code, you add this include at the beginning of the file:


#include

with type being replaced with the item you want. For example, to include queues, you do

#include

For vectors, which are automatically-managed dynamic arrays,

#include

There are many more data types covered in the STL, and you can check them out on www.cplusplus.com

However, you aren’t always going to rely on the STL. The STL doesn’t cover every data structure. Most notably, there is no STL type for trees. In addition, you may want to make your own version of the data structure so you can modify it with your own code.



This is especially true with trees, which you will learn about in the next big glob of tutorials; there are countless variations of trees, and in my tutorials and in COMP 15, you are only learning a few of them. Not only that, but since trees are a highly modifiable structure, at some point in the class, you’re likely to make your own variation of a kind of tree!