NOTE:

These are a little sketchy...I'll fill in details 'soon'.

What Came Before

After we'd been coding for a while, we noticed things like these in our code:

    cout << "Enter value one:  ";
    cin >> var1;
    cout << "Enter value two:  ";
    cin >> var2;
    cout << "Enter value three:  ";
    cin >> var3;

At first we said, "Aw, I can just copy/paste/edit and all will be fine." Then we saw things like this:

    cout << "Enter heights (negative to end):\n";
    i = 0;
    cin >> heights[i];
    while ((i+1) < MAX_HEIGHTS && heights[i] >= 0)
    {
        i++;
        cin >> heights[i];
    }
    used_heights = (heights[i] < 0 ? i : i+1);
    cout << "Enter weights (negative to end):\n";
    i = 0;
    cin >> weights[i];
    while ((i+1) < MAX_WEIGHTS && weights[i] >= 0)
    {
        i++;
        cin >> weights[i];
    }
    used_weights = (weights[i] < 0 ? i : i+1);

And we thought, that's a bit more complicated to adjust. Maybe I should use a function:

    void read_nonneg(double arr[], long MAX, long & used);

    // in some function...
    {
        cout << "Enter heights (negative to end):\n";
        read_nonneg(heights, MAX_HEIGHTS, used_heights);
        cout << "Enter weights (negative to end):\n";
        read_nonneg(weights, MAX_WEIGHTS, used_weights);
        // ...
    }

    void read_nonneg(double arr[], long MAX, long & used)
    {
        long i = 0;
        cin >> arr[i];
        while ((i+1) < MAX && arr[i] >= 0)
        {
            i++;
            cin >> arr[i];
        }
        used = (arr[i] < 0 ? i : i+1);
        return;
    }

Extracting the common data values into function arguments/parameters — be it for storage or mere access — proved much simpler in the long run.

Later we saw even weirder things like this:

    void swap(int & a, int & b)
    {
        int t = a;
        a = b;
        b = t;
        return;
    }
    void swap(short & a, short & b)
    {
        short t = a;
        a = b;
        b = t;
        return;
    }
    void swap(long & a, long & b)
    {
        long t = a;
        a = b;
        b = t;
        return;
    }
    void swap(float & a, float & b)
    {
        float t = a;
        a = b;
        b = t;
        return;
    }
    void swap(double & a, double & b)
    {
        double t = a;
        a = b;
        b = t;
        return;
    }
    void swap(char & a, char & b)
    {
        char t = a;
        a = b;
        b = t;
        return;
    }
    void swap(bool & a, bool & b)
    {
        bool t = a;
        a = b;
        b = t;
        return;
    }
    void swap(string & a, string & b)
    {
        string t = a;
        a = b;
        b = t;
        return;
    }

This isn't even as complicated as the first one, but it seems much more redundant — and it is already using functions!

Or how about this:

    cout << "Enter input file name:  ";
    cin.getline(fname, FNAME_MAX);
    file.open(fname);
    while (!file)
    {
        file.close();
        file.clear();
        cout << "Could not open '" << fname
             << "'...\a\n\nEnter input file name:  ";
        cin.getline(fname, FNAME_MAX);
        file.open(fname);
    }
    cout << "Enter output file name:  ";
    cin.getline(fname, FNAME_MAX);
    file2.open(fname);
    while (!file2)
    {
        file2.close();
        file2.clear();
        cout << "Could not open '" << fname
             << "'...\a\n\nEnter output file name:  ";
        cin.getline(fname, FNAME_MAX);
        file2.open(fname);
    }

And thought, "Hmm...first the values or variables changed between duplicated code. That we handled by making functions with arguments for the different values or variables. But now it isn't just values and variables — the variables' types are changing! How on earth can we handle that?!"

Well, lucky programmer, you are using C++! C++ supports generic programming via templates. With this powerful feature, you can write C++ code which is type-free and have the compiler fill in types as it generates the binary version of your program. Sound too good to be true? Follow along and see!

