Project 1

computer science II

c m s c 214
f a l l 2 0 0 2

Pointer Arithmetic

Background

C++ is a language built on top of C. For a high-level language, C is considered rather low-level. Low-level, when it comes to programming languages, means that it is close to the hardware. High-level languages gives you more abstractions, and makes you think about the hardware less.

In particular, C allows you to access addresses and manipulate addresses fairly easily. C allows you to do pointer arithmetic.

Pointer Arithmetic

As you know, a pointer is an address. You can either have a pointer point to a variable (hold the address of a variable) or to an array element. It's not that different.

Here's an example:

   int x, arr[ 10 ] ;
   int *p1, *p2 ;

   p1 = & x ; // p1 points to x
   p2 = & arr[ 2 ] ; // p2 points to arr[ 2 ]

In fact, pointers and arrays are very related in C (and thus in C++). By definition, arr[ i ] is the same as *(arr + i). arr + i is pointer arithmetic.

In pointer arithmetic, you can add a pointer to an int value. This will produce another pointer which points to an element further down an array.

For example, if p2 points to element 4 of an array, then p2 + 3 points to element 7 (but p2 is unaltered) and p2 - 3 points to element 1.

You might wonder what happens if an array doesn't have enough elements. For example, what does p2 + 100 mean if the array only has 10 elements? You might think it should know that the array does not have 10 elements, and produce some sort of error.

However, this is not the case. When you pass an array to a function, it arrives as a pointer. Thus, the function has no way to determine the size of the array. So, how does it know how to do pointer arithmetic?

When it sees arr[ i ], it knows arr, which is the address of element 0 of the array. It multiplies i by the size of an element in the array (which it knows because of the type of the the pointer, arr). It then dereferences that result.

So, in a nutshell:

ptr + i produces a pointer that points to i elements after ptr (even if it does not exist--pretend it's an infinite sized array).
ptr - i produces a pointer that points to i elements before ptr (even if it does not exist--pretend it's an infinite sized array).

To repeat, what pointer arithmetic does is to do the following computation for you. When it sees ptr + i, it translates this (internally) to addr(ptr) + (i * sizeof(type)) where type is the type of the dereferenced pointer and addr is a "function" that returns the address of the pointer (of course, the pointer is actually an address, so this function doesn't do much but return that address). Thus, if ptr is an int *, it uses the type int in the sizeof operation.

Pointer Subtraction

You can also subtract pointers, as long as they have the same type. This will determine the distance between the two pointers. For example, if p2 points to element 10 of an array, and p1 points to element 3, then p2 - p1 is 7.

p1 - p2 is -7. The answer is negative if p1's address is smaller than p2's address.

Notice that the pointers do NOT actually have to point to array elements. Internally, the compiler computes the difference in the addresses, and divides by the size of the dereferenced pointer type.

That is, it performs the computation [addr(p2) - addr(p1)] / sizeof(type)

Again, it does this computation so you don't have to perform the division yourself.

Reading More

Pointer arithmetic is usually covered in a book on C. For example, it is covered in the CMSC 106 textbook. Usually, a data structures book isn't all that interested in covering such material.