14. Array

Unit 14: Fixed-Length Array

Learning Objectives

After this unit, students should:

• understand the concept of a compound data type
• be able to manipulate arrays in C, including:
  • declaring an array of a particular type and length
  • accessing the elements within an array
• be aware that when declaring arrays, they are done so with a fixed-length
• be able to define an array as a function parameter
• be aware of the difference of pass by value and pass by reference, and that arrays, as parameters correspond to the latter, and consequently, the need to also indicate the length of an array as another parameter
• be aware that we cannot change the length of an array, only declare a new one of a different length
• be aware that we may check the length of an array using the sizeof operator
• be aware that VLA should be avoided in general, and is banned in CS1010

Your First Compound Data Type

We now look at the first of the two compound data types in C -- arrays.

An array is a data type that can hold one or more values. An array variable can only store values of the same type \(T\). We say that the array variable is an array of \(T\). For instance, we can declare a variable list to be an array of long, in which case, list can hold one or more long values.

There are three different types of arrays in C:

• A fixed-size array is an array in which the size is known during compile time.
• A variable-length array (VLA) is an array in which the size is variable (known only during run-time) and is allocated on the stack.
• A dynamically allocated array is an array in which the size is variable (known only during run-time) and is allocated on the heap.

In this unit, we will focus on fixed-size arrays. We will explain why VLA should not be used. We will leave our discussion of dynamically allocated arrays to later units.

Array Declaration

Let's first look at how we can declare an array variable. The declaration syntax for an array in C takes the following form:

long list[10];

We use the square bracket [ and ] to indicate that the variable list is an array. The number 10 indicates that marks holds 10 long values. The size of the array must be an integer value, not a variable.

Just like any other local variables, declaring an array does not uninitialized initialize it. An uninitialized array contains whatever values happened to be in the memory at that time.

Accessing the Array Elements

We can access the array elements using the index of the element, starting from 0. For instance, to initialize the first three elements of a list to 1, 2, 4, respectively, we can write:

long list[10];
list[0] = 1;
list[1] = 2;
list[2] = 4;

Same syntax, two different meanings

Beginners tend to confuse with the following:

long list[10];
list[10] = 1;

list[10] appears twice but it has two different meanings. In the first line, we are declaring an array called list of size 10. In the second line, we are using the array list, and accessing the element with index 10 (which is not valid).

Array Initialization

Initializing a large array using the method above could be tedious. Alternatively, we can initialize an array using a list of values when we declare the array.

long list[10] = {1, 2, 3, 1, 5, 10, 10, 4, 5, 3, };

If we do not specify a value during initialization, it will be set to 0 by default.

long list[10] = {1, 2, 3, 1, 5, 10, 10, 4, };
// list[8] and list[9] are both initialized to 0

Note that, after the declaration, we can no longer using this technique to reinitialized or initialize the array.

long list[10];
list = {1, 2, 3, 1, 5, 10, 10, 4, 5, 3, };  // error

Example: Array as Lookup Table

One useful application of a pre-initialized array is to use it as a lookup table. Consider the problem burger in Exercise 1, in which we need to find out how many burgers can be made given a list of ingredients. Instead of storing the number of ingredients needed for each burger in five different variables, we can put them into an array:

  long per_burger[5] = {3, 2, 1, 15, 5};

If we pass in the number of available ingredients in an array, then, we can do the following:

long count_burgers(long available[5]) {
  long per_burger[5] = {3, 2, 1, 15, 5};

  long num_burgers = LONG_MAX;

  for (long i = 0; i < 5; i += 1) {
    long k = available[i] / per_burger[i];
    if (num_burgers > k) {
      num_burgers = k;
    }
  }

  return num_burgers;
}

Passing Array as Parameter to Functions

C supports several different syntaxes for passing an array as a parameter into a function. The following function declarations mean the same thing.

a. Passing in the array with [, ] and the constant size of the array.

