Previous Table of Contents Next


7.2.6.3. Arrays

In C++, as in early versions of Pascal, arrays have only a single dimension. Multidimensional arrays are written as arrays of arrays. Also as in early versions of Pascal, the size of a C++ array is part of its type. This implies that the size of an array must be known at compilation time, which would be a nearly insurmountable obstacle were it not for the useful properties of pointers and the way in which C++ treats dynamic memory. Having all arrays’ sizes known during compilation dramatically simplifies compiler design, because it means that all stack frame sizes and layouts are known during compilation. Using dynamically allocated memory for all variable-sized data structures is not as much a hardship as it might appear, because those data structures can be wrapped in library classes and thereby made essentially as easy to use as built-in types.

As with pointers, the syntax for declaring arrays is derived from how the arrays are used. So, for example, if T is the name of a type,

   T x[10];

declares an array of T objects with 10 elements. The initial element always has index 0, so the indices of the elements of this array range from 0 through 9, inclusive.

Suppose we try to use both arrays and pointers in a single declaration, such as

   int *xx[10];

What does that mean? Again, we note that the declaration mirrors the use, so we are saying that *xx[10] has type int.4 Next we note that unary operators, such as *, and subscripting, all have the same precedence and group right to left. That means that *xx[10] means the same as *(xx[10]), and indeed we could have written the declaration as


4We aren’t quite saying that because xx[10] doesn’t exist the indices stop at 9. But for appropriate values of i, we are saying that *xx[i] has type int.
   int *(xx[10]);

with the same meaning. If declaration mirrors use, then the declaration must mean that if we extract an element of xx, we can apply * to that element and obtain an int. In other words, we have declared xx as an array of pointers to int. In effect, the fact that unary operators group right to left in expressions implies that they group left to right in declarations. If we wanted to declare a pointer to an array, we would have written

   int (*xp)[10];

7.2.6.4. Pointers and Arrays

On the surface, it appears that an expression enclosed in [ ] is a subscript, and that subscripting is a primitive operation. The truth is more subtle:

  Most uses of the name of an array automatically transform the array name into a pointer to its initial element.
  Pointer arithmetic is defined to be as convenient as indexing.
  The [] operator is actually defined in terms of pointer arithmetic.

We will consider each of these statements in turn.

There are very few operations on arrays directly: Essentially the only things you can do with a whole array is take its address or determine its size. So, for example, in

   int x[10];
   int* p = x;
   int (*xp)[10] = &x;

we have used x to initialize p without explicitly taking the address of x. Whenever we do that, it implicitly takes the address of the initial element of x, so p now points to that initial element.

On the other hand, when we write &x, we are taking the address of the entire array x, which, although it corresponds to the same memory location as the initial element, has a different type. We can then set xp to that address, because xp is a pointer to an array with the appropriate size and type.

It is important to realize that p and xp are not interchangeable in this context:

   p = &x;           // error
   xp = x;           // error

In each case, the error is that the types of the left-hand and right-hand sides of the assignment disagree, and there is no implicit conversion between those types.

The next important thing to realize about pointers is that if p points to an element of an array, then p+1 is defined to point to the next element and p-1 to the previous element, assuming that each element exists. In this particular example, we have set p to x, so p points to element 0 of the array x. That implies that p+5 points to element 5, and so on.

At an implementation level, computing p+n requires the machine to multiply n by the size of the object to which p points. This size can always be determined at compile time, so if n is a constant also (as it would be in p+1), the compiler can do that multiplication as it compiles the program.

Element n of the array x has address p+n, or, equivalently, x+n. From that, it should be easy to see that *(x+n) is the element itself, rather than the address, and that x[n] is therefore equivalent to *(x+n). Indeed, indexing is defined that way: x[n] means the same as *(x+n).

This definition has an amusing consequence: Because addition is commutative, x+n means the same as n+x, which means that x[n] means the same as n[x], provided only that x and n have built-in types. This property, however, is more amusing than useful.

The truly useful property is that not only can we refer to x[n], but we can also refer to p[n] where p is a pointer. This property implies that we can use a pointer to the initial element of an array as if it were the array itself. In fact, the pointer is more useful than the array for one important reason: It need not actually point to the initial element of the array. For example, consider

   void int_clear(int* p, int n)
   {
        while (--n >= 0)
               p[n] = 0;
   }

This function clears (sets to zero) n array elements starting at the one addressed by p. We can use this function to clear an array of integers, as in

   int table[100];
   int_clear(table, 100);

but we can also use it to clear any subarray of such an array, as in

   int_clear(table+23, 17);


Previous Table of Contents Next