Programming: Principles and Practice Using C++ (2014)

---

4.1 Computation

From one point of view, all that a program ever does is to compute; that is, it takes some inputs and produces some output. After all, we call the hardware on which we run the program a computer. This view is accurate and reasonable as long as we take a broad view of what constitutes input and output:

The input can come from a keyboard, from a mouse, from a touch screen, from files, from other input devices, from other programs, from other parts of a program. “Other input devices” is a category that contains most really interesting input sources: music keyboards, video recorders, network connections, temperature sensors, digital camera image sensors, etc. The variety is essentially infinite.

To deal with input, a program usually contains some data, sometimes referred to as its data structures or its state. For example, a calendar program may contain lists of holidays in various countries and a list of your appointments. Some of that data is part of the program from the start; other data is built up as the program reads input and collects useful information from it. For example, the calendar program will probably build your list of appointments from the input you give it. For the calendar, the main inputs are the requests to see the months and days you ask for (probably using mouse clicks) and the appointments you give it to keep track of (probably by typing information on your keyboard). The output is the display of calendars and appointments, plus the buttons and prompts for input that the calendar program writes on your screen.

Input comes from a wide variety of sources. Similarly, output can go to a wide variety of destinations. Output can be to a screen, to files, to network connections, to other output devices, to other programs, and to other parts of a program. Examples of output devices include network interfaces, music synthesizers, electric motors, light generators, heaters, etc.

From a programming point of view the most important and interesting categories are “to/from another program” and “to/from other parts of a program.” Most of the rest of this book could be seen as discussing that last category: how do we express a program as a set of cooperating parts and how can they share and exchange data? These are key questions in programming. We can illustrate that graphically:

The abbreviation I/O stands for “input/output.” In this case, the output from one part of code is the input for the next part. What such “parts of a program” share is data stored in main memory, on persistent storage devices (such as disks), or transmitted over network connections. By “parts of a program” we mean entities such as a function producing a result from a set of input arguments (e.g., a square root from a floating-point number), a function performing an action on a physical object (e.g., a function drawing a line on a screen), or a function modifying some table within the program (e.g., a function adding a name to a table of customers).

When we say “input” and “output” we generally mean information coming into and out of a computer, but as you see, we can also use the terms for information given to or produced by a part of a program. Inputs to a part of a program are often called arguments and outputs from a part of a program are often called results.

By computation we simply mean the act of producing some outputs based on some inputs, such as producing the result (output) 49 from the argument (input) 7 using the computation (function) square (see §4.5). As a possibly helpful curiosity, we note that until the 1950s a computer was defined as a person who did computations, such as an accountant, a navigator, or a physicist. Today, we simply delegate most computations to computers (machines) of various forms, of which the pocket calculator is among the simplest.

4.2 Objectives and tools

Our job as programmers is to express computations

• Correctly

• Simply

• Efficiently

Please note the order of those ideals: it doesn’t matter how fast a program is if it gives the wrong results. Similarly, a correct and efficient program can be so complicated that it must be thrown away or completely rewritten to produce a new version (release). Remember, useful programs will always be modified to accommodate new needs, new hardware, etc. Therefore a program — and any part of a program — should be as simple as possible to perform its task. For example, assume that you have written the perfect program for teaching basic arithmetic to children in your local school, and that its internal structure is a mess. Which language did you use to communicate with the children? English? English and Spanish? What if I’d like to use it in Finland? In Kuwait? How would you change the (natural) language used for communication with a child? If the internal structure of the program is a mess, the logically simple (but in practice almost always very difficult) operation of changing the natural language used to communicate with users becomes insurmountable.

Concerns about correctness, simplicity, and efficiency become ours the minute we start writing code for others and accept the responsibility to do that well; that is, we must accept that responsibility when we decide to become professionals. In practical terms, this means that we can’t just throw code together until it appears to work; we must concern ourselves with the structure of code. Paradoxically, concerns for structure and “quality of code” are often the fastest ways of getting something to work. When programming is done well, such concerns minimize the need for the most frustrating part of programming: debugging; that is, good program structure during development can minimize the number of mistakes made and the time needed to search for such errors and to remove them.

