Dynamic array

Dynamic Memory Allocation

Allocating memory

There are two ways that memory gets allocated for data storage:

1. Compile Time (or static) Allocation

   • Memory for named variables is allocated by the compiler

   • Exact size and type of storage must be known at compile time

   • For standard array declarations, this is why the size has to be constant

2. Dynamic Memory Allocation

   • Memory allocated "on the fly" during run time

   • dynamically allocated space usually placed in a program segment known as the heap or the free store

   • Exact amount of space or number of items does not have to be known by the compiler in advance.

   • For dynamic memory allocation, pointers are crucial

Dynamic Memory Allocation

• We can dynamically allocate storage space while the program is running, but we cannot create new variable names "on the fly"

• For this reason, dynamic allocation requires two steps:

  1. Creating the dynamic space.

  2. Storing its address in a pointer (so that the space can be accesed)

• To dynamically allocate memory in C++, we use the new operator.

• De-allocation:

  • Deallocation is the "clean-up" of space being used for variables or other data storage

  • Compile time variables are automatically deallocated based on their known extent (this is the same as scope for "automatic" variables)

  • It is the programmer's job to deallocate dynamically created space

  • To de-allocate dynamic memory, we use the delete operator

Allocating space with new

• To allocate space dynamically, use the unary operator new, followed by the type being allocated.

   new int;        // dynamically allocates an int 
   new double;     // dynamically allocates a double
  

• If creating an array dynamically, use the same form, but put brackets with a size after the type:

   new int[40];      // dynamically allocates an array of 40 ints 
   new double[size]; // dynamically allocates an array of size doubles
                     //  note that the size can be a variable
  

• These statements above are not very useful by themselves, because the allocated spaces have no names! BUT, the new operator returns the starting address of the allocated space, and this address can be stored in a pointer:

   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 
   int x = 40;
   int * list = new int[x];
   float * numbers = new float[x+10];
  

  Notice that this is one more way of initializing a pointer to a valid target (and the most important one).

Accessing dynamically created space

• So once the space has been dynamically allocated, how do we use it?

• For single items, we go through the pointer. Dereference the pointer to reach the dynamically created target:

    int * p = new int;	// dynamic integer, pointed to by p
  
    *p = 10;		// assigns 10 to the dynamic integer
    cout << *p;		// prints 10
  

• For dynamically created arrays, you can use either pointer-offset notation, or treat the pointer as the array name and use the standard bracket notation:

    double * numList = new double[size];	// dynamic array
  
    for (int i = 0; i < size; i++)
        numList[i] = 0;			// initialize array elements to 0
  
    numList[5] = 20;			// bracket notation
    *(numList + 7) = 15;			// pointer-offset notation
  					//   means same as numList[7]
  

Deallocation of dynamic memory

• To deallocate memory that was created with new, we use the unary operator delete. The one operand should be a pointer that stores the address of the space to be deallocated:

    int * ptr = new int;		// dynamically created int
    // ...
    delete ptr;			// deletes the space that ptr points to
  

  Note that the pointer ptr still exists in this example. That's a named variable subject to scope and extent determined at compile time. It can be reused:

    ptr = new int[10];		// point p to a brand new array
  

• To deallocate a dynamic array, use this form:

    delete [] name_of_pointer;
  

  Example:

    int * list = new int[40];	// dynamic array
  
    delete [] list;		// deallocates the array
    list = 0; 			// reset list to null pointer
  

  After deallocating space, it's always a good idea to reset the pointer to null unless you are pointing it at another valid target right away.
   

• To consider: So what happens if you fail to deallocate dynamic memory when you are finished with it? (i.e. why is deallocation important?)

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.

Dynamic Memory Allocation in Classes

Recap of DMA Basics

• Remember that memory allocation comes in two varieties:

  • Static (compile time): Sizes and types of memory (including arrays) must be known at compile time, allocated space given variable names, etc.

  • Dynamic (run-time): Memory allocated at run time. Exact sizes (like the size of an array) can be variable. Dynamic memory doesn't have a name (names known by compiler), so pointers used to link to this memory

• Allocate dynamic space with operator new, which returns address of the allocated item. Store in a pointer:

    int * ptr = new int;			// one dynamic integer
    double * nums = new double[size];     // array of doubles, called "nums"
  

