Pointers, Part 2: Pointers and Arrays
Chuck Allison is a regular columnist with CUJ and a software architect for the Family History Department of the Church of Jesus Christ of Latter Day Saints Church Headquarters in Salt Lake City. He has a B.S. and M.S. in mathematics, has been programming since 1975, and has been teaching and developing in C Since 1984. His current interest is object-oriented technology and education. He is a member of X3J16, the ANSI C++ Standards Committee. Chuck can be reached on the Internet at [email protected], or at (801)240-4510.
In last month's capsule I introduced the fundamentals of pointers in C: 1) a pointer is simply an object that holds the address of another object, and 2) when you define a pointer, you must also define what type of object it targets (this allows sensible pointer arithmetic). In spite of such simple rules, nothing in C seems to be as confusing and difficult to master as the proper use of pointers. Having taught C to more than 200 students over the past nine years, I have noticed that the relationship between pointers and arrays, especially multi-dimensional arrays, causes them much of the difficulty. I hope to clarify that relationship in this capsule.
Pointers and One-Dimensional Arrays
It may seem strange to say, but C does not really support arrays, at least not in the same way that it does "first-class" types such as integers or structures. Consider the following statements:
int i = 1, j;
int a[4] = {0,1,2,3}, b;
struct pair {int x; int y;};
struct pair p = {1,2}, q;
j = i; /* OK: integer assignment */
q = p; /* OK: structure assignment */
b = a; /* No can do! */
Not all operations are valid with arrays. We could do the following:
int a[4] = {0,1,2,3}, *p;
p = a; /* Stores &a[0] in p */
but it isn't a "real" assignment, because none of the data in the array is transferred from one location to another. Instead, the code copies the address of the data from one location to another.
In most contexts, the compiler interprets an array name as a pointer to its first element. The only exception is when an array name is the operand to the sizeof or & operators. You can express this principle as
a == &a[0]or equivalently as
*a == a[0]By the rules of pointer arithmetic (see last month's Code Capsule if you've forgotten them), if you add an integer i to an array name, the result is a pointer to the ith element of the array, that is,
a + i == &a[i]or, as I like to express it,
<B>Grand Pointer Principle #2: *(a + i) == a[i]</B>The program in Listing 1 illustrates these principles.
Since all array subscripting is really pointer arithmetic, you can use the expression i[a] in place of a[i]. This follows directly from the above formula:
a[i] == *(a + i) == *(i + a) == i[a]Of course, any program that uses such banalities should be shot instead of executed (to quote Andrew Koenig), and the programmer too. It is not altogether unreasonable, however, to use negative subscripts. If a pointer p traverses an array, you can retrieve the element preceding the current element, *p, with the expression p[-1], since
p[-1] == *(p - 1)Listing 2 contains an an ample mixture of pointer and array notation. It also employs a useful formula for the number of elements in an array:
size_t n = sizeof a / sizeof a[0];You can use any other valid subscript besides 0 in the divisor, but 0 is the safest since every array has a 0-th element.
A popular idiom that follows from the interaction of pointer and array notation is
strncpy(s,t,n)[n] = '\0';This idiom copies the string at t to s, guarantees no over-flow during copy, and null-terminates the destination string — all in one compact statement.
There is one other difference between pointers and array names to remember: because an array name is not a modifiable lvalue, you cannot change the address to which an array name is bound. For example:
int a[5], b[5], *p;
/* ... */
/* All the following are invalid */
a++;
a = p + 5;
b = a;
If you could make such assignments, you could easily lose track of where an array resides in memory (not a good idea!).
Exercise 1
Given the declarations
int a[] = {10,15,4,25,3,-4};
int *p = &a[2];
what is the result of each of the following expressions?
a) *(p+1) b) p[—1] c) p — a d) a[*p++] e) *(a+a[2])(Answers are at the end of the article. Don't Peek! Work them out first, please).
String Literals
String literals are arrays without names. You can find their sizeof and you can even subscript them (see Listing 3 and Listing 4) . Note that my compiler treats each occurrence of "hello" in Listing 3 as a separate object, returning a different address each time. Some compilers can "pool" equivalent string literals to save space.
Arrays as Parameters
C typically passes parameters by value, but it can't pass an array by value. Instead, C passes a pointer to the array's first element. Use of the pointer allows you to permanently change the elements of the array from within the called function — which you cannot do with parameters passed by value. In the function f in Listing 5, the address &a[0] is passed by value to the pointer b, so the expression b[i] behaves identically to the expression a[i].
Even though I defined the parameter b with array notation:
int b[]the effect would be the same as if I had written
int *bIn either case, the function cannot determine the size of the array at compile time. This explains why sizeof(b) == 2, the size of a pointer on my platform.
Pointer parameters that refer to array elements are common in text processing. Here is a function that copies one string to another (like strcpy, except it doesn't return anything):
void str_cpy(char *s1, const char *s2)
{
while (*s1++ = *s2++)
;
}
Th e while loop does not test for equality. Instead, it tests the value of s1, after the assignment, but before the increment operation on s1. (*p++ is another very common C idiom.) The loop stops after copying the terminating '\0'.
Exercise 2
The following statements modify the string s through a sequence of pointer expressions. What character is retrieved by each expression when executed in succession, and what is the final value of s?
char s[] = "desolate", *p = s;
*p++ == ?
*(p++) == ?
(*p)++ == ?
*++p == ?
*(++p) == ?
++*p == ?
++(*p) == ?
strcmp(s,?) == 0
(Thanks to Chet Small of Lincoln Laboratories for this very clever example.)
Arrays of Strings
There are two ways to implement arrays of strings in C: 1) as arrays of pointers, and 2) as two-dimensional arrays of characters. The program in Listing 6 illustrates the first approach. The memory layout looks like this:
This type of array is sometimes called a "ragged array" because the strings can be of different lengths. This scheme uses only the amount of memory required to hold the data, plus one pointer per string. The array of command-line parameters that the run-time system provides (argv[]) is a ragged array.
A disadvantage to the ragged array approach is that in most circumstances you need to dynamically allocate memory for each string. If you don't mind wasting a little bit of space, and if you know the length of the longest string you will encounter, you can use a fixed-size region of storage as a two-dimensional array of characters (one string per row). The memory layout for the array in Listing 7 is:
As the program in Listing 7 illustrates, you don't have to specify the first dimension of a multi-dimensional array if it can be inferred from the initializer.
C is somewhat unique among programming languages in that it allows you to use an array with only some of its subscripts. As the program in Listing 7 suggests, the expression array[i] is a pointer to the ith row. For the array defined as int a[2][3][4], what do you suppose a[i] represents? Or a[i][j]? Read on.
Pointers and Multi-Dimensional Arrays
Actually, there is no such thing as a multi-dimensional array in C (at least, there is no direct support for such). One usually thinks of a one-dimensional array as a vector, a 2-d array as a table (or matrix), and a 3-d array as a rectangular solid. As opposed to this geometric model, C supports the notion of "arrays of arrays." For example, if a 1-d array of integers, say
int a[4] = {0,1,2,3};
is an indexed collection of integers:
which we usually depict as a single vector:
then a 2-d array of integers, say,
int a[3][4] = {{0,1,2,3},{4,5,6,7},{8,9,0,1}};
is a collection that looks like this:
or, if you like,
which is a collection of arrays. So a is an "array of 3 arrays of 4 ints", and a[0] is one of those arrays of 4 ints. Pointer arithmetic in C is consistent with this addressing scheme. Since an array name always resolves to a pointer to its first element when used in an expression, an expression like a+1 is of type "pointer to array of 4 ints;" in this case it would point to the second row (i.e., a[1]).
The program in Listing 8 shows how to declare a pointer to an array. Such a pointer can replace the array name with no change in indexing syntax. Novices mistakenly assume that since a pointer to int can substitute for the name of an integer array,
int a[] = {0,1,2,3), *p = a;
/* ... */
P[i] = ...
a pointer to pointer to int will do the same thing for a two-dimensional array, as in:
int a[][4] = {{0,2,3,4},{4,5,6,7},{8,9,0,1}};
int **p = a; /* Suspicious pointer conversion */
/* ... */
P[i][j] = ...
By Grand Pointer Principle #2, p[i] [j] is equivalent to:
*(p[i] + jwhich is equivalent to
*(*(p + i) + j)Since p is a pointer to pointer to int, p + i advances past p by a distance equal to the size of i pointers — but we want to advance past p by i rows. Thus p must be bound to a type whose size is the size of row. To correctly define p, the programmer could use the interesting but consistent syntax:
int (*p)[4] = a;A compiler observes the following steps to evaluate the expression *(*(p + i) + j) with the correct definition of p:
1. p + i
This expression computes a pointer to the row which is i rows beyond the row targeted by p.
2. *(p + i)
This expression is that row targeted by (p + i) (which is an array).
3. Since the array *(p + i) is not the operand of a sizeof or & operation, it is immediately replaced with a pointer to its first element, namely, &a[i][0], which is a pointer to an int.
4. &a[i][0] + j
Since &a[i][0] is a pointer to an int, adding j advances it by j ints, resulting in &a[i][j].
5. *&a[i][j]
This expression is the integer a[i][j].
Table 1 summarizes this relationship between pointers and 2-d arrays. Don't let the fact that a + 1 and a[1] have the same value (0x8), tempt you to conclude that
a[i] == a + i /* not quite true */These two expressions are only equal in value, not in type, because sizeof(a+1) == 2 (a pointer), sizeof(a[1]) == 8 (an array of 4 integers).
Higher and Deeper
It naturally follows that a 3-d array is a collection of 2-d arrays. For example, for:
int a[2][3][4] = {{{0,1,2,3},{4,5,6,7},{8,9,0,1}},
{{2,3,4,5},{6,7,8,9},{0,1,2,3}}};
the memory layout is:
The First element of this array is the "2-d" array a[0] (technically, a[0] is an array of 3 arrays of 4 ints). To use a pointer compatible with the array name, a, define:
int (*p)[3][4] = a;Listing 9 has a sample program using such a pointer, and Table 2 is the 3-d analogue of Table 1.
The programs in both Listing 8 and Listing 9 show how to determine the "rank" (or dimension) of an array and all of its sub-arrays. For the 2-d array a in Listing 8, the rank is the number of rows (1-d objects) it contains, which is
sizeof a / sizeof a[0]and the rank of each row is the number of integers (0-dimensional objects) in each row of a, namely
sizeof a[0] / sizeof a[0][0]In general, if a is an n-dimensional array, then a is a collection of
sizeof a / sizeof a[0](n—1)-dimensional objects, and each (n—1)-dimensional object in a contains
sizeof a[0] / sizeof a[0][0](n—2)-dimensional objects, each of which in turn contains
sizeof a[0][0] / sizeof a[0][0][0](n—3)-dimensional objects, and so on. The number of 0-dimensional objects (e.g., integers) in each 1-dimensional object is
sizeof a[0][0]...[0] / sizeof a[0][0]...[0][0]
(n-1 subscripts) (n subscripts)
I think it's time to quit.
Exercise 3
Fill in the Array-to-Pointer conversion table below, as I did in the examples above, for the 4-dimensional array:
int a[2][3][4][5] =
{
{
{{0,1,2,3,4},{5,6,7,8,9},{0,1,2,3,4},{5,6,7,8,9}},
{{0,1,2,3,4},{5,6,7,8,9},{0,1,2,3,4},{5,6,7,8,9}},
{{0,1,2,3,4},{5,6,7,8,9},{0,1,2,3,4},{5,6,7,8,9}},
},
{
{{0,1,2,3,4},{5,6,7,8,9},{0,1,2,3,4},{5,6,7,8,9}},
{{0,1,2,3,4},{5,6,7,8,9},{0,1,2,3,4},{5,6,7,8,9}},
{{0,1,2,3,4},{5,6,7,8,9},{0,1,2,3,4},{5,6,7,8,9}},
}
};
Summary
Arrays in C differ from other data types in that they cannot be passed by value. All array operations (except the use of sizeof and &) involve pointers to the array's first element. Unless you understand this thoroughly, multi-dimensional arrays can cause you considerable confusion.
I'll finish this series on pointers next month with a discussion of pointers to functions, incomplete data types, and some examples of when you might want to use the volatile qualifier.
Answers to Exercises
1. Given the declarations
int a[] = {10,15,4,25,3,-4};
int *p = &a[2];
what is the result of each of the following expressions?
a) *(p+1) 25
b) p[-1] 15
c) p - a 2
d) a[*p++] 3
e) *(a+a[2] 3
2. The following statements modify the string s through a sequence of pointer expressions. What character is retrieved by each expression when executed in succession, and what is the final value of s?
char s[] = "desolate", *p = s;
*p++ == d
*(p++) == e
(*p)++ == s
*++p == o
*(++p) == l
++*p == m
++(*p) == n
strcmp(s,"detonate") == 0
3. See Table 3.