Dive Into Systems

1.5. Arrays and Strings

An array is a C construct that creates an ordered collection of data elements of the same type and associates this collection with a single program variable. Ordered means that each element is in a specific position in the collection of values (that is, there is an element in position 0, position 1, and so on), not that the values are necessarily sorted. Arrays are one of C’s primary mechanisms for grouping multiple data values and referring to them by a single name. Arrays come in several flavors, but the basic form is a one-dimensional array, which is useful for implementing list-like data structures and strings in C.

1.5.1. Introduction to Arrays

C arrays can store multiple data values of the same type. In this chapter, we discuss statically declared arrays, meaning that the total capacity (the maximum number of elements that can be stored in an array) is fixed and is defined when the array variable is declared. In the next chapter, we discuss dynamically allocated arrays and multi-dimensional arrays.

Table 1 shows Python and C versions of a program that initializes and then prints a collection of integer values. The Python version uses its built-in list type to store the list of values, whereas the C version uses an array of int types to store the collection of values.

In general, Python provides a high-level list interface to the programmer that hides much of the low-level implementation details. C, on the other hand, exposes a low-level array implementation to the programmer and leaves it up to the programmer to implement higher-level functionality. In other words, arrays enable low-level data storage without higher-level list functionality, such as len, append, insert, and so on.

Python version C version

Table 1. Syntax Comparison of Lists in Python and Arrays in C
Python version	C version
`# An example Python program using a list. def main(): # create an empty list my_lst = [] # add 10 integers to the list for i in range(10): my_lst.append(i) # set value at position 3 to 100 my_lst[3] = 100 # print the number of list items print("list %d items:" % len(my_lst)) # print each element of the list for i in range(10): print("%d" % my_lst[i]) # call the main function: main()`	`/* An example C program using an array. */ #include <stdio.h> int main(void) { int i, size = 0; // declare array of 10 ints int my_arr[10]; // set the value of each array element for (i = 0; i < 10; i++) { my_arr[i] = i; size++; } // set value at position 3 to 100 my_arr[3] = 100; // print the number of array elements printf("array of %d items:\n", size); // print each element of the array for (i = 0; i < 10; i++) { printf("%d\n", my_arr[i]); } return 0; }`

# An example Python program using a list.


def main():


    # create an empty list
    my_lst = []

    # add 10 integers to the list
    for i in range(10):
        my_lst.append(i)



    # set value at position 3 to 100
    my_lst[3] = 100

    # print the number of list items
    print("list %d items:" % len(my_lst))

    # print each element of the list
    for i in range(10):
        print("%d" % my_lst[i])


# call the main function:
main()

/* An example C program using an array. */
#include <stdio.h>

int main(void) {
    int i, size = 0;

    // declare array of 10 ints
    int my_arr[10];

    // set the value of each array element
    for (i = 0; i < 10; i++) {
        my_arr[i] = i;
        size++;
    }

    // set value at position 3 to 100
    my_arr[3] = 100;

    // print the number of array elements
    printf("array of %d items:\n", size);

    // print each element of the array
    for (i = 0; i < 10; i++) {
        printf("%d\n", my_arr[i]);
    }

    return 0;
}

The C and Python versions of this program have several similarities, most notably that individual elements can be accessed via indexing, and that index values start at 0. That is, both languages refer to the very first element in a collection as the element at position 0.

The main differences in the C and Python versions of this program relate to the capacity of the list or array and how their sizes (number of elements) are determined.

For a Python list:

my_lst[3] = 100   # Python syntax to set the element in position 3 to 100.

my_lst[0] = 5     # Python syntax to set the first element to 5.

For a C array:

my_arr[3] = 100;  // C syntax to set the element in position 3 to 100.

my_arr[0] = 5;    // C syntax to set the first element to 5.

In the Python version, the programmer doesn’t need to specify the capacity of a list in advance: Python automatically increases a list’s capacity as needed by the program. For example, the Python append function automatically increases the size of the Python list and adds the passed value to the end.

In contrast, when declaring an array variable in C, the programmer must specify its type (the type of each value stored in the array) and its total capacity (the maximum number of storage locations). For example:

int  arr[10];  // declare an array of 10 ints

char str[20];  // declare an array of 20 chars

The preceding declarations create one variable named arr, an array of int values with a total capacity of 10, and another variable named str, an array of char values with a total capacity of 20.

To compute the size of a list (size meaning the total number of values in the list), Python provides a len function that returns the size of any list passed to it. In C, the programmer has to explicitly keep track of the number of elements in the array (for example, the size variable in Table 1).