void foo(long list[10]) { 
  :
}

b. Passing in the array with [, ] and the variable containing the size of the array.

void foo(long len, long list[len]) { 
  :
}

c. Passing in the array with [, ]

void foo(long len, long list[]) { 
  :
}

While these three ways of declaring an array mean the same thing, in terms of human readability, Option (a) and (b) are better. Option (a) explicitly tells the reader of the code that this function expects an array called list of size 10. Option (b) explicitly tells the reader that the parameter len is the size of the array list. Option (c) does not explicitly relate len to list, and would have to depend on the comments of the code to tell the reader what len is for and how big is the array.

Option (b) is the most flexible and readable option and is the recommended way in CS1010.

To pass in an array as an argument, we just need to specify the name of the array:

long list[3] = {1, 2, 3};
foo(3, list);  // assuming `foo` is declared with Option (b)

Example: Finding Max

We can now revisit the flowchart for \(max\) and write the function in C:

long max(long length, long list[length])
{
  long max_so_far = list[0];
  for (long i = 1; i != length; i += 1) {
    if (list[i] > max_so_far) {
      max_so_far = list[i];
    }
  }
  return max_so_far;
}

Array is Passed By Reference

An array variable is treated differently than a variable of other types in C in several ways. One of these differential treatment has caught many new programmers by surprise -- it violates the pureness of functions. Whatever happens in the function no longer just stays in the function. Let's consider the following example:

void foo(long a[2]) {
  a[0] = a[1];
}

int main()
{
  long a[2] = {100, 200};
  foo(a);
  cs1010_println_long(a[0]);
  cs1010_println_long(a[1]);
}

If foo is a pure function with no side-effects, then calling foo should not change a. But if you run the code above, you will see that a[0] has changed 200!

When we pass a into foo, what do we actually push onto the stack? Unlike other variable types, we do not copy the whole array onto the stack. One reason for this is that array can be huge -- copying the whole array onto the stack for every function call with the array as an argument can be slow. Thus, in C, when an array is passed as an argument, only the memory address of the array is copied onto the stack.

The following figures illustrate this point. First, let's see how an array is laid out in the memory. When we declare an array a with two elements, the appropriate space is reserved on the stack. The elements of the array are stored consecutively in the memory. This implies, that, it is sufficient to know where the first element of the array is stored. With that memory address, we can find out where the rest of the elements in the array are, and by reading the content of that memory location, find out what their values are. This "trick" is what allows C to pass an array into a function efficiently.

When we call foo, we push the memory address of the array (i.e., of the first element of the array), on the stack. With this memory address, foo can now read the elements of the array a[0] and a[1], by accessing the memory of the array on the stack frame of main. If foo modifies to the array, then the array on the stack frame of main is updated as well.

This mechanism of passing arguments into a function is called "pass by reference", as opposed to "pass by value", in which we make a copy of the variable on the stack.

Mitigating Impurity with const

C does not give us any choice but to pass in an array by reference, making our job to reason about the behavior of our code difficult. Every time we pass an array into a function, we would have to read through the code of that function, to ensure that the array is not modified. Fortunately, C provides a mechanism to make our life better: the const keyword.

The const keyword is a qualifier that indicates that a variable is read-only, and therefore cannot be modified. A good programmer should always communicate to the reader of the code if a call-by-reference parameter will be modified or not. A better way to write our max is:

long max(const long length, const long list[len])
{
  long max_so_far = list[0];
  for (long i = 1; i != length; i += 1) {
    if (list[i] > max_so_far) {
      max_so_far = list[i];
    }
  }
  return max_so_far;
}

Here, we are communicating to whoever reading our code that length and the elements of list will not be modified anywhere in our code. Adding const will also help us to avoid bugs in case we had a typo in our code. A buggy version of max is as follows, where the programmer mixed up k and m. Since the programmer already qualified k with the const keyword, the code wouldn't compile, avoiding hours of hair-pulling debugging session.

