In c what is Array?

Answer 1

In all programming languages an array is an aggregate of data elements of the same type allocated within a contiguous memory allocation. That is, it is the fundamental means of representing a sequence of variables in memory.

For a type, T, T[size] is the type "array of size elements of type T".

Unlike normal variables which have both a name and an identity (a memory address that can be referred to by name), the elements of an array are anonymous; they have no individual names, but they do have identity. The elements within the array are indexed from 0 to size-1 and we can use this index to obtain the identity of each individual element:

int i[3]; /* an array of 3 ints identified as i[0], i[1] and i[2]. */

float f[4]; /* an array of 4 floats identified as f[0], f[1], f[2] and f[3]. */

Note that f is a name but f[x] is not; f[x] is merely a reference to a memory address, an identity. That is, the address of f plus offset x. f[2] is the same as saying address of f + 2 elements, which returns the address of the third element.

All offsets are the same length because each element is of the same type and are therefore the same size. Thus the length of an offset is determined by the size of the array's type. So if f is an array of type float, each offset is sizeof(float) bytes in length. We don't actually need to know the length of each element because the compiler already knows the length of every type and can work out how many bytes each element occupies. However, behind the scenes, f[2] really means address of f + (2 * sizeof (float)) bytes.

The index operator [] provides the most convenient method of accessing individual elements in an array. However, it is important that we do not attempt to access elements outside the range of an array:

float f[4]; /* index range: 0 to 3 inclusive */

f[4] = 3.14; /* f[4] is outwith the valid range */

The above code will result in undefined behaviour because the memory address identified as f[4] does not belong to the array and may not even belong to our program. The above is a common mistake because it is easy to forget that all arrays have zero-based indices; the first element is always identified as f[0], not f[1].

Arrays can be allocated statically (in the program's data segment), on the program stack or on the heap (free store):

int a[10]; /* static array */

void f()

{

int b[20]; /* stack array */

int* p;

p = malloc (30 * sizeof (int)); /* heap array */

free p;

}

In the above example, array a[] exists for the entire duration the program is running while arrays b[] and p[] exist only while function f is in scope.

Arrays allocated statically or upon the stack must be fixed size (constant size). Heap arrays can either be fixed-size or variable-size. Fixed-size arrays are easier to work with because the array bounds can be declared as constants. Variable-size arrays require us to maintain a separate variable to keep track of the current array bound.

There is no built-in copy or assignment operation for arrays, we can only copy or assign individual elements using built-in operations. In order to copy an array, the destination array must have sufficient elements to accommodate the elements we wish to copy. We can then copy those elements using a memory copy operation of the required size, thus copying several contiguous elements at once.

Arrays offer the most compact method of storing data because we do not need to maintain any "links" between one element and another as we would with a linked-list structure. The index operator also allows us to randomly access any element in an array in constant time. However, arrays are best suited to data where the number of elements is fixed.

If the number of elements changes, we must allocate the array on the heap and must reallocate the entire array whenever we need to make room for more elements. This means the array may be copied to new memory during the reallocation, which can be inefficient. Ideally we want to minimise the number of copies we make, thus it's better to "reserve" more memory than we actually need each time we reallocate. Often programmers will simply double the size upon each reallocation, however this can waste a lot of memory. A more realistic size is closer to 1.6 of the current size. Reserving memory means that some elements will be unused, so as well as keeping track of the array size we must also keep track of the number of used elements. We should also provide a means of shrinking an array whenever it reaches a certain threshold, so that we do not waste memory unnecessarily.

If our array is constantly changing size, then it may be more efficient to use another structure such as a linked list. However, when we do that we sacrifice constant time random access which is the major benefit of an array.

Multi-dimensional arrays are represented as an array of arrays. That is, each element within the array is itself an array. Fixed-size multi-dimensional arrays are the easiest to represent because the dimensions are fixed and the index operator allows us to specify the size in each dimension. Thus if we have an array of 50 integers that we want to represent as a table of 10 rows of 5 integers each, we can use the following declaration:

int i[10][5];

This creates a one-dimensional array of 10 elements where each element is a one-dimensional array of 5 integers. The memory is allocated contiguously, so it's really no different to:

int i[50];

The only real difference is that we don't need to calculate the start address of each row. That is, i[x] will return the address of the row at offset x while i[x][y] will return the address of the integer at offset i[x] + y.

Variable-size multi-dimensional arrays are somewhat trickier to implement. Here we have a number of choices. We can either allocate the entire array contiguously and use simple pointer arithmetic to determine the start address of each array with the array, or we can divide the array into separately allocated arrays along with a separate array of pointers to keep track of the start addresses for each of those arrays. The latter method uses more memory, but has the advantage in that each of the individual arrays need not be the same size.

An array of strings is an example of a two-dimensional variable-size array because each string is an array of char of variable length, and the array of strings is simply an array of char pointers, one for each string. The strings need not be allocated contiguously with each other, but each individual string must be contiguous within itself. This has the advantage in that each string can be deallocated and reallocated individually without affecting any of the other strings in the array. And if we need to increase the number of strings, we simply reallocate the array holding the char pointers, the currently allocated strings are left unaffected.

Whenever we use an array of pointers, p, the notation p[x] does not return the identity of the pointer at p + x, rather it returns the identity of that pointer's value. In other words, the pointer identified by address p + x is automatically dereferenced thus we obtain the start address of the array being pointed at by p[x]. This is extremely convenient because, even when a multi-dimensional array is allocated non-contiguously, we can still use the exact same notation we would if it were contiguously allocated.

In the following example, we first instantiate a fixed-size multi-dimensional array of 10 x 5 elements within contiguous memory and assign some values to each element. Then we instantiate the same array using 10 separate arrays of 5 elements each and then copy from one to the other.

Note the assignment statement used during the copy: p[row][col] = i[row][col]. Individual elements in both arrays are accessed with exactly the same notation using the index operator.

Note also that dynamic arrays must be released as soon as we are finished with them. It is not necessary to release individual elements in the reverse order they were created (as is done in this example), however each dimension must be released in the reverse order it was established. Thus we must release each row before we release the array itself.

/* array dimensions */

const int rows=10;

const int cols=5;

/* variables */

int row, col;

/* fixed-size array */

int i[10][5];

/* assign a value to each of the 50 integers */

for (row=0; row<rows; ++row)

{

for (col=0; col<cols; ++col)

{

i[row][col] = row * col;

}

}

/* variable-size array */

int** p;

/* allocate array of 10 pointer to int types */

p = malloc (rows * sizeof (int*));

/* allocate an array of 5 integers to each pointer in p[] */

for (row=0; row<rows; ++row)

{

p[row] = malloc (cols * sizeof (int));

}

/* copy elements from i to p */

for (row=0; row<rows; ++row)

{

for (col=0; col<cols; ++col)

{

p[row][col] = i[row][col];

}

}

/* deallocate (in reverse order of allocation) */

for (row=0; row<rows; ++row)

{

free (p[rows-row-1]);

}

free (p);