Saturday, October 19, 2013

Fun with arrays in C & C++ - Part2

In Part-1, we saw a couple of examples on array indexing and pointer arithmetic.

Lets dive a little deeper in to array types.

Arrays & pointers

An array is a series of contiguous values in memory and the array name gives us a handle to this list. In C and C++, a pointer refers to (or points to) another object in memory. Since arrays are guaranteed to be contiguous, if we have a pointer to the first element in the array, we can access the whole array (as long as we know how bit it is)

Assigning the address of the first element to a pointer:
int a[100];
int *p = a; //p  now points to a[0]

Here p is a pointer to int and we are simply using the array name for assignment. The array name is said to freely decay to a pointer to the object's type. i.e. if a is an array of objects of type T, then it can be seamlessly converted to a pointer to T (i.e. to a T*).

This is what happens when you pass an array's name to a function that takes a pointer as argument.
For example:
char str[] = "hello %d";
printf(str, 123);

The first argument to printf is actually a char* (well, const char* restrict, to be precise) but we're passing an array instead. This works alright without casts because the array type gets converted to pointer type.
(Note that explicitly specifying array size is optional when it is initialized to some value).

Type of an array
Since arrays get converted to pointers quite easily, people make the mistake of thinking they are the same, but they really aren't.
The type of a when declared as:
int a[100];
is:
int [100]

It gets converted to int* easily, but its native type is int[100]. In many contexts, this distinction makes quite a difference.

Multi-dimensional arrays

Consider this so called 2D array:
int a[3][5];

Most people think of it as a two dimensional array - one that has 3 rows and 5 columns. We can index all 15 elements (3x5) by using double subscripts:
a[0][0] gets us the first row, first column element and a[2][4] gets us the last row, last column element. Right?
Although the row-and-column way of thinking works, it doesn't scale well when the number of dimensions are more. With three dimensions, we can still visualize the array in 3D space but beyond that, all hell breaks loose for most people.

A more convenient way to understand multi-dimensional arrays is to think of them as array of arrays. Actually, more than being convenient, it possibly is a more correct way.
In this approach, this is how you interpret an array declaration:
1. Identify the array name
2. The number that immediately follows the array name is the array length
3. Whatever remains is the array object type
Using the above method, let's interpret:
int a[3][5];
1. The array name is: a
2. The length of the array is: 3
3. The type of each object in the array is: int[5]
Therefore: a is an array of length 3, and each element of a is an int[5]. i.e. a is an array of three arrays, each 5 int's long.
a[0] now gets the first element in the array - i.e. the first int[5]. a[1] gets us the next int[5] and a[2] the last int[5].

Pointer conversions

Continuing with the above example of int a[3][5], what should be some-type for the following assignment to work?

some-type p = a;

It is common for people to try int** p; When that doesn't work, they try to get around it by doing an explicit type-cast of a. This obviously is the wrong thing to do.

To answer the question, remember that the array name can convert to pointer to array object's type. In our example, each element in the array is of type int[5]. So a should seamlessly convert to pointer to int[5]. Right?
How do we declare a 'pointer to int[5]'? Here it is:

int (*p)[5];
p = a;

The parentheses around 'p' is needed as without it, the declarion would read:
int *p[5];
which declares an array of pointers (to int) rather than a pointer to an array.

some-type p = a[1];

What is some-type? Again, we know that a[1] has type int[5]. So p should also have the same type, right? However, int[5] is an array type and C (or C++) doesn't allow arrays to be assigned to each other. So p couldn't be an int[5]. But it can be something that an int[5] gets freely converted to. Using the knowledge that an array type can convert to a pointer to object type, it must be an int*.

int *p = a[1];
*p     = 5;    //writes to a[1][0]
p[2]   = 9;    //writes to a[1][2]

The advantage of this method is that it easily scales to higher dimensions.

Example:
int a[3][5][9];

a is an array of length 3, each element of which is an int[5][9].

Some sample pointer conversions follow:

int (*p1)[5][9] = a;
int (*p2)[9]    = a[0];
int *p3         = a[0][0];
int x           = a[0][0][0];

a[0][0][0]      = 5;
p2              = p1[0];
p3              = p2[0];

x               = p3[0]; //x becomes 5

Summary

• Be aware that an array and a pointer are not identical
• The type of array is different from a pointer to the element type
• Interpret a multi-dimensional array as an array of arrays
• Use the correct pointer types to access multi-dimensional arrays and avoid incorrect type-casts