This chapter introduces the important topic of data structures—collections of related data items. Arrays are data structures consisting of related data items of the same type. We considered classes in Chapter 3. In Chapter 19, Bits, Characters, C Strings and structs, we discuss the notion of structures. Structures and classes can each hold related data items of possibly different types. Arrays, structures and classes are “static” entities in that they remain the same size throughout program execution. (They may, of course, be of automatic storage class and hence be created and destroyed each time the blocks in which they are defined are entered and exited.)

After discussing how arrays are declared, created and initialized, we present a series of practical examples that demonstrate several common array manipulations. We then explain how character strings (represented until now by string objects) can also be represented by character arrays. We present an example of searching arrays to find particular elements. The chapter also introduces one of the most important computing applications—sorting data (i.e., putting the data in some particular order). Two sections of the chapter enhance the case study of class GradeBook in Chapters 3–6. In particular, we use arrays to enable the class to maintain a set of grades in memory and analyze student grades from multiple exams in a semester—two capabilities that were absent from previous versions of the GradeBook class. These and other chapter examples demonstrate the ways in which arrays allow programmers to organize and manipulate data.

The style of arrays we use throughout most of this chapter are C-style pointer-based arrays. (We’ll study pointers in Chapter 8.) In the final section of this chapter, and in Chapter 20, Standard Template Library (STL), we’ll cover arrays as full-fledged objects called vectors. We’ll discover that these object-based arrays are safer and more versatile than the C-style, pointer-based arrays we discuss in the early part of this chapter.

An array is a consecutive group of memory locations that all have the same type. To refer to a particular location or element in the array, we specify the name of the array and the position number of the particular element in the array.

Figure 7.1 shows an integer array called c. This array contains 12 elements. A program refers to any one of these elements by giving the name of the array followed by the position number of the particular element in square brackets ([]). The position number is more formally called a subscript or index (this number specifies the number of elements from the beginning of the array). The first element in every array has subscript 0 (zero) and is sometimes called the zeroth element. Thus, the elements of array c are c[0] (pronounced “c sub zero”), c[1], c[2] and so on. The highest subscript in array c is 11, which is 1 less than the number of elements in the array (12). Array names follow the same conventions as other variable names, i.e., they must be identifiers.

Fig. 7.1 Array of 12 elements.

A subscript must be an integer or integer expression (using any integral type). If a program uses an expression as a subscript, then the program evaluates the expression to determine the subscript. For example, if we assume that variable a is equal to 5 and that variable b is equal to 6, then the statement

adds 2 to array element c[ 11 ]. Note that a subscripted array name is an lvalue—it can be used on the left side of an assignment, just as nonarray variable names can.

Let us examine array c in Fig. 7.1 more closely. The name of the entire array is c. Its 12 elements are referred to as c[0] to c[ 11 ]. The value of c[0] is -45, the value of c[1] is 6, the value of c[2] is 0, the value of c[7] is 62, and the value of c[ 11 ] is 78. To print the sum of the values contained in the first three elements of array c, we’d write

To divide the value of c[ 6 ] by 2 and assign the result to the variable x, we would write

Common Programming Error 7.1

Note the difference between the “seventh element of the array” and “array element 7.” Array subscripts begin at 0, so the “seventh element of the array” has a subscript of 6, while “array element 7” has a subscript of 7 and is actually the eighth element of the array. Unfortunately, this distinction frequently is a source of off-by-one errors. To avoid such errors, we refer to specific array elements explicitly by their array name and subscript number (e.g., c[6] or c[7]).

The brackets used to enclose the subscript of an array are actually an operator. Brackets have the same level of precedence as parentheses. Figure 7.2 shows the precedence and associativity of the operators introduced so far. Note that brackets ([]) have been added to the first row of Fig. 7.2. The operators are shown top to bottom in decreasing order of precedence with their associativity and type.

Figure 7.5 sets the elements of a 10-element array s to the even integers 2, 4, 6, . . ., 20 (lines 17–18) and prints the array in tabular format (lines 20–24). These numbers are generated (line 18) by multiplying each successive value of the loop counter by 2 and adding 2.

