Arrays

An array is a homogeneous collection of data. By homogeneous, it means that all values in the collection have the same type.

Declaration

1

<data type> <array name> [ <size> ]

1

<data type> <array name> [ <size> ] = { <expr>, <expr>, ... }

It is guaranteed that the elements of the array occupy contiguous memory locations. This will lead to a very nice retrieval and update instructions later on. Visually, we typically represent the memory as sequence of box where each box is a memory location the size of the data type and subscripted (e.g., C[0], C[1], ...) with the index.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// a[0]=54, a[1]=9, a[2]=10
int a[3] = {54, 9, 10};

// size of b is 3 with b[0]=1, b[1]=2, b[2]=3
int b[] = {1, 2, 3};

// c[0]=17, c[1]=3, c[2]=10, c[3]=0, c[4]=0
int c[5] = {17, 3, 10}; 

// size of d is 2 with d[0]=1, d[1]=2
int d[2] = {1, 2, 3};  // warning issued: excess elements

1
2
3

int e[5];
e[5] = {8, 23, 12, -3, 6}; // too late to do this;
                           // compilation error

Retrieval and Update

Once we have declared an array, we can retrieve the element as well as update¹ the element at a certain index.

1

<array name> [ <index> ];

1

<array name> [ <index> ] = <expr>;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

#include <stdio.h>
#define MAX 5

