Big C++

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