Often, the elements of an array represent a series of values to be used in a calculation. For example, if the elements of an array represent exam grades, a professor may wish to total the elements of the array and use that sum to calculate the class average for the exam. The examples using class GradeBook later in the chapter, namely Figs. 7.16–7.17 and Figs. 7.23–7.24, use this technique.

The program in Fig. 7.8 sums the values contained in the 10-element integer array a. The program declares, creates and initializes the array in line 10. The for statement (lines 14–15) performs the calculations. The values being supplied as initializers for array a also could be read into the program from the user at the keyboard, or from a file on disk (see Chapter 17, File Processing). For example, the for statement

reads one value at a time from the keyboard and stores the value in element a[ j ].

Many programs present data to users in a graphical manner. For example, numeric values are often displayed as bars in a bar chart. In such a chart, longer bars represent proportionally larger numeric values. One simple way to display numeric data graphically is with a bar chart that shows each numeric value as a bar of asterisks (*).

Professors often like to examine the distribution of grades on an exam. A professor might graph the number of grades in each of several categories to visualize the grade distribution. Suppose the grades were 87, 68, 94, 100, 83, 78, 85, 91, 76 and 87. Note that there was one grade of 100, two grades in the 90s, four grades in the 80s, two grades in the 70s, one grade in the 60s and no grades below 60. Our next program (Fig. 7.9) stores this grade distribution data in an array of 11 elements, each corresponding to a category of grades. For example, n[0] indicates the number of grades in the range 0–9, n[7] indicates the number of grades in the range 70–79 and n[ 10 ] indicates the number of grades of 100. The two versions of class GradeBook later in the chapter (Figs. 7.16–7.17 and Figs. 7.23–7.24) contain code that calculates these grade frequencies based on a set of grades. For now, we manually create the array by looking at the set of grades.

The program reads the numbers from the array and graphs the information as a bar chart, displaying each grade range followed by a bar of asterisks indicating the number of grades in that range. To label each bar, lines 21–26 output a grade range (e.g., "70-79: ") based on the current value of counter variable i. The nested for statement (lines 29–30) outputs the bars. Note the loop-continuation condition in line 29 (stars < n[ i ]). Each time the program reaches the inner for, the loop counts from 0 up to n[ i ], thus using a value in array n to determine the number of asterisks to display. In this example, n[ 0 ]–n[5] contain zeros because no students received a grade below 60. Thus, the program displays no asterisks next to the first six grade ranges.

Common Programming Error 7.7

Although it is possible to use the same control variable in a for statement and in a second for statement nested inside, this is confusing and can lead to logic errors.

Sometimes, programs use counter variables to summarize data, such as the results of a survey. In Fig. 6.8, we used separate counters in our die-rolling program to track the number of occurrences of each side of a die as the program rolled the die 6,000,000 times. An array version of this program is shown in Fig. 7.10.

Figure 7.10 uses the array frequency (line 20) to count the occurrences of each side of the die. The single statement in line 26 of this program replaces the switch statement in lines 30–52 of Fig. 6.8. Line 26 uses a random value to determine which frequency element to increment during each iteration of the loop. The calculation in line 26 produces a random subscript from 1 to 6, so array frequency must be large enough to store six counters. However, we use a seven-element array in which we ignore frequency[ 0 ]—it is more logical to have the die face value 1 increment frequency[ 1 ] than frequency[ 0 ]. Thus, each face value is used as a subscript for array frequency. We also replace lines 56–61 of Fig. 6.8 by looping through array frequency to output the results (lines 31–33).

Our next example (Fig. 7.11) uses arrays to summarize the results of data collected in a survey. Consider the following problem statement:

This is a typical array-processing application. We wish to summarize the number of responses of each type (i.e., 1 through 10). The array responses (lines 17–19) is a 40-element integer array of the students’ responses to the survey. Note that array responses is declared const, as its values do not (and should not) change. We use an 11-element array frequency (line 22) to count the number of occurrences of each response. Each element of the array is used as a counter for one of the survey responses and is initialized to zero. As in Fig. 7.10, we ignore frequency[ 0 ].

Software Engineering Observation 7.2

The const qualifier should be used to enforce the principle of least privilege. Using the principle of least privilege to properly design software can greatly reduce debugging time and improper side effects and can make a program easier to modify and maintain.

