Preface iii
Special Features xxiv
1 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
11 Recursion 363
11.1 Triangle Numbers 364
CE 1 Tracing Through Recursive Functions 367
CE 2 Infinite Recursion 368
HT 1 Thinking Recursively 369
WE 1 Finding Files 372
11.2 Recursive Helper Functions 372
11.3 The Efficiency of Recursion 373
11.4 Permutations 377
11.5 Mutual Recursion 380
11.6 Backtracking 383
WE 2 Towers of Hanoi 389
C&S The Limits of Computation 390
12 Sorting and Searching 393
12.1 Selection Sort 394
12.2 Profiling the Selection Sort Algorithm 397
12.3 Analyzing the Performance of the Selection Sort Algorithm 398
ST 1 Oh, Omega, and Theta 399
ST 2 Insertion Sort 400
12.4 Merge Sort 402
12.5 Analyzing the Merge Sort Algorithm 405
ST 3 The Quicksort Algorithm 407
12.6 Searching 408
Linear Search 408
Binary Search 410
PT 1 Library Functions for Sorting and Binary Search 412
ST 4 Defining an Ordering for Sorting Objects 413
12.7 PROBLEM SOLVING Estimating the Running Time of an Algorithm 413
Linear Time 413
Quadratic Time 414
The Triangle Pattern 415
Logarithmic Time 417
WE 1 Enhancing the Insertion Sort Algorithm 418
C&S The First Programmer 418
13 Advanced C++ 421
13.1 Operator Overloading 422
Operator Functions 422
Overloading Comparison Operators 425
Input and Output 425
Operator Members 426
ST 1 Overloading Increment and Decrement Operators 427
ST 2 Implicit Type Conversions 428
ST 3 Returning References 429
WE 1 A Fraction Class 430
13.2 Automatic Memory Management 430
Constructors That Allocate Memory 430
Destructors 432
Overloading the Assignment Operator 433
Copy Constructors 437
PT 1 Use Reference Parameters to Avoid Copies 441
CE 1 Defining a Destructor Without the Other Two Functions of the âBig Threeâ 442
ST 4 Virtual Destructors 443
ST 5 Suppressing Automatic Generation of Memory Management Functions 443
ST 6 Move Operations 444
ST 7 Shared Pointers 445
WE 2 Tracing Memory Management of Strings 446
13.3 Templates 446
Function Templates 447
Class Templates 448
ST 8 Non-Type Template Parameters 450
14 Linked Lists, Stacks, and Queues 453
14.1 Using Linked Lists 454
14.2 Implementing Linked Lists 459
The Classes for Lists, Node, and Iterators 459
Implementing Iterators 460
Implementing Insertion and Removal 462
WE 1 Implementing a Linked List Template 472
14.3 The Efficiency of List, Array, and Vector Operations 472
14.4 Stacks and Queues 476
14.5 Implementing Stacks and Queues 479
Stacks as Linked Lists 479
Stacks as Arrays 482
Queues as Linked Lists 482
Queues as Circular Arrays 483
14.6 Stack and Queue Applications 484
Balancing Parentheses 484
Evaluating Reverse Polish Expressions 485
Evaluating Algebraic Expressions 487
Backtracking 490
ST 1 Reverse Polish Notation 492
15 Sets, Maps, and Hash Tables 495
15.1 Sets 496
15.2 Maps 499
PT 1 Use the auto Type for Iterators 503
ST 1 Multisets and Multimaps 503
WE 1 Word Frequency 504
15.3 Implementing a Hash Table 504
Hash Codes 504
Hash Tables 505
Finding an Element 507
Adding and Removing Elements 508
Iterating over a Hash Table 508
ST 2 Implementing Hash Functions 514
ST 3 Open Addressing 516
16 Tree Structures 519
16.1 Basic Tree Concepts 520
16.2 Binary Trees 524
Binary Tree Examples 524
Balanced Trees 526
A Binary Tree Implementation 527
WE 1 Building a Huffman Tree 528
16.3 Binary Search Trees 528
The Binary Search Property 529
Insertion 530
Removal 532
Efficiency of the Operations 533
16.4 Tree Traversal 538
Inorder Traversal 539
Preorder and Postorder Traversals 540
The Visitor Pattern 541
Depth-First and Breadth-First Search 542
Tree Iterators 543
16.5 Red-Black Trees 544
Basic Properties of Red-Black Trees 544
Insertion 546
Removal 548
WE 2 Implementing a Red-Black Tree 551
17 Priority Queues and Heaps 553
17.1 Priority Queues 554
WE 1 Simulating a Queue of Waiting Customers 557
17.2 Heaps 557
17.3 The Heapsort Algorithm 567
Appendix A Reserved Word Summary A-1
Appendix B Operator Summary A-3
Appendix C Character Codes A-5
Appendix D C++ Library Summary A-8
Appendix E C++ Language Coding Guidelines A-12
Appendix F Number Systems and Bit and Shift Operations A-19
Glossary G-1
Index I-1
Credits C-1
Quick Reference C-2