int main(void) {
  int numbers[MAX];
  int i, sum = 0;

  printf("Enter %d integers: ", MAX);
  for (i=0; i<MAX; i++) {
    scanf("%d", &numbers[i]);
  }

  for (i=0; i<MAX; i++) {
    sum += numbers[i];
  }

  printf("Sum = %d\n", sum);
  return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#include <stdio.h>
#define MAX 5

int main(void) {
  int numbers[MAX] = {4,12,-3,7,6};
  int i, sum = 0;

  for (i=0; i<MAX; i++) {
    sum += numbers[i];
  }

  printf("Sum = %d\n", sum);
  return 0;
}

1
2
3
4
5

#define N 10
int source[N] = { 10, 20, 30, 40, 50 };
int dest[N];
dest = source;  // illegal!
                // We cannot assign to the array (i.e., `<array name> = <expr>;`)!

Arrays and Pointers

So far, the syntax for array retrieval and update is the same as in other programming languages. What sets C array aparts from other programming languages is that there is a correspondence between the array and pointers. The correspondence can be summarised as the following:

To put it as a code, we can write it as:

(arr == &arr[0]) == true;

Of course, we cannot simply state such correspondence without proof.

1
2
3
4
5
6
7

int a[3] = {1, 2, 3};
printf("a = %p\n", a);
printf("&a[0] = %p\n", &a[0]);
printf("&a[1] = %p\n", &a[1]);
printf("&a[2] = %p\n", &a[2]);
printf("(a == &a[0]) = %d\n", a == &a[0]); // Print Boolean as int
printf("(a == &a) = %d\n", a == &a);       // This is uncommon and may be compiler specific

This correspondence hides a very important implication. Some of these implications are rather weird, but they are a logical implication. It is best if you go through the following parts slowly.

Retrieval ≈ Dereferencing

Since "The name of the array corresponds to the address of the first element", as a logical conclusion, the following code:

*arr

Retrieves the first element of the array arr. And we know that the first element is at index 0. We can incorporate this information as a shift from first address since we also know that "the elements of the array occupy contiguous memory locations".

*(arr + 0)

Now, we can see how a retrieval of any index can be mapped into a dereferencing operation with shifts. Given an index idx, we can also retrieve the element via:

*(arr + idx)

As such, we can summarise this as:

1
2
3
4

   arr[idx]
=> *(arr + idx)  // by dereferencing
=> *(idx + arr)  // by commutativity
=> idx[arr]

1
2

int arr[3] = {1, 2, 3};
printf("%d\n", 1[arr]); // equivalent to arr[1]

This simple pointer arithmetic is the reason why array access is so fast. Coupled with the fact that we do not check whether the index is out of bound, this operation is ultra fast and pretty much unsafe. The job of checking if the index is out of bound is delegated to you as the programmer.

Array Variable ≉ Variable

Recall that each variable has four attributes: name, type, address and value. Array variable clearly has name and type. However, because "The name of the array corresponds to the address of the first element" and that the name is how we retrieve a value for an array, we have to accept the conclusion that an array variable is not a usual variable.

In particular, the address and the value of an array variable are always the same. Looking at it through the box-and-arrow diagram below, the correct visual representation of an array should the one on the top instead of the bottom.

In the correct visualisation, there is no memory allocated for the array variable. This is the reason why there is no address corresponding to the name. In the incorrect visualisation, the box for a assumes that it has a separate address from a[0]. As such, the name a is treated by the compiler to be a placeholder for the address of its first element. However, this only happens in the function where the array is declared. As you will see later when we pass an array into a function, this does not happen for function parameters.

Although this may seem weird, it actually explains why you cannot assign to an array variable. How can you when there is no variable to store such value! What you can do instead is to update the elements of the array as exemplified below:

1
2
3
4
5
6
7

#define N 10
int source[N] = { 10, 20, 30, 40, 50 };
int dest[N];
int i;
for (i = 0; i < N; i++) {
  dest[i] = source[i];
}

Arrays and Functions

For a function to accept an array, we simply have to specify it in the function prototype. Let's consider the array summation code we have from before. The prototype should be one of the following:

1
2

int sumArray(int[], int);
int sumArray(int arr[], int size);

We can now write the function as in the example below:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <stdio.h>

int sumArray(int [], int);

int main(void) {
  int val[6] = {44, 9, 17, -4, 22};
  printf("Sum = %d\n", sumArray(val, 6));
  return 0;
}

int sumArray(int arr[], int size) {
  int i, sum=0;

  for (i=0; i<size; i++) {
    sum += arr[i];
  }
  return sum;
}

When you run the code, the box-and-arrow diagram would look something like the image on the right. Do note that since the variable arr is a parameter in the function sumArray, we have an actual variable storing the value! The value here is still the starting address of the array. Hence, you see that it now truly behaves like a pointer.

1

int sumArray(int arr[8], int size) { ... }

By the arrays and pointers correspondence above, we can have an alternate definition to the function using pointers. In fact, you will see that the function body will remain the same while the function prototype will change.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <stdio.h>

int sumArray(int*, int);

int main(void) {
  int val[6] = {44, 9, 17, -4, 22};
  printf("Sum = %d\n", sumArray(val, 6));
  return 0;
}

int sumArray(int *arr, int size) {
  int i, sum=0;

  for (i=0; i<size; i++) {
    sum += arr[i];
  }
  return sum;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

double sum_of_square(double[], int); // prototype
:
double sum_of_square(double arr[], int size) {
  int i;
  double sum = 0.0;
  for(i=0; i<size; i++) {
    sum += (arr[i] * arr[i]);
  }
  return sum;
}

We have learnt that for a function to modify a variable (e.g., v) outside the function, the caller has to pass the address of the variable (e.g., &v) into the function. What about an array? By the arrays and pointers correspondence, the value of the address itself is already the address. As such, there is no need to pass the address explicitly into the function.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <stdio.h>

void modifyArray(float [], int);
void printArray(float [], int);

int main(void) {
  float num[4] = {3.1, 5.9, -2.1, 8.8};
  modifyArray(num, 4);
  printArray(num, 4);
  return 0;
}

void modifyArray(float arr[], int size) {
  int i;
  for (i=0; i<size; i++) {
    arr[i] *= 2;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

void abs_array(int[], int); // prototype
:
void abs_array(int arr[], int size) {
  int i;
  for(i=0; i<size; i++) {
    if(arr[i] < 0) {
      arr[i] = -arr[i]; // or abs(arr[i]) if you include <math.h>
    }
  }
}

Why Pointers?

Let's look at a possible reason why the name of the array is treated as the pointer to the first element. Here, we will use a numerical argument. Do not worry too much if you cannot follow the computation closely.

Consider an array of int with 1 billion element. Since each int has a size of 4 bytes, the total size of:

4 × 1,000,000,000 = 4,000,000,000 bytes ≈ 4GB

This array has an enormous size of 4GB! That's roughly the size of the RAM of a common laptop. So the array already takes up the entire RAM.

Now consider if calling a function actually copies the array instead just the pointer. It means we now have to be able to store twice the size of the array. That equates to 8GB! Clearly, that's larger than what most common laptops would have.

Even worse, imagine if the function then calls another function (or even recursion). The amount of memory needed is going to be unreasonably large. To remedy this, the convention is to simply pass the pointer to the first element. As a problematic side-effect, the function may modify the content of the array. This means that it is now the responsibility of the programmers to avoid this.