Making a template Function

Recognizing when to use a template is fairly simple (in general). Simply notice that you are repeating a lot of code and that you'd like to make it into a re-usable function. Then, when you can't because data types are different — even though the code itself is NO different — make the function anyway and change it to a template.

Let's practice with that swap function from above:

    void swap(int & a, int & b)
    {
        int t = a;
        a = b;
        b = t;
        return;
    }
    // ...etc...

All 7 of these functions are essentially the same. In fact, the code for swapping two values is never different. Note the code for swapping two Rational objects or two String objects:

    void swap(Rational & a, Rational & b)
    {
        Rational t = a;
        a = b;
        b = t;
        return;
    }
    void swap(String & a, String & b)
    {
        String t = a;
        a = b;
        b = t;
        return;
    }

Same thing! Only the types of a, b, and t have changed!

So, since we are performing the same code to variables/values which are merely differently typed, we know that we want to make a template, how do we do it? First we remove the offending type:

    void swap(_____ & a, _____ & b)
    {
        _____ t = a;
        a = b;
        b = t;
        return;
    }

Now we fill in the blank with a clearly identifying name. (Sure the five underscores would work, but it is a little tacky and confusing.) The book and many other authors use T, but we know this is a poor identifier in general. (Sure it is being used in a general function — look, we're using the generic names a, b, and t — but I'm trying to make a point that you can use proper, clear identifiers even for these template blanks!) I'll use SwapType since this is the type of information we'll be swap'ing:

    void swap(SwapType & a, SwapType & b)
    {
        SwapType t = a;
        a = b;
        b = t;
        return;
    }

But if the compiler saw that, it would complain saying, "What's this SwapType nonsense?! I've never heard of such a type!" (Or something to that effect...*grin*) So, we needed to make a way to identify the name of the new template function's blank to the compiler. Since this blank is to be filled in with a data type, we say:

    template <typename SwapType>
    void swap(SwapType & a, SwapType & b)
    {
        SwapType t = a;
        a = b;
        b = t;
        return;
    }

To indicate that the following function is covered by a template which uses the typename SwapType. Odd syntax, perhaps, but valid C++ code, nonetheless!

template Function Instantiation

Let's say that in our program we had some variables:

    short one, two;
    double three, four;
    Date five, six;
    String seven, eight;
    short nine, ten;
    char eleven[10], twelve[10];

And we wanted to swap them pairwise. We would obviously code:

    swap(one, two);
    swap(four, three);
    swap(five, six);
    swap(eight, seven);
    swap(nine, ten);
    swap(twelve, eleven);

