C++ Notes: Example: Expanding an Array

A central problem in programming is the fixed size of arrays. This problem can be avoided by dynamically allocating arrays. The following shows a simple problem: read integers then print them. But you don't know how many integers there will be.

Fixed Allocation Example

This program fragment will break if more than 1000 integers are entered.

const int MAX = 1000;
int a[MAX];            // allocated on call stack
int n = 0;

//--- Read into the array
while (cin >> a[n]) {  // can overflow array
    n++;
}

//--- Write out the array
for (int i=0; i<n; i++) {
    cout << a[i] << endl;
}

You can check to see if MAX has been exceeded in the input loop, but then what should you do? Giving an error message and stopping doesn't solve anyone's problem. Continuing with only part of the data is worse because it will give the wrong answer. The way to handle this is to make the array bigger!

Dynamic Allocation Example

This program is only limited by the amount of memory. It starts with a small array and expands it only if necessary.

int  max = 10;            // Current allocated max size.
int* a   = new int[max];  // Allocate space in heap.
int  n   = 0;             // Current number of elements.

//--- Read into the array
while (cin >> a[n]) {
    n++;
    if (n >= max) {
        max = max * 2;            // Double the previous size.
        int* temp = new int[max]; // Allocate new, bigger array.
        for (int i=0; i<n; i++) {
            temp[i] = a[i];       // Copy old array to new array.
        }
        delete [] a;              // Free old array memory.
        a = temp;                 // Now a points to new array.
    }         
}
//--- Write out the array etc.

Expansion policy

A common policy for how much larger to make a dynamic array is to double the previous allocation. Another it to add a fixed size. Making it only 1 element larger is usually not done because of the overhead of memory allocation, copying, and deallocation.

Remaining problems

This is a very nice technique, but doesn't solve all problems. For example.

If the reallocation is made in a function on a parameter, how is this information transmitted back to the original pointer to the array and the size information.
It's awkward to make the necessary test and allocation everywhere.

The solution to these, and other, problems is in the STL vector class.