Previous Table of Contents Next


8.3.3.1. Arrays or Isolated Objects?

The syntax for allocating multidimensional dynamic arrays is harder to understand than it might be because C++ tries to make two common usages particularly easy. One is allocating isolated objects. For example, if tp is a Thing*, then

   tp = new Thing;

makes tp point at a newly allocated Thing object. The other is allocating one-dimensional arrays of objects, so that

   tp = new Thing[5];

makes tp point at the initial element of an array of five objects of type Thing.

These two ways of allocating memory are so common that it makes sense to make them both as convenient as possible. That convenience comes at a cost: Although these two uses of new return the same type, they are really allocating two different types. We can make this clearer by giving a name to the type “array of 5 objects of type Thing”:

   typedef Thing Thingarray[5];

Now we might well expect

   tp = new Thingarray;

to work the same way as

   tp = new Thing[5];

and indeed it does—but it is exactly here that the problem lies.

Look again at the first example:

   tp = new Thing;

Here we are allocating an object of type Thing and putting the resulting pointer into a Thing*. So when we say

   tp = new Thingarray;

we might feel entitled to say that tp should be of type Thingarray*, not type Thing*. Why does this discrepancy occur? How do we resolve it?

The discrepancy comes from the fact that the size of an array is part of its type and from the desire to know the types of objects during compilation. We might be able to say that the type of the expression new Thing[5] is “pointer to array of 5 Thing objects,” but if we did so, what would be the type of new Thing[n]? Because the value of n is not known during compilation, the type of new Thing[n] cannot include the value of n, which means that it cannot be an array type directly. If the type of a new expression were an array type for a constant size, and not otherwise, that would be even harder to understand the way the language is actually defined.

We can resolve the discrepancy by remembering two simple rules:

  Allocating an array always yields a pointer to its initial element.
  Allocating a single object always yields a pointer to the object.

8.3.3.2. Arrays of Arrays

We can apply these rules to understand what happens in

   p = new Thing[10][5];

What should be the type of p? We note first that in C++, as in C, there are no true multidimensional arrays; instead we use arrays of arrays. Thus, for example, if we say

   Thing t[10][5];

then t is a 10-element array, each element of which is a 5-element array of Things. That implies that new Thing [10][5] is a request to allocate an array of arrays. If we apply our rules, we see that evaluating new Thing [10][5] should yield a pointer to the first element of the array. Which array? The array of arrays. That array has 10 elements—each element of it is an array of 5 elements—so p should be a pointer to an array of 5 elements of type Thing. As it happens, we’ve already defined a name for that type, so

   Thingarray* p = new Thing[10][5];

works fine. If we want to write it out longhand, we can do it this way:

   Thing (*p)[5] = new Thing[10][5];

Readers who do not understand all the fine points of declaration syntax should think of p as something with the property that *p is an array of 5 elements of type Thing. In other words, p is a pointer to an array—in this case, the array that is the initial element of an array of 10 arrays.

Notice that the value 10 appears in only one place. In particular, it is not part of the type of p. This is what makes it possible to say, for instance,

   p = new Thing[n][5];

without having to know the value of n during compilation. In that sense, the “type” Thing[n][5] isn’t quite a type at all, but rather something that looks almost like a type.

Indeed, the variable dimension must always be the first one to appear after new because the “type” of Thing[10][n], for example, must contain the value of n and that would never do if n were unknown until execution time.

8.3.3.3. Two Variable Dimensions

The foregoing discussion implies that although we have a way to allocate an array with one variable dimension, we do not have a way to allocate one with two. Suppose, for example, we want an m by n array of Things; how do we allocate such a beast?

One way is simply to allocate an m*n-element array and adopt the convention that the element at row i and column j is at position i*m+j. This technique essentially imitates the arithmetic that a compiler does anyway for two-dimensional arrays. It’s a bit of a pain, but an appropriate class definition can make it easier. That approach is left to the reader as an exercise.

The other approach is more flexible: Instead of trying to allocate an array of arrays, allocate an array of pointers, each one of which points to the initial element of an array. For an m by n array, we want m pointers, each of which points at the initial element of an n-element array:

   Thing** pp = new Thing* [m];
   int i;
   for (i = 0; i < m; i++)
        pp[i] = new Thing[n];

We can then pretend that pp is a two-dimensional array, and refer to pp[i][j]. Moreover, if we want, we can even make the “rows” of the matrix different sizes; nothing requires them all to be exactly n elements each.


Previous Table of Contents Next