Jump to content

  • Log In with Google      Sign In   
  • Create Account

Like
0Likes
Dislike

OPPs, Move Aside, OOPs

By Sobeit Void | Published Mar 03 2004 10:36 AM in General Programming

code c++ yada generic new oop compiler generate getting
If you find this article contains errors or problems rendering it unreadable (missing images or files, mangled code, improper text formatting, etc) please contact the editor so corrections can be made. Thank you for helping us improve this resource



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.



    <span class="codekeyword">template</span> <<span class="codekeyword">typename</span> T>

       <span class="codekeyword">class</span> Foo

    {

        T t_;

     <span class="codekeyword">public</span>:



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



        <span class="codekeyword">void</span> Print_Value()

        {

          cout << t_ << "\n";

        }

    };



    <span class="codekeyword">template</span> <<span class="codekeyword">typename</span> T>

      <span class="codekeyword">void</span> Print_Size( T t )

    {

       cout << "Size is " << <span class="codekeyword">sizeof</span>(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.



    <span class="codekeyword">template</span> <<span class="codekeyword">typename</span> T>

       <span class="codekeyword">class</span> Foo

    {

       T t_;

     <span class="codekeyword">public</span>:



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



       <span class="codekeyword">void</span> Print_Value()

       {

         cout << t_ << "\n";

       }

    };



    <span class="codekeyword">template</span> <<span class="codekeyword">typename</span> T>

      <span class="codekeyword">void</span> Print_Size( T t )

    {

       cout << "Size is " << <span class="codekeyword">sizeof</span>(t) << "\n";

    }



    <span class="codekeyword">#include</span> <iostream>

    <span class="codekeyword">using namespace</span> std;



    <span class="codekeyword">int</span> main()

    {

       <span class="codekeyword">int</span>    i = 6;

       <span class="codekeyword">float</span>  f = 7;

       <span class="codekeyword">double</span> d = 8;



       Foo<<span class="codekeyword">int</span>>    foo_int( i );

       Foo<<span class="codekeyword">float</span>>  foo_float( f );

       Foo<<span class="codekeyword">double</span>> foo_double( d );



       foo_int.Print_Value();

       foo_float.Print_Value();

       foo_double.Print_Value();



       Print_Size( i );

       Print_Size( f );

       Print_Size( d );



       <span class="codekeyword">return</span> 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.



    <span class="codekeyword">class</span> Foo_Int

    {

      <span class="codekeyword">int</span> i_;

    <span class="codekeyword">public</span>:

       Foo_Int( <span class="codekeyword">int</span> i ) : i_(i) {}

       <span class="codekeyword">void</span> Print_Value() { cout << i_ << "\n"; }

    };



    <span class="codekeyword">class</span> Foo_Float

    {

      <span class="codekeyword">float</span> f_;

    <span class="codekeyword">public</span>:

       Foo_Float( <span class="codekeyword">float</span> f ) : f_(f) {}

       <span class="codekeyword">void</span> Print_Value() { cout << f_ << "\n"; }

    };



    <span class="codekeyword">class</span> Foo_Double

    {

      <span class="codekeyword">double</span> d_;

    <span class="codekeyword">public</span>:

       Foo_Double( <span class="codekeyword">double</span> d ) : d_(d) {}

       <span class="codekeyword">void</span> Print_Value() { cout << d_ << "\n"; }

    };



    <span class="codekeyword">void</span> Print_Size( <span class="codekeyword">int</span> i )   { cout << <span class="codekeyword">sizeof</span>(<span class=

"codekeyword">int</span>)    << "\n"; }

    <span class="codekeyword">void</span> Print_Size( <span class="codekeyword">float</span> f ) { cout << <span class="codekeyword">sizeof</span>(<span class=

"codekeyword">float</span>)  << "\n"; }

    <span class="codekeyword">void</span> Print_Size( <span class="codekeyword">double</span> d ){ cout << <span class="codekeyword">sizeof</span>(<span class=

"codekeyword">double</span>) << "\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.



    <span class="codekeyword">#define</span> SQR(x) ((x) * (x))


Now try using it like so



    <span class="codekeyword">#include</span> <iostream>

    <span class="codekeyword">using namespace</span> std;



    <span class="codekeyword">#define</span> SQR(x) ((x) * (x))



    <span class="codekeyword">int</span> main()

    {

       <span class="codekeyword">int</span> x = 2;



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



       <span class="codekeyword">return</span> 0;

    }


A better(?) solution would be using templates



    <span class="codekeyword">#include</span> <iostream>

    <span class="codekeyword">using namespace</span> std;



    <span class="codekeyword">template</span> <<span class="codekeyword">typename</span> T>

        T SQR( T t )

    {

        <span class="codekeyword">return</span> t * t;

    }



    <span class="codekeyword">int</span> main()

    {

       <span class="codekeyword">int</span> x = 2;



       cout  << SQR( ++x ) << "\n"; <span class="codecomment">// correctly prints 9</span>



       <span class="codekeyword">return</span> 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.



    <span class="codecomment">// Base class for link list element</span>

    <span class="codekeyword">class</span> NodeBase

    {

       <span class="codekeyword">friend class</span> LinkList;

       NodeBase *next_;

    <span class="codekeyword">public</span>:

       NodeBase() : next_(0)   {}

       <span class="codekeyword">virtual</span> ~NodeBase() = 0 {}

    };



    <span class="codecomment">// Link list container</span>

    <span class="codekeyword">class</span> LinkList

    {

       NodeBase *head_;

       NodeBase *tail_;

    <span class="codekeyword">public</span>:



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



       ~LinkList()

       {

          <span class="codekeyword">while</span>( 0 != head_ )

          {

             NodeBase *temp = head_;

             head_ = head_->next_;

             <span class="codekeyword">delete</span> temp;

          }

          head_ = 0;

          tail_ = 0;

       }



       <span class="codecomment">// Appends an element to the list</span>

       <span class="codekeyword">void</span> Append( NodeBase *item )

       {

          <span class="codekeyword">if</span> ( 0 == head_ )

          {

             head_ = item;

             tail_ = item;

          }

          <span class="codekeyword">else</span>

          {

             tail_->next_ = item;

             tail_ = item;

          }

       }



       <span class="codecomment">// Link list traversal methods</span>

       NodeBase* Get_Head() <span class="codekeyword">const</span> { <span class="codekeyword">return</span> head_; }

       NodeBase* Get_Next( <span class="codekeyword">const</span> NodeBase * <span class="codekeyword">const</span> element ) <span class="codekeyword">const</span>

       {

          <span class="codekeyword">return</span> 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



    <span class="codecomment">// Note: Link list container class omitted for beverity</span>



    <span class="codekeyword">#include</span> <iostream>

    <span class="codekeyword">using namespace</span> std;



    <span class="codecomment">// Link list element, notice the inheritance</span>

    <span class="codekeyword">class</span> Foo : <span class="codekeyword">public</span> NodeBase

    {

       <span class="codekeyword">int</span> i_;

    <span class="codekeyword">public</span>:

       <span class="codekeyword">explicit</span> Foo( <span class="codekeyword">int</span> i ) : NodeBase(), i_(i)  {}



       <span class="codekeyword">friend</span> ostream& <span class="codekeyword">operator</span><<( ostream &os, <span class="codekeyword">const</span> Foo &f  )

       {

          <span class="codekeyword">return</span> os << f.i_;

       }

    };



    <span class="codekeyword">int</span> main()

    {

       LinkList link_list;



       <span class="codecomment">// add elements to link list</span>

       link_list.Append( <span class="codekeyword">new</span> Foo(2) );

       link_list.Append( <span class="codekeyword">new</span> Foo(3) );

       link_list.Append( <span class="codekeyword">new</span> Foo(4) );



       NodeBase *temp = link_list.Get_Head();



       <span class="codecomment">// prints elements in list</span>

       <span class="codekeyword">while</span> ( 0 != temp )

       {

          Foo *f = <span class="codekeyword">dynamic_cast</span><Foo*>( temp );



          cout << *f << " ";  <span class="codecomment">// prints 2,3,4</span>



          temp = link_list.Get_Next( temp );

       }



       <span class="codekeyword">return</span> 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 beslow. 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 multipleinheritance 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 thederived 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 programrobust.

  • 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'thappen.

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!



    <span class="codekeyword">template</span> <<span class="codekeyword">typename</span> T>

       <span class="codekeyword">class</span> LinkList;   <span class="codecomment">// forward declaration</span>



    <span class="codecomment">// Generic class for link list element, no inheritance necessary</span>

    <span class="codekeyword">template</span> <<span class="codekeyword">typename</span> T>

       <span class="codekeyword">class</span> NodeBase

    {

       <span class="codekeyword">friend class</span> LinkList<T>;

       NodeBase *next_;



       T t_; <span class="codecomment">// generic list element stored here</span>

    <span class="codekeyword">public</span>:

       NodeBase() : next_(0), t_() {}

       NodeBase( <span class="codekeyword">const</span> T &t ) : next_(0), t_(t) {}



       <span class="codecomment">// access generic element</span>

       T& Get_Element() { <span class="codekeyword">return</span> t_; }

    };



    <span class="codecomment">// Link list container</span>

    <span class="codekeyword">template</span> <<span class="codekeyword">typename</span> T>

       <span class="codekeyword">class</span> LinkList

    {

       <span class="codekeyword">typedef</span> NodeBase<T> NodeBase;



       NodeBase *head_;

       NodeBase *tail_;

    <span class="codekeyword">public</span>:



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



       ~LinkList()

       {

          <span class="codekeyword">while</span>( 0 != head_ )

          {

             NodeBase *temp = head_;

             head_ = head_->next_;

             <span class="codekeyword">delete</span> temp;

          }

          head_ = 0;

          tail_ = 0;

       }



       <span class="codecomment">// Appends an element to the list</span>

       <span class="codekeyword">void</span> Append( <span class="codekeyword">const</span> T &t )

       {

          NodeBase *item = <span class="codekeyword">new</span> NodeBase(t);



          <span class="codekeyword">if</span> ( 0 == head_ )

          {

             head_ = item;

             tail_ = item;

          }

          <span class="codekeyword">else</span>

          {

             tail_->next_ = item;

             tail_ = item;

          }

       }



       <span class="codecomment">// Link list traversal methods</span>

       NodeBase* Get_Head() <span class="codekeyword">const</span> { <span class="codekeyword">return</span> head_; }

       NodeBase* Get_Next( <span class="codekeyword">const</span> NodeBase * <span class="codekeyword">const</span> element ) <span class="codekeyword">const</span>

       {

          <span class="codekeyword">return</span> element->next_;

       }

    };



    <span class="codekeyword">#include</span> <iostream>

    <span class="codekeyword">using namespace</span> std;



    <span class="codecomment">// No need to derive from base class</span>

    <span class="codekeyword">class</span> Foo

    {

       <span class="codekeyword">int</span> i_;

    <span class="codekeyword">public</span>:

       <span class="codekeyword">explicit</span> Foo( <span class="codekeyword">int</span> i ) : i_(i)  {}



       <span class="codekeyword">friend</span> ostream& <span class="codekeyword">operator</span><<( ostream &os, <span class="codekeyword">const</span> Foo &f  )

       {

          <span class="codekeyword">return</span> os << f.i_;

       }

    };



    <span class="codekeyword">int</span> main()

    {

       LinkList<Foo> link_list;



       link_list.Append( Foo(2) );

       link_list.Append( Foo(3) );

       link_list.Append( Foo(4) );



       NodeBase<Foo> *temp = link_list.Get_Head();



       <span class="codecomment">// No downcast necessary</span>

       <span class="codekeyword">while</span> ( 0 != temp )

       {

          cout << temp->Get_Element() << " ";



          temp = link_list.Get_Next( temp );

       }



       <span class="codekeyword">return</span> 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.



    <span class="codecomment">// generic calculation components</span>

    <span class="codekeyword">template</span> <<span class="codekeyword">typename</span> T>

       <span class="codekeyword">struct</span> Add

    {

       <span class="codekeyword">static</span> T Calculate( T t1, T t2 ) { <span class="codekeyword">return</span> t1 + t2; }

    };



    <span class="codekeyword">template</span> <<span class="codekeyword">typename</span> T>

       <span class="codekeyword">struct</span> Subtract

    {

       <span class="codekeyword">static</span> T Calculate( T t1, T t2 ) { <span class="codekeyword">return</span> t1 - t2; }

    };



    <span class="codekeyword">template</span> <<span class="codekeyword">typename</span> T>

       <span class="codekeyword">struct</span> Multiply

    {

       <span class="codekeyword">static</span> T Calculate( T t1, T t2 ) { <span class="codekeyword">return</span> t1 * t2; }

    };



    <span class="codekeyword">template</span> <<span class="codekeyword">typename</span> T>

       <span class="codekeyword">struct</span> Divide

    {

       <span class="codekeyword">static</span> T Calculate( T t1, T t2 ) { <span class="codekeyword">return</span> 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



    <span class="codecomment">// A Generic operation performed on 4 inputs</span>

    <span class="codekeyword">template</span> <  <span class="codekeyword">typename</span> T,

             <span class="codekeyword">template</span> <<span class="codekeyword">typename</span>> <span class="codekeyword">class</span> Op1,

             <span class="codekeyword">template</span> <<span class="codekeyword">typename</span>> <span class="codekeyword">class</span> Op2,

             <span class="codekeyword">template</span> <<span class="codekeyword">typename</span>> <span class="codekeyword">class</span> Op3 >

       <span class="codekeyword">class</span> Operation

    {

    <span class="codekeyword">public</span>:

       <span class="codecomment">// perform a calcuation on the inputs</span>

       <span class="codekeyword">static</span> T Calculate( T t1, T t2, T t3, T t4 )

       {

          T temp1 = Op1<T>::Calculate( t1, t2 );



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



          <span class="codekeyword">return</span> Op3<T>::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.



    <span class="codecomment">// Note: Generic calculation/operation classes omitted for beverity</span>



    <span class="codekeyword">#include</span> <iostream>

    <span class="codekeyword">using namespace</span> std;



    <span class="codekeyword">int</span> main()

    {

       <span class="codecomment">// 1 + 3 - 2 * 4</span>

       cout << Operation<<span class="codekeyword">int</span>, Add, Subtract, Multiply>::Calculate(1,3,2,4) << "\n";



       <span class="codecomment">// (0.5 * 2 + 3) / 0.3</span>

       cout << Operation<<span class="codekeyword">double</span>, Multiply, Add, Divide>::Calculate(0.5,2,3,0.3) << "\n";



       <span class="codecomment">// 0.7 * 2 + 0.8 * 2</span>

       cout << Operation<<span class="codekeyword">float</span>, Multiply, Add, Multiply>::Calculate(0.7,2,0.8,2) << "\n";



       <span class="codecomment">// 1 + 2 + 3 + 4</span>

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



       <span class="codekeyword">return</span> 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








Comments

Note: Please offer only positive, constructive comments - we are looking to promote a positive atmosphere where collaboration is valued above all else.




PARTNERS