Programming

Abstractions in
C ++

Eric S. Roberts
Stanford University
Autumn Quarter 2012
Foreword
This text represents a major revision of the course reader that weve been using at
Stanford for the last several years. The primary goal of the revision was to bring the
approach more closely in line with the way C++ is used in industry, which will in
turn make it easier to export Stanfords approach to teaching data structures to a
larger fraction of schools. Even though this quarters draft is reasonably complete,
the text remains somewhat rough. In particular, these chapters have not yet had the
benefit of the wonderful copyediting service that my wife Lauren Rusk has provided
for all my books.

This textbook has had an interesting evolutionary history that in some ways
mirrors the genesis of the C++ language itself. Just as Bjarne Stroustrups first
version of C++ was implemented on top of a C language base, this reader began its
life as my textbook Programming Abstractions in C (Addison-Wesley, 1998). In
2002-03, Julie Zelenski updated it for use with the C++ programming language,
which we began using in CS106 B and CS106 X during that year. Although the
revised text worked fairly well at the outset, CS106 B and CS106 X have evolved in
recent years so that their structure no longer tracks the organization of the book. In
2009, I embarked on a comprehensive process of rewriting the book so that students
in these courses can use it as both a tutorial and a reference. As always, that process
takes a considerable amount of time, and there are almost certainly some sections of
the book that need a substantial rewrite.

I want to thank my colleagues at Stanford over the last several years, starting
with Julie Zelenski for her extensive work on the initial C++ revision. My
colleagues Keith Schwarz, Jerry Cain, Stephen Cooper, and Mehran Sahami have
all made important contributions to the revision. I also need to express my thanks to
several generations of section leaders and so many students over the years, all of
whom have helped make it so exciting to teach this wonderful material. Finally, I
want to thank the students in CS106 B in winter quarter 2011-12 who put up with a
partially finished reader and contributed many error reports and suggestions.

Ive always believed that programming is one of the most challenging and
exciting intellectual activities that humans have ever discovered. By staying close
to the machine, C++ gives you all the freedom you need to build applications that
take advantage of the full power of modern computing. I hope you all enjoy the
ride.

i
 Contents
1 Overview of C++ 1
1.1 Your first C++ program 2
1.2 The history of C++ 3
1.3 The structure of a C++ program 6
1.4 Variables 14
1.5 Data types 19
1.6 Expressions 26
1.7 Statements 36
Summary 47
Review questions 48
Exercises 50

2 Functions and Libraries 55

2.1 The idea of a function 56
2.2 Libraries 59
2.3 Defining functions in C++ 61
2.4 The mechanics of function calls 65
2.5 Reference parameters 73
2.6 Interfaces and implementations 78
2.7 Principles of interface design 85
2.8 Designing a random number library 90
2.9 Introduction to the Stanford libraries 107
Summary 112
Review questions 114
Exercises 115

3 Strings 125
3.1 Using strings as abstract values 126
3.2 String operations 129
3.3 The <cctype> library 137
3.4 Modifying the contents of a string 138
3.5 The legacy of C-style strings 139
3.6 Writing string applications 140
3.7 The strlib.h library 146
Summary 147
Review questions 148
Exercises 149

ii
4 Streams 159
4.1 Using strings as abstract values 160
4.2 Formatted input 165
4.3 Data files 167
4.4 Class hierarchies 181
4.5 The simpio.h and filelib.h libraries 186
Summary 188
Review questions 189
Exercises 190

5 Collections 195
5.1 The Vector class 197
5.2 The Stack class 211
5.3 The Queue class 217
5.4 The Map class 226
5.5 The Set class 232
5.6 Iterating over a collection 236
Summary 243
Review questions 245
Exercises 246

6 Designing Classes 261

6.1 Representing points 262
6.2 Operator overloading 268
6.3 Rational numbers 281
6.4 Designing a token scanner class 292
6.5 Encapsulating programs as classes 301
Summary 303
Review questions 305
Exercises 306

iii
 7 Introduction to Recursion 315
7.1 A simple example of recursion 316
7.2 The factorial function 318
7.3 The Fibonacci function 325
7.4 Checking palindromes 332
7.5 The binary search algorithm 335
7.6 Mutual recursion 336
7.7 Thinking recursively 338
Summary 340
Review questions 342
Exercises 344

8 Recursive Strategies 349

8.1 The Towers of Hanoi 350
8.2 The subset-sum problem 361
8.3 Generating permutations 364
8.4 Graphical recursion 368
Summary 375
Review questions 375
Exercises 376

9 Backtracking Algorithms 389

9.1 Recursive backtracking in a maze 390
9.2 Backtracking and games 400
9.3 The minimax algorithm 409
Summary 415
Review questions 416
Exercises 417

10 Algorithmic Analysis 429

10.1 The sorting problem 430
10.2 Computational complexity 435
10.3 Recursion to the rescue 443
10.4 Standard complexity classes 449
10.5 The Quicksort algorithm 452
10.6 Mathematical induction 458
Summary 462
Review questions 463
Exercises 466

iv
11 Pointers and Arrays 473
11.1 The structure of memory 474
11.2 Pointers 484
11.3 Arrays 494
11.4 Pointer arithmetic 500
Summary 506
Review questions 508
Exercises 510

12 Dynamic Memory Management 515

12.1 Dynamic allocation and the heap 516
12.2 Linked lists 519
12.3 Freeing memory 523
12.4 Defining a CharStack class 527
12.5 Heap-stack diagrams 536
12.6 Unit testing 543
12.7 Copying objects 546
12.8 The uses of const 550
12.9 Efficiency of the CharStack class 558
Summary 560
Review questions 562
Exercises 564

13 Efficiency and Representation 569

13.1 Software patterns for editing text 570
13.2 Designing a simple text editor 572
13.3 An array-based implementation 579
13.4 A stack-based implementation 586
13.5 A list-based implementation 591
Summary 607
Review questions 608
Exercises 610

v
 14 Linear Structures 615
14.1 Templates 616
14.2 Implementing stacks 619
14.3 Implementing queues 634
14.4 Implementing vectors 649
14.5 Integrating prototypes and code 656
Summary 657
Review questions 658
Exercises 659

15 Maps 663
15.1 Implementing maps using vectors 664
15.2 Lookup tables 668
15.3 Hashing 671
15.4 Implementing the HashMap class 682
Summary 683
Review questions 684
Exercises 685

16 Trees 689
16.1 Family trees 691
16.2 Binary search trees 693
16.3 Balanced trees 706
16.4 Implementing maps using BSTs 717
16.5 Partially ordered trees 719
Summary 722
Review questions 724
Exercises 727

17 Sets 737
17.1 Sets as a mathematical abstraction 738
17.2 Expanding the set interface 742
17.3 Implementation strategies for sets 747
17.4 Optimizing sets of small integers 753
Summary 761
Review questions 762
Exercises 764

vi
18 Graphs 767
18.1 The structure of a graph 768
18.2 Representation strategies 772
18.3 A low-level graph abstraction 776
18.4 Graph traversals 783
18.5 Defining a Graph class 789
18.6 Finding shortest paths 804
18.7 Algorithms for searching the web 808
Summary 812
Review questions 813
Exercises 815

19 Inheritance 823
19.1 Simple inheritance 824
19.2 A hierarchy of graphical shapes 832
19.3 A class hierarchy for expressions 841
19.4 Parsing an expression 861
19.5 Multiple inheritance 870
Summary 873
Review questions 875
Exercises 877

20 Strategies for iteration 885

20.1 Using iterators 886
20.2 Using functions as data values 890
20.3 Encapsulating data with functions 899
20.4 The STL algorithms library 904
20.5 Functional programming in C++ 907
20.6 Implementing iterators 911
Summary 918
Review questions 920
Exercises 921

A Stanford library interfaces 927

Index 1025

vii
Chapter 1
An Overview of C++

Out of these various experiments come programs. This is our

experience: programs do not come out of the minds of one person
or two people such as ourselves, but out of day-to-day work.
Stokely Carmichael and Charles V. Hamilton,
Black Power, 1967
2 Overview of C++

In Lewis Carrolls Alices Adventures in Wonderland, the King asks the White
Rabbit to begin at the beginning and go on till you come to the end: then stop.
Good advice, but only if youre starting from the beginning. This book is designed
for a second course in computer science and therefore assumes that you have
already begun your study of programming. At the same time, because first courses
vary considerably in what they cover, it is difficult to rely on any specific material.
Some of you, for example, will already understand C++ control structures from
prior experience with closely related languages such as C or Java. For others,
however, the structure of C++ will seem unfamiliar. Because of this disparity in
background, the best approach is to adopt the Kings advice. This chapter therefore
begins at the beginning and introduces you to those parts of the C++ language
you will need to write simple programs.

1.1 Your first C++ program

As you will learn in more detail in the following section, C++ is an extension of an
extremely successful programming language called C, which appeared in the early
1970s. In the book that serves as Cs defining document, The C Programming
Language, Brian Kernighan and Dennis Ritchie offer the following advice on the
first page of Chapter 1:

The only way to learn a new programming language is by

writing programs in it. The first program to write is the same
for all languages:
Print the words
hello, world
This is the big hurdle; to leap over it you have to be able to
create the program text somewhere, compile it successfully,
load it, run it, and find out where the output went. With these
mechanical details mastered, everything else is comparatively
easy.

If you were to rewrite it in C++, the Hello World program would end up looking
something like the code in Figure 1-1.

At this point, the important thing is not to understand exactly what all of the
lines in this program mean. There is plenty of time to master those details later.
Your missionand you should decide to accept itis to get the HelloWorld
program running. Type in the program exactly as it appears in Figure 1-1 and then
figure out what you need to do to make it work. The exact steps you need to use
depend on the programming environment youre using to create and run C++
programs. If you are using this textbook for a class, your instructor will presumably
provide some reference material on the programming environments you are
 1.1 Your first C++ program 3

expected to use. If you are reading this book on your own, youll need to refer to
the documentation that comes with whatever programming environment youre
using for C++.

When you get all of these details worked out, you should see the output from the
HelloWorld program on a window somewhere on your computer screen. On the
Apple Macintosh on which I prepared this book, that window looks like this:

On your computer, the window will probably have a somewhat different appearance
and may include additional status messages along with your programs cheery
hello, world greeting. But the message will be there. And although it may not be
true that everything else is comparatively easy as Kernighan and Ritchie suggest,
you will have achieved a significant milestone.

1.2 The history of C++

In the early days of computing, programs were written in machine language, which
consists of the primitive instructions that can be executed directly by the machine.
Programs written in machine language are difficult to understand, mostly because
the structure of machine language reflects the design of the hardware rather than the
needs of programmers. Worse still, each type of computing hardware has its own
4 Overview of C++

machine language, which means that a program written for one machine will not run
on other types of hardware.

In the mid-1950s, a group of programmers under the direction of John Backus at

IBM had an idea that profoundly changed the nature of computing. Would it be
possible, Backus and his colleagues wondered, to write programs that resembled the
mathematical formulas they were trying to compute and have the computer itself
translate those formulas into machine language? In 1955, this team produced the
initial version of FORTRAN (whose name is a contraction of formula translation),
which was the first example of a higher-level programming language.

Since that time, many new programming languages have been invented, most of
which build on previous languages in an evolutionary way. C++ represents the
joining of two branches in that evolution. One of its ancestors is a language called
C, which was designed at Bell Laboratories by Dennis Ritchie in 1972 and then
later revised and standardized by the American National Standards Institute (ANSI)
in 1989. But C++ also descends from a family of languages designed to support a
different style of programming that has dramatically changed the nature of software
development in recent years.

The object-oriented paradigm

Over the last two decades, computer science and programming have gone through
something of a revolution. Like most revolutionswhether political upheavals or
the conceptual restructurings that Thomas Kuhn describes in his 1962 book The
Structure of Scientific Revolutionsthis change has been driven by the emergence
of an idea that challenges an existing orthodoxy. Initially, the two ideas compete,
and, at least for a while, the old order maintains its dominance. Over time,
however, the strength and popularity of the new idea grows, until it begins to
displace the older idea in what Kuhn calls a paradigm shift. In programming, the
old order is represented by the procedural paradigm, in which programs consist of
a collection of procedures and functions that operate on data. The new model is
called the object-oriented paradigm, in which programs are viewed instead as a
collection of data objects that embody particular characteristics and behavior.

The idea of object-oriented programming is not really all that new. The first
object-oriented language was SIMULA, a language for coding simulations designed
by the Scandinavian computer scientists Ole-Johan Dahl and Kristen Nygaard in
1967. With a design that was far ahead of its time, SIMULA anticipated many of
the concepts that later became commonplace in programming, including the concept
of abstract data types and much of the modern object-oriented paradigm. In fact,
much of the terminology used to describe object-oriented languages comes from the
original 1967 report on SIMULA.
 1.2 The history of C++ 5

Unfortunately, SIMULA did not generate a great deal of interest in the years
after its introduction. The first object-oriented language to gain any significant
following within the computing profession was Smalltalk, which was developed at
the Xerox Palo Alto Research Center in the late 1970s. The purpose of Smalltalk,
which is described in the book Smalltalk-80: The Language and Its Implementation
by Adele Goldberg and David Robson, was to make programming accessible to a
wider audience. As such, Smalltalk was part of a larger effort at Xerox PARC that
gave rise to much of the modern user-interface technology that is now standard on
personal computers.

Despite many attractive features and a highly interactive user environment that
simplifies the programming process, Smalltalk never achieved much commercial
success. The profession as a whole took an interest in object-oriented programming
only when the central ideas were incorporated into variants of C, which had already
become an industry standard. Although there were several parallel efforts to design
an object-oriented language based on C, the most successful was the language C++,
which was developed by Bjarne Stroustrup at AT&T Bell Laboratories in the early
1980s. C++ includes standard C as a subset, which makes it possible to integrate
C++ code into existing C programs in a gradual, evolutionary way.

Although object-oriented languages have gained some of their popularity at the

expense of procedural ones, it would be a mistake to regard the object-oriented and
procedural paradigms as mutually exclusive. Programming paradigms are not so
much competitive as they are complementary. The object-oriented and the
procedural paradigmalong with other important paradigms such as the functional
programming style embodied in LISPall have important applications in practice.
Even within the context of a single application, you are likely to find a use for more
than one approach. As a programmer, you must master many different paradigms,
so that you can use the conceptual model that is most appropriate to the task at
hand.

The compilation process

When you write a program in C++, your first step is to create a file that contains the
text of the program, which is called a source file. Before you can run your
program, you need to translate the source file into an executable form. The first
step in that process is to invoke a program called a compiler, which translates the
source file into an object file containing the corresponding machine-language
instructions. This object file is then combined with other object files to produce an
executable file that can be run on the system. The other object files typically
include predefined object files called libraries that contain the machine-language
instructions for various operations commonly required by programs. The process of
6 Overview of C++

combining all the individual object files into an executable file is called linking.
The steps in the compilation process are illustrated in Figure 1-2.

As noted in the discussion of the HelloWorld program earlier in this chapter,

the specific details of the compilation process vary from one machine to another.
There is no way that a general textbook like this can tell you exactly what
commands you should use to run a program on your system. The good news is that
the C++ programs themselves will look the same. One of the advantages of
programming in a higher-level language like C++ is that doing so allows you to
ignore the particular characteristics of the hardware and create programs that will
run on many different machines.

1.3 The structure of a C++ program

The best way to get a feeling for the C++ programming language is to look at some
sample programs, even before you understand the details of the language. The
HelloWorld program is a start, but it is so simple that it doesnt include many of
the features youd expect to see in a program. Since this book is designed for a
second course in computer science, youve almost certainly written programs that
read input from the user, store values in variables, use loops to perform repeated
calculations, and make use of subsidiary functions to simplify the structure of the
 1.3 The structure of a C++ program 7

program. The HelloWorld program does none of these things. To illustrate more
of the features of C++, Figure 1-3 shows the code for a program that lists powers of
two along with some annotations that describe the various parts of the program.
8 Overview of C++

When you run the PowersOfTwo program shown in Figure 1-3, the computer
begins by asking you for an exponent limit, which specifies how many powers of
two the program should generate. If you type in 8, for example, the program will
generate a list of the powers of two up to 28, as follows:

This screen image shows what happens if you execute the PowersOfTwo program.
Such images are called sample runs. In each sample run, input from the user
appears in blue so that it is easy to distinguish input data from the output generated
by the program.

As the annotations in Figure 1-3 indicate, the PowersOfTwo program is divided

into several components, which are discussed in the next few sections.

Comments
Much of the text in Figure 1-3 consists of English-language comments. A comment
is text that is ignored by the compiler but which nonetheless conveys information to
other programmers. A comment consists of text enclosed between the markers
/* and */ and may continue over several lines. Alternatively, you can also specify
single-line comments, which begin with the characters // and extend through the
end of the line. This book uses the multiline /* . . . */ comment form except when
the comment marks some part of a program that is not yet complete. Adopting that
strategy makes it easier to find unfinished parts of a program.

Modern programming environments typically use colors to make it easier to

distinguish the various parts of a program. On a color monitor, it is easy to display
many colors, so that a programming environment might, for example, display
keywords in one color, strings in another, and comments in yet some other shade.
Because this text is typeset using only two colors, program listings must be more
economical in their use of color. The only visual distinction that survives the
restricted color palette is between comments, which appear in blue, and the code
actually executed by the computer, which appears in black.
 1.3 The structure of a C++ program 9

As you can see from Figure 1-3, the PowersOfTwo program includes a comment
at the beginning that describes the program as a whole and one before the definition
of raiseToPower that describes the operation of that function at a lower level of
detail. In addition, the program includes a couple of one-line comments that act like
section headings in English text.

Library inclusions
Modern programs are never written without using libraries, which are collections of
previously written tools that perform useful operations. C++ defines a number of
standard libraries, of which one of the most important is iostream. This library
defines a set of simple input and output operations based on a data structure called a
stream, which is a data structure used to manage the flow of information to or from
some data source, such as the console or a file.

To gain access to the iostream library, your program must contain the line

#include <iostream>

This line instructs the C++ compiler to read the relevant definitions from what is
called a header file. The angle brackets in this line indicate that the header file is a
system library that is part of standard C++. Beginning in Chapter 2, you will also
have occasion to use header files that you have written yourself or that come from
other libraries. Those header files typically end with the suffix .h and are enclosed
in quotation marks instead of angle brackets.

In C++, reading in a header file using #include is often not sufficient by itself
to use a system library. To ensure that the names defined in different parts of a
large system do not interfere with one another, the designers of C++ made it
possible to segment code into structures called namespaces, each of which keeps
track of its own set of names. The standard C++ libraries use a namespace called
std, which means that you cannot refer to the names defined in standard header
files like iostream unless you let the compiler know to which namespace those
definitions belong.

Increasingly, professional C++ programmers specify the namespace explicitly by

adding the prefix std:: before each name to which it applies. Using this approach,
the first line of the HelloWorld program becomes

std::cout << "hello, world" << std::endl;

If you want to write code that looks like that of a professional, you can adopt this
style. For someone just learning the language, all those std:: tags make programs
harder to read, so this book instead adopts the convention of adding the line

using namespace std;

10 Overview of C++

at the end of the library inclusion section. At timesmost importantly when you
start to define your own library interfaces in Chapter 2you will need to remember
that the complete name of anything in the standard library namespace includes the
std:: prefix. For the moment, however, it is probably easiest to think of the

using namespace std;

as one of the incantations that the C++ compiler requires to work its magic on your
code.

Function prototypes
Computation in a C++ program is carried out in the context of functions. A
function is a named section of code that performs a specific operation. The
PowersOfTwo program contains two functionsmain and raiseToPowereach
of which is described in more detail in one of the sections that follow. Although the
definitions of these functions appear toward the end of the file, the PowersOfTwo
program provides a concise description of the raiseToPower function just after the
library inclusions. This concise form is called a prototype and makes it possible to
make calls to that function before its actual definition appears.

A C++ prototype consists of the first line of the function definition followed by a
semicolon, as illustrated by the prototype

int raiseToPower(int n, int k);

This prototype tells the compiler everything it needs to know about how to call that
function when it appears in the code. As you will see in the expanded discussion of
functions in Chapter 2, the prototype for raiseToPower indicates that the function
takes two integers as arguments and returns an integer as its result.

You must provide the declaration or definition of each function before making
any calls to that function. C++ requires such prototype declarations so the compiler
can check whether calls to functions are compatible with the function definitions. If
you accidentally supply the wrong number of arguments or if the arguments are of
the wrong type, the compiler reports an error, which makes it easier to find such
problems in your code.

The main program

Every C++ program must contain a function with the name main. This function
specifies the starting point for the computation and is called when the program starts
up. When main has finished its work and returns, execution of the program ends.
 1.3 The structure of a C++ program 11

The first line of the main function in the PowersOfTwo program is an example
of a variable declaration, which reserves space for a value used by the program. In
this case, the line

int limit;

introduces a new variable named limit capable of holding a value of type int, the
standard type used to represent integers. The syntax of variable declarations is
discussed in more detail in the section on Variables later in this chapter. For now,
all you need to know is that this declaration creates space for an integer variable that
you can then use in the body of the main function.

The next line of the main function is

cout << "This program lists powers of two." << endl;

This line has the same effect of the single statement in HelloWorld and sends a
message to the user indicating what the program does. The identifier cout refers to
the console output stream, which is one of the facilities defined by the iostream
interface. The effect of this statement is to take the characters enclosed in quotation
marks and send them to the cout stream, followed by the end-of-line sequence
endl, which ensures that next output operation will begin on a new line.

The next two lines are concerned with asking the user to provide a value for the
variable limit. The line

cout << "Enter exponent limit: ";

also prints a message to the cout stream, just as the first line did. The purpose of
this line is to let the user know what kind of input value is required. Such messages
are generally known as prompts.

When you print a prompt requesting input from the user, it is conventional to
omit the endl value so that the prompt appears on the same line as the user input.
When the computer executes this line of the program, it will display the prompt but
leaves the console cursorthe blinking vertical bar or square that marks the current
input positionat the end of the line, waiting for the users value, as follows:
12 Overview of C++

The actual request for the input value is the line

cin >> limit;

The identifier cin represents the console input stream, which is the counterpart to
cout for reading input from the user. This statement indicates that the next value
from the cin stream should be stored in the variable limit. Moreover, because
limit is declared as an integer variable, the >> operator automatically converts the
characters typed by the user into the appropriate integer. Thus, when the user types
8 and hits the RETURN key, the effect is to set limit to 8.

The next line of the main function is a for statement, which is used to repeat a
block of code. Like all control statements in C++, the for statement is divided into
a header line, which defines the nature of the control operation, and a body, which
indicates which statements are affected by the control operation. In this case, the
division looks like this:

The header linewhich you will have a chance to understand in more detail in the
section on The for statement later in this chapterindicates that the statements
in the body, whatever they are, should be repeated for each value of i beginning
with 0 and continuing up to and including the value of limit. Each execution of
the body of the loop prints a single line showing the value of 2i for the current value
of the variable i.

The single statement in the body of the loop is

cout << "2 to the " << i << " = "

<< raiseToPower(2, i) << endl;

This statement illustrates a couple of points. First, statements can be split across
more than one line; it is the semicolon that marks the end of the statement, and not
simply the end of the line. Second, this statement showcases the ability of the cout
stream to chain different output values together and to convert numeric quantities
into a printable form. The first part of the output is the character sequence

2 to the

This output is then followed by the value of the variable i, an equal sign surrounded
by spaces, the value of the function call

raiseToPower(2, i)
 1.3 The structure of a C++ program 13

and finally the end of line marker. The spaces in the strings ensure that the numeric
values do not run together.

Before the program can print the output line, however, it must invoke the
raiseToPower function to see what the value should be. Calling raiseToPower
suspends the execution of the main function, which then waits until the desired
value is returned.

As is typically the case with functions, raiseToPower needs some information

from the main program in order to do its work. If you think about what raising a
number to a power involves, you quickly realize that raiseToPower needs to know
the base, which in this case is the constant 2, and the exponent, which is currently
stored in the variable i. That variable, however, is declared within the body of the
main function and is accessible only within the main program. If raiseToPower
is to have access to the value of the base and exponent, the main program must pass
them as arguments to the function by including them in parentheses after the
function name. Doing so copies those values into the corresponding parameters, as
described in the following section.

As was true in the HelloWorld program as well, the final statement in main is

return 0;

This statement indicates that the value of the main function is 0. By convention,
C++ uses the value of the main function to report the status of the entire program.
A value of 0 indicates success; any other value is taken as an indication of failure.

Function definitions
Because large programs are difficult to understand in their entirety, most programs
are broken down into several smaller functions, each of which is easier to
understand. In the PowersOfTwo program, the raiseToPower function is used to
raise an integer to a poweran operation that is not built into C++ and must
therefore be defined explicitly.

The first line of raiseToPower is the variable declaration

int result = 1;

This declaration introduces a new variable named result capable of holding

values of type int and initializes it to have the value 1.

The next statement in the function is a for loopsimilar to the one youve
already seen in the main programthat executes its body k times. The body of the
for loop consists of the line
14 Overview of C++

result *= n;

which is C++ shorthand for the English sentence Multiply result by n. Because
the function initializes the value of result to 1 and then multiplies result by n a
total of k times, the variable result ends up with the value nk.

The last statement in raiseToPower is

return result;

which indicates that the function should return result as the value of the function.

1.4 Variables
Data values in a program are usually stored in variables, which are named locations
in memory capable of holding a particular data type. You have already seen
examples of variables in the PowersOfTwo program and are almost certainly
familiar with the basic concept from your earlier programming experience. The
purpose of this section is to outline the rules for using variables in C++.

Variable declarations
In C++, you must declare each variable before you use it. The primary function of
declaring a variable is to make an association between the name of the variable and
the type of value that variable contains. The placement of the declaration in a
program also determines the scope of the variable, which is the region in which that
variable is accessible.

The usual syntax for declaring a variable is

type namelist;

where type indicates the data type and namelist is a list of variable names separated
by commas. In most cases, each declaration introduces a single variable name. For
example, the function main in PowersOfTwo begins with the line

int limit;

which declares the variable limit to be of type int. You can, however, declare
several variable names at once, as in the following declaration, which declares three
variables named n1, n2, and n3:

double n1, n2, n3;

In this case, the variables are each declared to be of type double, which is the type
C++ uses to represent numbers that can have fractional parts. The name double is
 1.4 Variables 15

short for double-precision floating-point, but there is no reason to worry about what
all those terms mean. This declaration appears in the AddThreeNumbers program
in Figure 1-4, which reads in three numbers and writes out their sum.

It is important to remember that both the name and the type of a variable remain
fixed throughout its lifetime but that the value of that variable will typically change
as the program runs. To emphasize the dynamic nature of the value of a variable, it
often helps to diagram variables as boxes in which the name appears outside as a
label on the box and the value appears on the inside. For example, you might
diagram the declaration of limit like this:

Assigning a value to limit overwrites any previous contents of the box, but does
not change the name or the type.

In C++, the initial contents of a variable are undefined. If you want a variable to
have a particular value, you need to initialize it explicitly. To do so, all you need to
do is include an equal sign and a value after a variable name. Thus, the declaration

int result = 1;
16 Overview of C++

is a shorthand for the following code, in which the declaration and assignment are
separate:

int result;
result = 1;

An initial value specified as part of a declaration is called an initializer.

Naming conventions
The names used for variables, functions, types, constants, and so forth are
collectively known as identifiers. In C++, the rules for identifier formation are

1. The name must start with a letter or the underscore character (_).
2. All other characters in the name must be letters, digits, or the underscore. No
spaces or other special characters are permitted in names.
3. The name must not be one of the reserved keywords listed in Table 1-1.

Uppercase and lowercase letters appearing in an identifier are considered to be

different. Thus, the name ABC is not the same as the name abc. Identifiers can be
of any length, but C++ compilers are not required to consider any more than the
first 31 characters in determining whether two names are identical.

You can improve your programming style by adopting conventions for

identifiers that help readers identify their function. In this text, names of variables
and functions begin with a lowercase letter, such as limit or raiseToPower. The
names of classes and other programmer-defined data types begin with an uppercase
letter, as in Direction or TokenScanner. Constant values are written entirely in
uppercase, as in PI or HALF_DOLLAR. Whenever an identifier consists of several
English words run together, the usual convention is to capitalize the first letter of
 1.4 Variables 17

each word to make the name easier to read. Because that strategy doesnt work for
constants, programmers use the underscore character to mark the word boundaries.

Local and global variables

Most variables are declared with the body of a function. Such variables are called
local variables. The scope of a local variable extends to the end of the block in
which it is declared. When the function is called, space for each local variable is
allocated for the duration of that function call. When the function returns, all its
local variables disappear.

If a variable declaration appears outside any function definition, that declaration

introduces a global variable. The scope of a global variable is the remainder of the
file in which it is declared, and it exists throughout the execution of a program.
Global variables are therefore able to store values that persist across function calls.
While that property may seem useful, the disadvantages of global variables easily
outweigh their advantages. For one thing, global variables can be manipulated by
any function in a program, and it is difficult to keep those functions from interfering
with one another. Because of the problems they so often cause, global variables are
not used in this text except to declare constants, as discussed in the following
section. Although global variables may sometimes seem tempting, you will find it
easier to manage the complexity of your programs if you avoid them as well.

Constants
As you write your programs, you will find that you often use the same constant
many times in a program. If, for example, you are performing geometrical
calculations that involve circles, the constant ! comes up frequently. Moreover, if
those calculations require high precision, you might actually need all the digits that
fit into a value of type double, which means you would be working with the value
3.14159265358979323846. Writing that constant over and over again is tedious at
best, and likely to introduce errors if you type it in by hand each time instead of
cutting and pasting the value. It would be better if you could give this constant a
name and then refer to it by that name everywhere in the program. You could, of
course, simply declare it as a local variable by writing

double pi = 3.14159265358979323846;

but you would then be able to use it only within the method in which it was defined.
A better strategy is to declare it as a global constant like this:

const double PI = 3.14159265358979323846;

The keyword const at the beginning of this declaration indicates that the value will
not change after the variable is initialized, thereby ensuring that the value remains
18 Overview of C++

constant. It would not be appropriate, after all, to change the value of ! (despite the
fact that a bill was introduced in 1897 into the Indiana State Legislature attempting
to do just that). The rest of the declaration consists of the type, the name, and the
value, as before. The only difference is that the name is written entirely in
uppercase to be consistent with the C++ naming conventions for constants.

Using named constants offers several advantages. First, descriptive constant

names make the program easier to read. More importantly, using constants can
dramatically simplify the problem of maintaining the code for a program as it
evolves. Even if the value of PI is unlikely to change, some constants in a
program specify values that might change as the program evolves, even though they
will be constant for a particular version of that program.

The importance of this principle is easiest to illustrate by historical example.

Imagine for the moment that you are a programmer in the late 1960s working on the
initial design of the ARPANET, the first large-scale computer network and the
ancestor of todays Internet. Because resource constraints were quite serious at that
time, you would need to impose a limitas the actual designers of the ARPANET
did in 1969on the number of host computers that could be connected. In the early
years of the ARPANET, that limit was 127 hosts. If C++ had existed in those days,
you might have declared a constant that looked like this:

const int MAXIMUM_NUMBER_OF_HOSTS = 127;

At some later point, however, the explosive growth of networking would force you
to raise this bound. That process would be relatively easy if you used named
constants in your programs. To raise the limit on the number of hosts to 1023, it
might well be sufficient to change this declaration so that it read

const int MAXIMUM_NUMBER_OF_HOSTS = 1023;

If you used MAXIMUM_NUMBER_OF_HOSTS everywhere in your program to refer to

that maximum value, making this change would automatically propagate to every
part of the program in which the name was used.

Note that the situation would be entirely different if you had used the numeric
constant 127 instead. In that case, you would need to search through the entire
program and change all instances of 127 used for this purpose to the larger value.
Some instances of 127 might well refer to other things than the limit on the number
of hosts, and it would be just as important not to change any of those values. In the
likely event that you made a mistake, you would have a very hard time tracking
down the bug.
 1.5 Data types 19

1.5 Data types

Each variable in a C++ program contains a value constrained to be of a particular
type. You set the type of the variable as part of the declaration. So far, you have
seen variables of type int and double, but these types merely scratch the surface
of the types available in C++. Programs today work with many different data types,
some of which are built into the language and some of which are defined as part of a
particular application. Learning how to manipulate data of various types is an
essential part of mastering the basics of any language, including C++.

The concept of a data type

In C++ , every data value has an associated data type. From a formal perspective, a
data type is defined by two properties: a domain, which is the set of values that
belong to that type, and a set of operations, which defines the behavior of that type.
For example, the domain of the type int includes all integers

. . . !5, !4, !3, !2, !1, 0, 1, 2, 3, 4, 5 . . .

and so on, up to the limits established by the hardware of the machine. The set of
operations applicable to values of type int includes, for example, the standard
arithmetic operations like addition and multiplication. Other types have a different
domain and set of operations.

As you will learn in the later chapters in this book, much of the power of modern
programming languages like C++ comes from the fact that you can define new data
types from existing ones. To get that process started, C++ includes several
fundamental types that are defined as part of the language. These types, which act
as the building blocks for the type system as a whole, are called atomic or
primitive types. These predefined types are grouped into five categoriesinteger,
floating-point, Boolean, character, and enumerated typeswhich are discussed in
the sections that follow.

Integer types
Although the concept of an integer seems like a simple one, C++ actually includes
several different data types for representing integer values. In most cases, all you
need to know is the type int, which corresponds to the standard representation of
an integer on the computer system you are using. In certain cases, however, you
need to be more careful. Like all data, values of type int are stored internally in
storage units that have a limited capacity. Those values therefore have a maximum
size, which limits the range of integers you can use. To get around this problem,
C++ defines three integer typesshort, int, and longdistinguished from each
other by the size of their domains.
20 Overview of C++

Unfortunately, the language definition for C++ does not specify an exact range
for these three types. As a result, the range for the different integer types depends
on the machine and the compiler youre using. In the early years of computing, the
maximum value of type int was typically 32,767, which is very small by todays
standards. If you had wanted, for example, to perform a calculation involving the
number of seconds in a year, you could not use type int on those machines,
because that value (31,536,000) is considerably larger than 32,767. Modern
machines tend to support larger integers, but the only properties you can count on
are the following:

The internal size of an integer cannot decrease as you move from short to int
to long. A compiler designer for C++ could, for example, decide to make
short and int the same size but could not make int smaller than short.
The maximum value of type int must be at least 32,767 (2151).
The maximum value of type long must be at least 2,147,483,647 (2311).

The designers of C++ could have chosen to define the allowable range of type
int more precisely. For example, they could have declaredas the designers of
Java didthat the maximum value of type int would be 2311 on every machine.
Had they done so, it would be easier to move a program from one system to another
and have it behave in the same way. The ability to move a program between
different machines is called portability, which is an important consideration in the
design of a programming language.

In C++, each of the integer types int, long, and short may be preceded by the
keyword unsigned. Adding unsigned creates a new data type in which no
negative values are allowed. Unsigned values also offer twice the range of positive
values when compared to their signed counterparts. On modern machines, for
example, the maximum value of type int is typically 2,147,483,647, but the
maximum value of type unsigned int is 4,294,967,295. C++ allows the type
unsigned int to be abbreviated to unsigned, and most programmers who use
this type tend to follow this practice.

An integer constant is ordinarily written as a string of decimal digits. If the

number begins with the digit 0, however, the compiler interprets the value as an
octal (base 8) integer. Thus, the constant 040 is taken to be in octal and represents
the decimal number 32. If you prefix a numeric constant with the characters 0x, the
compiler interprets that number as hexadecimal (base 16). Thus, the constant 0xFF
is equivalent to the decimal constant 255. You can explicitly indicate that an
integer constant is of type long by adding the letter L at the end of the digit string.
Thus, the constant 0L is equal to 0, but the value is explicitly of type long.
Similarly, if you use the letter U as a suffix, the constant is taken to be unsigned.
 1.5 Data types 21

Floating-point types
Numbers that include a decimal fraction are called floating-point numbers, which
are used to approximate real numbers in mathematics. C++ defines three different
floating-point types: float, double, and long double. Although ANSI C++
does not specify the exact representation of these types, the way to think about the
difference is that the longer typeswhere long double is longer than double,
which is in turn longer than floatallow numbers to be represented with greater
precision at the cost of occupying more memory space. Unless you are doing
exacting scientific calculation, however, the differences between these types will
not make a great deal of difference. In keeping with a common convention among
C++ programmers, this text uses the type double as its standard floating-point
type.

Floating-point constants in C++ are written with a decimal point. Thus, if 2.0
appears in a program, the number is represented internally as a floating-point value;
if the programmer had written 2, this value would be an integer. Floating-point
values can also be written in a special programmers style of scientific notation, in
which the value is represented as a floating-point number multiplied by an integral
power of 10. To write a number using this style, you write a floating-point number
in standard notation, followed immediately by the letter E and an integer exponent,
optionally preceded by a + or - sign. For example, the speed of light in meters per
second can be written in C++ as

2.9979E+8

where the E stands for the words times 10 to the power.

Boolean type
In the programs you write, it is often necessary to test a particular condition that
affects the subsequent behavior of your code. Typically, that condition is specified
using an expression whose value is either true or false. This data typefor which
the only legal values are the constants true and falseis called Boolean data,
after the mathematician George Boole, who developed an algebraic approach for
working with such values.

In C++, the Boolean type is called bool. You can declare variables of type
bool and manipulate them in the same way as other data objects. The operations
that apply to the type bool are described in detail in the section entitled Boolean
operators on page 34.
22 Overview of C++