• Clean up memory with operator delete. Apply to the pointer. Use delete [] form for arrays:

    delete ptr;		// deallocates the integer allocated above
    delete [] nums;	// deallocates the double array above
  

• Remember that to access a single dynamic item, dereference is needed:

    cout << ptr;		// prints the pointer contents
    cout << *ptr;		// prints the target
  

• For a dynamically created array, the pointer attaches to the starting position of the array, so can act as the array name:

    nums[5] = 10.6;
    cout << nums[3];
  

Dynamic Allocation of Objects

• Just like basic types, objects can be allocated dynamically, as well.

• But remember, when an object is created, the constructor runs. Default constructor is invoked unless parameters are added:

    Fraction * fp1, * fp2, * flist;
    fp1 = new Fraction;		// uses default constructor
    fp2 = new Fraction(3,5);	// uses constructor with two parameters
  
    flist = new Fraction[20];	// dynamic array of 20 Fraction objects
  				//  default constructor used on each
  

• Deallocation with delete works the same as for basic types:

    delete fp1;
    delete fp2;
    delete [] flist;
  

Notation: dot-operator vs. arrow-operator

• dot-operator requires an object name (or effective name) on the left side

    objectName.memberName		// member can be data or function
  

• The arrow operator works similarly as with structures.

    pointerToObject->memberName
  

• Remember that if you have a pointer to an object, the pointer name would have to be dereferenced first, to use the dot-operator:

    (*fp1).Show();
  

• Arrow operator is a nice shortcut, avoiding the use or parintheses to force order of operations:

    fp1->Show();		// equivalent to (*fp1).Show();
  

• When using dynamic allocation of objects, we use pointers, both to single object and to arrays of objects. Here's a good rule of thumb:
  For pointers to single objects, arrow operator is easiest:

    fp1->Show();
    fp2->GetNumerator();
    fp2->Input();
  

  For dynamically allocated arrays of objects, the pointer acts as the array name, but the object "names" can be reached with the bracket operator. Arrow operator usually not needed:

    flist[3].Show();
    flist[5].GetNumerator();
  
    // note that this would be INCORRECT, flist[2] is an object, not a pointer
    flist[2]->Show();
  

Using dynamic allocation inside classes

A motivating example

Suppose we want an array as member data of a class, but we don't want to be stuck with a fixed upper bound on the size. How do we accomplish this?

The solution would be to use dynamic allocation on the array. But how to arrange it? Can a dynamic array be physically embedded inside a class? What if an object of that class type is created statically? Then the compiler has to know the size. But the internal contents are to be dynamic?!

Solution: Only the pointer will be in the member data section. Dynamic memory will not be physically in the object, but only linked by the member data pointer.

Setting it up, using good design principles!

• To set up dynamic memory as contents of an object, declare one or more pointers as member data

• Always initialize pointers in the constructor!

  • Constructor might go ahead and dynamically allocate space right away, assigning addresses to pointers.

  • If not allocating space right away, best to initialize to null pointer until ready for use

• Use new inside class member functions to allocate space, attaching space to pointers (could be in constructors, or other member functions)

• Make sure to use delete to clean up dynamically allocated space whenever finished using it

  • This could happen in regular member functions, wherever space is cleared

  • This should happen in the destructor, because this is guaranteed to be the last function that runs for an object!

• Suggestion: Separate memory management tasks from the functionality/algorithmic tasks wherever possible:

  • Write a set of member functions just for dealing with memory management issues -- like creation of space, deallocation, resizing, etc

  • Your algorithmic functions can call the memory-handling functions, when needed

  • The more uses of new and delete there are in a class, the more complicated it gets, and the more chances of a memory leak. Separation of tasks helps minimize this.

Application Example: Dynamically resizing an array

(This was discussed in the pre-requisite course. See COP 3014 notes for full details. Just a summary is listed here)

To change the size of a dynamically allocated array (perhaps to add space), you cannot just append the next consecutive slots. Must find free space for entire array, in one consecutive set of memory. Summary of the basic process:

1. Dynamically create a new array of desired size. (This step will require a second pointer for temporary use).

2. Copy the old array's contents into the new one

3. Deallocate the memory of the old array (avoid memory leak)

4. Adjust pointers so that the new array has the desired name

This process is used in the following code example.

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.

Second version of Phone Book example

This one contains overloads of operator<< and operator>> in class Entry, instead of Show() and Load()