long max(const long k, const long list[k])
{
  long m = list[0];
  for (long i = 1; i != k; i += 1) {
    if (list[i] > m) {
      k = list[i];
    }
  }
  return m;
}

Pointers

A more visual way to illustrate the fact that a memory location contains the memory address of another variable is to draw an arrow.

For this reason, in C, a variable that stores a memory address is called a pointer. We will examine this in more detail in Unit 15, but for now, we will just introduce the * notation in C. This notation is overused in C and often confuses. You have seen how * is used for multiplication. We will now use * to indicate that a variable is a pointer, by putting it in front of the name of the variable.

For instance, the line below declares a variable named address that contains the memory address of a double value.

double *addr;

Common Bug

It is possible to write as

double* addr;

too, but this is not recommended. Suppose you want to declare two addresses, you might write,

double* from_addr, to_addr;

thinking that both from_addr and to_addr are of type double*. But C treats to_addr as a double, not an address of a double! In any case, if you follow the CS1010 style, you shouldn't be declaring two variables in one line.

We can use * to dereference a pointer, but let's keep that for another day, and stick to using * in a variable declaration for now.

Array Decay

We have seen in the above, how calling foo(a) would cause the address of array a to be passed into the function foo. This behavior is rooted in the principle in how C treats the name of an array: array decay. Once you understand this concept, all the special treatments C makes to array would fall into place!

This is how array decay works. In C, the name of the variable of an array is treated differently from a non-array variable. If we declare an array

type name[num_of_elems];

then any reference to name is a synonym to the pointer to the first element of the array name. This explains why when we call foo with a, it is the address of the first element of a that is pushed onto the stack.

  long a[2] = {100, 200};
  foo(a);

This also explains why we have so many options when declaring an array as a parameter to a function. All three options below

void foo(long list[10]) { .. }
void foo(long len, long list[len]) { .. }
void foo(long len, long list[]) { .. }

are equivalent to:

void foo(long *list) { .. }

or

void foo(long len, long *list) { .. }

since we are just passing in the pointer to a long variable. Using long *x is a perfectly valid (and common) C syntax for passing in an array, it is just not as readable since we can't tell if x is meant to be just an address to a variable, or meant to be an array.

Array decay works everywhere, not just during argument passing to a function.

Suppose we write

long a[2] = {0, 1};
long b[2] = {0, 1};

if (a == b) {  // always false
  :
}

b = a; // not possible

Line 4 above is equivalent to comparing the memory addresses of the first elements of a and b and therefore is always false (since the array elements do not have the same memory address).

Line 8 above is equivalent to assigning the memory address of the first element of a into the memory address of b, which is not allowed. We cannot change the memory address of a variable since this is determined by the OS.

Returning Array from a Function

Now that we have a better understanding of how we can pass an array as a pointer into a function, let's see how we can return an array from a function. Exploiting array decay, we can return the array as a pointer from a function. Consider the square function that computes the square of every element in the list:

long* square(const long length, long list[len])
{
  for (long i = 1; i != length; i += 1) {
    list[i] = list[i] * list[i];
  }
  return list;
}

We can call the function like this:

  long a[5] = {1, 2, 3, 4, 5};
  long *a2;
  a2 = square(5, a);

If you examine the content of a2, you will find that a2 correctly contains the square of the input array a. We are, however, passing in a as a reference, the code snippet above modifies a as well! One might argue that it is pointless to return an array in this case, since we could have just defined the function as a void function:

void square(const long length, long list[len])
{
  for (long i = 1; i != length; i += 1) {
    list[i] = list[i] * list[i];
  }
}

and assign a2 to a a to a2 (if we want to store the squared list in a2).

  long a[5] = {1, 2, 3, 4, 5};
  square(5, a);
  long *a2;
  a2 = a;

