Wednesday, October 16, 2013

Fun with arrays in C & C++ - Part1

I was explaining some stuff about arrays and pointers to a colleague and thought I should do a post about this. So here goes..

Declare 'a' as an array of 100 int objects:
int a[100];

Set the 10th element to the value 1000:
a[9] = 1000;

The square brackets we used in the above expression is called the subscript operator. We use the index value 9 to access the 10th element because arrays in C and C++ are indexed from 0.

So far so good. Now, what if that statement is slightly modified to:
9[a] = 1000;

If that looks weird and possibly wrong to you, be assured that it is perfectly legal C/C++ code! Moreover, it is identical to the statement: a[9] = 1000.
If this is news to you, then you need to read on..

The subscript operator

The subscript operator works like this:
The expression E1[E2] is equivalent to *(E1+E2); where E1 and E2 are expressions themselves. i.e.

E1[E2] = *(E1+E2) = *(E2+E1) = E2[E1]

(keep in mind that we've not yet discussed operator overloading in C++, so the above explanation involving symmetry of + operator remains valid for basic data types)

That explains why:
a[9] = *(a+9) = *(9+a) = 9[a]

For E1[E2] to work, (E1+E2) should have an address type so that the dereferencing operator * can be applied to it. That requires one of E1 & E2 to be of pointer type and the other be of integral type.

Pointer Arithmetic

The result of adding an integer 'n' to a pointer is an address that is 'n' objects (and not bytes) away from the original address; but only if the original address and the resulting address are in the same array.

For the example array declared above, the expression (a+99) yields a pointer to the last element of the array: a[99]. But it is illegal to evaluate (a+200) since the array is not large enough for the resulting address to be valid. Evaluating such an expression leads to undefined behaviour (demons flying out of your nose and things like that). One subtle exception is that you're allowed to evaluate such expressions if the addresses involved point to one past the last element of the array. i.e. it is OK to do (a+100) even though a[100] is invalid. However, you are not allowed to dereference such an address and that is why evaluating a[100] is not legal (that involves applying * to the address one past the last element).

Another side effect of the definition of pointer arithmetic is that you can add integer values only to pointers that point to elements in an array. Other expressions will compile fine (since the compiler does not have any mechanism to determine where the pointer is going to point to at runtime) but result in undefined behaviour.

Note that we said objects and not bytes in the definition of pointer addition. Adding an integer value to an address always advances that address by that many elements, irrespective of the size of one element. On a 32-bit machine where int is 4 bytes long, adding 10 to an int* actually advances it by 40 bytes. Adding the same value to a double* will advance it by 80 bytes since a double is 64-bits wide. That is why a[10] which is *(a+10) always gets the 10th element in the array, irrespective of the type of elements in the array.

The result of subtracting an integer from a pointer works in a similar way. Both the operand address and the resulting address must be within the same array (or at most one past the last element of an array).

Unlike addition, you are allowed to subtract two pointers. This works as long as both are pointers to elements (or one past the last element) in the same array. The result is an integer and is equal to the number of elements between the two addresses.
i.e. (a+50) - (a+10) yields 40.

  • a[b] = *(a+b) = *(b+a) = b[a]
  • You can add or subtract an integer to/from a pointer to get a pointer as result
  • But you can't add two pointers since that doesn't make sense
  • But you can subtract two pointers to get an integer result
  • In all pointer arithmetic, the operand address and the resulting address must point to elements within the same array or at most one past the last element of an array
  • (a+n) gets you the address of a[n]. i.e. it is equivalent to &a[n].

Food for thought

What does the following expression mean?