Physics and Astronomy |
Back to top
The occasional appendices and optional examples in this module are for advanced material that you will not need for this module. They are intended for enthusiastic students who are interested in going further in programming for its own sake. This optional appendix goes into a little more detail about the thinking behind creating multi-dimensional pseudo arrays, and the use of pointers in general. How to use pointers effectivelyGiven the flexibility and usefulness of pointers and memory addresses the obvious question is "given a situation where they might be useful, how do we decide how to use them?". In general, this will depend on the answers to the following questions:
Questions to help us understand a
specific use of pointers and memory addresses
It is important to realise that questions 2, 3 and 4 may have more than one possible answer in which case the key is to choose one and carefully document it. Also, we may not necessarily answer the questions in that order: it's quite likely that we will have a particular way we want to access the data (Q3) for example, and this will influence the answers to questions 2 and 4. Or there may be restrictions on how we want to allocate objects which will then effect the other two. We saw examples of both of these later on in the lecture and in the examples. Example: a fixed-size two-dimensional array of doublesApplying these questions to a fixed-sized two-dimensional array of such as double ar[N1][N2] we find:
Arrays of pointersThe 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:
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:
The code looked like this: #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; } Things that link to other things
Ask yourself (or a colleague on the same module):
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
|
Question | Answer |
---|---|
1. What type of "thing" is this the address of and what are the values we need to represent this "thing"? | For a symmetrical matrix of size N there are N rows of numbers, the first row is one number long, the second two numbers long, .. and the final row N numbers long, for N*(N-1) numbers altogether. Each number is stored as a float. |
2. How are we going to organise and store these values in the computer's memory? | We will use N independent chunks of data, the first large enough to store one floating-point point number, the second two, ... and the last N numbers. As before, each of the N independent chunks of data will need its own pointer to store its address, but this time we will dynamically allocate an array of pointers. |
3. How are we going to proceed from knowing a single memory address to being to access any of these values? | This will allow elements to be accessed via the usual ar[j][k] notation. |
4. How are we going to allocate new "things", and if necessary resize and/or free them? |
|
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; }
Compare this code's memory map with that of a true two-dimensional array.
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;However, p and array are different things. p is a pointer to M pointers to N ints. By contrast, array points to a single block of M*N ints.
They are dereferenced as follows:
p[i][j] => *( *(p+i) + j)Double deference: deference: (p+i), add j and dereference the result.
array[i][j] => *(array + (N*i + j))Single deference: add N*i+j to array and dereference that.
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]);
The following monstrous construction declares a pointer that can be used to dynamically allocate a true two-dimensional array but we don't recommend you ever use it!
int (*par)[N], j; printf("First dimension?\n"); scanf("%d", &j); par = malloc(j * sizeof *par); par[j-1][0] = 3.14159;
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.
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.
Poor | Better |
---|---|
#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().
The text of each key point is a link to the place in the web page.