CMPT
225 Lab - A Template Function
This lab will cover the basics of
writing a template function in C++. Templates allows us to create classes or
functions that can be used to manipulate data of any type thereby avoiding the
need to create multiple similar classes or functions that differ only in the
type of data that they use. There are a couple of examples of template classes
(List and Stack) posted on the lecture
notes page. You can find more about class templates here (about half
way down the page), and function templates here.
Introduction
Let's say I write a function to
sort integer arrays. If it was well written it will do a good job of sorting
arrays of integers. But what happens when I want to sort an array of strings?
Presumably, I must write another function, one that is functionally identical,
but where its array parameter contains strings. This seems very inefficient
(and prone to irritating errors if I copy and paste much of the code from
function to function). And, of course, once I have sorted my strings I may
decide that I need to sort some doubles ...
Templates deal with this issue by
using template parameters. A template parameter is a parameter that can be
given a type as an argument at compile time, at which point the function is
created.
In this lab you will make a
selection sort template function.
Getting
Started
Copy and paste the code at the end of this
document into a .cpp file and run it. The code implements the selection sort
function (which we will be looking at in class shortly). The algorithm is
divided up into three functions.
selectionSort
getSmallest
swap
This is partly to make the three processes
involved in the sort explicit and partly to give you more practice turning
functions into template functions.
Have a good look at the program and satisfy
yourself that you know what it is doing. One thing to note is that the program
already includes a template function that prints the contents of an array one
line at a time. Its prototype is:
template <class T> print(T arr[], int
n);
The keyword template indicates
that it is a template function. The <class T> indicates a template
parameter. The word class denotes
that the argument passed to the template parameter should be a type and T is the name of that template parameter
(so the T could be anything).
Selection
Sort Template Function
Now change the three functions that make up
selection sort into template functions that will sort data of any type. Test
that it works correctly by sorting the array of strings that is declared in the
program. You can use the print
function for a model for how to achieve this. This involves a fair amount of
copying and pasting of template parameters, but should also involve some
thought. Don't just replace every incidence of int with T. Remember that
indexes have to be integers!
Once you are finished sort the array of
strings before printing it.
Get
Smallest Recursively
If you have time re-write the getSmallest
function as a recursive function.
Program
You can find the program file
here: cmpt225labtemplate.cpp.
John Edgar (johnwill@sfu.ca)