Abstract

For the past century, the OOP (Object Oriented Programming) paradigm has been touted as the software technique for code reusability, extensibility, yada yada.. While this is true in most cases, there are situations where OOP is not appropriately suited. There is a new contender - Generic Programming and templates. Welcome to a whole new concept in C++ - getting the compiler to generate code automatically.

Gentle intro

We start by diving straight into code - no dilly dallies. In C++, you declared a generic class/function using the template keyword.

    template <typename T>
       class Foo
    {
        T t_;
     public:

        Foo( T t ) : t_(t)  {}

        void Print_Value()
        {
          cout << t_ << "\n";
        }
    };

    template <typename T>
      void Print_Size( T t )
    {
       cout << "Size is " << sizeof(t) << "\n";
    }

The above declares a generic class and function which takes a generic parameter. To use it, you need to instantiate the class by specifying the generic parameter like so.

    template <typename T>
       class Foo
    {
       T t_;
     public:

       Foo( T t ) : t_(t)  {}

       void Print_Value()
       {
         cout << t_ << "\n";
       }
    };

    template <typename T>
      void Print_Size( T t )
    {
       cout << "Size is " << sizeof(t) << "\n";
    }

    #include 
    using namespace std;

    int main()
    {
       int    i = 6;
       float  f = 7;
       double d = 8;

       Foo<int>    foo_int( i );
       Foo<float>  foo_float( f );
       Foo<double> foo_double( d );

       foo_int.Print_Value();
       foo_float.Print_Value();
       foo_double.Print_Value();

       Print_Size( i );
       Print_Size( f );
       Print_Size( d );

       return 0;
    }

All the above instances are different. The compiler creates a new class/function type when you use a different parameter. This means now in your code, it would be like you had just written.

    class Foo_Int
    {
      int i_;
    public:
       Foo_Int( int i ) : i_(i) {}
       void Print_Value() { cout << i_ << "\n"; }
    };

    class Foo_Float
    {
      float f_;
    public:
       Foo_Float( float f ) : f_(f) {}
       void Print_Value() { cout << f_ << "\n"; }
    };

    class Foo_Double
    {
      double d_;
    public:
       Foo_Double( double d ) : d_(d) {}
       void Print_Value() { cout << d_ << "\n"; }
    };

    void Print_Size( int i )   { cout << sizeof(int)    << "\n"; }
    void Print_Size( float f ) { cout << sizeof(float)  << "\n"; }
    void Print_Size( double d ){ cout << sizeof(double) << "\n"; }

This doesn't look terribly useful right now, so let's move on to the next section and see some practical use for templates.

Note: You need a compiler that is compliant with the C++ standard to do generic programming successfully. Common compilers like Microsoft VC++ 6.0, VSNet are still not there. I recommend using Comeau or GCC.

Better than Macros

If you haven't heard how evil macros can be, then you probably haven't been programming long enough. Anyway, we look at this very common macro for calculating the square.

    #define SQR(x) ((x) * (x))

Now try using it like so

    #include 
    using namespace std;

    #define SQR(x) ((x) * (x))

    int main()
    {
       int x = 2;

       cout  << SQR( ++x ) << "\n"; // prints 16 instead of 9. DOH!

       return 0;
    }

A better(?) solution would be using templates

    #include 
    using namespace std;

    template <typename T>
        T SQR( T t )
    {
        return t * t;
    }

    int main()
    {
       int x = 2;

       cout  << SQR( ++x ) << "\n"; // correctly prints 9

       return 0;
    }

By using templates, the function is type safe and insidious bugs like this are squashed into oblivion.

Reusability

Let's look at the implementation of a classic data structure - the link list. The usual way in C to do a reuse a link list involves the error prone methods of copy, paste, and modify. Let's see we can design a reusable link list class using OOP.

    // Base class for link list element
    class NodeBase
    {
       friend class LinkList;
       NodeBase *next_;
    public:
       NodeBase() : next_(0)   {}
       virtual ~NodeBase() = 0 {}
    };

    // Link list container
    class LinkList
    {
       NodeBase *head_;
       NodeBase *tail_;
    public:

       LinkList() : head_(0), tail_(0) {}

       ~LinkList()
       {
          while( 0 != head_ )
          {
             NodeBase *temp = head_;
             head_ = head_->next_;
             delete temp;
          }
          head_ = 0;
          tail_ = 0;
       }

       // Appends an element to the list
       void Append( NodeBase *item )
       {
          if ( 0 == head_ )
          {
             head_ = item;
             tail_ = item;
          }
          else
          {
             tail_->next_ = item;
             tail_ = item;
          }
       }

       // Link list traversal methods
       NodeBase* Get_Head() const { return head_; }
       NodeBase* Get_Next( const NodeBase * const element ) const
       {
          return element->next_;
       }
    };

