Preface v
Special Features xxiv
Quick Reference xxviii
Introduction 1
1.1 What is Programming? 2
1.2 The Anatomy of a Computer 3
C&S Computers are Everywhere 5
1.3 Machine Code and Programming Languages 5
C&S Standards Organizations 7
1.4 Becoming Familiar with Your Programming Environment 7
PT 1 Backup Copies 10
1.5 Analyzing Your First Program 11
CE 1 Omitting Semicolons 13
ST 1 Escape Sequences 13
1.6 Errors 14
CE 2 Misspelling Words 15
1.7 PROBLEM SOLVING Algorithm Design 16
The Algorithm Concept 16
An Algorithm for Solving an Investment Problem 17
Pseudocode 18
From Algorithms to Programs 19
HT 1 Describing an Algorithm with Pseudocode 19
WE 1 Writing an Algorithm for Tiling a Floor 21
2 Fundamental Data Types 25
2.1 Variables 26
Variable Definitions 26
Number Types 28
Variable Names 29
The Assignment Statement 30
Constants 31
Comments 31
CE 1 Using Undefined Variables 33
CE 2 Using Uninitialized Variables 33
PT 1 Choose Descriptive Variable Names 33
PT 2 Do Not Use Magic Numbers 34
ST 1 Numeric Types in C++ 34
ST 2 Numeric Ranges and Precisions 35
ST 3 Defining Variables with auto 35
2.2 Arithmetic 36
Arithmetic Operators 36
Increment and Decrement 36
Integer Division and Remainder 36
Converting Floating-Point Numbers to Integers 37
Powers and Roots 38
CE 3 Unintended Integer Division 39
CE 4 Unbalanced Parentheses 40
CE 5 Forgetting Header Files 40
CE 6 Roundoff Errors 41
PT 3 Spaces in Expressions 42
ST 4 Casts 42
ST 5 Combining Assignment and Arithmetic 42
C&S The Pentium Floating-Point Bug 43
2.3 Input and Output 44
Input 44
Formatted Output 45
2.4 PROBLEM SOLVING First Do It By Hand 47
WE 1 Computing Travel Time 48
HT 1 Carrying out Computations 48
WE 2 Computing the Cost of Stamps 51
2.5 Strings 51
The string Type 51
Concatenation 52
String Input 52
String Functions 52
C&S International Alphabets and Unicode 55
3 Decisions 59
3.1 The if Statement 60
CE 1 A Semicolon After the if Condition 63
PT 1 Brace Layout 63
PT 2 Always Use Braces 64
PT 3 Tabs 64
PT 4 Avoid Duplication in Branches 65
ST 1 The Conditional Operator 65
3.2 Comparing Numbers and Strings 66
CE 2 Confusing = and == 68
CE 3 Exact Comparison of Floating-Point Numbers 68
PT 5 Compile with Zero Warnings 69
ST 2 Lexicographic Ordering of Strings 69
HT 1 Implementing an if Statement 70
WE 1 Extracting the Middle 72
C&S Dysfunctional Computerized Systems 72
3.3 Multiple Alternatives 73
ST 3 The switch Statement 75
3.4 Nested Branches 76
CE 4 The Dangling else Problem 79
PT 6 Hand-Tracing 79
3.5 PROBLEM SOLVING Flowcharts 81
3.6 PROBLEM SOLVING Test Cases 83
PT 7 Make a Schedule and Make Time for Unexpected Problems 84
3.7 Boolean Variables and Operators 85
CE 5 Combining Multiple Relational Operators 88
CE 6 Confusing && and || Conditions 88
ST 4 Short-Circuit Evaluation of Boolean Operators 89
ST 5 De Morgan¢s Law 89
3.8 APPLICATION Input Validation 90
C&S Artificial Intelligence 92
4 Loops 95
4.1 The while Loop 96
CE 1 Infinite Loops 100
CE 2 Don¢t Think ¢are We There Yet?¢ 101
CE 3 Off-by-One Errors 101
C&S The First Bug 102
4.2 PROBLEM SOLVING Hand-Tracing 103
4.3 The for Loop 106
PT 1 Use for Loops for Their Intended Purpose Only 109
PT 2 Choose Loop Bounds That Match Your Task 110
PT 3 Count Iterations 110
4.4 The do Loop 111
PT 4 Flowcharts for Loops 111
4.5 Processing Input 112
Sentinel Values 112
Reading Until Input Fails 114
ST 1 Clearing the Failure State 115
ST 2 The Loop-and-a-Half Problem and the break Statement 116
ST 3 Redirection of Input and Output 116
4.6 PROBLEM SOLVING Storyboards 117
4.7 Common Loop Algorithms 119
Sum and Average Value 119
Counting Matches 120
Finding the First Match 120
Prompting Until a Match is Found 121
Maximum and Minimum 121
Comparing Adjacent Values 122
HT 1 Writing a Loop 123
WE 1 Credit Card Processing 126
4.8 Nested Loops 126
WE 2 Manipulating the Pixels in an Image 129
4.9 PROBLEM SOLVING Solve a Simpler Problem First 130
4.10 Random Numbers and Simulations 134
Generating Random Numbers 134
Simulating Die Tosses 135
The Monte Carlo Method 136
C&S Digital Piracy 138
5 Functions 141
5.1 Functions as Black Boxes 142
5.2 Implementing Functions 143
PT 1 Function Comments 146
5.3 Parameter Passing 146
PT 2 Do Not Modify Parameter Variables 148
5.4 Return Values 148
CE 1 Missing Return Value 149
ST 1 Function Declarations 150
HT 1 Implementing a Function 151
WE 1 Generating Random Passwords 152
WE 2 Using a Debugger 152
5.5 Functions Without Return Values 153
5.6 PROBLEM SOLVING Reusable Functions 154
5.7 PROBLEM SOLVING Stepwise Refinement 156
PT 3 Keep Functions Short 161
PT 4 Tracing Functions 161
PT 5 Stubs 162
WE 3 Calculating a Course Grade 163
5.8 Variable Scope and Global Variables 163
PT 6 Avoid Global Variables 165
5.9 Reference Parameters 165
PT 7 Prefer Return Values to Reference Parameters 169
ST 2 Constant References 170
5.10 Recursive Functions (Optional) 170
HT 2 Thinking Recursively 173
C&S The Explosive Growth of Personal Computers 174
6 Arrays and Vectors 179
6.1 Arrays 180
Defining Arrays 180
Accessing Array Elements 182
Partially Filled Arrays 183
CE 1 Bounds Errors 184
PT 1 Use Arrays for Sequences of Related Values 184
C&S Computer Viruses 185
6.2 Common Array Algorithms 185
Filling 186
Copying 186
Sum and Average Value 186
Maximum and Minimum 187
Element Separators 187
Counting Matches 187
Linear Search 188
Removing an Element 188
Inserting an Element 189
Swapping Elements 190
Reading Input 191
ST 1 Sorting with the C++ Library 192
ST 2 A Sorting Algorithm 192
ST 3 Binary Search 193
6.3 Arrays and Functions 194
ST 4 Constant Array Parameters 198
6.4 PROBLEM SOLVING Adapting Algorithms 198
HT 1 Working with Arrays 200
WE 1 Rolling the Dice 203
6.5 PROBLEM SOLVING Discovering Algorithms by Manipulating Physical Objects 203
6.6 Two-Dimensional Arrays 206
Defining Two-Dimensional Arrays 207
Accessing Elements 207
Locating Neighboring Elements 208
Computing Row and Column Totals 208
Two-Dimensional Array Parameters 210
CE 2 Omitting the Column Size of a Two-Dimensional Array Parameter 212
WE 2 A World Population Table 213
6.7 Vectors 213
Defining Vectors 214
Growing and Shrinking Vectors 215
Vectors and Functions 216
Vector Algorithms 216
Two-Dimensional Vectors 218
PT 2 Prefer Vectors over Arrays 219
ST 5 The Range-Based for Loop 219
7 Pointers and Structures 223
7.1 Defining and Using Pointers 224
Defining Pointers 224
Accessing Variables Through Pointers 225
Initializing Pointers 227
CE 1 Confusing Pointers with the Data to Which They Point 228
PT 1 Use a Separate Definition for Each Pointer Variable 229
ST 1 Pointers and References 229
7.2 Arrays and Pointers 230
Arrays as Pointers 230
Pointer Arithmetic 230
Array Parameter Variables are Pointers 232
ST 2 Using a Pointer to Step Through an Array 233
CE 2 Returning a Pointer to a Local Variable 234
PT 2 Program Clearly, Not Cleverly 234
ST 3 Constant Pointers 235
7.3 C and C++ Strings 235
The char Type 235
C Strings 236
Character Arrays 237
Converting Between C and C++ Strings 237
C++ Strings and the [] Operator 238
ST 4 Working with C Strings 238
7.4 Dynamic Memory Allocation 240
CE 3 Dangling Pointers 242
CE 4 Memory Leaks 243
7.5 Arrays and Vectors of Pointers 243
7.6 PROBLEM SOLVING Draw a Picture 246
HT 1 Working with Pointers 248
WE 1 Producing a Mass Mailing 249
C&S Embedded Systems 250
7.7 Structures 250
Structured Types 250
Structure Assignment and Comparison 251
Functions and Structures 252
Arrays of Structures 252
Structures with Array Members 253
Nested Structures 253
7.8 Pointers and Structures 254
Pointers to Structures 254
Structures with Pointer Members 255
ST 5 Smart Pointers 256
8 Streams 259
8.1 Reading and Writing Text Files 260
Opening a Stream 260
Reading from a File 261
Writing to a File 262
A File Processing Example 262
8.2 Reading Text Input 265
Reading Words 265
Reading Characters 266
Reading Lines 267
CE 1 Mixing >> and getline Input 268
ST 1 Stream Failure Checking 269
8.3 Writing Text Output 270
ST 2 Unicode, UTF-8, and C++ Strings 272
8.4 Parsing and Formatting Strings 273
8.5 Command Line Arguments 274
C&S Encryption Algorithms 277
HT 1 Processing Text Files 278
WE 1 Looking for for Duplicates 281
8.6 Random Access and Binary Files 281
Random Access 281
Binary Files 282
Processing Image Files 282
C&S Databases and Privacy 286
9 Classes 289
9.1 Object-Oriented Programming 290
9.2 Implementing a Simple Class 292
9.3 Specifying the Public Interface of a Class 294
CE 1 Forgetting a Semicolon 296
9.4 Designing the Data Representation 297
9.5 Member Functions 299
Implementing Member Functions 299
Implicit and Explicit Parameters 299
Calling a Member Function from a Member Function 301
PT 1 All Data Members Should Be Private; Most Member Functions Should Be Public 303
PT 2 const Correctness 303
9.6 Constructors 304
CE 2 Trying to Call a Constructor 306
ST 1 Overloading 306
ST 2 Initializer Lists 307
ST 3 Universal and Uniform Initialization Syntax 308
9.7 PROBLEM SOLVING Tracing Objects 308
HT 1 Implementing a Class 310
WE 1 Implementing a Bank Account Class 314
C&S Electronic Voting Machines 314
9.8 PROBLEM SOLVING Discovering Classes 315
PT 3 Make Parallel Vectors into Vectors of Objects 317
9.9 Separate Compilation 318
9.10 Pointers to Objects 322
Dynamically Allocating Objects 322
The -> Operator 323
The this Pointer 324
9.11 PROBLEM SOLVING Patterns for Object Data 324
Keeping a Total 324
Counting Events 325
Collecting Values 326
Managing Properties of an Object 326
Modeling Objects with Distinct States 327
Describing the Position of an Object 328
C&S Open Source and Free Software 329
10 Inheritance 333
10.1 Inheritance Hierarchies 334
10.2 Implementing Derived Classes 338
CE 1 Private Inheritance 341
CE 2 Replicating Base-Class Members 341
PT 1 Use a Single Class for Variation in Values, Inheritance for Variation in Behavior 342
ST 1 Calling the Base-Class Constructor 342
10.3 Overriding Member Functions 343
CE 3 Forgetting the Base-Class Name 345
10.4 Virtual Functions and Polymorphism 346
The Slicing Problem 346
Pointers to Base and Derived Classes 347
Virtual Functions 348
Polymorphism 349
PT 2 Don¢t Use Type Tags 352
CE 4 Slicing an Object 352
CE 5 Failing to Override a Virtual Function 353
ST 2 Virtual Self-Calls 354
HT 1 Developing an Inheritance Hierarchy 354
WE 1 Implementing an Employee Hierarchy for Payroll Processing 359
C&S Who Controls the Internet? 360
