Challenge #11

Templates & Sorting
Templates enable us to define functions and classes that have parameters for type names – essentially then we can use the same function (or object) for use with different types, making our programs much more flexible. Consider the following functions;

void swap_values(int& variable1, int& variable2)
{
int temp;
temp = variable1;
variable1 = variable2;
variable2 = temp;
}
void swap_values(char& variable1, char& variable2)
{
char temp;
temp = variable1;
variable1 = variable2;
variable2 = temp;
}

The function name is overloaded to deal with first integers and then characters. The function is one we should be familiar with, simply to swap two values (maybe as part of a sorting algorithm. The function is quite disappointing though, especially if we consider that to swap 2 double type variables, we’d need to write a third function. Wouldn’t it be nicer if we could just send any type to the one function and it swap them over – afterall we only mention the type 3 times! Well, yes there is a way to do this, and it involves using templates;

template <class T>
void swap_values(T& variable1, T& variable2)
{
T temp;
temp = variable1;
variable1 = variable2;
variable2 = temp;
}

Sorting Functions

Consider the following 2 functions – what do they do?

void sort(int a[], int number_used)
{
int index_of_next_smallest;
for (int index = 0; index < number_used – 1; index++)
{
index_of_next_smallest = index_of_smallest(a, index, number_used);
swap_values(a[index], a[index_of_next_smallest]);
}
}
int index_of_smallest(const int a[], int start_index, int number_used)
{
int min = a[start_index];
int index_of_min = start_index;
for (int index = start_index + 1; index < number_used; index++)
if (a[index] < min)
{
min = a[index];
index_of_min = index;
}
return index_of_min;
}

They sort an array of integers – before we carry on, make sure you understand how it does it.
Now suppose we want to sort an array of doubles, or characters, or any other object – what would we need to do? Looking at the above functions the word ‘int’ is used 3 times when indicating the type of the value stored
in the array – identify them! These three instances can each be replaced by a template class and it will make the same code usable for arrays of several different types. In fact it will make the functions usable by an array of any type so long as they have the assignment ‘=’ and ‘<’ operators correctly defined. This added note is important.

Exercises

Part 1: Change the code above so that you can use the sorting algorithm to sort arrays of different types – i.e. integers, characters, doubles etc. – write a demonstration program to demonstrate it.

Part 2: Add the following functions to your Doubly Linked List class from last week:-

a) Sort – You may use the sorting algorithm shown above.
b) Unique – removes duplicates values from the list.
c) Extend your Doubly Linked List, so that you have a linked list that can contain a list of any type of data (not just integers).