In order to make our bubble sort function more generic (an thereby more useful) we could give it a function signature something along these lines:
template<class T>
void bubbleSort(T numbers[], size_t size);
This would mean we could call the function with an array of any type and the compiler would deduct the type to instantiate the function using the first parameter i.e.
float f[4] = {1.1f,0.2f,-2.3f,0.3f};
int i[4] = {6,3,1,5};
char *s = "zyxw"; // nicer syntax than...
//char s[4] = {'z','y','x','w'};
bubbleSort(f,4); // uses float
bubbleSort(i,4); // uses int
bubbleSort(s,4); // uses char
With the wonders of (take a deep breath)
explicit template function argument specification we can do this now too...
bubbleSort<double*>(f,4); uses double
Even though we're using a float array the function is explicitly instantiated using the type
double. This would compile fine but obviously yield a runtime error in this specific case because we'd be performing pointer arithmetic (i.e using the array) with a
double type which is twice as big as the
float parameter. But hang on a second... why does it even compile? You may have noticed something amiss here... we've used
double* here explictly but when we don't specify the type i.e.
bubbleSort(f,4) shouldn't the type of
f be
float and not
float*? If this were true then our function would be written by the compiler thus:
// not what we get
void bubbleSort(float *numbers[], size_t size);
// this IS what we get!
void bubbleSort(float numbers[], size_t size);
The reason for this, and the reason why all the above code examples work is because when the compiler does type deduction it performs a number of type conversions on the actual type passed. If you want more details on this here's an excellent article by Angelika Langer on
Function Template Arguments. I learnt alot reading this article. Jump to the section entitled "Implicit Type Conversions Involved in Template Argument Deduction" if you are just interested in what we've been talking about here, but I heartily recommend you read the whole thing. Anyway, I've got off the beaten track again, it's time to finish making our poor old, slow bubbleSort generic... aren't we done? No. It may work in it's current state for all POD (Plain Old Data) types but try this:
std::vector<int> array;
array.push_back(6);
array.push_back(3);
array.push_back(1);
array.push_back(5);
bubbleSort(array, array.size());
...and you'll quickly see it doesn't work for STL containers. You could always compile it and see why but put simply it's because we are asking the compiler to instantiate something along these lines:
void bubbleSort(std::vector<int> numbers[], size_t size);
Which is obviously ludicrous! Anyway, when we want to iterate though an STL container we don't pass the containers to algorithms but the containers
iterator. I.e.
std::swap(array.begin(), array.end());.
The iterator is an abstract concept, by that I mean that anything that behaves like an iterator
is an iterator, including simple arrays. The reason why simple arrays are iterators too is because iterators are implemented using operator overloading of ++, --, [] among others (and depending on the type of iterator) to use the same syntax as pointer arithmetic. This gives us a clue as to how we can write our fully generic
bubbleSort function. If we pass "pointers" to the start and end we can use pointer arithmetic inside the function body and it should work with both simple arrays and STL containers. One thing to note is that STL ranges are defined with a closed start and an open end. This means the
begin() of an iterator points to the first element whilst the
end() actually points to the element directly
after the last element. This is something we need to be aware of when writing the function, luckily for us it is a really good design decision and greatly simplifies a lot of things for us! Anyway, I don't want to stray from the path of this blog anymore so perhaps we'll discuss STL ranges later, here's the final implementation of
bubbleSort...
template<class Iter, class T>
void bubbleSort(Iter left, Iter right, T)
{
bool swap = true;
while(swap)
{
swap = false;
for(Iter it = left + 1; it!=right; ++it)
{
if(*it<*(it-1))
{
T tmp = *it;
*it = *(it-1);
*(it-1) = tmp;
swap = true;
}
}
}
}
However we can't use this function in exactly the same way as we use
std::sort, it has 3 arguments! The first two specify the range we want to sort and the 3rd passes the type used in the container of the iterator! We need this to store our temporary variable
T tmp = *it. Notice that there is no parameter variable specified as we only need to use the type. This makes the usage of this function pretty ugly:
//dereference first element to pass type of container
bubbleSort(array.begin(),array.end(),*array.begin());
No worries we can use explicit function template argument specification! (I hear you cry ... erm), well no we can't. We'd have to specify all the template arguments which would make the function quite tedious to use. A better solution is to write a simple function overload to call the above for us:
template<class Iter>
void bubbleSort(Iter left, Iter right)
{
bubbleSort(left, right, *left);
}
This is a neat trick we can use to quite clearly derive the container type of an iterator in a lot of situations.
To conclude this part we now have a more useful generic version of our algorithm which can by used for simple arrays and STL containers. The point of this blog has been to demonstrate how it's possible to convert an algorithm into a more useful, generic form. We'll look at some faster sorting algorithms in part III...
