Template Specialization Lab

In this lab, we will look at some examples of Template Specialization. The files are in ~cs253/pub/Labs/TempSpecLab.

A Bar Graph Template

In 1.cc, we have a program that defines the BarGraph template. Here’s how to use it:

        BarGraph<int> alpha;
        alpha += 12;
        alpha += 6;
        alpha += 4;
        alpha += 6;
        alpha.dump();

This create a BarGraph of integers, uses it to count four integers, and then produce this bar graph:

         4 *
         6 **
        12 *

This template has several features worth discussion:

It uses a std::map to count the elements as they come in. The key of the map is the templated type T, an int, in this case. The value of the map is an unsigned int. Why unsigned?
It creates an typedef alias called Con for the type of the map. That way, it's easy to use Con::iterator in the for loop.
It overloads += to “add” items to the bar graph. Note that the return type of operator+= is void. Isn’t += suppposed to return a reference to *this? Does it have to?
It uses a std::string temporary to print a number of stars. That is, string(23, '*') calls the string ctor to creates a temporary unnamed string that contains 23 asterisks.
It uses an iterator to traverse the sorted map.

Advantages of templates

The benefit of a template is its generality. BarGraph should work for any type, as long as it is (think “Duck Typing”):

assignable
comparable via <
printable via <<

including int, float, string, etc.

Disadvantages of templates

Sure, BarGraph works for lots of types, but it’s not the most efficient solution for all types. It uses a map, which is a general solution, but that generality is not always needed.

Consider 2.cc, which introduces template specialization. It features a hand-written version BarGraph<bool>. This is a version of BarGraph tuned specially for counting booleans. Of course, the general version of BarGraph still exists, so it works for all other types, too.

The specialization BarGraph<bool> is:

Smaller: only has two unsigned variables.
Faster: does a boolean test instead of a map lookup, and doesn’t have to iterate through the possible values, since there are only false and true.
Better: outputs false and true instead of 0 and 1.

(Of course, it’s certainly possible that g++’s implemention of map has a specialization for map<bool,whatever> that is smaller & faster in just that way. Who knows?)

Exercises

Instead of .dump(), overload << so that you can insert a BarGraph object into an ostream.
Create a specialization for BarGraph<char> that uses more efficient storage than a map. How can you portably determine the range of possible values for a char? (Try the numeric_limits class, provided by <limits>.)

For extra fame & glory:

Add an operator so that you can do graph += "foo" for a BarGraph<char>. This should be equivalent to:

        graph += 'f';
        graph += 'o';
        graph += 'o';

CS253: Problem Solving with C++