Dynamic Memory Allocation

Memory Allocation:

There are two types of memory allocation.

1) Static memory allocation -- allocated by the compiler. Exact size and type of memory must be known at compile time.

2) Dynamic memory allocation -- memory allocated during run time. Exact sizes or amounts (like the size of an array, for example) does not have to be known by the compiler in advance.  This memory is allocated by the run time system.  To allocate memory dynamically, we have to use pointers.

Dynamic Memory Allocation:

To dynamically allocate memory in C++, we use the new operator.  To de-allocate dynamic memory, we use the delete operator.  Dynamic memory is created in an area of memory often referred to as the "free store", or the "heap".  We can only allocate space during run time.  We cannot create new variable names during run time -- all identifiers must be known by the compiler.  For this reason, creating dynamic memory involves two steps:

  1. Creating the dynamic space.
  2. Storing its address in a statically allocated pointer (which has a name).

This gives us a name by which we can refer to the dynamic data.  We always access dynamically allocated space through a pointer.

For step (1), use the new operator, followed by the type being allocated.

 new int;        // dynamically allocates an int 
 new double;     // dynamically allocates a double 
 new Fraction;   // dynamically allocates a Fraction object 
 new int[40];    // dynamically allocates an array of 40 ints 

These statements above are not very useful by themselves, because the allocated spaces have no names!  How do we get to them?
The new operator returns the address of the allocated space, so we must capture this in a pointer (with an assignment statement).

 int * p;        // declare a pointer p 
 p = new int;    // dynamically allocate an int and load address into p 

 double * d;     // declare a pointer d 
 d = new double; // dynamically allocate a double and load address into d 

 // we can also do these in single line statements 

 Fraction * fp = new Fraction; 

 int x = 40; 
 int * ptr = new int[x]; 
Notice that this last example shows that a variable can be used as the size, when creating an array dynamically, since the allocation is happening at run time. This is different from the static allocation, which requires a constant value for the size.

Dynamically allocating objects:  We see from the examples above that this works on user-defined types as well (like Fraction).  However, don't forget that the Fraction constructor has to run when we create a Fraction object.  If the class has a default constructor, then this is the one that runs unless you specify otherwise.  To use a different constructor, just pass in the parameters after the dynamic allocation:

 Fraction * fp = new Fraction(3,5);  // initializes object to 3/5

Deleting dynamic memory:  You never need to worry about getting rid of statically allocated memory. Those variables are automatically handled by the compiler, which has already determined their scope and their lifetime. However, anything you create dynamically will not be taken care of by the compiler. It is up to you to clean this memory up when you are done with it. To deallocate dynamically allocated memory, apply the delete operator to the pointer, and it will delete the dynamic memory that the pointer is pointing to. (Note: This does not deallocate the pointer).

 delete fp;      // deletes the fraction pointed to by fp 
 delete [] ptr;  // deletes the array allocated in the example above 
When deallocating a dynamic array, use the form:
 delete [] pointername

Notation --  The arrow operator:

If we dynamically allocate an object, and therefore can only refer to it with a pointer, then how do we call its public member data or member functions?  The usual format is:   objectName.memberName

Consider the following:

 Fraction * fp = new Fraction;   // fp is a pointer to a dynamic Fraction object 

How do we call the Show() function for this object?  We don't have a separate name for the object, but we can refer to it by de-referencing the pointer.  So, the object's effective name is:  *fp

So, here are some calls to Fraction member functions:


Note: The parintheses here are essential, because the dot-operator has higher precedence than the * operator, and we need to dereference the pointer first!  This statement would be incorrect:

 *fp.Show();  // this would be the same as  *(fp.Show());  which is syntactically incorrect 

Since having to deal with the parintheses is notationally yucky (a technical computer term), we have another operator for these situations that is nicer to use -- the arrow operator    ->     This operator can be used instead of the dot operator when are accessing objects through pointers.  Here are the equivalent function calls with the arrow operator:

 fp -> Evaluate();    // note that the spacing is irrelevant.  Just keep the arrow together -> 

Application Example: Dynamically resizing an array

If you have an existing array, and you want to make it bigger (add array cells to it), you cannot simply append new cells to the old ones.  Remember that arrays are stored in consecutive memory, and you never know whether or not the memory immediately after the array is already allocated for something else.   For that reason, the process takes a few more steps.  Here is an example using an integer array.  Let's say this is the original array:
 int * list = new int[size]; 

I want to resize this so that the array called list has space for 5 more numbers (presumably because the old one is full).
There are four main steps.

1) Create an entirely new array of the appropriate type and of the new size. (You'll need another pointer for this).

 int * temp = new int[size + 5]; 

2) Copy the data from the old array into the new array (keeping them in the same positions). This is easy with a for-loop.

 for (int i = 0; i < size; i++) 
    temp[i] = list[i]; 

3) Delete the old array -- you don't need it anymore! (Do as your Mom says, and take out the garbage!)

 delete [] list;    // this deletes the array pointed to by "list"

4) Change the pointer. You still want the array to be called "list" (its original name), so change the list pointer to the new address.

 list = temp; 

That's it! The list array is now 5 larger than the previous one, and it has the same data in it that the original one had. But, now it has room for 5 more items.

Code Example: PhoneBook Database Simulation

The above link is to an example that involves two classes and uses dynamic memory allocation.  The classes are Entry and Directory.

Entry -- An object of this class type represents a single entry in a phone book.  The data members stored in an entry object are name, address, and phone number.  Strings (i.e. null-terminated character arrays) are used to store these items.

Directory -- An object of type Directory stores a list of Entry objects, using a dynamic array.  The Directory class also provides services (public member functions) for adding new entries, deleting entries, modifying entries, searching for entries, and displaying all entries in the phone book.  The Directory class also has a function for dynamically resizing the array of Entries when more memory space is needed.

Note that in this class, the destructor is also implemented for the Directory class, with a needed definition inside. Since the member data of an object of type Directory includes a pointer, which is being used to point to dynamically allocated space (i.e. the array of entries), it is our job in the code to deallocate that space. When the object is deallocated, the compiler only automatically gives up the space inside the object. The pointer entryList is pointing to data that is physically outside the object, so it doesn't get automatically "cleaned up". But, we can clean up this space (before the object goes away) by doing it in the last function that runs for an object (which is always the destructor). Note that the definition of this destructor is:

 delete [] entryList;
This simply deallocates the dynamic array attached to entryList, before we let this pointer be deallocated along with the object.