Is there a way then, to keep list unmodified, while returning a "new" array? You might be tempted to do this:

long* square(const long length, const long list[len])
{
  long squared[length];
  for (long i = 1; i != length; i += 1) {
    squared[i] = list[i] * list[i];
  }
  return squared;
}

This is wrong for two reasons:

• We are declaring an array squared with a variable size on the stack. This is called a variable-length array, or VLA. This is a misnomer since once the array is created, the length is fixed. VLA is banned in CS1010. Even outside of CS1010, VLA should be used with extreme care. A VLA is allocated on the stack, which typically has very limited memory. If the stack runs out of memory, your program would crash! The situation is worse if the size of the VLA is read as an input from the users -- this implies that an external user could enter malicious input to crash your program.
• By returning squared, we are returning the memory address of an array allocated on the stack. Recall that when a function exits, the memory allocated to it on the stack is reclaimed and reused. Thus, the array squared no longer exists, and the content of the returned array is not now undetermined.

There is a right way to do this involving allocating memory on the heap, but we will explore it in a later unit. But, in short, at this point, you haven't learned enough yet to have a correct and meaningful way to return an array from a function.

Array Index Out of Bound

A common bug when we work with arrays is accessing a location beyond what is allocated to the array. Unlike other languages like Java, which checks the bound for you, C does not. So we could write the following code and it would compile perfectly.

int main()
{
  long a[10];
  for (long i = 0; i <= 10; i += 1) {
    a[i] = 1;
  }
}

Running this, however, would lead to memory corruption, since we are writing to a[10] (the 11-th element) but we only asked for 10 elements for the array a. So we are writing to a memory that we are not supposed to and thus causing your program to behave incorrectly.

Similarly, reading from a memory location that we are not supposed to could lead to a misbehaving program. You have seen this in Problem 1.1(d).

Other Facts About Arrays

Skipping Elements During Initialization

If we have a large array, and we want most of it to be initialized to 0, and only some non-zero, we can use element designators, putting the index of the element we want to initialize to non-zero in square brackets [ and ].

long vector[100] = {1, [5] = 2, 3, [99] = -1};

This statement initializes vector[0] to 1, vector[5] to 2, vector[6] to 3, and vector[99] to -1. The rest of the elements will be 0.

Skipping the Size in Declaration

If you supply an initialization list, the number of elements already indicates the length to the compiler, so you can skip the length.

long marks[] = {1, 3, 2, 8, 5,}

This makes it easy to add or remove items from the array, without having to remember to keep the array length consistent.

Determining the Number of Elements in the Array

C provides a sizeof operator, which returns the number of bytes allocated to a type. We can use sizeof long for instance, to determine the number of bytes allocated to long on a platform. We can also use sizeof on a variable instead of the type. This becomes useful to determine, programmatically, the length of an array (esp if the array length is skipped in the array declaration). We can calculate the number of elements in marks with

long marks[] = { 1, 2, 3, 5, 8 };
long num_of_elem = sizeof marks/sizeof marks[0];

Problem Set 14

Problem 14.1

Consider the snippet below.

void doThat(long a[], long b[]) {
  a[0] = 100;
  b[1] = 200;
  // Line A
}

void doThis(long a[]) {
  long *b = a;  
  doThat(a, b);
}

int main()
{
  long a[3] = {0, 0, 0};
  doThis(a);
  // Line B
}

a. Show the content of the stack at Line A if the program above is executed. b. What is the content of array a at Line B?

Problem 14.2

Consider the snippet below.

void doThat(long list[]) {
  list[1] = 200;
  // Line A
}

void doThis(const long a[]) {
  long b[2] = {10, 10};
  a = b;
  doThat(a);
}

int main()
{
  long a[3] = {0, 0, 0};
  doThis(a);
  // Line B
}

a. Does the code compile cleanly? b. Show the content of the stack at Line A if the program above is executed. c. What is the content of array a at Line B?