(Note that it doesn't matter which is first or second in the list since the entire point of the function is to swap the values in those memory locations.)

Since the compiler only has only the one templated function swap, it will have to create binary versions — called instantiations — to place in the executable. To do that, it must validate the call — make sure that the function will work with the provided types. It will first make a checklist of all the things in the function that rely on the template type:

    template <typename SwapType>
    void swap(SwapType & a, SwapType & b)      // both arguments same
    {
        SwapType t = a;                                // copy construction
        a = b;                                         // operator=
        b = t;
        return;
    }

That done, it will then check each call against this list to verify that all is well:

    swap(one, two);               // both short
                                  // can copy construct short
                                  // can assign short

Since all is well here, it creates a binary version by filling in all the blanks in the template with short. It calls this binary version swap<short>. Now, when it looks for a swap function to call, it has this list:

  1. swap<short>

  2.     template <typename SwapType>
        void swap(SwapType & a, SwapType & b)
        {
            SwapType t = a;
            a = b;
            b = t;
            return;
        }            // both args same type, copy constr, op=
    

If it ever sees another call with short as the template candidate, it will immediately use that version — avoiding the checklist process.

Before we do the other three calls, though, note how we validated this template. The compiler had to go through the function's definition to build its checklist of type necessities. What does that mean? It means the compiler had to see the entire function definition before a call to the function could happen.

Hmm... Sounds familiar... Oh, yeah! inline functions were the same way, weren't they? To call an inline function, you had to have the entire definition first. Otherwise it just made a regular call.

But it is actually much worse for templates. If the compiler doesn't have the definition before the call — it won't allow the call at all.

So, what does all that mean? It means you cannot effectively prototype a template function. The compiler must see the entire definition before the call is allowed. Even then the compiler must validate the call by testing its checklist.

Okay. Now a couple of terms and we'll continue checking our swap template. The process of validating the checklist and creating the binary version is called instantiation of the template. The funny name of the binary version is called the instantiation/instantiated name. Okay...back to the example...

Next the compiler sees this call:

    swap(four, three);

Before running through the checklist, though, it now has a choice. It first looks to see if there is a prior instantiation. Finding only swap<short>, it must re-validate the template for double:

    swap(four, three);      // both double
                            // can copy construct double
                            // can assign double

And thus swap<double> is generated and added to the list of swap functions available:

  1. swap<short>

  2. swap<double>

  3.     template <typename SwapType>
        void swap(SwapType & a, SwapType & b)
        {
            SwapType t = a;
            a = b;
            b = t;
            return;
        }            // both args same type, copy constr, op=
    

Next it sees the call:

    swap(five, six);

Seeing no pre-instantiated possibility with a Date type, it must validate the template for Date:

    swap(five, six);      // both Date
                          // can copy construct Date
                          // can assign Date

(Note how we don't even wonder if the programmer who created this Date class properly overloaded operator= or created a copy constructor — we know that the compiler would create both for us were there only non-dynamic members involved in the class and that the programmer would be an idiot to have written a class with dynamic members and not done these things!)

All being well, we create swap<Date> and add it to the list of swap functions available. Next up is:

    swap(eight, seven);

We look through the list for a String version of swap. Seeing none, we proceed to our checklist:

    swap(eight, seven);      // both String
                             // can copy construct String (dynamic memory)
                             // can assign String (dynamic memory)

An thus swap<String> is born and placed in our pool of swaps.

Next we see:

    swap(nine, ten);

This one is pretty easy as we simply find swap<short> in our list and use it! No validation needed since it was done already!

Let's pause again and look at what's been happening. How many swap functions does the compiler have now? Five, right: one blank and four binary instantiations. How many versions of swap are in the executable? Four: the four instantiations. Now for the kicker: How many swap functions did we write? One: the template. That's pretty sweet. We write it once and it is re-used five times (twice for short, remember)! That's pretty powerful!

But, all is not well in the land of templates. Let's try that last call:

    swap(twelve, eleven);

Here we have the candidate type char[10]. Validating:

    same type?           yes
    can copy construct?  NO
    can assign?          NO

Oops...um...I know! Let's try the pointer version of the candidate type: char * const.

    same type?           yes
    can copy construct?  yes
    can assign?          NO

Well, we made it farther, but we still didn't finish. Wasn't there another bit about passing constant pointers to functions? Something about dropping the constness of the pointer since pointers are pass-by-value anyway?

Yes, there was such a concept. However, our swap template is taking in its parameters by reference — not by value. Therefore, it doesn't actually help us to re-consider it as char *. We'll get an error in initialization of the references.

So, the compiler fails on this call and we have to re-think our plan. (See below...)

Arrays vs. Subscript-able Objects

Let's try template'ing a function with array parameters and see if it gives us any ideas of how to fix our swap. A good, simple candidate is linear search:

    long linsearch(const double arr[], const long MAX, double find_me)
    {
        long i = 0;
        while (i < MAX && arr[i] != find_me)
        {
            i++;
        }
        return (i >= MAX ? -1 : i);
    }

The most obvious way to template this is:

    template <typename ArrType>
    long linsearch(const ArrType arr[], const long MAX, ArrType find_me)
    {
        long i = 0;
        while (i < MAX && arr[i] != find_me)
        {
            i++;
        }
        return (i >= MAX ? -1 : i);
    }

It looks a little odd since find_me isn't really an array, but it'll do. Let's test it out:

    long a[15], f1;
    bool b[5], f2;
    Rational c[30], f3;
    String d[52], f4;
    String e;
    char f5;

Here we have several arrays to look through and as well as variables holding the things we want to find. Calls we want to test are:

    linsearch(a, 15, f1);
    linsearch(b, 5, f2);
    linsearch(c, 30, f3);
    linsearch(d, 52, f4);
    linsearch(e, e.size(), f5);

The compiler's checklist for linsearch is something like:

Checking these against the calls we see:

    1st arg        3rd arg     match?   copy       op!= ?    instantiation
                                        constr?
   ---------------------------------------------------------------------------------
     long[15]        long       yes      yes        yes      linsearch<long>
     bool[5]         bool       yes      yes        yes      linsearch<bool>
     Rational[30]    Rational   yes      yes        yes      linsearch<Rational>
     String[52]      String     yes      yes        yes      linsearch<String>
     String          char       NO       N/A        N/A      N/A

What's the problem here? Everybody else worked! Why can't we search through a String for a character? It really should work, shouldn't it?

The problem seems to start with the fact that a String is an object of a class type and its elements are of the built-in type char. All our other arrays were simple C-style arrays. This array has been encapsulated inside an object. So, to alter that, we need to remove the [ ] from the argument list:

    template <typename ArrType>
    long linsearch(const ArrType arr, const long MAX, ArrType find_me)
    // ...

Next we note that, again, the array is of String and its elements are of char. So, we need a second template blank for the elements — separate from the array! We do this by using a comma-separated list in the template's typename declaration area:

    template <typename ArrType, typename ElemType>
    long linsearch(const ArrType arr, const long MAX, ElemType find_me)
    // ...

Of course, this has drastically altered our checklist:

Weird! We now not only have two template types, we have an indirect template typename: the result of the subscript on the first argument.

Rechecking our list for the String:

    1st arg        3rd arg     copy       op[] ?    op!= ?    instantiation
                               constr?    (result)
   --------------------------------------------------------------------------------
     String          char       y/y        yes       yes      linsearch<String,char>
                                           (char)

Finally! But, let's recheck the others — at the very least the instantiation name must change since there's an extra template type now:

    1st arg        3rd arg     copy       op[] ?    op!= ?    instantiation
                               constr?    (result)
   --------------------------------------------------------------------------------
     String          char       y/y        yes       yes      linsearch<String,char>
                                           (char)
     long[15]        long       NO         N/A       N/A
     bool[5]         bool       NO         N/A       N/A
     Rational[30]    Rational   NO         N/A       N/A
     String[52]      String     NO         N/A       N/A

Oo! Oo! The pointer thing! Once again:

    1st arg     3rd arg     copy       op[] ?      op!= ?    instantiation
                            constr?    (result)
   -----------------------------------------------------------------------------------------
     String       char       y/y        yes         yes      linsearch<String,char>
                                        (char)
     long*        long       y/y        yes         yes      linsearch<long*,long>
                                        (long)
     bool*        bool       y/y        yes         yes      linsearch<bool*,bool>
                                        (bool)
     Rational*    Rational   y/y        yes         yes      linsearch<Rational*,Rational>
                                        (Rational)
     String*      String     y/y        yes         yes      linsearch<String*,String>
                                        (String)

Cool! (But why is it just * instead of *const? Recall that most of the time the compiler will discard the constness of a pointer for argument types. Not the constness of elements, but of the pointer itself. It couldn't before — in our swap — because of the presence of the reference on the arguments. If your compiler does, it needs some serious help! Call a counselor now...)

Minimizing Template Type Requirements

avoid copy construction of templated parameters using const&

array & position vs. pointer/iterator

revisiting binary search

another look at comparison

revisiting linear search

Also See...

Examples from lecture...