9.2 Dynamic Arrays

In this section you will see that array variables are actually pointer variables. You will also find out how to write programs with dynamic arrays. A dynamic array is an array whose size is not specified when you write the program, but is determined while the program is running.

Array Variables and Pointer Variables

In Chapter 7 we described how arrays are kept in memory. At that point we had not learned about pointers, so we discussed arrays in terms of memory addresses. But, a memory address is a pointer. So, in C++ an array variable is actually a pointer variable that points to the first indexed variable of the array. Given the following two variable declarations, p and a are the same kind of variable:

int a[10];
typedef int* IntPtr;
IntPtr p;

The fact that a and p are the same kind of variable is illustrated in Display 9.4. Since a is a pointer that points to a variable of type int (namely the variable a[0]), the value of a can be assigned to the pointer variable p as follows:

p = a;

After this assignment, p points to the same memory location that a points to. So, p[0], p[1], … p[9] refer to the indexed variables a[0], a[1], … a[9]. The square bracket notation you have been using for arrays applies to pointer variables as long as the pointer variable points to an array in memory. After this assignment, you can treat the identifier p as if it were an array identifier. You can also treat the identifier a as if it were a pointer variable, but there is one important reservation. You cannot change the pointer value in an array variable, such as a. You might be tempted to think the following is legal, but it is not:

IntPtr p2;
. . .//p2 is given some pointer value.
a = p2;//ILLEGAL. You cannot assign a different address to a.

Display 9.5 illustrates the working of the program in Display 9.4. As in Display 9.3, variables are represented as boxes and the value of the variable is written inside the box. An arrow indicates a pointer or reference to another memory location, in this case, the first element of the array.

Display 9.4 Arrays and Pointer Variables

 1     //Program to demonstrate that an array variable is a kind of pointer variable. 
 2    #include <iostream>
 3    using namespace std;
 4
 5    typedef int* IntPtr;
 6
 7    int main( )
 8    {
 9        IntPtr p;
10        int a[10];
11        int index;
12
13        for (index = 0; index < 10; index++)
14            a[index] = index;
15
16        p = a;
17
18        for (index = 0; index < 10; index++)
19            cout << p[index] << " ";
20        cout << endl;
21
22        for (index = 0; index < 10; index++)            Note that changes to the array p
23            p[index] = p[index] + 1;                       are also changes to the array a.
24
25        for (index = 0; index < 10; index++)
26            cout << a[index] << " ";
27        cout << endl;
28
29        return 0;
30    }

Output

0 1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 10

A four-part diagram explaining Display 9.4. — Display 9.5 Explanation of Display 9.4

Figure 9.5 Full Alternative Text

Creating and Using Dynamic Arrays

One problem with the kinds of arrays you have used thus far is that you must specify the size of the array when you write the program—but you may not know what size array you need until the program is run. For example, an array might hold a list of student identification numbers, but the size of the class may be different each time the program is run. With the kinds of arrays you have used thus far, you must estimate the largest possible size you may need for the array and hope that size is large enough. There are two problems with this. First, you may estimate too low, and then your program will not work in all situations. Second, since the array might have many unused positions, this can waste computer memory. Dynamic arrays avoid these problems. If your program uses a dynamic array for student identification numbers, then the size of the class can be entered as input to the program and the dynamic array can be created to be exactly that size.

Dynamic arrays are created using the new operator. The creation and use of dynamic arrays is surprisingly simple. Since array variables are pointer variables, you can use the new operator to create dynamic variables that are arrays and treat these dynamic array variables as if they were ordinary arrays. For example, the following creates a dynamic array variable with ten array elements of type double:

typedef double* DoublePtr;
DoublePtr p;
p = new double[10];

To obtain a dynamic array of elements of any other type, simply replace double with the desired type. To obtain a dynamic array variable of any other size, simply replace 10 with the desired size.

There are also a number of less obvious things to notice about this example. First, the pointer type that you use for a pointer to a dynamic array is the same as the pointer type you would use for a single element of the array. For instance, the pointer type for an array of elements of type double is the same as the pointer type you would use for a simple variable of type double. The pointer to the array is actually a pointer to the first indexed variable of the array. In the previous example, an entire array with ten indexed variables is created and the pointer p is left pointing to the first of these ten indexed variables.