Our main tool for organizing a program — and for organizing our thoughts as we program — is to break up a big computation into many little ones. This technique comes in two variations:

• Abstraction: Hide details that we don’t need to use a facility (“implementation details”) behind a convenient and general interface. For example, rather than considering the details of how to sort a phone book (thick books have been written about how to sort), we just call the sortalgorithm from the C++ standard library. All we need to know to sort is how to invoke (call) that algorithm, so we can write sort(b) where b refers to the phone book; sort() is a variant (§21.9) of the standard library sort algorithm (§21.8, §B.5.4) defined in std_library.h. Another example is the way we use computer memory. Direct use of memory can be quite messy, so we access it through typed and named variables (§3.2), standard library vectors (§4.6, Chapters 17-19), maps (Chapter 21), etc.

• “Divide and conquer”: Here we take a large problem and divide it into several little ones. For example, if we need to build a dictionary, we can separate that job into three: read the data, sort the data, and output the data. Each of the resulting problems is significantly smaller than the original.

Why does this help? After all, a program built out of parts is likely to be slightly larger than a program where everything is optimally merged together. The reason is that we are not very good at dealing with large problems. The way we actually deal with those — in programming and elsewhere — is to break them down into smaller problems, and we keep breaking those into even smaller parts until we get something simple enough to understand and solve. In terms of programming, you’ll find that a 1000-line program has far more than ten times as many errors as a 100-line program, so we try to compose the 1000-line program out of parts with fewer than 100 lines. For large programs, say 10,000,000 lines, applying abstraction and divide-and-conquer is not just an option, it’s an essential requirement. We simply cannot write and maintain large monolithic programs. One way of looking at the rest of this book is as a long series of examples of problems that need to be broken up into smaller parts together with the tools and techniques needed to do so.

When we consider dividing up a program, we must always consider what tools we have available to express the parts and their communications. A good library, supplying useful facilities for expressing ideas, can crucially affect the way we distribute functionality into different parts of a program. We cannot just sit back and “imagine” how best to partition a program; we must consider what libraries we have available to express the parts and their communication. It is early days yet, but not too soon to point out that if you can use an existing library, such as the C++ standard library, you can save yourself a lot of work, not just on programming but also on testing and documentation. The iostreams save us from having to directly deal with the hardware’s input/output ports. This is a first example of partitioning a program using abstraction. Every new chapter will provide more examples.

Note the emphasis on structure and organization: you don’t get good code just by writing a lot of statements. Why do we mention this now? At this stage you (or at least many readers) have little idea about what code is, and it will be months before you are ready to write code upon which other people could depend for their lives or livelihood. We mention it to help you get the emphasis of your learning right. It is very tempting to dash ahead, focusing on the parts of programming that — like what is described in the rest of this chapter — are concrete and immediately useful and to ignore the “softer,” more conceptual parts of the art of software development. However, good programmers and system designers know (often having learned it the hard way) that concerns about structure lie at the heart of good software and that ignoring structure leads to expensive messes. Without structure, you are (metaphorically speaking) building with mud bricks. It can be done, but you’ll never get to the fifth floor (mud bricks lack the structural strength for that). If you have the ambition to build something reasonably permanent, you pay attention to matters of code structure and organization along the way, rather than having to come back and learn them after failures.

4.3 Expressions

The most basic building block of programs is an expression. An expression computes a value from a number of operands. The simplest expression is simply a literal value, such as 10, 'a', 3.14, or "Norah".

Names of variables are also expressions. A variable represents the object of which it is the name. Consider:

// compute area:
int length = 20; // a literal integer (used to initialize a variable)
int width = 40;
int area = length*width; // a multiplication

