Pointers to Pointers

Pointers to Pointers ( "The Middleman")

Another pointer curiosity that C throws our way is pointers that point to other pointers. This may seem like a needless feature, but it comes in very handy when you have multidimensional data whose size you don't know before-hand. You can then use these pointers to pointers to set up an arbitrary-sized multidimensional array.

It works like this: you can think of a pointer to a pointer as being essentially a list of lists. It's kind of like the words in the dictionary: the first pointer tells you where to find each of the lists for the letters of the alphabet. Each letter is then itself a pointer that forms a list (by pointing to the first element) of all of the words beginning with that letter. If you add another dimension (and make a pointer to a pointer to a pointer), you can have each word also be a list, pointing to the first out of several different meanings for the word.

Here's how it works in C++. The following program reads in a table of numbers and finds the average for each row and column. The first two numbers it reads in tell how many rows and columns there are. The rest of the numbers are the ones in the table.

Example

`#include `
` `
`  void main(void)`
`  {`
`    int** table;                        // *Two*-dimensional pointer.`
`    int   rows, cols, i, j, sum;        // Dimensions of table.`
` `
`    cin >> rows >> cols;                // Find out the number of rows & cols.`
` `
`  // What we'd really like to do here is say:`
`  //   table = new int[rows][cols];`
`  // Unfortunately, this doesn't work in C++, since it instead tries to set up`
`  // a one-dimensional array like this:`
`  //   table = new int[rows * cols];`
`  // And a one-dimensional array (a pointer to integers) is absolutely`
`  // incompatible with a two-dimensional array (a pointer to a pointer to`
`  // integers), so our program will crash.  Note that the syntax above will`
`  // work, however, in Java.`
` `
`    table = new (int*)[rows];           // Allocate the rows.`
`    for(i = 0; i < rows; i++)`
`      table[i] = new int[cols];         // Allocate each row's columns.`
` `
`    for(i = 0; i < rows; i++)           // Find row sums.`
`    {`
`      sum = 0;`
`      for(j = 0; j < cols; j++)`
`        sum += table[i][j];`
`      cout << "Row sum for row " << i << ": " << sum << endl;`
`    }`
` `
`    for(j = 0; j < cols; j++)           // Find column sums.`
`    {`
`      sum = 0;`
`      for(i = 0; i < rows; i++)`
`        sum += table[i][j];`
`      cout << "Col sum for col " << j << ": " << sum << endl;`
`    }`
`  }`

Notice how we had to explicitly allocate both dimensions of the array, starting with the first dimension, the rows; and then for each row we allocated its columns. You may be wondering why the outer dimension is allocated using "new (int*)[n]", while the inner dimension is allocated using "new int[n]". This is because each dimension but the last is a pointer to the next dimension. The final array dimension is obviously simply a list of integers, so in the inner loop we merely allocate a list of integers. The next dimension up, however, is not a list of integers; it's a list of lists of integers. As such, each entry in this list will itself be a pointer to a list of integers -- the final dimension. Therefore, the code allocating the outside dimension must allocate a list of pointers to integers.

If we had additional dimensions, for each column in each row we would then have to allocate the list of cells, and so forth. Here's how a three-dimensional array allocation might look like. Assume that x, y, and z are the size of each array dimension. Notice how the outer dimension is now a list of (int**)'s -- a list of lists of lists -- and the second dimension is now the one that is (int*) -- a list of lists -- while the final dimension is still a list of integers.

Example

`  int    i, j;`
`  int*** array3d;`
` `
`  array3d = new (int**)[x];`
`  for(i = 0; i < x; i++)`
`  {`
`    array3d[i] = new(int*)[y];`
`    for(j < 0; j < y; j++)`
`      array3d[i][j] = new int[z];`
`  }`