Templates with <class Comparable> in C++

I am attempting to compare algorithms. I am not familiar with the C++. I want to create a main where I will include the code below as a header. I don't completely understand what "template class Comparable" is though.

#include <vector>
using namespace std;

template <class Comparable> 
void SelectionSort(vector<Comparable> & nums, int low, int high)
{
    for (int i = low; i <= high-1; i++) {
        int indexOfMin = i;                     // traverse the list to
        for (int j = i+1; j <= high; j++) {     // find the index of the
            if (nums[j] < nums[indexOfMin]) {   // next smallest item
                indexOfMin = j;
            }
        }

        Comparable temp = nums[i];              // swap the next smallest
        nums[i] = nums[indexOfMin];             // item into its correct
        nums[indexOfMin] = temp;                // position
    }
}

template <class Comparable> void SelectionSort(vector<Comparable> & nums) 
{
    SelectionSort(nums, 0, nums.size()-1);
}

Solution

Your main sort function there looks like this (snipping the "template" part for now):

void SelectionSort(vector<Comparable> & nums) 
{
    SelectionSort(nums, 0, nums.size()-1);
}

Looks like a normal sort function that acts on a vector of Comparables. But what is a Comparable? Well imagine if "Comparable" were nothing more than an alias for "int" (it's not, but imagine). Then you'd have this:

void SelectionSort(vector<int> & nums) 
{
    SelectionSort(nums, 0, nums.size()-1);
}

This is ordinary C++ code. It declares and defines a function that sorts a vector of ints. Pretty straightforward.

Comparable doesn't have a standard meaning like that. It is a term invented by the code in your question. It is declared by the text template <class Comparable>, approximately the way a variable is declared. It is something like a "type variable". An ordinary variable represents one of many values; a type variable represents one of many types.

template <class Comparable> void SelectionSort(vector<Comparable> & nums) 
{
    SelectionSort(nums, 0, nums.size()-1);
}

This code declares that Comparable is not automatically int, or float, or std::string, but rather may be any type at all. To use this function you must specify what type you want when you call the function. You can do it explicitly:

std::vector<int> someints;
SelectionSort<int>(someints);

(And this will make "Comparable" mean "int" after all, within that one call.)

Or you can leave out that extra specification and hope for the compiler to figure it out:

std::vector<int> someints;
SelectionSort(someints);

And you can use the same template for different types as much as you want; it is not "spent" in any sense by one use:

std::vector<int> someints, moreints;
std::vector<float> somefloats;
SelectionSort(someints);
SelectionSort(somefloats);
SelectionSort(moreints);

For a simple purpose like this, you can imagine that SelectionSort is a function that works on many types, not just one. But actually it is not a function. It is a whole family of potential functions, some of which may be instantiated by the compiler. The code just above calls SelectionSort three times, but with only two Comparable types, and so behind the scenes it creates two actual functions.

I've been talking about Comparable as a variable, but it can't vary WITHIN an instance of the template. You can't do Comparable=float within SelectionSort<int> or anything like that. It varies from one instance of the template to another, not within one instance. When the template is instantiated as a real function, Comparable is replaced by the type that was specified for it and then forgotten; that function doesn't "know" it is an instance of the template. It's just a function that happens to have angle brackets in its name. I think.

There are indeed some very powerful, complicated, mind-bending things that can be done with templates. But you probably don't need to know much about those for your purpose.

One more important basic point, though, is that there are also template classes. std::vector itself is one of them. They work in a roughly analogous way to template functions like SelectionSort: the header <vector> declares the vector template only once for all types, but then you can say std::vector<int> and then later std::vector<SomeClassIMade> and so on, and thereby automatically instantiate two (or more) actual classes. All these classes will work like a C++ vector is supposed to, but each one will only know how to handle its own specified element type, and will not understand any other.