With arrays, why is it the case that a[5] == 5[a]?

As Joel points out in Stack Overflow podcast #34, in C Programming Language (aka: K & R), there is mention of this property of arrays in C: a[5] == 5[a]

Joel says that it's because of pointer arithmetic but I still don't understand. Why does a[5] == 5[a]?

Solution 1:

The C standard defines the [] operator as follows:

a[b] == *(a + b)

Therefore a[5] will evaluate to:

*(a + 5)

and 5[a] will evaluate to:

*(5 + a)

a is a pointer to the first element of the array. a[5] is the value that's 5 elements further from a, which is the same as *(a + 5), and from elementary school math we know those are equal (addition is commutative).

Solution 2:

Because array access is defined in terms of pointers. a[i] is defined to mean *(a + i), which is commutative.

Solution 3:

I think something is being missed by the other answers.

Yes, p[i] is by definition equivalent to *(p+i), which (because addition is commutative) is equivalent to *(i+p), which (again, by the definition of the [] operator) is equivalent to i[p].

(And in array[i], the array name is implicitly converted to a pointer to the array's first element.)

But the commutativity of addition is not all that obvious in this case.

When both operands are of the same type, or even of different numeric types that are promoted to a common type, commutativity makes perfect sense: x + y == y + x.

But in this case we're talking specifically about pointer arithmetic, where one operand is a pointer and the other is an integer. (Integer + integer is a different operation, and pointer + pointer is nonsense.)

The C standard's description of the + operator (N1570 6.5.6) says:

For addition, either both operands shall have arithmetic type, or one operand shall be a pointer to a complete object type and the other shall have integer type.

It could just as easily have said:

For addition, either both operands shall have arithmetic type, or the left operand shall be a pointer to a complete object type and the right operand shall have integer type.

in which case both i + p and i[p] would be illegal.

In C++ terms, we really have two sets of overloaded + operators, which can be loosely described as:

pointer operator+(pointer p, integer i);

and

pointer operator+(integer i, pointer p);

of which only the first is really necessary.

So why is it this way?

C++ inherited this definition from C, which got it from B (the commutativity of array indexing is explicitly mentioned in the 1972 Users' Reference to B), which got it from BCPL (manual dated 1967), which may well have gotten it from even earlier languages (CPL? Algol?).

So the idea that array indexing is defined in terms of addition, and that addition, even of a pointer and an integer, is commutative, goes back many decades, to C's ancestor languages.

Those languages were much less strongly typed than modern C is. In particular, the distinction between pointers and integers was often ignored. (Early C programmers sometimes used pointers as unsigned integers, before the unsigned keyword was added to the language.) So the idea of making addition non-commutative because the operands are of different types probably wouldn't have occurred to the designers of those languages. If a user wanted to add two "things", whether those "things" are integers, pointers, or something else, it wasn't up to the language to prevent it.

And over the years, any change to that rule would have broken existing code (though the 1989 ANSI C standard might have been a good opportunity).

Changing C and/or C++ to require putting the pointer on the left and the integer on the right might break some existing code, but there would be no loss of real expressive power.

So now we have arr[3] and 3[arr] meaning exactly the same thing, though the latter form should never appear outside the IOCCC.

Solution 4:

And, of course

 ("ABCD"[2] == 2["ABCD"]) && (2["ABCD"] == 'C') && ("ABCD"[2] == 'C')

The main reason for this was that back in the 70's when C was designed, computers didn't have much memory (64KB was a lot), so the C compiler didn't do much syntax checking. Hence "X[Y]" was rather blindly translated into "*(X+Y)"

This also explains the "+=" and "++" syntaxes. Everything in the form "A = B + C" had the same compiled form. But, if B was the same object as A, then an assembly level optimization was available. But the compiler wasn't bright enough to recognize it, so the developer had to (A += C). Similarly, if C was 1, a different assembly level optimization was available, and again the developer had to make it explicit, because the compiler didn't recognize it. (More recently compilers do, so those syntaxes are largely unnecessary these days)

Solution 5:

One thing no-one seems to have mentioned about Dinah's problem with sizeof:

You can only add an integer to a pointer, you can't add two pointers together. That way when adding a pointer to an integer, or an integer to a pointer, the compiler always knows which bit has a size that needs to be taken into account.