We design a link list container class which holds a pointer to the abstract node item object. Elements in the link container derive publicly from this base class. For this example, there is a member function for appending an item to the list. An example of the link list container in action is

    // Note: Link list container class omitted for beverity

    #include 
    using namespace std;

    // Link list element, notice the inheritance
    class Foo : public NodeBase
    {
       int i_;
    public:
       explicit Foo( int i ) : NodeBase(), i_(i)  {}

       friend ostream& operator<<( ostream &os, const Foo &f  )
       {
          return os << f.i_;
       }
    };

    int main()
    {
       LinkList link_list;

       // add elements to link list
       link_list.Append( new Foo(2) );
       link_list.Append( new Foo(3) );
       link_list.Append( new Foo(4) );

       NodeBase *temp = link_list.Get_Head();

       // prints elements in list
       while ( 0 != temp )
       {
          Foo *f = dynamic_cast( temp );

          cout << *f << " ";  // prints 2,3,4

          temp = link_list.Get_Next( temp );
       }

       return 0;
    }

So now we have a reusable link list container. But is it really reusable as we think? Let's analyze its problems.

• Downcast required to access list element

  When we access the link list element, we need to use dymanic_cast to convert the base pointer downwards. The problem is dynamic_cast may be slow. The compiler needs to search through the base inheritance graph to check validity of the downcast at runtime. It is highly impossible to get constant time downcast, especially with multiple inheritance graphs. Performance may be badly affected.

  The second issue is we are violating the LSP (Liskov Substitutability Principle). In simple terms, the LSP states that when we use base classes interfaces, we shouldn't need to know about the derived class. By using RTTI (runtime type information) downcasting, the OO design is flawed. The downcast can fail, and we need to inject additional checks (not done here) to make the program robust.

• Elements required to derive from a base

  As elements derive from a common base, we can insert any elements into any link list. Say we have another element class Bar, we can insert that into a Foo linked list. When elements shouldn't be mixed in the same list, the compiler has no way of detecting that. It is up to the programmer's vigilance to ensure that kind of bugs doesn't happen.

Of note, this design is similar to Java Object base class for its standard containers. While this is a design flaw in Java or not, we cannot argue because there is no other alternatives. In other languages where type info is less strict, the design may be considered acceptable. But in C++ strict static type model, we cannot depend on it.

Is it impossible to build a reusable link list class? Are we dooomed to suffer the cut, paste, modify syndrome in C++? Before generic programming, maybe, but here comes templates to the rescue!

    template <typename T>
       class LinkList;   // forward declaration

    // Generic class for link list element, no inheritance necessary
    template <typename T>
       class NodeBase
    {
       friend class LinkList;
       NodeBase *next_;

       T t_; // generic list element stored here
    public:
       NodeBase() : next_(0), t_() {}
       NodeBase( const T &t ) : next_(0), t_(t) {}

       // access generic element
       T& Get_Element() { return t_; }
    };

    // Link list container
    template <typename T>
       class LinkList
    {
       typedef NodeBase NodeBase;

       NodeBase *head_;
       NodeBase *tail_;
    public:

       LinkList() : head_(0), tail_(0) {}

       ~LinkList()
       {
          while( 0 != head_ )
          {
             NodeBase *temp = head_;
             head_ = head_->next_;
             delete temp;
          }
          head_ = 0;
          tail_ = 0;
       }

       // Appends an element to the list
       void Append( const T &t )
       {
          NodeBase *item = new NodeBase(t);

          if ( 0 == head_ )
          {
             head_ = item;
             tail_ = item;
          }
          else
          {
             tail_->next_ = item;
             tail_ = item;
          }
       }

       // Link list traversal methods
       NodeBase* Get_Head() const { return head_; }
       NodeBase* Get_Next( const NodeBase * const element ) const
       {
          return element->next_;
       }
    };

    #include 
    using namespace std;

    // No need to derive from base class
    class Foo
    {
       int i_;
    public:
       explicit Foo( int i ) : i_(i)  {}

       friend ostream& operator<<( ostream &os, const Foo &f  )
       {
          return os << f.i_;
       }
    };

    int main()
    {
       LinkList link_list;

       link_list.Append( Foo(2) );
       link_list.Append( Foo(3) );
       link_list.Append( Foo(4) );

       NodeBase *temp = link_list.Get_Head();

       // No downcast necessary
       while ( 0 != temp )
       {
          cout << temp->Get_Element() << " ";

          temp = link_list.Get_Next( temp );
       }

       return 0;
    }

