Lab 6. Arrays: Many Values, One Name

[Illustration]

Introduction

Every variable you have written so far holds one value. That stops being enough the moment a program deals
with all the test scores, or all the rolls of a die. You could declare score1, score2, score3 —
bearable for three, unbearable for thirty, and impossible for a count you do not know until the program runs,
since a loop cannot invent a variable name on each pass.

An array is a group of values of the same type, stored one after another in memory under a single name.
You pick out a value by number rather than by name — and a loop counter is a number, which is the whole
point. Everything in this lab follows from that.

Declaring an array

int score[10];

That defines an array called score holding ten int values. The 10 in brackets is the size
declarator — how many elements the array has. It must be a constant, since the compiler sets aside the
memory before the program ever runs, so this is idiomatic:

const int SIZE = 10;
int score[SIZE];

The ten elements sit in consecutive memory, four bytes each, so score occupies forty bytes.

Subscripts start at zero

Each element is picked out by its subscript, written in brackets after the array name. Here is the one
fact that causes more bugs in this chapter than everything else combined:

Subscripts start at 0. An array of ten elements has subscripts 0 through 9. There is no score[10].

An element behaves exactly like an ordinary variable of its type. You can assign to it, read it, print it,
pass it to a function, use it in arithmetic:

score[0] = 88;
score[7] = score[0] + 5;
cout << score[7] << endl;

The same brackets mean two different things

Square brackets appear in two places and mean something different in each:

int score[10];    // definition:  10 is the SIZE DECLARATOR — how many elements
score[3] = 88;    // statement:    3 is the SUBSCRIPT      — which element

In a definition the number is a count; everywhere else it is a position. Read the line and ask which one you
are looking at.

Arrays and loops belong together

Because a subscript is just an integer, a loop counter can serve as one. This is the pattern you will write
dozens of times this semester:

for (int i = 0; i < SIZE; i++)
{
    score[i] = 1;
}

Look closely at the condition: i < SIZE, not i <= SIZE. With SIZE equal to 10, i takes the values 0
through 9 and stops. That is exactly the set of valid subscripts. Writing <= there is the single most
common array bug in C++, and the next section shows you what it costs.

Task A. Storing, printing, and editing

Write a program edit-array.cpp that creates an array of ten integers and lets the user edit any element:

Create an array myData of 10 integers.
Fill every cell with the value 1, using a for loop.
Print all ten elements on one line, separated by spaces.
Ask the user for a cell index i and a new value v.
If i is a valid subscript (0 ≤ i < 10), set myData[i] = v and go back to step 3.
Otherwise, print a message and exit.

Steps 3–5 repeat, and the body must run once before there is any index to test — so a do while is the
natural shape:

// make the array and fill it with 1
do
{
    // print the array
    // get i and v from the user
    // if i is a valid subscript, update the array at index i
} while ( /* the index was valid */ );

Example

$ ./edit-array

1 1 1 1 1 1 1 1 1 1

Input index: 8
Input value: 99

1 1 1 1 1 1 1 1 99 1

Input index: 0
Input value: 300

300 1 1 1 1 1 1 1 99 1

Input index: 10
Input value: 5

Index out of range. Exit.

Test it properly: use the program’s own interface to produce 5 10 15 20 25 30 35 40 45 50, proving every
element is reachable, then check both edges — 0 and 9 accepted, -1 and 10 ending the program.

What C++ does not check

C++ never checks whether a subscript is within the array’s boundaries. Not when you compile, not when you
run. If myData has ten elements and you write myData[25] = 3;, the compiler will not complain, the
program will not stop, and the assignment will happen — to whatever memory sits twenty-five elements past the
start of the array. That memory belongs to something else.

Type this in as spill.cpp and run it:

#include <iostream>
using namespace std;

int main()
{
    int spill[3]  = {2, 2, 2};   // we will write past the end of this one
    int victim[3] = {1, 1, 1};   // and watch this one change

    cout << "victim before: ";
    for (int i = 0; i < 3; i++)
    {
        cout << victim[i] << " ";
    }
    cout << endl;

    for (int i = 0; i < 5; i++)   // 5 writes into a 3-element array
    {
        spill[i] = 99;
    }

    cout << "victim after:  ";
    for (int i = 0; i < 3; i++)
    {
        cout << victim[i] << " ";
    }
    cout << endl;
    return 0;
}

On the lab machines this prints:

victim before: 1 1 1
victim after:  99 99 1

