Assignment Top StringsArrays Contents

Arrays

In this chapter, we will study arrays, a device used for bringing related bits of data together underneath one roof, so to speak. Such a device is known as a data structure; an array is one of the most basic of data structures.

An array is composed of slots. Each slot can hold one piece of data. If the array has ten slots, then it can hold 10 pieces of data. Each piece of data is known as an element.

Depending upon the programming language, arrays can be heterogeneous or homogeneous. Orthogonally, they can be fixed-size or dynamic. The word heterogeneous means that a single array can hold multiple types of data. That is to say, one array could hold a string in one slot and an integer in another. Conversely, if an array is homogeneous, then each piece of data stored in the array must be the same type. A fixed-size array is given a specified number of slots at creation time; the number of slots cannot change while the program is running. On the other hand, a dynamic array can grow larger, if necessary, to accommodate additional data items. In C, arrays are homogeneous and fixed-sized. Note that this fixed size can be determined while the program is running, but once you make the allocation then you can't change that size at a later date.

Arrays as data structures

As stated previously, a data structure is simply a collection of bits of information16 that are somehow glued together into a single whole, along with a set of operations for manipulating said bits. Usually, the bits are somehow related, so the data structure is a convenient way to keep all these related bits nicely packaged together.

At its most basic, a data structure supports the following actions:

We will study these actions with an eye to how long each action is expected to take.

An array is a data structure with the property that each individual piece of data can be accessed just as quickly as any of the others. In other words, the process of putting data in and taking data out takes a constant amount of time regardless of the size of the array and which slot is being used to store a data item17.

Array creation

There are two basic ways to create an array, statically and dynamically. Note that a dynamically created array is not the same thing as a dynamic array; a dynamically created array can only be fixed-size in C.

A static array lasts as long as the function in which the array was created lasts (runs). If you create a static array in main then it lasts for the duration of your program. Since creation of an array entails the allocation of memory somewhere to serve as slots, we refer to array creation as array allocation.

To allocate a static array, one uses bracket notation:

    int a[10];

This statement creates a constant, named a, that refers to 10 slots in memory. Each of the slots can hold an integer. The size of the array (i.e. the number of slots) is placed between the brackets that follow the variable name. The reason a is a constant and not a variable is that the value of a cannot be changed. The value of a is a particular piece of memory where the ten slots are located; that value is forever fixed while a exists.

Pictorially, we represent the constant created when an array is statically allocated like this:

We read this image as "a holds a location in memory where one can find the first slot of an array". This is a bit wordy, so we often use the less precise shorthand, "the array a".

Arrays created in this manner have what might be considered random values in each of the slots. Such an array is said to be uninitialized. We can also initialize arrays at allocation time:

    int b[3] = { 42, 13, 77 };

The initialization values are comma-separated and placed between braces. It is considered "bad style" to have a mismatch between the number of slots and the number of initializers18. If you are bad at counting, you can have C count for you. The following statement is equivalent to the previous one.

    int b[] = { 42, 13, 77 };

In either case, we end up with a picture like this:

In the latter version, the number of slots is omitted. One must specify the number of slots, either explicitly using non-empty brackets, or implicitly, using initializers. It is an error to do neither. Thus, the statement:

    int c[];

will generate an error.

Remember, if you allocate an array and do not give any initializers, the slots are filled with whatever random bits are lying around in the memory allocated. Such uninitialized slots are said to be filled with garbage, just like when a variable is created but not initialized.

Indexing into Arrays

You can retrieve a value stored in an array by using bracket notation. With bracket notation, you specify exactly which element you wish to extract from the array. This specification is called an index. The first element of the array has index 0, the second index 1, and so on. The last element in an array with n slots has an index of n-1. This concept of having the first element having an index of zero is known as zero-based counting, a common concept in Computer Science. Here is some code that extracts the first element of an array. Note that the first interaction creates a variable named items that points to an array of three elements:

    //test
    int sum;
    int items[3] = { 7, 11, 711 };
    printf("the first slot holds %d\n",items[0]);
    printf("the second slot holds %d\n",items[1]);
    printf("the third slot holds %d\n",items[2]);
    sum = items[0] + items[1] + items[2];
    printf("the sum of the three elements is %d\n",sum);

The first three print statements should produce, respectively:

   the first slot holds 7
   the second slot holds 11
   the third slot holds 711

Accessing an element in a slot does not remove the element. Thus, the last print statement yields:

    the sum of the three elements is 729

In the statement:

    sum = items[0] + items[1] + items[2];

the appearance of items[0], items[1], and items[2] to the right of the assignment operator means that they are rvalues. Thus, we use their values to compute the sum.

