section 5.3: Pointers and Arrays

For some people, section 5.3 is evidently the hardest section in this book, or even if they haven't read this book, the most confusing aspect of the language. C introduces a novel and, it can be said, elegant integration of pointers and arrays, but there are a distressing number of ways of misunderstanding arrays, or pointers, or both. Take this section very slowly, learn the things it does say, and don't learn anything it doesn't say (i.e. don't make any false assumptions).

It's not necessarily true that ``the pointer version will in general be faster''; efficiency is (or ought to be) a secondary concern when considering the use of pointers.

page 98

On the top half of this page, we aren't seeing anything we haven't seen before. We already knew (or should have known) that the declaration int a[10]; declares an array of ten contiguous int's numbered from 0 to 9. We saw on page 94 and again on page 96 that & can be used to take the address of one cell of an array.

What's new on this page are first the nice pictures (and they are nice pictures; I think they're the right way of thinking about arrays and pointers in C) and the definition of pointer arithmetic. If the phrase ``then by definition pa+1 points to the next element'' alarms you; if you hadn't known that pa+1 points to the next element; don't worry. You hadn't known this, and you aren't expected even to have suspected it: the reason that pa+1 points to the next element is simply that it's defined that way, as the sentence says. Furthermore, subtraction works in an exactly analogous way: If we were to say

	pa = &a[5];

Note furthermore that we do not have to worry about the size of the objects pointed to. Adding 1 to a pointer (or subtracting 1) always means to move over one object of the type pointed to, to get to the next element. (If you're too worried about machine addresses, or the actual address values stored in pointers, or the actual sizes of things, it's easy to mistakenly assume that adding or subtracting 1 adds or subtracts 1 from the machine address, but as we mentioned, you don't have to think at this low level. We'll see in section 5.4 how pointer arithmetic is actually scaled, automatically, by the size of the object pointed to, but we don't have to worry about it if we don't want to.)

Deep sentence:

The meaning of ``adding 1 to a pointer,'' and by extension, all pointer arithmetic, is that pa+1 points to the next object, and pa+i points to the i-th object beyond pa.

This aspect of pointers--that arithmetic works on them, and in this way--is one of several vital facts about pointers in C. On the next page, we'll see the others.

page 99

Deep sentences:

The correspondence between indexing and pointer arithmetic is very close. By definition, the value of a variable or expression of type array is the address of element zero of the array.

Don't worry too much yet about the assertion that ``pa and a have identical values.'' We're not surprised about the value of pa after the assignment pa = &a[0]; we've been taking the address of array elements for several pages now. What we don't know--we're not yet in a position to be surprised about it or not--is what the ``value'' of the array a is. What is the value of the array a?

In some languages, the value of an array is the entire array. If an array appears on the right-hand sign of an assignment, the entire array is assigned, and the left-hand side had better be an array, too. C does not work this way; C never lets you manipulate entire arrays.

In C, by definition, the value of an array, when it appears in an expression, is a pointer to its first element. In other words, the value of the array a simply is &a[0]. If this statement makes any kind of intuitive sense to you at this point, that's great, but if it doesn't, please just take it on faith for a while. This statement is a fundamental (in fact the fundamental) definition about arrays and pointers in C, and if you don't remember it, or don't believe it, then pointers and arrays will never make proper sense. (You will also need to know another bit of jargon: we often say that, when an array appears in an expression, it decays into a pointer to its first element.)

Given the above definition, let's explore some of the consequences. First of all, though we've been saying

	pa = &a[0];

	pa = a;

	i = a[5];

	i = *(a+5);

	int *pa = &a[0];

The idea of the previous paragraph isn't worth much, because if you've got an array a, indexing it using the notation a[i] is considerably more natural and convenient than the alternate *(a+i). The significant fact is that this little correspondence between the expressions a[i] and *(a+i) holds for more than just arrays. If pa is a pointer, we can get at locations near it by using *(pa+i), as we learned on page 98, but we can also use pa[i]. This time, using the ``other'' notation (array instead of pointer, when we thought we had a pointer) can be more convenient.

At this point, you may be asking why you can write pa[i] instead of *(pa+i). You may be wondering how you're going to remember that you can do this, or remember what it means if you see it in someone else's code, when it's such a surprising fact in the first place. There are several ways to remember it; pick whichever one suits you:

1. It's an arbitrary fact, true by definition; just memorize it.
2. If, for an array a, instead of writing a[i], you can also write *(a+i) (as we proved a few paragraphs back); then it's only fair that for a pointer pa, instead of writing *(pa+i), you can also write pa[i].
3. Deep sentence: ``In evaluating a[i], C converts it to *(a+i) immediately; the two forms are equivalent.''
4. An array is a contiguous block of elements of a particular type. A pointer often points to a contiguous block of elements of a particular type. Therefore, it's very handy to treat a pointer to a contiguous block of elements as if it were an array, by saying things like pa[i].
5. [This is the most radical explanation, though it's also the most true; but if it offends your sensibilities or only seems to make things more confusing, please ignore it.] When you said a[i], you weren't really subscripting an array at all, because an array like a in an expression always turns into a pointer to its first element. So the array subscripting operator [] always finds itself working on pointers, and it's a simple identity (another definition) that pa[i] is *(pa+i).

The authors point out that ``There is one difference between an array name and a pointer that must be kept in mind,'' and this is quite true, but note very carefully that there is in fact every difference between an array and a pointer. When an array name appears in most expressions, it turns into a pointer (to the array's first element), but that does not mean that the array is a pointer. You may hear it stated that ``an array is just a constant pointer,'' and this is a convenient explanation, but it is a simplified and potentially misleading explanation.

With that said, do make sure you understand why a=pa and a++ (where a is an array) cannot mean anything.

Deep sentence:

When an array name is passed to a function, what is passed is the location of the initial element.

	int a[10];
	f(a);

	char string[] = "Hello, world!";
	int len = strlen(string);

We now realize that we've been operating under a gentle fiction during the first four chapters of the book. Whenever we wrote a function like getline or getop which seemed to accept an array of characters, and whenever we thought we were passing arrays of characters to these routines, we were actually passing pointers. This explains, among other things, how getline and getop were able to modify the arrays in the caller, even though we said that call-by-value meant that functions can't modify variables in their callers since they receive copies of the parameters. When a function receives a pointer, it cannot modify the original pointer in the caller, but it can definitely modify what the pointer points to.

If that doesn't make sense, make sure you appreciate the full difference between a pointer and what it points to! It is intirely possible to modify one without modifying the other. Let's illustrate this with an example. If we say

	char a[] = "hello";
	char b[] = "world";

	char *p = a;

	*p = 'H';

If we say

	p = b;

page 100

Since, as we've just seen, functions never receive arrays as parameters, but instead always receive pointers, how have we been able to get away with defining functions (like getline and getop) which seemed to accept arrays? The answer is that whenever you declare an array parameter to a function, the compiler pretends that you actually declared a pointer. (It does this mostly so that we can get away with the ``gentle fiction'' of pretending that we can pass arrays to functions.)

When you see a statement like ``char s[]; and char *s; are equivalent'' (as in fact you see at the top of page 100), you can be sure that (and you must remember that) it is only function formal parameters that are being talked about. Anywhere else, arrays and pointers are quite different, as we've discussed.

Expressions like p[-1] (at the end of section 5.3) may be easier to understand if we convert them back to the pointer form *(p + -1) and thence to *(p-1) which, as we've seen, is the object one before what p points to.

With the examples in this section, we begin to see how pointer manipulations can go awry. In sections 5.1 and 5.2, most of our pointers were to simple variables. When we use pointers into arrays, and when we begin using pointer arithmetic to access nearby cells of the array, we must be careful never to go off the end of the array, in either direction. A pointer is only valid if it points to one of the allocated cells of an array. (There is also an exception for a pointer just past the end of an array, which we'll talk about later.) Given the declarations

	int a[10];
	int *pa;

	pa = a;
	*pa = 0;
	*(pa+1) = 1;
	pa[2] = 2;
	pa = &a[5];
	*pa = 5;
	*(pa-1) = 4;
	pa[1] = 6;
	pa = &a[9];
	*pa = 9;
	pa[-1] = 8;

However, the statements

	pa = a;
	*(pa+10) = 0;	/* WRONG */
	*(pa-1) = 0;	/* WRONG */
	pa = &a[5];
	*(pa+10) = 0;	/* WRONG */
	pa = &a[10];
	*pa = 0;	/* WRONG */

	int *pa2;
	pa = &a[5];
	pa2 = pa + 10;	/* WRONG */
	pa2 = pa - 10;	/* WRONG */

	int a[10];
	int *pa, *pa2;
	pa = &a[5];
	pa2 = pa + 10;	/* WRONG */
	*pa2 = 0;	/* WRONG */