victim was never assigned to, yet its first two elements changed — because spill[3] and spill[4] are
not part of spill at all, but the memory just after it, where victim lives.

The compiler is silent: compile with g++ -Wall and there is still no warning. Your output may differ
from mine, since where a variable lands is the compiler’s choice — and a bug whose symptoms change when you
recompile is a miserable thing to hunt, which is the real cost here. Bigger overruns usually crash: change
the 5 to 50 and the program will probably die with *** stack smashing detected ***, a net your compiler
added rather than a check the language performed.

The defence is yours: get the loop condition right, and validate any subscript that came from the user.

Task B. Reading an array from a file

Arrays are usually filled from data the program did not write itself. You met input redirection in Lab 3;
this time the program opens the file by name, which is what you need when a program reads more than one file
or has to react to a file that is not there.

Opening a file

ifstream, from <fstream>, is an input file stream. You define one with the name of the file to open, use
it exactly as you use cin, and close it when you are done:

ifstream inFile("scores.txt");

inFile >> number;
inFile.close();

When the file is not there

Opening can fail: wrong name, wrong directory, no permission. The stream then evaluates as false, which is
what if (!inFile) tests. Program 8-3 in the textbook prints a message and carries on — the wrong move,
since every read that follows will fail too and the program will produce confident nonsense.

Stop instead:

#include <cstdlib>

if (!inFile)
{
    cout << "Error: could not open scores.txt" << endl;
    exit(EXIT_FAILURE);
}

exit ends the program immediately, from wherever it is called — no return, no unwinding back through
main. Its argument is the exit status, the number handed back to the shell: EXIT_SUCCESS (0) means it
worked, EXIT_FAILURE (1) means it did not. Both names live in <cstdlib>, and it is the same number
return 0; produces at the end of main. In bash, $? holds it, and build tools read it to decide
whether to keep going:

$ ./scores
Error: could not open scores.txt
$ echo $?
1

A word of caution. exit skips destructors and any cleanup a function was about to do. Reasonable in
main when a program cannot start; a poor idea inside a function some other program may be relying on.

Reading until the data runs out

You rarely know how many values a file holds, but you do know the most your array can take. So the loop
guards on two things at once — capacity, and whether the read succeeded:

while (count < CAPACITY && inFile >> score[count])
{
    count++;
}

inFile >> score[count] is both an action and a test: it reads a value and reports whether it managed to.
The order matters — count < CAPACITY comes first, so a full array is never the target of a read that would
write past the end.

When the loop ends, count holds the number of values actually read. The array has CAPACITY elements, but
only the first count mean anything, so count — not CAPACITY — is what every later loop must use.
Carry it alongside the array from here on.

The task

Create a file scores.txt containing these seven numbers, one per line:

Write a program scores.cpp that declares an array with room for 20 scores, opens scores.txt, exits with
EXIT_FAILURE if the file cannot be opened, reads the values into the array, and prints how many it read
followed by the values themselves.

Example

$ ./scores
Read 7 scores.
88 72 95 61 79 100 84

Then rename scores.txt and run it again to confirm the failure path works. Add more than twenty numbers to
the file and confirm the program stops at twenty instead of running off the end of the array.

Task C. Arrays as lookup tables

An array does not have to be filled by a loop. When you know the values as you write the program, supply them
in the definition itself, in an initialization list:

int days[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

One statement, twelve values, in order, starting at subscript 0 — replacing a dozen assignments and far
easier to check by eye. Two rules the compiler enforces, and one convenience it offers:

The list may be shorter than the array; elements you leave off are set to zero. So
int count[7] = {0}; zeroes an entire array, however large.
The list may never be longer, and you cannot skip a position — values fill from the left with no gaps.
If you initialize an array you may leave the size out and let the compiler count:

int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};   // the compiler counts 12

That last form is worth using whenever the list is the definitive statement of how many there are — add an
element and nothing else needs changing.

Leaving element 0 unused

A small trick that shapes the rest of this lab. Months are numbered 1 to 12, but subscripts start at 0, so
with the array above March is days[2]. Every lookup means remembering to subtract one, and every time you
forget you get a bug. The alternative is to declare thirteen elements and deliberately waste the first:

int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
//              ^ unused placeholder so that March is days[3]

Now the month number is the subscript: days[3] is March. Four wasted bytes buys the disappearance of a
whole category of off-by-one error. When data is naturally numbered from 1 this is usually the right call —
and you will use it twice more before this lab is over.

