Features


Pointer Power in C and C++, Part 1

Christopher Skelly


Christopher Skelly has been a teacher of C and C++ for the past ten years, first for Plum Hall Inc., and then for his own company, Insight Resource Inc. Insight Resource also developed the bestselling help utility, KO-PILOT for WordPerfect, which Brit Hume called "the best add-in ever written." Chris has served on both the C and C++ ANSI committees, and was the Technical Chairman for this year's "C Plus C++" and "C++ in Action" conferences, presented by Boston University. He writes regularly for the C User's Journal and the C++ Journal, and can be reached at Insight Resource Inc., 914-631-5032, or at 71005.771@compuserve.com.

Pointers have always been the trickiest part of C to fully master. The syntax of declarations and expressions using pointers is decidedly different. Arrays have an often fuzzily understood relationship to pointers in C. Perhaps a minority of C programmers really understand that [] has no intrinsic connection with "arrayness," just as * has no fixed connection with "pointerness." Pointer arithmetic is tricky, especially with multiply-dimensioned arrays, or higher-level pointers like char **p. Pointers to functions provide a sublime power in C programs, but one easily misused, as any number of physically-damaged devices might testify to. Early BASIC and Pascal made it hard to shoot yourself in the foot. Early C made it easy, and later C and C++ can only help you if you let them. The situation I encountered teaching C in the early 1980s was well represented by one student who observed, "I was doing fine with C, until we got to pointers."

This two-part article sets out to help you master C's pointer power. Pointers turn out to be a marvelous aspect of the C family of languages. They let you solve many complex problems efficiently and elegantly, often using runtime analysis and decision-making stratagems. Despite their complex aspects, pointers in C turn out to be governed by relatively simple underlying ideas, which can be used to resolve even the most complex pointer problems. This article is based on the somewhat unconventional idea that pointers in C and C++, for all their power, are really quite simple, once one understands a small set of central principles.

This set of principles is designed to be extremely practical and simple to use. Virtually everything in this article applies to both C and C++.

Understanding this model of pointer behavior is critical. You can memorize rules or the meaning of certain particular expressions. You can even learn to work with simple pointers by rote. But unless you understand the underlying principles, you will get stuck every time by whatever the next level of complexity happens to be. C and C++ are wonderful at always having a next level of complexity available, should you have need of it!

The program in Listing 1, inspired by Alan Feuer's great C Puzzle Book, illustrates the kind of complex pointer expression you will want to be able to handle, if not with great ease, at least with the certainty that you are approaching the problem correctly. At the end of this two-part series, I will solve this puzzle, using the techniques described here.

Expressions like ++*--*++pppp[0] +5 arise with great infrequency in the real world! Nevertheless, the ability to decipher such an expression is a fundamental part of fluency in C. The most important advantage of fluency is the freedom to think more about the real problem at hand, and less about the programming language.

The following analysis starts simply enough, but it quickly jumps to more complicated levels based on the fundamental premise. I call the fundamental premise, the Campleat Pointer, perhaps because the great Angling classic really does represent the point I am trying to make, or perhaps, as my wife suggests, because I would rather be trout fishing than practically anything else.

The Compleat Pointer

First, you must start off with a fundamental question. What exactly is a pointer?

In English, a "pointer" is an indicator. It directs you toward something. An arrow indicating a location, or a hot tip about a certain opportunity, a pointer always directs your attention to something besides itself. The same is true in C and C++. Calling something a pointer is a poetic way of saying that you can use this thing to find something else. The something else is the thing "pointed at." Imagine a line pointing from the first thing to the second. In reality, of course, there is no line, dotted or otherwise, connecting the two objects. The lines drawn in diagrams are quite imaginary.

Key Fact #1 — A pointer is a variable containing an address.

The real connection a pointer makes is that the content of the pointer is the address of the object pointed at. All the power and subtlety of pointers comes out of this fundamental connection. Pointers are variables, which store the addresses of other programming objects. Remember that an object in Standard C is simply a region of storage. I'll use the term class object to refer to instances of classes in C++ or other object-oriented systems.

