How is an index use when coding arrays?

Answer 1

An array is a single block of contiguous memory addresses divided into one or more units known as elements. The elements are implicitly indexed such that an array of nelements has a valid range of indices in the range 0 to n-1, inclusive. This is what we call a zero-based index and is the default for all built-in arrays in C.

All arrays allocated locally or statically are named arrays while all arrays allocated on the heap are anonymous arrays (you cannot name something that only exists at runtime) thus we must use a pointer variable (which may be named or anonymous depending on where it is allocated) to keep track of the start address. However, unlike a named variable where the name implicitly refers to the variable's value, an array name implicitly refers to the start address; it is a reference (an alias for an address) not a variable. The upshot is that we don't need to differentiate between a named array and an anonymous array; we can implicitly refer to both by their start address and they both work in exactly the same way. As a result, pointers and arrays are closely related.

In particular, the built-in array subscript operator []works exactly the same way regardless of whether we are referring to a named array or to an anonymous array via a pointer variable.

Subscripting a C-style built-in array is defined in terms of the pointer operations + (increment) and * (dereference) such that for every built-in array a and integer j within the range of a, we find the following equivalences hold true:

a[j] j[a]

Note that the + (increment) operator when applied to a memory address (whether represented by a pointer or a reference) increments the address in terms of the address type. That is, for an array of type T we would refer to it using a pointer or reference of type T* and the + operator will increment the address in units of sizeof (T) bytes. This is all done Behind the Scenes and is entirely automatic; we need only think in terms of how many elements we wish to increment by.

Given the above equivalences, we find the following equivalences also hold true:

a == a+0 = &a[0]

That is, a is a reference to the first (and only the first) element in the array. Note that the & operator is necessary because a reference is implicitly an address but a[0] is implicitly a value, therefore we need to explicitly take the address of that value.

It therefore follows that following equivalences must also hold true as well:

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

In other words, a[0] implicitly dereferences the value that is offset 0 elements from the address referred to by a.

[Note that these equivalences are fairly low-level and do not hold for C++ standard-library containers such as std::vectorand std::array].

The reason these equivalences work is simply because the array subscript operator is nothing more than eye-candy for the underlying pointer arithmetic. When we write a[j] the compiler will translate this just as if we'd actually written *(a+j). Given that a+j == j+a (built-in addition is always a transitive operation) it should now be less of a surprise to find that a[j] == j[a].

Here's a technical example to prove it really works:

char c[] = {"abcde"};

assert (c[3]==3[c]); // e.g., ('d' == 'd')