←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 intemplate< class T >
or
template< typename ElementType >
or
template< class BorderType, class 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?