We can also use an expression involving variables as an index. The following code gives exactly the print outs as previously:

    //test
    int items[3] = { 7, 11, 711 };
    int i = 0;
    printf("the first slot holds %d\n",items[i]);
    printf("the second slot holds %d\n",items[i+1]);
    printf("the third slot holds %d\n",items[i+2]);
    int sum = items[i] + items[i+1] + items[i+2];
    printf("the sum of the three elements is %d\n",sum);

In addition to retrieving elements of an array, we can change existing elements as well, by using the assignment operator:

    //test
    int a[3] = { 7, 11, 711 };
    a[1] = 13;                                  // replace 11 with 13
    printf("the second element is %d\n",a[1]);  //should print: the second element is 13

In the statement:

    a[1] = 13;

the expression a[1] is considered an rvalue and thus refers to a location in memory that is to be updated. As with retrieving values, we can use any arithmetic expression as an index when replacing elements.

Array indices that are out of bounds

When we use an index that is too small (i.e. a negative index) or too large (i.e. an index greater than or equal to the size of the array), we say the array index is out of bounds. What actually happens if we use an out-of-bounds index?

    //test
    int items[3] = { 7, 11, 711 };                   //only three slots!
    printf("the fourth slot holds %d\n",items[3]);

We get a surprising result:

    the fourth slot holds 134513712

You may get a different number printed, but you will likely not get an error message, even though an error has clearly occurred. Why is this?

C is designed to be a very fast language. Generally, a program written in C will run faster (by a stopwatch) than the equivalent program written in some other programming language. One reason for its speed is due to the fact that it does very little error checking. When an array is allocated, the slots are allocated consecutively in a block of memory. When we ask for a particular slot, C calculates how far into the block to look for the value in that slot. An index of zero refers to a slot at the beginning of the block, an index of one refers to the next slot in, and so on. Since no error checking is performed, asking for a slot beyond the last slot simply tells C to reference memory beyond the block allocated to the array. What is found there can be anything.

Behavior of a program that retrieves or changes memory that is out of bounds is undefined. When one is lucky, the program crashes immediately upon the out-of-bounds access. When one is less lucky, the program runs for a while before crashing, making the determination of what caused the crash much more difficult. If one is extremely unlucky, the program never crashes. In this last case, only thorough testing along with a very careful screening of the output reveals the existence of the error.

Arrays and aliases to arrays

