Section 1 - Dynamic Allocation of 2-D Arrays

3B.1.1 Dynamic Allocation of 1-D Arrays (REVIEW)

We've already seen how we can allocate (and delete) memory for a dynamic 1D array.

Allocation:

double *temperature;
temperature = new double[1000];

Deallocation:

delete[] temperature;

 So far, so good.  What about 2-D arrays?

3B.1.2 Dynamic Multi-Dimensional Arrays

An array of arrays - or multi-dimensional array - can be declared as an ordinary 2-D bracketed array:

#define NUM_CITIES 30
double flightTimes[NUM_CITIES][NUM_CITIES];

This is straightforward.

What about dynamic allocation? How do we duplicate the flexible approach of dynamic memory when the array is 2 (or more) dimensions? There are two array indices here, and that means we could use dynamic allocation for one or both.

3B.1.3 Partial Dynamic Allocation of 2-D Arrays

Let's look at the case where we use simple array allocation for the master column of the two-dimensional array, and dynamic allocation for the rows.

Declare a simple array of row vectors, or pointers, as follows:

double *flightTimes[NUM_CITIES];

Now, we have 30 pointers. So far, how many doubles have we allocated?

Answer: none.

Next, for each row pointer in this master column, we allocate 30 doubles.

for (row = 0; row < NUM_CITIES; row++)
{
  flightTimes[row] = new double[NUM_CITIES];
}

Now we have it! flightTimes[3][5] will refer to, for example, the double that is in the 3rd (actually 4th) row and 5th (actually 6th) column; we count down the master column to pointer 3, then we skip across the 1-D dynamic array of doubles pointed to by that pointer to double 5.

When we are done, we would have to delete the memory. How do you suppose that would have to be done?

Answer:

for (row = 0; row < NUM_CITIES; row++)
{
  delete[] flightTimes[row];
}

The flightTimes variable is a fixed sized array, so there is nothing to delete there.  But each of its elements is a dynamically allocated array of doubles, so we release this memory through a loop.

3B.1.4 Total Dynamic Allocation of 2-D Arrays

Now, for the completely dynamic version. In this version we use dynamic allocation for both the row and the column dimensions. So no simple array will be declared. We need to change the first array of pointers from a simple array to a dynamic array. That means we start with what?

How about this:

double **flightTimes;

Why is this a double pointer? Because we will continue next by declaring a set of pointers dynamically: this will be our master column, which earlier didn't require dynamic allocation.   When we declare a set of ints dynamically we need to start with an int pointer and use new. When we want a set of pointers dynamically, we need a pointer pointer (not a typo!) and use new. 

First, we construct the master row of pointers. For that we need a single statement:

flightTimes = new double* [NUM_CITIES];

Now we have NUM_CITIES double pointers. In other words, we are where we started in the earlier, "partial" dynamic allocation section. From here we can repeat the loop we saw above without changes:

for (row = 0; row < NUM_CITIES; row++)
{
  flightTimes[row] = new double[NUM_CITIES];
}

3B.1.5 Food For Thought

This was a long lesson with a lot of individual topics.  Here are two challenge questions for you to think about for the next couple of days.

Whether we declare a bracketed 2-D array, a partially dynamic 2-D array or a completely dynamic 2-D array is a matter of taste and need.  If memory is very tight we might opt for a completely dynamic 2-D array.  In all cases, however, we access the individual array elements using the same, simple bracket notation, i.e., flightTimes[j][k].