Also notice that when you call new, the size of the dynamic array is given in square brackets after the type, which in this example is the type double. This tells the computer how much storage to reserve for the dynamic array. If you omit the square brackets and the 10, the computer will allocate enough storage for only one variable of type double, rather than for an array of ten indexed variables of type double. As illustrated in Display 9.6, you can use an int variable in place of the constant 10 so that the size of the dynamic array can be read into the program.

An illustration shows a code segment with a “Dynamic Array.” — Display 9.6 A Dynamic Array

Figure 9.6 Full Alternative Text

The program in Display 9.6 sorts a list of numbers. This program works for lists of any size because it uses a dynamic array to hold the numbers. The size of the array is determined when the program is run. The user is asked how many numbers there will be, and then the new operator creates a dynamic array of that size. The size of the dynamic array is given by the variable array_size.

Notice the delete statement, which destroys the dynamic array variable a in Display 9.6. Since the program is about to end anyway, we did not really need this delete statement; however, if the program went on to do other things with dynamic variables, you would want such a delete statement so that the memory used by this dynamic array is returned to the freestore. The delete statement for a dynamic array is similar to the delete statement you saw earlier, except that with a dynamic array you must include an empty pair of square brackets, like so:

delete [] a;

The square brackets tell C++ that a dynamic array variable is being eliminated, so the system checks the size of the array and removes that many indexed variables. If you omit the square brackets, you would be telling the computer to eliminate only one variable of type int. For example,

delete a;

is not legal, but the error is not detected by most compilers. The ANSI C++ standard says that what happens when you do this is “undefined.” That means the author of the compiler can have this do anything that is convenient— convenient for the compiler writer, not for you. Even if it does something useful, you have no guarantee that either the next version of that compiler or any other compiler you compile this code with will do the same thing. The moral is simple: Always use the

delete [] arrayPtr;

syntax when you are deleting memory that was allocated with something like

arrayPtr = new MyType[37];

You create a dynamic array with a call to new using a pointer, such as the pointer a in Display 9.6. After the call to new, you should not assign any other pointer value to this pointer variable, because that can confuse the system when the memory for the dynamic array is returned to the freestore with a call to delete.

How to Use a Dynamic Array

Define a pointer type: Define a type for pointers to variables of the same type as the elements of the array. For example, if the dynamic array is an array of double, you might use the following:
```
typedef double* DoubleArrayPtr;
```
Declare a pointer variable: Declare a pointer variable of this defined type. The pointer variable will point to the dynamic array in memory and will serve as the name of the dynamic array.
```
DoubleArrayPtr a;
```
Call new: Create a dynamic array using the new operator:
```
a = new double[array_size];
```
The size of the dynamic array is given in square brackets as in the example above. The size can be given using an int variable or other int expression. In the example above, array_size can be a variable of type int whose value is determined while the program is running.
Use like an ordinary array: The pointer variable, such as a, is used just like an ordinary array. For example, the indexed variables are written in the usual way: a[0], a[1], and so forth. The pointer variable should not have any other pointer value assigned to it, but should be used like an array variable.
Call delete[ ]: When your program is finished with the dynamic variable, use delete and empty square brackets along with the pointer variable to eliminate the dynamic array and return the storage that it occupies to the freestore for reuse. For example:
```
delete [] a;
```

Dynamic arrays are created using new and a pointer variable. When your program is finished using a dynamic array, you should return the array memory to the freestore with a call to delete. Other than that, a dynamic array can be used just like any other array.

Self-Test Exercises

Write a type definition for pointer variables that will be used to point to dynamic arrays. The array elements are to be of type char. Call the type CharArray.
Suppose your program contains code to create a dynamic array as follows:
```
int *entry;
entry = new int[10];
```
so that the pointer variable entry is pointing to this dynamic array. Write code to fill this array with ten numbers typed in at the keyboard.
Suppose your program contains code to create a dynamic array as in Self-Test Exercise 10, and suppose the pointer variable entry has not had its (pointer) value changed. Write code to destroy this new dynamic array and return the memory it uses to the freestore.

What is the output of the following code fragment? The code is assumed to be embedded in a correct and complete program.

int a[10];
int *p = a;
int i;
for (i = 0; i < 10; i++)
     a[i] = i;
for (i = 0; i < 10; i++)
     cout << p[i] << " ";
cout << endl;

