Lesson #20

How pointers and arrays interact

Overview

In this lesson I will cover the following topics

1. Using pointers to access array elements.

2. Pointer arithmetic.

3. Comparing pointers vs comparing the things they point at.

4. Bare array names and applying indicies against pointers.

Body

Another look at arrays

C is unusual among programming languages in the way it handles arrays. In C arrays and pointers are closely bound together. You can't really understand one without understanding the other. In this lesson I will describe how arrays and pointers interact.

Let me start by talking about an array of integers. Here's an example

int my_array = { 10, 12, 14, 16 };

This declares an array of four integers and initializes the elements. After the initialization the memory layout of the array looks like this

+----+--- my_array
| 10 |
+----+
| 0  |
+----+
| 0  |
+----+
| 0  |
+----+--- my_array
| 12 |
+----+
| 0  |
+----+
| 0  |
+----+
| 0  |
+----+--- my_array
| 14 |
+----+
| 0  |
+----+
| 0  |
+----+
| 0  |
+----+--- my_array
| 16 |
+----+
| 0  |
+----+
| 0  |
+----+
| 0  |
+----+---

Here I'm assuming that each array element requires four bytes (32 bits) of memory. Thus the entire array requires (4 elements * 4 bytes/element) 16 bytes of memory. The first four bytes are used for my_array, the next four bytes are used for my_array, and so forth. Remember: each byte can only hold values from 0 to 255. Large numbers require more than one byte to store their value. In this example, the numbers being stored in my_array are all small and they fit into a single byte. The other bytes are just zero. On many machines the "least significant byte" is the first byte in a group of four. However there are other machines that use a different ordering. This is not normally much of a concern one way or another.

Each array element has an address in memory. We could talk about those addresses using the "address of" operator. It looks like this

int main(void)
{
int  my_array = { 10, 12, 14, 16 };
int *p;

p = &my_array;
// Stores the address of the zeroth element of my_array into p.

*p = 8;
// This has the same effect as my_array = 8

// etc...
return 0;
}

Once I make p point at the zeroth element of my_array I can modify that element by using *p. This is no different than the way pointers work with individual integers. I could point p at any array element I wanted. For example

p = &my_array;

points p at the last array element. Then

*p = 8;

would have the same effect as my_array = 8.

Now things start getting good. The C language assures us that arrays will be laid out in contiguous memory. In other words: my_array will follow right after my_array, my_array will follow right after my_array, and so forth. There won't be any gaps or holes in the memory layout of an array.

In addition, when you increment a pointer the value stored in that pointer increases by an amount equal to the size of the thing the pointer is pointing at. Whew! You had better read that sentence twice! Here is what I mean

p = &my_array;

I'm assigning to p the address of the zeroth element of my_array. The pointer p now points at my_array.

p++;

