C++ track: lab 6: Templates

When you wrote your sparse matrix class for lab 5, your underlying data representation was, in one way or another, a linked list of SparseVectors.

It is often the case in programming that we find ourselves needing to rewrite code we wrote some days, weeks or months before to do something slightly different. Some of you may have implemented your outer linked list internally in SparseMatrix, and others of you have may have made a second version of SparseVector that stored "SparseVector *"s instead of ints.

Either way, you likely found yourself reusing or rewriting a good part of the functionality of your original SparseVector. This kind of situation is just one of many good candidates for templating.

Consider the following pseudo-C++-code for a class Array that acts like an array of integers:

// This would go into a header file such as "Array.h".

class Array
{
public:
    Array(int len=10)                  
      : len_(len), data_(new int[len])  { }
    ~Array()                            { delete [] data_; }
    int len() const                     { return len_;     }
    int& operator[](int i) const        { return data_[check(i)]; }
    Array(const Array&);
    Array& operator= (const Array&);

private:
    int  len_;
    int* data_;
    int  check(int i) const
    { 
        if ((i < 0) || (i >= len_))
        { 
            throw std::string("Out of bounds exception!"); 
        }

        return i; 
    }
}; 

Time out: Explain that code

Okay, there are some things that should be brought to your attention about the above code first:

1. Almost all of the code is in the header file! Except for the copy constructor and the overloaded assignment operator, all the class methods are defined directly in the header file. These are all examples of inlined code. In general, you can "inline" functions or methods that are "short and sweet," where that definition is up to the particular compiler you choose. The compiler is free to ignore you and not inline functions you've declared as inline, but it will generally inline them unless the function is really large (in which case you shouldn't be inlining it anyway).

2. Notice that the one-argument constructor has a funny signature:

       Array(int len=10)
   

   This is an example of a defaulted argument. If the user of the class doesn't specify the argument in their constructor call, the value 10 is assumed.

   This constructor also uses the inline assignment technique we saw earlier, in which the statements after the colon apply the values inside the parentheses to the instance variables outside and before the parentheses.

3. There is an operator overload of the bracket-pair operator here. If it's not clear, that means code like this:

       Array t();
       t[5] = 2;
       cout << t[1];
   

   makes two calls to that operator. The value inside the brackets is, of course, the argument to the method. The compiler translates those lines into something like this:

     t.operator[](5).operator=(2);
     cout << t.operator[](1);
   

4. This class's private method check() throws an exception. In this case, the type of the object it throws is a std::string, which is an instance of the string class provided by the standard library, in the std namespace. (Whew!)

   Exceptions provide another mechanism for dealing with runtime errors. We'll talk in class about how to "catch" one of these thrown exceptions. For this example, all you need to understand is that check() throws an exception if the index is out of bounds.

Okay, on with templates.

What if we wanted to make the Array class implement an array of floats? Or doubles? Or char *s? Or Array-of-ints?

The templated version:

// This would go into a header file such as "Array.h".

template<typename T>
class Array 
{
public:
    Array(int len=10)                : len_(len), data_(new T[len]) { }
   ~Array()                          { delete [] data_; }
    int len() const                  { return len_;     }
    T& operator[](int i) const       { return data_[check(i)]; }
    Array(const Array<T>&);
    Array<T>& operator= (const Array<T>&);

private:
    int len_;
    T*  data_;
    int check(int i) const
    { 
        if ((i < 0) || (i >= len_))
        {
            throw std::string("Out of bounds exception!");
        }

        return i; 
    }
}; 

To create Arrays of various types, instantiate like this:

  Array<int> intArray(100);
  Array<float> floatArray(50);
  Array<char *> aC();
  Array< Array<int> > wowzers();

Note the last one, an array of arrays of ints, requires a space between the two closing >'s. Otherwise, the compiler interprets it as a >> operator.

More Notes

To define methods of templated classes outside of the class block, prepend the template specification in front of each method signature like so:

template <typename T>
returnType someClass<T>::whateverMethod(..) 
{
    // code goes here
}

Constructors and destructors do not take on the template parameter in their name, so you'd write someClass's constructor like this:

template <typename T>
someClass<T>::someClass(..) { .... }

as opposed to:

// WRONG!
template <typename T>
someClass<T>::someClass<T>(..) { .... }

Compiling templates

Compiling templates is "special", because templates are not classes! They are blueprints for classes in a similar relationship to the way classes are blueprints for actual objects. We'll talk more about how to get them to compile in class, but the bottom line is that the easiest way is to put all the code inside the header file.

Program to write

1. Modify your SparseVector class such that it is templated on the type of the data element.

   It should then be possible to create a SparseVector of any numeric type. Use whatever code you tested your class with in lab 4 to re-test, keeping in mind that you'll have to change each mention of SparseVector to one of SparseVector<int>.

2. Template your SparseMatrix class on a data type such that the user can create a SparseMatrix of any numeric type. i.e.,

     SparseMatrix<int> a(50,50);
     SparseMatrix<float> b(100000,100000);
   

   Continue to return a 0 if an element is not in the underlying data representation, even if that value does not necessarily make sense in the context of certain data types.

3. Compile and test against this new checksparsematrix.cc to make sure everything still works.

4. Replace any asserts or other error-handling code in SparseMatrix with thrown exceptions. You may throw any data type you like, but std::strings are probably easiest.

Convince yourself that your exceptions work by writing a small test routine, lab6.cc, which generates some exceptions via poor code. Try catching the exceptions and not catching them.