The first for statement (lines 26–27) takes the responses one at a time from the array responses and increments one of the 10 counters in the frequency array (frequency[ 1 ] to frequency[ 10 ]). The key statement in the loop is line 27, which increments the appropriate frequency counter, depending on the value of responses[ answer ].

Let’s consider several iterations of the for loop. When control variable answer is 0, the value of responses[ answer ] is the value of responses[ 0 ] (i.e., 1 in line 17), so the program interprets frequency[ responses[ answer ] ]++ as

which increments the value in array element 1. To evaluate the expression, start with the value in the innermost set of square brackets (answer). Once you know answer’s value (which is the value of the loop control variable in line 26), plug it into the expression and evaluate the next outer set of square brackets (i.e., responses[ answer ], which is a value selected from the responses array in lines 17–19). Then use the resulting value as the subscript for the frequency array to specify which counter to increment.

When answer is 1, responses[ answer ] is the value of responses[ 1 ], which is 2, so the program interprets frequency[ responses[ answer ] ]++ as

which increments array element 2.

When answer is 2, responses[ answer ] is the value of responses[ 2 ], which is 6, so the program interprets frequency[ responses[ answer ] ]++ as

which increments array element 6, and so on. Regardless of the number of responses processed in the survey, the program requires only an 11-element array (ignoring element zero) to summarize the results, because all the response values are between 1 and 10 and the subscript values for an 11-element array are 0 through 10.

If the data in the responses array had contained an invalid value, such as 13, the program would have attempted to add 1 to frequency[ 13 ], which is outside the bounds of the array. C++ has no array bounds checking to prevent the computer from referring to an element that does not exist. Thus, an executing program can “walk off” either end of an array without warning. You should ensure that all array references remain within the bounds of the array.

Common Programming Error 7.8

Referring to an element outside the array bounds is an execution-time logic error. It is not a syntax error.

Error-Prevention Tip 7.1

When looping through an array, the array subscript should never go below 0 and should always be less than the total number of elements in the array (one less than the size of the array). Make sure that the loop-termination condition prevents accessing elements outside this range.

Portability Tip 7.1

The (normally serious) effects of referencing elements outside the array bounds are system dependent. Often this results in changes to the value of an unrelated variable or a fatal error that terminates program execution.

C++ is an extensible language. Section 7.11 presents C++ Standard Library class template vector, which enables programmers to perform many operations that are not available for C++’s built-in arrays. For example, we’ll be able to compare vectors directly and assign one vector to another. In Chapter 11, we extend C++ further by implementing an array as a user-defined class of our own. This new array definition will enable us to input and output entire arrays with cin and cout, initialize arrays when they are created, prevent access to out-of-range array elements and change the range of subscripts (and even their subscript type) so that the first element of an array is not required to be element 0. We’ll even be able to use noninteger subscripts.

Error-Prevention Tip 7.2

In Chapter 11, we’ll see how to develop a class representing a “smart array,” which checks that all subscript references are in bounds at runtime. Using such smart data types helps eliminate bugs.

To this point, we have discussed only integer arrays. However, arrays may be of any type. We now introduce storing character strings in character arrays. Recall that, starting in Chapter 3, we have been using string objects to store character strings, such as the course name in our GradeBook class. A string such as "hello" is actually an array of characters. While string objects are convenient to use and reduce the potential for errors, character arrays that represent strings have several unique features, which we discuss in this section. As you continue your study of C++, you may encounter C++ capabilities that require you to use character arrays in preference to string objects. You may also be asked to update existing code using character arrays.

A character array can be initialized using a string literal. For example, the declaration

initializes the elements of array string1 to the individual characters in the string literal "first". The size of array string1 in the preceding declaration is determined by the compiler based on the length of the string. It is important to note that the string "first" contains five characters plus a special string-termination character called the null character. Thus, array string1 actually contains six elements. The character-constant that represents the null character is '' (backslash followed by zero). All strings represented by character arrays end with this character. A character array representing a string should always be declared large enough to hold the number of characters in the string and the terminating null character.

Character arrays also can be initialized with individual character constants in an initializer list. The preceding declaration is equivalent to the more tedious form

