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.