Characters
In the early days, computers were designed to work only with numeric data and
were sometimes called number crunchers as a result. Modern computers, however,
work less with numeric data than they do with text data, that is, any information
composed of individual characters that appear on the keyboard and the screen. The
ability of modern computers to process text data has led to the development of word
processing systems, online reference libraries, electronic mail, social networks, and
a seemingly infinite supply of exciting applications.

The most primitive elements of text data are individual characters, which are
represented in C++ using the predefined data type char. The domain of type char
is the set of symbols that can be displayed on the screen or typed on the keyboard:
the letters, digits, punctuation marks, spacebar, RETURN key, and so forth.
Internally, these values are represented inside the computer by assigning each
character a numeric code. In most implementations of C++, the coding system used
to represent characters is called ASCII, which stands for the American Standard
Code for Information Interchange. The decimal values of the characters in the
ASCII set are shown in Table 1-2, where the ASCII code for any character is the
sum of the numbers at the beginning of its row and column.

Although it is important to know that characters are represented internally using

a numeric code, it is not generally useful to know what numeric value corresponds
 1.5 Data types 23

to a particular character. When you type the letter A, the hardware logic built into
the keyboard automatically translates that character into the ASCII code 65, which
is then sent to the computer. Similarly, when the computer sends the ASCII code
65 to the screen, the letter A appears.

You can write a character constant in C++ by enclosing the character in single
quotes. Thus, the constant 'A' represents the internal code of the uppercase letter
A. In addition to the standard characters, C++ allows you to write special characters
in a multicharacter form beginning with a backward slash (\). This form is called
an escape sequence. Table 1-3 shows the escape sequences that C++ supports.

Strings
Characters are most useful when they are collected together into sequential units. In
programming, a sequence of characters is called a string. So far, the strings youve
seen in the HelloWorld and PowersOfTwo programs have been used simply to
display messages on the screen, but they have many more applications than that.

You write string constants in C++ by enclosing the characters contained within
the string in double quotes. As with character, C++ uses the escape sequences from
Table 1-3 to represent special characters. If two or more string constants appear
consecutively in a program, the compiler concatenates them together. The most
important implication of this rule is that you can break a long string over several
lines so that it doesnt end up running past the right margin of your program.
24 Overview of C++

Given that they are essential to so many applications, all modern programming
languages include special features for working with strings. Unfortunately, C++
complicates the issue by defining two different string types: an older style inherited
from C and a more sophisticated string library that supports the object-oriented
paradigm. To minimize confusion, this text uses the string library wherever
possible, and you shouldfor the most partfeel free to ignore the fact that two
string models exist. The times when that complexity raises its ugly head are
outlined in Chapter 3, which covers the string library in more detail. For the
moment, you can simply imagine that C++ offers a built-in data type called string
whose domain is the set of all sequences of characters. You can declare variables of
type string and pass string values back and forth between functions as arguments
and results.

The fact that string is a library type and not a built-in feature does have a few
implications. If you use the type name string in a program, you need to add the
string library to the list of #include lines, like this:

#include <string>

Moreover, because the string type is part of the standard library namespace, the
compiler will recognize the type name only if you have included the line

using namespace std;

at the beginning of the file, as the programs in this book invariably do.

Enumerated types
As the discussion of ASCII codes in the preceding section makes clear, computers
store character data in integer by assigning a number to each character. This idea of
encoding data as integers by numbering the elements of the domain is actually a
much more general principle. C++ allows you to define new types simply by listing
the elements in their domain. Such types are called enumerated types.

The syntax for defining an enumerated type is

enum typename { namelist };

where typename is the name of the new type and namelist is a list of the constants in
the domain, separated by commas. In this book, all type names start with an
uppercase letter, and the names of the enumeration constants are written entirely in
uppercase. For example, the following definition introduces a new Direction
type whose values are the four compass directions:

enum Direction { NORTH, EAST, SOUTH, WEST };

 1.5 Data types 25

When the C++ compiler encounters this definition, it assigns values to the constant
names by numbering them consecutively starting with 0. Thus, NORTH is assigned
the value 0, EAST is assigned the value 1, SOUTH is assigned the value 2, and WEST
is assigned the value 3.

C++ allows you to assign explicit underlying values to each of the constants of
an enumerated type. For example, the type declaration

enum Coin {
PENNY = 1,
NICKEL = 5,
DIME = 10,
QUARTER = 25,
HALF_DOLLAR = 50,
DOLLAR = 100
};

introduces an enumerated type for U.S. coinage in which each constant is defined to
equal the monetary value of that coin. If you supply values for some of the
constants but not others, the C++ compiler will automatically choose values for the
unassigned constants by numbering them consecutively after the last value you
supplied. Thus, the type declaration

enum Month {
JANUARY = 1,
FEBRUARY,
MARCH,
APRIL,
MAY,
JUNE,
JULY,
AUGUST,
SEPTEMBER,
OCTOBER,
NOVEMBER,
DECEMBER
};

introduces a type for the months of the year in which JANUARY has the value 1,
FEBRUARY has the value 2, and so forth up to DECEMBER, which has the value 12.

Compound types
The atomic types described in the preceding sections form the basis of a very rich
type system that allows you to create new types from existing ones. Moreover,
because C++ represents a synthesis of the object-oriented and procedural
26 Overview of C++

paradigms, the type system includes both objects and more traditional structures.
Learning how to define and manipulate these types is, to a large extent, the theme of
this entire book. It therefore does not make sense to squeeze a complete description
of these types into Chapter 1. Thats what the rest of the chapters are for.

Over the years of teaching this material at Stanford, we have discovered that you
are much more likely to master the concepts of object-oriented programming if the
details of defining classes and objects are presented after you have had a chance to
use them in a high-level way. This book adopts that strategy and postpones any
discussion of how to create your own objects until Chapter 6, at which point you
will have had plenty of time to discover just how useful objects can be.

1.6 Expressions
Whenever you want a program to perform calculations, you need to write an
expression that specifies the necessary operations in a form similar to that used for
expressions in mathematics. For example, suppose that you wanted to solve the
quadratic equation

ax2 + bx + c = 0

As you know from high-school mathematics, this equation has two solutions given
by the formula

x =

The first solution is obtained by using + in place of the symbol; the second is
obtained by using instead. In C++, you could compute the first of these solutions
by writing the following expression:

(-b + sqrt(b * b - 4 * a * c)) / (2 * a)

There are a few differences in form: multiplication is represented explicitly by a *,

division is represented by a /, and the square root function (which comes from a
library called <cmath> described in detail in Chapter 2) is written using the name
sqrt rather than a mathematical symbol. Even so, the C++ form of the expression
captures the intent of its mathematical counterpart in a way that is quite readable,
particularly if youve written programs in any modern programming language.

In C++, an expression is composed of terms and operators. A term, such as the

variables a, b, and c or the constants 2 and 4 in the preceding expression, represents
a single data value and must be either a constant, a variable, or a function call. An
operator is a character (or sometimes a short sequence of characters) that indicates a
 1.7 Expressions 27

computational operation. A list of the operators available in C++ appears in

Table 1-4. The table includes familiar arithmetic operators like + and - along with
several others that pertain only to types introduced in later chapters.

Precedence and associativity

The point of listing all the operators in a single table is to establish how they relate
to one another in terms of precedence, which is a measure of how tightly an
operator binds to its operands in the absence of parentheses. If two operators
compete for the same operand, the one that appears higher in the precedence table is
applied first. Thus, in the expression

(-b + sqrt(b * b - 4 * a * c)) / (2 * a)

the multiplications b * b and 4 * a * c are performed before the subtraction

because * has a higher precedence than -. It is, however, important to note that
the - operator occurs in two forms. Operators that connect two operands are called
binary operators; operators that take just one operand are called unary operators.
When a minus sign is written in front of a single operand, as in -b, it is interpreted
as a unary operator signifying negation. When it appears between two operands, as
it does inside the argument to sqrt, the minus sign is a binary operator signifying
28 Overview of C++

subtraction. The precedence of the unary and binary versions of an operator are
different and are listed separately in the precedence table.

If two operators have the same precedence, they are applied in the order
specified by their associativity, which indicates whether that operator groups to the
left or to the right. Most operators in C++ are left-associative, which means that the
leftmost operator is evaluated first. A few operatorsmost notably the assignment
operator discussed in its own section later in this chapterare right-associative,
which mean that they group from right to left. The associativity for each operator
appears in Table 1-4.

The quadratic formula illustrates the importance of paying attention to

precedence and associativity rules. Consider what would happen if you wrote the
expression without the parentheses around 2 * a, as follows:

(-b + sqrt(b * b - 4 * a * c)) / 2 * a

Without the parentheses, the division operator would be performed first because /
and * have the same precedence and associate to the left. This example illustrates
the use of the bug icon to mark code that is intentionally incorrect to make sure that
you dont copy it into your own programs.

Mixing types in an expression

In C++, you can write an expression that includes values of different numeric types.
If C++ encounters an operator whose operands are of different types, the compiler
automatically converts the operands to a common type by choosing the type that
appears closest to the top of the hierarchy in Table 1-5. The result of applying the
operation is always that of the arguments after any conversions are applied. This
convention ensures that the result of the computation is as precise as possible.
 1.7 Expressions 29

As an example, suppose that n is declared as an int, and x is declared as a

double. The expression

n + 1

is evaluated using integer arithmetic and produces a result of type int. The
expression

x + 1

however, is evaluated by converting the integer 1 to the floating-point value 1.0 and
adding the results together using double-precision floating-point arithmetic, which
results in a value of type double.

Integer division and the remainder operator

The fact that applying an operator to two integer operands generates an integer
result leads to an interesting situation with respect to the division operator. If you
write an expression like

9 / 4

C++s rules specify that the result of this operation must be an integer, because both
operands are of type int. When C++ evaluates this expression, it divides 9 by 4
and discards any remainder. Thus, the value of this expression in C++ is 2, not
2.25.

If you want to compute the mathematically correct result of 9 divided by 4, at

least one of the operands must be a floating-point number. For example, the three
expressions

9.0 / 4
9 / 4.0
9.0 / 4.0

each produce the floating-point value 2.25. The decimal fraction is thrown away
only if both operands are of type int. The operation of discarding a decimal
fraction is called truncation.

The / operator in C++ is closely associated with the % operator, which returns
the remainder left over when the first operand is divided by the second. For
example, the value of

9 % 4
30 Overview of C++

is 1, since 4 goes into 9 twice, with 1 left over. The following are some other
examples of the % operator:
0 % 4 = 0 19 % 4 = 3
1 % 4 = 1 20 % 4 = 0
4 % 4 = 0 2001 % 4 = 1

The / and % operators turn out to be extremely useful in a wide variety of

programming applications. You can, for example, use the % operator to test whether
one number is divisible by another; to determine whether an integer n is divisible by
3, you just check whether the result of the expression n % 3 is 0.

It is, however, important to use caution if either or both of the operands to / and
% might be negative, because the results may differ from machine to machine. On
most machines, division truncates its result toward 0, but this behavior is not
actually guaranteed by the ANSI standard. In general, it is good programming
practice to avoidas this book doesusing these operators with negative values.

Type casts
In C++, you can specify explicit conversion by using what is called a type cast,
which specifies an explicit conversion from one type to another. In C++, type casts
are usually written by specifying the name of the desired type followed by the value
you wish to convert in parentheses. For example, if num and den are declared as
integers, you can compute the floating-point quotient by writing

quotient = double(num) / den;

The first step in evaluating the expression is to convert num to a double, after
which the division is performed using floating-point arithmetic as described in the
section on Mixing types in an expression earlier in this chapter.

As long as the conversion moves upward in the hierarchy shown in Table 1-5,
the conversion involves no loss of information. If, however, you convert a value of
a more precise type to a less precise one, some information may be lost. For
example, if you use a type cast to convert a value of type double to type int, any
decimal fraction is simply dropped. Thus, the value of the expression

int(1.9999)

is the integer 1.

The assignment operator

In C++, assignment of values to variables is built into the expression structure.
The = operator takes two operands, just like + or *. The left operand must indicate
a value that can change, which is typically a variable name. When the assignment
 1.7 Expressions 31

operator is executed, the expression on the right-hand side is evaluated, and the
resulting value is then stored in the variable that appears on the left-hand side.
Thus, if you evaluate an expression like

result = 1

the effect is that the value 1 is assigned to the variable result. In most cases,
assignment expressions of this sort appear in the context of simple statements,
which are formed by adding a semicolon after the expression, as in the line

result = 1;

Such statements are often called assignment statements.

The assignment operator converts the type of the value on the right-hand side so
that it matches the declared type of the variable. Thus, if the variable total is
declared to be of type double, and you write the assignment statement

total = 0;

the integer 0 is converted into a double as part of making the assignment. If n is

declared to be of type int, the assignment

n = 3.14159265;

has the effect of setting n to 3, because the value is truncated to fit in the integer
variable.

Even though assignment operators usually occur in the context of simple

statements, they can also be incorporated into larger expressions, in which case the
result of applying the assignment operator is simply the value assigned. For
example, the expression

z = (x = 6) + (y = 7)

has the effect of setting x to 6, y to 7, and z to 13. The parentheses are required in
this example because the = operator has a lower precedence than +. Assignments
that are written as part of larger expressions are called embedded assignments.

Although there are contexts in which embedded assignments are convenient,

they often make programs more difficult to read because the assignment is easily
overlooked in the middle of a complex expression. For this reason, this text limits
the use of embedded assignments to a few special circumstances in which they seem
to make the most sense. Of these, the most important is when you want to set
several variables to the same value. C++s definition of assignment as an operator
32 Overview of C++

makes it possible, instead of writing separate assignment statements, to write a

single statement like

n1 = n2 = n3 = 0;

which has the effect of setting all three variables to 0. This statement works
because C++ evaluates assignment operators from right to left. The entire statement
is therefore equivalent to

n1 = (n2 = (n3 = 0));

The expression n3 = 0 is evaluated, which sets n3 to 0 and then passes 0 along as

the value of the assignment expression. That value is assigned to n2, and the result
is then assigned to n1. Statements of this sort are called multiple assignments.

As a programming convenience, C++ allows you to combine assignment with a

binary operator to produce a form called a shorthand assignment. For any binary
operator op, the statement

variable op= expression;

is equivalent to

variable = variable op (expression);

where the parentheses are included to emphasize that the entire expression is
evaluated before op is applied. Thus, the statement

balance += deposit;

is a shorthand for

balance = balance + deposit;

which adds deposit to balance.

Because this same shorthand applies to any binary operator in C++, you can
subtract the value of surcharge from balance by writing

balance -= surcharge;

Similarly, you can divide the value of x by 10 using

x /= 10;
 1.7 Expressions 33

Increment and decrement operators

Beyond the shorthand assignment operators, C++ offers a further level of
abbreviation for the particularly common programming operations of adding or
subtracting 1 from a variable. Adding 1 to a variable is called incrementing it;
subtracting 1 is called decrementing it. To indicate these operations in an
extremely compact form, C++ uses the operators ++ and --. For example, the
statement

x++;

in C++ has the same effect on the variable x as

x += 1;

which is itself short for

x = x + 1;

Similarly,

y--;

has the same effect as

y -= 1;

or

y = y - 1;

As it happens, these operators are more intricate than the previous examples
would suggest. To begin with, each of these operators can be written in two ways.
The operator can come after the operand to which it applies, as in

x++

or before the operand, as in

++x

The first form, in which the operator follows the operand, is called the suffix form,
the second, the prefix form.

If all you do is execute the ++ operator in isolationas you do in the context of

a separate statement or the standard for loop patternsthe prefix and suffix
operators have precisely the same effect. You notice the difference only if you use
34 Overview of C++

these operators as part of a larger expression. Then, like all operators, the ++
operator returns a value, but the value depends on where the operator is written
relative to the operand. The two cases are as follows:

x++ Calculates the value of x first, and then increments it. The value
returned to the surrounding expression is the original value before the
increment operation is performed.
++x Increments the value of x first, and then uses the new value as the
value of the ++ operation as a whole.

The -- operator behaves similarly, except that the value is decremented rather than
incremented.

You may wonder why would anyone use such an arcane feature. The ++ and --
operators are certainly not essential. Moreover, there are not many circumstances in
which programs that embed these operators in larger expressions are demonstrably
better than those that use a simpler approach. On the other hand, ++ and -- are
firmly entrenched in the historical tradition shared by the languages C, C++, and
Java. Programmers use them so frequently that they have become essential idioms
in these languages. In light of their widespread use in programs, you need to
understand these operators so that you can make sense of existing code.

Boolean operators
C++ defines three classes of operators that manipulate Boolean data: the relational
operators, the logical operators, and the ?: operator. The relational operators are
used to compare two values. C++ defines six relational operators, as follows:

== Equal
!= Not equal
> Greater than
< Less than
>= Greater than or equal to
<= Less than or equal to

When you write programs that test for equality, be careful to use the == operator,
which is composed of two equal signs. A single equal sign is the assignment
operator. Since the double equal sign violates conventional mathematical usage,
replacing it with a single equal sign is a particularly common mistake. This mistake
can also be very difficult to track down because the C++ compiler does not usually
catch it as an error. A single equal sign turns the expression into an embedded
assignment, which is perfectly legal in C++; it just isnt at all what you want.
 1.7 Expressions 35

The relational operators can be used to compare atomic data values like integers,
floating-point numbers, Boolean values, and characters, but those operators can also
be applied to many of the types supplied by libraries, such as string.

In addition to the relational operators, C++ defines three logical operators that
take Boolean operands and combine them to form other Boolean values:

! Logical not (true if the following operand is false)

&& Logical and (true if both operands are true)
|| Logical or (true if either or both operands are true)

These operators are listed in decreasing order of precedence.

Although the operators &&, ||, and ! closely resemble the English words and,
or, and not, it is important to remember that English can be somewhat imprecise
when it comes to logic. To avoid that imprecision, it is often helpful to think of
these operators in a more formal, mathematical way. Logicians define these
operators using truth tables, which show how the value of a Boolean expression
changes as the values of its operands change. The truth table in Table 1-6 illustrates
the result for each of the logical operators, given all possible values of the variables
p and q.

Whenever a C++ program evaluates an expression of the form

exp1 && exp2

or
exp1 || exp2

the individual subexpressions are always evaluated from left to right, and evaluation
ends as soon as the result can be determined. For example, if exp1 is false in the
expression involving &&, there is no need to evaluate exp2 since the final result will
always be false. Similarly, in the example using ||, there is no need to evaluate
the second operand if the first operand is true. This style of evaluation, which
stops as soon as the result is known, is called short-circuit evaluation.
36 Overview of C++

The C++ programming language includes another Boolean operator called ?:

that can be extremely useful in certain situations. In programming parlance, the
name of this operator is always pronounced as question-mark colon, even though
the two characters do not appear adjacent to each other in the code. Unlike the
other operators in C++, ?: is written in two parts and requires three operands. The
general form of the operation is

(condition) ? exp1 : exp2

The parentheses are not technically required, but C++ programmers often include
them to emphasize the boundaries of the conditional test.

When a C++ program encounters the ?: operator, it first evaluates the condition.
If the condition turns out to be true, exp1 is evaluated and used as the value of the
entire expression; if the condition is false, the value is the result of evaluating
exp2. For example, you can use the ?: operator to assign to max either the value of
x or the value of y, whichever is greater, as follows:

max = (x > y) ? x : y;

1.7 Statements
Programs in C++ are composed of functions, which are made up in turn of
statements. As in most languages, statements in C++ fall into one of two principal
classifications: simple statements that perform some action and control statements
that affect the way in which other statements are executed. The sections that follow
review the principal statement forms available in C++, giving you the tools you
need to write your own programs.

Simple statements
The most common statement in C++ is the simple statement, which consists of an
expression followed by a semicolon:

expression;

In most cases, the expression is a function call, an assignment, or a variable

followed by the increment or decrement operator.

Blocks
As C++ is defined, control statements typically apply to a single statement. When
you are writing a program, you often want a particular control statement to apply to
a whole group of statements. To indicate that a sequence of statements is part of a
coherent unit, you can assemble those statements into a block, which is a collection
of statements enclosed in curly braces, as follows:
 1.7 Statements 37

{
statement1
statement2
. . .
statementn
}

When the C++ compiler encounters a block, it treats the entire block as a single
statement. Thus, whenever the notation statement appears in a pattern for one of the
control forms, you can substitute for it either a single statement or a block. To
emphasize that they are statements as far as the compiler is concerned, blocks are
sometimes referred to as compound statements. In C++, the statements in any
block may be preceded by declarations of variables.

The statements in the interior of a block are usually indented relative to the
enclosing context. The compiler ignores the indentation, but the visual effect is
extremely helpful to the human reader, because it makes the structure of the
program jump out at you from the format of the page. Empirical research has
shown that indenting three or four spaces at each new level makes the program
structure easiest to see; the programs in this text use three spaces for each new level.
Indentation is critical to good programming, so you should strive to develop a
consistent indentation style in your programs.

The if statement
In writing a program, you will often want to check whether some condition applies
and use the result of that check to control the subsequent execution of the program.
This type of program control is called conditional execution. The easiest way to
express conditional execution in C++ is by using the if statement, which comes in
two forms:

if (condition) statement
if (condition) statement else statement

You use the first form of the if statement when your solution strategy calls for a set
of statements to be executed only if a particular Boolean condition is true. If the
condition is false, the statements that form the body of the if statement are
simply skipped. You use the second form of the if statement for situations in
which the program must choose between two independent sets of actions based on
the result of a test. This statement form is illustrated by the following code, which
reports whether an integer n is even or odd.
38 Overview of C++

if (n % 2 == 0) {
cout << "That number is even." << endl;
} else {
cout << "That number is odd." << endl;
}

As with any control statement, the statements controlled by the if statement can
be either a single statement or a block. Even if the body of a control form is a single
statement, you are free to enclose it in a block if you decide that doing so improves
the readability of your code. The programs in this book enclose the body of every
control statement in a block unless the entire statementboth the control form and
its bodyis so short that it fits on a single line.

The switch statement

The if statement is ideal for those applications in which the program logic calls for
a two-way decision point: some condition is either true or false, and the program
acts accordingly. Some applications, however, call for more complicated decision
structures involving several mutually exclusive cases: in one case, the program
should do x; in another case, it should do y; in a third, it should do z; and so forth.
In many applications, the most appropriate statement to use for such situations is the
switch statement, which has the following syntactic form:

switch (e) {
case c1:
statements
break;
case c2:
statements
break;
. . . more case clauses . . .
default:
statements
break;
}

The expression e is called the control expression. When the program executes a
switch statement, it evaluates the control expression and compares it against the
values c1, c2, and so forth, each of which must be a constant. If one of the constants
matches the value of the control expression, the statements in the associated case
clause are executed. When the program reaches the break statement at the end of
the clause, the operations specified by that clause are complete, and the program
continues with the statement that follows the entire switch statement.
 1.7 Statements 39

The default clause is used to specify what action occurs if none of the
constants match the value of the control expression. The default clause, however,
is optional. If none of the cases match and there is no default clause, the program
simply continues on with the next statement after the switch statement without
taking any action at all. To avoid the possibility that the program might ignore an
unexpected case, it is good programming practice to include a default clause in
every switch statement unless you are certain you have enumerated all the
possibilities.

The code pattern Ive used to illustrate the syntax of the switch statement
deliberately suggests that break statements are required at the end of each clause.
In fact, C++ is defined so that if the break statement is missing, the program starts
executing statements from the next clause after it finishes the selected one. While
this design can be useful in some cases, it causes many more problems than it
solves. To reinforce the importance of remembering to exit at the end of each case
clause, the programs in this text include a break or return statement in each such
clause.

The one exception to this rule is that multiple case lines specifying different
constants can appear together, one after another, before the same statement group.
For example, a switch statement might include the following code:

case 1:
case 2:
statements
break;

which indicates that the specified statements should be executed if the select
expression is either 1 or 2. The C++ compiler treats this construction as two case
clauses, the first of which is empty. Because the empty clause contains no break
statement, a program that selects the first path simply continues on with the second
clause. From a conceptual point of view, however, you are better off if you think of
this construction as a single case clause representing two possibilities.

The constants in a switch statement must be a scalar type, which is defined in

C++ as a type that uses an integer as its underlying representation. In particular,
characters are often used as case constants, as illustrated by the following function,
which tests to see if its argument is a vowel:
40 Overview of C++

bool isVowel(char ch) {

switch (ch) {
case 'A': case 'E': case 'I': case 'O': case 'U':
case 'a': case 'e': case 'i': case 'o': case 'u':
return true;
default:
return false;
}
}

Enumerated types also qualify as scalar types, as illustrated by the function

string directionToString(Direction dir) {

switch (dir) {
case NORTH: return "NORTH";
case EAST: return "EAST";
case SOUTH: return "SOUTH";
case WEST: return "WEST";
default: return "???";
}
}

which converts a Direction value to a string. The default clause returns "???"
if the internal value of dir does not match any of the Direction constants.

As a second example of using switch with enumerated types, the following

function returns the number of days for a given month and year:

int daysInMonth(Month month, int year) {

switch (month) {
case APRIL:
case JUNE:
case SEPTEMBER:
case NOVEMBER:
return 30;
case FEBRUARY:
return (isLeapYear(year)) ? 29 : 28;
default:
return 31;
}
}

This code assumes the existence of a function isLeapYear(year) that tests

whether year is a leap year. You can implement isLeapYear using the logical
operators && and ||, as follows:
 1.7 Statements 41

bool isLeapYear(int year) {

return ((year % 4 == 0) && (year % 100 != 0))
|| (year % 400 == 0);
}

This function simply encodes the rule for determining leap years: a leap year is any
year divisible by 4, except for years ending in 00, in which case the year must be
divisible by 400.

Functions that return Boolean valueslike isVowel and isLeapYear in this

sectionare called predicate functions. Predicate functions play a useful role in
programming, and you will encounter many of them in this text.

The while statement

In addition to the conditional statements if and switch, C++ includes several
control statements that allow you to execute some part of the program multiple
times to form a loop. Such control statements are called iterative statements. The
simplest iterative statement in C++ is the while statement, which executes a
statement repeatedly until a conditional expression becomes false. The general
form for the while statement looks like this:

while (conditional-expression) {
statements
}

When a program encounters a while statement, it first evaluates the conditional

expression to see whether it is true or false. If it is false, the loop terminates
and the program continues with the next statement after the entire loop. If the
condition is true, the entire body is executed, after which the program goes back to
the beginning of the loop to check the condition again. A single pass through the
statements in the body constitutes a cycle of the loop.

There are two important principles about the operation of a while loop:

1. The conditional test is performed before every cycle of the loop, including the
first. If the test is false initially, the body of the loop is not executed at all.
2. The conditional test is performed only at the beginning of a loop cycle. If that
condition becomes false at some point during the loop, the program wont
notice that fact until it completes the entire cycle. At that point, the program
evaluates the test condition again. If it is still false, the loop terminates.

The operation of the while loop is illustrated by the following function, which
computes the sum of the digits in an integer:
42 Overview of C++

int digitSum(int n) {
int sum = 0;
while (n > 0) {
sum += n % 10;
n /= 10;
}
return sum;
}

The function depends on the following observations:

The expression n % 10 always returns the last digit in a positive integer n.

The expression n / 10 returns a number without its final digit.

The while loop is designed for situations in which there is some test condition
that can be applied at the beginning of a repeated operation, before any of the
statements in the body of the loop are executed. If the problem you are trying to
solve fits this structure, the while loop is the perfect tool. Unfortunately, many
programming problems do not fit easily into the standard while loop structure.
Instead of allowing a convenient test at the beginning of the operation, some
problems are structured in such a way that the test you want to write to determine
whether the loop is complete falls most naturally somewhere in the middle of the
loop.

The most common example of such loops are those that read in data from the
user until some special value, or sentinel, is entered to signal the end of the input.
When expressed in English, the structure of the sentinel-based loop consists of
repeating the following steps:

1. Read in a value.
2. If the value is equal to the sentinel, exit from the loop.
3. Perform whatever processing is required for that value.

Unfortunately, there is no test you can perform at the beginning of the loop to
determine whether the loop is finished. The termination condition for the loop is
reached when the input value is equal to the sentinel; in order to check this
condition, the program must first read in some value. If the program has not yet
read in a value, the termination condition doesnt make sense.

When some operations must be performed before you can check the termination
condition, you have a situation that programmers call the loop-and-a-half problem.
One strategy for solving the loop-and-a-half problem in C++ is to use the break
statement, which, in addition to its use in the switch statement, has the effect of
immediately terminating the innermost enclosing loop. Using break, it is possible
 1.7 Statements 43

to code the loop structure in a form that follows the natural structure of the problem,
which is called the read-until-sentinel pattern:

while (true) {
Prompt user and read in a value.
if (value == sentinel) break;
Process the data value.
}

Note that the

while (true)

line itself seems to introduce an infinite loop because the value of the constant true
can never become false. The only way this program can exit from the loop is by
executing the break statement inside it. The AddIntegerList program in
Figure 1-5 uses the read-until-sentinel pattern to compute the sum of a list of
integers terminated by the sentinel value 0.

There are other strategies for solving the loop-and-a-half problem, most of which
involve copying part of the code outside the loop or introducing additional Boolean
variables. Empirical studies have demonstrated that students are more likely to
write correct programs if they use a break statement to exit from the middle of the
loop than if they are forced to use some other strategy. This evidence and my own
experience have convinced me that using the read-until-sentinel pattern is the best
solution to the loop-and-a-half problem.

The for statement

One of the most important control statements in C++ is the for statement, which is
used in situations in which you want to repeat an operation a particular number of
times. All modern programming languages have a statement that serves that
purpose, but the for statement in the C family of languages is especially powerful
and is useful in a wide variety of applications.

You have already seen two examples of the for loop in the PowersOfTwo
program earlier in this chapter. The first appeared in the main program, when it
cycled through the desired values of the exponent. That loop looked like this:

for (int i = 0; i <= limit; i++) {

cout << "2 to the " << i << " = "
<< raiseToPower(2, i) << endl;
}
44 Overview of C++

The second example appeared in the implementation of raiseToPower and had the
following form:

for (int i = 0; i < k; i++) {

result *= n;
}

Each of these examples represents an idiomatic pattern that will come up often as
you write your programs.
 1.7 Statements 45

Of these two patterns, the second is more common. The general form of this
pattern is

for (int var = 0; var < n; var++)

and has the effect of executing the body of the loop n times. You can substitute any
variable name you want into this pattern, but that variable is often not used inside
the body of the for loop at all, as is the case in raiseToPower.

The pattern from the main program counts from one value to another and has the
following general form:

for (int var = start; var <= finish; var++)

In this pattern, the body of the for loop is executed with the variable var set to each
value between start and finish, inclusive. Thus, you could use a for loop to have
the variable i count from 1 to 100 like this:

for (int i = 1; i <= 100; i++)

You can also use the for loop pattern to implement the factorial function, which
is defined as the product of the integers between 1 and n and is usually written in
mathematics as n! The code is similar to the implementation of raiseToPower:

int fact(int n) {
int result = 1;
for (int i = 1; i <= n; i++) {
result *= i;
}
return result;
}

In this implementation, the for loop ensures that the variable i counts from 1 to n.
The body of the loop then updates the value of result by multiplying it by i,
which takes on each of the desired values in turn.

The variable used in these for loop patterns is called an index variable. The
convention of using single-letter names such as i and j for index variables dates
back at least as far as the early versions of FORTRAN (which required integer
variables to start with a predefined set of letters in the middle of the alphabet) but
also fits with similar conventions in mathematics. Although short variable names
are usually poor choices because they convey very little about the purpose of that
variable, the fact that this naming convention exists makes such names appropriate
in this context. Whenever you see the variable i or j in a for loop, you can be
reasonably confident that the variable is counting through some range of values.
46 Overview of C++

The for loop in C++, however, is considerably more general than the earlier
examples suggest. The general form of the for loop pattern is

for (init; test; step) {

statements
}

This code is equivalent to the following while statement

init;
while (test) {
statements
step;
}

The code fragment specified by init, which is typically a variable declaration, runs
before the loop begins and is most often used to initialize an index variable. For
example, if you write