The task

Write a program months.cpp that holds two arrays of thirteen elements — the month names and the number of
days in each — both with an unused element 0. Ask the user for a month number and report the name and the
length of that month. Reject numbers outside 1–12.

The two arrays work together: subscript 7 means July in one and 31 days in the other. Keeping them in step
is your job, not the compiler’s — nothing connects the arrays except the fact that you use the same subscript
in both.

Example

$ ./months
Enter a month number (1-12): 9
September has 30 days.

$ ./months
Enter a month number (1-12): 13
There is no month number 13.

Task D. A running table: Fibonacci numbers

The Fibonacci sequence starts with F(0) = 0 and F(1) = 1, and every term after that is the sum of the
two before it, F(n) = F(n−1) + F(n−2):

0, 1, 1 (=1+0), 2 (=1+1), 3 (=2+1), 5 (=3+2), 8 (=5+3), 13 (=8+5), and so on.

To compute a term you need the two before it, so the program has to remember them. An array is the natural
place — each element is computed once and stays available:

int fib[60];
fib[0] = 0;
fib[1] = 1;
// and every later term follows from the two before it
fib[i] = fib[i - 1] + fib[i - 2];

Notice that the loop computing those terms cannot start at 0 or at 1 — fib[0 - 2] is not a subscript. The
first two terms are given, and the loop starts at 2.

The task

Write a program fibonacci.cpp that uses an array of int to compute and print every Fibonacci number from
F(0) to F(59).

Example

$ ./fibonacci
F(0) = 0
F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5
...

Now read the output carefully — all of it, not just the beginning. Somewhere past two billion the numbers
stop being Fibonacci numbers. Find the first term that is wrong, and explain in a comment what happened and
why. Two questions will get you there: what is the largest value an int can hold, and what happens when a
sum exceeds it? The array is working perfectly — the problem is entirely in the type of its elements.

Task E. Passing arrays to functions

This is the heart of the lab. You have been passing functions ints, doubles and strings since Lab 2.
Arrays can be passed too, but they behave differently from everything else you have passed, and the
difference matters.

An array parameter has empty brackets

In the prototype and the definition, an array parameter is written with brackets and nothing inside them:

void printArray(int arr[], int count);

The brackets are empty because the function does not care how big the array is. That is not a convenience but
a limitation, and it leads straight to the second parameter.

The size does not come along

Passing an array tells the function where the elements are, not how many there are. The function cannot find
out on its own, so you must pass the count separately, and the function must trust you. Pass the wrong
number and it will read past the end of the array with nothing to stop it — exactly the spill.cpp
situation. In exchange, one function serves arrays of any size:

printArray(scores, 7);
printArray(temperatures, 365);

An array argument is not copied

When you pass an int, the function gets a copy; changing the parameter leaves the caller’s variable alone.
You saw this in Lab 3, and it is why reference parameters exist.

Arrays do not work that way. Passing an array does not copy it. The function operates on the caller’s
actual elements, so a function that assigns to its array parameter changes the caller’s array — permanently,
with no & anywhere in sight.

Sometimes that is what you want — a function that fills or sorts an array has to reach the caller’s data.
Often it is not, and a function meant only to look at your array can quietly wreck it.

Looking ahead. Why an array behaves this way — what is actually handed to the function — is the
subject of Chapter 10 and Lab 7. For now, take it as a rule: an int argument is copied, an array argument
is not.

`const` says “I will not touch it”

Put const in front of an array parameter and you promise the function will not modify the array. The
compiler holds you to it: any assignment to an element of a const parameter is a compile error.

int sumArray(const int arr[], int count);     // reads only
void doubleArray(int arr[], int count);       // modifies the caller's array

Try breaking the promise deliberately — put const on doubleArray and compile. You will get something like:

error: assignment of read-only location

(The message mentions const int*. Ignore the star for now; that is Lab 7’s business.)

The prototype becomes documentation the compiler checks — a reader can tell at a glance which functions are
safe to call on data they care about, and the promise cannot rot, because the code stops compiling the moment
someone breaks it. Mark every array parameter const unless the function’s job is to change the array.

The task

Write a program stats.cpp containing these five functions, with prototypes above main and definitions
below it:

void printArray(const int arr[], int count);
int  sumArray(const int arr[], int count);
int  getHighest(const int arr[], int count);
int  getLowest(const int arr[], int count);
void doubleArray(int arr[], int count);

