How to use pointers effectively

Example: a fixed-size two-dimensional array of doubles

Arrays of pointers

The first generalisation of a simple array we made in the lecture was to go from a fixed matrix (two-dimensional array) to one where we know the first dimension (the number of rows) won't change but the length of each row will do. Given we are dealing with a matrix it's very likely we would adopt the following requirement:

• Requirement: the data must be accessed using the same [j][k] notation as a true two-dimensional array
  

In fact, this is an extremely common requirement in this sort of situation.

Assuming a first dimension of M then answering our four questions we see:

#include <stdlib.h>
#define M 3
int main() {
  int n;
  float *p[M];        // This is the array of pointers

  printf("Size of each vector?\n");
  scanf("%d", &n);    // Find the row size
  
  for (int i = 0; i < M; ++i)
    p[i] = xmalloc(n * sizeof *p[i]); // Allocate rows
  
  p[0][1] = 3.14159;
  // Use p for something 
  
  // Advanced point: resizing the arrays
  // feel free to skip this.
  printf("New size of each vector?\n");
  scanf("%d", &n);   // Find new the row size
  
  for (int i = 0; i < M; ++i)
    p[i] = realloc(p[i], n * sizeof *p[i]); // Resize the rows
  
  // Do something else

  return 0;
}

Step through this code

Things that link to other things

 Things that can link to other Things (that in turn can link to other Things...) are extremely powerful provided we know how to follow the links!

The key application of this is simple:

Pointers can point to other pointers

We illustrate this with an example not found in the lecture.

Using pointers to pointers to create a 2-D symmetric matrix

Physical problems often involve arrays that are symmetric: ar[j][[k] == ar[k][j] Rather than store every off-diagonal value twice we can consider a "triangular matrix" where the first row is of length one, the second of length two etc and make sure we only access ar[j][k] where k <= j  (Even if we didn't want to resize the "matrix", ordinary arrays wouldn't be able to handle this as the rows are of different lengths.)

This has the interesting property that if we do want to resize the matrix we don't need to resize the rows: the first row always has length one, the second length two etc. Rather, if we shrink the array we just free() the unwanted rows, if we grow the array we just allocate more rows. What we will need to do is to change the number of pointers to the rows. Thus this is essentially the miror image of the previous example where we could change the length of the rows but not the number of rows.
Let's answer our four questions:

Allocating and freeing data often has a required order

Calls to malloc() and free() are frequently in the reverse order.

#include<stdio.h>
#include<stdlib.h>
// Shrink or extend a symmetric array
float **resizesymarray(float **p, int oldm, int newm) {
  int i;

  // Is the new one smaller?
  for (i = newm; i < oldm; ++i) 
    free(p[i]);

  p = realloc(p, newm * sizeof *p); 

  // Is the new one bigger?
  for (i = oldm; i < newm; ++i) 
      p[i] = malloc((i+1) * sizeof *p[i]);
  
  return p;
}

// Create a new symmetric array
float **newsymarray(int m) {
  return resizesymarray(NULL, 0, m);
}

// Free a symmetric array
void freesymarray(float **p, int m) {
  resizesymarray(p, m, 0);
}
  
int main() {
  float **p = NULL;
  int n, newn;

  printf("Size of array (>0)?\n");
  scanf("%i", &n);

  p = newsymarray(n);
  p[0][0] = 17;
  p[n-1][1] = 11.3;

  printf("New size of array (>0)?\n");
  scanf("%i", &newn);

  p = resizesymarray(p, n, newn);
  // Do stuff here

  freesymarray(p, newn);
  // Do more stuff not requiring p

  return 0;
}

Step through this code

Compare this code's memory map with that of a true two-dimensional array.

Differences from true multi-dimensional arrays

At first sight p above looks just like a "real" array, in that their elements are accessed using the same source-level notation:

  int array[M][N];
  int **p = NULL;

  p = new2dint(M, N);

  p[1][7] = 17;
  array[1][7] = 17;

They are dereferenced as follows:

p[i][j] => *( *(p+i) + j)  

array[i][j] => *(array + (N*i + j))

This is why for functions which have arguments which are multidimensional arrays we must tell the function the size of the array (which the left-most size being optional):

int oldstylefun(float array[][N]);
int newstylefun(int n, float array[][n]);
int three_d_fun(int m, int n, float array[][m][n]);

  int (*par)[N], j;

  printf("First dimension?\n");
  scanf("%d", &j);
  par = malloc(j * sizeof *par);
  par[j-1][0] = 3.14159;

Advantages and disadvantages of using malloc()

Allocated memory is permanent

Unlike true arrays, which vanish when the function returns, allocated memory is permanent until explicitly freed. This means that memory can be allocated inside sub-functions and is still there for the calling function when the sub-fnction retunrs.

malloc() is quite slow

One not very obvious disadvantage of malloc() is that because it's so general it's also quite slow. This means that for, say, short arrays that will be used within a function (and the functions it calls) and then thrown away at the end of the function it is better to use automatic ("normal") arrays if we can.

#include <stdlib.h>

void poorfun(int n) {
  double *x;

  x = xmalloc(n * sizeof *x);
  // .. Do some stuff with x

  free(x);
}

void betterfun(int n) {
  double x[n];

  // .. Do some stuff with x
}

The first version has more ways to go wrong, we might forget to call free(), and is also slower. (However, until C99 programmers had no choice as array sizes had to be declared at compile time.) It's not unknown for the speed of some programs to be dominated by calls to malloc().

Summary

The text of each key point is a link to the place in the web page.