What is the output of the following code fragment? The code is assumed to be embedded in a correct and complete program.

int array_size = 10;
int *a;
a = new int [array_size];
int *p = a;
int i;
for (i = 0; i < array_size; i++)
     a[i] = i;
p[0] = 10;
for (i = 0; i < array_size; i++)
     cout << a[i] << " ";
cout << endl;

Pointer Arithmetic (Optional)

There is a kind of arithmetic you can perform on pointers, but it is an arithmetic of addresses, not an arithmetic of numbers. For example, suppose your program contains the following code:

typedef double* DoublePtr;
DoublePtr d;
d = new double[10];

After these statements, d contains the address of the indexed variable d[0]. The expression d + 1 evaluates to the address of d[1], d + 2 is the address of d[2], and so forth. Notice that although the value of d is an address and an address is a number, d+1 does not simply add 1 to the number in d. If a variable of type double requires 8 bytes (eight memory locations) and d contains the address 2001, then d+1 evaluates to the memory address 2009. Of course, the type double can be replaced by any other type and then pointer addition moves in units of variables for that type.

This pointer arithmetic gives you an alternative way to manipulate arrays. For example, if arraySize is the size of the dynamic array pointed to by d, then the following will output the contents of the dynamic array:

for (int i = 0; i < arraySize; i++)
        cout << *(d + i)<< " ";

This code is equivalent to the following:

for(int i = 0; i < arraySize; i++)
       cout << d[i] << " ";

You may not perform multiplication or division of pointers. All you can do is add an integer to a pointer, subtract an integer from a pointer, or subtract two pointers of the same type. When you subtract two pointers, the result is the number of indexed variables between the two addresses. Remember, for subtraction of two pointer values, these values must point into the same array! It makes little sense to subtract a pointer that points into one array from another pointer that points into a different array. You can use the increment and decrement operators ++ and −−. For example, d++ will advance the value of d so that it contains the address of the next indexed variable, and d−− will change d so that it contains the address of the previous indexed variable.

Self-Test Exercises

These exercises apply to the optional section on pointer arithmetic.

What is the output of the following code fragment? The code is assumed to be embedded in a correct and complete program.

int arraySize = 10;
int *a;
a = new int[arraySize];
int i;
for (i = 0; i < arraySize; i++)
       *(a + i) = i;
for (i = 0; i < arraySize; i++)
       cout << a[i] << " ";
cout << endl;

What is the output of the following code fragment? The code is assumed to be embedded in a correct and complete program.

int arraySize = 10;
int *a;
a = new int[arraySize];
int i;
for (i = 0; i < arraySize; i++)
       a[i] = i;
while (*a < 9)
{
       a++;
       cout << *a << " ";
}
cout << endl;

Multidimensional Dynamic Arrays (Optional)

You can have multidimensional dynamic arrays. You just need to remember that multidimensional arrays are arrays of arrays, or arrays of arrays of arrays, or so forth. For example, to create a two-dimensional dynamic array, you must remember that it is an array of arrays. To create a two- dimensional array of integers, you first create a one-dimensional dynamic array of pointers of type int*, which is the type for a one-dimensional array of ints. Then you create a dynamic array of ints for each indexed variable of the array of pointers.

A type definition may help to keep things straight. The following is the variable type for an ordinary one-dimensional dynamic array of ints:

typedef int* IntArrayPtr;

To obtain a 3-by-4 array of ints, you want an array whose base type is IntArrayPtr. For example:

IntArrayPtr *m = new IntArrayPtr[3];

This is an array of three pointers, each of which can name a dynamic array of ints, as follows:

for (int i = 0; i < 3; i++)
        m[i] = new int[4];

The resulting array m is a 3-by-4 dynamic array. A simple program to illustrate this is given in Display 9.7.

An illustration shows a code segment with a “Two-Dimensional Dynamic Array.” — Display 9.7 A Two-Dimensional Dynamic Array

Figure 9.7 Full Alternative Text

Be sure to notice the use of delete in Display 9.7. Since the dynamic array m is an array of arrays, each of the arrays created with new in the for loop must be returned to the freestore manager with a call to delete[]; then, the array m itself must be returned to the freestore with another call to delete[]. There must be one call to delete[] for each call to new that created an array. (Since the program ends right after the calls to delete[], we could safely omit these calls, but we wanted to illustrate their usage.)