We changed the Nodebase class to a generic list element class that stores a copy of the list element. List elements no longer need to derive from this base class. By removing the inheritance, we no longer need to downcast. Also, you cannot mix different types in the link list because templates are type safe. We have a reuseable linked list without sacrificing speed or type safety.

Before you run off and write your own templated link list class, take a look at the C++ Standard Template Library (STL). It contains reusable container classes like linked lists, trees, and many others. However, there are times when you need to write your own reusable container, and that brings us to the next level of generic programming.

Policy based Design

This section shows the real power of generic programming. In OOP, reusability is achieved using polymorphism. As seen above, generic programming reuses code at compile time. By resolving at compile time, there is no runtime performance penalty and the class is still type safe.

Policy based design brings this concept to another level. Instead of just designing our templates for generic types, we design them for generic behaviour. This means we can customize the behaviour of the class at compile time. Some examples of customization are multi/single threaded behaviour, level of error checking performed, memory allocation used etc. All these class design issues are resolved at compile time and done with a reusable generic class.

This sounds scary and almost like a fairy tale, but it is proven in "Modern C++ Design" by Andrei Alexandrascu's. The book shows policy based designs in it's full raw power. Here I show a gentle example.

We design four generic functions which correspond to addition, substraction, multiplication and division operations.

    // generic calculation components
    template <typename T>
       struct Add
    {
       static T Calculate( T t1, T t2 ) { return t1 + t2; }
    };

    template <typename T>
       struct Subtract
    {
       static T Calculate( T t1, T t2 ) { return t1 - t2; }
    };

    template <typename T>
       struct Multiply
    {
       static T Calculate( T t1, T t2 ) { return t1 * t2; }
    };

    template <typename T>
       struct Divide
    {
       static T Calculate( T t1, T t2 ) { return t1 / t2; }
    };

We declare them as a static member function instead of a free function as this is required later. Notice the static member function names are the same. We declare a generic operation class like so

    // A Generic operation performed on 4 inputs
    template <  typename T,
             template <typename> class Op1,
             template <typename> class Op2,
             template <typename> class Op3 >
       class Operation
    {
    public:
       // perform a calcuation on the inputs
       static T Calculate( T t1, T t2, T t3, T t4 )
       {
          T temp1 = Op1::Calculate( t1, t2 );

          T temp2 = Op2::Calculate( temp1, t3 );

          return Op3::Calculate( temp2, t4 );
       }
    };

We used a feature known as template template parameters. The double template word is not a typo.

In addition to taking a generic variable, this operation class takes in generic classes as well. The Calculate method performs a calculation using the 3 supplied generic classes on the 3 inputs. We can have an unlimited different Operation class by mixing the generic classes. An usage example is as shown.

    // Note: Generic calculation/operation classes omitted for beverity

    #include 
    using namespace std;

    int main()
    {
       // 1 + 3 - 2 * 4
       cout << Operation<int, Add, Subtract, Multiply>::Calculate(1,3,2,4) << "\n";

       // (0.5 * 2 + 3) / 0.3
       cout << Operation<double, Multiply, Add, Divide>::Calculate(0.5,2,3,0.3) << "\n";

       // 0.7 * 2 + 0.8 * 2
       cout << Operation<float, Multiply, Add, Multiply>::Calculate(0.7,2,0.8,2) << "\n";

       // 1 + 2 + 3 + 4
       cout << Operation<int, Add, Add, Add>::Calculate(1,2,3,4) << "\n";

       return 0;
    }

Notice how we can achieve different calculations operations with 1 generic Operation class. By using other complex calculations other than basic add/subtract/multiply/divide, we can have an unlimited number of calculation operations. The class has become truly extensible.

Conclusion

You may be wondering if all these template stuff is practical or just fancy programming.

Generic containers like STL have proven to be reusable and fast, unlike OOP implementations.

Policy based design brings reusability one step furthur. Some things you can do with policy based design is to provide the class with a choice of memory allocation type, threading model, operation types. All of these without sacrificing speed or type safety.

In summary, generic programming achieves what OOP cannot do in resuability. If not for complier limitations, generic programming would be more popular. Generic programming cannot replace OOP or vice versa. They complement each other and should be used whenever appropriate.

Using OOP only is like using only a screwdriver to do all your construction - it works but you get screwed eventually..

References

Here are some recommended stuff to keep in touch with generic programming and STL

• Effective C++/More Effective C++/Effective STL by Scott Meyers
• The C++ Standard Library: A Tutorial and Reference by Nicolai M. Josuttis
• Exceptional C++ and More Exceptional C++ by Herb Stutter
• The Boost library at http://www.boost.org
• Modern C++ Design: Generic Programming and Design Patterns Applied by Andrei Alexandrescu