for (int i = 0; . . .

the loop will begin by setting the index variable i to 0. If the loop begins

for (int i = -7; . . .

the variable i will start as !7, and so on.

The test expression is a conditional test written exactly like the test in a while
statement. As long as the test expression is true, the loop continues. Thus, the
loop

for (int i = 0; i < n; i++)

begins with i equal to 0 and continues as long as i is less than n, which turns out to
represent a total of n cycles, with i taking on the values 0, 1, 2, and so forth, up to
the final value n1. The loop

for (int i = 1; i <= n; i++)

begins with i equal to 1 and continues as long as i is less than or equal to n. This
loop also runs for n cycles, with i taking on the values 1, 2, and so forth, up to n.

The step expression indicates how the value of the index variable changes from
cycle to cycle. The most common form of step specification is to increment the
index variable using the ++ operator, but this is not the only possibility. For
example, one can count backward using the -- operator, or count by twos using +=
2 instead of ++.
 Summary 47

As an illustration of counting in the reverse direction, the program

int main() {
for (int t = 10; t >= 0; t--) {
cout << t << endl;
}
return 0;
}

generates the following sample run:

Each of the expressions in a for statement is optional, but the semicolons must
appear. If init is missing, no initialization is performed. If test is missing, it is
assumed to be true. If step is missing, no action occurs between loop cycles.

Summary
This chapter is itself a summary, which makes it hard to condense it to a few central
points. Its purpose was to introduce you to the C++ programming language and
give you a crash course in how to write simple programs in that language. This
chapter focused on the low-level structure of the language, focusing on the concepts
of expressions and statements, which together make it possible to define functions.

Important points in this chapter include:

In the 30+ years of its existence, the C++ programming language has become
one of the most widely used languages in the world.
A typical C++ program consists of comments, library inclusions, program-level
definitions, function prototypes, a function named main that is called when the
program is started, and a set of auxiliary functions that work together with the
main program to accomplish the required task.
Variables in a C++ program must be declared before they are used. Most
variables in C++ are local variables, which are declared within a function and
can only be used inside the body of that function.
48 Overview of C++

A data type is defined by a domain of values and a set of operations. C++

includes several primitive types that allow programs to store common data values
including integers, floating-point numbers, Booleans, and characters. As you
will learn in later chapters, C++ also allows programmers to define new types
from existing ones.
The easiest way to perform input and output operations in C++ is to use the
iostream library. This library defines three standard streams that refer to the
console: cin for reading input data, cout for writing normal program output,
and cerr for reporting error messages. Console input is traditionally performed
using the >> operator, as in the statement

cin >> limit;

which reads a value from the console into the variable limit. Console output
uses the << operator, as illustrated by the line

cout << "The answer is " << answer << endl;

which would display the value of answer on the console along with an
identifying label. The endl value ensures that the next console output appears
on a new line.
Expressions in C++ are written in a form similar to that in most programming
languages, with individual terms connected by operators. A list of the C++
operators appears in Table 1-4 along with their precedence and associativity.
Statements in C++ fall into two general categories: simple statements and control
statements. A simple statement consists of an expressiontypically an
assignment or a function callfollowed by a semicolon. The control statements
described in this chapter are the if, switch, while, and for statements. The
first two are used to express conditional execution, while the last two are used to
specify repetition.
C++ programs are typically subdivided into several functions. You can use the
examples in this chapter as models for writing your own functions, or you can
wait until functions are covered in more detail in Chapter 2.

Review questions
1. When you write a C program, do you prepare a source file or an object file?

2. What characters are used to mark comments in a C++ program?

3. In an #include line, the name of the library header file can be enclosed in
either angle brackets or double quotation marks. What is the difference
between the two forms of punctuation?
 Review questions 49

4. How would you define a constant called CENTIMETERS_PER_INCH with the

value 2.54?

5. What is the name of the function that must be defined in every C++ program?
What statement typically appears at the end of that function?

6. What is the purpose of endl when you are writing to the cout output stream?

7. Define each of the following terms for variables: name, type, value, and scope.

8. Indicate which of the following are legal variable names in C++:

a. x g. total output
b. formula1 h. aVeryLongVariableName
c. average_rainfall i. 12MonthTotal
d. %correct j. marginal-cost
e. short k. b4hand
f. tiny l. _stk_depth

9. What are the two attributes that define a data type?

10. What is the difference between the types short, int, and long?

11. What does ASCII stand for?

12. List all possible values of type bool.

13. What statements would you include in a program to read a value from the user
and store it in the variable x, which is declared as a double?

14. Suppose that a function contains the following declarations:

int i;
double d;
char c;
string s;

Write a statement that displays the values of each of these variables on the
screen, along with the name of the variable so that you can tell the values apart.

15. Indicate the values and types of the following expressions:

a. 2 + 3 d. 3 * 6.0
b. 19 / 5 e. 19 % 5
c. 19.0 / 5 f. 2 % 7

16. What is the difference between the unary minus and the subtraction operator?

17. What does the term truncation mean?

50 Overview of C++

18. What is a type cast and how do you indicate one in C++?

19. Calculate the result of each of the following expressions:

a. 6 + 5 / 4 - 3
b. 2 + 2 * (2 * 2 - 2) % 2 / 2
c. 10 + 9 * ((8 + 7) % 6) + 5 * 4 % 3 * 2 + 1
d. 1 + 2 + (3 + 4) * ((5 * 6 % 7 * 8) - 9) - 10

20. How do you specify a shorthand assignment operation?

21. What is the difference between the expressions ++x and x++?

22. What is meant by short-circuit evaluation?

23. Write out the general syntactic form for each of the following control
statements: if, switch, while, for.

24. Describe in English the operation of the switch statement, including the role
of the break statement at the end of each case clause.

25. What is a sentinel?

26. What for loop control line would you use in each of the following situations?
a. Counting from 1 to 100
b. Counting by sevens starting at 0 until the number has more than two digits
c. Counting backward by twos from 100 to 0

Exercises
1. Write a program that reads in a temperature in degrees Celsius and displays the
corresponding temperature in degrees Fahrenheit. The conversion formula is

F= C + 32

2. Write a program that converts a distance in meters to the corresponding English

distance in feet and inches. The conversion factors you need are

1 inch = 0.0254 meters

1 foot = 12 inches

3. As mathematical historians have told the story, the German mathematician Carl
Friedrich Gauss (1777-1855) began to show his mathematical talent at a very
early age. When he was in elementary school, Gauss was asked by his teacher
to compute the sum of the numbers between 1 and 100. Gauss is said to have
 Exercises 51

given the answer instantly: 5050. Write a program that computes the answer to
the question Gausss teacher posed.

4. Write a program that reads in a positive integer N and then calculates and
displays the sum of the first N odd integers. For example, if N is 4, your
program should display the value 16, which is 1 + 3 + 5 + 7.

5. Write a program that reads in a list of integers from the user until the user
enters the value 0 as a sentinel. When the sentinel appears, your program
should display the largest value in the list, as illustrated in the following sample
run:

Be sure to define the sentinel value as a constant in a way that makes it easy to
change. You should also make sure that the program works correctly if all the
input values are negative.

6. For a slightly more interesting challenge, write a program that finds both the
largest and the second-largest number in a list, prior to the entry of a sentinel.
Once again using 0 as the sentinel, a sample run of this program might look like
this:

The values in this sample run are the number of pages in the British hardcover
editions of J. K. Rowlings Harry Potter series. The output therefore tells us
52 Overview of C++

that the longest book (Harry Potter and the Order of the Phoenix) has 766
pages and the second-longest book (Harry Potter and the Goblet of Fire)
weighs in at a mere 636 pages.

7. Using the AddIntegerList program from Figure 1-5 as a model, write a

program AverageList that reads in a list of integers representing exam scores
and then prints out the average. Because some unprepared student might
actually get a score of 0, your program should use !1 as the sentinel to mark the
end of the input.

8. Using the digitSum function from the section entitled The while statement
as a model, write a program that reads in an integer and then displays the
number that has the same digits in the reverse order, as illustrated by this
sample run:

9. Every positive integer greater than 1 can be expressed as a product of prime

numbers. This factorization is unique and is called the prime factorization.
For example, the number 60 can be decomposed into the factors 2 x 2 x 3 x 5,
each of which is prime. Note that the same prime can appear more than once in
the factorization.

Write a program to display the prime factorization of a number n, as

illustrated by the following sample run:

10. In 1979, Douglas Hofstadter, Professor of Cognitive Science at the University

of Indiana, wrote Gdel, Escher, Bach, which he described as a metaphorical
fugue on minds and machines in the spirit of Lewis Carroll. The book won
the Pulitzer Prize for Literature and has over the years become one of the
classics of computer science. Much of its charm comes from the mathematical
oddities and puzzles it contains, many of which can be expressed in the form of
computer programs. Of these, one of the most interesting concerns the
 Exercises 53

sequence of numbers formed by repeatedly executing the following rules for

some positive integer n:
If n is equal to 1, youve reached the end of the sequence and can stop.
If n is even, divide it by two.
If n is odd, multiply it by three and add one.
Although it also goes by several other names, this sequence is often called the
hailstone sequence because the values tend to go up and down before coming
back to 1, much as hailstones do in the clouds in which they form.
Write a program that reads in a number from the user and then generates the
hailstone sequence from that point, as in the following sample run:

As you can see, this program offers a narrative account of the process as it goes
along, much as Hofstadter does in his book.
One of the fascinating things about the hailstone sequence is that no one has
yet been able to prove that the process always stops. The number of steps in
the process can get very large, but somehow, it always seems to climb back
down to one.

11. The German mathematician Leibniz (16461716) discovered the rather

remarkable fact that the mathematical constant ! can be computed using the
following mathematical relationship:

" 1 + + + . . .

The formula to the right of the equal sign represents an infinite series; each
fraction represents a term in that series. If you start with 1, subtract one-third,
54 Overview of C++

add one-fifth, and so on, for each of the odd integers, you get a number that
gets closer and closer to the value of !/4 as you go along.
Write a program that calculates an approximation of ! consisting of the first
10,000 terms in Leibnizs series.

12. You can also compute ! by approximating the area bounded by a circular arc.
Consider the following quarter circle:

which has a radius r equal to two inches. From the formula for the area of a
circle, you can easily determine that the area of the quarter circle should be !
square inches. You can also approximate the area computationally by adding
up the areas of a series of rectangles, where each rectangle has a fixed width
and the height is chosen so that the circle passes through the midpoint of the top
of the rectangle. For example, if you divide the area into 10 rectangles from
left to right, you get the following diagram:

The sum of the areas of the rectangles approximates the area of the quarter
circle. The more rectangles there are, the closer the approximation.

For each rectangle, the width w is a constant derived by dividing the radius
by the number of rectangles. The height h, on the other hand, varies depending
on the position of the rectangle. If the midpoint of the rectangle in the
horizontal direction is given by x, the height of the rectangle can be computed
using the sqrt function to express the distance formula

h =

The area of each rectangle is then simply h " w.

Write a program to compute the area of the quarter circle by dividing it into
10,000 rectangles.
Chapter 2
Functions and Libraries

I have always imagined Paradise as a kind of library.

Jorge Luis Borges, Poem of the Gifts, 1960
56 Functions and Libraries

As you know from the examples from Chapter 1, programs in C++ typically consist
of a sequence of functions. This chapter looks more expansively at the idea of a
function and the realization of that concept in C++. In addition, this chapter
explores how functions can be stored in libraries, which makes it easier to use those
functions in a variety of applications.

2.1 The idea of a function

When you are in the early stages of your study of programming, your most
important responsibility is learning how to use functions effectively in programs.
Fortunately, the concept of a function is likely to be familiar from mathematics, so
that youre not learning a new concept completely from scratch. At the same time,
functions in C++ are much more general than their counterparts in mathematics,
which means that youll have to move beyond the mathematical conception and
think more expansively about how you might use functions as a programmer. The
sections that follow begin with the mathematical notion of a function and then
generalize that concept to encompass the applications of functions in the
programming domain.

Functions in mathematics
When you studied mathematics in high school, you almost certainly encountered the
concept of a function. For example, you might have seen a function definition like

(x) = x 2 + 1

which states that the function transforms a number x into the square of x plus one.
For any value of x, you can compute the value of the function simply by evaluating
the formula that appears in the definition. Thus, the value of (3) is 32 + 1, or 10.

Ever since the development of FORTRAN in the 1950s, programming languages

have incorporated this mathematical approach to functions into their computational
framework. For example, building on the examples of functions you saw in
Chapter 1, you know that you can implement the function in C++ like this:

double f(double x) {
return x * x + 1;
}

This definition includes various bits of syntax that are absent from the mathematical
formulation, but the basic idea is the same. The function f takes an input value
represented by the variable x and returns as its output the value of the expression
x * x + 1.
 2.1 The idea of a function 57

Functions in programming
In programming languages, the concept of a function is more general than it is in
mathematics. Like their mathematical counterparts, functions in C++ can specify
input values, but dont need to do so. Similarly, functions in C++ arent required to
return results. The essential characteristic of a C++ function is that it associates a
computational operationspecified by a block of code that forms the body of the
functionwith a particular name. Once a function has been defined, other parts of
the program can trigger the associated operations using only the function name.
There is no need to repeat the code for the underlying operation, because the steps
required to implement that operation are specified in the function body.

This model of functions in the context of programming makes it possible to

define several terms that are essential to understanding how functions work in C++.
First of all, a function is a block of code that has been organized into a separate unit
and given a name. The act of using the name to invoke that code is known as
calling that function. To specify a function call in C++, you write the name of the
function, followed by a list of expressions enclosed in parentheses. These
expressions, called arguments, allow the calling program to pass information to the
function. If a function requires no information from its caller, it need not have any
arguments, but an empty set of parentheses must appear in both the function
definition and any calls to that function.

Once called, the function takes the data supplied as arguments, does its work,
and then returns to the program at the point in the code from which the call was
made. Remembering what the calling program was doing so that the program can
get back to the precise location of the call is one of the essential characteristics of
the function-calling mechanism. The operation of going back to the calling
program is called returning from the function. As it returns, a function often passes
a value back to its caller. This operation is called returning a value.

The advantages of using functions

Functions play several important roles in a programming language. First, defining
functions makes it possible to write the code for an operation once but then use it
many times. The ability to invoke the same sequence of instructions from many
parts of a program can dramatically reduce its size. Having the code for a function
appear in just one place also makes a program easier to maintain. If you need to
make a change in the way a function operates, it is far easier to do so if the code
appears only once than if the same operations are repeated throughout the code.

Defining a function, however, is valuable even if you use that function only once
in a particular program. The most important role that functions play is that they
make it possible to divide a large program into smaller, more manageable pieces.
58 Functions and Libraries

This process is called decomposition. As you almost certainly know from your
prior experience with programming, writing a program as one monolithic block of
code is a sure-fire recipe for disaster. What you want to do instead is subdivide the
high-level problem into a set of lower-level functions, each of which makes sense
on its own. Finding the right decomposition, however, turns out to be a challenging
task that requires considerable practice. If you choose the individual pieces well,
each one will have integrity as a unit and make the program as a whole much
simpler to understand. If you choose unwisely, the decomposition can easily get in
your way. There are no hard-and-fast rules for selecting a particular decomposition.
Programming is an art, and you will learn to choose good decomposition strategies
mostly through experience.

As a general rule, however, it makes sense to begin the decomposition process

starting with the main program. At this level, you think about the problem as a
whole and try to identify the major pieces of the entire task. Once you figure out
what the big pieces of the program are, you can define them as independent
functions. Since some of these functions may themselves be complicated, it is often
appropriate to decompose them into still smaller ones. You can continue this
process until every piece of the problem is simple enough to be solved on its own.
This process is called top-down design or stepwise refinement.

Functions and algorithms

In addition to their role as a tool for managing complexity, functions are important
in programming because they provide a basis for the implementation of algorithms,
which are precisely specified strategies for solving computational problems. The
term comes from the name of the ninth-century Persian mathematician Abu Jafar
Mohammed ibn Ms al-Khowrizm, whose treatise on mathematics entitled Kitab
al jabr wal-muqabala gave rise to the English word algebra. Mathematical
algorithms, however, go back much further in history, and certainly extend at least
as far as the early Greek, Chinese, and Indian civilizations.

One of the earliest known algorithms worthy of that distinction is named for the
Greek mathematician Euclid, who lived in Alexandria during the reign of Ptolemy I
(323-283 BCE). In his great mathematical treatise called Elements, Euclid outlines a
procedure for finding the greatest common divisor (or gcd for short) of two integers
x and y, which is defined to be the largest integer that divides evenly into both. For
example, the gcd of 49 and 35 is 7, the gcd of 6 and 18 is 6, and the gcd of 32 and
33 is 1. In modern English, Euclids algorithm can be described as follows:

1. Divide x by y and compute the remainder; call that remainder r.

2. If r is zero, the algorithm is complete, and the answer is y.
3. If r is not zero, set x to the old value of y, set y equal to r, and repeat the process.
 2.2 Libraries 59

You can easily translate this algorithmic description into the following code in C++:

int gcd(int x, int y) {

int r = x % y;
while (r != 0) {
x = y;
y = r;
r = x % y;
}
return y;
}

Euclids algorithm is considerably more efficient than any strategy you would be
likely to discover on your own, and is still used today in a variety of practical
applications, including the implementation of the cryptographic protocols that
enable secure communication on the Internet.

At the same time, it is not easy to see exactly why the algorithm gives the correct
result. Fortunately for those who rely on it in modern-day applications, Euclid was
able to prove the correctness of his algorithm in Elements, Book VII, proposition 2.
While it is not always necessary to have formal proofs of the algorithms that drive
computer-based applications, having such proofs makes it possible to have more
confidence in the correctness of those programs.

2.2 Libraries
When you write a C++ program, most of the code the computer executes is not the
code you have written yourself, but the library code that you have loaded along with
your application. In a way, programs today are like icebergs, in which most of the
bulk lies hidden beneath the surface. If you want to become an effective C++
programmer, you need to spend at least as much time learning about the standard
libraries as you do learning the language itself.

Every program you have seen in this bookall the way back to the tiny
HelloWorld example at the beginning of Chapter 1includes the <iostream>
library, which gives the program access to the cin and cout streams. The details
of how those streams are implemented arent important to you when you are writing
HelloWorld or PowersOfTwo. Those implementations, in fact, are not simply
beyond your reach at the moment, but entirely beyond the scope of this book. In
your role as a programmer, all that matters is that you know how to use these
libraries and that the library implementations do what theyre supposed to do.

For some reason, beginning programmers are sometimes uncomfortable with the
idea of calling a function without understanding its underlying implementation. In
60 Functions and Libraries

fact, youve probably been doing precisely that in mathematics for a long time. In
high school, you presumably encountered several functions that turned out to be
useful even if you had no ideaand probably no interestin how the values of that
function are computed. In your algebra classes, for example, you learned about
functions like logarithms and square root. If you took a trigonometry course, you
worked with functions like sine and cosine. If you needed to know the value of one
of these functions, you didnt compute the result by hand, but instead looked up the
answer in a table or, more likely, typed the appropriate values into a calculator.

When youre writing programs, you want to follow that same strategy. If you
need to invoke some mathematical function, what you want to have is a library
function that computes it with no more conceptual effort than it takes to press the
right key on a calculator. Fortunately, C++ has an extensive mathematical library
called <cmath> that includes all the functions you are ever likely to need. The most
common functions in the <cmath> library appear in Table 2-1. Dont worry if you
 2.3 Defining functions in C++ 61

have no idea what some of those functions mean. This book requires very little
mathematics and will explain any concepts beyond basic algebra as they come up.

Whenever a library makes some service available to the programs that include it,
computer scientists say that the library exports that service. The <iostream>
library, for example, exports the cin and cout streams; the <cmath> library
exports the sqrt function, along with the other functions in Table 2-1.

One of the design goals of any library is to hide the complexity involved in the
underlying implementation. By exporting the sqrt function, the designers of the
<cmath> library make it far easier to write programs that use it. When you call the
sqrt function, you dont need to have any idea how sqrt works internally. Those
details are relevant only to the programmers who implement the <cmath> library in
the first place.

Knowing how to call the sqrt function and knowing how to implement it are
both important skills. It is important to recognize, however, that those two skills
calling a function and implementing oneare to a large extent independent.
Successful programmers often use functions that they wouldnt have a clue how to
write. Conversely, programmers who implement a library function can never
anticipate all the potential uses for that function.

To emphasize the difference in perspective between programmers who

implement a library and those who use it, computer scientists have assigned names
to programmers working in each of these roles. Naturally enough, a programmer
who implements a library is called an implementer. Conversely, a programmer who
calls functions provided by a library is called a client of that library. As you go
through the chapters in this book, you will have a chance to look at several libraries
from both of these perspectives, first as a client and later as an implementer.

2.3 Defining functions in C++

Although you saw several functions in Chapter 1 and even had a chance to write a
few of your own in the exercises, it makes sense to review the rules for writing
functions in C++ before going on to investigate how to use them most effectively.
In C++, a function definition has the following syntactic form:

type name(parameters) {
. . . body . . .
}

In this example, type is the type returned by the function, name is the function name,
and parameters is a list of declarations separated by commas, giving the type and
name of each parameter to the function. A parameter is a placeholder for one of the
62 Functions and Libraries

arguments supplied in the function call and acts in most respects like a local
variable. The only difference is that each parameter is initialized automatically to
hold the value of the corresponding argument. If a function takes no parameters, the
entire parameter list in the function header line is empty.

The body of the function is a block consisting of the statements that implement
the function, along with the declarations of any local variables the function requires.
For functions that return a value to their caller, at least one of those statements must
be a return statement, which usually has the form

return expression;

Executing the return statement causes the function to return immediately to its
caller, passing back the value of the expression as the value of the function.

Functions can return values of any type. The following function, for example,
returns a Boolean value indicating whether the argument n is an even integer:

bool isEven(int n) {
return n % 2 == 0;
}

Once you have defined this function, you can use it in an if statement like this:

if (isEven(i)) . . .

As noted in Chapter 1, functions that return Boolean results play an important role
in programming and are called predicate functions.

Functions, however, do not need to return a value at all. A function that does not
return a value and is instead executed for its effect is often called a procedure.
Procedures are indicated in the definition of a function by using the reserved word
void as the result type. Procedures ordinarily finish by reaching the end of the
statements in the body. You can, however, signal early completion of a procedure
by executing a return statement without a value expression, as follows:

return;

Function prototypes
When the C++ compiler encounters a function call in your program, it needs to have
some information about that function in order to generate the correct code. In most
cases, the compiler doesnt need to know all the steps that form the body of the
function. All it really needs to know is what arguments the function requires and
what type of value it returns. That information is usually provided by a prototype,
which is simply the header line of the function followed by a semicolon.
 2.3 Defining functions in C++ 63

You have already seen examples of prototypes in Chapter 1. The PowersOfTwo

program from Figure 1-3, for example, provides the following prototype for the
raiseToPower function:

int raiseToPower(int n, int k);

which tells the compiler that raiseToPower takes two integers as arguments and
returns an integer as its result. The names of the parameters are optional in a
prototype, but supplying them usually helps the reader.

If you always define functions before you call them, prototypes are not required.
Some programmers organize their source files so that the low-level functions come
at the beginning, followed by the intermediate-level functions that call them, with
the main program coming at the very bottom. While this strategy can save a few
prototype lines, it forces an order on the source file that often makes it harder for the
reader to figure out what is going on. In particular, programs organized in this way
end up reflecting the opposite of top-down design, since the most general functions
appear at the end. In this text, every function other than main has an explicit
prototype, which makes it possible to define those functions in any order.

Overloading
In C++, it is legal to give the same name to more than one function as long as the
pattern of arguments is different. When the compiler encounters a call to a function
with that name, it checks to see what arguments have been provided and chooses the
version of the function that fits those arguments. Using the same name for more
than one version of a function is called overloading. The pattern of arguments
taken by a functionwhich refers only to the number and types of the arguments
and not the parameter namesis called its signature.

As an example of overloading, the <cmath> library includes several versions of

the function abs, one for each of the built-in arithmetic types. For example, the
library includes the function

int abs(int x) {
return (x < 0) ? -x : x;
}

as well as the identically named function

double abs(double x) {
return (x < 0) ? -x : x;
}
64 Functions and Libraries

The only difference between these functions is that the first version takes an int as
its argument and the second takes a double. The compiler chooses which of these
versions to invoke by looking at the types of the arguments the caller provides.
Thus, if abs is called with an int, the compiler invokes the integer-valued version
of the functions and returns a value of type int. If, by contrast, the argument is of
type double, the compiler will choose the version that takes a double.

The primary advantage of using overloading is that doing so makes it easier for
you as a programmer to keep track of different function names for the same
operation when it is applied in slightly different contexts. If, for example, you need
to call the absolute value function in C, which does not support overloading, you
have to remember to call fabs for floating-point numbers and abs for integers. In
C++, all you need to remember is the single function name abs.

Default parameters
In addition to overloading, C++ makes it possible to specify that certain parameters
are optional. The parameter variables still appear in the function header line, but the
prototype for the function specifies the values that those parameters should have if
they do not appear in the call. Such parameters are called default parameters.

To indicate that a parameter is optional, all you need to do is include an initial

value in the declaration of that parameter in the function prototype. For example, if
you were designing a set of functions to implement a word processor, you might
define a procedure with the following prototype:

void formatInColumns(int nColumns = 2);

The formatInColumns procedure takes the number of columns as an argument,

but the = 2 in the prototype declaration means that this argument may be omitted. If
you leave it out and call

formatInColumns();

the parameter variable nColumns will automatically be initialized to 2.

When you use default parameters, it helps to keep the following rules in mind:

The specification of the default value appears only in the function prototype and
not in the function definition.
Any default parameters must appear at the end of the parameter list.

Default parameters tend to be overused in C++. It is always possibleand

usually preferableto achieve the same effect through overloading. Suppose, for
 2.4 The mechanics of function calls 65

example, that you want to define a procedure setInitialLocation that takes an

x and a y coordinate as arguments. The prototype presumably looks like this:

void setInitialLocation(double x, double y);

Now suppose that you want to change this definition so that the initial location
defaults to the origin (0, 0). One way to accomplish that goal is to add initializers to
the prototype, like this:

void setInitialLocation(double x = 0, double y = 0);

While this definition has the desired effect, having it in place makes it possible to
call setInitialLocation with one argument, which would almost certainly be
confusing to anyone reading the code. It is almost certainly better to define an
overloaded version of the function with the following implementation:

void setInitialLocation() {
setInitialLocation(0, 0);
}

2.4 The mechanics of function calls

Although you can certainly get by with an intuitive understanding of how the
function-calling process works, it sometimes helpsparticularly when you start to
work with recursive functions in Chapter 7to understand precisely what happens
when one function calls another in C++. The sections that follow define the process
in detail and then walk you through a simple example designed to help you visualize
exactly what is going on.

The steps in calling a function

Whenever a function call occurs, the C++ compiler generates code to implement the
following operations:

1. The calling function computes values for each argument using the bindings of
local variables in its own context. Because the arguments are expressions, this
computation can involve operators and other functions, all of which are
evaluated before execution of the new function actually begins.
2. The system creates new space for all the local variables required by the new
function, including any parameters. These variables are allocated together in a
block, which is called a stack frame.
3. The value of each argument is copied into the corresponding parameter
variable. If there is more than one argument, the arguments are copied into the
parameters in order; the first argument is copied into the first parameter, and so
66 Functions and Libraries

forth. If necessary, type conversions are performed between the argument

values and the parameter variables, as in an assignment statement. For
example, if you pass a value of type int to a function that expects a parameter
of type double, the integer is converted into the equivalent floating-point value
before it is copied into the parameter variable.
4. The statements in the function body are executed until the program encounters
a return statement or there are no more statements to execute.
5. The value of the return expression, if any, is evaluated and returned as the
value of the function. If the value being returned does not precisely match the
result type declared for the function, a type conversion is performed. Thus, if a
return statement specifies a floating-point value in a function defined to
return an int, the result is truncated to an integer.
6. The stack frame created for this function call is discarded. In the process, all
local variables disappear.
7. The calling program continues, with the returned value substituted in place of
the call.

Although this process may seem to make sense, you probably need to work
through an example or two before you understand it thoroughly. Reading through
the example in the next section will give you some insight into the process, but it is
probably even more helpful to take one of your own programs and walk through it
at the same level of detail. And while you can trace through a program on paper or
a whiteboard, it may be better to get yourself a supply of 3 ! 5 index cards and then
use a card to represent each stack frame. The advantage of the index-card model is
that you can create a stack of index cards that closely models the operation of the
computer. Calling a function adds a card; returning from the function removes it.

The combinations function

Suppose that you have a collection of six coins, which in the United States might be
a penny, a nickel, a dime, a quarter, a half-dollar, and a dollar. Given those six
coins, how many ways are there to choose two of them? As you can see from the
full enumeration of the possibilities in Figure 2-1, the answer is 15. As a computer
scientist, you should immediately think about the more general question: Given a
set containing n distinct elements, how many ways can you choose a subset with k
elements? The answer to that question is well known in mathematics and is
computed by the combinations function C(n, k), which is defined as follows:

C(n, k) =

where the exclamation point indicates the factorial function, which is simply the
product of the integers between 1 and the specified number, inclusive.
 2.4 The mechanics of function calls 67

The code to compute the combinations function in C++ appears in Figure 2-2, along
with a main program that requests values of n and k from the user and then displays
the value of the function C(n, k). A sample run of the program might look like this:

As you can see from Figure 2-2, the Combinations program is divided into
three functions. The main function handles the interaction with the user. The
combinations function computes C(n, k). Finally, the fact function, which is
borrowed from Chapter 1, computes the factorials required for the computation.
68 Functions and Libraries

Figure 2-2.
 2.4 The mechanics of function calls 69

Tracing the combinations function

While the Combinations program can be interesting in its own right, the purpose
of this example is to illustrate the steps involved in executing functions. In C++, all
programs begin by making a call to the function main. To implement a function
call, the systemwhich encompasses both the operating system youre using and
the hardware on which it runscreates a new stack frame to keep track of the local
variables that function declares. In the Combinations program, the main function
declares two integers, n and k, so the stack frame must include space for these
variables.

In the diagrams in this book, each stack frame appears as a rectangle surrounded
by a double line. The frame rectangle shows the code for the function along with a
pointing-hand icon that makes it easy to keep track of the current execution point. It
also contains labeled boxes for each of the local variables. The stack frame for
main therefore looks like this when execution begins:

From this point, the system executes the statements in order, printing out the
prompts on the console, reading in the associated values from the user, and storing
those values in the variables in that frame. If the user enters the values shown in the
earlier sample run, the frame will look like this when it reaches the statement that
displays the result:
70 Functions and Libraries

Before the program can complete the output line, it has to evaluate the call to
combinations(n, k). At this point, the function main is calling the function
combinations, which means that the computer has to go through all the steps that
are required in making a function call.

The first step is to evaluate the arguments in the context of the current frame.
The variable n has the value 6, and the variable k has the value 2. These two
arguments are then copied into the parameter variables n and k when the computer
creates the combinations stack frame. The new frame gets stacked on top of the
old one, which allows the computer to remember the values of the local variables in
main, even though they are not currently accessible. The situation after creating the
new frame and initializing the parameter variables looks like this:

To compute the value of the combinations function, the program must make
three calls to the function fact. In C++, those function calls can happen in any
order, but its easiest to process them from left to right. The first call, therefore, is
the call to fact(n). To evaluate this function, the system must create yet another
stack frame, this time for the function fact with an argument value of 6:

Unlike the earlier stack frames, the frame for fact includes both parameters and
local variable. The parameter n is initialized to the value of the calling argument
 2.4 The mechanics of function calls 71

and therefore has the value 6. The two local variables, i and result, have not yet
been initialized, but the system nonetheless needs to reserve space in the frame for
those variables. Until you assign a new value to those variables, they will contain
whatever data happened to be left over in the memory cells assigned to that stack
frame, which is completely unpredictable. It is therefore important to initialize all
local variables before you use them, ideally as part of the declaration.

The system then executes the statements in the function fact. In this instance,
the body of the for loop will be executed six times. On each cycle, the value of
result is multiplied by the loop index i, which means that it will eventually hold
the value 720 (1 ! 2 ! 3 ! 4 ! 5 ! 6 or 6!). When the program reaches the return
statement, the stack frame looks like this:

In this diagram, the box for the variable i is empty, because the value of i is no
longer defined at this point in the program. In C++, index variables declared in a
for loop header are accessible only inside the loop body. Showing an empty box
emphasizes the fact that the value of i is no longer available.

Returning from a function involves copying the value of the return expression
(in this case the local variable result), into the point at which the call occurred.
The frame for fact is then discarded, which leads to the following configuration:
72 Functions and Libraries

The next step in the process is to make a second call to fact, this time with the
argument k. In the calling frame, k has the value 2. That value is then used to
initialize the parameter n in the new stack frame, as follows:

The computation of fact(2) is a bit easier to perform in ones head than the
earlier call to fact(6). This time around, the value of result will be 2, which is
then returned to the calling frame, like this:

The code for combinations makes one more call to fact, this time with the
argument n - k. As before, this call creates a new frame with n equal to 4:
 2.5 Reference parameters 73

The value of fact(4) is 1 ! 2 ! 3 ! 4, or 24. When this call returns, the system is
able to fill in the last of the missing values in the calculation, as follows:

The computer then divides 720 by the product of 2 and 24 to get the answer 15.
This value is then returned to the main function, which leads to the following state:

From here, all that remains is to generate the output line and return from the
main function, which completes the execution of the program.

2.5 Reference parameters

In C++, whenever you pass a simple variable from one function to another, the
function gets a copy of the calling value. Assigning a new value to the parameter as
part of the function changes the local copy but has no effect on the calling
argument. For example, if you try to implement a procedure that initializes a
variable to zero using the code

void setToZero(int var) {

var = 0;
}
74 Functions and Libraries

that procedure ends up having no effect whatever. If you call

setToZero(x);

the parameter var is initialized to a copy of whatever value is stored in x. The

assignment statement

var = 0;

inside the function sets the local copy to 0 but leaves x unchanged in the calling
program.

If you want to change the value of the calling argumentand there are often
compelling reasons for doing soyou can change the parameter from the usual kind
of C++ parameter (which is called a value parameter) into a reference parameter
by adding an ampersand between the type and the name in the function header.
Unlike value parameters, reference parameters are not copied. What happens
instead is that the function receives a reference to the original variable, which means
that the memory used for that variable is shared between the function and its caller.
The new version of setToZero looks like this:

void setToZero(int & var) {

var = 0;
}

This style of parameter passing is known as call by reference. When you use
call by reference, the argument corresponding to the reference parameter must be an
assignable value, such as a variable name. Although calling setToZero(x) would
correctly set the integer variable x to 0, it would be illegal to call setToZero(3)
because 3 is not assignable.

In C++, one of the most common uses of call by reference occurs when a
function needs to return more than one value to the calling program. A single result
can easily be returned as the value of the function itself. If you need to return more
than one result from a function, the return value is no longer appropriate. The
standard approach to solving the problem is to turn that function into a procedure
and pass values back and forth through the argument list.

As an example, suppose that you are writing a program to solve the quadratic
equation

ax2 + bx + c = 0

Because of your commitment to good programming style, you want to structure that
program into three phases as illustrated in the following flowchart:
 2.5 Reference parameters 75

The Quadratic program in Figure 2-3 shows how call by reference makes it
possible to decompose the quadratic equation problem in this way. Each of the
functions in Figure 2-3 corresponds to one of the phases in the flowchart. The main
program provides information to the function using conventional parameters.
Whenever a function needs to get information back to the main program, it uses
reference parameters. The solveQuadratic function uses parameters of each
type. The parameters a, b, and c are used as input to the function and give it access
to the three coefficients. The parameters x1 and x2 are output parameters and allow
the program to pass back the two roots of the quadratic equation.

The Quadratic program also introduces a new strategy for reporting errors.
Whenever the code encounters a condition that makes further progress impossible, it
calls a function named error that prints a message indicating the nature of the
problem and then terminates the execution of the program. The code for error
looks like this:

void error(string msg) {

cerr << msg << endl;
exit(EXIT_FAILURE);
}

The code for error uses two features of C++ that have not yet made their
appearance in this book: the cerr output stream and the exit function. The cerr
stream is similar to cout, but is reserved for reporting errors. The exit function
terminates the execution of the main program immediately, using the value of the
parameter to report the program status. The constant EXIT_FAILURE is defined in
the <cstdlib> library and is used to indicate that some kind of failure occurred.
76 Functions and Libraries

page 1 of figure.
 2.5 Reference parameters 77

The error function, of course, would be useful in many applications beyond the
one that solves quadratic equations. Although you could easily copy the code into
another program, it would make much more sense to save the error function in a
library. In the following section, youll have a chance to do precisely that.
78 Functions and Libraries

2.6 Interfaces and implementations

When you define a library in C++, you need to supply two parts. First, you must
define the interface, which provides the information clients need to use the library
but leaves out the details about how the library works. Second, you need to provide
the implementation, which specifies the underlying details. A typical interface will
export several definitions, which are typically functions, types, or constants. Each
individual definition is called an interface entry.

In C++, the interface and implementation are usually written as two separate
files. The name of the interface file ends with .h, which marks it as a header file.
The implementation appears in a file with the same root, but with the suffix .cpp.
Following this convention, the error library is defined in the file error.h and
implemented in the file error.cpp.

Defining the error library

The contents of the error.h interface appear in Figure 2-4. As you can see, the
file consists mostly of comments. The only other parts of the interface are the
prototype for the error function and three additional lines that are often referred to
as interface boilerplate, which is a patterned set of lines that appears in every
 2.6 Interfaces and implementations 79

interface. In this interface, the boilerplate consists of the #ifndef and #define
lines at the beginning of the interface and the matching #endif line at the end.
These lines make sure that the compiler doesnt compile the same interface twice.
The #ifndef directive checks whether the _error_h symbol has been defined.
When the compiler reads this interface for the first time, the answer is no. The next
line, however, defines that symbol. Thus, if the compiler is later asked to read the
same interface, the _error_h symbol will already be defined, and the compiler will
skip over the contents of the interface this time around. This book uses the
convention of checking for a symbol that begins with an underscore followed by the
name of the interface file after replacing the dot with a second underscore.

The prototype for error, however, looks slightly different when it appears in
interface form. The parameter declaration now uses the type name std::string
to indicate that string comes from the std namespace. Interfaces are typically
read before the using namespace std line and therefore cannot use identifiers
from that namespace without explicitly including the std:: qualifier.

The error.cpp implementation appears in Figure 2-5. Comments in the

implementation are intended for programmers responsible for maintaining the
library and are often less extensive than those in the interface. Here, the body of the
80 Functions and Libraries

error function is all of two lines long, and the purpose of each of those lines is
instantly recognizable to any C++ programmer.

Exporting types
The error.h interface described in the preceding section exports a single function
and nothing else. Most of the interfaces you will use in C++ also export data types.
Most of these types will be classes, which are the foundation of the object-oriented
type system that C++ provides. Given that you wont learn how to define your own
classes until Chapter 6, it is premature to introduce class-based examples at this
point in the text. What does make sense is to create an interface that exports one of
the enumerated types introduced in Chapter 1, such as the Direction type used to
encode the four standard compass points:

enum Direction { NORTH, EAST, SOUTH, WEST };

The simplest approach to making this type accessible through a library interface
would be to write a direction.h interface that contained only this line along with
the usual interface boilerplate. If you were to adopt that strategy, you wouldnt
need to supply an implementation at all.

It is more useful, however, to have this interface export some simple functions
for working with Direction values. For example, it would be useful to export the
directionToString function defined on page 40, which returns the name of a
direction given the enumerated value. For some of the programs that appear later in
this book, it will be useful to have functions leftFrom and rightFrom that return
the Direction value that results from turning 90 degrees in the specified direction,
so that, for example, leftFrom(NORTH) would return WEST. If you add these
functions to the direction.h interface, you will also need to supply a
direction.cpp file to implement those functions. Those files appear in
Figures 2-6 and 2-7.

The implementations of leftFrom and rightFrom require some subtlety that is

worth a little explanation. While C++ lets you freely convert an enumerated value
to an integer, conversions in the opposite directionfrom an integer to the
corresponding value of an enumerated typerequire a type cast. This fact is
illustrated by the implementation of rightFrom, which looks like this:

Direction rightFrom(Direction dir) {

return Direction((dir + 1) % 4);
}
 2.6 Interfaces and implementations 81

direction.h
82 Functions and Libraries

The arithmetic operators in the expression

(dir + 1) % 4

automatically convert the Direction value to its underlying representation as an

 2.6 Interfaces and implementations 83

integer: 0 for NORTH, 1 for EAST, 2 for SOUTH, and 3 for WEST. Turning right from
one of these compass points corresponds to adding one to the underlying value, with
the exception to turning right from WEST, when it is necessary to cycle back to the
value 0 to indicate the direction NORTH. As is so often the case in situations that
involve cyclical structures, using the % operator eliminates the need for special-case
testing. Before it returns, however, the function must use a type cast to convert the
result of the arithmetic expression to the Direction value that rightFrom is
defined to return.

As a cautionary reminder about the dangers of using % with negative numbers,

the leftFrom function cannot be defined as

Direction leftFrom(Direction dir) {

return Direction((dir - 1) % 4);
}

The problem with this implementation arises when you call leftFrom(NORTH).
When dir has the value NORTH, the expression

(dir - 1) % 4

has the value 1 on most machines, which is not a legal Direction. Fortunately, it
is easy to fix the problem by coding leftFrom like this:

Direction leftFrom(Direction dir) {

return Direction((dir + 3) % 4);
}

Exporting constant definitions

In addition to functions and types, interfaces often export constant definitions so
that several clients can share that constant without redefining it in every source file.
If, for example, you are writing programs that involve geometrical calculations, it is
useful to have a definition of the mathematical constant !, which, given the usual
conventions for constants, would presumably be named PI. If you declare PI as a
constant in the fashion introduced in Chapter 1, you would write

const double PI = 3.14159265358979323846;

In C++, constants written in this form are private to the source file that contains
them and cannot be exported through an interface. To export the constant PI, you
need to add the keyword extern to both its definition and the prototype declaration
in the interface. This strategy is illustrated by the gmath.h interface in Figure 2-8,
which exports PI along with some simple functions that simplify working with
angles in degrees. The corresponding implementation appears in Figure 2-9.
84 Functions and Libraries

the gmath.h interface

 2.7 Principles of interface design 85

2.7 Principles of interface design

One of the reasons that programming is difficult is that programs reflect the
complexity of the underlying application. As long as computers are used to solve
problems of ever-increasing sophistication, the process of programming will of
necessity become more sophisticated as well.

Writing a program to solve a large or difficult problem forces you to manage a

staggering amount of complexity. There are algorithms to design, special cases to
consider, user requirements to meet, and innumerable details to get right. To make
programming manageable, you must reduce the complexity of the programming
process as much as possible. Functions reduce some of the complexity; libraries
offer a similar reduction in programming complexity but at a higher level of detail.
A function gives its caller access to a set of steps that together implement a single
operation. A library gives its client access to a set of functions and types that
implement what computer scientists describe as a programming abstraction. The
extent to which a particular abstraction simplifies the programming process,
however, depends on how well you have designed its interface.
86 Functions and Libraries

To design an effective interface, you must balance several criteria. In general,

you should try to develop interfaces that are

Unified. An interface should define a consistent abstraction with a clear unifying

theme. If a function does not fit that theme, it should be defined elsewhere.
Simple. To the extent that the underlying implementation is itself complex, the
interface must seek to hide that complexity from the client.
Sufficient. When clients use an abstraction, the interface must provide sufficient
functionality to meet their needs. If some critical operation is missing from an
interface, clients may decide to abandon it and develop their own, more powerful
abstraction. As important as simplicity is, the designer must avoid simplifying
an interface to the point that it becomes useless.
General. A well-designed interface should be flexible enough to meet the needs
of many different clients. An interface that performs a narrowly defined set of
operations for one client is not as useful as one that can be used in many
different situations.
Stable. The functions defined in an interface should continue to have precisely
the same structure and effect, even if the underlying implementation changes.
Making changes in the behavior of an interface forces clients to change their
programs, which compromises the value of interface.

The sections that follow discuss each of these criteria in detail.

The importance of a unifying theme

Unity gives strength.
Aesop, The Bundle of Sticks, ~600 BCE
A central feature of a well-designed interface is that it presents a unified and
consistent abstraction. In part, this criterion implies that the functions within a
library should be chosen so that they reflect a coherent theme. Thus, the <cmath>
library exports mathematical functions, the <iostream> library exports the cin,
cout, and cerr streams along with the operators that perform input and output, and
the error.h interface introduced in section 2.6 exports a function for reporting
errors. Each interface entry exported by these libraries fits the purpose of that
interface. For example, you would not expect to find sqrt in the <string> library
since it fits much more naturally into the framework of the <cmath> library.

The principle of a unifying theme also influences the design of the functions
within a library interface. The functions within an interface should behave in as
consistent a way as possible. For example, all the functions in the <cmath> library
measure angles in radians. If some functions measured angles in degrees, clients
would have to remember what units to use for each function.
 2.7 Principles of interface design 87

Simplicity and the principle of information hiding

Embrace simplicity.
Lao-tzu, The Way of Lao-tzu, ~550 BCE
Because a primary goal of using interfaces is to reduce the complexity of the
programming process, it makes sense that simplicity is a desirable criterion in the
design of an interface. In general, an interface should be as easy to use as possible.
The underlying implementation may perform extremely intricate operations, but the
client should be able to think about those operations in a simple, more abstract way.

To a certain extent, an interface acts as a reference guide to a particular library

abstraction. When you want to know how to use the error function, you consult
the error.h interface to find out how to do so. The interface contains precisely the
information that you, as a client, need to knowand no more. For clients, getting
too much information can be as bad as getting too little, because additional detail is
likely to make the interface more difficult to understand. Often, the real value of an
interface lies not in the information it reveals but rather in the information it hides.

When you design an interface, you should try to protect the client from as many
of the complicating details of the implementation as possible. In that respect, it is
perhaps best to think of an interface not primarily as a communication channel
between the client and the implementation, but instead as a wall that divides them.

Like the wall that divided the lovers Pyramus and Thisbe in Greek mythology,
the wall representing an interface contains a chink that allows the client and the
implementation to communicate. The main purpose of the wall, however, is to keep
the two sides apart. Because we conceive of it as lying at the border of the
abstraction represented by the library, an interface is sometimes called an
abstraction boundary. Ideally, all the complexity involved in the realization of a
library lies on the implementation side of the wall. The interface is successful if it
keeps that complexity away from the client side. Keeping details confined to the
implementation domain is called information hiding.

The principle of information hiding has important practical implications for

interface design. When you write an interface, you should be sure you dont reveal
details of implementation, even in the commentary. Especially if you are writing an
interface and an implementation at the same time, you may be tempted to describe
88 Functions and Libraries

in your interface all the clever ideas you used in the implementation. Try to resist
that temptation. The interface is written for the benefit of the client and should
contain only what the client needs to know.

Similarly, you should design the functions in an interface so that they are as
simple as possible. If you can reduce the number of arguments or find a way to
eliminate confusing special cases, it will be easier for the client to understand how
to use those functions. Moreover, it is good practice to limit the total number of
functions exported by interface, so that the client does not become lost in a mass of
functions, unable to make sense of the whole.

Meeting the needs of your clients

Everything should be as simple as possible, but no simpler.
attributed to Albert Einstein
Simplicity is only part of the story. You can easily make an interface simple just by
throwing away any parts of it that are hard or complicated. There is a good chance
you will also make the interface useless. Sometimes clients need to perform tasks
that have some inherent complexity. Denying your clients the tools they require just
to make the interface simpler is not an effective strategy. Your interface must
provide sufficient functionality to serve the clients needs. Learning to strike the
right balance between simplicity and completeness in interface design is one of the
fundamental challenges in programming.

In many cases, the clients of an interface are concerned not only with whether a
particular function is available but also with the efficiency of its implementation.
For example, if you are developing a system for air-traffic control and need to call
functions provided by a library interface, those functions must return the correct
answer quickly. Late answers may be just as devastating as wrong answers.

For the most part, efficiency is a concern for the implementation rather than the
interface. Even so, you will often find it valuable to think about implementation
strategies while you are designing the interface itself. Suppose, for example, that
you are faced with a choice of two designs. If you determine that one of them
would be much easier to implement efficiently, it makes senseassuming there are
no compelling reasons to the contraryto choose that design.

The advantages of general tools

Give us the tools and we will finish the job.
Winston Churchill, BBC broadcast, 1941
An interface that is perfectly adapted to a particular clients needs may not be useful
to others. A good library abstraction serves the needs of many different clients. To
 2.7 Principles of interface design 89

do so, it must be general enough to solve a wide range of problems and not be
limited to one highly specific purpose. By choosing a design that offers flexibility,
you can create interfaces that are widely used.

The desire to ensure that an interface remains general has an important practical
implication. When you are writing a program, you will often discover that you need
a particular tool. If you decide that the tool is important enough to go into a library,
you then need to change your mode of thought. When you design the interface for
that library, you have to forget about the original application and instead design
your interface for a more general audience.

The value of stability

People change and forget to tell each other. Too bad
causes so many mistakes.
Lillian Hellman, Toys in the Attic, 1959
Interfaces have another property that makes them critically important to
programming: they tend to be stable over long periods of time. Stable interfaces
can dramatically simplify the problem of maintaining large programming systems
by establishing clear boundaries of responsibility. As long as the interface does not
change, both implementers and clients are relatively free to make changes on their
own side of the abstraction boundary.

For example, suppose that you are the implementer of the math library. In the
course of your work, you discover a clever new algorithm for calculating the sqrt
function that cuts in half the time required to calculate a square root. If you can say
to your clients that you have a new implementation of sqrt that works just as it did
before, only faster, they will probably be pleased. If, on the other hand, you were to
say that the name of the function had changed or that its use involved certain new
restrictions, your clients would be justifiably annoyed. To use your improved
implementation of square root, they would be forced to change their programs.
Changing programs is a time-consuming, error-prone activity, and many clients
would happily give up the extra efficiency for the convenience of being able to
leave their programs alone.

Interfaces, however, simplify the task of program maintenance only if they

remain stable. Programs change frequently as new algorithms are discovered or as
the requirements of applications change. Throughout such evolution, however, the
interfaces must remain as constant as possible. In a well-designed system, changing
the details of an implementation is a straightforward process. The complexity
involved in making that change is localized on the implementation side of the
abstraction boundary. On the other hand, changing an interface often produces a
global upheaval that requires changing every program that depends on it. Thus,
90 Functions and Libraries

interface changes should be undertaken very rarely and then only with the active
participation of clients.

Some interface changes, however, are more drastic than others. For example,
adding an entirely new function to an interface is usually a relatively
straightforward process, since no clients already depend on that function. Changing
an interface in such a way that existing programs will continue to run without
modification is called extending the interface. If you find that you need to make
evolutionary changes over the lifetime of an interface, it is usually best to make
those changes by extension.

2.8 Designing a random number library

The easiest way to illustrate the principles of interface design is to go through a
simple design exercise. To this end, this section goes through the design process
leading up to the creation of the random.h interface in the Stanford libraries, which
makes it possible to write programs that make seemingly random choices. Being
able to simulate random behavior is necessary, for example, if you want to write a
computer game that involves flipping a coin or rolling a die, but is also useful in
more practical contexts, as well. Programs that simulate such random events are
called nondeterministic programs.

Getting a computer to behave in a random way involves a certain amount of

complexity. For the benefit of client programmers, you want to hide this
complexity behind an interface. In this section, you will have the opportunity to
focus your attention on that interface from several different perspectives: that of the
interface designer, the implementer, and the client.

Random versus pseudorandom numbers

Partly because early computers were used primarily for numerical applications, the
idea of generating randomness using a computer is often expressed in terms of
being able to generate a random number in a particular range. From a theoretical
perspective, a number is random if there is no way to determine in advance what
value it will have among a set of equally probable possibilities. For example,
rolling a die generates a random number between 1 and 6. If the die is fair, there is
no way to predict which number will come up. The six possible values are equally
likely.

Although the idea of a random number makes intuitive sense, it is a difficult

notion to represent inside a computer. Computers operate by following a sequence
of instructions in memory and therefore function in a deterministic mode. How is it
possible to generate unpredictable results by following a deterministic set of rules?
 2.8 Designing a random number library 91

If a number is the result of a deterministic process, any user should be able to work
through that same set of rules and anticipate the computers response.

Yet computers do in fact use a deterministic procedure to generate what we call

random numbers. This strategy works because, even though the user could, in
theory, follow the same set of rules and anticipate the computers response, no one
actually bothers to do so. In most practical applications, it doesnt matter if the
numbers are truly random; all that matters is that the numbers appear to be random.
For numbers to appear random, they should (1) behave like random numbers from a
statistical point of view and (2) be sufficiently difficult to predict in advance that no
user would bother. Random numbers generated by an algorithmic process inside
a computer are referred to as pseudorandom numbers to underscore the fact that no
truly random activity is involved.

Pseudorandom numbers in the standard libraries

The <cstdlib> library exports a low-level function called rand that produces
pseudorandom numbers. The prototype for rand is

int rand();

which indicates that rand takes no arguments and returns an integer. Each call to
rand produces a different value that is difficult for clients to predict and therefore
appear to be random. The result of rand is guaranteed to be nonnegative and no
larger than the constant RAND_MAX, which is also defined in <cstdlib>. Thus,
each time you call rand, it returns a different integer between 0 and RAND_MAX,
inclusive.

If you want to get a feel for how the rand function works, one strategy is to
write a simple program to test it. The RandTest program in Figure 2-10 displays
the value of RAND_MAX and then prints out the result of calling rand ten times. A
sample run of this program looks like this:
92 Functions and Libraries

As you can see, the value of rand is always positive, and never larger than the
value of RAND_MAX. The values, moreover, appear to jump around unpredictably
within that range, which is exactly what you want from a pseudorandom process.

Given that the C++ libraries include a function for generating pseudorandom
numbers, it is reasonable to ask why one would bother to develop a new interface to
support this process. The answer, in part, is that the rand function itself does not
return a value that clients are likely to use directly. For one thing, the value of
RAND_MAX depends on the hardware and software environment. On most systems,
it is defined to be the largest positive integer, which is typically 2,147,483,647, but
it may have different values on different systems. Moreover, even if you could
count on RAND_MAX having that particular value, there are few (if any) applications
where what you need is a random number between 0 and 2,147,483,647. As a
client, you are much more likely to want values that fall into some other range,
usually much smaller. For example, if you are trying to simulate flipping a coin,
you want a function that has only two outcomes: heads and tails. Similarly, if you
are trying to represent rolling a die, you need to produce a random integer between
1 and 6. If you are trying to simulate processes in the physical world, you will often
need to produce random values over continuous range, where the result needs to be
represented as a double rather than an int. If you could design an interface that
 2.8 Designing a random number library 93

was better suited to the needs of such clients, that interface would be much more
flexible and easy to use.

Another reason to design a higher-level interface is that using the low-level

functions from <cstdlib> introduces several complexitiesas you will discover
when you turn your attention to the implementationthat clients would be happy to
ignore. Part of your job as an interface designer is to hide that complexity from
clients as much as possible. Defining a higher-level random.h interface makes that
possible, because all the complexity can be localized within the implementation.

Choosing the right set of functions

As an interface designer, one of your primary challenges is choosing what functions
to export. Although interface design turns out to be more of an art than a science,
there are some general principles you can apply, including those outlined in
section 2.7. In particular, the functions you export through random.h should be
simple and should hide as much of the underlying complexity as possible. They
should also provide the functionality necessary to meet the needs of a wide range of
clients, which means that you need to have some idea of what operations clients are
likely to need. Understanding those needs depends in part on your own experience,
but often requires interacting with potential clients to get a better sense of their
requirements.

From my own experience with programming, I know that the operations clients
expect from an interface like random.h include the following:

The ability to select a random integer in a specified range. If you want, for
example, to simulate the process of rolling a standard six-sided die, you need to
choose a random integer between 1 and 6.
The ability to choose a random real number in a specified range. If you want to
position an object at a random point in space, you would need to choose random
x and y coordinates within whatever limits are appropriate to the application.
The ability to simulate a random event with a specific probability. If you want
to simulate flipping a coin, you want to generate the value heads with probability
0.5, which corresponds to 50 percent of the time.

Translating these conceptual operations into a set of function prototypes is a

relatively straightforward task. The first three functionsrandomInteger,
randomReal, and randomChancein the random.h interface correspond to these
three operations. The complete interface, which also exports a function called
setRandomSeed that will be described later in the chapter, appears in Figure 2-11.
94 Functions and Libraries

As you can see from either the comments or the prototype in Figure 2-11, the
randomInteger function takes two integer arguments and returns an integer in that
range. If you want to simulate a die roll, you would call

randomInteger(1, 6)

To simulate a spin on a European roulette wheel (American wheels have both a 0

and a 00 slot in addition to the numbers from 1 to 36), you would call

randomInteger(0, 36)

The function randomReal is conceptually similar to randomInteger. It takes

two floating-point values, low and high, and returns a floating-point value r subject
to the condition that low ! r < high. For example, calling randomReal(0, 1)
returns a random number that can be as small as 0 but is always strictly less than 1.
In mathematics, a range of real numbers that can be equal to one endpoint but not
the other is called a half-open interval. On a number line, a half-open interval is
marked using an open circle to show that the endpoint is excluded, like this:

In mathematics, the standard convention is to use square brackets to indicate closed

ends of intervals and parentheses to indicate open ones, so that the notation [0, 1)
indicates the half-open interval corresponding to this diagram.

The function randomChance is used to simulate random events that occur with
some fixed probability. To be consistent with the conventions of statistics, a
probability is represented as a number between 0 and 1, where 0 means that the
event never occurs and 1 means that it always does. Calling randomChance(p)
returns true with probability p. Thus, calling randomChance(0.75) returns
true 75 percent of the time.

You can use randomChance to simulate flipping a coin, as illustrated by the

following function, which returns "heads" or "tails" with equal probability:

string flipCoin() {
if (randomChance(0.50)) {
return "heads";
} else {
return "tails";
}
}
 2.8 Designing a random number library 95

random.h
96 Functions and Libraries

Constructing a client program

One of the best ways to validate the design of an interface is to write applications
that use it. The program in Figure 2-12, for example, uses the randomInteger
function to play the casino game called craps. The rules for craps appear in the
comments at the beginning of the program, although you would probably want the
program to explain the rules to the user as well. In this example, the printed
instructions have been omitted to save space.

Although the Craps.cpp program is nondeterministic and will produce

different outcomes each time, one possible sample run looks like this:

Implementing the random number library

Up to now, this chapter has looked only at the design of the random.h interface.
Before you can actually use that interface in a program, it is necessary to write the
corresponding random.cpp implementation. All you know at this point is that you
have a function rand in the <cstdlib> library that generates a random integer
between 0 and a positive constant called RAND_MAX, which is some point on a
number line that looks like this:

To simulate the die roll, for example, what you need to do is transform that random
integer into one of the following discrete outcomes:

As it happens, there are many bad strategies for performing this transformation.
A surprising number of textbooks, for example, suggest code that looks like this:

int die = rand() % 6 + 1;

 2.8 Designing a random number library 97

craps.cpp
98 Functions and Libraries

This code looks reasonable on the surface. The rand function always returns a
positive integer, so the remainder on division by six must be an integer between
0 and 5. Adding one to that value gives an integer in the desired range of 1 to 6.

The problem here is that rand guarantees only that the value it produces is
uniformly distributed over the range from 0 to RAND_MAX. There is, however, no
guarantee that the remainders on division by six will be at all random. In fact, early
versions of rand distributed with the Unix operating system generated values that
alternated between odd and even values, despite the fact that those values did fall
uniformly over the range. Taking the remainder on division by six would also
alternate between even and odd values, which hardly fits any reasonable definition
of random behavior. If nothing else, it would be impossible to roll doubles on
 2.8 Designing a random number library 99

successive die rolls, given that one die would always be even and the other would
always be odd.

What you want to do instead is divide the integers between 0 and RAND_MAX into
six equal-sized segments that correspond to the different outcomes, as follows:

In the more general case, you need to divide the number line between 0 and
RAND_MAX into k equal intervals, where k is the number of possible outcomes in the
desired range. Once youve done that, all you need to do is map the interval number
into the value the client wants.

The process of transforming the result of the rand function into an integer in a
finite range can be understood most easily if you decompose it into the following
four-step process:

1. Normalize the integer result from rand by converting it into a floating-point

number d in the range 0 ! d < 1.
2. Scale the value d by multiplying it by the size of the desired range, so that it
spans the correct number of integers.
3. Translate the value by adding in the lower bound so that the range begins at the
desired point.
4. Convert the number to an integer by calling the function floor from <cmath>
library, which returns the largest integer that is smaller than its argument.

These phases are illustrated in Figure 2-13, which also traces one possible path
through the process. If the initial call to rand returns 848,256,064 and the value of
RAND_MAX has its most common value of 2,147,483,647, the normalization process
produces a value close to 0.4 (the values in Figure 2-13 have been rounded to a
single digit after the decimal point to make them fit in the diagram). Multiplying
this value by 6 in the scaling step gives 2.4, which is then shifted to 3.4 in the
translation step. In the conversion step, calling floor on 3.4 yields the value 3.

Writing the code to implement this process is not as easy as it might appear,
because there are several pitfalls that can easily trap the insufficiently careful
programmer. Consider, for example, just the normalization step. You cant convert
the result of rand to a floating-point value in the half-open interval [0, 1) by calling

double d = double(rand()) / RAND_MAX;

100 Functions and Libraries

The problem here is that rand might return the value RAND_MAX, which would
mean that the variable d would be assigned the value 1.0, which is specifically
excluded from the half-open interval. Whats worse is that you also cant write

double d = double(rand()) / (RAND_MAX + 1);

although the problem in this case is more subtle. As noted earlier, RAND_MAX is
typically chosen to be the largest positive value of type int. If that is indeed the
case, adding one to it cannot possibly produce a value in the integer range.

To fix these problems, what you need to do instead is perform the addition using
type double instead of int, as follows:

double d = rand() / (double(RAND_MAX) + 1);

A similar problem arises in the scaling step. Mathematically, the number of

integer values in the inclusive range from low to high is given by the expression
high - low + 1. That calculation, however, overflows the range of an integer if
high is a large positive number and low is a negative number with a large absolute
magnitude. Thus, this expression must be evaluated using double precision as well.
 2.8 Designing a random number library 101

Taking these complexities into account, the implementation of randomInteger

looks like this:

int randomInteger(int low, int high) {

double d = rand() / (double(RAND_MAX) + 1);
double s = d * (double(high) - low + 1);
return int(floor(low + s));
}

The implementations of randomReal and randomChance are relatively simple,

given that youve already had to work out the complexities for randomInteger:

double randomReal(double low, double high) {

double d = rand() / (double(RAND_MAX) + 1);
double s = d * (high - low);
return low + s;
}

bool randomChance(double p) {
return randomReal(0, 1) < p;
}

Initializing the random number seed

Unfortunately, the implementations of the randomInteger, randomReal, and
randomChance functions from the preceding section dont quite work in exactly
the way clients would want. The problem is thatfar from producing unpredictable
resultsprograms that use them always produce exactly the same results. If, for
example, you were to run the Craps program twenty times in succession, you
would see exactly the same output each time. So much for randomness.

To figure out why the implementation is behaving in this way, it helps to go

back to the RandTest program and run it again. This time, the output is
102 Functions and Libraries

The output is the same as the first time around. In fact, the RandTest program
produces the same output every time because the designers of the C++ library (and
the earlier C libraries on which these libraries are based) decided that rand should
return the same random sequence each time a program is run.

At first, it may be hard to understand why a function that is supposed to return a

random number would always return the same sequence of values. After all,
deterministic behavior of this sort seems to run counter to the whole idea of
randomness. There is, however, a good reason behind this behavior: programs that
behave deterministically are easier to debug.

To get a sense of why such repeatability is important, suppose you have written a
program to play an intricate game, such as Monopoly. As is always the case with
newly written programs, the odds are good that your program will have a few bugs.
In a complex program, bugs can be relatively obscure, in the sense that they only
occur in rare situations. Suppose you are playing the game and discover that the
program is starting to behave in a bizarre way. As you begin to debug the program,
it would be very convenient if you could regenerate the same state and take a closer
look at what is going on. Unfortunately, if the program is running in a random way,
a second run of the program will behave differently from the first. Bugs that
showed up the first time may not occur on the second pass. The designers of the
original C libraries therefore concluded that it had to be possible to use rand in a
deterministic way in order to support debugging.

At the same time, it also has to be possible to use rand so that it doesnt always
deliver the same results. To understand how to implement this behavior, it helps to
understand how rand works internally. The rand function generates each new
random value by applying a set of mathematical calculations to the last value it
produced. Because you dont know what those calculations are, it is best to think of
the entire operation as a black box where old numbers go in on one side and new
pseudorandom numbers pop out on the other. Since the first call to rand produces
the value 1103527590, the second call to rand corresponds to putting 1103527590
into one end of the black box and having 377401575 pop out on the other side:

On the next call to rand, the implementation puts 377401575 into the black box,
which returns 662824084:

This same process is repeated on each call to rand. The computation inside the
black box is designed so that (1) the numbers are uniformly distributed over the
legal range, and (2) the sequence goes on for a long time before it begins to repeat.
 2.8 Designing a random number library 103

But what about the first call to randthe one that returns 1103527590? The
implementation must have a starting point. There must be an integer s0 that goes
into the black box and produces 1103527590:

This initial valuethe value that is used to get the entire process startedis called
the seed for the random number generator. In the <cstdlib> library, you can set
that seed explicitly by calling srand(seed).

As you know from the multiple runs of the RandTest program, the C++ library
sets the initial seed to a constant value every time a program is started, which is why
rand always generates the same sequence of values. That behavior, however,
makes sense only during the debugging phase. Most modern languages change the
default behavior so that the functions in the random-number library return different
results on each run unless the programmer specifies otherwise. That design is
considerably simpler for clients, and it makes sense to incorporate that design
change into the random.h interface. It is still necessary to allow clients to generate
a repeatable sequence of values, because doing so simplifies the debugging process.
The need to provide that option is the reason for the inclusion in the interface of the
setRandomSeed function. During the debugging phase, you can add the line

setRandomSeed(1);

at the beginning of the main program. The calls to the other entries exported by the
random.h interface will then produce the repeatable sequence of values generated
by using 1 as the initial seed. When you are convinced that the program is working,
you can remove this line to restore unpredictable behavior.

To implement this change, the functions randomInteger, randomReal, and

randomChance must first check to see whether the random number seed has
already been initialized and, if not, set it to some starting value that would be
difficult for users to predict, which is usually taken from the value of the system
clock. Because that value is different each time you run a program, the random
number sequence changes as well. In C++, you can retrieve the current value of the
system clock by calling the function time and then converting the result to an
integer. This technique allows you to write the following statement, which has the
effect of initializing the pseudorandom number generator to an unpredictable point:

srand(int(time(NULL)));

Although it requires only a single line, the operation to set the random seed to an
unpredictable value based on the system clock is quite obscure. If this line were to
appear in the client program, the client would have to understand the concept of a
104 Functions and Libraries

random number seed, along with the functions srand and time and the constant
NULL (which you wont learn about until Chapter 11). To make things as easy as
possible for the client, you need to hide this complexity away.

The situation becomes even more complicated, however, when you realize that
this initialization step must be performed onceand only oncebefore delivering
up the results of any of the other functions. To ensure that the initialization code
doesnt get executed every time, you need a Boolean flag to record whether that
initialization has been performed. Unfortunately, it doesnt work to declare that flag
as a global variable because C++ does not specify the order in which global
variables are initialized. If you declare other global values whose initial values
were produced by the random-library library, there would be no way to ensure that
the initialization flag had been set correctly.

In C++, the best strategy is to declare the initialization flag inside the context of
the function that checks to see whether the necessary initialization has already been
performed. That variable, however, cant be declared as a traditional local variable,
because doing so would mean that a new variable was created on every call. To
make this strategy work, you need to mark the flag as static, as shown in the
following implementation:

void initRandomSeed() {
static bool initialized = false;
if (!initialized) {
srand(int(time(NULL)));
initialized = true;
}
}

When it is marked with the keyword static, the variable initialized becomes
a static local variable. Like any local variable, a static local variable is accessible
only within the body of the function; the difference with a static local variable is
that the compiler allocates only one copy of that variable, which is then shared by
all calls to initRandomSeed. The rules of C++ ensure that static local variables
are initialized exactly once and, moreover, that the initialization occurs before the
function containing them is called. Defining initRandomSeed represents the final
step in coding the random.cpp implementation, which appears in Figure 2-14.

My goal in going through the code for the random.cpp implementation is not
for you to master all of its intricacies. What I hope to do instead is convince you
why it is important for you as a client of random.h not to have to understand all
those details. The code in random.cpp is subtle and contains many potential
pitfalls that are likely to ensnare the casual programmer who tries to implement
these functions from scratch. The primary purpose of library interfaces is to hide
precisely this sort of complexity.
 2.8 Designing a random number library 105

Figure 2-8
106 Functions and Libraries

Figure 2-8
 2.9 Introduction to the Stanford libraries 107

2.9 Introduction to the Stanford libraries

Up to this point, the programs in this book use only standard features of C++. For
that reason, these programs should work with any C++ compiler on any type of
hardware. The standard libraries, however, do not include all the features that you
would want as a programmer. Even though almost all modern applications use
graphical displays, the standard libraries offer no graphical capabilities. Every
modern operating system provides libraries that support drawing pictures on the
screen, but those libraries are different for each machine. In order to create
applications that are as interesting as those you are used to using, you will need to
use nonstandard libraries somewhere along the way.

As part of the supporting material for this textbook, Stanford University provides
a set of libraries that make learning to program in C++ both easier and more
enjoyable. For example, those libraries include a graphics package that works the
same way on the most common computing platforms. The Stanford libraries also
provide a home for the libraries developed in this chapter. After going to all the
trouble of defining and implementing interfaces like error.h, direction.h,
gmath.h, and random.h, it doesnt make sense to abandon those tools or even to
force potential clients to copy the associated code. Every one of those interfaces
will come in handy for certain applications, and it makes sense to include those
interfaces as part of a library. Creating a compiled library, however, is beyond the
scope of this text, mostly because the details for doing so differ from machine to
machine. The Stanford web site for this book includes a precompiled version of
these libraries for all the major platforms that students are likely to use. You can
download those libraries from the web site along with the .h files that define the
library interfaces. It might take a little time to figure out how to use the Stanford
libraries in the programming environment youre using, but that effort will quickly
repay itself many times over.

A library to simplify input and output

In addition to the library interfaces introduced in this chapter, the Stanford libraries
include several other interfaces that will make programming somewhat easier. Of
these, the most important is the simpio.h interface, which simplifies the process of
getting input from the user. Instead of the lines

int limit;
cout << "Enter exponent limit: ";
cin >> limit;

using simpio.h allows you to collapse this set of operations into a single line:

int limit = getInteger("Enter exponent limit: ");

108 Functions and Libraries

Although the code for the simpio.h strategy is considerably shorter, the real
advantage is that the getInteger function checks the users input for errors.
Suppose, for example, that your program is in the process of executing the line

int n = getInteger("Enter an integer: ");

The implementation of getInteger displays the prompt string and waits for user
input, like this:

If the user intends to type 120 but mistakenly types a minus sign in place of the
zero, getInteger will notice that the input is not a legal integer and give the user
another chance to enter the correct value, as shown in the following sample run:

The >> operator, by contrast, does not check for this type of error. If the user enters
12- in response to the statement

cin >> n;

the variable n would get the value 12, leaving the minus sign in the input stream.

In addition to getInteger, the simpio.h also exports a getReal function for

reading a floating-point value and a getLine function for reading an entire line as a
string. You will learn how to implement these functions in Chapter 4, but you can
use them now to get in the habit.

The Stanford libraries also include a console library, which creates a console
window on the screen as soon as your program starts up. Having this window
appear automatically solves the problem that Dennis Ritchie identified in The C
Programming Language when he wrote that one of the harder challenges in running
a program is to find out where the output went. To use this library, all you have
to do is add the line

#include "console.h"

at the beginning of your program. If this line appears, the program creates the
console. If its missing, the program works the way it always did.
 2.9 Introduction to the Stanford libraries 109

Graphical programs in the Stanford libraries

One of the challenges of using C++ as a teaching language is that C++ doesnt offer
a standard graphics library. Although it is perfectly possible to learn about data
structures and algorithms without using graphics, having a graphics library makes
the process a lot more fun. And because youre likely to learn things more easily if
you can have a little fun along the way, the Stanford libraries include a library
package that supports simple two-dimensional graphics on most common platforms.

The primary interface to the graphics library is gwindow.h, which exports a

class called GWindow that represents a graphics window. To draw graphics on the
screen, you need to declare GWindow object and then invoke methods on that object.
Although the GWindow class exports a much larger set of methods, the programs in
this book use only the methods shown in Table 2-2. Almost every graphics package
supports methods that look very similar to the ones in this table, and it should be
easy to adapt the examples in this text to work with other graphics libraries.

Figure 2-15 shows a simple graphics application, which is designed to illustrate

the methods in Table 2-2 rather than to draw anything useful. The output of the
program appears in Figure 2-16 at the top of page 111.
110 Functions and Libraries

GraphicsExample.cpp
 2.9 Introduction to the Stanford libraries 111

The first line in the GraphicsExample program declares a GWindow object,

which implements the graphical operations. The simplest form of the declaration is

GWindow gw;

which creates a small graphics window and displays it on the screen. You can,
however, specify the window size by invoking an alternate form of the constructor:

GWindow gw(width, height);

The parameters width and height are measured in units called pixels, which are the
individual dots that cover the surface of the display screen.

All graphical operations are implemented as methods applied to the GWindow

stored in the variable gw. For that reason, any piece of code that uses graphics must
have access to that object. If you decompose your program into several functions,
you will typically need to pass the value of gw as a reference parameter to any
function that needs access to the graphical capabilities of the window.

Coordinates in the graphics window are represented using a pair of values (x, y)
where the x and y values represent the distance in that dimension from the origin,
which is the point (0, 0) in the upper left corner of the window. As in traditional
Cartesian coordinates, the value for x increases as you move rightward across the
window. Having the location of the origin in the upper left corner, however, means
that the y value increases as you move downward, which is precisely opposite to the
112 Functions and Libraries

usual Cartesian plane. Computer-based graphics packages invert the y coordinate

because text moves downward on the page. By having y values increase as you
move downward, successive lines of text appear at increasing values of y.

Summary
In this chapter, you learned about functions, which enable you to refer to an entire
set of operations by using a simple name. By allowing the programmer to ignore
the internal details and concentrate only on the effect of a function as a whole,
functions are an essential tool for reducing the conceptual complexity of programs.

The important points introduced in this chapter include:

A function is a block of code that has been organized into a separate unit and
given a name. Other parts of the program can then call that function, possibly
passing it information in the form of arguments and receiving a result returned
by that function.
Functions serve several useful purposes in programming. Allowing the same set
of instructions to be shared by many parts of a program reduces both its size and
its complexity. More importantly, functions make it possible to decompose large
programs into smaller, more manageable pieces. Functions also serve as the
basis for implementing algorithms, which are precisely specified strategies for
solving computational problems.
Functions become even more useful when they are collected into a library,
which can then be shared by many different applications. Each library typically
defines several functions that share a single conceptual framework. In computer
science, the process of making a function available through a library is called
exporting that function.
The <cmath> library exports several functions that are likely to be familiar from
mathematics, including functions like sqrt, sin, and cos. As a client of the
<cmath> library, you need to know how to call these functions, but do not need
to know the details of how they work.
In C++, functions must be declared before they are used. A function declaration
is called a prototype. In addition to the prototype, functions have an
implementation, which specifies the individual steps that function contains.
A function that returns a value must have a return statement that specifies the
result. Functions may return values of any type. Functions that return Boolean
values are called predicate functions and play an important role in programming.
A function that returns no result and is executed only for its effect is called a
procedure.
 Summary 113

C++ allows you to define several functions with the same name as long as the
compiler can use the number and types of the arguments to determine which
function is required. This process is called overloading. The argument pattern
that distinguishes each of the overloaded variants is called a signature. C++ also
makes it possible to specify default parameters, which are used if the client
omits them from the call.
Variables declared with a function are local to that function and cannot be used
outside of it. Internally, all the variables declared within a function are stored
together in a stack frame.
When you call a function, the arguments are evaluated in the context of the caller
and then copied into the parameter variables specified in the function prototype.
The association of arguments and parameters always follows the order in which
the variables appear in each of the lists.
C++ makes it possible for a function and its caller to share the value of a
parameter variable by marking it with the ampersand character (&). This style of
parameter transmission is referred to as call by reference.
When a function returns, it continues from precisely the point at which the call
was made. The computer refers to this point as the return address and keeps
track of it in the stack frame.
Programmers who create a library are its implementers; programmers who make
use of one are called its clients. The connection between the implementer and
the client is called an interface. Interfaces typically export functions, types, and
constants, which are collectively known as interface entries.
In C++, interfaces are stored in header files, which typically end with a .h
suffix. Every interface should include several lines of interface boilerplate to
ensure that the compiler reads it only once.
When you design an interface, you must balance several criteria. Well-designed
interfaces are unified, simple, sufficient, general, and stable.
The random.h interface exports several functions that make it easy to simulate
random behavior.
The interfaces defined in this chaptererror.h, direction.h, gmath.h, and
random.hare exported as part of a Stanford library package so that clients can
use them without having to rewrite the necessary code. The Stanford library also
defines several other useful interfaces, including a simplified input/output library
(simpio.h), a library to produce an interactive console (console.h), and a
library to display graphical windows on the screen (gwindow.h).
114 Functions and Libraries

Review questions
1. Explain in your own words the difference between a function and a program.

2. Define the following terms as they apply to functions: call, argument, return.

3. True or false: Every function in a C++ program requires a prototype.

4. What is the prototype of the function sqrt in the <cmath> library?

5. Can there be more than one return statement in the body of a function?

6. What is a predicate function?

7. What is meant by the term overloading? How does the C++ compiler use
signatures to implement overloading?

8. How do you specify a default value for a parameter?

9. True or false: It is possible to specify a default value for the first parameter to a
function without specifying a default value for the second.

10. What is a stack frame?

11. Describe the process by which arguments are associated with parameters.

12. Variables declared within a function are said to be local variables. What is the
significance of the word local in this context?

13. What does the term call by reference mean?

14. How do you indicate call by reference in a C++ program?

15. Define the following terms in the context of libraries: client, implementation,
interface.

16. If you were writing an interface called mylib.h, what lines would you include
as the interface boilerplate?

17. Describe the process used to export a constant definition as part of an interface.

18. What criteria does this chapter list as important in the process of interface
design?
 Review questions 115

19. Why is it important for an interface to be stable?

20. What is meant by the term pseudorandom number?

21. On most computers, how is the value of RAND_MAX chosen?

22. What four steps are necessary to convert the result of rand into an integer
value with a different range?

23. How would you use the randomInteger function to generate a pseudorandom
number between 1 and 100?

24. By executing each of the statements in the implementation by hand, determine

whether the randomInteger function works with negative arguments. What
are the possible results of calling the function randomInteger(-5, 5)?

25. Assuming that d1 and d2 have already been declared as variables of type int,
could you use the multiple assignment statement

d1 = d2 = RandomInteger(1, 6);

to simulate the process of rolling two dice?

26. True or false: The rand function ordinarily generates the same sequence of
random numbers every time a program is run.

27. What is meant by the term seed in the context of random numbers?

28. What suggestion does this chapter offer for debugging a program involving
random numbers?

29. What functions are defined in the final version of the random.h interface? In
what context would you use each function?

Exercises
1. If you did not do so the first time around, rewrite the Celsius-to-Fahrenheit
program from exercise 1 in Chapter 1 so that it uses a function to perform the
conversion.

2. Reimplement the distance-conversion program from exercise 2 in Chapter 1 so

that it uses a function. In this case, the function must produce both the number
of feet and the number of inches, which means that you need to use call by
reference to return these values.
116 Functions and Libraries

3. When a floating-point number is converted to an integer in C++, the value is

truncated by throwing away any fraction. Thus, when 4.99999 is converted to
an integer, the result is 4. In many cases, it would be useful to have the option
of rounding a floating-point value to the nearest integer. Given a positive
floating-point number x, you can round it to the closest integer by adding 0.5
and then truncating the result to an integer. Because truncation always moves
toward zero, rounding negative numbers requires you to subtract 0.5, rather
than adding it.

Write a function roundToNearestInt(x) that rounds the floating-point

number x to the nearest integer. Show that your function works by writing a
suitable main program to test it.

4. If you are unfortunate enough to be outside in winter weather, you know that
your perception of the cold is dependent on the wind speed as well as the
temperature. The faster the wind blows, the colder you feel. To quantify the
how wind affects temperature perception, the National Weather Service reports
the wind chill, which is illustrated on their website as shown in Figure 2-17.
 Exercises 117

As you can see at the bottom of Figure 2-17, the National Weather Service
calculates wind chill using the formula

35.74 + 0.6215 t 35.75 v 0.16 + 0.4275 t v 0.16

where t is the Fahrenheit temperature and v is the wind speed in miles per hour.

Write a function windChill that takes the values of t and v and returns the
wind chill. In doing so, your function should take account of two special cases:

If there is no wind, windChill should return the original temperature t.

If the temperature is greater than 40 F, the wind chill is undefined, and
your function should call error with an appropriate message.

Although it will be easier to do so once you learn how to format numeric

data in Chapter 4, you already know enough to generate a table that presents the
wind-chill data in columns as shown in Figure 2-17. If youre up for more of a
challenge, write a main program that uses windChill to produce that table.

5. Greek mathematicians took a special interest in numbers that are equal to the
sum of their proper divisors (a proper divisor of n is any divisor less than n
itself). They called such numbers perfect numbers. For example, 6 is a perfect
number because it is the sum of 1, 2, and 3, which are the integers less than 6
that divide evenly into 6. Similarly, 28 is a perfect number because it is the
sum of 1, 2, 4, 7, and 14.

Write a predicate function isPerfect that takes an integer n and returns

true if n is perfect, and false otherwise. Test your implementation by
writing a main program that uses the isPerfect function to check for perfect
numbers in the range 1 to 9999 by testing each number in turn. When a perfect
number is found, your program should display it on the screen. The first two
lines of output should be 6 and 28. Your program should find two other perfect
numbers in the range as well.

6. An integer greater than 1 is said to be prime if it has no divisors other than

itself and one. The number 17, for example, is prime, because there are no
numbers other than 1 and 17 that divide evenly into it. The number 91,
however, is not prime because it is divisible by 7 and 13. Write a predicate
method isPrime(n) that returns true if the integer n is prime, and false
otherwise. To test your algorithm, write a main program that lists the prime
numbers between 1 and 100.

7. Even though clients of the <cmath> library typically dont need to understand
how functions like sqrt work internally, the implementers of that library have
118 Functions and Libraries

to be able to design an effective algorithm and write the necessary code. If you
were asked to implement the sqrt function without using the library version,
there are many strategies you could adopt. One of the easiest strategies to
understand is successive approximation in which you make a guess at the
solution and then refine that guess by choosing new values that move closer to
the solution.

You can use successive approximation to determine the square root of x by

adopting the following strategy:

1. Begin by guessing that the square root is x / 2. Call that guess g.

2. The actual square root must lie between g and x / g. At each step in the
successive approximation, generate a new guess by averaging g and x / g.
3. Repeat step 2 until the values g and x / g are as close together as the
machine precision allows. In C++, the best way to check for this condition
is to test whether the average is equal to either of the values used to
generate it.

Use this strategy to write your own implementation of the sqrt function.

8. Although Euclids algorithm for calculating the greatest common divisor is one
of the oldest to be dignified with that term, there are other algorithms that date
back many centuries. In the Middle Ages, one of the problems that required
sophisticated algorithmic thinking was determining the date of Easter, which
falls on the first Sunday after the first full moon following the vernal equinox.
Given this definition, the calculation involves interacting cycles of the day of
the week, the orbit of the moon, and the passage of the sun through the zodiac.
Early algorithms for solving this problem date back to the third century and are
described in the writings of the eighth-century scholar known as the Venerable
Bede. In 1800, the German mathematician Carl Friedrich Gauss published an
algorithm for determining the date of Easter that was purely computational in
the sense that it relied on arithmetic rather than looking up values in tables. His
algorithmtranslated directly from the Germanappears in Figure 2-18.
Write a procedure
void findEaster(int year, string & month, int & day);

that returns the Easter date for year in the reference parameters month and day.

Unfortunately, the algorithm in Figure 2-18 only works for years in the 18th
and 19th centuries. It is easy, however, to search the web for extensions that
work for all years. Once you have completed your implementation of Gausss
algorithm, undertake the necessary research to find a more general approach.
 Exercises 119

9. The combinations function C(n, k) described in this chapter determines the

number of ways you can choose k values from a set of n elements, ignoring the
order of the elements. If the order of the value mattersso that, in the case of
the coin example, choosing a quarter first and then a dime is seen as distinct
from choosing a dime and then a quarteryou need to use a different function,
which computes the number of permutations. This function is denoted as
P(n, k), and has the following mathematical formulation:

P(n, k) =

Although this definition is mathematically correct, it is not well suited to

implementation in practice because the factorials involved can get much too
large to store in an integer variable, even when the answer is small. For
example, if you tried to use this formula to calculate the number of ways to
select two cards from a standard 52-card deck, you would end up trying to
evaluate the following fraction:

even though the answer is the much more manageable 2652 (52 ! 51).

Write a function permutations(n, k) that computes the P(n, k) function

without calling the fact function. Part of your job in this problem is to figure
out how to compute this value efficiently. To do so, you will probably find it
useful to play around with some relatively small values to get a sense of how
the factorials in the numerator and denominator of the formula behave.
120 Functions and Libraries

10. The C(n, k) function from the text and the P(n, k) function from the preceding
exercise come up often in computational mathematics, particularly in an area
called combinatorics, which is concerned with counting the ways objects can
be combined. Now that you have C++ implementations for each of these
functions, it might be worth putting them in a library so that you can use them
in many different applications.

Write the files combinatorics.h and combinatorics.cpp for a library

that exports the functions permutations and combinations. When you
write the implementation, make sure to rewrite the code for the combinations
function so that it uses the efficiency enhancements suggested for permutations
in exercise 9.

11. Using the direction.h interface as an example, design and implement a

calendar.h interface that exports the Month type from Chapter 1, along with
the functions daysInMonth and isLeapYear, which also appear in that
chapter. Your interface should also export a monthToString function that
returns the constant name for a value of type Month. Test your implementation
by writing a main program that asks the user to enter a year and then writes out
the number of days in each month of that year, as in the following sample run:

12. Write a program RandomAverage that repeatedly generates a random real

number between 0 and 1 and then displays the average after a specified number
of trials entered by the user.

13. I shall never believe that God plays dice with the world.
Albert Einstein, 1947

Despite Einsteins metaphysical objections, the current models of physics, and

particularly of quantum theory, are based on the idea that nature does indeed
involve random processes. A radioactive atom, for example, does not decay for
any specific reason that we mortals understand. Instead, that atom has a
 Exercises 121

random probability of decaying within a period of time. Sometimes it does,

sometimes it doesnt, and there is no way to know for sure.

Because physicists consider radioactive decay a random process, it is not

surprising that random numbers can be used to simulate it. Suppose you start
with a collection of atoms, each of which has a certain probability of decaying
in any unit of time. You can then approximate the decay process by taking
each atom in turn and deciding randomly whether it decays, considering the
probability.

Write a program that simulates the decay of a sample that contains 10,000
atoms of radioactive material, where each atom has a 50 percent chance of
decaying in a year. The output of your program should show the number of
atoms remaining at the end of each year, which might look something like this:

As the numbers indicate, roughly half the atoms in the sample decay each
year. In physics, the conventional way to express this observation is to say that
the sample has a half-life of one year.

14. Random numbers offer yet another strategy for approximating the value of !.
Imagine that you have a dartboard hanging on your wall that consists of a circle
painted on a square backdrop, as in the following diagram:
122 Functions and Libraries

What happens if you throw a whole bunch of darts completely randomly,

ignoring any darts that miss the board altogether? Some of the darts will fall
inside the gray circle, but some will be outside the circle in the white corners of
the square. If the darts are random, the ratio of the number of darts landing
inside the circle to the total number of darts hitting the square should be
approximately equal to the ratio between the two areas. The ratio of the areas
is independent of the actual size of the dartboard, as illustrated by the formula

! = =

To simulate this process in a program, imagine that the dart board is drawn
on the standard Cartesian coordinate plane with its center at the origin and a
radius of 1 unit. The process of throwing a dart randomly at the square can be
modeled by generating two random numbers, x and y, each of which lies
between 1 and +1. This (x, y) point always lies somewhere inside the square.
The point (x, y) lies inside the circle if

< 1

This condition, however, can be simplified considerably by squaring each side

of the inequality, which gives the following more efficient test:

x2 + y2 < 1

If you perform this simulation many times and compute the fraction of darts
that fall within the circle, the result will be an approximation of "/4.

Write a program that simulates throwing 10,000 darts and then uses the
simulation technique described in this exercise to generate and display an
approximate value of ". Dont worry if your answer is correct only in the first
few digits. The strategy used in this problem is not particularly accurate, even
though it occasionally proves useful as an approximation technique. In
mathematics, this technique is called Monte Carlo integration, after the capital
city of Monaco.

15. Heads. . . .
Heads. . . .
Heads. . . .
A weaker man might be moved to re-examine his faith, if in
nothing else at least in the law of probability.
Tom Stoppard, Rosencrantz and Guildenstern Are Dead, 1967

Write a program that simulates flipping a coin repeatedly and continues until
three consecutive heads are tossed. At that point, your program should display
 Exercises 123

the total number of coin flips that were made. The following is one possible
sample run of the program:

16. Use the graphics library to draw a rainbow that looks something like this:

Starting at the top, the six stripes in the rainbow are red, orange, yellow, green,
blue, and magenta, respectively; cyan makes a lovely color for the sky.

17. Use the graphics library to write a program that draws a checkerboard on the
graphics window. Your picture should include the red and black pieces, as they
exist at the beginning of the game, like this:
124 Functions and Libraries

18. One of the principles that defines Taoist philosophy is that dichotomies do not
have sharp boundaries, and that there is mixing even between categories that
most people see as opposites. This idea is captured in the Yin-Yang symbol, in
which each region contains a bit of the other color:

Write a graphics program to draw this symbol at the center of an empty

graphics window. The challenge here is to decompose the drawing in such a
way that you can create it using only the methods in Table 2-2, which do not
include facilities for drawing and filling arcs and semicircles.
Chapter 3
Strings

Whisper music on those strings.

T. S. Eliot, The Waste Land, 1922
126 Strings

Up to now, most of the programming examples you have seen in this book have
used numbers as their basic data type. These days, computers work less with
numeric data than with text data, which is a generic term for information composed
of individual characters. The ability of modern computers to process text data has
led to the development of text messaging, electronic mail, word processing systems,
online reference libraries, and a wide variety of other useful applications.

This chapter introduces the C++ <string> library, which provides a convenient
abstraction for working with strings of characters. Having this library in your
toolbox will make it much easier to write interesting applications. This chapter,
however, also introduces the notion of a class, which is the term computer scientists
have adopted for data types that support the object-oriented programming paradigm.
Although C++ also defines a more primitive string type, most text-processing
applications work instead with objects of a class called string. By working with
the string class in this chapter, you will have a better sense of what classes are
when you begin to define your own classes in Chapter 6.

3.1 Using strings as abstract values

Conceptually, a string is simply a sequence of characters. For example, the string
"hello, world" is a sequence of 12 characters including ten letters, a comma, and
a space. In C++, the string class and its associated operations are defined in the
<string> library, and you must therefore include this library in any source file that
manipulates string data.

In Chapter 1, you learned that data types are defined by two properties: a domain
and a set of operations. For strings, the domain is easy to identify: the domain of
type string is the set of all sequences of characters. The more interesting problem
is to identify the appropriate set of operations. Early versions of C++ followed the
lead of the older C language and offered little support for manipulating strings. The
only facilities were low-level operations that required you to understand the
underlying representation. The designers of C++ soon solved that problem by
introducing a string class that enables clients to work at a more abstract level.

For the most part, you can use string as a primitive data type in much the same
way that you use types like int and double. You can, for example, declare a
variable of type string and assign it an initial value, much as you would with a
numeric variable. When you declare a string variable, you typically specify its
initial value as a string literal, which is a sequence of characters enclosed in double
quotes. For example, the declaration

const string ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

sets the constant ALPHABET to a 26-character string containing the uppercase letters.
 3.1 Using strings as abstract values 127

You can also use the operators >> and << to read and write data values of type
string, although doing so requires some caution. For example, you could make
the Hello program more conversational by rewriting the main function like this:

int main() {
string name;
cout << "Enter your name: ";
cin >> name;
cout << "Hello, " << name << "!" << endl;
return 0;
}

This program reads a string from the user into the variable name and then includes
that name as part of the greeting, as shown in the following sample run:

This program, however, behaves in a somewhat surprising way if you enter a

users full name instead of the first name alone. For example, if I had typed my full
name in response to the prompt, the sample run would look like this:

Even though the program contains no code to take the two pieces of my name apart,
it somehow still uses only my first name when it prints its greeting. How does the
program know to be so colloquial?

Answering this question requires you to understand in more detail how the >>
operator behaves when you use it to read a string value. Although you might expect
it to read an entire line of input, the >> operator stops as soon as it hits the first
whitespace character, which is defined to be any character that appears as blank
space on the display screen. The most common whitespace character is the space
character itself, but the set of whitespace characters also includes tabs and the
characters that mark the end of a line.
128 Strings

If you want to read a string that contains whitespace characters, you cant use the
>> operator. The standard approach is to call the function

getline(cin, str);

which reads an entire line from the console input stream cin into the variable str,
which is passed by reference. Incorporating getline into the HelloName program
gives rise to the code shown in Figure 3-1 and enables the program to display the
full name of the user, as follows:

In practice, reading a complete line is a much more common operation than

reading a substring bounded by whitespace characters. As a result, programs that
need to read a string from the user are far more likely to use the getline function
(or the getLine function from simpio.h introduced in section 2-9) than the >>
operator.
 3.2 String operations 129

3.2 String operations

If you need to perform more complex operations using the <string> library, you
will discover that the data type string doesnt behave in precisely the same way
that more traditional types do. One of the major differences is in the syntax used to
invoke function calls. For example, if you were assured that the <string> library
exports a function named length, you might imagine that the way to determine the
length of a string str would be to use a statement like this:

int nChars = length(str);

As the bug icon emphasizes, this statement is incorrect in C++. The problem with
this expression is that the data type string is not a traditional type but is instead an
example of a class, which is probably easiest to define informally as a template that
describes a set of values together with an associated set of operations. In the
language of object-oriented programming, the values that belong to a class are
called objects. A single class can give rise to many different objects; each such
object is said to be an instance of that class.

The operations that apply to instances of a class are called methods. In C++,
methods look and behave much like traditional functions, although it helps to give
them a new name to emphasize that there are differences. Unlike functions,
methods are tightly coupled to the class to which they belong. In cases where it is
useful to emphasize the distinction, traditional functions are sometimes called
free functions because they are not bound to a particular class.

In the object-oriented world, objects communicate by sending information and

requests from one object to another. Collectively, these transmissions are called
messages. The act of sending a message corresponds to having one object invoke a
method that belongs to a different object. For consistency with the conceptual
model of sending messages, the object that initiates the method is called the sender,
and the object that is the target of that transmission is called the receiver. In C++,
sending a message is specified using the following syntax:

receiver.name(arguments)

The object-oriented version of the statement that sets nChars to the length of the
string object str is therefore

int nChars = str.length();

Table 3-1 lists the most common methods exported by the <string> library, all of
which use the receiver syntax.
130 Strings

<string> methods
 3.2 String operations 131

Operator overloading
As you can see from the first section of Table 3-1, the <string> library redefines
several of the standard operators using an extremely powerful C++ feature called
operator overloading, which redefines the behavior of operators depending on the
types of their operands. In the <string> library, the most important overloaded
operator is the + sign. When + is applied to numbers, it performs addition. When +
is applied to strings, it performs concatenation, which is just a fancy word for
joining the two strings together end to end.

You can also use the shorthand += form to concatenate new text to the end of an
existing string. Both the + and += operators allow concatenation of strings or single
characters, as illustrated by the following example, which sets the string variable
str to the string "abcd":

string str = "abc";

str += 'd';

Those of you who are familiar with Java may expect the + operator to support
values of other types by converting those values to strings and then concatenating
them together. That feature is not available in C++, which treats any attempt to use
the + operator with incompatible operands as an error.

C++ also overloads the relational operators so that you can compare string
values much more conveniently than you can in many other languages, including C
and Java. For example, you can check to see whether the value of str is equal to
"quit" like this:

if (str == "quit") . . .

The relational operators compare strings using lexicographic order, which is the
order defined by the underlying ASCII codes. Lexicographic order means that case
is significant, so "abc" is not equal to "ABC".

Selecting characters from a string

In C++, positions within a string are numbered starting from 0. For example, the
characters in the string "hello, world" are numbered as in the following diagram:

The position number written underneath each character is called its index.

The <string> library offers two different mechanisms for selecting individual
characters from a string. One approach is to supply the index inside square brackets
132 Strings

after the string. For example, if the string variable str contains "hello, world",
the expression

str[0]

selects the character 'h' at the beginning of the string. Although C++ programmers
tend to use the square-bracket syntax for its expressiveness, it is arguably better to
call the at method instead. The expressions str[i] and str.at(i) have almost
the same meaning in C++; the only difference is that at checks to make sure the
index is in range.

No matter which syntax you use, selecting an individual character in a string

returns a direct reference to the character in the string, which allows you to assign a
new value to that character. For example, you can use either the statement

str[0] = 'H';

or the statement

str.at(0) = 'H';

to change the value of the string from "hello, world" to "Hello, world".
Partly because the second form generates confusion by suggesting that it is possible
to assign a value to the result of any function and partly because experience has
shown that students have more trouble understanding examples written using at, I
have chosen to use bracket selection for the programming examples in this book,
despite the lack of range-checking.

Although index positions in strings are conceptually integers, the string class
complicates matters by using the type size_t to represent both index positions and
lengths in a string. If you want to be slavishly correct in your coding, you should
use that type (which is automatically defined when you include the <string>
header file) every time you store a string index in a variable. At Stanford, we have
found that the additional conceptual complexity of using size_t gets in the way of
student understanding and have chosen to use int for this purpose. Using int
works just fine unless your strings are longer than 2,147,483,647 characters long,
although you may get a warning message from some compilers.

String assignment
C++ does take some steps to mitigate the conceptual problems that follow from
allowing the client to change individual characters in an existing string. In
particular, C++ redefines assignment for strings so that assigning one string to
another copies the underlying characters. For example, the assignment statement
 3.2 String operations 133

str2 = str1;

overwrites any previous contents of str2 with a copy of the characters contained in
str1. The variables str1 and str2 therefore remain independent, which means
that changing the characters in str1 does not affect str2. Similarly, C++ copies
the characters in any string passed as a value parameter. Thus, if a function makes
changes to an argument that happens to be a string, those changes are not reflected
in the calling function unless the string parameter is passed by reference.

Extracting parts of a string

Concatenation makes longer strings from shorter pieces. You often need to do the
reverse: separate a string into the shorter pieces it contains. A string that is part of a
longer string is called a substring. The string class exports a method called
substr that takes two parameters: the index of the first character you want to select
and the desired number of characters. Calling str.substr(start, n) creates a
new string by extracting n characters from str starting at the index position
specified by start. For example, if str contains the string "hello, world", the
method call

str.substr(1, 3)

returns the three-character substring "ell". Because indices in C++ begin at 0, the
character at index position 1 is the character 'e'.

The second argument in the substr method is optional. If it is missing, substr

returns the substring that starts at the specified position and continues through the
end of the string. Thus, calling

str.substr(7)

returns the string "world". Similarly, if n is supplied but fewer than n characters
follow the specified starting position, substr returns characters only up to the end
of the original string.

The following function uses substr to return the second half of the parameter
str, which is defined to include the middle character if the length of str is odd:

string secondHalf(string str) {

return str.substr(str.length() / 2);
}

Searching within a string

From time to time, you will find it useful to search a string to see whether it
contains a particular character or substring. To make such search operations
134 Strings

possible, the string class exports a method called find, which comes in several
forms. The simplest form of the call is

str.find(search);

where search is the content youre looking for, which can be either a string or a
character. When called, the find method searches through str looking for the first
occurrence of the search value. If the search value is found, find returns the index
position at which the match begins. If the character does not appear before the end
of the string, find returns the constant string::npos. Unlike the constants that
you saw in Chapter 1, the identifier npos is defined as part of the string class and
therefore requires the string:: qualifier whenever it appears.

The find method also takes an optional second argument that indicates the
index position at which to start the search. The effect of both styles of the find
method is illustrated by the following examples, which assume that the variable str
contains the string "hello, world":

str.find('o') ! 4
str.find('o', 5) ! 8
str.find('x') ! str::npos

As with string comparison, the methods for searching a string consider uppercase
and lowercase characters to be different.

Iterating through the characters in a string

Even though the methods exported by the string class give you the tools you need
to implement string applications from scratch, it is usually easier to write programs
by adapting existing code examples that implement particularly common operations.
In programming terminology, such illustrative examples are called patterns. When
you work with strings, one of the most important patterns involves iterating through
the characters in a string, which requires the following code:

for (int i = 0; i < str.length(); i++) {

. . . body of loop that manipulates str[i] . . .
}

On each loop cycle, the selection expression str[i] refers to the ith character in
the string. Because the purpose of the loop is to process every character, the loop
continues until i reaches the length of the string. Thus, you can count the number
of spaces in a string using the following function:
 3.2 String operations 135

int countSpaces(string str) {

int nSpaces = 0;
for (int i = 0; i < str.length(); i++) {
if (str[i] == ' ') nSpaces++;
}
return nSpaces;
}

For some applications, you will find it useful to iterate through a string in the
opposite direction, starting with the last character and continuing backward until
you reach the first. This style of iteration uses the following for loop:

for (int i = str.length() - 1; i >= 0; i--)

Here, the index i begins at the last index position, which is one less than the length
of the string, and then decreases by one on each cycle, down to and including the
index position 0.

Assuming that you understand the syntax and semantics of the for statement,
you could work out the patterns for each iteration direction from first principles
each time this pattern comes up in an application. Doing so, however, will slow you
down enormously. These iteration patterns are worth memorizing so that you dont
have to waste any time thinking about them. Whenever you recognize that you
need to cycle through the characters in a string, some part of your nervous system
between your brain and your fingers should be able to translate that idea effortlessly
into the following line:

for (int i = 0; i < str.length(); i++)

For some applications, you will need to modify the basic iteration pattern to start
or end the iteration at a different index position. For example, the following
function checks to see whether a string begins with a particular prefix:

bool startsWith(string str, string prefix) {

if (str.length() < prefix.length()) return false;
for (int i = 0; i < prefix.length(); i++) {
if (str[i] != prefix[i]) return false;
}
return true;
}

This code begins by checking to make sure that str is not shorter than prefix (in
which case, the result must certainly be false) and then iterates only through the
characters in prefix rather than the string as a whole.
136 Strings

As you read through the code for the startsWith function, it is useful to pay
attention to the placement of the two return statements. The code returns false
from inside the loop, as soon as it discovers the first difference between the string
and the prefix. The code returns true from outside the loop, after it has checked
every character in the prefix without finding any differences. You will encounter
examples of this basic pattern over and over again as you read through this book.

The startsWith function and the similar endsWith function you will have a
chance to write in exercise 1 turn out to be very useful, even though they are not
part of the standard <string> library in C++. They are thus ideal candidates for
inclusion in a library of string functions that you create for yourself by applying the
same techniques used in Chapter 2 to define the error library. The Stanford
libraries include an interface called strlib.h that exports several useful string
functions. The contents of that interface are described in more detail later in this
chapter and appear in full in Appendix A.

Growing a string through concatenation

The other important pattern to memorize as you learn how to work with strings
involves creating a new string one character at a time. The loop structure itself will
depend on the application, but the general pattern for creating a string by
concatenation looks like this:

string str = "";

for (whatever loop header line fits the application) {
str += the next substring or character;
}

As a simple example, the following method returns a string consisting of n copies of

the character ch:

string repeatChar(int n, char ch) {

string str = "";
for (int i = 0; i < n; i++) {
str += ch;
}
return str;
}

The repeatChar function is useful, for example, if you need to generate some kind
of section separator in console output. One strategy to accomplish this goal would
be to use the statement
cout << repeatChar(72, '-') << endl;

which prints a line of 72 hyphens.

 3.3 The <cctype> library 137

Many string-processing functions use the iteration and concatenation patterns

together. For example, the following function reverses the argument string so that,
for example, calling reverse("desserts") returns "stressed":

string reverse(string str) {

string rev = "";
for (int i = str.length() - 1; i >= 0; i--) {
rev += str[i];
}
return rev;
}

3.3 The <cctype> library

Given that strings are composed of characters, it is often useful to have tools for
working with those individual characters, and not just the string as a whole. The
<cctype> library exports a variety of functions that work with characters, the most
common of which appear in Table 3-2.

The first section of Table 3-2 defines a set of predicate functions to test whether
a character belongs to a particular category. Calling isdigit(ch), for example,
returns true if ch is one of the digit characters in the range between '0' and '9'.
138 Strings

Similarly, calling isspace(ch) returns true if ch is any of the characters that

appear as white space on a display screen, such as spaces and tabs. The functions in
the second section of Table 3-2 make it easy to convert between uppercase and
lowercase letters. Calling toupper('a'), for example, returns the character 'A'.
If the argument to either the toupper or tolower function is not a letter, the
function returns its argument unchanged, so that tolower('7') returns '7'.

The functions in the <cctype> library often come in handy when you are
working with strings. The following function, for example, returns true if the
argument str is a nonempty string of digits, which means that it represents an
integer:

bool isDigitString(string str) {

if (str.length() == 0) return false;
for (int i = 0; i < str.length(); i++) {
if (!isdigit(str[i])) return false;
}
return true;
}

Similarly, the following function returns true if the strings s1 and s2 are equal,
ignoring differences in case:

bool equalsIgnoreCase(string s1, string s2) {

if (s1.length() != s2.length()) return false;
for (int i = 0; i < s1.length(); i++) {
if (tolower(s1[i]) != tolower(s2[i])) return false;
}
return true;
}

The implementation of equalsIgnoreCase returns false as soon as it finds the

first character position that doesnt match, but must wait until it reaches the end of
the loop to return true.

3.4 Modifying the contents of a string

Unlike other languages such as Java, C++ allows you to change the characters in a
string by assigning new values to a particular index position. That fact makes it
possible to design your own string functions that change the content of a string in
much the same way that the erase, insert, and replace functions do. In most
cases, however, it is better to write functions so that they return a transformed
version of a string without changing the original.
 3.4 Modifying the contents of a string 139

As an illustration of how these two approaches differ, suppose that you want to
design a string counterpart to the toupper function in the <cctype> library that
converts every lowercase character in a string to its uppercase equivalent. One
approach is to implement a procedure that changes the contents of the argument
string, as follows:

void toUpperCaseInPlace(string & str) {

for (int i = 0; i < str.length(); i++) {
str[i] = toupper(str[i]);
}
}

An alternative strategy is to write a function that returns an uppercase copy of its

argument without changing the original. If you use the iteration and concatenation
patterns, such a function might look like this:

string toUpperCase(string str) {

string result = "";
for (int i = 0; i < str.length(); i++) {
result += toupper(str[i]);
}
return result;
}

The strategy that modifies the string in place is more efficient, but the second is
more flexible and less likely to cause unexpected results. Having the first version,
however, makes it possible to code the second in a more efficient way:

string toUpperCase(string str) {

toUpperCaseInPlace(str);
return str;
}

In this implementation, C++ automatically copies the argument string because it is

passed by value. Given that str is no longer connected to the argument string in
the callers domain, it is perfectly acceptable to modify it in place and then return a
copy back to the caller.

3.5 The legacy of C-style strings

In its early years, C++ succeeded in part because it includes all of C as a subset,
thereby making it possible to evolve gradually from one language to the other. That
design decision, however, means that C++ includes some aspects of C that no
longer make sense in a modern object-oriented language, but nonetheless need to be
maintained for compatibility.
140 Strings

In C, strings are implemented as low-level arrays of characters, which offer none

of the high-level facilities that make the string class so useful. Unfortunately, the
decision to keep C++ compatible with C means that C++ must support both styles.
String literals, for example, are implemented using the older C-based style. For the
most part, you can ignore this historical detail because C++ automatically converts a
string literal to a C++ string whenever the compiler can determine that what you
want is a C++ string. If you initialize a string using the line

string str = "hello, world";

C++ automatically converts the C-style string literal "hello, world" to a C++
string object, because youve told the compiler that str is a string variable. By
contrast, C++ does not allow you to write the declaration

string str = "hello" + ", " + "world";

even though it seems as if this statement would have the same ultimate effect. The
problem here is that this version of the code tries to apply the + operator to string
literals, which are not C++ string objects.

If you need to get around this problem, you can explicitly convert a string literal
to a string object by calling string on the literal. The following line, for example,
correctly converts "hello" to a C++ string object and then uses concatenation to
complete the calculation of the initial value:

string str = string("hello") + ", " + "world";

Another problem that arises from having two different representations for strings
is that some C++ libraries require the use of C-style strings instead of the more
modern C++ string class. If you use these library abstractions in the context of an
application that uses C++ strings, you must at some point convert the C++ string
objects into their older, C-style counterparts. Specifying that conversion is simple
enough: all you have to do is apply the c_str method to the C++ version of a string
to obtain its C-style equivalent. The more important problem, however, is that
having to master two different representations for strings increases the conceptual
complexity of C++, thereby making it harder to learn.

3.6 Writing string applications

Although they are useful to illustrate how particular string functions work, the string
examples you have seen so far are too simple to give you much insight into writing
a significant string-processing application. This section addresses that deficiency
by developing two applications that manipulate string data.
 3.6 Writing string applications 141

Recognizing palindromes
A palindrome is a word that reads identically backward and forward, such as level
or noon. The goal of this section is to write a predicate function isPalindrome
that checks whether a string is a palindrome. Calling isPalindrome("level")
should return true; calling isPalindrome("xyz") should return false.

As with most programming problems, there are several reasonable strategies for
solving this problem. In my experience, the approach that most students are likely
to try first uses a for loop to run through each index position in the first half of the
string. At each position, the code then checks to see whether that character matches
the one that appears in the symmetric position relative to the end of the string.
Adopting that strategy leads to the following code:

bool isPalindrome(string str) {

int n = str.length();
for (int i = 0; i < n / 2; i++) {
if (str[i] != str[n - i - 1]) return false;
}
return true;
}

Given the string functions youve already encountered in this chapter, you can also
code isPalindrome in the following, much simpler form:

bool isPalindrome(string str) {

return str == reverse(str);
}

Of these two implementations, the first is more efficient. The second version has
to construct a new string that is the reverse of the original; worse still, it does so by
concatenating the characters together one at a time, which means that the program
creates as many intermediate string values as there are characters in the original
string. The first version doesnt have to create any strings at all. It does its work by
selecting and comparing characters, which turn out to be less costly operations.

Despite this difference in efficiency, I believe that the second coding is much
better, particularly as an example for new programmers. For one thing, it takes
advantage of existing code by making use of the reverse function. For another, it
hides the complexity involved in calculating index positions required by the first
version. It takes at least a minute or two for most students to figure out why the
code includes the selection expression str[n - i - 1] or why it is appropriate to
use the < operator in the for loop test, as opposed to <=. By contrast, the line

return str == reverse(str);

142 Strings

reads almost as fluidly as English: a string is a palindrome if it is equal to the same

string in reverse order.

Particularly as you are learning about programming, it is much more important

to work toward the clarity of the second implementation than the efficiency of the
first. Given the speed of modern computers, it is almost always worth sacrificing a
few machine cycles to make a program easier to understand.

Translating English to Pig Latin

To give you more of a sense of how to implement string-processing applications,
this section describes a C++ program that reads a line of text from the user and then
translates each word in that line from English to Pig Latin, a made-up language
familiar to most children in the English-speaking world. In Pig Latin, words are
formed from their English counterparts by applying the following rules:

1. If the word contains no vowels, no translation is done, which means that the
translated word is the same as the original.
2. If the word begins with a vowel, the function adds the string "way" to the end
of the original word.
3. If the word begins with a consonant, the function extracts the string of
consonants up to the first vowel, moves that collection of consonants to the end
of the word, and adds the string "ay".

As an example, suppose that the English word is scram. Because the word begins
with a consonant, you divide it into two parts: one consisting of the letters before
the first vowel and one consisting of that vowel and the remaining letters:

You then interchange these two parts and add ay at the end, as follows:

Thus the Pig Latin word for scram is amscray. For a word that begins with a vowel,
such as apple, you simply add way to the end, which leaves you with appleway.

The code for the PigLatin program appears in Figure 3-2. The main program
reads a line of text from the user and then calls lineToPigLatin to convert that
line to Pig Latin. The lineToPigLatin function then calls wordToPigLatin to
convert each word to its Pig Latin equivalent. Characters that are not part of a word
are copied directly to the output line so that punctuation and spacing remain
unaffected.
 3.6 Writing string applications 143

page 1 of figure.
144 Strings

Page 2 of figure.
 3.6 Writing string applications 145

A sample run of the program might look like this:

It is worth taking a careful look at the implementations of lineToPigLatin

and wordToPigLatin in Figure 3-2. The lineToPigLatin function finds the
word boundaries in the input and provides a useful pattern for separating a string
into individual words. The wordToPigLatin function uses substr to extract
pieces of the English word and then uses concatenation to put them back together in
their Pig Latin form. In Chapter 6, you will learn about a more general facility
called a token scanner that divides a string into its logically connected parts.
146 Strings

3.7 The strlib.h library

As Ive noted from time to time in the text, several of the functions in this chapter
seem ideal for inclusion in a library. Once you have written these functions as part
of one application, it would be silly not to use them in other applications that need
to perform the same operations. While functions like wordToPigLatin are
unlikely to show up anywhere else, you will often have occasion to use functions
like toUpperCase and startsWith. To avoid having to rewrite them or to
cut-and-paste the code, it makes sense to put those functions into a library so that
you always have them available.

The Stanford libraries distributed with the book include an interface called
strlib.h that exports the functions shown in Table 3-3. You can see on this list
several functions whose definitions appear in this chapter. In the exercises, you will
have a chance to fill in the definitions of some of the others, including endsWith
and trim. The first four functions in Table 3-3, all of which are concerned with
converting numeric values to string form, require techniques that are beyond the
limits of your knowledge of C++, but only for the moment. In Chapter 4, you will
learn how to use a new data type called a stream, which will make it easy to
implement these functions.
 Summary 147

Summary
In this chapter, you have learned how to use the <string> library, which makes it
possible to write string-processing functions without worrying about the details of
the underlying representation. The important points in this chapter include:

The <string> library exports a class called string that represents a sequence
of characters. Although C++ also includes a more primitive string type to
maintain compatibility with the C programming language, it is best to use the
string class in any programs that you write.
If you use the >> extraction operator to read string data, the input stops at the
first whitespace character. If you want to read an entire line of text from the
user, it is usually better to use the getline function from the standard C++
libraries.
The most common methods exported by the string class appear in Table 3-1
on page 130. Because string is a class, the methods use the receiver syntax
instead of the traditional functional form. Thus, to obtain the length of a string
stored in the variable str, you need to invoke str.length().
Several of the methods exported by the string class destructively modify the
receiver string. Giving clients free access to methods that change the internal
state of an object makes it harder to protect that objects integrity. The programs
in this book therefore minimize the use of these methods.
The string class uses operator overloading to simplify many common string
operations. For strings, the most important operators are + (for concatenation),
[] (for selection), and the relational operators.
The standard pattern for iterating through the characters in a string is

for (int i = 0; i < str.length(); i++) {

. . . body of loop that manipulates str[i] . . .
}

The standard pattern for growing a string by concatenation is

string str = "";

for (whatever loop header line fits the application) {
str += the next substring or character;
}

The <cctype> library exports several functions for working with individual
characters. The most important of these functions appear in Table 3-2.
148 Strings

Review questions
1. What is the difference between a character and a string?

2. True or false: If you execute the lines

string line;
cin >> line;

the program will read an entire line of data from the user and store it in the
variable line.

3. Which arguments to the getline function are passed by reference?

4. What is the difference between a method and a free function?

5. True or false: In C++, you can determine the length of the string stored in the
variable str by calling length(str).

6. If you call s1.replace(0, 1, s2), which string is the receiver?

7. What is the effect of the + operator when it is used with two string operands?

8. When C++ evaluates the expression s1 < s2, what rule does the string class
use to compare the string values?

9. What two syntactic forms does this chapter describe for selecting an individual
character from a string? How do these two syntactic forms differ in their
implementation?

10. When you select an individual character from a C++ string, you can use either
the at method or the standard subscript notation using square brackets. From
the clients perspective, what is the difference between these two options?

11. True or false: If you assign the value of the string variable s1 to the string
variable s2, the string class copies the characters so that subsequent changes
to the characters in one string will not affect the characters in the other.

12. True or false: The index positions in a string begin at 0 and extend up to the
length of the string minus 1.

13. What are the arguments to the substr method? What happens if you omit the
second argument?
 Review questions 149

14. What value does the find method return to indicate that the search string does
not appear?

15. What are the arguments to the substr method? What happens if you omit the
second argument?

16. What is the significance of the optional second argument to the find method?

17. What is the effect of each of the following calls to the <string> library:

string s = "ABCDE"
string t = "";

a. s.length() f. s.replace(0, 2, "Z")

b. t.length() g. s.substr(0, 3)
c. s[2] h. s.substr(4)
d. s + t i. s.substr(3, 9)
e. t += 'a' j. s.substr(3, 3)

18. What is the pattern for iterating through each character in a string?

19. How does this pattern change if you want to iterate through the characters in
reverse order, starting with the last character and ending with the first?

20. What is the pattern for growing a string through concatenation?

21. What is the result of each of the following calls to the <cctype> library:

a. isdigit(7) d. toupper(7)
b. isdigit('7') e. toupper('A')
c. isalnum(7) f. tolower('A')

22. Why does C++ support both a string class and a more primitive string type?

23. How can you convert a primitive string value to a C++ string? How can you
specify a conversion in the opposite direction?

Exercises
1. Implement the function endsWith(str, suffix), which returns true if
str ends with suffix. Like its startsWith counterpart, the endsWith
function should allow the second argument to be either a string or a character.
150 Strings

2. The strlib.h function exports a function trim(str) that returns a new

string formed by removing all whitespace characters from the beginning and
end of str. Write the corresponding implementation.

3. Without using the built-in string method substr, implement a free function
substr(str, pos, n) that returns the substring of str beginning at position
pos and containing at most n characters. Make sure that your function
correctly applies the following rules:

If n is missing or greater than the length of the string, the substring should
extend through the end of the original string.
If pos is greater than the length of the string, substr should call error
with an appropriate message.

4. Implement a function capitalize(str) that returns a string in which the

initial character is capitalized (if it is a letter) and all other letters are converted
to lowercase. Characters other than letters are not affected. For example, both
capitalize("BOOLEAN") and capitalize("boolean") should return
the string "Boolean".

5. In most word games, each letter in a word is scored according to its point
value, which is inversely proportional to its frequency in English words. In
Scrabble, the points are allocated as follows:

Points Letters
1 A, E, I, L, N, O, R, S, T, U
2 D, G
3 B, C, M, P
4 F, H, V, W, Y
5 K
8 J, X
10 Q, Z

For example, the word "FARM" is worth 9 points in Scrabble: 4 for the F, 1
each for the A and the R, and 3 for the M. Write a program that reads in words
and prints out their score in Scrabble, not counting any of the other bonuses
that occur in the game. You should ignore any characters other than uppercase
letters in computing the score. In particular, lowercase letters are assumed to
represent blank tiles, which can stand for any letter but have a score of 0.

6. An acronym is a new word formed by combining, in order, the initial letters of

a series of words. For example, the word scuba is an acronym formed from
the first letters in self-contained underwater breathing apparatus. Similarly,
AIDS is an acronym for Acquired Immune Deficiency Syndrome. Write a
 Exercises 151

function acronym that takes a string and returns the acronym formed from
that string. To ensure that your function treats hyphenated compounds like
self-contained as two words, it should define the beginning of a word as any
alphabetic character that appears either at the beginning of the string or after a
nonalphabetic character.

7. Write a function

string removeCharacters(string str, string remove);

that returns a new string consisting of the characters in str after removing all
instances of the characters in remove. For example, if you call

removeCharacters("counterrevolutionaries", "aeiou")

the function should return "cntrrvltnrs", which is the original string after
removing all of its vowels.

8. Modify your solution to exercise 7 so that, instead of using a function that

returns a new string, you define a function removeCharactersInPlace that
removes the letters from the string passed as the first argument.

9. The waste of time in spelling imaginary sounds and their history

(or etymology as it is called) is monstrous in English . . .
George Bernard Shaw, 1941

In the early part of the 20th century, there was considerable interest in both
England and the United States in simplifying the rules used for spelling
English words, which has always been a difficult proposition. One suggestion
advanced as part of this movement was to eliminate all doubled letters, so that
bookkeeper would be written as bokeper and committee would become comite.
Write a function removeDoubledLetters(str) that returns a new string in
which any duplicated characters in str have been replaced by a single copy.

10. Write a function

string replaceAll(string str, char c1, char c2);

that returns a copy of str with every occurrence of c1 replaced by c2. For
example, calling

replaceAll("nannies", 'n', 'd');

should return "daddies".

152 Strings

Once you have coded and tested this function, write an overloaded version

string replaceAll(string str, string s1, string s2);

that replaces all instances of the string s1 with the replacement string s2.

11. The concept of a palindrome is often extended to full sentences by ignoring

punctuation and differences in the case of letters. For example, the sentence

Madam, Im Adam.

is a sentence palindrome, because if you only look at the letters and ignore any
distinction between uppercase and lowercase letters, it reads identically
backward and forward.
Write a predicate function isSentencePalindrome(str) that returns
true if the string str fits this definition of a sentence palindrome. For
example, you should be able to use your function to write a main program
capable of producing the following sample run:

12. Write a function createRegularPlural(word) that returns the plural of

word formed by following these standard English rules:

a. If the word ends in s, x, z, ch, or sh, add es to the word.

b. If the word ends in a y preceded by a consonant, change the y to ies.
c. In all other cases, add just an s.

Write a test program and design a set of test cases to verify that your program
works.

13. Like most other languages, English include two types of numbers. The
cardinal numbers (such as one, two, three, and four) are used in counting; the
ordinal numbers (such as first, second, third, and fourth) are used to indicate a
position in a sequence. In text, ordinals are usually indicated by writing the
digits in the number, followed by the last two letters of the English word that
 Exercises 153

names the corresponding ordinal. Thus, the ordinal numbers first, second,
third, and fourth often appear in print as 1st, 2nd, 3rd, and 4th. The ordinals
for 11, 12, and 13, however, are 11th, 12th, and 13th. Devise a rule that
determines what suffix should be added to each number, and then use this rule
to write a function createOrdinalForm(n) that returns the ordinal form of
the number n as a string.

14. When large numbers are written out on paper, it is traditionalat least in the
United Statesto use commas to separate the digits into groups of three. For
example, the number one million is usually written in the following form:

1,000,000

To make it easier for programmers to display numbers in this fashion,

implement a function

string addCommas(string digits);

that takes a string of decimal digits representing a number and returns the
string formed by inserting commas at every third position, starting on the
right. For example, if you were to execute the main program

int main() {
while (true) {
string digits;
cout << "Enter a number: ";
getline(cin, digits);
if (digits == "") break;
cout << addCommas(digits) << endl;
}
return 0;
}

your implementation of the addCommas function should be able to produce the

following sample run:
154 Strings

15. As written, the PigLatin program in Figure 3-2 behaves oddly if you enter a
string that includes words beginning with an uppercase letter. For example, if
you were to capitalize the first word in the sentence and the name of the Pig
Latin language, you would see the following output:

Rewrite the wordToPigLatin function so that any word that begins with a
capital letter in the English line still begins with a capital letter in Pig Latin.
Thus, after making your changes in the program, the output should look like
this:

16. Most peopleat least those in English-speaking countrieshave played the

Pig Latin game at some point in their lives. There are, however, other
invented languages in which words are created using some simple
transformation of English. One such language is called Obenglobish, in which
words are created by adding the letters ob before the vowels (a, e, i, o, and u)
in an English word. For example, under this rule, the word english gets the
letters ob added before the e and the i to form obenglobish, which is how the
language gets its name.

In official Obenglobish, the o b characters are added only before vowels

that are pronounced, which means that a word like game would become
gobame rather than gobamobe because the final e is silent. While it is
impossible to implement this rule perfectly, you can do a pretty good job by
adopting the rule that the ob should be added before every vowel in the
English word except

Vowels that follow other vowels

An e that occurs at the end of the word
 Exercises 155

Write a function obenglobish that takes an English word and returns its
Obenglobish equivalent, using the translation rule given above. For example,
if you used your function with the main program

int main() {
while (true) {
string word = getLine("Enter a word: ");
if (word == "") break;
string trans = obenglobish(word);
cout << word << " -> " << trans << endl;
}
return 0;
}

you should be able to generate the following sample run:

17. If you played around with codes and ciphers as a child, the odds are good that
you at some point used a cyclic cipherwhich is often called a Caesar cipher
because the Roman historian Suetonius records that Julius Caesar used this
techniquein which you replace each letter in the original message by the
letter that appears a fixed distance ahead in the alphabet. As an example,
suppose that you wanted to encode a message by shifting every letter ahead
three places. In this cipher, each A becomes an D, B becomes E, and so on. If
you reach the end of the alphabet, the process cycles around to the beginning,
so that X becomes A, Y becomes B, and Z becomes C.

To implement a Caesar cipher, you should first define a function

string encodeCaesarCipher(string str, int shift);

that returns a new string formed by shifting every letter in str forward the
number of letters indicated by shift, cycling back to the beginning of the
156 Strings

alphabet if necessary. After you have implemented encodeCaesarCipher,

write a program that generates the following sample run:

Note that the transformation applies only to letters; any other characters are
copied unchanged to the output. Moreover, the case of letters is unaffected:
lowercase letters come out as lowercase, and uppercase letters come out as
uppercase. You should also write your program so that a negative value of
shift means that letters are shifted toward the beginning of the alphabet
instead of toward the end, as illustrated by the following sample run:

18. Although they are certainly simple, Caesar ciphers are also extremely easy to
break. There are, after all, only 25 values for the number of characters to shift.
If you want to break a Caesar cipher, all you have to do is try each of the 25
possibilities and see which one translates the original message into something
readable. A better scheme is to allow each letter in the original message to be
represented by an arbitrary letter instead of one a fixed distance from the
original. In this case, the key for the encoding operation is a translation table
that shows what each of the 26 letters becomes in the encrypted form. Such a
coding scheme is called a letter-substitution cipher.

The key in a letter-substitution cipher is a 26-character string that indicates

the translation for each character in the alphabet in order. For example, the
key "QWERTYUIOPASDFGHJKLZXCVBNM" indicates that the encoding process
should use the following translation rule:

Write a program that implements encryption using a letter-substitution

cipher. Your program should be able to duplicate the following sample run:
 Exercises 157

19. Using the definition of keys for letter-substitution ciphers as described in the
preceding problem, write a function invertKey that takes an encryption key
and returns the 26-letter key necessary to decrypt a message encoded with that
encryption key.

20. There is no gene for the human spirit.

Tagline for the 1997 film GATTACA

The genetic code for all living organisms is carried in its DNAa molecule
with the remarkable capacity to replicate its own structure. The DNA
molecule itself consists of a long strand of chemical bases wound together
with a similar strand in a double helix. DNAs ability to replicate comes from
the fact that its four constituent basesadenosine, cytosine, guanine, and
thyminecombine with each other only in the following ways:

Cytosine on one strand links only with guanine on the other, and vice versa.
Adenosine links only with thymine, and vice versa.

Biologists abbreviate the names of the bases by writing only the initial letter:
A, C, G, or T.

Inside the cell, a DNA strand acts as a template to which other DNA
strands can attach themselves. As an example, suppose that you have the
following DNA strand, in which the position of each base has been numbered
as it would be in a C++ string:

Your mission in this exercise is to determine where a shorter DNA strand can
attach itself to the longer one. If, for example, you were trying to find a match
for the strand
158 Strings

the rules for DNA dictate that this strand can bind to the longer one only at
position 1:

By contrast, the strand

matches at either position 2 or position 7.

Write a function

int findDNAMatch(string s1, string s2, int start = 0);

that returns the first position at which the DNA strand s1 can attach to the
strand s2. As in the find method for the string class, the optional start
parameter indicates the index position at which the search should start. If
there is no match, findDNAMatch should return 1.
Chapter 4
Streams

We will not be satisfied until justice rolls down like waters and
righteousness like a mighty stream.
Reverend Martin Luther King, Jr.
I Have a Dream, August 28, 1963
(paraphrasing Amos 5:24)
160 Streams

Ever since HelloWorld back in Chapter 1, the programs in this book have made
use of an important data structure called a stream, which C++ uses to manage the
flow of information to or from some data source. In the earlier chapters, you have
used the << and >> operators and have already had occasion to use the three
standard streams exported by the <iostream> library: cin, cout, and cerr. You
have, however, only scratched the surface of what you can do even with the
standard streams. To write C++ programs that move beyond the simple examples
you have seen up to now, you will have to learn more about streams and how to use
them to create more sophisticated applications. This chapter begins by giving you
more insight into the features provided by the << and >> operators. It then moves
on to introduce the notion of data files and shows you how to implement
file-processing applications. The chapter then concludes by exploring the structure
of the C++ stream classes as a representative example of inheritance hierarchies in
an object-oriented language.

4.1 Formatted output

The easiest way to generate formatted output in C++ is to use the << operator. This
operator is called the insertion operator because it has the effect of inserting data
into a stream. The operand on the left is the output stream; the operand on the right
is the data you want to insert into that stream. The << operator is overloaded so that
the operand on the right can be a string or any primitive value. If this operand is not
a string, the << operator converts it to string form before sending it to the output
stream. This feature makes it easy to display the values of variables, because C++
handles the output conversion automatically.

C++ makes generating output even more convenient by having the << operator
return the value of the stream. This design decision makes it possible to chain
several output operations together, as you have already seen in several examples in
this text. Suppose, for example, that you want to display the value of the variable
total on an output line that begins with some text telling the user what that value
represents. In C++, you would start with the expression

cout << "The total is "

which copies the characters in the string "The total is " to the cout stream. To
insert the decimal representation of the value in total, all you need to do is chain
on another instance of the << operator like this:

cout << "The total is " << total

This expression has the intended effect because the << operator returns the stream.
Thus, the left operand of the second << is simply cout, which means that the value
 4.1 Formatted output 161

of total is displayed there. Finally, you can signal the end of an output line by
inserting the value endl using yet another instance of the << operator:

cout << "The total is " << total << endl;

If total contains the value 42, the resulting output would look like this on the
console:

Even though you have been using statements like this one since the very
beginning, knowing that the << operator propagates the value of cout through the
expression as it moves along the chain of insertion operators may help you to
appreciate how output works in C++.

Although it seems as if it might be a simple string constant, the endl value used
to signal the end of an output line is actually an example of something that C++
calls a manipulator, which is just a fancy name for a special type of value used to
control formatting. The C++ libraries export a variety of manipulators that you can
use to specify the format for output values, the most common of which appear in
Table 4-1. For the most part, these manipulators are automatically available when
you include the <iostream> library. The only exceptions are the manipulators that
take parameters, such as setw(n), setprecision(digits), and setfill(ch). To
use these manipulators, you need to include <iomanip> as well.

Manipulators typically have the effect of setting properties of the output stream
in a way that changes the formatting of subsequent output. As the individual entries
in Table 4-1 make clear, some manipulators are transient, which means that they
affect only the next data value that appears. Most, however, are persistent, which
means that they take effect for that stream until they are explicitly changed.

One of the most common applications of manipulators involves specifying a

field width to support tabular output. Suppose, for example, that you want to
rewrite the PowersOfTwo program from Chapter 1 so that the numbers in the table
are aligned in columns. To do so, all you would need to do is add the appropriate
manipulators in the output statement, which will look something like this:

cout << right << setw(2) << i

<< setw(8) << raiseToPower(2, i) << endl;
162 Streams

Output manipulator table

 4.1 Formatted output 163

This statement prints the value of i in a field of width 2 and the value of the
function raiseToPower(2, i) in a field of width 8. Both fields are justified on
the right because the effect of the right manipulator is persistent. If you used this
line to display the powers of two between 0 and 16, the output would look like this:

Understanding the use of the setprecision(digits) manipulator is complicated

by the fact that the interpretation of the argument depends on other mode settings
for the stream. In the absence of any specifications to the contrary, C++ represents
floating-point numbers using either decimal or scientific notation, choosing the
representation that is more compact. The fact that C++ can choose either of these
representations makes sense if all you care about is seeing the value. If, however,
you want to control the output more precisely, you need to indicate which of these
formats you would like C++ to use. The fixed manipulator specifies that
floating-point values should always appear as a string of digits with a decimal point
in the appropriate position. Conversely, the scientific manipulator specifies that
values should always use the programming form of scientific notation in which the
exponent is separated from the value by the letter E. Each of these formats
interprets the setprecision manipulator in a slightly different way, which makes
it harder to provide a concise description of how setprecision works.

As is often the case in programming, one of the best ways to understand how
some highly detailed aspect of a library works is to write simple test programs that
allow you to see what happens on the screen. The PrecisionExample program in
Figure 4-1 shows how three constantsthe mathematical constant !, the speed of
light in meters per second, and the fine-structure constant that characterizes the
strength of electrical interactionappear using different floating-point modes and
precision. The output of the program is shown in Figure 4-2.
164 Streams

Program listing for PrecisionExample.

 4.2 Formatted input 165

Although the mechanisms for formatted input and output (which computer
scientists often abbreviate as I/O) in any programming language can be quite useful,
they also tend to be detail-ridden. In general, it makes sense to learn how to
perform a few of the most common formatting tasks but to look up the details of
other, less common operations only when you need to use them.

4.2 Formatted input

Formatted input in C++ is enabled by the operator >>, which you have already used
in a variety of programs. This operator is called the extraction operator, because it
is used to extract formatted data from an input stream. Up to now, you have used
the >> operator to request input values from the console, typically using a sequence
of statements such as the following lines from the PowersOfTwo program from
Chapter 1:

int limit;
cout << "Enter exponent limit: ";
cin >> limit;
166 Streams

By default, the >> operator skips over whitespace characters before trying to
read the input data. If necessary, you can change this behavior by using the skipws
and noskipws manipulators, which appear in the list of input manipulators in
Table 4-2. For example, if you execute the lines

char ch;
cout << "Enter a single character: ";
cin >> noskipws >> ch;

it would be possible to enter a space or tab character in response to the prompt. Had
you left out the noskipws manipulator, the program would have skipped over the
whitespace characters before storing the next input character in ch.

Although the extraction operator makes it easy to write simple test programs that
read input data from the console, it is not widely used in practice. The primary
problem with the >> operator is that it offers little support for checking whether user
input is valid. Users are notoriously sloppy when entering data into a computer.
They make typographical errors or, worse still, fail to understand exactly what input
the program requires. Well-designed programs check the users input to make sure
that it is well-formed and that it makes sense in the context.

Unfortunately, the >> operator is simply not up to this task, which is the reason
behind the existence of the simpio.h library introduced in section 2-9. If you use
the facilities provided by this library, the code to read a value from the user shrinks
from three lines to one:

int limit = getInteger("Enter exponent limit: ");

As noted in Chapter 2, the getInteger function also implements the necessary

error checking internally, making it much safer to use as well. Youll have a chance
to see how getInteger is implemented later in this chapter, after which it wont
seem so mysterious.
 4.3 Data files 167

4.3 Data files

Whenever you want to store information on the computer for longer than the
running time of a program, the usual approach is to collect the data into a logically
cohesive whole and store it on a permanent storage medium as a file. Ordinarily, a
file is stored using magnetic or optical media, such as the hard disk installed inside
your computer or a portable flash drive or memory stick. The specific details of the
medium, however, are not critical; the important point is that the permanent data
objects you store on the computerdocuments, games, executable programs, source
code, and the likeare all stored in the form of files.

On most systems, files come in a variety of types. For example, in the

programming domain, you work with source files, object files, and executable files,
each of which has a distinct representation. When you use a file to store data for
use by a program, that file usually consists of text and is therefore called a text file.
You can think of a text file as a sequence of characters stored in a permanent
medium and identified by a file name. The name of the file and the characters it
contains have the same relationship as the name of a variable and its contents.

As an example, the following text file contains the first stanza of Lewis Carrolls
nonsense poem Jabberwocky, which appears in Through the Looking Glass:

The name of the file is Jabberwocky.txt, and the contents of the file consist of
the four lines of characters that comprise the first stanza of the poem.

When you look at a file, it is often convenient to regard it as a two-dimensional

structure: a sequence of lines composed of individual characters. Internally,
however, text files are represented as a one-dimensional sequence of characters. In
addition to the printing characters you can see, files also contain a newline character
that marks the end of each line.

In many respects, text files are similar to strings. Each consists of an ordered
collection of characters with a specified endpoint. On the other hand, strings and
files differ in several important respects. The most important difference is the
permanence of the data. A string is stored temporarily in the computers memory
during the time that a program runs; a file is stored permanently on a long-term
storage device until it is explicitly deleted. There is also a difference in how you
refer to individual characters in strings and files. Because each character in a string
168 Streams

has an index, you can process those characters in any order simply by choosing the
appropriate sequence of index values. By contrast, characters in a text file tend to
be processed sequentially. Programs that work with file data typically start at the
beginning of the file and then work their wayeither reading existing characters
from an input file or writing new ones to an output fileto the end of the file.

Using file streams

As you will discover in section 4.4, the C++ stream library exports several classes
that form a hierarchical structure. To help you make sense of that structure as a
whole, it is useful to start with two stream classesifstream and ofstream
exported by the <fstream> library. Once you are familiar with those examples, it
will be easier to generalize from that experience to understand the stream hierarchy
as a whole.

The most common methods that apply to file streams appear in Table 4-3.
Studying this table, however, is not likely to be as helpful to you as learning a few
simple patterns for working with files. File processing in any language tends to be
idiomatic in the sense that you need to learn a general strategy and then apply that
strategy in the applications you write. C++ is no exception to this rule.

Reading or writing a file in C++ requires the following steps:

1. Declare a stream variable to refer to the file. Programs that work with files
typically declare a stream variable for each file that is simultaneously active.
Thus, if you are writing a program that reads an input file and uses that data to
write an output file, you need to declare two variables, as follows:

ifstream infile;
ofstream outfile;

2. Open the file. Before you can use a stream variable, you need to establish an
association between that variable and an actual file. This operation is called
opening the file and is performed by calling the stream method open. For
example, if you want to read the text contained in the Jabberwocky.txt file,
you open the file by executing the method call

infile.open("Jabberwocky.txt");

Because the stream libraries predate the introduction of the string class, the
open method expects a C-style string as the file name. A string literal is
therefore acceptable as is. If, however, the name of the file is stored in a
string variable named filename, you will need to open the file like this:

infile.open(filename.c_str());
4.3 Data files 169
170 Streams

If the requested file is missing, the stream will record that error and let you
check for it by calling the predicate method fail. It is your responsibility as a
programmer to recover from such failures, and you will see various strategies
for doing so later in this chapter.
3. Transfer the data. Once you have opened the data files, you then use the
appropriate stream operations to perform the actual I/O operations. Depending
on the application, you can choose any of several strategies to transfer the file
data. At the simplest level, you can read or write files character by character.
In some cases, however, it is more convenient to process files line by line. At a
still higher level, you can choose to read and write formatted data, which allows
you to intermix numeric data with strings and other data types. The details of
each of these strategies appear in the sections that follow.

4. Close the file. When you have finished all data transfers, you need to indicate
that fact to the file system by calling the stream method close, as follows:

infile.close();

This operation, which is called closing the file, breaks the association between
a stream and the actual file.

Single character I/O

In many applications, the best way to process the data in a text file is to go through
the contents of the file one character at a time. Input streams in the C++ library
support reading a single character using a method called get, which exists in two
forms. The simplest strategy is to use the first form of the get method listed in
Table 4-3, which stores the next character from the stream in a variable passed by
reference, as shown in the following code that reads the first character from the
infile stream into the variable ch:

char ch;
infile.get(ch);

For most applications, of course, the goal is not to read a single character, but
instead to read successive characters, one at a time, as you go through the file. C++
makes this operation very easy by allowing streams to be used in conditional
contexts. The general pattern for reading all the characters in a file looks like this:

char ch;
while (infile.get(ch)) {
Perform some operation on the character.
}
 4.3 Data files 171

The get method reads the next character into the variable ch and returns the stream.
That stream, in turn, is interpreted as true if the get operation succeeds and as
false if it fails, presumably because there are no characters left in the file. The
effect, therefore, is to execute the body of the while loop once for each character
until the stream reaches the end of the file.

Although this strategy is extremely simple, many C++ programmers will use the
version of get that returns a character, mostly because that strategy was available
even back in the days of C programming. This form of the get method has the
following prototype:

int get();

At first glance, the result type seems odd. The prototype indicates that get returns
an int, even though it would seem more appropriate for the method to return a
char. The reason for this design decision is that returning a character would make
it harder for a program to detect the end of the input file. There are only 256
possible character codes, and a data file might contain any of those values. There is
no valueor at least no value of type charthat you could use as a sentinel to
indicate the end-of-file condition. By extending the definition so that get returns
an integer, the implementation can return a value outside the range of legal
character codes to indicate the end-of-file condition. That value has the symbolic
name of EOF.

If you use this form of the get method, the code pattern to read an entire file
character by character looks like this:

while (true) {
int ch = infile.get();
if (ch == EOF) break;
Perform some operation on the character.
}

This implementation uses the read-until-sentinel pattern that was introduced in the
AddList program from Chapter 1. The body of the while loop reads the next
character into the integer variable ch and then exits the loop if ch is the end-of-file
sentinel.

Many C++ programmers, however, implement this loop in the following slightly
shorter but decidedly more cryptic form:

int ch;
while ((ch = infile.get()) != EOF) {
Perform some operation on the character.
}
172 Streams

In this form of the code, the test expression for the while loop uses embedded
assignment to combine the operations of reading in a character and testing for the
end-of-file condition. When C++ evaluates this test, it begins by evaluating the
subexpression

ch = infile.get()

which reads a character and assigns it to ch. Before executing the loop body, the
program then goes on to make sure the result of the assignment is not EOF. The
parentheses around the assignment are required; without them, the expression would
incorrectly assign to ch the result of comparing the character against EOF. Because
this idiom occurs frequently in existing C++ code, you need to recognize it and
understand it when it appears. In your own code, it is far easier to use the simpler
idiom based on the call-by-reference version of get.

For output streams, the put method takes a char value as its argument and
writes that character to the stream. A typical call to put therefore looks like this:

outfile.put(ch);

As an example of the use of get and put, the ShowFileContents program in

Figure 4-3 displays the contents of a text file on the console. Assuming that the
Jabberwocky.txt file exists, a sample run of this program might look like this:

The code in Figure 4-3 also includes the function promptUserForFile, which
asks the user to enter a file name and then opens that file for input. If the file does
not exist or cannot be opened for some reason, promptUserForFile asks the user
for a new file name, continuing that process until the open call succeeds. This
design allows the program to recover gracefully if the user enters an invalid file
name. For example, if the user forgot to include the .txt extension the first time
around, the first few lines of the console output would look like this:
 4.3 Data files 173

Figure
174 Streams

Although the logic behind the implementation of promptUserForFile is easy

to follow, there are a few important details that are worth mentioning. The open
call, for example, needs to use c_str to convert the C++ string stored in filename
to the old-style C string that the stream library requires. Similarly, the call to clear
inside the while loop is necessary to ensure that the failure status indicator in the
stream is reset before the user enters a new file name.

When you are reading character data from an input file, you will sometimes find
yourself in the position of not knowing that you should stop reading characters until
you have already read more than you need. Consider, for example, what happens
when the C++ extraction operator tries to read an integer, which is represented as a
string of decimal digits. The library implementation cannot know that the number is
finished until it reads a character that is not a digit. That character, however, may
be part of some subsequent input, and it is essential not to lose that information.

C++ solves this problem for input streams by exporting a method called unget
that has the following form:

infile.unget();

The effect of this call is to push the most recent character back into the input
stream so that it is returned on the next call to get. The specifications for the C++
library guarantees that it will always be possible to push one character back into the
input file, but you should not rely on being able to read several characters ahead and
then push them all back. Fortunately, being able to push back one character is
sufficient in the vast majority of cases.

Line-oriented I/O
Because files are usually subdivided into individual lines, it is often useful to read
an entire line of data at a time. The stream function that performs this operation is
called getline, which is not the same as the getLine function from simpio.h
even though they serve a similar purpose. The getline functionwhich is
defined as a free function rather than a methodtakes two references parameters:
the input stream from which the line is read and a string variable into which the
result is written. Calling

getline(infile, str);

copies the next line of the file into the variable str, up to but not including the
newline character that signals the end of the line. Like get, the getline function
returns the input stream, which makes it easy to test for the end-of-file condition.
All you have to do is use the getline call itself as a test expression.
 4.3 Data files 175

The getline function makes it possible to rewrite the ShowFileContents

program so that the program reads the file one line at a time. Using this approach,
the while loop in the main program looks like this:

string line;
while (getline(infile, line)) {
cout << line << endl;
}

The while loop reads each line of data from the file into the string variable line
until the stream reaches the end of the file. For each line, the body of the loop uses
the << operator to send the line to cout, followed by a newline character.

Formatted I/O
In addition to the character-by-character and line-by-line approaches to processing
files, it is also possible to use the << and >> operators on file streams, just as you
have already had occasion to do with the console streams. Suppose, for example,
that you want to revise the AddIntegerList program from Figure 1-4 so that it
takes its input from a data file instead of from the console. The simplest approach is
to open a data file for input and use the resulting ifstream instead of cin to read
the input values.

The only other change you need to make is in the code that exits the loop when
the input is complete. The console version of the program used a sentinel value to
indicate the end of the input. For the version that reads from a file, the loop should
continue until there are no more data values to read. The easiest way to test for that
condition is to use the >> operator as a test. Since >> returns the stream, it will
indicate the end-of-file condition by setting the fail flag, which C++ then
interprets as false.

If you make these changes to the original code, the program looks like this:

int main() {
ifstream infile;
promptUserForFile(infile, "Input file: ");
int total = 0;
int value;
while (infile >> value) {
total += value;
}
infile.close();
cout << "The sum is " << total << endl;
return 0;
}
176 Streams

Unfortunately, this implementation strategy is less than ideal, even if it is not

technically incorrect. If all the numbers are formatted in exactly the right way, the
program will get the right answer. If, however, there are extraneous characters in
the file, the loop will exit before all the input values have been read. Worse still, the
program will give no indication that an error has occurred.

The crux of the problem is that the extraction operator in the expression

infile >> value;

will set the failure indicator in either of two cases:

1. Reaching the end of the file, at which point there are no more values to read.
2. Trying to read data from the file that cannot be converted to an integer.

You can make things better by checking to make sure the end of the file has been
reached when the loop exits. For example, you could at least let the user know that
an error had occurred by adding the following lines after the while loop:

if (!infile.eof()) {
error("Data error in file");
}

The error doesnt provide the user with much guidance as to the source of the data
error, but at least its better than nothing.

Another problem, however, is that the extraction operator is overly permissive in

terms of the formats it allows. Unless you specify otherwise, the >> operator will
accept any sequence of whitespace characters as data separators. Thus, the data in
the input file need not be one value per line, but can be formatted in any of a
number of ways. For example, if you wanted to use your application to add the first
five integers, it would not be necessary to enter the data with one value per line, as
illustrated by the following data file:

1
2
3
4
5

It would work just as welland might indeed be more convenientto put the
values on a single line like this:

1 2 3 4 5
 4.3 Data files 177

One problem with having this much flexibility is that it becomes harder to detect
certain kinds of formatting errors. What happens, for example, if you accidentally
include a space in one of the integers? As things stand, the SumIntegerFile
application would simply read the digits before and after the space as two separate
values. In such cases, it is often better to insist on more rigid formatting rules to
improve data integrity.

In the SumIntegerFile application, it probably makes sense to insist that the

data values appear one per line, as in the first sample file. Unfortunately, enforcing
that restriction is difficult if the only tools you have are file streams and the
extraction operator. One way to start would be to read the data file one line at a
time and then convert each line to an integer before adding it to the total. If you
were to adopt this approach, the main program would look like this:

int main() {
ifstream infile;
promptUserForFile(infile, "Input file: ");
int total = 0;
string line;
while (getline(infile, line)) {
total += stringToInteger(line);
}
infile.close();
cout << "The sum is " << total << endl;
return 0;
}

The only thing thats missing is the implementation of stringToInteger.

Although the C++ libraries include a function called atoi that converts a string
to an integer, that function predates the <string> library and therefore requires the
use of C strings, which are much less convenient to use. It would be great if you
could find a way to implement that conversion while remaining entirely in the C++
domain. You know that the C++ libraries must contain the necessary code, because
the >> operator has to perform that conversion when it reads an integer from a file.
If there were a way to use that same code to read an integer from a string, the
implementation of stringToInteger would follow immediately as a result. As
you will learn in the following section, the C++ stream libraries provide precisely
that capability, which will turn out to be useful in a wide variety of applications.

String streams
Given that files and strings are both sequences of characters, it seems reasonable to
think that programming languages might allow you to treat them symmetrically.
C++ provides that capability through the <sstream> library, which exports several
178 Streams

classes that allow you to associate a stream with a string value in much the same
way that the <fstream> library allows you to associate a stream with a file. The
istringstream class is the counterpart of ifstream and makes it possible to use
stream operators to read data from a string. For output, the ostringstream class
works very much like ofstream except that the output is directed to a string rather
than a file.

The existence of the istringstream class makes it possible to implement the

stringToInteger method described in the last section as follows:

int stringToInteger(string str) {

istringstream stream(str);
int value;
stream >> value >> ws;
if (stream.fail() || !stream.eof()) {
error("stringToInteger: Illegal integer format");
}
return value;
}

The first line of the function introduces an important feature of variable declarations
that you have not yet seen. If you are declaring an object, C++ allows you to supply
arguments after the variable name that control how that object is initialized. Here,
the line

istringstream stream(str);

declares a variable named stream and initializes it to an istringstream object

that is already set up to read data from the string variable str. The next two lines

int value;
stream >> value >> ws;

read an integer value from that stream and store it in the variable value. In this
implementation, whitespace characters are allowed either before or after the value.
The first >> operator automatically skips over any whitespace characters that appear
before the value; the ws manipulator at the end of the line reads any whitespace
characters that follow the value, thereby ensuring that the stream will be positioned
correctly at the end of the line if the input is correctly formatted. The lines

if (stream.fail() || !stream.eof()) {
error("stringToInteger: Illegal integer format");
}
 4.3 Data files 179

then check to make sure that the input is valid. If the string cannot be parsed as an
integer, stream.fail() will return true, thereby triggering the error message. If,
however, the string begins with a number but then contains some additional
characters, stream.eof() will be false, which also triggers the error message.

If you need to convert in the other direction, you can use the ostringstream
class. The following function, for example, converts an integer into a string of
decimal digits:

string integerToString(int n) {
ostringstream stream;
stream << n;
return stream.str();
}

The << operator in the second line converts the value into its decimal representation
just as it would for a file. Here, however, the output is directed to a string value
stored internally as part of the ostringstream object. The str function in the
return statement copies the value of that internal string so that it can be returned to
the caller. It is interesting to note that converting in this direction is substantially
easier because it is no longer necessary to take account of formatting errors.

A better strategy for console input

String streams also offer a solution to the problem of checking whether user input is
properly formed. As discussed in the section on Formatted input earlier in the
chapter, the >> operator does not check the users input for errors. Consider, for
example, what happens if you ask the user for an integer value using the following
statements from the PowersOfTwo program:

int limit;
cout << "Enter exponent limit: ";
cin >> limit;

If the user enters a valid integer, everything is fine. But what happens if the user
tries to enter the value 16 but slips down one row on the keyboard and types the
letter t instead of the digit 6? In an ideal world, the program would look at the
input 1t and complain about its validity. Unfortunately, if you use the extraction
operator in C++, that error will go undetected. When it is asked to read a value into
the integer variable limit, the >> operator reads characters until it finds one that is
illegal in an integer field. Input therefore stops on the t, but the value 1 is still a
legal integer, so the program would keep right on going with limit equal to 1.
180 Streams

The most effective way to ensure that user input is valid is to read an entire line
as a string and then convert that string to an integer. This strategy is embodied in
the function getInteger shown in Figure 4-4. This function reads an integer from
the user just as the >> operator does but also makes sure that the integer is valid.
The logic of getInteger is similar to that used in the stringToInteger function
from the preceding section. The only major difference is that getInteger gives
the user a chance to reenter a corrected value instead of terminating the program
with an error message, as illustrated in the following sample run:

PowersOfTwo
This program lists powers of two.
Enter exponent limit: 1t
Illegal integer format. Try again.
Enter exponent limit: 16

As this example makes clear, getInteger finds the typographical error in the first
input line and then asks the user for a new value. When the user presses RETURN
after correctly typing the value 16, getInteger returns this value to the caller.
 4.4 Class hierarchies 181

As you can see from the code in Figure 4-4, the getInteger function takes a
prompt string, which it then displays to the user before reading the input line. This
design decision follows directly from the fact that the getInteger function needs
that information in order to repeat the prompt string if an error occurs.

The getInteger function is a more reliable tool for reading integer data than
the >> operator. For that reason, it makes sense to use getInteger instead of >>
in any application that requires checking for errors. As you already know from
Chapter 2, the Stanford libraries include getInteger as part of the simpio library.

4.4 Class hierarchies

When the designers of C++ undertook the task of modernizing the input/output
libraries, they chose to adopt an object-oriented approach. One implication of that
decision is that the data types in the stream libraries are implemented as classes.
Classes have a number of advantages over older strategies for representing data. Of
these, the most important is that classes provide a framework for encapsulation,
which is the process of combining the data representation and the associated
operations into a coherent whole that reveals as few details as possible about the
underlying structure. The classes you have already seen in this chapter illustrate
encapsulation well. When you use these classes, you have no idea how they are
implemented. As a client, all you need to know is what methods are available for
those classes and how to call them.

Object-oriented programming, however, offers other important advantages

besides encapsulation. Classes in an object-oriented language form a hierarchy in
which each class automatically acquires the characteristics of the classes that
precede it in the hierarchy. This property is called inheritance. Although C++
tends to use inheritance somewhat less frequently than many object-oriented
languages do, it is nonetheless one of the features that sets the object-oriented
paradigm apart from earlier programming models.

Biological hierarchies
The class structure of an object-oriented language is similar in many ways to the
biological classification system developed by the Swedish botanist Carl Linnaeus in
the eighteenth century as a way to represent the structure of the biological world. In
Linnaeuss conception, living things are first subdivided into kingdoms. The
original system contained only the plant and animal kingdoms, but there are some
forms of lifesuch as fungi and bacteriathat dont fit well in either category and
now have kingdoms of their own. Each kingdom is then further broken down into
the hierarchical categories of phylum, class, order, family, genus, and species.
Every living species fits at the bottom of this hierarchy but also belongs to some
category at each higher level.
182 Streams

This biological classification system is illustrated in Figure 4-5, which shows the
classification of the common black garden ant, which has the scientific name of
Lasius niger, corresponding to its genus and species. This species of ant, however,
is also part of the family Formicidae, which is the classification that actually
identifies it as an ant. Moving upward in the hierarchy from there, Lasius niger is
also of the order Hymenoptera (which also includes bees and wasps), the class
Insecta (which consists of the insects), and the phylum Arthropoda (which also
includes, for example, shellfish and spiders).
 4.4 Class hierarchies 183

One of the properties that makes this biological classification system useful is
that all living things belong to a category at every level in the hierarchy. Each
individual life form therefore belongs to several categories simultaneously and
inherits the properties that are characteristic of each one. The species Lasius niger,
for example, is an ant, an insect, and arthropod, and an animalall at the same
time. Moreover, each individual ant shares the properties that it inherits from each
of those categories. One of the defining characteristics of the class Insecta is that
insects have six legs. All ants must therefore have six legs because ants are
members of that class.

The biological metaphor also helps to illustrate the distinction between classes
and objects. Every common black garden ant has the same classification, but there
can be many different ants that all fit that single pattern. Thus, each of the ants

is an instance of Lasius niger. In the language of object-oriented programming,

Lasius niger is a class and each individual ant is an object.

The stream class hierarchy

The classes in the stream libraries form hierarchies that are in many ways similar to
the biological hierarchy introduced in the preceding section. So far, you have seen
two types of input streamsifstream and istringstreamand two types of
output streamsofstream and ostringstreamthat in each pairing share a
common set of operations. In C++, these classes form the hierarchy shown in
Figure 4-6. At the top of the hierarchy is the class ios, which represents a general
stream type that can be used for any kind of I/O. The hierarchy is then subdivided
184 Streams

into two categoriesistream and ostreamthat generalize the notions of input

stream and output stream, respectively. The C++ file and string stream classes then
fall naturally into the appropriate position in this hierarchy, as shown.

Figure 4-6 provides a useful framework for introducing some of the terminology
associated with object-oriented programming. In this diagram, which was drawn
using the same geometrical structure as the evolutionary diagram in Figure 4-5,
each class is a subclass of the class that appears above it in the hierarchy. Thus,
istream and ostream are both subclasses of ios. In the opposite direction, ios
is called a superclass of both istream and ostream. Similar relationships exist at
different levels of this diagram. For example, ifstream is a subclass of istream,
and ostream is a superclass of ofstream.

The relationship between subclasses and superclasses is in many ways best

conveyed by the English words is a. Every ifstream object is also an istream
and, by continuing up the hierarchy, an ios. As in the biological hierarchy, this
relationship implies that the characteristics of any class are inherited by its
subclasses. In C++, these characteristics correspond to the methods and other
definitions associated with the class. Thus, if the istream class exports a
particular method, that method is automatically available to any ifstream or
istringstream object. More globally, any methods exported by the ios class are
available to every class in the hierarchy shown in Figure 4-6.

Although simple diagrams that show only the relationships among classes are
often useful in their own right, it is useful to expand them to include the methods
exported at each level, as shown in Figure 4-7. This enhanced diagram adopts parts
of a standard methodology for illustrating class hierarchies called the Universal
Modeling Language, or UML for short. In UML, each class appears as a
rectangular box whose upper portion contains the name of the class. The methods
exported by that class appear in the lower portion. In UML diagrams, subclasses
use open arrowheads to point to their superclasses.

UML diagrams of the sort shown in Figure 4-7 make it easy to determine what
methods are available to each of the classes in the diagram. Because each class
inherits the methods of every class in its superclass chain, an object of a particular
class can call any method defined in any of those classes. For example, the diagram
indicates that any ifstream object has access to the following methods:

The open and close methods from the ifstream class itself
The get and unget methods and the >> operator from the istream class
The clear, fail, and eof methods from the ios class
 4.4 Class hierarchies 185

Choosing the right level in the stream hierarchy

One of the most important decisions you need to make when you use object
hierarchies is finding the right level at which to work. As a general rule, it is best to
write your code so that it uses the most general level in the hierarchy that supports
the operations you need. Adopting this rule ensures that your code is as flexible as
possible in that it supports the widest range of types.

As an example, you will often find it useful to define a copyStream method that
copies all the characters from one input stream to another. If you had come up with
this idea as you were working with file streams, you might have been tempted to
implement the method as follows:

void copyStream(ifstream & infile, ofstream & outfile) {

while (true) {
int ch = infile.get();
if (ch == EOF) break;
outfile.put(ch);
}
}

Although this implementation is not technically incorrect, it is certainly problematic

enough to justify the bug icon. The problem is that the method works only for file
streams, even though the code would be perfectly appropriate for any type of input
186 Streams

and output stream if you had chosen more general types for the arguments. A much
better implementation of copyStream looks like this:

void copyStream(istream & is, ostream & os) {

char ch;
while (is.get()) {
os.put(ch);
}
}

The advantage of the new coding is that you can use this version of copyStream
with any stream types. For example, given this implementation of copyStream,
you could replace the while loop in ShowFileContents with the single line

copyStream(infile, cout);

which copies the contents of the file to cout. The previous versionin which the
second argument is declared to be an ofstream rather than the more general class
ostreamfails because cout is not a file stream.

4.5 The simpio.h and filelib.h libraries

Chapter 3 introduced several new functions that were useful enough to package up
as the strlib.h library. In this chapter, you have seen several useful tools for
working with streams that have also made their way into two interfaces in the
Stanford library: the simpio.h interface you have already seen and a filelib.h
interface for the methods that are more closely related to files.

Although it is possible to list the contents of each of those interfaces in tables of

the sort you have already seen for the standard libraries, most modern interfaces are
not described on paper. With the expansion of the web, programmers use online
reference materials more often than printed ones. Figure 4-8, for example, shows
the web-based documentation for the simpio.h library.

Although the tabular description fits well on the printed page and the web-based
documentation is ideal for online browsing, you do have another option for learning
what resources are available in an interface: you can read the .h file. If an interface
is designed and documented effectively, reading the .h file may well be the best
option. In any event, reading .h files is a programming skill that you will need to
cultivate if you want to become proficient in C++.

To give yourself some practice in reading interfaces, you should look at the
filelib.h interface, which appears in Appendix A. That interface includes the
promptUserForFile function developed in this chapter, along with a number of
other functions that will likely come in handy when you work with files.
 4.5 The simpio.h and filelib.h libraries 187

Web documentation for simpio.h

188 Streams

Summary
In this chapter, you have learned how to use the libraries in the stream hierarchy to
support input/output operations involving the console, strings, and data files.
Important points in this chapter include:

The <iostream> library exports three standard streams: cin, cout, and cerr.
The <iomanip> library makes it possible to control the output format. This
library exports a set of manipulators, the most important of which appear in
Table 4-1. The <iomanip> library includes manipulators for input as well, but
these are less important in practice.
The <fstream> library in C++ supports reading and writing data files. The
most important methods that apply to file streams are listed in Table 4-3.
The C++ stream libraries allow you to choose any of several different strategies
when reading a file. You can read the file character by character using the get
methods, line by line using the getline method, or as formatted data using the
>> extraction operator.
The <sstream> library makes it possible to use the >> and << operators to read
and write string data.
The classes in the stream library form a hierarchy in which subclasses inherit the
behavior of their superclasses. When you design functions to work with streams,
it is important to choose the most general level of the hierarchy for which the
necessary operations are defined.
At various points in the first three chapters, the text defines new functions that
are likely to prove useful in many different contexts. To make sure that these
functions are easily available without having to copy the code, those functions
are exported through several interfaces that constitute the Stanford C++ libraries.

Review questions
1. What are the three standard file streams defined by the <iostream> library?

2. What are the formal names for the << and >> operators?

3. What value do the << and >> operators return? Why is this value important?

4. What is a manipulator?

5. What is the difference between a transient and a persistent property?

6. In your own words, describe how the fixed and scientific manipulators
change the format for floating-point output. What happens if you dont
specify either of these options?
 Review questions 189

7. Suppose that the constant PI has been defined as

const double PI = 3.14159265358979323846;

What output manipulators would you use to produce each line of the following
sample run:

8. What is the purpose of the types ifstream and ofstream?

9. The argument to open must be a C-style string. How does this requirement
affect the code you write to open a file?

10. How can you determine if an open operation on a stream was successful?

11. When you are using the get method to read a file character by character, how
do you detect the end of a file?

12. Why is the return type of get declared as int instead of char?

13. What is the purpose of the unget method?

14. When you are using the getline method to read a file line by line, how do
you detect the end of a file?

15. What classes does the <sstream> library support? How are these classes
different from the ones provided in <fstream>?

16. What is meant by the following terms: subclass, superclass, and inheritance?

17. True or false: The stream class hierarchy of Figure 4-7 shows that istream
is a subclass of istringstream.

18. Why does the copyStream function take arguments of type istream and
ostream instead of ifstream and ofstream?

19. What are the advantages of using the getInteger and getReal functions
from simpio.h over using the >> extraction operator?

20. If this text does not describe the functions exported by a library in tabular
form, what options do you have for learning how to use that library?
190 Streams

Exercises
1. The <iomanip> library gives programmers more control over output format,
which makes it easy, for example, to create formatted tables. Write a program
that displays a table of trigonometric sines and cosines that looks like this:

The numeric columns should all be aligned on the right, and the columns
containing the trigonometric functions (which are listed here for angles at
15-degree intervals) should all have seven digits after the decimal point.

2. In exercise 4 in Chapter 2, you wrote a function windChill that calculated

the wind chill for a given temperature and wind velocity. Write a program that
uses this function to display these values in tabular form, as illustrated by the
table from the National Weather service shown in Figure 2-17 on page 116.

3. Write a program that prints the longest line in a file chosen by the user. If
several lines are all equally long, your program should print the first such line.

4. Write a program that reads a file and reports how many lines, words, and
characters appear in it. For the purposes of this program, a word consists of a
consecutive sequence of any characters except whitespace characters. As an
example, suppose that the file Lear.txt contains the following passage from
Shakespeares King Lear,
 Exercises 191

your program should be able to generate the following sample run:

The counts in the output should be displayed in a column that is aligned on

the right but which expands to fit the data. For example, if you have a file
containing the full text of George Eliots Middlemarch, the output of your
program should look like this:

5. The filelib.h interface exports several functions that make it easy to work
with filenames. Two functions that are particularly useful are getRoot and
getExtension, which divide a function into its root, which is the identifying
part of the filename, and the extension, which indicates its type. For example,
given the filename Middlemarch.txt used in the preceding exercise, the
root is Middlemarch and the extension is .txt (note that filelib.h defines
the extension to includes the dot). Write the code necessary to implement
these functions. To find out how to handle special cases, such as filenames
that dont include a dot, consult the filelib.h interface in Appendix A.

6. Another useful function in filelib.h is

string defaultExtension(string filename, string ext);

which adds ext to the end of filename if it doesnt already have an

extension. For example,
defaultExtension("Shakespeare", ".txt")

would return "Shakespeare.txt". If filename already has an extension,

that name is returned unchanged, so that
defaultExtension("library.h", ".cpp")

would ignore the specified extension and return "library.h" unchanged. If,
however, ext includes a star before the dot, defaultExtension removes
192 Streams

any existing extension from filename and adds the new one (minus the star).
Thus,
defaultExtension("library.h", "*.cpp")

would return "library.cpp". Write the code for defaultExtension so

that it behaves as described in this exercise.

7. On occasion, publishers find it useful to evaluate layouts and stylistic designs

without being distracted by the actual words. To do so, they sometimes
typeset sample pages in such a way that all of the original letters are replaced
with random letters. The resulting text has the spacing and punctuation
structure of the original, but no longer conveys any meaning that might get in
the way of the design. The publishing term for text that has been replaced in
this way is greek, presumably after the old saying Its all Greek to me,
which is itself adapted from a line from Julius Caesar.

Write a program that reads characters from an input file and displays them
on the console after making the appropriate random substitutions. Your
program should replace every uppercase character in the input by a random
uppercase character and every lowercase character by a random lowercase
one. Nonalphabetic characters should remain unchanged. For example, if the
input file Troilus.txt contains the text from Troilus and Cressida,

your program should generate output that looks something like this:

8. Even though comments are essential for human readers, the compiler simply
ignores them. If you are writing a compiler, you therefore need to be able to
recognize and eliminate comments that occur in a source file.

Write a function
void removeComments(istream & is, ostream & os);
 Exercises 193

that copies characters from the input stream is to the output stream os, except
for characters that appear inside C++ comments. Your implementation should
recognize both comment conventions:

Any text beginning with /* and ending with */, possibly many lines later.
Any text beginning with //and extending through the end of the line.

The real C++ compiler needs to check to make sure that these characters are
not contained inside quoted strings, but you should feel free to ignore that
detail. The problem is tricky enough as it stands.

9. Books were bks and Robin Hood was Rbinhd. Little Goody Two
Shoes lost her Os and so did Goldilocks, and the former became a
whisper, and the latter sounded like a key jiggled in a lck. It was
impossible to read cockadoodledoo aloud, and parents gave up
reading to their children, and some gave up reading altogether. . . .
James Thurber, The Wonderful O, 1957

In James Thurbers childrens story The Wonderful O, the island of Ooroo is

invaded by pirates who set out to banish the letter O from the alphabet. Such
censorship would be much easier with modern technology. Write a program
that asks the user for an input file, an output file, and a string of letters to be
eliminated. The program should then copy the input file to the output file,
deleting any of the letters that appear in the string of censored letters, no
matter whether they appear in uppercase or lowercase form.

As an example, suppose that you have a file containing the first few lines
of Thurbers novel, as follows:

If you run your program with the input

it should write the following file:

194 Streams

If you try to get greedy and banish all the vowels by entering aeiou in
response to the prompt, the contents of the output file would be

10. Some files use tab characters to align data into columns. Doing so, however,
can cause problems for applications that are unable to work directly with tabs.
For these applications, it is useful to have access to a program that replaces
tabs in an input file with the number of spaces required to reach the next tab
stop. In programming, tab stops are usually set at every eight columns. For
example, suppose that the input file contains a line of the form

where the symbol represents the space taken up by a tab, which differs
depending on its position in the line. If the tab stops are set every eight
spaces, the first tab character must be replaced by five spaces and the second
tab character by three.

Write a program that copies an input file to an output file, replacing all tab
characters by the appropriate number of spaces.

11. Using the functions stringToInteger and integerToString as a model,

write the code necessary to implement stringToReal and realToString.

12. Complete the implementation of the simpio.h interface by implementing the

functions getReal and getLine.
Chapter 5
Collections

In this way I have made quite a valuable collection.

Mark Twain, A Tramp Abroad, 1880
196 Collections

As you know from your programming experience, data structures can be assembled
to form hierarchies. The atomic data types like int, char, double, and the
enumerated types occupy the lowest level in the hierarchy. To represent more
complex information, you combine the atomic types to form larger structures.
These larger structures can then be assembled into even larger ones in an
open-ended process. Collectively, these assemblages are called data structures.

As you learn more about programming, you will discover that particular data
structures are so useful that they are worth studying in their own right. Moreover, it
is usually far more important to know how to use those structures effectively than it
is to understand their underlying representation. For example, even though a string
might be represented inside the machine as an array of characters, it also has an
abstract behavior that transcends its representation. A type defined in terms of its
behavior rather than its representation is called an abstract data type, which is often
abbreviated to ADT. Abstract data types are central to the object-oriented style of
programming, which encourages programmers to think about data structures in a
holistic way.

This chapter introduces five classesVector, Stack, Queue, Map, and Set
each of which represents an important abstract data type. Each of these classes,
moreover, contains a collection of values of some simpler type. Such classes are
therefore called collection classes. For the moment, you dont need to understand
how these classes are implemented, because your primary focus is on learning how
to use these classes as a client. In later chapters, youll have a chance to explore a
variety of implementation strategies and learn about the algorithms and data
structures necessary to make those implementations efficient.

Being able to separate the behavior of a class from its underlying

implementation is a fundamental precept of object-oriented programming. As a
design strategy, it offers the following advantages:

Simplicity. Hiding the internal representation from the client means that there
are fewer details for the client to understand.
Flexibility. Because a class is defined in terms of its public behavior, the
programmer who implements one is free to change its underlying private
representation. As with any abstraction, it is appropriate to change the
implementation as long as the interface remains the same.
Security. The interface boundary acts as a wall that protects the implementation
and the client from each other. If a client program has access to the
representation, it can change the values in the underlying data structure in
unexpected ways. Making the data private in a class prevents the client from
making such changes.
 5.1 The Vector class 197

To use any of the collection classes introduced in this chapter, you must include
the appropriate interface, just as you would for any of the libraries from the earlier
chapters. The interface for each of the collection classes is simply the name of the
class spelled with a lowercase initial letter and followed with the extension .h at the
end. For example, in order to use the Vector class in a program, you must include
the line

#include "vector.h"

The collection classes used in this book are inspired by and draw much of their
structure from a more advanced set of classes available for C++ called the
Standard Template Library, or STL for short. Although the STL is enormously
powerful, it is more difficult to understand from both the client and implementation
perspectives. The advantage of using the simplified version is that you can
understand the entire implementation by the time you finish this book. Knowing
how the implementation works gives you greater insight into what the Standard
Template Library is doing for you behind the scenes.

5.1 The Vector class

One of the most valuable collection classes is the Vector class, which provides a
facility similar to the arrays you have almost certainly encountered in your earlier
experience with programming. Arrays have been around since the early days of
programming. Like most languages, C++ supports arrays, and you will have the
chance to learn how C++ arrays work in Chapter 11. Arrays in C++, however, have
a number of weaknesses, including the following:

Arrays are allocated with a fixed size that you cant subsequently change.
Even though arrays have a fixed size, C++ does not make that size available to
the programmer. As a result, programs that work with arrays typically need an
additional variable to keep track of the number of elements.
Traditional arrays offer no support for inserting and deleting elements.
C++ makes no effort to ensure that the elements you select are actually present
in the array. For example, if you create an array with 25 elements and then try to
select the value at index position 50, C++ will simply look at the memory
addresses at which element 50 would appear if it existed.

The Vector class solves each of these problems by reimplementing the array
concept in the form of an abstract data type. You can use the Vector class in place
of arrays in any application, usually with surprisingly few changes in the source
code and at most a minor reduction in efficiency. In fact, once you have the
Vector class, its unlikely that you will have much occasion to use arrays at all,
unless you actually have to implement classes like Vector, which, not surprisingly,
198 Collections

uses arrays in its underlying structure. As a client of the Vector class, however,
you are not interested in that underlying structure and can leave the array mechanics
to the programmers who implement the abstract data type.

As a client of the Vector class, you are concerned with a different set of issues
and need to answer the following questions:

1. How is it possible to specify the type of object contained in a Vector?

2. How does one create an object that is an instance of the Vector class?
3. What methods exist in the Vector class to implement its abstract behavior?

The next three sections explore the answers to each of these questions in turn.

Specifying the base type of a Vector

In C++, collection classes specify the type of object they contain by including the
type name in angle brackets following the class name. For example, the class
Vector<int> represents a vector whose elements are integers, Vector<char>
specifies a vector whose elements are single characters, and Vector<string>
specifies one in which the elements are strings. The type enclosed within the angle
brackets is called the base type for the collection.

Classes that include a base-type specification are called parameterized classes in

the object-oriented community. In C++, parameterized classes are more often
called templates, which reflects the fact that C++ compilers treat Vector<int>,
Vector<char>, and Vector<string> as independent classes that share a
common structure. The name Vector acts as a template for stamping out a whole
family of classes, in which the only difference is what type of value the vector
contains. For now, all you need to understand is how to use templates; the process
of implementing basic templates is described in Chapter 14.

Declaring a Vector object

One of the philosophical principles behind abstract data types is that clients should
be able to think of them as if they were built-in primitive types. Thus, just as you
would declare an integer variable by writing a declaration such as

int n;

it ought to be possible to declare a new vector by writing

Vector<int> vec;
 5.1 The Vector class 199

In C++, that is precisely what you do. That declaration introduces a new variable
named vec, which isas the template marker in angle brackets indicatesa vector
of integers.

Vector operations
When you declare a Vector variable, it starts out as an empty vector, which means
that it contains no elements. Since an empty vector is not particularly useful, one
of the first things you need to learn is how to add new elements to a Vector object.
The usual approach is to invoke the add method, which adds a new element at the
end of the Vector. For example, if vec is an empty vector of integers as declared
in the preceding section, executing the code

vec.add(10);
vec.add(20);
vec.add(40);

changes vec into a three-element vector containing the values 10, 20, and 40. As
with the characters in a string, C++ numbers the elements of a vector starting with
0, which means that you could diagram the contents of vec like this:

Unlike the more primitive array type that will be introduced in Chapter 11, the
size of a vector is not fixed, which means that you can add additional elements at
any time. Later in the program, for example, you could call

vec.add(50);

which would add the value 50 to the end of the vector, like this:

The insertAt method allows you to add new elements in the middle of a
vector. The first argument to insertAt is an index number, and the new element
is inserted before that position. For example, calling

vec.insertAt(2, 30);

inserts the value 30 before index position 2, as follows:

200 Collections

Internally, the implementation of the Vector class has to expand the array storage
and move the values 40 and 50 over one position to make room for the 30. From
your perspective as a client, the implementation simply takes care of such details,
and you dont need to understand how it does so.

The Vector class also lets you remove elements. For example, calling

vec.removeAt(0);

removes the element from position 0, leaving the following values:

Once again, the implementation takes care of shifting elements to close the gap left
by the deleted value.

The Vector class includes two methods for selecting and modifying individual
elements. The get method takes an index number and returns the value in that
index position. For example, given the value of vec shown in the most recent
diagram, calling vec.get(2) would return the value 40.

Symmetrically, you can use the set method to change the value of an existing
element. For example, calling

vec.set(3, 70);

changes the value in index position 3 from 50 to 70, like this:

The get, set, insertAt, and removeAt methods all check to make sure that
the index value you supply is valid for the vector. For example, if you were to call
vec.get(4) in this vector, the get method would call error to report that the
index value 4 is too large for a vector in which the index values run from 0 to 3.
For get, set, and removeAt, the Vector implementation checks that the index is
greater than or equal to 0 and less than the number of elements. The insertAt
method allows the index to be equal to the number of elements, in which case the
new value is added at the end of the array, just as it is with add.
 5.1 The Vector class 201

The operation of testing whether an index is valid is called bounds-checking.

Bounds-checking makes it easier to catch programming errors that can often go
unnoticed when you work with traditional arrays.

Selecting elements in a vector

Even though the get and set methods are easy to use, hardly anyone actually calls
these methods. One of the characteristics of C++ that sets it apart from most other
languages is that classes can override the definition of the standard operators. This
feature makes it possible for the Vector class to support the more traditional syntax
of using square brackets to specify the desired index. Thus, to select the element at
position i, you can use the expression vec[i], just as you would with a traditional
array. You can, moreover, change the value of that element by assigning a new
value to vec[i]. For example, you can set element 3 in vec to 70 by writing

vec[3] = 70;

The resulting syntax is marginally shorter than calling set, but is more evocative of
the array operations that the Vector class is designed to emulate.

The index used to select an element from an array can be any expression that
evaluates to an integer. One of the most common index expressions is the index of
a for loop that cycles through each of the index values is order. The general
pattern for cycling through the index positions in a vector looks like this:

for (int i = 0; i < vec.size(); i++) {

loop body
}

Inside the loop body, you can refer to the current element as vec[i].

As an example, the following code writes out the contents of the vector vec as a
comma-separated list enclosed in square brackets:

cout << "[";

for (int i = 0; i < vec.size(); i++) {
if (i > 0) cout << ", ";
cout << vec[i];
}
cout << "]" << endl;

If you were to execute this code given the most recent contents of vec, you would
see the following output on the screen:
202 Collections

Passing a Vector object as a parameter

The code at the end of the preceding section is so useful (particularly when youre
debugging and need to see what values a vector contains), that it is worth defining a
function for this purpose. At one level, encapsulating the code inside a function is
easy; all you have to do is add the appropriate function header, like this:

void printVector(Vector<int> & vec) {

cout << "[";
for (int i = 0; i < vec.size(); i++) {
if (i > 0) cout << ", ";
cout << vec[i];
}
cout << "]" << endl;
}

The header line, however, involves one subtlety that you have to understand before
you can use collection classes effectively. As described in Chapter 2, the & before
the parameter name indicates that the argument vec is passed by reference, which
means that the value in the function is shared with the value in the caller.
Call-by-reference is more efficient than C++s default model of call-by-value,
which would require copying every element in the vector. In the printVector
example, there is no reason to make that copy, so call-by-reference represents a
more efficient design.

Perhaps more importantly, using call-by-reference makes it possible to write

functions that change the contents of a vector. As an example, the following
function deletes any zero-valued elements from a vector of integers:

void removeZeroElements(Vector<int> & vec) {

for (int i = vec.size() - 1; i >= 0; i--) {
if (vec[i] == 0) vec.removeAt(i);
}
}

The for loop cycles through each element and checks whether its value is 0. If so,
the function calls removeAt to delete that element from the vector. To ensure that
 5.1 The Vector class 203

removing an element doesnt change the positions of elements that have not yet
been checked, the for loop starts at the end of the vector and runs backwards.

This function depends on the use of call-by-reference. If you had left out the
ampersand in this header line, removeZeroElements would have no effect at all.
The code would remove the zero elements from the local copy of vec, but not from
the vector the caller supplied. When removeZeroElements returns, that copy
goes away, leaving the original vector unchanged. This kind of error is easy to
make, and you should learn to look for it when your programs go awry.

The ReverseFile program in Figure 5-1 shows a complete C++ program that
uses Vector to display the lines from a file in reverse order. The functions
promptUserForFile and readEntireFile will come in handy in a variety of
applications. For this reason, both of these functionsalong with many other
useful functions for working with filesare included in the filelib.h library
listed in Appendix A.

Creating a Vector of a predefined size

The examples you have seen up to this point start out with an empty vector and then
add elements to it, one at a time. In many applications, building up a vector one
element at a time is tedious, particularly if you know the size of the vector in
advance. In such cases, it makes more sense to specify the number of elements as
part of the declaration.

As an example, suppose that you wanted to create a vector to hold the scores for
each hole on an 18-hole golf course. The strategy you already know is to create an
empty Vector<int> and then add 18 elements to it using a for loop, as follows:

const int N_HOLES = 18;

Vector<int> golfScores;
for (int i = 0; i < N_HOLES; i++) {
golfScores.add(0);
}

A better approach is to include the size as a parameter to the declaration like this:

Vector<int> golfScores(N_HOLES);

This declaration creates a Vector<int> with N_HOLES elements, each of which is

initialized to 0 for a Vector of type int. The effect of these two code fragments is
the same. Each of them creates a Vector<int> filled with 18 zero values. The
first form requires the client to initialize the elements; the second hands that
responsibility off to the Vector class itself.
204 Collections

Figure 4-1
 5.1 The Vector class 205

As a more significant example of when you might want to declare a vector of a

constant size, consider the LetterFrequency program in Figure 5-2, which counts
how often each of the 26 letters appears in a data file. Those counts are maintained
in the variable letterCounts, which is declared as follows:

Vector<int> letterCounts(26);

Each element in this vector contains the count of the letter at the corresponding
index in the alphabet, with the number of As in letterCounts[0], the number of
Bs in letterCounts[1], and so on. For each letter in the file, all the program has
to do is increment the value at the appropriate index position in the vector, which
206 Collections

can be calculated arithmetically based on the ASCII code of the character. This
calculation occurs in the statement

letterCounts[toupper(ch) - 'A']++;

Subtracting the ASCII value 'A' from the uppercase character code gives the index
of the character ch in the alphabet. This statement then updates the count by
incrementing that element of the vector.

The remainder of the program is mostly concerned with formatting the output so
that the letter counts are properly aligned in columns. As an example, here is what
the LetterCounts program produces if you run it on a file containing the text of
George Eliots Middlemarch:

Constructors for the Vector class

The sample programs youve seen so far in this chapter declare vectors in two
different ways. The ReverseFile program in Figure 5-1 defines an empty vector
of strings using the declaration

Vector<string> lines;

The LetterFrequency program declares a vector containing 26 zeroes like this:

 5.1 The Vector class 207

Vector<int> letterCounts(26);

As it happens, there is more going on in these declarations than meets the eye.
When you declare a variable of a primitive type, as in

double total;

C++ does not make any attempt to initialize that variable. The contents of the
memory used to hold the variable total continue to contain whatever value
happened to be there, which can easily lead to unexpected results. For this reason,
declarations of primitive variables usually include an explicit initializer that sets the
variable to the desired starting value, as in

double total = 0.0;

The situation is different when you declare a variable to be an instance of a C++

class. In that case, C++ automatically initializes that variable by invoking a special
method called a constructor. For example, in the declaration

Vector<string> lines;

C++ calls the Vector constructor, which initializes the variable lines to be an
empty vector that belongs to the parameterized class Vector<string>. The
declaration

Vector<int> letterCounts(26);

calls a different version of the constructor to initialize a Vector<int> with 26

elements.

The C++ compiler determines which version of the constructor to call by looking
at the arguments appearing in the declaration, just as it does for overloaded
functions. The declaration of lines provides no arguments, which tells the
compiler to invoke the constructor that takes no arguments, which is called the
default constructor. The declaration of letterCounts provides an integer
argument, which tells the compiler to invoke the version of the constructor that
takes an integer indicating the vector size. The two versions of the Vector
constructor appearalong with a complete list of the Vector methodsin
Table 5-1.

If you look closely at the constructor descriptions in Table 5-1, youll discover
that the second form of the constructor accepts an optional argument indicating the
initial value to use for each of the elements. That argument is usually omitted, in
which case, the initial value for the elements is the default value for the base type,
208 Collections

which is 0 for numeric types, false for type bool, the character whose ASCII
value is 0 for type char, and the result of calling the default constructor for a class.

Vector operators
Partly to illustrate the power of operator overloading and partly because these
operators turn out to be so useful, the Vector class in the Stanford library defines
several operators that apply to vector objects. You have already seen the use of
square brackets, which make it possible to select objects from a vector using the
traditional selection syntax for arrays. The Vector class also defines the operators
+ and += as shorthands for concatenating two vectors and for adding elements to an
existing vector.
 5.1 The Vector class 209

The + operator on vectors is defined so that it works in exactly the way it does
for strings. If the character vectors v1 and v2 contain the values

and

evaluating the expression v1 + v2 creates a new five-element vector, as follows:

The += operator adds elements to the end of an existing vector, but is also useful
if you need to initialize the contents of a vector. For example, you can declare and
initialize the vector v1 like this:

Vector<char> v1;
v1 += 'A', 'B', 'C';

If you are using C++11, which is the new C++ standard released in 2011, you can
simplify this initialization, as follows:

Vector<char> v1 = { 'A', 'B', 'C' };

Representing two-dimensional structures

The type parameter used in the Vector class can be any C++ type and may itself be
a parameterized type. In particular, you can create a two-dimensional structure by
declaring a Vector whose base type is itself a Vector. The declaration

Vector< Vector<int> > sudoku(9, Vector<int>(9));

initializes the variable sudoku to a Vector of nine elements, each of which is itself
a Vector of nine elements. The base type of the inner vector is int, and the base
type of the outer vector is Vector<int>. The type of the whole assemblage is
therefore

Vector< Vector<int> >

210 Collections

Although some C++ compilers have been extended so that the spaces are optional,
this declaration adheres to the C++ standard by including spaces around the inner
type parameter. Those spaces ensure that the angle brackets for the type parameters
are interpreted correctly. If you instead write this declaration as

Vector<Vector<int>> sudoku(9, Vector<int>(9));

many C++ compilers will interpret the >> as a single operator and be unable to
compile this line.

The Grid class in the Stanford libraries

Although using nested vectors makes it possible to represent two-dimensional
structures, that strategy is by no means convenient. To simplify the development of
applications that need to work with two-dimensional structures, the Stanford version
of the collection class library includes a class called Grid, even though there is no
direct counterpart for this class in the Standard Template Library. The entries
exported by grid.h appear in Table 5-2.
 5.2 The Stack class 211

5.2 The Stack class

When measured in terms of the operations it supports, the simplest collection class
is the Stack class, whichdespite its simplicityturns out to be useful in a variety
of programming applications. Conceptually, a stack provides storage for a
collection of data values, subject to the restriction that values must be removed from
a stack in the opposite order from which they were added. This restriction implies
that the last item added to a stack is always the first item that gets removed.

In light of their importance in computer science, stacks have a terminology of

their own. Adding a new value to a stack is called pushing that value; removing the
most recent item from a stack is called popping the stack. Moreover, the order in
which stacks are processed is sometimes called LIFO, which stands for last in,
first out.

A common (but possibly apocryphal) explanation for the words stack, push, and
pop is that the stack model is derived from the way plates are stored in a cafeteria.
Particularly, if you are in a cafeteria in which customers pick up their own plates at
the beginning of a buffet line, those plates are placed in spring-loaded columns that
make it easy for people in the cafeteria line to take the top plate, as illustrated in the
following diagram:

When a dishwasher adds a new plate, it goes on the top of the stack, pushing the
others down slightly as the spring is compressed, as shown:

Customers can take plates only from the top of the stack. When they do, the
remaining plates pop back up. The last plate added to the stack is the first one a
customer takes.

The primary reason that stacks are important in programming is that nested
function calls behave in a stack-oriented fashion. For example, if the main program
calls a function named f, a stack frame for f gets pushed on top of the stack frame
for main, as illustrated by the following diagram:
212 Collections

If f calls g, a new stack frame for g is pushed on top of the frame for f, as follows:

When g returns, its frame is popped off the stack, restoring f to the top of the stack
as shown in the original diagram.

The structure of the Stack class

Like Vector and Grid, Stack is a collection class that requires you to specify the
element type. For example, Stack<int> represents a stack whose elements are
integers, and Stack<string> represents one in which the elements are strings.
Similarly, if you define the classes Plate and Frame, you can create stacks of these
objects using the classes Stack<Plate> and Stack<Frame>. The list of entries
exported by the stack.h interface appears in Table 5-3.
 5.2 The Stack class 213

Stacks and pocket calculators

One interesting application of stacks is in electronic calculators, where they are used
to store intermediate results of a calculation. Although stacks play a central role in
the operation of most calculators, that role is easiest to see in early scientific
calculators that required users to enter expressions in Reverse Polish Notation, or
RPN.

In Reverse Polish Notation, operators are entered after the operands to which
they apply. For example, to compute the result of the expression

8.5 * 4.4 + 6.9 / 1.5

on an RPN calculator, you would enter the operations in the following order:

When the ENTER button is pressed, the calculator takes the previous value and
pushes it on a stack. When an operator button is pressed, the calculator first checks
whether the user has just entered a value and, if so, automatically pushes it on the
stack. It then computes the result of applying the operator by

Popping the top two values from the stack

Applying the arithmetic operation indicated by the button to these values
Pushing the result back on the stack

Except when the user is actually typing in a number, the calculator display shows
the value at the top of the stack. Thus, at each point in the operation, the calculator
display and stack contain the values shown in Figure 5-3.
214 Collections

Implementing the RPN calculator in C++ requires making some changes in the
user-interface design. In a real calculator, the digits and operations appear on a
keypad. In this implementation, it is easier to imagine that the user enters lines on
the console, where those lines take one of the following forms:

A floating-point number
An arithmetic operator chosen from the set +, -, *, and /
The letter Q, which causes the program to quit
The letter H, which prints a help message
The letter C, which clears any values left on the stack

A sample run of the calculator program might therefore look like this:

Because the user enters each number on a separate line terminated with the RETURN
key, there is no need for any counterpart to the calculators ENTER button, which
really serves only to indicate that a number is complete. The calculator program
can simply push the numbers on the stack as the user enters them. When the
calculator reads an operator, it pops the top two elements from the stack, applies the
operator, displays the result, and then pushes the result back on the stack.

The complete implementation of the calculator application appears in Figure 5-4.

 5.2 The Stack class 215

Figure 4-4
216 Collections

Figure 4-4
 5.3 The Queue class 217

5.3 The Queue class

As you learned in section 5.2, the defining feature of a stack is that the last item
pushed is always the first item popped. As noted in the introduction to that section,
this behavior is often referred to in computer science as LIFO, which is an acronym
for the phrase last in, first out. The LIFO discipline is useful in programming
contexts because it reflects the operation of function calls; the most recently called
function is the first to return. In real-world situations, however, its usefulness is
more limited. In human society, our collective notion of fairness assigns some
priority to being first, as expressed in the maxim first come, first served. In
programming, the usual phrasing of this ordering strategy is first in, first out,
which is traditionally abbreviated as FIFO.

A data structure that stores items using a FIFO discipline is called a queue. The
fundamental operations on a queuewhich are analogous to the push and pop
operations for stacksare called enqueue and dequeue. The enqueue operation
adds a new element to the end of the queue, which is traditionally called its tail.
The dequeue operation removes the element at the beginning of the queue, which
is called its head.

The conceptual difference between these structures can be illustrated most easily
with a diagram. In a stack, the client must add and remove elements from the same
end of the internal data structure, as follows:

In a queue, the client adds elements at one end and removes them from the other,
like this:

As you might expect from the fact that the models are so similar, the structure of
the Queue class looks very much like its Stack counterpart. The list of entries in
Table 5-4 bears out that supposition. The only differences are in the terminology,
which reflects the difference in the ordering of the elements.
218 Collections

The queue data structure has many applications in programming. Not

surprisingly, queues turn up in many situations in which it is important to maintain a
first-in/first-out discipline in order to ensure that service requests are treated fairly.
For example, if you are working in an environment in which a single printer is
shared among several computers, the printing software is usually designed so that
all print requests are entered in a queue. Thus, if several users decide to enter print
requests, the queue structure ensures that each users request is processed in the
order received.

Queues are also common in programs that simulate the behavior of waiting lines.
For example, if you wanted to decide how many cashiers you needed in a
supermarket, it might be worth writing a program that could simulate the behavior
of customers in the store. Such a program would almost certainly involve queues,
because a checkout line operates in a first-in/first-out way. Customers who have
completed their purchases arrive in the checkout line and wait for their turn to pay.
Each customer eventually reaches the front of the line, at which point the cashier
totals up the purchases and collects the money. Because simulations of this sort
represent an important class of application programs, it is worth spending a little
time understanding how such simulations work.

Simulations and models

Beyond the world of programming, there are an endless variety of real-world events
and processes thatalthough they are undeniably importantare nonetheless too
complicated to understand completely. For example, it would be very useful to
know how various pollutants affect the ozone layer and how the resulting changes
 5.3 The Queue class 219

in the ozone layer affect the global climate. Similarly, if economists and political
leaders had a more complete understanding of exactly how the national economy
works, it would be possible to evaluate whether a cut in the capital-gains tax would
spur investment or whether it would exacerbate the existing disparities of wealth
and income.

When faced with such large-scale problems, it is usually necessary to come up

with an idealized model, which is a simplified representation of some real-world
process. Most problems are far too complex to allow for a complete understanding.
There are just too many details. The reason to build a model is that, despite the
complexity of a particular problem, it is often possible to make certain assumptions
that allow you to simplify a complicated process without affecting its fundamental
character. If you can come up with a reasonable model for a process, you can often
translate the dynamics of the model into a program that captures the behavior of that
model. Such a program is called a simulation.

It is important to remember that creating a simulation is usually a two-step

process. The first step consists of designing a conceptual model for the real-world
behavior you are trying to simulate. The second consists of writing a program that
implements the conceptual model. Because errors can occur in both steps of the
process, maintaining a certain skepticism about simulations and their applicability
to the real world is probably wise. In a society conditioned to believe the answers
delivered by computers, it is critical to recognize that the simulations can never be
better than the models on which they are based.

The waiting-line model

Suppose that you want to design a simulation that models the behavior of a
supermarket waiting line. By simulating the waiting line, you can determine some
useful properties of waiting lines that might help a company make such decisions as
how many cashiers are needed, how much space needs to be reserved for the line
itself, and so forth.

The first step in the process of writing a checkout-line simulation is to develop a

model for the waiting line, detailing the simplifying assumptions. For example, to
make the initial implementation of the simulation as simple as possible, you might
begin by assuming that there is one cashier who serves customers from a single
queue. You might then assume that customers arrive with a random probability and
enter the queue at the end of the line. Whenever the cashier is free and someone is
waiting in line, the cashier begins to serve that customer. After an appropriate
service periodwhich you must also model in some waythe cashier completes
the transaction with the current customer, and is free to serve the next customer in
the queue.
220 Collections

Discrete time
Another assumption often required in a model is some limitation on the level of
accuracy. Consider, for example, the time that a customer spends being served by
the cashier. One customer might spend two minutes; another might spend six. It is
important, however, to consider whether measuring time in minutes allows the
simulation to be sufficiently precise. If you had a sufficiently accurate stopwatch,
you might discover that a customer actually spent 3.14159265 minutes. The
question you need to resolve is how accurate you need to be.

For most models, and particularly for those intended for simulation, it is useful
to introduce the simplifying assumption that all events within the model happen in
discrete integral time units. Using discrete time assumes that you can find a time
unit thatfor the purpose of the modelyou can treat as indivisible. In general,
the time units used in a simulation must be small enough that the probability of
more than one event occurring during a single time unit is negligible. In the
checkout-line simulation, for example, minutes may not be accurate enough; two
customers could easily arrive in the same minute. On the other hand, you could
probably get away with using seconds as the time unit and discount the possibility
that two customers arrive in precisely the same second.

Although the checkout-line example assumes that simulation time is measured in

seconds, in general, there is no reason you have to measure time in conventional
units. When you write a simulation, you can define the unit of time in any way that
fits the structure of the model. For example, you could define a time unit to be five
seconds and then run the simulation as a series of five-second intervals.

Events in simulated time

The real advantage of using discrete time units is not that it makes it possible to
work with variables of type int instead of being forced to use type double. The
most important property of discrete time is that it allows you to structure the
simulation as a loop in which each time unit represents a single cycle. When you
approach the problem in this way, a simulation program has the following form:

for (int time = 0; time < SIMULATION_TIME; time++) {

Execute one cycle of the simulation.
}

Within the body of the loop, the program performs the operations necessary to
advance through one unit of simulated time.

Think for a moment about what events might occur during each time unit of the
checkout-line simulation. One possibility is that a new customer might arrive.
Another is that the cashier might finish with the current customer and go on the
 5.3 The Queue class 221

serve the next person in line. These events bring up some interesting issues. To
complete the model, you need to say something about how often customers arrive
and how much time they spend at the cash register. You could (and probably
should) gather approximate data by watching a real checkout line in a store. Even if
you collect that information, however, you will need to simplify it to a form that (1)
captures enough of the real-world behavior to be useful and (2) is easy to
understand in terms of the model. For example, your surveys might show that
customers arrive at the line on average once every 20 seconds. This average arrival
rate is certainly useful input to the model. On the other hand, you would not have
much confidence in a simulation in which customers arrived exactly once every 20
seconds. Such an implementation would violate the real-world condition that
customer arrivals have some random variability and that they sometimes bunch
together.

For this reason, the arrival process is usually modeled by specifying the
probability that an arrival takes place in any discrete time unit instead of the average
time between arrivals. For example, if your studies indicated that a customer
arrived once every 20 seconds, the average probability of a customer arriving in any
particular second would be 1/20 or 0.05. If you assume that arrivals occur randomly
with an equal probability in each unit of time, the arrival process forms a pattern
that mathematicians call a Poisson distribution.

You might also choose to make simplifying assumptions about how long it takes
to serve a particular customer. For example, the program is easier to write if you
assume that the service time required for each customer is uniformly distributed
within a certain range. If you do, you can use the randomInteger function from
the random.h interface to pick the service time.

Implementing the simulation

Even though it is longer than the other programs in this chapter, the code for the
simulation program is reasonably easy to write and appears in Figure 5-5. The core
of the simulation is a loop that runs for the number of seconds indicated by the
parameter SIMULATION_TIME. In each second, the simulation performs the
following operations:

1. Determine whether a new customer has arrived and, if so, add that person to the
queue.
2. If the cashier is busy, note that the cashier has spent another second with the
current customer. Eventually, the required service time will be complete,
which will free the cashier.
3. If the cashier is free, serve the next customer in the waiting line.
222 Collections

Figure 4-5
 5.3 The Queue class 223

Figure 4-5
224 Collections

The waiting line itself is represented, naturally enough, as a queue. The value
stored in the queue is the time at which that customer arrived in the queue, which
makes it possible to determine how many seconds that customer spent in line before
reaching the head of the queue.

The simulation is controlled by the following constants:

SIMULATION_TIMEThis constant specifies the duration of the simulation.

ARRIVAL_PROBABILITYThis constant indicates the probability that a new
customer will arrive at the checkout line during a single unit of time. In keeping
with standard statistical convention, the probability is expressed as a real number
between 0 and 1.
MIN_SERVICE_TIME, MAX_SERVICE_TIMEThese constants define the legal
range of customer service time. For any particular customer, the amount of time
spent at the cashier is determined by picking a random integer in this range.
 5.3 The Queue class 225

When the simulation is complete, the program reports the simulation constants
along with the following results:

The number of customers served

The average amount of time customers spent in the waiting line
The average length of the waiting line

For example, the following sample run shows the results of the simulation for the
indicated constant values:

The behavior of the simulation depends significantly on the values of the

constants used to control it. Suppose, for example, that the probability of a
customer arriving increases from 0.05 to 0.10. Running the simulation with these
parameters gives the following results:

As you can see, doubling the probability of arrival causes the average waiting
time to grow from under nine seconds to more than a minute, which is obviously a
dramatic increase. The reason for the poor performance is that the arrival rate in the
second run of the simulation means that new customers arrive at the same rate at
which they are served. When this arrival level is reached, the length of the queue
and the average waiting time both begin to grow very quickly. Simulations of this
sort make it possible to experiment with different parameter values. Those
experiments, in turn, make it possible to identify potential sources of trouble in the
corresponding real-world systems.
226 Collections

5.4 The Map class

This section introduces another generic collection called a map, which is
conceptually similar to a dictionary. A dictionary allows you to look up a word to
find its meaning. A map is a generalization of this idea that provides an association
between an identifying tag called a key and an associated value, which may be a
much larger and more complicated structure. In the dictionary example, the key is
the word youre looking up, and the value is its definition.

Maps have many applications in programming. For example, an interpreter for a

programming language needs to be able to assign values to variables, which can
then be referenced by name. A map makes it easy to maintain the association
between the name of a variable and its corresponding value. When they are used in
this context, maps are often called symbol tables, which is just another name for the
same concept.

In addition to the Map class described in this section, the Stanford libraries offer
a HashMap class that has almost the same structure and behavior. The HashMap
class is more efficient but somewhat less convenient to use for certain applications.
For now, its best to focus on the Map class until you understand how maps work in
general. Youll have a chance to learn about the differences between these two
implementations of the map concept in Chapters 15 and 16.

The structure of the Map class

As with the collection classes introduced earlier in this chapter, Map is implemented
as a template class that must be parameterized with both the key type and the value
type. For example, if you want to simulate a dictionary in which individual words
are associated with their definitions, you can start by declaring a dictionary
variable as follows:

Map<string,string> dictionary;

Similarly, if you are implementing a programming language, you could use a Map to
store the values of floating-point variables by associating variable names and
values, as follows:

Map<string,double> symbolTable;

These definitions create empty maps that contain no keys and values. In either
case, you would subsequently need to add key/value pairs to the map. In the case of
the dictionary, you could read the contents from a data file. For the symbol table,
you would add new associations whenever an assignment statement appeared.
 5.4 The Map class 227

The most common methods used with the Map class appear in Table 5-5. Of
these, the ones that implement the fundamental behavior of the map concept are put
and get. The put method creates an association between a key and a value. Its
operation is analogous to assigning a value to a variable in C++: if there is a value
already associated with the key, the old value is replaced by the new one. The get
method retrieves the value most recently associated with a particular key and
therefore corresponds to the act of using a variable name to retrieve its value. If no
value appears in the map for a particular key, calling get with that key returns the
default value for the value type. You can check whether a key exists in a map by
calling the containsKey method, which returns true or false depending on
whether the specified key has been defined.

A few simple diagrams may help to illustrate the operation of the Map class in
more detail. Suppose that you have declared the symbolTable variable to be a
Map<string,double> as you saw earlier in the section. That declaration creates
228 Collections

an empty map with no associations, as represented by the following diagram that

contains an empty set of bindings:

Once you have the map, you can use put to establish new associations. For
example, if you call

symbolTable.put("pi", 3.14159);

the conceptual effect is to add an association between the key "pi" and the value
3.14159, as follows:

Calling

symbolTable.put("e", 2.71828);

would add a new association between the key "e" and the value 2.71828, like this:

You can then use get to retrieve these values. Calling symbolTable.get("pi")
would return the value 3.14159, and calling symbolTable.get("e") would
return 2.71828.

Although it hardly makes sense in the case of mathematical constants, you could
change the values in the map by making additional calls to put. You could, for
example, reset the value associated with "pi" (as an 1897 bill before the Indiana
State General Assembly sought to do) by calling

symbolTable.put("pi", 3.0);

which would leave the map in the following state:

At this point, calling symbolTable.containsKey("pi") would return true; by

contrast, calling symbolTable.containsKey("x") would return false.
 5.4 The Map class 229

Using maps in an application

If you fly at all frequently, you quickly learn that every airport in the world has a
three-letter code assigned by the International Air Transport Association (IATA).
For example, John F. Kennedy airport in New York City is assigned the three-letter
code JFK. Other codes, however, are considerably harder to recognize. Most
web-based travel systems offer some means of looking up these codes as a service
to their customers.

Suppose that you have been asked to write a simple C++ program that reads a
three-letter airport code from the user and responds with the location of that airport.
The data you need is in the form of a text file called AirportCodes.txt, which
contains a list of the several thousand airport codes that IATA has assigned. Each
line of the file consists of a three-letter code, an equal sign, and the location of the
airport. If the file were sorted in descending order by passenger traffic in 2009, as
compiled by Airports Council International, the file would begin with the lines in
Figure 5-6.

The existence of the Map class makes this application extremely easy to write.
The entire application fits on a single page, as shown in Figure 5-7.
230 Collections

Figure 4-7
 5.4 The Map class 231

The main program in the AirportCodes application reads in three-letter codes,

looks up the corresponding location, and writes that back to the console, as shown
in the following sample run:

Maps as associative arrays

The Map class overloads the square bracket operators used for array selection so that
the statement

map[key] = value;

acts as a shorthand for

map.put(key, value);

Similarly, the expression map[key] returns the value from map associated with key
in exactly the same way that map.get(key) does. While these shorthand forms of
the put and get methods are undoubtedly convenient, using array notation for
maps is initially surprising, given that maps and arrays seem to be entirely different
in their structure. If you think about maps and arrays in the right way, however,
they turn out to be more alike than you might at first suspect.

The insight necessary to unify these two seemingly different structures is that
you can think of arrays as structures that map index positions to elements. Suppose,
for example, that you have an arrayor equivalently a vectorcontaining a set of
scores such as those you might assign for a gymnastics match:

This array maps the key 0 into the value 9.2, the key 1 into 9.9, the key 2 into 9.7,
and so forth. Thus, you can think of an array as simply a map with integer keys.
Conversely, you can think of a map as an array that uses the key type as its indices,
which is precisely what the overloaded selection syntax for the Map class suggests.
232 Collections

Using array syntax to perform map operations is becoming increasingly common

in programming languages even beyond the C++ domain. Many popular scripting
languages implement all arrays internally as maps, making it possible to use index
values that are not necessarily integers. Arrays implemented using maps as their
underlying representation are called associative arrays.

5.5 The Set class

One of the most useful collection classes is the Set class, which exports the entries
shown in Table 5-6. This class is used to model the mathematical abstraction of a
set, which is a collection in which the elements are unordered and in which each
value appears only once. Sets turn out to be extremely useful in many algorithmic
 5.5 The Set class 233

applications and are therefore worth a chapter of their own. Even before you have a
chance to read the more detailed account in Chapter 18, it is worth presenting a few
examples of sets so you can get a better sense of how they work and how they might
be useful in applications.

Implementing the <cctype> library

In Chapter 3, you learned about the <cctype> library, which exports several
predicate functions that test the type of a character. Calling isdigit(ch), for
example, tests whether the character ch is one of the digit characters. In that case,
you can implement the function by testing the character code for ch against a
simple range of values, as follows:

bool isdigit(ch) {
return ch >= '0' && ch <= '9';
}

The situation gets a little more complicated with some of the other functions.
Implementing ispunct in this same style would be more difficult because the
punctuation characters are spread over several intervals of the ASCII range. Things
would be a lot easier if you could simply define a set of all the punctuation marks,
in which case all you need to do to implement ispunct(ch) is check whether the
character ch is in that set.

A set-based implementation of the predicate functions from <cctype> appears

in Figure 5-8. The code creates a Set<char> for each of the character types and
then defines the predicate functions so that they simply invoke contains on the
appropriate set. For example, to implement isdigit, the cctype implementation
defines a set containing the digit characters like this:

const Set<char> DIGIT_SET = setFromString("0123456789");

The setFromString function, which appears at the bottom of Figure 5-8, is a

simple helper function that creates a set by adding each of the characters in the
argument string. This function makes it very easy to define sets like the set of
punctuation characters simply by listing the characters that fit that description.

One of the advantages of working with sets is that doing so makes it easier to
think in terms of abstract, high-level operations. While most of the sets in
cctype.cpp use setFromString to create the set from the actual characters, a
few use the + operator, which is overloaded to return the union of two sets. For
example, once you have defined the sets LOWER_SET and UPPER_SET so that they
contain the lowercase and uppercase letters, you can define ALPHA_SET by writing

const Set<char> ALPHA_SET = LOWER_SET + UPPER_SET;

234 Collections

Figure 4-8
 5.5 The Set class 235

Creating a word list

In the discussion of the Map class earlier in the chapter, one of the examples used to
explain the underlying concept was that of a dictionary in which the keys were
individual words and the corresponding values were the definitions. In some
applications, such as a spelling checker or a program that plays Scrabble, you dont
need to know the definition of a word. All you need to know is whether a particular
combination of letters is a legal word. For such applications, the Set class is an
ideal tool. Instead of a map containing both words and definitions, all you need is a
Set<string> whose elements are the legal words. A word is legal if it is
contained in the set, and illegal if it is not.

A set of words with no associated definitions is called a lexicon. If you have a

text file named EnglishWords.txt containing all the words in English, one word
per line, you could create an English lexicon using the following code:

Set<string> lexicon;
ifstream infile;
infile.open("EnglishWords.txt");
if (infile.fail()) error("Can't open EnglishWords.txt");
string word;
while (getline(infile, word)) {
lexicon.add(word);
}
infile.close();

The Lexicon class in the Stanford libraries

Although the Set class works reasonably well as the underlying representation for a
lexicon, it is not particularly efficient. Because having an efficient representation
for lexicons opens up many exciting possibilities for programming projects, the
Stanford libraries include a Lexicon class, which is essentially a specialized
version of Set optimized for storing sets of words. The entries exported by the
Lexicon class appear in Table 5-7. As you can see, these entries are largely the
same as those for Set.

The library distribution also includes a data file called EnglishWords.dat that
contains a compiled representation of a lexicon containing a reasonably complete
list of English words. Programs that use the English lexicon conventionally
initialize it using the declaration

Lexicon english("EnglishWords.dat");

In word games like Scrabble, it is useful to memorize as many two-letter words

as you can, because knowing the two-letter words makes it easier to attach new
236 Collections

words to the existing words on the board. Given that you have a lexicon containing
English words, you could create such a list by generating all two-letter strings and
then using the lexicon to check which of the resulting combinations are actually
words. The code to do so appears in Figure 5-9.

As you will discover in the following section, it is also possible to solve this
problem by going through the lexicon and printing out the words whose length is
two. Given that there are more than 100,000 English words in the lexicon and only
676 (26 ! 26) combinations of two letters, the strategy used in Figure 5-9 is
probably more efficient.

5.6 Iterating over a collection

The TwoLetterWords program introduced in Figure 5-9 produces a list of the
two-letter words by generating every possible combination of two letters and then
looking up each one to see whether that two-letter string appears in the lexicon of
English words. Another strategy that accomplishes the same result is to go through
every word in the lexicon and display the words whose length is equal to 2. To do
so, all you need is some way of stepping through each word in a Lexicon object,
one word at a time.
 Summary 237

Iterating through the elements is a fundamental operation for any collection

class. Moreover, if the package of collection classes is well designed, clients should
be able to use the same strategy to perform that operation, no matter whether they
are cycling through all elements in a vector or a grid, all keys in a map, or all words
in a lexicon. The Standard Template Library offers a powerful mechanism called an
iterator for doing just that. Unfortunately, understanding these standard iterators
depends on a high level of familiarity with the low-level details of C++, most
notably the concept of pointers. Given that one of the goals of this text is to defer
covering those details until you understand the high-level ideas, introducing
standard iterators has the effect of dragging in a large amount of complexity to
achieve a goal that is in fact quite simple. All you really need is some way to
express the algorithmic idea suggested by the following pseudocode:

For each element in a particular collection {

Process that element
}

Most modern languages define a syntactic form that expresses precisely that
idea. Unfortunately, the syntax of C++ does not yet include such a facility,
although one has been proposed for a future release. The good news, however, is
that it is possible to use the macro-definition capabilities of the C++ preprocessor to
238 Collections

achieve exactly what you would like to see in the language. Although the
implementation is beyond the scope of this text, the collection classesboth those
in the Standard Template Library and the simplified versions used in this text
support a new control pattern called a range-based for loop that has the following
form:

for (type variable : collection) {

body of the loop
}

For example, if you want to iterate through all the words in the English lexicon and
select only those containing two letters, you could write

for (string word : english) {

if (word.length() == 2) {
cout << word << endl;
}
}

The range-based for loop is a new feature of C++11, which is the new C++
standard released in 2011. Because this standard is so recent, the C++11 extensions
have not yet been incorporated into all C++ programming, including several of the
leading ones. If you are working with an older compiler, you wont be able to use
the range-based for loop in its standard form. But dont despair. The Stanford
C++ libraries include an interface called foreach.h that uses the C++ preprocessor
to define a foreach macro with a very similar form:

foreach (type variable in collection) {

body of the loop
}

The only differences are the name of the keyword and the use of the keyword in
rather than a colon. Like the range-based for loop, foreach works with the
collection classes in both the Stanford and STL implementations.

Iteration order
When you use the range-based for loop, it is sometimes useful to understand the
order in which it processes the individual values. There is no universal rule. Each
collection class defines its own policy about iteration order, usually based on
considerations of efficiency. The classes youve already seen make the following
guarantees about the order of values:

When you iterate through the elements of the Vector class, the range-based for
loop delivers the elements in order by index position, so that the element in
position 0 comes first, followed by the element in position 1, and so on, up to the
 Summary 239

end of the vector. The iteration order is therefore the same as that produced by
the traditional for loop pattern:

for (int i = 0; i < vec.size(); i++) {

code to process vec[i]
}

When you iterate through the elements of the Grid class, the range-based for
loop begins by cycling through the elements of row 0 in order, then the elements
of row 1, and so forth. This iteration strategy for Grid is thus analogous to
using the following for loop:
for (int row = 0; row < grid.numRows(); row++) {
for (int col = 0; col < grid.numCols(); col++) {
code to process grid[row][col]
}
}

This order, in which the row subscript appears in the outer loop, is called
row-major order.
When you iterate through the elements of the Map class, the range-based for
loop returns the keys in the natural order for the key type. For example, a Map
whose keys are integers will process the keys in ascending numerical order. A
Map whose keys are strings will process the keys in lexicographic order, which
is the order determined by comparing the underlying ASCII codes.
When you iterate through the elements of a Set or a Lexicon, the range-based
for loop always returns the elements in the natural order for the value type. In
the Lexicon class, the range-based for loop returns the words in lower case.
You cannot use the range-based for loop in conjunction with the Stack and
Queue classes. Allowing unrestricted access to these structures would violate
the principle that only one element (the element at the top of a stack or the one at
the head of a queue) is visible at a particular time.

Pig Latin revisited

When you convert English to Pig Latin as described in section 3.2, most words turn
into something that sounds vaguely Latinate but certainly distinct from conventional
English. There are, however, a few words whose Pig Latin equivalents just happen
to be English words. For example, the Pig Latin translation of trash is ashtray, and
the translation for entry is entryway. Such words are not all that common; in the
lexicon stored in EnglishWords.dat, there are only 27 words with that property
out of over 100,000 English words. Given the range-based for loop and the
translateWord function from the PigLatin program from Chapter 3, it is easy
to write a program that lists all such words, as shown in Figure 5-10.
240 Collections

Computing word frequencies

The WordFrequency program in Figure 5-11 is another application in which
iteration plays an important role. Given the tools you have at your disposal from
earlier examples, the necessary code is quite straightforward. The strategy for
dividing a line into words is similar to what you have already seen in the PigLatin
program from Chapter 3. To keep track of the mapping between words and their
associated counts, a Map<string,int> is precisely what you need.
 Summary 241

Figure 4-11, page 2

242 Collections

Computing word frequencies turns out to be useful for applications in which the
use of such modern tools might at first seem surprising. Over the last few decades,
for example, computer analysis has become central to resolving questions of
disputed authorship. There are several plays from the Elizabethan era that might
have been written by Shakespeare, even though they are not part of the traditional
canon. Conversely, several Shakespearean plays that are attributed to Shakespeare
have parts that dont sound like his other works and may have in fact been written
by someone else. To resolve such questions, Shakespearean scholars often compute
the frequency of particular words that appear in the text and see whether those
frequencies match what we expect to find based on an analysis of Shakespeares
known works.
 Summary 243

Suppose, for example, that you have a text file containing a passage from
Shakespeare, such as the following well-known lines from Act 5 of Macbeth:

If you are trying to determine the relative frequency of words in Shakespeares

writing, you can use the WordFrequency program to count how many times each
word appears in the data file. Thus, given the file Macbeth.txt, you would like
your program to produce something like the following output:

Summary
This chapter introduced the C++ classes Vector, Stack, Queue, Map, and Set that
together represent a powerful framework for storing collections. For the moment,
you have looked at these classes only as a client. In subsequent chapters, you will
have a chance to learn more about how they are implemented. Given that you will
be implementing them as you complete the text, the classes presented here have
been simplified to some extent from the vector, stack, queue, map, and set
classes in the Standard Template Library, although they export a very similar
collection of methods. The differences are noted in Appendix B.

Important points in this chapter include:

Data structures defined in terms of their behavior rather their representation are
called abstract data types. Abstract data types have several important
advantages over more primitive data structures. These advantages include
simplicity, flexibility, and security.
Classes that contain other objects as elements of an integral collection are called
collection classes. In C++, collection classes are defined using a template or
parameterized type, in which the type name of the element appears in angle
244 Collections

brackets after the name of the collection class. For example, the class
Vector<int> signifies a vector containing values of type int.
The Vector class is an abstract data type that behaves in much the same fashion
as a one-dimensional array but is much more powerful. Unlike arrays, a Vector
can grow dynamically as elements are added and removed. They are also more
secure, because the Vector class checks to make sure that selected elements
exist. Although you can use vectors of vectors to create two-dimensional
structures, it is often easier to use the Grid class in the Stanford libraries.
The Stack class represents a collection of objects whose behavior is defined by
the property that items are removed from a stack in the opposite order from
which they were added: last in, first out (LIFO). The fundamental operations on
a stack are push, which adds a value to the stack, and pop, which removes and
returns the value most recently pushed.
The Queue class is similar to the Stack class except for the fact that elements
are removed from a queue in the same order in which they were added: first in,
first out (FIFO). The fundamental operations on a queue are enqueue, which
adds a value to the end of a queue, and dequeue, which removes and returns the
value from the front.
The Map class makes it possible to associate keys with values in a way that
makes it possible to retrieve those associations efficiently. The fundamental
operations on a map are put, which adds a key/value pair, and get, which
returns the value associated with a particular key.
The Set class represents a collection in which the elements are unordered and in
which each value appears only once, as with sets in mathematics. The
fundamental operations on a set include add, which stores a new element in the
set and contains, which checks to see whether an element is in the set.
With the exception of Stack and Queue, all collection classes support the the
range-based for loop pattern, which makes it easy to cycle through the elements
of the collection. Each collection defines its own iteration order, as described in
the section on Iteration order on page 238.
In addition to the Map and Set classes, the Stanford libraries export the closely
related classes HashMap and HashSet. The only difference between Map and
HashMap (or between Set and HashSet) is the order in which the range-based
for loop iterates through the elements. The Map and Set classes step through
the elements in increasing order as defined by the value type. The HashMap and
HashSet classes are more efficient, but step through elements in a seemingly
random order.
 Review questions 245

Review questions
1. True or false: An abstract data type is one defined in terms of its behavior
rather than its representation.

2. What three advantages does this chapter cite for separating the behavior of a
class from its underlying implementation?

3. What is the STL?

4. If you want to use the Vector class in a program, what #include line do you
need to add to the beginning of your code?

5. List at least three advantages of the Vector class over the more primitive
array mechanism available in C++.

6. What is meant by the term bounds-checking?

7. What is a parameterized type?

8. What type name would you use to store a vector of Boolean values?

9. True or false: The default constructor for the Vector class creates a vector
with ten elements, although you can make it longer later.

10. How would you initialize a Vector<int> with 20 elements, all equal to 0?

11. What method do you call to determine the number of elements in a Vector?

12. If a Vector object has N elements, what is the legal range of values for the
first argument to insertAt? What about for the argument to removeAt?

13. What feature of the Vector class makes it possible to avoid explicit use of the
get and set methods?

14. Why is it important to pass vectors and other collection object by reference?

15. What declaration would you use to initialize a variable called chessboard to
an 8!8 grid, each of whose elements is a character?

16. Given the chessboard variable from the preceding exercise, how would you
assign the character 'R' (which stands for a white rook in standard chess
notation) to the squares in the lower left and lower right corners of the board?

17. What do the acronyms LIFO and FIFO stand for? How do these terms apply
to stacks and queues?
246 Collections

18. What are the names of the two fundamental operations for a stack?

19. What are the names for the corresponding operations for a queue?

20. What does the peek operation do in each of the Stack and Queue classes?

21. Describe in your own words what is meant by the term discrete time in the
context of a simulation program.

22. What are the two type parameters used with the Map class.

23. What happens if you call get for a key that doesnt exist in a map?

24. What are the syntactic shorthand forms for get and put that allow you to treat
maps as associative arrays?

25. Why do the Stanford libraries include a separate Lexicon class even though it
is easy to implement a lexicon using the Set class?

26. What are the two kinds of data files supported by the constructor for the
Lexicon class?

27. What is the general form of the range-based for loop pattern?

28. What reason does the chapter offer for disallowing the use of the range-based
for loop with the Stack and Queue classes?

29. Describe the order in which the range-based for loop processes elements for
each of the collection classes introduced in this chapter.

Exercises
1. Write the overloaded functions

void readVector(istream & is, Vector<int> & vec);

void readVector(istream & is, Vector<double> & vec);
void readVector(istream & is, Vector<string> & vec);

each of which reads lines from the input stream specified by is into the vector
vec. In the input stream, each element of the vector appears on a line of its
own. The function should read elements until it encounters a blank line or the
end of the file.

To illustrate the operation of this function, suppose that you have the data
file
 Exercises 247

and that you have opened infile as an ifstream on that file. In addition,
suppose that you have declared the variable roots as follows:

Vector<double> roots;

The first call to readVector(infile, roots) should initialize roots so

that it contains the four elements shown at the beginning of the file. The
second call should change the value of roots so that it contains the eight
elements shown at the end of the file. Calling readVector a third time
should set roots to an empty vector.

2. In statistics, a collection of data values is often referred to as a distribution.

One of the primary goals of statistical analysis is to find ways to compress the
complete set of data into summary statistics that express properties of the
distribution as a whole. The most common statistical measure is the mean,
which is simply the traditional average. For the distribution x1, x2, x3, . . . , xn,
the mean is usually represented by the symbol . Write a function

double mean(Vector<double> & data);

that returns the mean of the data in the vector.

3. Another common statistical measure is the standard deviation, which provides

an indication of how much the values in a distribution x1, x2, x3, . . . , xn differ
from the mean. In mathematical form, the standard deviation (!) is expressed
as follows, at least if you are computing the standard deviation of a complete
distribution as opposed to a sample:

! =
248 Collections

The Greek letter sigma (!) indicates a summation of the quantity that follows,
which in this case is the square of the difference between the mean and each
individual data point. Write a function

double stddev(Vector<double> & data);

that returns the standard deviation of the data distribution.

4. A histogram is a graphical way of displaying data by dividing the data into

separate ranges and then indicating how many data values fall into each range.
For example, given the set of exam scores

100, 95, 47, 88, 86, 92, 75, 89, 81, 70, 55, 80

a traditional histogram would have the following form:

The asterisks in the histogram indicate one score in the 40s, one score in the
50s, five scores in the 80s, and so forth.

When you generate histograms using a computer, however, it is much

easier to display them sideways on the page, as in this sample run:

Write a program that reads in a vector of integers from a data file and then
displays a histogram of those numbers, divided into the ranges 09, 1019,
2029, and so forth, up to the range containing only the value 100. Your
program should generate output that looks as much like the sample run as
possible.
 Exercises 249

5. Extend the flexibility of the previous exercise by defining a hist.h interface

that gives clients more control over the format of the histogram. At a
minimum, your interface should allow clients to specify the minimum and
maximum values along with the size of each histogram range, but you should
feel free to provide other capabilities as well. Use your imagination!

6. In the third century B.C.E., the Greek astronomer Eratosthenes developed an

algorithm for finding all the prime numbers up to some upper limit N. To
apply the algorithm, you start by writing down a list of the integers between 2
and N. For example, if N were 20, you would begin by writing the following
list:

You then circle the first number in the list, indicating that you have found a
prime. Whenever you mark a number as a prime, you go through the rest of
the list and cross off every multiple of that number, since none of those
multiples can itself be prime. Thus, after executing the first cycle of the
algorithm, you will have circled the number 2 and crossed off every multiple
of 2, as follows:

To complete the algorithm, you simply repeat the process by circling the
first number in the list that is neither crossed off nor circled, and then crossing
off its multiples. In this example, you would circle 3 as a prime and cross off
all multiples of 3 in the rest of the list, which results in the following state:

Eventually, every number in the list will either be circled or crossed out, as
shown in this diagram:

The circled numbers are the primes; the crossed-out numbers are composites.
This algorithm is called the sieve of Eratosthenes.

Write a program that uses the sieve of Eratosthenes to generate a list of the
primes between 2 and 1000.

7. One of the problems in using the Grid class is that it isnt as easy to set up a
particular set of initial values as it is with a vector, where you can add the
250 Collections

elements you want with the += operator. One way to streamline the process of
initializing a grid is to define a function

void fillGrid(Grid<int> & grid, Vector<int> & values);

that fills the elements of the grid from the values in the vector. For example,
the code

Grid<int> matrix(3, 3);

Vector<int> values;
values += 1, 2, 3;
values += 4, 5, 6;
values += 7, 8, 9;
fillGrid(matrix, values);

initializes the variable matrix to be a 3 ! 3 grid containing the values

8. A magic square is a two-dimensional grid of integers in which the rows,

columns, and diagonals all add up to the same value. One of the most famous
magic squares appears in the 1514 engraving Melencolia I by Albrecht
Drer shown in Figure 5-12, in which a 4 ! 4 magic square appears in the
upper right, just under the bell. In Drers square, which can be read more
easily in the magnified inset shown at the right of the figure, all four rows, all
four columns, and both diagonals add up to 34. A more familiar example is
the following 3 ! 3 magic square in which each of the rows, columns, and
diagonals add up to 15, as shown:

Implement a function

bool isMagicSquare(Grid<int> & square);

 Exercises 251

that tests to see whether the grid contains a magic square. Your program
should work for square grids of any size. If you call isMagicSquare with a
grid in which the number of rows and columns are different, it should simply
return false.

9. In the last several years, a new logic puzzle called Sudoku has become quite
popular throughout the world. In Sudoku, you start with a 9 ! 9 grid of
integers in which some of the cells have been filled in with digits between 1
and 9. Your job in the puzzle is to fill in each of the empty spaces with a digit
between 1 and 9 so that each digit appears exactly once in each row, each
column, and each of the smaller 3 ! 3 squares. Each Sudoku puzzle is carefully
constructed so that there is only one solution. For example, Figure 5-13 shows
a typical Sudoku puzzle on the left and its unique solution on the right.
252 Collections

Although you wont discover the algorithmic strategies you need to solve
Sudoku puzzles until later in this book, you can easily write a method that
checks to see whether a proposed solution follows the Sudoku rules against
duplicating values in a row, column, or outlined 3 ! 3 square. Write a function

bool checkSudokuSolution(Grid<int> & puzzle);

that performs this check and returns true if the puzzle is a valid solution.
Your program should check to make sure that puzzle contains a 9 ! 9 grid of
integers and report an error if this is not the case.

10. In the game of Minesweeper, a player searches for hidden mines on a

rectangular grid that mightfor a very small boardlook like this:

One way to represent that grid in C++ is to use a grid of Boolean values
marking mine locations, where true indicates the location of a mine. In
Boolean form, this sample grid therefore looks like this:
 Exercises 253

Given such a grid of mine locations, write a function

void fixCounts(Grid<bool> & mines, Grid<int> & counts);

that creates a grid of integers storing the number of mines in each neighborhood.
The neighborhood of a location includes the location itself and the eight adjacent
locations, but only if they are inside the boundaries of the grid. The reference
parameter counts is used to store the result. Your job in this exercise is to make
sure that it has the same size as the mines grid and then to assign to each element
an integer between 0 and 9. For example, if mineLocations contains the Boolean
grid shown earlier, the code

Grid<int> mineCounts;
fixCounts(mineLocations, mineCounts);

should initialize mineCounts as follows:

11. The resize method in the Grid class resets the dimensions of the grid but
also initializes every element of the grid to its default value. Write a function

void reshape(Grid<int> & grid, int nRows, int nCols);

that resizes the grid but fills in the data from the original grid by copying
elements in the standard row-major order (left-to-right/top-to-bottom). For
example, if myGrid initially contains the values
254 Collections

calling the function

reshape(myGrid, 4, 3)

should change the dimensions and contents of myGrid as follows:

If the new grid does not include enough space for all of the original values, the
values at the bottom of the grid are simply dropped. For example, if you call

reshape(myGrid, 2, 5)

there is no room for the last two elements, so the new grid will look like this:

Conversely, if there are not enough elements in the original grid to fill the
available space, the entries at the end should simply retain their default values.

12. Write a program that uses a stack to reverse a sequence of integers read from
the console one number per line, as shown in the following sample run:
 Exercises 255

13. And the fi