Another difference that might not be apparent from looking at the Python and C versions of this program is how the Python list and the C array are stored in memory. C dictates the array layout in program memory, whereas Python hides how lists are implemented from the programmer. In C, individual array elements are allocated in consecutive locations in the program’s memory. For example, the third array position is located in memory immediately following the second array position and immediately before the fourth array position.

1.5.2. Array Access Methods

Python provides multiple ways to access elements in its lists. C, however, supports only indexing, as described earlier. Valid index values range from 0 to the capacity of the array minus 1. Here are some examples:

int i, num;
int arr[10];  // declare an array of ints, with a capacity of 10

num = 6;      // keep track of how many elements of arr are used

// initialize first 5 elements of arr (at indices 0-4)
for (i=0; i < 5; i++) {
    arr[i] = i * 2;
}

arr[5] = 100; // assign the element at index 5 the value 100

This example declares the array with a capacity of 10 (it has 10 elements), but it only uses the first six (our current collection of values is size 6, not 10). It’s often the case when using statically declared arrays that some of an array’s capacity will remain unused. As a result, we need another program variable to keep track of the actual size (number of elements) in the array (num in this example).

Python and C differ in their error-handling approaches when a program attempts to access an invalid index. Python throws an IndexError exception if an invalid index value is used to access elements in a list (for example, indexing beyond the number of elements in a list). In C, it’s up to the programmer to ensure that their code uses only valid index values when indexing into arrays. As a result, for code like the following that accesses an array element beyond the bounds of the allocated array, the program’s runtime behavior is undefined:

int array[10];   // an array of size 10 has valid indices 0 through 9

array[10] = 100;  // 10 is not a valid index into the array

The C compiler is happy to compile code that accesses array positions beyond the bounds of the array; there is no bounds checking by the compiler or at runtime. As a result, running this code can lead to unexpected program behavior (and the behavior might differ from run to run). It can lead to your program crashing, it can change another variable’s value, or it might have no effect on your program’s behavior. In other words, this situation leads to a program bug that might or might not show up as unexpected program behavior. Thus, as a C programmer, it’s up to you to ensure that your array accesses refer to valid positions!

1.5.3. Arrays and Functions

The semantics of passing arrays to functions in C is similar to that of passing lists to functions in Python: the function can alter the elements in the passed array or list. Here’s an example function that takes two parameters, an int array parameter (arr), and an int parameter (size):

void print_array(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d\n", arr[i]);
    }
}

The [] after the parameter name tells the compiler that the type of the parameter arr is array of int, not int like the parameter size. In the next chapter, we show an alternate syntax for specifying array parameters. The capacity of the array parameter arr isn’t specified: arr[] means that this function can be called with an array argument of any capacity. Because there is no way to get an array’s size or capacity just from the array variable, functions that are passed arrays almost always also have a second parameter that specifies the array’s size (the size parameter in the preceding example).

To call a function that has an array parameter, pass the name of the array as the argument. Here is a C code snippet with example calls to the print_array function:

int some[5], more[10], i;

for (i = 0; i < 5; i++) {  // initialize the first 5 elements of both arrays
    some[i] = i * i;
    more[i] = some[i];
}

for (i = 5; i < 10; i++) { // initialize the last 5 elements of "more" array
    more[i] = more[i-1] + more[i-2];
}

print_array(some, 5);    // prints all 5 values of "some"
print_array(more, 10);   // prints all 10 values of "more"
print_array(more, 8);    // prints just the first 8 values of "more"

In C, the name of the array variable is equivalent to the base address of the array (that is, the memory location of its 0th element). Due to C’s pass by value function call semantics, when you pass an array to a function, each element of the array is not individually passed to the function. In other words, the function isn’t receiving a copy of each array element. Instead, an array parameter gets the value of the array’s base address. This behavior implies that when a function modifies the elements of an array that was passed as a parameter, the changes will persist when the function returns. For example, consider this C program snippet:

void test(int a[], int size) {
    if (size > 3) {
        a[3] = 8;
    }
    size = 2; // changing parameter does NOT change argument
}

int main(void) {
    int arr[5], n = 5, i;

    for (i = 0; i < n; i++) {
        arr[i] = i;
    }

    printf("%d %d", arr[3], n);  // prints: 3 5

    test(arr, n);
    printf("%d %d", arr[3], n);  // prints: 8 5

    return 0;
}