main should define the seven scores from Task B as an initialized array, then use the functions to print
them, and report their sum, their average, the highest, and the lowest. Then call doubleArray and print the
array again to show that the caller’s data really did change.

For the average, divide the sum by the count — but a sum of int divided by an int is integer division,
which throws away the fraction. Convert first:

static_cast<double>(total) / count

For getHighest, assume arr[0] is the highest and loop from i = 1, replacing that guess whenever you find
something larger. Starting from the first element rather than from 0 or some invented “very small” number
means it works for any data, including arrays where every value is negative.

Example

$ ./stats
Scores:  88 72 95 61 79 100 84
Sum:     579
Average: 82.7143
Highest: 100
Lowest:  61
Doubled: 176 144 190 122 158 200 168

Task F. The National Commerce Bank case study

Textbook section 8.14.

National Commerce Bank has hired you as a contract programmer. An ATM asks a customer to key in a four-digit
PIN and stores each digit in an int array; the customer’s real PIN comes back from a database as another
four-element array. Your job is the function that decides whether the two match.

The specification. Write a Boolean function testPIN taking three arguments — the digits the customer
entered, the digits from the database, and the number of digits in a PIN — returning true if the two arrays
hold the same values in the same order. The digit count is a parameter rather than a hard-coded 4 so that the
function survives the bank deciding next year that PINs are six digits.

The pseudocode.

For each element in the first array
    Compare the element with the corresponding one in the 2nd array
    If the two elements contain different values
        Return false
    End If
End For   // If we made it this far the values are the same
Return true

Read that carefully, because the shape is not obvious. The function returns false from inside the loop the
moment it finds a mismatch, and returns true only after the loop finishes without finding one. The common
wrong version returns true from inside the loop on the first match, reporting success for any two PINs
that happen to share a first digit.

The task

Write a program pin.cpp containing testPIN and a main that tests it. Both array parameters should be
const — the function compares, it does not modify. Your main should define three PINs:

int pin1[NUM_DIGITS] = {2, 4, 1, 8};   // the base set of values
int pin2[NUM_DIGITS] = {2, 4, 6, 8};   // one element differs from pin1
int pin3[NUM_DIGITS] = {1, 2, 3, 4};   // every element differs from pin1

and make three calls: pin1 against pin2, pin1 against pin3, and pin1 against itself. Each call
should print SUCCESS when the function gives the right answer and ERROR when it does not.

Example

$ ./pin
SUCCESS: pin1 and pin2 are correctly identified as different.
SUCCESS: pin1 and pin3 are correctly identified as different.
SUCCESS: pin1 and pin1 are correctly reported to be the same.

Those three cases are not arbitrary. A function that always returns false passes the first two; a function
that always returns true passes the third. Only a correct one passes all three. Choosing test cases that
can each fail for a different reason is most of what testing is.

Task G. Counting with subscripts

Task C’s idea taken one step further. If a value is a small whole number, you can use the value itself as a
subscript, and an array becomes a set of counters. To tally forty rolls of a die, declare one counter per
face and zero them all:

int count[7] = {0};    // count[1] through count[6]; count[0] unused again

Then, for each roll, use the rolled number to select the counter to increment:

count[roll[i]]++;

Read that inner expression slowly. roll[i] is the value of the i-th roll — say, a 4. That 4 becomes the
subscript, so the statement increments count[4]. One line, no if, no switch, no six-way branch: the
same “the number is the subscript” idea as the months, and one of the things arrays are genuinely good at.

The task

Write a program tally.cpp that holds an initialized array of these forty die rolls:

int roll[NUM_ROLLS] = {3, 6, 1, 4, 4, 2, 5, 6, 3, 3,
                       1, 5, 2, 6, 4, 4, 1, 3, 5, 2,
                       6, 6, 3, 4, 2, 1, 5, 3, 4, 6,
                       2, 5, 4, 3, 1, 6, 4, 2, 5, 3};

counts how many times each face came up, and prints a histogram — one row per face, with a row of asterisks
as long as that face’s count, followed by the count itself.

Example

$ ./tally
| ***** (5)
| ****** (6)
| ******** (8)
| ******** (8)
| ****** (6)
| ******* (7)
total rolls: 40

That last line is the program checking its own work. The six counts have to add up to the number of rolls; if
they do not, either the tally loop or the histogram loop has an off-by-one in it. Print the total by summing
the counters, not by printing NUM_ROLLS — a check that cannot fail is not a check.