In programming, an array alias is a second variable referring to the same array as the first. In the following code, we want to configure b as an alias for a. To do this, we will have to properly define b. However, for now, assume that ... contains a definition of b (we'll formally define it in a few minutes). Let's see what should happen if we can establish b as an alias to a.

    double a[3] = { 2.7, 3.1, 1.4 };
    ...
    b = a;

If we were to change an element using b, we would see the new element using a:

    double a[3] = { 2.7, 3.1, 1.4 };
    ...
    b = a;
    b[0] = 1.61;
    printf("does a[0] == b[0]? %d\n",a[0] == b[0]);

The answer we would get is:

    does a[0] == b[0]? 1

Recall that a non-zero integer means true, so the 1 following the question mark means the equality test evaluated to true: the first element of a and the first element of b are the same.

OK, now that you see how aliasing works, we need to figure out the proper technique for defining b. What is missing from the above code fragments is how to create the variable b. One would think we would have to create b as the same kind of array as a:

    double a[3] = { 2.7, 3.1, 1.4 };
    double b[3];
    b = a;

After all, it is only logical that a and b should have the same type if we are going to have them point to the same thing. Unexpectedly, we get the following error message when we compile:

    error: incompatible types when assigning to type 'double[3]' from type 'double *'

Why this error occurs will become clear in time, but for now, remember this rule:

For a statically allocated array, you cannot reassign its name.

If you declared a statically allocated array, it has a fixed location. You can't move it to a new location. The statement b = a was trying to move a statically allocated array.

If we look at the error message carefully we see that we are assigning to type 'double[3]'. This makes sense because clearly the type of b is an array of three doubles. What is strange is the next part, from type 'double *'. Somehow, when we use the name of an array on the right-hand side of an assignment, its type morphs. Let's try again, changing the type of b to double *, the type that a appears to have become:

    //test
    double a[3] = { 2.7, 3.1, 1.4 };
    double *b;
    b = a;
    b[0] = 1.61;
    printf("does a[0] == b[0]? %d\n",a[0] == b[0]); //should print true: 1

We see now that the program compiles correctly and, indeed, b appears to be an alias of a. Especially note that we use the same syntax to index a slot an array, whether we use the array name or a variable that has been assigned the array name.

So why the double *? In C, when an asterisk appears in a type, it means a variable of that type will hold the address of a memory location. So a variable of type double * will hold the address of a memory location that stores a real number. Recall that, in our example, a is a memory location where the first slot of an array of doubles can be found. So if we want to store this memory location in another variable, the type of the other variable must be double *. Of course, if a instead referred to a statically allocated array of integers, then the type of b would have to be int *.

A variable that holds a memory location and is of a type containing an asterisk is known as a pointer. In our example, both the constant a and variable b hold memory locations. We call the constant a a pseudopointer since its type is double [3], not double *. The variable b, on the other hand, has type double *, so it is a true pointer. In all but a very few situations, pseudopointers are converted to pointers, so it is convenient to think of the constant a as a pointer. Assignment is one situation where the difference between pointers and pseudopointers becomes apparent . If we try to assign to a, the compiler rejects our attempt:

    //test
    double a[3] = { 2.7, 3.1, 1.4 };
    double *b;
    b = a;                  // OK, can assign a pseudopointer to a pointer
    a = b;                  // rejected, cannot assign to a pseudopointer

The last line generates the error:

    error: incompatible types when assigning to type 'double[3]' from type 'double *'

just like we saw before. When we refer to a pseudopointer as a value, the compiler converts it to a pointer (as in the next to the last line). When we refer to a pseudopointer as a location, in order to reassign it (as in the last line), the compiler says no.

Other than assignment and one other difference, discussed in the next section, it is generally OK to think of a pseudopointer as a pointer. But don't be surprised by what happens if you don't keep these two exceptions in mind.

Graphically, we represent a pointer with an arrow. So b, from our example, looks like this:

Suppose the array to which a refers starts at memory location 1958. Then, an alternate view of b would be:

In fact, you can see where a and b point by using the %p directive in the control string for printf:

    //test
    double a[3] = { 2.7, 3.1, 1.4 };
    double *b;
    b = a;
    printf("a points to %p\n",a);
    printf("b points to %p\n",b);

Running this code will yield something like:

    a points to 0x96b0570
    b points to 0x96b0570

Whatever memory locations are printed, they should match. We can also see that the %p directive causes the pointed-to location to be printed out in hexadecimal (hexadecimal numbers in C begin with 0x). Note that from now on, we will use the terms memory location and address interchangeably. Thus, we will often say things like "variables a and b hold the address of the array".

Determining the length of an array

One can compute the length of a statically allocated array using the sizeof operator:

    //test
    double a[3] = { 2.7, 3.1, 1.4 };
    printf("the size of a is %zu\n",sizeof(a));

Depending on your system, it yields something like:

    the size of a is 24

This appears to be incorrect; shouldn't the size of a be three? There are three elements in a, but that is not the same thing as asking how much total size the array a takes in memory.

The sizeof operator is working correctly, but it is not returning the number of slots in the array. Instead, it is returning the number of bytes19 allocated for the array. If one knew how many bytes made up a double, we could compute the number of slots. Luckily, the sizeof operator can tell us the number of bytes each double slot requires. By dividing the size of the array (in bytes) by the size of a slot (in bytes), we get the number of slots:

    //test
    double a[3] = { 2.7, 3.1, 1.4 };
    printf("the size of a is %zu\n",sizeof(a)/sizeof(double));

Now we get the desired result:

    the size of a is 3

You likely have noticed a new format specifier in the guide string in the above example: %zu. The sizeof operator returns a 64-bit integer on 64-bit computers and a 32-bit integer on 32-bit computers. The specifier for 32-bit integers is %d, as we have seen before, but the specifier for 64-bit integers is %ld. In order to write portable code that runs on both kinds of computers, we use the generic %zu specifier that can hand both kinds of integers.

Two quick questions for you at this point. First, looking at the example above, it should be easy to modify that code so that you could figure out how much space an array of 50 integers required. Can you do that? Second, is this trick (sizeof the array divided by sizeof each element) required for strings (arrays of characters)? Why or why not?

We can simplify the process of finding the number of slots by using a macro:

    //test
    #define SLOTS(t) (sizeof(t)/sizeof(*t))
    double a[3] = { 2.7, 3.1, 1.4 };
    printf("the size of a is %zu\n",SLOTS(a));

You can read more about C macros on the web. When we run this code, as before, we get the desired result:

    the size of a is 3

If we try to use sizeof to find the size of an array through an alias:

    //test
    #define SLOTS(t) (sizeof(t)/sizeof(*t))
    double a[3] = { 2.7, 3.1, 1.4 };
    double *b = a;
    printf("the size of a is %zu\n",SLOTS(b));

On a 32-bit machine, we get an incorrect answer:

    the size of a is 0

The reason is because sizeof, when applied to a true pointer variable, returns the size of the variable, not the size of memory allocated. In this case, sizeof(double *) returns how many bytes it takes to store an address of a double. We can deduce that the size of a double * is less than the size of a double, on a 32-bit machine. Using integer division, we get a zero result.

Pointers and indexing

Luckily, one can use the same notation to index into an array, whether using the name of the array or a pointer to the array. In fact a pseudopointer to an array is immediately converted into a pointer nearly every time we reference an array name.

When we refer to a particular slot in an array, either through the array name or a pointer, as in:

    a[5]

a number of computations are made in finding the desired slot. First, if the array name is used, it is converted into a pointer. Second, the address stored in the pointer is extracted. This address is known as the base address and is the address of the first slot. Then, the value of the index, which refers to a slot number, is converted to an offset. The offset reflects how many bytes past the base address the desired slot resides. Suppose a, in the example above, points to an integer array. Then slot five is located 5 * sizeof(int) bytes past the base address. If the array of integers starts at memory location 1000 and an integer is 4 bytes, then slot 5 is located at memory location 1000 + 5 * 4 or 1020.

You can also use pointer offsets directly to access a slot in an array. These two statements are equivalent:

    array[5] = 0;
    *(array + 5) = 0;

The latter form is known as star-notation or dereferencing. In fact, C converts array access using brackets to star notation in computing offsets to the base address.

The following four statements are also equivalent:

    array[0] = 5;
    *(array + 0) = 5;
    *(array) = 5;
    *array = 5;

In fact, *array is often used as a short hand to the first element of an array, especially in dealing with arrays of characters. This form is known as pointer dereferencing.

The evils of statically allocated arrays

Statically allocated arrays suffer from two problems. The first is that they cannot be returned from the function that created them. We haven't covered functions yet, but the following function definition is easy enough to understand:

    double *
    newArrayOfThreeDoubles()
        {
        double a[3] = {0.0};
        return a;
        }

The function allocates a static array that can hold three doubles; each slot has been initialized to zero. As its final act, the function returns the address of this statically allocated array.

If we try to compile this function, we get the following warning:

    warning: function returns address of local variable [-Wreturn-local-addr]

The problem is the memory allocated to the array is expected to be of use while the function is executing; after the function returns, that memory is free to be reused. Once the memory was reused, the caller of the function now has an array whose slots appear to change at random. Back in the day, such warnings were only pipe dreams, so a program that contained such code would be happily compiled, so consider yourself lucky you live in an age where the compiler looks after you so well.

The second problem with static arrays is that their misuse accounts for a vast majority of the security holes found in the past and many of the security holes currently being uncovered. The reason is the C programming language is quite popular for writing the guts of software systems, since it is so fast. The reason it is so fast is that C does not check for out-of-bounds errors with regard to accessing array elements. It turns out that a large amount of the C code extant has been written by people not properly trained in Modern Computer Science theory and practice. The result is a perfect storm of vulnerable code, illustrated by the following, rather simple, code fragment:

    char buffer[512];               //create a static array of char
    printf("What is your name? ");  //print a prompt for the user
    scanf("%s",buffer);             //read the response into the array

What could possibly be wrong with this code? Surely, no one has a name longer than 511 characters? This issue, known as the buffer overflow problem, will be discussed further in the chapter on input and output.

Dynamically allocated arrays

We have discussed statically allocated arrays at length because they are the easiest version of arrays for beginners to learn. Yet, as a programmer gets more and more sophisticated, statically allocated arrays appear less and less in the programs he or she writes. This is mainly due to the two dangers listed in the previous section. Dynamically allocated arrays solve the first problem, returning a local array from a function.

Dynamically allocated arrays exist for as long as the program runs, regardless of when or where they are allocated. Here is a template for dynamically allocated array. In this code, we are allocating an array of type XXXX with YYYY slots. The system call that finds a block of space and allocates that space is malloc. Note that malloc is configured to return a zero when it is unable to allocate the requested memory. You should always check to make sure that any malloc you perform actually succeeds.

    XXXX *a;

    a = malloc(sizeof(XXXX) * YYYY);
    if (a == 0)
        {
        fprintf(stderr, "memory allocation failed\n");
        exit(1);
        }

In the template, XXXX is replaced by a type, say int or double or char *. YYYY is replaced by the number of slots desired.

If we wish for an integer array with eight slots, we fill out the template like this:

    int *a;

    a = malloc(sizeof(int) * 8);
    if (a == 0)
        {
        fprintf(stderr, "memory allocation failed\n");
        exit(1);
        }

The function malloc does the actual allocation and it needs to know the number of bytes required. We compute that quantity with the sizeof operator, which we use to give us the number of bytes needed by one slot. We multiply that by the number of slots to get the total number of bytes. Note that arrays allocated in this manner are uninitialized; their slots are filled with garbage.

Alternatively, we can ask the sizeof operator to compute the size of what a pointer points to:

    int *a;
    a = malloc(sizeof(*a) * 8); //equivalent to malloc(sizeof(int) * 8);

If the memory cannot be allocated by malloc (maybe you're asking for too many slots), the function returns zero.

We haven't talked about if statements yet, but the code following the allocation is easy enough to read. If the malloc function returns a zero rather than an address, we print an error message and exit the program. Recall that if main returns a non-zero value, an error is assumed. The exit function mimics main returning immediately with the given value.

One other note on the above example. The fprintf statement prints to stderr, which is by default associated with the console. There are lots of cases where you might direct regular output (stdout) to a file rather than the console. By writing to stderr, we can see error messages on the console even if the regular output from a program is being captured elsewhere.

Once the array has been successfully allocated, you can use indexing just like with statically allocated arrays, both for retrieving and changing elements in the array. Moreover, the array will last until the program ends or until you free up the memory allocated to be used again. To free the array, you simply call the free function:

    free(a);

Be careful when you free things. You can only free things that have been allocated with malloc (or similar functions), you may not free the same thing more than once, and you may not refer to slots in an array you have previously freed.

You have probably heard of memory leaks. An example of a memory leak is a situation where a program that runs for a long time (when is the last time you turned your smartphone off?) consumes new memory as it processes requests but never releases those dynamically allocated resources. Eventually, the system runs out of space to allocate additional resources (malloc returns a zero). The issue of memory leaks is critical for applications that run for any amount of time. While you don't have to worry about memory leaks for project0, this is a major issue for the writers of any modern operating system.

Finally, for completeness, we note that the second problem with statically allocated arrays, the buffer overflow problem, can be solved with dynamically allocated arrays. You can use dynamically allocated arrays to simulate dynamic arrays (those arrays that grow as needed). We will cover this technique in a later chapter.

There is a lot going on in this section that you likely don't understand at this point and that's OK. You should, however, be able to use this template if you are required to use dynamically allocated arrays in a program.

Pointers to static arrays

We have already discussed pointers to arrays of one dimension. Here is an example:

    int a[10];    //a is a one-dimensional array
    int *p = a;   //p points to the first slot of a

Although, we will not discuss them in detail until later, it is possible to have multi-dimensional static arrays:

    int b[10][12];          //a two-dimensional array, 10 rows and 12 columns
    int c[50][60][40];      //a 3D array, 50 sheets, 60 rows, and 40 columns
    int d[11][13][17][19];  //a 4D array, 11 ledgers, 13 sheets, 17 rows, and 19 columns

Based upon the array a and the pointer p above, one might think that a pointer to b would look like this:

    int b[10][12];
    int **q = b;        //compiler warning, types do not match

Instead, we get a compiler warning. This is because when the pseudopointer b devolves into a pointer, only the first dimension becomes a pointer; the remaining dimensions remain arrays. The correct type for q would be:

    int b[10][12];
    int (*q)[12] = b;

The parentheses are required since the brackets have a higher precedence than than the asterisk. Without the parentheses, q would be a one-dimensional array of integer pointers. With them, it is a pointer to a one-dimensional array of integers with length 12. Thus, the variable q points to the first set of 12 integers, while the expression q+1 points to the second set of 12 integers. The expression q+2 points to the third set of twelve integers, and so on.

Pointers r and s, which are to point to arrays c and d above, respectively, would be defined as follows:

    int c[50][60][40]; 
    int (*r)[60][40] = c;

    int d[11][13][17][19];
    int (*s)[13][17][19] = d;

Remember, when an array name devolves into a pointer, the type of that pointer can be generated by removing the first set of brackets and adding the asterisk and parentheses in its stead.

The reason for this behavior is as follows. Consider our example of a two dimensional array:

    int b[10][12];          //10 rows, 12 columns
    int (*q)[12] = b;
    int **z = b;            //not really valid, but likely will compile

The expression q[0] refers to the first set of 12 integers, while q[1] refers to the second set of 12, and so on. Thus q[1][2] refers to the third integer in the second set of 12, as expected. C needs to know how many integers it needs to skip over to move from row 0 to row 1. The answer is twelve and can be found in the types of both b and q. On the other hand, that information is missing in z and computations invoving elements of z invariably go wrong.

lusth@cs.ua.edu


Assignment Top StringsArrays Contents