Here I'm incrementing the pointer. I'm not incrementing what it points at (I'm not using the indirection operator). Instead I'm modifying the address stored in p. However, since p is a pointer to int and since integers are four bytes (in this example), "incrementing" p actually causes the address stored in p to advance by four. The pointer is then left pointing at my_array since that is what follows immediately after my_array. In the following picture each box is an entire array element. The boxes in this picture are actually four bytes together.

+----+
p -> | 10 |  my_array
+----+
| 12 |  my_array
+----+
| 14 |  my_array
+----+
| 16 |  my_array
+----+

The "p ->" notation is how I will show p pointing at something. Now after I increment p I get this picture.

+----+
| 10 |  my_array
+----+
p -> | 12 |  my_array
+----+
| 14 |  my_array
+----+
| 16 |  my_array
+----+

If I increment p again I get

+----+
| 10 |  my_array
+----+
| 12 |  my_array
+----+
p -> | 14 |  my_array
+----+
| 16 |  my_array
+----+

Do you get the idea? I can increment p and by doing so I can step down the array. Take a look at these two loops. They have the same effect.

int  i;
int *p;

// Using array indicies.
for (i = 0; i < 4; i++) {
printf("my_array[i] is %d\n", my_array[i]);
}

// Using pointers.
for (p = &my_array; p < &my_array; p++) {
printf("*p is %d\n", *p);
}

The first loop uses techniques you've seen before. It sweeps an integer index over all the legal values for my_array and prints out the value of each element of my_array.

The second loop does basically the same thing using pointers. It first assigns the address of my_array to p. Then, as long as p points into the array it prints the value of *p (one of the array elements). After each loop pass it increments p so that it will point at the next element in the array.

Notice that in the second loop I talk about my_array. Yet there is no my_array. Isn't that an error? In fact, my usage is perfectly fine. I'm not actually trying to touch my_array. Instead I'm just asking about its address. The expression &my_array is the address of the first memory location just past the end of the array. If p is less than that address it must still be pointing into the array normally. Once p becomes equal to or greater than that address it will be pointing off the end of the array and the loop must end. I can't try to access *p if p is pointing off into space!

This technique of using a pointer to step down an array instead of array indicies is very common. In some cases it will give you a faster program. Many C programmers use pointers to access their arrays all the time. You need to get used to seeing it.

Pointer arithmetic

Actually you can do more than just increment (and decrement) pointers. You can add (or subtract) an integer to (from) a pointer. You can also subtract one pointer from another. Let me explain what happens using some examples. Suppose we had our friend my_array again:

int  my_array = { 10, 12, 14, 16 };
int *p;

Let me give p a meaningful value.

p = &my_array;

Now the address stored in p is the address of the zeroth element of my_array. I can compute the address of element number one by doing p + 1. This expression takes a pointer and adds an integer. The result is a new pointer. In this case it is the address of the next integer in memory after the one p is pointing at. In this example p + 1 would be the same as &my_array.

The expression p + 2 points at the integer two places in memory after the one p is pointing at. In this example p + 2 would be the same as &my_array.

Things are more interesting if I start off pointing p at the middle of the array. Suppose I did p = &my_array. In that case p + 1 would be the same as &my_array and p - 1 would be the same as &my_array. Here is a picture. Like before each box in this picture represents an entire integer.

+----+
p - 2 ->| 10 |  my_array
+----+
p - 1 ->| 12 |  my_array
+----+
p     ->| 14 |  my_array
+----+
p + 1 ->| 16 |  my_array
+----+

So an expression like *(p - 1) = 8 is perfectly legal and reasonable. It stores the value of 8 into the memory location pointed at by p - 1. The expression p - 1 happens to be the address of element number one in my_array (in my current example). In other words, *(p - 1) = 8 is the same, in this case, as my_array = 8.

When you do things like this, you have to be certain you are not going off the end of the array. For example if you set p to point at my_array using p = &my_array then you can't do *(p + 2) = 8. The expression p + 2 would be the address of my_array. But there is no my_array. While it might be fine to talk about the address of my_array, you certainly can't put an 8 into that memory location! It would be exactly like doing my_array = 8 and I've already talked about why that's bad!

On the other hand, if you set p to point at my_array using p = &my_array then there is absolutely no problem doing *(p + 2) = 8. In that case you would be storing the 8 into my_array and that exists just fine. The bottom line: when you use pointers you need to consider what they are pointing at. How far you can "index off a pointer" in each direction will depending on how the pointer has been initialized.

Another thing you can do with pointers is compute the difference between two of them. This really only makes sense if the two pointers are pointing into the same array. If they are not, computing their difference might cause unpredictable things to happen. Take a look at this picture.

+----+
p1 -> | 10 |  my_array
+----+
| 12 |  my_array
+----+
p2 -> | 14 |  my_array
+----+
| 16 |  my_array
+----+

I got this by doing something like

p1 = &my_array;
p2 = &my_array;

Now I can compute the difference between p2 and p1 like this

p2 - p1

The result of this expression is the number of "slots" in the array between the two pointers. In this case the answer would be 2. I would have to increment p1 two times in order to make it equal to p2. If I did

p1 - p2

I would get -2. The negative result just says that p1 is not beyond p2 as would have been necessary to get a positive answer.

You might not be surprised to learn at this point that you can also compare two pointers.

if (p1 == p2) {
// I do this if p1 and p2 point at the same thing.
}

if (p1 < p2) {
// I do this if p1 is "before" p2 in the array.
}

if (p1 > p2) {
// I do this if p1 is "after" p2 in the array.
}

There are also !=, >=, and <= operators that you can apply to two pointers as well.

Be careful!

A POINTER IS AN ADDRESS!!

Don't forget that.

if (*p1 == *p2) ...

This compares the things the pointers are pointing at. It does not compare the pointers. The pointers might contain totally different addresses and yet point at (different) things with the same value.

if (p1 == p2) ...

This compares the pointers. It does not compare the things they are pointing at. The pointers might be pointing at things with the same value and yet have totally different addresses.

So which do you want to use? It depends on what you are trying to say. Sometimes you want to talk about the pointers and sometimes you want to talk about the things they are pointing at. There is no rule you can follow in general. You need to consider each case by itself.

Arrays don't exist

Actually, arrays don't exist in C. It's true. C only has pointers. Here's why I say that...

When you say the name of an array without specifying an index, the compiler understands that to mean the address of the zeroth element of the array. Check out this loop

for (p = my_array; p < my_array + 4; p++) {
printf("*p is %d\n", *p);
}

This is the way a loop like this might actually be written using pointers. The first thing it does is assign my_array to p. Despite how it looks this does not assign the entire array to the pointer. It wouldn't fit anyway! Instead the compiler treats the "naked" my_array as the address of the zeroth element of the array. Thus I'm initializing p with a pointer to the start of the array.

Next I have to run the loop "as long as" the address in p is in bounds. In particular, if p is less than the address my_array + 4 I'm okay. Notice that I'm adding the integer 4 to the address of the beginning of the array to compute the address just past the end of the array. There are no array indicies mentioned here and we don't need them. Welcome to C!

But... if you like indicies, don't dispair. You can apply them to pointers as well! Check this out.

int  my_array = { 10, 12, 14, 16 };
int *p;

p = &my_array;

p = 8;

Here I point p at my_array. Now, as explained earlier, I could do

*(p + 1) = 8;

to assign 8 to the next slot in the array after the spot where the pointer is pointing. Yet the notation *(p + 1) is a pain. C allows you to abbreviate this with the square brackets as p. Cool, eh? Since I've got p pointing into the middle of my_array, I could also do

p[-1] = 8;

This would assign 8 to my_array. (Do you see that?)

Now let's take a look at a normal, down to earth expression like

my_array = 8;

The compiler thinks of this in the following way: the name my_array is the address of the beginning of the array. The  notation means compute the address of the element 1 position(s) downstream from the address my_array and then use that address to access the element. In other words the compiler thinks you wrote

*(my_array + 1) = 8;

You can, in fact, write this and it will work exactly the same way.

When you declare an array, all you are really doing is telling the compiler to allocate a block of memory and to arrange things so that the name of the array is taken as a pointer to the first element in that block. Everything else is done with pointers from then on. The square bracket notation is just a convenience and nothing more. If you fully understand this, then you have a good grasp of pointers in C.

Summary

1. You can take the address of an array element just the way you take the address of any variable. For example, &my_array is the address of the third element of my_array. You can use pointers to scan down an array just as effectively as you can use integer indicies. For example,

int  my_array;
int *p;

for (p = &my_array; p < &my_array; p++) {
*p = ...
}

This works because incrementing (or decrementing) a pointer "steps" the pointer by an appropriate amount depending on the type of thing it is pointing at. For example, if integers are four bytes on your machine, doing a p++ on a pointer to integer will cause the address stored in p to advance by 4.

2. In addition to incrementing and decrementing pointers, you can also add an integer to a pointer to compute an address a certain number of "slots" downstream (or upstream if the integer is negative) from the pointer. For example, if p points at my_array, p + 2 would point at my_array, and p - 2 would point at my_array.

3. You can compare two pointers for equality to see if they point at the same thing or not. However, this is different than comparing the things they point at.

if (p1 == p2) { ...

This is "true" if p1 and p2 contain the same address.

if (*p1 == *p2) { ...

This is "true" if the variables pointed at by p1 and p2 contain the same value. In this case p1 and p2 might be pointing at two different variables.

4. When you use the name of an array without an index, the compiler takes that to be a pointer to the first element of the array. Thus

int  my_array;
int *p;

p = my_array;
// Stores &my_array into p.

When you apply square brackets to a pointer, the compiler accesses an appropriate array element using the pointer to find the starting address of the "array".

p    = &my_array;
p = 10;
// Same as *(p + 1) = 10. This stores 10 into my_array.

© Copyright 2003 by Peter C. Chapin.
Last Revised: June 17, 2003