Task H (Bonus). Rock, Paper, Scissors

Textbook section 8.15.

Two players form a hand at the same time: a fist is rock, a flat palm is paper, two fingers are scissors.
Matching hands tie. Rock breaks scissors, scissors cut paper, paper wraps rock. Write a program that plays it
against the user.

Naming the choices

Represent the three hands as numbers 1, 2 and 3, and keep their names in an array — with element 0 unused, so
that the choice number is its own subscript:

const string name[4] = {" ", "rock", "paper", "scissors"};

Now name[playerChoice] is the word for whatever the player picked, with no arithmetic in between. That is
the third appearance of this trick in one lab, and it is not a coincidence: whenever a program has a small
fixed set of choices numbered from 1, an array indexed by the choice number is usually the tidiest thing
available.

Random numbers

You have not needed randomness before now. Two functions from <cstdlib> provide it.

rand() returns a non-negative pseudorandom integer from a very large range. Narrow it with the remainder
operator — rand() % 3 gives 0, 1 or 2, so this gives 1, 2 or 3:

computerChoice = 1 + rand() % 3;

The catch is the word pseudo. rand produces a fixed sequence computed from a starting value called the
seed, and the default seed never changes — so an unseeded program plays the identical game every run. Seed
it with something that differs between runs; the clock is the usual choice:

#include <cstdlib>
#include <ctime>

srand(time(0));      // time(0) is the current time in seconds

Call srand once, near the top of main, never inside the loop — time(0) returns the same value for a
whole second, so reseeding in a fast loop makes the numbers dramatically less random.

Try it. Comment out the srand line and run your finished program three times, making the same picks
each time. Three identical games. Worth seeing once, and it is why programs that need randomness for
anything serious do not use rand at all.

The task

Write a program rps.cpp that seeds the generator, then repeatedly asks the player to pick 1, 2, 3, or 0 to
quit. Each round, generate the computer’s choice, report both hands by name, and say who won. Keep the
running score in a three-element array — ties, player wins, computer wins — and print the final tally when the
player quits.

Example

$ ./rps

Pick 1 (rock), 2 (paper), 3 (scissors), or 0 to quit: 1
You picked rock, the computer picked scissors. You win.

Pick 1 (rock), 2 (paper), 3 (scissors), or 0 to quit: 2
You picked paper, the computer picked rock. You win.

Pick 1 (rock), 2 (paper), 3 (scissors), or 0 to quit: 3
You picked scissors, the computer picked scissors. A tie.

Pick 1 (rock), 2 (paper), 3 (scissors), or 0 to quit: 0

Final score -- you: 2, computer: 0, ties: 1

Your output will not match this one, and it should not — the computer’s hands come from the clock.

The winner test is worth a moment’s thought. A tie is easy. For the rest, there are exactly three ways the
player wins, and you can write them as one condition; everything else that is not a tie is a loss. Resist the
urge to write nine cases.

How to submit your programs

Submit through Gradescope

Write a separate program for each task and submit the source files:

edit-array.cpp    scores.cpp    months.cpp    fibonacci.cpp
stats.cpp         pin.cpp       tally.cpp     rps.cpp (bonus)

Submit scores.txt along with scores.cpp. Do not submit compiled executables.

Each program should start with a comment containing your name and a short description, for example:

/*
Author: your name
Course: CSCI-135
Instructor: their name
Assignment: Lab 6

Here, briefly, at least in one or a few sentences
describe what the program does.
*/

[comic C++ illustration]

Lab 6. Arrays: Many Values, One Name

Introduction

Declaring an array

Subscripts start at zero

The same brackets mean two different things

Arrays and loops belong together

Task A. Storing, printing, and editing

Example

What C++ does not check

Task B. Reading an array from a file

Opening a file

When the file is not there

Reading until the data runs out

The task

Example

Task C. Arrays as lookup tables

Leaving element 0 unused

The task

Example

Task D. A running table: Fibonacci numbers

The task

Example

Task E. Passing arrays to functions

An array parameter has empty brackets

The size does not come along

An array argument is not copied

const says “I will not touch it”

The task

Example

Task F. The National Commerce Bank case study

The task

Example

Task G. Counting with subscripts

The task

Example

Task H (Bonus). Rock, Paper, Scissors

Naming the choices

Random numbers

The task

Example

How to submit your programs

Submit through Gradescope

`const` says “I will not touch it”