Key Fact #2 — A pointer always "knows" the type of thing it addresses. It can be properly used only to access something of the correct type.

Computer memory is organized into one or more ranges of addresses. Almost every object in a program has a unique memory address. The address tells where in the computer's memory the object is located. Since a pointer holds the address of an object, the pointer can be used as a tool for accessing the object pointed at. This is the heart of the pointer concept.

Yet all addresses are not the same, at least not according to a pointer. Each pointer has a built-in sense of the type of object stored at the address which the pointer contains. This is the second crucial observation.

Put more formally, a pointer always points to an object of some particular type. The type may be one of the built-in types, such as char, short, int, long, float, or double, or any one of the possible derived types, including arrays, functions, structs, unions, and even other pointers. C++ adds classes to Standard C, allowing C++ pointers to point at class objects, or even at class-object members, though the latter are implemented rather differently than typical C pointers. Even the special case pointer to void points at a specific type, and such a pointer has its own set of resources and limitations.

Every pointer value is thus really a package, a collection of two specific pieces of information: an address and a type pointed at. One might think of this combination of information about where something is located, as well as what is located there, as an "access cookie." The word "cookie" means a package or collection of ingredients mixed and cooked together properly. Since pointers are almost always used to access objects, the term access cookie reminds you that it always takes both ingredients, the address and the type, to properly access an object.

Key Fact #3 — Pointer values are address/type pairs, just like pointer variables. However, pointer values are not storable Ivalues.

Next, you should understand the important distinction between pointer variables and pointer values. Pointer-like values often exist which are not contained in any specific variable. Simple pointer expressions like p + 1 evaluate to these pointer-like values, without ever being stored in any specific variable.

In other words, if p is the name of a pointer variable, then p + 1 is a pointer value, but not a pointer variable. Why? Because the expression p + 1 gives us an address, and it has an associated type, exactly as if it were a pointer variable, yet there is no variable that is actually storing the value p + 1. Pointer variables always store pointer values, but pointer values are not always stored in pointer variables. Both C and C++ call objects with storable addresses, lvalues, though they disagree in some surprising ways as to exactly what an lvalue is.

In most cases, the same rules apply to pointer variables and pointer values. Both variables and values can have the indirection operator (*) applied to them. This is called dereferencing the pointer. But some operators, like the address-of operator (&) can only be applied to pointer variables, not to pointer values. Strictly speaking, I ought to reserve the word pointer for pointer variables, and always refer to pointer values explicitly as address/type values or with some other term. For practical purposes however, I will sometimes use the word pointer for both variables and values. Whenever the distinction is critical, however, I'll use the specifically correct term.

To review, the absolutely essential pointer principles are:

Essential Programming Concepts

There are two essential programming concepts that will be of real benefit to those studying pointers in C. The first I call The Three Attributes, and the second The Ladder of Indirection. If you understand the Three Attributes you can understand the Ladder of Indirection, and mastering the Ladder is the heart of playing Pointer Dominos. Knowing how to play Pointer Dominos is the key to mastering pointers in C.

Key Fact #4 — Every pointer has three fundamental attributes. These attributes are the location, the contents, and the indirect value of the pointer.

You know that a pointer is an address storer, that is, it contains an address. You also know the difference between pointer variables and pointer values. The Three Attributes are the attributes of a pointer variable.

The contents of a pointer is the first of three critical values which can be derived from that pointer. These three values are so critical to the proper understanding of pointers that I've named them the Three Attributes. Technically, each of these attributes is the value of an expression using the pointer. I choose to focus on three of these particular expressions, since these three yield the most critical information involved with the pointer.

The expression which will always return the contents of a pointer is simply the name of the pointer. If you have a pointer p, that address which is the current contents of the pointer is represented by the symbol p in your program.

A pointer variable has a second attribute, a second value intimately associated with that pointer. This second attribute is the location of the pointer. The location of the pointer is the place in memory where the pointer itself is stored. This location, like the contents, is an address. But the pointer's location is generally a very different address from the address stored in the pointer as the pointer's contents.

