Arrays are used to store a sequence of homogeneous or covariant data types in contiguous memory.

Arrays may be allocated statically, on the stack or on the heap. Static arrays must be fixed-length however arrays on the stack or heap may be either fixed-length or variable-length:

int a[10]; /* static array of 10 elements (fixed-length) */

void f (const unsigned int x) {

int b[10]; /* stack array of 10 elements (fixed-length) */

int c[x]; /* stack array of x elements (fixed-length) */

int * d = malloc (10 * sizeof(int)); /* heap array of (initially) 10 elements (variable-length) */

int * e = malloc (x * sizeof(int)); /* heap array of (initially) x elements (variable-length) */

}

Note that pointers d and e are both allocated on the stack, but the arrays they point to are allocated on the heap.

The elements within an array are anonymous (unlike primitive variables, they have no names associated with them), however we can refer to them by their individual addresses. The name of the array (or a pointer to the array) serves as a reference to the start of the array, thus all elements are referenced via a zero-based offset from this address (where the first element is at offset 0). Given that every element is the same length (in bytes), it is trivial to calculate the address of any element within the array given that element's zero-based index (where the first element is at index 0). However, the array suffix operator [] provides a more convenient notation for the programmer without the need to use pointer arithmetic.

void f (void) {

int x = a[5]; /* store the value of the 6th element of a in x */

}

An array's name (if it has one) implicitly converts to a pointer when passed to a function. However, a function cannot determine the length of an array from a pointer alone, you must also pass the length of the array via a separate argument:

void f(const int const * a, const unsigned int n) {

/* a is a constant pointer to an array of n constant integers */

}

To avoid buffer overflows, it is important that the programmer keep track of all array lengths independently of the arrays themselves. For fixed-length arrays this is typically achieved through constants while variable-length arrays use variables. Every time an array is reallocated, the variable indicating its length must be updated according to the new length.

In order to maintain the relationship between an array and its length, we may use a data structure:

typedef struct my_array {

int* the_array;

unsigned int length;

};

Multi-dimensional arrays are represented as arrays of arrays:

int x[5][10];

Here, x is an array of 5 elements where each element is itself an array of 10 integers. We can think of this array as being a table of 5 rows and 10 columns holding 50 integers in total (just as if we'd declared the array int x[50]). The difference is that when we access element x[3], say, we are actually referring to an array of 10 integers rather than just a single integer. Mapping the integers multi-dimensionally allows us to access individual elements by row and column indices, just as we would a spreadsheet, grid or matrix.

Multi-dimensional variable-length arrays are a bit more complex than their fixed-length counterparts, but they are more flexible in that the inner arrays need not be the same length. For instance, an array of variable length strings is effectively a two-dimensional array because the inner arrays are null-terminated character sequences:

char* string[10];

Here, string is a contiguous array of 10 pointers to char, but each pointer can refer to any character array no matter where it is allocated. Thus string[4] would refer to the fifth character array while string[4][2] would refer to the third character in that array. Note that when we define multi-dimensional arrays non-contiguously, each individual array must be contiguous within itself and each array of pointers adds another level of indirection. Thus if we wanted a variable-length array of variable length strings, we must use a pointer to pointer to char:

char** string;

That is, string can now be used to point to a contiguous array of pointers to char.

Other than the physical limitations of the hardware, there is no limit to the number of dimensions we may define. A three-dimensional array can be imagined as being an array of grids or a grid of tables or as a cube (depending on what it is the array actually represents). We can extend this approach into four dimensions and beyond, such that a four-dimensional array may be thought of as being an array of cubes, or a table of tables, or a cube of arrays, and so on.

Resources

Top Categories

Product

Company