Note the use of single quotes to delineate each character constant. Also, note that we explicitly provided the terminating null character as the last initializer value. Without it, this array would simply represent an array of characters, not a string. As we discuss in Chapter 8, not providing a terminating null character for a string can cause logic errors.

Because a string is an array of characters, we can access individual characters in a string directly with array subscript notation. For example, string1[ 0 ] is the character 'f', string1[ 3 ] is the character 's' and string1[ 5 ] is the null character.

We can input a string directly into a character array from the keyboard using cin and >>. For example, the declaration

creates a character array capable of storing a string of up to 19 characters and a terminating null character. The statement

reads a string from the keyboard into string2 and appends the null character to the end of the string input by the user. Note that the preceding statement provides only the name of the array and no information about the size of the array. It is your responsibility to ensure that the array into which the string is read is capable of holding any string the user types at the keyboard. By default, cin reads characters from the keyboard until the first white-space character is encountered—regardless of the array size. Thus, inputting data with cin and >> can insert data beyond the end of the array (see Section 8.13 for information on preventing insertion beyond the end of a char array).

Common Programming Error 7.9

Not providing cin >> with a character array large enough to store a string typed at the keyboard can result in loss of data in a program and other serious runtime errors.

A character array representing a null-terminated string can be output with cout and <<. The statement

prints the array string2. Note that cout <<, like cin >>, does not care how large the character array is. The characters of the string are output until a terminating null character is encountered; the null character is not printed. [Note: cin and cout assume that character arrays should be processed as strings terminated by null characters; cin and cout do not provide similar input and output processing capabilities for other array types.]

Figure 7.12 demonstrates initializing a character array with a string literal, reading a string into a character array, printing a character array as a string and accessing individual characters of a string.

Lines 23–24 of Fig. 7.12 use a for statement to loop through the string1 array and print its characters separated by spaces. The condition in the for statement, string1[ i ] != '', is true until the loop encounters the terminating null character of the string.

Chapter 6 discussed the storage-class specifier static. A static local variable in a function definition exists for the program’s duration but is visible only in the function’s body.

Performance Tip 7.1

We can apply static to a local array declaration so that the array is not created and initialized each time the program calls the function and is not destroyed each time the function terminates in the program. This can improve performance, especially when using large arrays.

A program initializes static local arrays when their declarations are first encountered. If a static array is not initialized explicitly by you, each element of that array is initialized to zero by the compiler when the array is created. Recall that C++ does not perform such default initialization for automatic variables.

Figure 7.13 demonstrates function staticArrayInit (lines 25–41) with a static local array (line 28) and function automaticArrayInit (lines 44–60) with an automatic local array (line 47).

Function staticArrayInit is called twice (lines 13 and 17). The static local array is initialized to zero by the compiler the first time the function is called. The function prints the array, adds 5 to each element and prints the array again. The second time the function is called, the static array contains the modified values stored during the first function call. Function automaticArrayInit also is called twice (lines 14 and 18). The elements of the automatic local array are initialized (line 47) with the values 1, 2 and 3. The function prints the array, adds 5 to each element and prints the array again. The second time the function is called, the array elements are reinitialized to 1, 2 and 3. The array has automatic storage class, so the array is recreated and reinitialized during each call to automaticArrayInit.

Common Programming Error 7.10

Assuming that elements of a function’s local static array are initialized every time the function is called can lead to logic errors in a program.

The version of class GradeBook (Figs. 7.16–7.17) presented here uses an array of integers to store the grades of several students on a single exam. This eliminates the need to repeatedly input the same set of grades. Array grades is declared as a data member in line 29 of Fig. 7.16—therefore, each GradeBook object maintains its own set of grades.

Note that the size of the array in line 29 of Fig. 7.16 is specified by public const static data member students (declared in line 13). This data member is public so that it is accessible to the clients of the class. We’ll soon see an example of a client program using this constant. Declaring students with the const qualifier indicates that this data member is constant—its value cannot be changed after being initialized. Keyword static in this variable declaration indicates that the data member is shared by all objects of the class—all GradeBook objects store grades for the same number of students. Recall from Section 3.6 that when each object of a class maintains its own copy of an attribute, the variable that represents the attribute is known as a data member—each object (instance) of the class has a separate copy of the variable in memory. There are variables for which each object of a class does not have a separate copy. That is the case with static data members, which are also known as class variables. When objects of a class containing static data members are created, all the objects share one copy of the class’s static data members. A static data member can be accessed within the class definition and the member-function definitions like any other data member. As you’ll soon see, a public static data member can also be accessed outside of the class, even when no objects of the class exist, using the class name followed by the binary scope resolution operator (::) and the name of the data member. You’ll learn more about static data members in Chapter 10.

