Brief C++

Cay S Hostmann grew up in Northern Germany and attended the Christian-Albrechts-Universität in Kiel, a harbor town at the Baltic sea. He received a M.S. in computer science from Syracuse University, and a Ph.D. in mathematics from the University of Michigan in Ann Arbor. For four years, He was VP and CTO of an Internet startup that went from 3 people in a tiny office to a public company. He now teaches computer science at San Jose State University. In his copious spare time, he writes books and articles on programming languages and computer science education.

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