Here the literals 20 and 40 are used to initialize the variables length and width. Then, length and width are multiplied; that is, we multiply the values found in length and width. Here, length is simply shorthand for “the value found in the object named length.” Consider also

length = 99; // assign 99 to length

Here, as the left-hand operand of the assignment, length means “the object named length,” so that the assignment expression is read “Put 99 into the object named by length.” We distinguish between length used on the left-hand side of an assignment or an initialization (“the lvalue of length” or “the object named by length”) and length used on the right-hand side of an assignment or initialization (“the rvalue of length,” “the value of the object named by length,” or just “the value of length”). In this context, we find it useful to visualize a variable as a box labeled by its name:

That is, length is the name of an object of type int containing the value 99. Sometimes (as an lvalue) length refers to the box (object) and sometimes (as an rvalue) length refers to the value in that box.

We can make more complicated expressions by combining expressions using operators, such as + and *, in just the way that we are used to. When needed, we can use parentheses to group expressions:

int perimeter = (length+width)*2; // add then multiply

Without parentheses, we’d have had to say

int perimeter = length*2+width*2;

which is clumsy, and we might even have made this mistake:

int perimeter = length+width*2; // add width*2 to length

This last error is logical and cannot be found by the compiler. All the compiler sees is a variable called perimeter initialized by a valid expression. If the result of that expression is nonsense, that’s your problem. You know the mathematical definition of a perimeter, but the compiler doesn’t.

The usual mathematical rules of operator precedence apply, so length+width*2 means length+(width*2). Similarly a*b+c/d means (a*b)+(c/d) and not a*(b+c)/d. See §A.5 for a precedence table.

The first rule for the use of parentheses is simply “If in doubt, parenthesize,” but please do learn enough about expressions so that you are not in doubt about a*b+c/d. Overuse of parentheses, as in (a*b)+(c/d), decreases readability.

Why should you care about readability? Because you and possibly others will read your code, and ugly code slows down reading and comprehension. Ugly code is not just hard to read, it is also much harder to get correct. Ugly code often hides logical errors. It is slower to read and makes it harder to convince yourself — and others — that the ugly code is correct. Don’t write absurdly complicated expressions such as

a*b+c/d*(e-f/g)/h+7 // too complicated

and always try to choose meaningful names.

4.3.1 Constant expressions

Programs typically use a lot of constants. For example, a geometry program might use pi and an inch-to-centimeter conversion program will use a conversion factor such as 2.54. Obviously, we want to use meaningful names for those constants (as we did for pi; we didn’t say 3.14159). Similarly, we don’t want to change those constants accidentally. Consequently, C++ offers the notion of a symbolic constant, that is, a named object to which you can’t give a new value after it has been initialized. For example:

constexpr double pi = 3.14159;
pi = 7; // error: assignment to constant
double c = 2*pi*r; // OK: we just read pi; we don’t try to change it

Such constants are useful for keeping code readable. You might have recognized 3.14159 as an approximation to pi if you saw it in some code, but would you have recognized 299792458? Also, if someone asked you to change some code to use pi with the precision of 12 digits for your computation, you could search for 3.14 in your code, but if someone incautiously had used 22/7, you probably wouldn’t find it. It would be much better just to change the definition of pi to use the more appropriate value:

constexpr double pi = 3.14159265359;

Consequently, we prefer not to use literals (except very obvious ones, such as 0 and 1) in most places in our code. Instead, we use constants with descriptive names. Non-obvious literals in code (outside definitions of symbolic constants) are derisively referred to as magic constants.

In some places, such as case labels (§4.4.1.3), C++ requires a constant expression, that is, an expression with an integer value composed exclusively of constants. For example:

constexpr int max = 17; // a literal is a constant expression
int val = 19;

max+2 // a constant expression (a const int plus a literal)
val+2 // not a constant expression: it uses a variable