The expression which gives us the location of a pointer is composed of the pointer's name, preceded by the & or address-of operator, as in

&p /* &p is the LOCATION of the pointer */
The first two attributes, location and contents, are attributes of every variable. A simple int variable, x, has a location given by &x and a contents or current value given by x. But a pointer has a third attribute, an indirect value, the critical value that makes a pointer special to begin with.

The indirect value may also be the trickiest of the three attributes to work with and to fully understand. To find the indirect value of a pointer, you take the contents of the pointer as an address, from which you retrieve a value. The indirect value is thus the value at the contents of the pointer. The expression for the indirect value also has a type, and the type is always the same as the type part of the pointer itself. If p is a pointer to char, then the indirect value of p is a char. If p points at a double, then the indirect value of p is a double.

In a program, the expression which evaluates to the third attribute, or indirect value, is *p, as in

*p /* *p is the INDIRECT VALUE of p */
There are several good ways to think about the meaning of the term indirect value. In a sense, the contents of the pointer is the pointer's direct value. When you access a variable directly, you expect to receive the value of that variable's contents. But with a pointer, you can use this contents as an address to go look for something else. In effect, you get to the thing you are looking for indirectly, using the pointer as an intermediate stepping stone. This is where the term indirect value comes from.

These three attributes can be organized into a small but powerful set of values concerning a pointer. If you keep these three values clearly distinguished one from another in working with a pointer, you will be most likely to use the pointer correctly in your programs.

To review, the three attributes are:

Key Fact #5 — The three attributes of a pointer represent three distinct address levels. These address levels can also be called levels of indirection.

You may have noticed that although I discussed the contents of the pointer as the very first attribute, I am now showing the location as the top or first attribute. The reason why will become clear in just a moment.

Let's think about these three attributes of every pointer. What do they reveal? First of all, they show that there are levels of addressing, at least three levels represented by the three attributes. Each attribute is at a different level in the addressing scheme.

Start with p itself. p is a variable containing an address. I call p a level 1 expression. Level 1 means that p holds the address of something else. Look at what happens when you tack the ampersand onto p in front. Now you get the address of p, &p. &p is the address of something whose contents is also an address, that is, an address of an address. This I call a level 2 expression. Starting with the value &p, you can do the process of going to an address and finding a value twice.

*p is also at a different level than p. To get to *p from p you go to an address. You use up one level of addressing and go "down" to the next lower level. So if p is level 1, *p is level 0. *p is just like other variables which don't hold addresses, such as the int variable i.

To review, we have three different levels of indirection represented by the three attributes:

It's not hard to imagine the levels connected together as steps on a ladder, and that's precisely the second essential programming concept about pointers, the Ladder of Indirection.

The Ladder of Indirection

The Ladder of Indirection is really a model of how expressions change level in pointer space. In the model, pointer space is a series of discrete planes, starting at ground level 0, and connected by a "ladder," or means of ascending and descending.

Key Fact #6 — Pointer space is organized into a series of planes or levels.

Every pointer expression can be assigned to one of these planes. The plane of a pointer expression is a measure of how much potential for indirection there is in that pointer expression.

All pointers and pointer expressions can be seen as existing on particular planes in this model of pointer space. The ladder is visualized as connecting the planes from level 0 upwards to infinity. Each rung up is the next plane on the Ladder of Indirection. Each rung down is the next plane down.

Moving up the ladder of indirection involves the process known as referencing, or taking the address of something. When you take the address of something you create a reference to that thing. References to objects are exactly what gets stored in pointers. Every pointer must have at least one level of indirection associated with it, or it couldn't be called a pointer. Some pointer expressions have two or more levels of indirection associated with them. By the way, don't be fooled by C++ references. References in C++ are a distinct set of types, so-called precisely because they do indeed store an address rather than a complete object. Referencing and dereferencing in C are general terms, synonymous with taking an address of something and with going to something by means of its address.

