Previous Section
 < Free Open Study > 
Next Section


4.4 Dynamically Allocated Arrays

A template is a nice feature: It allows the client program to specify the type of the items on the structure at the time when an object of the data type is defined. Now, if we could just find a technique to enable the client to specify the maximum number of items on the stack at the same time. Then we would not need to use an auxiliary file. Of course, C++ provides such a technique. We can let the maximum number of items be a parameter to a class constructor. The implementation structure is an array, however. Doesn't the compiler need to know the size of an array at compile time? Yes, it does if the array is in static storage, but memory for the array can be allocated at run time if we let it be in dynamic storage (the free store or heap). This change requires the following changes in the class definition:

template<class ItemType>
class StackType
{
public:
  StackType(int max);  // max is stack size.
  StackType();         // Default size is 500.
  // Rest of the prototypes go here.
private:
  int top;
  int maxStack;        // Maximum number of stack items.
  ItemType* items;     // Pointer to dynamically allocated memory.
};

When declaring a class object, the client can specify the maximum number of stack items by using the parameterized constructor:

StackType<int> myStack(100);
// Integer stack of at most 100 items.

StackType<float> yourStack(50);
// Floating-point stack of at most 50 items.

Alternatively, the client can accept the default size of 500 by using the default constructor:

StackType<char> aStack;

Within the function definition for each constructor, we use the new operator to allocate an array of exactly the desired size. Earlier we saw that the expression new SomeType allocates a single variable of type SomeType on the free store and returns a pointer to it. To allocate an array, you attach to the data type name the array size in brackets: new AnotherType [size]. In this case, the new operator returns the base address of the newly allocated array. Here are the implementations of the StackType constructors:

template<class ItemType>
StackType<ItemType>::StackType(int max)
{
  maxStack = max;
  top = -1;
  items = new ItemType[maxStack];
}
template<class ItemType>
StackType<ItemType>::StackType()
{
  maxStack = 500:
  top = -1;
  items = new ItemType[maxStack];
}

Notice that items is now a pointer variable, not an array name. It points to the first element of a dynamically allocated array. In C++, however, you can attach an index expression to any pointer-not only an array name-as long as the pointer points to an array. Thus items can be indexed exactly as it was when it was defined as an array of type ItemType (see Figure 4.5). Only one member function then needs to be changed: IsFull.

Click To expand
Figure 4.5: A stack in which the array is in dynamic storage
template<class ItemType>
bool StackType<ItemType>::IsFull() const
{
  return (top == maxStack-1);
}
C++: Lifetime of a Variable
Start example

The lifetime of a variable is the time during program execution when the variable has storage assigned to it.

  • The lifetime of a global variable is the entire execution of the program.

  • The lifetime of a local variable is the execution of the block in which it is declared.[2]

  • The lifetime of a dynamically allocated variable lasts from the time it is allocated until the time it is deallocated.

End example

We do, however, need to use a class destructor. If the stack is a local variable (and not declared as static), the memory allocated to the stack object is deallocated when the stack goes out of scope. As a consequence, the memory allocated to top, maxStack, and items is deallocated, but the array to which items points is not. For this reason, we must include a class destructor. A class destructor is a member function with the same name as a class constructor except that the destructor has a tilde (~) in front of the type name. A destructor is implicitly invoked when a class object goes out of scope-for example, when control leaves the block in which an object is declared. We include the prototype of the destructor in the public part of the class definition,

~StackType();     // Destructor

and implement the function as follows:

template<class ItemType>
StackType<ItemType>::~StackType()
{
  delete [] items;
}

To deallocate an array, you insert brackets between the word delete and the name of the pointer. See how this class destructor differs from an operation that makes a stack empty? Setting the top data member to -1 makes the stack empty, but the allocated space is still there. The class destructor releases the space that was allocated to the array. Making a structure empty is a logical operation defined in an ADT specification, whereas a class destructor is an implementation-level operation. Implementations that do not use dynamically allocated space typically do not need destructors.

Before we leave this StackType implementation, let's ask whether we need to provide both a parameterized constructor and a default constructor. Isn't the parameterized constructor good enough? In most cases, yes. Sometimes, however, the user may want to declare an array of stack objects, in which case the parameterized constructor cannot be used. (Remember the rule: If a class has any constructors and an array of class objects is declared, one of the constructors must be the default constructor, and it is invoked for each element in the array.) It's wisest to include a default constructor in the StackType class to allow client code like this:

StackType<float> stackGroup [10];
// 10 stacks, each of size 500

[2]Sometimes it is useful for a local variable to retain its value, so C++ lets the user extend the lifetime of a local variable to the entire run of the program. To do so, you preface the data type identifier with the reserved word static when the variable is defined. Otherwise, the default storage category is automatic, in which storage is allocated on entry and deallocated on exit from a block.



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)