Rex Jaeschke is an independent computer consultant, author and seminar leader. He participates in both ANSI and ISO C Standards meetings and is editor of The Journal of C Language Translation, a quarterly publication aimed at implementors of C language translation tools. Readers are encouraged to submit column topics and suggestions to Rex at 2051 Swans Neck Way, Reston, VA 22091 or via UUCP at rex@aussie.com.
Programmers new to C and familiar with higher-level languages tend not to use arrays of pointers. Instead, they use multi-dimensional arrays. This month I'll compare the two. Each has its benefits and costs. Both can be accessed using the exact same notation. (I will primarily deal with one-dimensional arrays of pointers versus two-dimensional arrays. However, the concepts and constructs presented can easily be extended to deal with n-dimensional arrays.)
A Simple Case
First, I'll compare a two-dimensional array of int with an array of pointers to int. See Listing 1.The notation a[i][j] is intuitive — it is similar to what other languages require to access an element of a two-dimensional array. In the case of an array of pointers, I must define separate arrays to represent the five "rows," as follows:
int i0[] = { 1, 3, 5, 7}; int i1[] = { 0, 2, 4, 6}; int i2[] = {-4, -3, -2, -1}; int i3[] = {-2, 9, 12, 11}; int i4[] = {11, 13, 15, 17}; int *a[5] = {i0, i1, i2, i3, i4};From this point on, the array of pointers can also be accessed using the notation a[i][j], so the executable code can remain the same. To see why this is possible I will take a specific element, a[3][2]. In the 2D array case a[3][2] clearly is the eleent with value 12. (Don't forget that each dimension starts at element zero.)In C, any array expression can be rewritten as an equivalent pointer expression and vice versa, without exception. This is stated formally as:
a[i] = *(a + i)Using this fundamental identity, I can rewrite a 2D array expression as any of the following:
a[3][2] (a[3])[2] *((a[3]) + 2) *((*(a + 3)) + 2)a + 3 gets the address of the fourth element in a and *(a + 3) gets the value of this element. That is, * (a + 3) is equivalent to a[3]. Now a[3] is the address of the first element in i3, so by adding 2, I get the address of the third element in i3. Then by dereferencing that, I get the value of the third element, which is 12. The scaling factors of the 'Add 3' and 'Add 2' are different. In the first case, I am moving forward 3 int pointers whereas in the second, I move forward 2 ints.The fact that C permits any pointer expression to be arbitrarily subscripted to one level allows arrays of pointers to be accessed using the same notation as for multi-dimensional arrays.
If I can use the same notation, why choose one approach over the other? In the case of the 2D array, the memory allocated is contiguous. You can reliably walk through memory off the end of one row onto the next. In the pointer array, while the array of pointers and each array of ints are contiguous, their position in memory in relation to each other is undefined. They could be anywhere in memory.
The array of pointers approach takes a little more work to define. I must define each of the rows separately. Note, however, that even though the rows in the multi-dimensional array are implicitly defined as part of the whole array, they can also be directly accessed using the notation a[i]. C permits an n-dimensional array to be referenced with less than the maximum number of subscripts. So, even though the rows are not named explicitly, I can still access them. a[2] is an expression that designates the whole of row 3. (If you aren't convinced, try displaying sizeof(a[2]).) Of course, a[2] is converted to &a[2][0] in almost every situation it can appear, so the idea that a row is an array in its own right is not necessarily obvious.
At this stage the only significant difference between the two approaches is that the array of pointers requires more memory. Not only do I allocate space for the 20 ints, I also need space for five pointers to ints. In the 2D array only the 20 ints are stored. The pointers can be constructed implicitly using an expression. They do not exist as separate objects. Later examples will show more differences.
Arrays Of Strings
A common situation is to have an array of strings. For example, Listing 2 shows a lookup table of valid commands against which you match user input. The same effect can be achieved via a 2D array of char:
char command[] [8] = { "ADD", "DELETE", "LIST", "REPLACE" };However, there are now some interesting differences between the two approaches. Note that the strings have different lengths (as is most often the case with real commands). In the pointer array approach, memory is allocated for each command string and its corresponding trailing null character. As such, the total number of chars allocated is 4 + 7 + 5 + 8 = 24. In the 2D array case each row must have the same size by definition. That is, the array requires 4 * 8 = 32 chars. Of course, the pointer array also has an array of four pointers to char which could require another 8 or 16 (for example) bytes. As a result, the 2D array requires the same or less memory to represent. The big difference, however, is that using the pointer array approach you can effectively have what looks like a 2D array with varying length rows yet still use the familiar 2D subscript notation.Take the case of a list of commands in which a few of them are quite a bit longer then the others. In this case, the memory saved by using variable-length rows will likely more than compensate for that lost by needing a separate array of pointers. In any event, even if the space savings are minimal or non-existent, the flexibility of variable length rows may justify selecting pointer arrays over 2D arrays.
Another difference is that with the 2D array approach, you are guaranteed that the strings can be modified. This is not the case with the pointer arrays. Take a closer look at the initializer.
char *command[] = { "ADD", "DELETE", "LIST", "REPLACE" };The compiler sees four expressions in the initializer list and assumes (correctly) that the array command has four elements each of type pointer to char. Since each element is a scalar, the compiler recognizes that it must allocate space for four unnamed arrays of char, initialize them with the given text plus trailing null, take the address of the first char in each such array, and use these addresses as the initializer values for the elements in command.Standard C does not define whether string literals are stored in read/write or read-only memory and, of course, implementations vary. As a result, an expression such as
command[1][0] = 'a'may produce a fatal runtime error.Although the initializer for the 2D array version is identical, the compiler interprets it differently. For example, the initializer expression
"ADD"is treated as shorthand for
{'A', 'D', 'D', '\0'}To guarantee the strings are writable, I must define the strings as separate arrays rather than using string literals, as follows:
char cm0[] = "ADD"; char cm1[] = "DELETE"; char cm2[] = "LIST"; char cm3[] = "REPLACE"; char *command[] = {cm0, cm1, cm2, cm3};Now the compiler initializes the named arrays cm0 through cm3 (which, in the absence of const, are read/write) instead of allocating space for the strings itself.Regardless of how the array of pointers is initialized, expressions such as
*(command[1] + 4)) *(command[3] + 2)can be written using 2D array notation as follows:
command[1] [4] command[3] [2]Sharing Versus Duplication
In some applications, I may want to share a common piece of data rather than duplicate (and maintain) it in multiple places. Consider the case in which I have four commands defined. Each user has access to a subset of these commands based on some password validation. At the lowest level of privilege, a user can only read existing file records. At the next level, the user can also add new records and modify existing ones. Only at the highest level can users delete records. This can be implemented using arrays of pointers as shown in Listing 3.Since the sizes of each array are determined by the compiler based on the initializer lists, I can add new commands of any length, remove commands, and change the names of existing commands, simply by changing the initializer lists.
Each level array contains a null-terminated list of pointers into valid commands for that level. There is only one copy of the set of command names. This copy is shared by all level arrays. By creating an array of levels (called mode) I can easily use a user's access level as a subscript into mode to get at that user's command set. I used the const qualifier because in most cases the command names are unlikely to be modified at runtime.
As you might expect, I can achieve the same thing using 2D arrays.
const char *mode[][5] = { {"LIST", NULL}, {"ADD", "LIST", "REPLACE", NULL}, {"ADD", "DELETE", "LIST", "REPLACE", NULL}, };This approach requires that I duplicate the commands in each row, however. Also, to add, change, or delete a command we must deal with each copy of it. Since each row has space for five entries, I waste space on the shorter-level lists. The memory required by the approaches is similar, but the pointer array alternative provides more flexibility.
Conclusion
I have illustrated some of the tradeoffs between arrays of pointers and 2D arrays. Next month I'll continue with the comparison. In particular, I'll discuss allocation of both at runtime using malloc, and the tradeoffs of sorting lists of elements.