Lesson 25:Template Specialization and Partial Template Specialization

Template Specialization

In many cases when working with templates, you'll write one generic version for all possible data types and leave it at that--every vector may be implemented in exactly the same way. The idea of template specialization is to override the default template implementation to handle a particular type in a different way.
For instance, while most vectors might be implemented as arrays of the given type, you might decide to save some memory and implement vectors of bools as a vector of integers with each bit corresponding to one entry in the vector. So you might have two separate vector classes. The first class would look like this.

template <typename T>
class vector
{
    // accessor functions and so forth
    private:
    T* vec_data;   // we'll store the data as block of dynamically allocated 
                   // memory
    int length;    // number of elements used 
    int vec_size;  // actual size of vec_data
};

But when it comes to bools, you might not really want to do this because most systems are going to use 16 or 32 bits for each boolean type even though all that's required is a single bit. So we might make our boolean vector look a little bit different by representing the data as an array of integers whose bits we manually manipulate. (For more on manipulating bits directly, see bitwise operators and bit manipulations in C and C++.)

To do this, we still need to specify that we're working with something akin to a template, but this time the list of template parameters will be empty:

template <>

and the class name is followed by the specialized type: class className<type>. In this case, the template would look like this:

template <>
class vector <bool>
{
    // interface

    private:
    unsigned int *vector_data;
    int length;
    int size;
};

Note that it would be perfectly reasonable if the specialized version of the vector class had a different interface (set of public methods) than the generic vector class--although they're both vector templates, they don't share any interface or any code.

It's worth pointing out that the salient reason for the specialization in this case was to allow for a more space-efficient implementation, but you could think of other reasons why this might come in handy--for instance, if you wanted to add extra methods to one templated class based on its type, but not to other templates. For instance, you might have a vector of doubles with a method that returns the non-integer component of each element although you might think prefer inheritance in this case. There isn't a particular reason to prevent the existence of a vector of doubles without those extra features. If, however, you felt strongly about the issue and wanted to prevent it, you could do so using template specialization.

Another time when you might want to specialize certain templates could be if you have a template type that relies on some behavior that was not implemented in a collection of classes you'd like to store in that template. For example, if you had a templated sortedVector type that required the > operator to be defined, and a set of classes written by someone else that didn't include any overloaded operators but did include a function for comparison, you might specialize your template to handle these classes separately.

Template Partial Specialization

Partial template specialization stems from similar motives as full specialization as described above. This time, however, instead of implementing a class for one specific type, you end up implementing a template that still allows some parameterization. That is, you write a template that specializes on one feature but still lets the class user choose other features as part of the template. Let's make this more concrete with an example.

Going back to the idea of extending the concept of vectors so that we can have a sortedVector, let's think about how this might look: we'll need a way of making comparisons. Fine; we can just use > if it's been implemented, or specialize if it hasn't. But now let's say that we wanted to have pointers to objects in our sorted vector. We could sort them by the value of the pointers, just doing a standard > comparison (we'll have a vector sorted from low to high):

template <typename T>
class sortedVector
{
    public:
    void insert (T val)
    {
        if ( length == vec_size )   // length is the number of elements
        {
            vec_size *= 2;    // we'll just ignore overflow possibility!
            vec_data = new T[vec_size];
        }
        ++length;  // we are about to add an element
        
   // we'll start at the end, sliding elements back until we find the
   // place to insert the new element
        int pos;
        for( pos = length; pos > 0 && val > vec_data[pos - 1]; --pos )
        {
            vec_data[pos] = vec_data[pos - 1];
        }
        vec_data[pos] = val;
    }
    // other functions...
    private:
    T *vec_data;
    int length;
    int size;
};

Now, notice that in the above for loop, we're making a direct comparison between elements of type T. That's OK for most things, but it would probably make more sense to have sorted on the actual object type instead of the pointer address. To do that, we'd need to write code that had this line:

for( pos = length; pos > 0 && *val > *vec_data[pos - 1]; --pos )

Of course, that would break for any non-pointer type. What we want to do here is use a partial specialization based on whether the type is a pointer or a non-pointer (you could get fancy and have multiple levels of pointers, but we'll stay simple).

To declare a partially specialized template that handles any pointer types, we'd add this class declaration:

template <typename T>
class sortedVector<T *>
{
    public:
    // same functions as before.  Now the insert function looks like this:
    insert( T *val )
    {
        if ( length == vec_size ) // length is the number of elements
        {
            vec_size *= 2;// we'll just ignore overflow possibility!
            vec_data = new T[vec_size];
        }
        ++length;  // we are about to add an element
        
  // we'll start at the end, sliding elements back until we find the

 // place to insert the new element
        int pos;
        for( pos = length; pos > 0 && *val > *vec_data[pos - 1]; --pos )
        {
            vec_data[pos] = vec_data[pos - 1];
        }
        vec_data[pos] = val;
    }

    private:
    T** vec_data;
    int length;
    int size;
};

There are a couple of syntax points to notice here. First, our template parameter list still names T as the parameter, but the declaration now has a T * after the name of the class; this tells the compiler to match a pointer of any type with this template instead of the more general template. The second thing to note is that T is now the type pointed to; it is not itself a pointer. For instance, when you declare a sortedVector<int *>, T will refer to the int type! This makes some sense if you think of it as a form of pattern matching where T matches the type if that type is followed by an asterisk. This does mean that you have to be a tad bit more careful in your implementation: note that vec_data is a T** because we need a dynamically sized array made up of pointers.

You might wonder if you really want your sortedVector type to work like this--after all, if you're putting them in an array of pointers, you'd expect them to be sorted by pointer type. But there's a practical reason for doing this: when you allocate memory for an array of objects, the default constructor must be called to construct each object. If no default constructor exists (for instance, if every object needs some data to be created), you're stuck needing a list of pointers to objects, but you probably want them to be sorted the same way the actual objects themselves would be!

Note, by the way, that you can also partially specialize on template arguments--for instance, if you had a fixedVector type that allowed the user of the class to specify both a type to store and the length of the vector (possibly to avoid the cost of dynamic memory allocations), it might look something like this:

template <typename T, unsigned length>
class fixedVector { ... };

Then you could partially specialize for booleans with the following syntax

template <unsigned length>
class fixedVector<bool, length> {...}

Note that since T is no longer a template parameter, it's left out of the template parameter list, leaving only length. Also note that length now shows up as part of fixedVector's name (unlike when you have a generic template declaration, where you specify nothing after the name). (By the way, don't be surprised to see a template parameter that's a non-type: it's perfectly valid, and sometimes useful, to have template arguments that are integer types such as unsigned.)

A final implementation detail comes up with partial specializations: how does the compiler pick which specialization to use if there are a combination of completely generic types, some partial specializations, and maybe even some full specializations? The general rule of thumb is that the compiler will pick the most specific template specialization--the most specific template specialization is the one whose template arguments would be accepted by the other template declarations, but which would not accept all possible arguments that other templates with the same name would accept.

For instance, if you decided that you wanted a sortedVector<int *> that sorted by memory location, you could create a full specialization of sortedVector and if you declared a sortedVector<int *>, then the compiler would pick that implementation over the less-specific partial specialization for pointers. It's the most specialized since only an int * matches the full specialization, not any other pointer type such as a double *, whereas int * certainly could be a parameter to either of the other templates.