Back to July Calendar 

Previous Entry Next Entry→

September 13, 2005

Chapter 21 of Deitel is about the Standard Template Library (STL.)   The title page includes some interesting quotes, starting with "The shapes a bright container can contain!"  This is from the poem, I Knew a Woman, by Theodore Roethke.  Quite the rakish ramble, that! 
 
The next quotation offered is, "Journey over all the universe in a map, without the expense and fatigue of traveling, without suffering the inconveniences of heat, cold, hunger, and thirst." --Miguel de Cervantes (Don Quixote, 1615.)   I question the attribution, since I can't verify it.  I searched all of Don Quixote and Bartleby's Quotations.  Well, perhaps, as Sancho Panza intoned, "A closed mouth catches no flies."   So I'll just shut up and move on to maps.
 
To get a good handle on STL, I'll need to look at chapter 11 (Templates) and Chapter 17 (Data Structures.)  There are function templates and class templates.  Each provides a sort of cookie cutter approach to creating a wide variety of function and class types.   The idea is that if you find yourself doing a lot of overloading for a function, you may as well make a template for that function.  Function templates are like macros created with the preprocessor command #define, but avoid some of the pitfalls of macros, such as a failure to do type checking.    
 
All function-template definitions begin with keyword template followed by a list of formal type parameters to the function template enclosed in brockets; each formal type parameter must be preceded by either of the interchangeable keywords class or typename, as in

templateclass T >

or

templatetypename ElementType >

or

templateclass BorderTypeclass FillType >
Here's Deitel's example illustrating the use of a template function.  The key observation is that "T" is for type.  Any type.  So the first parameter of printArray() can be an int, double or a char, without having to write code to overload the function for that purpose, such as
void printArray( const int *, const int );
void printArray( const double *, const int );
void printArray( const char *, const int );
 
   1  //  Fig. 11.1: fig11_01.cpp
  2  // Using template functions.
  3  #include <iostream>
  4 
  5  using std::cout;
  6  using std::endl;
  7 
  8  // function template printArray definition
  9  template< class T >
 10  void printArray( const T *array, const int count )
 11  {
 12     for ( int i = 0; i < count; i++ )
 13        cout << array[ i ] << " ";
 14 
 15     cout << endl;
 16 
 17  } // end function printArray
 18 
 19  int main()
 20  {
 21     const int aCount = 5;
 22     const int bCount = 7;
 23     const int cCount = 6;
 24 
 25     int a[ aCount ] = { 1, 2, 3, 4, 5 };
 26     double b[ bCount ] = { 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7 };
 27     char c[ cCount ] = "HELLO"// 6th position for null
 28 
 29     cout << "Array a contains:" << endl;
 30 
 31     // call integer function-template specialization
 32     printArray( a, aCount );                       
 33 
 34     cout << "Array b contains:" << endl;
 35 
 36     // call double function-template specialization
 37     printArray( b, bCount );                      
 38 
 39     cout << "Array c contains:" << endl;
 40 
 41     // call character function-template specialization
 42     printArray( c, cCount );                         
 43 
 44     return 0;
 45 
 46
  } // end main
 
=================
 
Thus, function templates and overloading are closely related ideas.  
 
Class templates are called parameterized types because they need at least one type parameter to specify how to treat a cookie cutter class template specific. 
 

The “stack” data structure (insert items at the top and retrieve those items in last-in-first-out LIFO order) can be independent of the type of the items being placed in the stack. You can specify the type of stuff you're stacking when you instantiate the stack This is good software reusability . Instantiating classes that are type-specific versions of a generic class through class templates is a technique called generic programming.   Here's the example from Deitel:

  1  //  Fig. 11.2: tstack1.h
  2  // Stack class template.
  3  #ifndef TSTACK1_H
  4  #define TSTACK1_H
  5 
  6
  template< class T >
  7
  class Stack {     
  8 
  9  public:
 10     Stack( int = 10 );  // default constructor (stack size 10)
 11 
 12     // destructor
 13     ~Stack()
 14     {
 15        delete [] stackPtr;
 16    
 17     } // end ~Stack destructor
 18 
 19     bool push( const T& );  // push an element onto the stack

 20     bool pop( T& );         // pop an element off the stack

 21 
 22     // determine whether Stack is empty
 23     bool isEmpty() const
 24     {
 25        return top == -1;
 26    
 27     } // end function isEmpty
 28 
 29     // determine whether Stack is full
 30     bool isFull() const
 31     {
 32        return top == size - 1;
 33    
 34     } // end function isFull
 35 
 36  private:
 37     int size;     // # of elements in the stack
 38     int top;      // location of the top element
 39    
T *stackPtr;  // pointer to the stack
 40 
 41  }; // end class Stack
 42 
 43  // constructor
 44  template< class T >      

 45 
Stack< T >::Stack( int s )
 46  {
 47     size = s > 0 ? s : 10
 48     top = -1// Stack initially empty
 49    
stackPtr = new T[ size ]; // allocate memory for elements
 50 
 51  } // end Stack constructor
 52 
 53  // push element onto stack;
 54  // if successful, return true; otherwise, return false
 55  template< class T >                       

 56 
bool Stack< T >::push( const T &pushValue )
 57  {
 58     if ( !isFull() ) {
 59        stackPtr[ ++top ] = pushValue;  // place item on Stack
 60        return true // push successful
 61 
 62     } // end if
 63 
 64     return false// push unsuccessful
 65 
 66  } // end function push
 67 
 68  // pop element off stack;
 69  // if successful, return true; otherwise, return false
 70  template< class T >               

 71 
bool Stack< T >::pop( T &popValue )
 72  {
 73     if ( !isEmpty() ) {
 74        popValue = stackPtr[ top-- ];  // remove item from Stack
 75        return true// pop successful
 76 
 77     } // end if
 78 
 79     return false// pop unsuccessful
 80 
 81  } // end function pop
 82 
 83  #endif

 

Note that the member functions that are defined outside the class begin with template< class T > .  When doubleStack is instantiated as type Stack<double> (say, "stack of doubles") the compiler (invisibly) associates T with a double to make the source code for a Stack class of type double
 
For some reason, Deitel decided to put a size limit of 10 on this stack.  I wonder why?  The very next section in that chapter suggests including a second parameter, elements, to make this a variable upper bound.  Also, you can assign a default type to T.  Thus the declaration  template< class T = string, int elements> would so the default type is to have a Stack of strings and elements could specify the maximum number of strings you could keep on the stack. 
 
The advice of Deitel is to "whenever possible, specify the size of a container class (such as an array class or a stack class) at compile time (possibly through a non-type template size parameter.)  This eliminates the execution-time overhead of using new to create the space dynamically."  Further, "Whenever possible, specify the size of a container at compile time (possibly through a non-type template size parameter.)  This avoids the possibility of a potentially fatal execution-time error if new is unable to obtain the needed memory."
 
Wow.  That's strong language and it sounds important.  And it reminds of this woman whose execution is scheduled for tomorrow in Texas.  It seems, from what little I know, that the evidence was as wobbly as the defense was weak.  Is Governor Perry going to pull a George Bush and allow this possibly innocent woman to be killed by the state after being wrongfully imprisoned all this time?