And by the way, 299792458 is one of the fundamental constants of the universe: the speed of light in vacuum measured in meters per second. If you didn’t instantly recognize that, why would you expect not to be confused and slowed down by other literals embedded in code? Avoid magic constants!

A constexpr symbolic constant must be given a value that is known at compile time. For example:

constexpr int max = 100;
void use(int n)
{
constexpr int c1 = max+7; // OK: c1 is 107
constexpr int c2 = n+7; // error: we don’t know the value of c2
// ...
}

To handle cases where the value of a “variable” that is initialized with a value that is not known at compile time but never changes after initialization, C++ offers a second form of constant (a const):

constexpr int max = 100;
void use(int n)
{
constexpr int c1 = max+7; // OK: c1 is 107
const int c2 = n+7; // OK, but don’t try to change the value of c2
// ...
c2 = 7; // error: c2 is a const
}

Such “const variables” are very common for two reasons:

• C++98 did not have constexpr, so people used const.

• “Variables” that are not constant expressions (their value is not known at compile time) but do not change values after initialization are in themselves widely useful.

4.3.2 Operators

We just used the simplest operators. However, you will soon need more as you want to express more complex operations. Most operators are conventional, so we’ll just explain them later as needed and you can look up details if and when you find a need. Here is a list of the most common operators:

We used lval (short for “value that can appear on the left-hand side of an assignment”) where the operator modifies an operand. You can find a complete list in §A.5.

For examples of the use of the logical operators && (and), || (or), and ! (not), see §5.5.1, §7.7, §7.8.2, and §10.4.

Note that a<b<c means (a<b)<c and that a<b evaluates to a Boolean value: true or false. So, a<b<c will be equivalent to either true<c or false<c. In particular, a<b<c does not mean “Is b between a and c?” as many have naively (and not unreasonably) assumed. Thus, a<b<c is basically a useless expression. Don’t write such expressions with two comparison operations, and be very suspicious if you find such an expression in someone else’s code — it is most likely an error.

An increment can be expressed in at least three ways:

++a
a+=1
a=a+1

Which notation should we use? Why? We prefer the first version, ++a, because it more directly expresses the idea of incrementing. It says what we want to do (increment a) rather than how to do it (add 1 to a and then write the result to a). In general, a way of saying something in a program is better than another if it more directly expresses an idea. The result is more concise and easier for a reader to understand. If we wrote a=a+1, a reader could easily wonder whether we really meant to increment by 1. Maybe we just mistyped a=b+1, a=a+2, or even a=a-1; with ++a there are far fewer opportunities for such doubts. Please note that this is a logical argument about readability and correctness, not an argument about efficiency. Contrary to popular belief, modern compilers tend to generate exactly the same code from a=a+1 as for ++a when a is one of the built-in types. Similarly, we prefer a*=scale over a=a*scale.

4.3.3 Conversions

We can “mix” different types in expressions. For example, 2.5/2 is a double divided by an int. What does this mean? Do we do integer division or floating-point division? Integer division throws away the remainder; for example, 5/2 is 2. Floating-point division is different in that there is no remainder to throw away; for example, 5.0/2.0 is 2.5. It follows that the most obvious answer to the question “Is 2.5/2 integer division or floating-point division?” is “Floating-point, of course; otherwise we’d lose information.” We would prefer the answer 1.25 rather than 1, and 1.25 is what we get. The rule (for the types we have presented so far) is that if an operator has an operand of type double, we use floating-point arithmetic yielding a double result; otherwise, we use integer arithmetic yielding an int result. For example:

5/2 is 2 (not 2.5)

2.5/2 means 2.5/double(2), that is, 1.25

'a'+1 means int{'a'}+1

The notations type(value) and type{value} mean “convert value to type as if you were initializing a variable of type type with the value value.” In other words, if necessary, the compiler converts (“promotes”) int operands to doubles or char operands to ints. The type{value} notation prevents narrowing (§3.9.2), but the type(value) notation does not. Once the result has been calculated, the compiler may have to convert it (again) to use it as an initializer or the right hand of an assignment. For example:

double d = 2.5;
int i = 2;
double d2 = d/i; // d2 == 1.25
int i2 = d/i; // i2 == 1
int i3 {d/i}; // error: double -> int conversion may narrow (§3.9.2)

d2 = d/i; // d2 == 1.25
i2 = d/i; // i2 == 1

Beware that it is easy to forget about integer division in an expression that also contains floating-point operands. Consider the usual formula for converting degrees Celsius to degrees Fahrenheit: f = 9/5 * c + 32. We might write

double dc;
cin >> dc;
double df = 9/5*dc+32; // beware!

Unfortunately, but quite logically, this does not represent an accurate temperature scale conversion: the value of 9/5 is 1 rather than the 1.8 we might have hoped for. To get the code mathematically correct, either 9 or 5 (or both) will have to be changed into a double. For example:

double dc;
cin >> dc;
double df = 9.0/5*dc+32; // better

4.4 Statements

An expression computes a value from a set of operands using operators like the ones mentioned in §4.3. What do we do when we want to produce several values? When we want to do something many times? When we want to choose among alternatives? When we want to get input or produce output? In C++, as in many languages, you use language constructs called statements to express those things.

So far, we have seen two kinds of statements: expression statements and declarations. An expression statement is simply an expression followed by a semicolon. For example:

a = b;
++b;

Those are two expression statements. Note that the assignment = is an operator so that a=b is an expression and we need the terminating semicolon to make a=b; a statement. Why do we need those semicolons? The reason is largely technical. Consider:

a = b ++ b; // syntax error: missing semicolon

Without the semicolon, the compiler doesn’t know whether we mean a=b++; b; or a=b; ++b;. This kind of problem is not restricted to computer languages; consider the exclamation “man eating tiger!” Who is eating whom? Punctuation exists to eliminate such problems, for example, “man-eating tiger!”

When statements follow each other, the computer executes them in the order in which they are written. For example:

int a = 7;
cout << a << '\n';

Here the declaration, with its initialization, is executed before the output expression statement.

In general, we want a statement to have some effect. Statements without effect are typically useless. For example:

1+2; // do an addition, but don’t use the sum
a*b; // do a multiplication, but don’t use the product

Such statements without effects are typically logical errors, and compilers often warn against them. Thus, expression statements are typically assignments, I/O statements, or function calls.

We will mention one more type of statement: the “empty statement.” Consider the code:

if (x == 5);
{ y = 3; }

This looks like an error, and it almost certainly is. The ; in the first line is not supposed to be there. But, unfortunately, this is a legal construct in C++. It is called an empty statement, a statement doing nothing. An empty statement before a semicolon is rarely useful. In this case, it has the unfortunate consequence of allowing what is almost certainly an error to be acceptable to the compiler, so it will not alert you to the error and you will have that much more difficulty finding it.

What will happen if this code is run? The compiler will test x to see if it has the value 5. If this condition is true, the following statement (the empty statement) will be executed, with no effect. Then the program continues to the next line, assigning the value 3 to y (which is what you wanted to have happen if x equals 5). If, on the other hand, x does not have the value 5, the compiler will not execute the empty statement (still no effect) and will continue as before to assign the value 3 to y (which is not what you wanted to have happen unless x equals 5). In other words, theif-statement doesn’t matter; y is going to get the value 3 regardless. This is a common error for novice programmers, and it can be difficult to spot, so watch out for it.

The next section is devoted to statements used to alter the order of evaluation to allow us to express more interesting computations than those we get by just executing statements in the order in which they were written.

4.4.1 Selection

In programs, as in life, we often have to select among alternatives. In C++, that is done using either an if-statement or a switch-statement.

4.4.1.1 if-statements

The simplest form of selection is an if-statement, which selects between two alternatives. For example:

int main()
{
int a = 0;
int b = 0;
cout << "Please enter two integers\n";
cin >> a >> b;

if (a<b) // condition
// 1st alternative (taken if condition is true):
cout << "max(" << a << "," << b <<") is " << b <<"\n";
else
// 2nd alternative (taken if condition is false):
cout << "max(" << a << "," << b <<") is " << a << "\n";
}

An if-statement chooses between two alternatives. If its condition is true, the first statement is executed; otherwise, the second statement is. This notion is simple. Most basic programming language features are. In fact, most basic facilities in a programming language are just new notation for things you learned in primary school — or even before that. For example, you were probably told in kindergarten that to cross the street at a traffic light, you had to wait for the light to turn green: “If the traffic light is green, go” and “If the traffic light is red, wait.” In C++ that becomes something like

if (traffic_light==green) go();

and

if (traffic_light==red) wait();

So, the basic notion is simple, but it is also easy to use if-statements in a too-simple-minded manner. Consider what’s wrong with this program (apart from leaving out the #include as usual):

// convert from inches to centimeters or centimeters to inches
// a suffix ‘i’ or ‘c’ indicates the unit of the input

int main()
{
constexpr double cm_per_inch = 2.54; // number of centimeters in
// an inch
double length = 1; // length in inches or
// centimeters
char unit = 0;
cout<< "Please enter a length followed by a unit (c or i):\n";
cin >> length >> unit;
if (unit == 'i')
cout << length << "in == " << cm_per_inch*length << "cm\n";
else
cout << length << "cm == " << length/cm_per_inch << "in\n";
}

Actually, this program works roughly as advertised: enter 1i and you get 1in == 2.54cm; enter 2.54c and you’ll get 2.54cm == 1in. Just try it; it’s good practice.

The snag is that we didn’t test for bad input. The program assumes that the user enters proper input. The condition unit=='i' distinguishes between the case where the unit is 'i' and all other cases. It never looks for a 'c'.

What if the user entered 15f (for feet) “just to see what happens”? The condition (unit == 'i') would fail and the program would execute the else part (the second alternative), converting from centimeters to inches. Presumably that was not what we wanted when we entered 'f'.

We must always test our programs with “bad” input, because someone will eventually — intentionally or accidentally — enter bad input. A program should behave sensibly even if its users don’t.

Here is an improved version:

// convert from inches to centimeters or centimeters to inches
// a suffix ‘i’ or ‘c’ indicates the unit of the input
// any other suffix is an error
int main()
{
constexpr double cm_per_inch = 2.54; // number of centimeters in
// an inch
double length = 1; // length in inches or
// centimeters
char unit = ' '; // a space is not a unit
cout<< "Please enter a length followed by a unit (c or i):\n";
cin >> length >> unit;

if (unit == 'i')
cout << length << "in == " << cm_per_inch*length << "cm\n";
else if (unit == 'c')
cout << length << "cm == " << length/cm_per_inch << "in\n";
else
cout << "Sorry, I don't know a unit called '" << unit << "'\n";
}

We first test for unit=='i' and then for unit=='c' and if it isn’t (either) we say, “Sorry.” It may look as if we used an “else-if-statement,” but there is no such thing in C++. Instead, we combined two if-statements. The general form of an if-statement is

if ( expression ) statement else statement

That is, an if, followed by an expression in parentheses, followed by a statement, followed by an else, followed by a statement. What we did was to use an if-statement as the else part of an if-statement:

if ( expression ) statement else if ( expression ) statement else statement

For our program that gives this structure:

if (unit == 'i')
. . . // 1st alternative
else if (unit == 'c')
. . . // 2nd alternative
else
. . . // 3rd alternative

In this way, we can write arbitrarily complex tests and associate a statement with each alternative. However, please remember that one of the ideals for code is simplicity, rather than complexity. You don’t demonstrate your cleverness by writing the most complex program. Rather, you demonstrate competence by writing the simplest code that does the job.