The class’s constructor (declared in line 16 of Fig. 7.16 and defined in lines 17–24 of Fig. 7.17) has two parameters—the course name and an array of grades. When a program creates a GradeBook object (e.g., line 13 of fig07_18.cpp), the program passes an existing int array to the constructor, which copies the array’s values into the data member grades (lines 22–23 of Fig. 7.17). The grade values in the passed array could have been input from a user or read from a file on disk (as we discuss in Chapter 17, File Processing). In our test program, we simply initialize an array with a set of grade values (Fig. 7.18, lines 10–11). Once the grades are stored in data member grades of class GradeBook, all the class’s member functions can access the grades array as needed to perform various calculations.

Member function processGrades (declared in line 21 of Fig. 7.16 and defined in lines 48–63 of Fig. 7.17) contains a series of member function calls that output a report summarizing the grades. Line 51 calls member function outputGrades to print the contents of the array grades. Lines 148–150 in member function outputGrades use a for statement to output each student’s grade. Although array indices start at 0, a professor would typically number students starting at 1. Thus, lines 149–150 output student + 1 as the student number to produce grade labels "Student 1: ", "Student 2: ", and so on.

Member function processGrades next calls member function getAverage (lines 54–55) to obtain the average of the grades in the array. Member function getAverage (declared in line 24 of Fig. 7.16 and defined in lines 98–108 of Fig. 7.17) uses a for statement to total the values in array grades before calculating the average. Note that the averaging calculation in line 107 uses const static data member students to determine the number of grades being averaged.

Lines 58–59 in member function processGrades call member functions getMinimum and getMaximum to determine the lowest and highest grades of any student on the exam, respectively. Let’s examine how member function getMinimum finds the lowest grade. Because the highest grade allowed is 100, we begin by assuming that 100 is the lowest grade (line 68). Then, we compare each of the elements in the array to the lowest grade, looking for smaller values. Lines 71–76 in member function getMinimum loop through the array, and lines 74–75 compare each grade to lowGrade. If a grade is less than lowGrade, lowGrade is set to that grade. When line 78 executes, lowGrade contains the lowest grade in the array. Member function getMaximum (lines 82–95) works similarly to member function getMinimum.

Finally, line 62 in member function processGrades calls member function outputBarChart to print a distribution chart of the grade data using a technique similar to that in Fig. 7.9. In that example, we manually calculated the number of grades in each category (i.e., 0–9, 10–19, . . ., 90–99 and 100) by simply looking at a set of grades. In this example, lines 120–121 use a technique similar to that in Fig. 7.10 and Fig. 7.11 to calculate the frequency of grades in each category. Line 117 declares and creates array frequency of 11 ints to store the frequency of grades in each grade category. For each grade in array grades, lines 120–121 increment the appropriate element of the frequency array. To determine which element to increment, line 121 divides the current grade by 10 using integer division. For example, if grade is 85, line 121 increments frequency[ 8 ] to update the count of grades in the range 80–89. Lines 124–139 next print the bar chart (see Fig. 7.18) based on the values in array frequency. Like lines 29–30 of Fig. 7.9, lines 135–136 of Fig. 7.17 use a value in array frequency to determine the number of asterisks to display in each bar.

The program of Fig. 7.18 creates an object of class GradeBook (Figs. 7.16–7.17) using the int array gradesArray (declared and initialized in lines 10–11). Note that we use the binary scope resolution operator (::) in the expression “GradeBook::students” (line 10) to access class GradeBook’s static constant students. We use this constant here to create an array that is the same size as array grades stored as a data member in class GradeBook. Lines 13–14 pass a course name and gradesArray to the GradeBook constructor. Line 15 displays a welcome message, and line 16 invokes the GradeBook object’s processGrades member function. The output reveals the summary of the 10 grades in myGradeBook.