The call in main to the test function is passed the argument arr, whose value is the base address of the arr array in memory. The parameter a in the test function gets a copy of this base address value. In other words, parameter a refers to the same array storage locations as its argument, arr. As a result, when the test function changes a value stored in the a array (a[3] = 8), it affects the corresponding position in the argument array (arr[3] is now 8). The reason is that the value of a is the base address of arr, and the value of arr is the base address of arr, so both a and arr refer to the same array (the same storage locations in memory)! Figure 1 shows the stack contents at the point in the execution just before the test function returns.

A stack with two frames: main at the bottom and test on the top. main has two variables, an integer n (5) and an array storing values 0, 1, 2, 8, and 4. Test also has two values, an integer size (2) and an array parameter arr that stores the base memory address of the array in main’s stack frame.

Figure 1. The stack contents for a function with an array parameter

Parameter a is passed the value of the base address of the array argument arr, which means they both refer to the same set of array storage locations in memory. We indicate this with the arrow from a to arr. Values that get modified by the function test are highlighted. Changing the value of the parameter size does not change the value of its corresponding argument n, but changing the value of one of the elements referred to by a (for example, a[3] = 8) does affect the value of the corresponding position in arr.

1.5.4. Introduction to Strings and the C String Library

Python implements a string type and provides a rich interface for using strings, but there is no corresponding string type in C. Instead, strings are implemented as arrays of char values. Not every character array is used as a C string, but every C string is a character array.

Recall that arrays in C might be defined with a larger size than a program ultimately uses. For example, we saw earlier in the section "Array Access Methods" that we might declare an array of size 10 but only use the first six positions. This behavior has important implications for strings: we can’t assume that a string’s length is equal to that of the array that stores it. For this reason, strings in C must end with a special character value, the null character ('\0'), to indicate the end of the string.

Strings that end with a null character are said to be null-terminated. Although all strings in C should be null-terminated, failing to properly account for null characters is a common source of errors for novice C programmers. When using strings, it’s important to keep in mind that your character arrays must be declared with enough capacity to store each character value in the string plus the null character ('\0'). For example, to store the string "hi", you need an array of at least three chars (one to store 'h', one to store 'i', and one to store '\0').

Because strings are commonly used, C provides a string library that contains functions for manipulating strings. Programs that use these string library functions need to include the string.h header.

When printing the value of a string with printf, use the %s placeholder in the format string. The printf function will print all the characters in the array argument until it encounters the '\0' character. Similarly, string library functions often either locate the end of a string by searching for the '\0' character or add a '\0' character to the end of any string that they modify.

Here’s an example program that uses strings and string library functions:

#include <stdio.h>
#include <string.h>   // include the C string library

int main(void) {
    char str1[10];
    char str2[10];
    int len;

    str1[0] = 'h';
    str1[1] = 'i';
    str1[2] = '\0';

    len = strlen(str1);

    printf("%s %d\n", str1, len);  // prints: hi 2

    strcpy(str2, str1);     // copies the contents of str1 to str2
    printf("%s\n", str2);   // prints:  hi

    strcpy(str2, "hello");  // copy the string "hello" to str2
    len = strlen(str2);
    printf("%s has %d chars\n", str2, len);   // prints: hello has 5 chars
}

The strlen function in the C string library returns the number of characters in its string argument. A string’s terminating null character doesn’t count as part of the string’s length, so the call to strlen(str1) returns 2 (the length of the string "hi"). The strcpy function copies one character at a time from a source string (the second parameter) to a destination string (the first parameter) until it reaches a null character in the source.

Note that most C string library functions expect the call to pass in a character array that has enough capacity for the function to perform its job. For example, you wouldn’t want to call strcpy with a destination string that isn’t large enough to contain the source; doing so will lead to undefined behavior in your program!

C string library functions also require that string values passed to them are correctly formed, with a terminating '\0' character. It’s up to you as the C programmer to ensure that you pass in valid strings for C library functions to manipulate. Thus, in the call to strcpy in the preceding example, if the source string (str1) was not initialized to have a terminating '\0' character, strcpy would continue beyond the end of the str1 array’s bounds, leading to undefined behavior that could cause it to crash.

The previous example uses the strcpy function safely. In general, though, strcpy poses a security risk because it assumes that its destination is large enough to store the entire string, which may not always be the case (for example, if the string comes from user input).

We chose to show strcpy now to simplify the introduction to strings, but we illustrate safer alternatives in Section 2.6.

In the next chapter, we discuss C strings and the C string library in more detail.