Every time you take something's address you go up a level on the ladder. Every time you go to an address, you go down a level on the ladder. Different operators take you up and down the ladder in different ways.

Imagine the dizzying whole of pointer space, with its Ladder connecting planes ascending upward forever. Well, not really forever. Standard C says an identifier may be declared with up to 12 modifying declarators, so level 12 is the top, though some heavy duty compilers might support more. Objects and expressions seem to move around or change values on a given plane, but sometimes they leap up and jump to the next plane above. Something's address has just been taken. At other times, references snake down from one plane to the one below. An address on the higher plane has been used to descend to a particular location on the lower. Except for ground level 0, this whole organization of planes is highly symmetrical. Each level is equal to every other level. Each one has its own precise level of indirection. The critical point is that the level of indirection is an intrinsic part of the type of a pointer. A level 2 pointer, in general, should not be used where a level one pointer is required. Using pointers properly means always keeping track of the level of indirection associated with each pointer.

Level 0 is different for one particular reason. You cannot go beneath it. There is no level -1. So indirection has to stop when an expression reaches level 0. Only with pointer expressions can you ever go down a level, and you always have to stop at the bottom.

Master Pointers to Get Arrays

The heading for this section, with its fully intended pun, is designed to introduce a very powerful, but also subtle, relationship that exists in C between pointers and arrays.

While it is very true that understanding pointers fully might well lead to a raise in pay, at least for a professional programmer, the real issue here is that arrays in C are much more closely related to pointers than might be apparent at first glance. One of the deeper elegances of C concerns this special relationship between pointers and arrays. Incidentally, some have considered this elegance a weakness in certain contexts.

Key Fact #7 — The name of an array usually behaves as if the array name were a pointer value.

Why does an array name in a C expression often behave like a pointer value? The answer is simple, a matter of formal definition, built right into the fundamentals of C. An array name used in a program is really an expression in its own right. When the translator comes upon an array name, the translator will evaluate the array name expression according to the standard rules for expression evaluation. In almost every context, the array-name expression will evaluate to an address. What address? The address of the data actually stored in the first element of the array! Since arrays in C are indexed starting with 0, I call this address the address of the "zeroth" element of the array.

Key Fact #8 — The name of an array, in almost every context, evaluates to the address of the array's own "zeroth" element.

The reason for making such a hedged statement is the desire to avoid a common misunderstanding, usually stated something like "an array name is a pointer." This apparently reasonable statement is in fact quite false. An array never becomes a pointer and a pointer is not the same type as an array. What is true is that array names act like pointer values is nearly every context. But not always. An array name as the operand of the sizeof operator evaluates to the size of the entire array, not the size of a pointer, just one example of an array name not behaving like a pointer.

The [] operator, usually thought of as being related to arrays, is also a dereferencing operator. p[n] lives on the plane below p. To see that this is the case consider the simple array declaration

int arr[10];
What level does the expression arr have in most contexts? arr is a level-one expression, evaluating to the address of the zeroth element of arr, in virtually every context. arr behaves in this regard like a pointer to int, though you must be careful not to say that an array name is a pointer. Pointers are modifiable lvalues, array names are non-modifiable array-name lvalues, not quite the same thing!

In any event, arr will typically behave like a level-one value. What about arr[0]? arr[0] is clearly a level 0 value. arr[0] represents the actual data in the first element of the arr array. So the subscript brings you down one level of indirection, just as the * did in a dereference.

Summary

In this installment, I have defined the Three Attributes and the Ladder of Indirection, and discussed the role of arrays. In the next installment, I will teach you the game of Pointer Dominos. This is a game which I made up in the process of teaching C classes in the early 1980's. The essential notion here is that working with pointers is as simple as playing dominos. There are only a small number of moves, and the moves are always played in a particular order.

The rules of pointer dominos, and the solution to the puzzle in Listing 1 will be described in Part 2 of "Pointer Power in C and C++," appearing in next month's C Users Journal.