Table of Contents Table of Location of VideoNotes Inside front cover and inside back cover Chapter 1 Introduction to Computers and C++ Programming 1 1.1 Computer Systems 2 Hardware 2 Software 7 High-Level Languages 8 Compilers 9 History Note 12 1.2 Programing and Problem-Solving 12 Algorithms 12 Program Design 15 Object-Oriented Programming 16 The Software Life Cycle 17 1.3 Introduction to C++ 18 Origins of the C++ Language 18 A Sample C++ Program 19 Pitfall: Using the Wrong Slash in \n 23 Programming Tip: Input and Output Syntax 23 Layout of a Simple C++ Program 24 Pitfall: Putting a Space Before the include File Name 26 Compiling and Running a C++ Program 26 Programming Tip: Getting Your Program to Run 27 1.4 Testing and Debugging 29 Kinds of Program Errors 30 Pitfall: Assuming Your Program Is Correct 31 Chapter Summary 31 Answers to Self-Test Exercises 32 Programming Projects 35 Chapter 2 C++ Basics 39 2.1 Variables and Assignments 40 Variables 40 Names: Identifiers 42 Variable Declarations 44 Assignment Statements 45 Pitfall: Uninitialized Variables 47 Programming Tip: Use Meaningful Names 49 2.2 Input and Output 50 Output Using cout 50 Include Directives and Namespaces 52 Escape Sequences 53 Programming Tip: End Each Program with a \n or endl 54 Formatting for Numbers with a Decimal Point 55 Input Using cin 56 Designing Input and Output 58 Programming Tip: Line Breaks in I/O 58 2.3 Data Types and Expresions 60 The Types int and double 60 Other Number Types 62 The Type char 63 The Type bool 64 Introduction to the Class string 65 Type Compatibilities 66 Arithmetic Operators and Expressions 68 Pitfall: Whole Numbers in Division 71 More Assignment Statements 73 2.4 Simple Flow of Control 73 A Simple Branching Mechanism 74 Pitfall: Strings of Inequalities 79 Pitfall: Using = in place of == 80 Compound Statements 81 Simple Loop Mechanisms 83 Increment and Decrement Operators 86 Programming Example: Charge Card Balance 88 Pitfall: Infinite Loops 89 2.5 Program Style 92 Indenting 92 Comments 92 Naming Constants 94 Chapter Summary 97 Answers to Self-Test Exercises 97 Programming Projects 102 Chapter 3 More Flow of Control 109 3.1 Using Boolean Expresions 110 Evaluating Boolean Expressions 110 Pitfall: Boolean Expressions Convert to int Values 114 Enumeration Types (Optional) 117 3.2 Multiway Branches 118 Nested Statements 118 Programming Tip: Use Braces in Nested Statements 119 Multiway if-else Statements 121 Programming Example: State Income Tax 123 The switch Statement 126 Pitfall: Forgetting a break in a switch Statement 130 Using switch Statements for Menus 131 Blocks 133 Pitfall: Inadvertent Local Variables 136 3.3 More About C++ Loop Statements 137 The while Statements Reviewed 137 Increment and Decrement Operators Revisited 139 The for Statement 142 Pitfall: Extra Semicolon in a for Statement 147 What Kind of Loop to Use 148 Pitfall: Uninitialized Variables and Infinite Loops 150 The break Statement 151 Pitfall: The break Statement in Nested Loops 152 3.4 Designing Loops 153 Loops for Sums and Products 153 Ending a Loop 155 Nested Loops 158 Debugging Loops 160 Chapter Summary 163 Answers to Self-Test Exercises 164 Programming Projects 170 Chapter 4 Procedural Abstraction and Functions That Return a Value 177 4.1 Top-Down Design 178 4.2 Predefined Functions 179 Using Predefined Functions 179 Random Number Generation 184 Type Casting 186 Older Form of Type Casting 188 Pitfall: Integer Division Drops the Fractional Part 188 4.3 Programer-Defined Functions 189 Function Definitions 189 Functions That Return a Boolean Value 195 Alternate Form for Function Declarations 195 Pitfall: Arguments in the Wrong Order 196 Function Definition–Syntax Summary 197 More About Placement of Function Definitions 198 Programming Tip: Use Function Calls in Branching Statements 199 4.4 Procedural Abstraction 200 The Black-Box Analogy 200 Programming Tip: Choosing Formal Parameter Names 203 Programming Tip: Nested Loops 204 Case Study: Buying Pizza 207 Programming Tip: Use Pseudocode 213 4.5 Scope and Local Variables 214 The Small Program Analogy 214 Programming Example: Experimental Pea Patch 217 Global Constants and Global Variables 217 Call-by-Value Formal Parameters Are Local Variables 220 Block Scope 222 Namespaces Revisited 223 Programming Example: The Factorial Function 226 4.6 Overloading Function Names 228 Introduction to Overloading 228 Programming Example: Revised Pizza-Buying Program 231 Automatic Type Conversion 234 Chapter Summary 236 Answers to Self-Test Exercises 236 Programming Projects 241 Chapter 5 Functions for All Subtasks 247 5.1 void Functions 248 Definitions of void Functions 248 Programming Example: Converting Temperatures 251 return Statements in void Functions 251 5.2 Call-By-Reference Parameters 255 A First View of Call-by-Reference 255 Call-by-Reference in Detail 258 Programming Example: The swap_values Function 263 Mixed Parameter Lists 264 Programming Tip: What Kind of Parameter to Use 265 Pitfall: Inadvertent Local Variables 266 5.3 Using Procedural Abstraction 269 Functions Calling Functions 269 Preconditions and Postconditions 271 Case Study: Supermarket Pricing 272 5.4 Testing and Debugging Functions 277 Stubs and Drivers 278 5.5 General Debugging Techniques 283 Keep an Open Mind 283 Check Common Errors 283 Localize the Error 284 The assert Macro 286 Chapter Summary 288 Answers to Self-Test Exercises 289 Programming Projects 292 Chapter 6 I/O Streams as an Introduction to Objects and Classes 301 6.1 Streams and Basic File I/O 302 Why Use Files for I/O? 303 File I/O 304 Introduction to Classes and Objects 308 Programming Tip: Check Whether a File Was Opened Successfully 310 Techniques for File I/O 312 Appending to a File (Optional) 316 File Names as Input (Optional) 317 6.2 Tools for Stream I/O 319 Formatting Output with Stream Functions 319 Manipulators 325 Streams as Arguments to Functions 328 Programming Tip: Checking for the End of a File 328 A Note on Namespaces 331 Programming Example: Cleaning Up a File Format 332 6.3 Character I/O 334 The Member Functions get and put 334 The putback Member Function (Optional) 338 Programming Example: Checking Input 339 Pitfall: Unexpected '\n' in Input 341 Programming Example: Another new_line Function 343 Default Arguments for Functions (Optional) 344 The eof Member Function 349 Programming Example: Editing a Text File 351 Predefined Character Functions 352 Pitfall: toupper and tolower Return Values 354 Chapter Summary 356 Answers to Self-Test Exercises 357 Programming Projects 364 Chapter 7 Arrays 373 7.1 Introduction to Arrays 374 Declaring and Referencing Arrays 374 Programming Tip: Use for Loops with Arrays 376 Pitfall: Array Indexes Always Start with Zero 376 Programming Tip: Use a Defined Constant for the Size of an Array 376 Arrays in Memory 378 Pitfall: Array Index Out of Range 379 Initializing Arrays 381 7.2 Arrays in Functions 383 Indexed Variables as Function Arguments 383 Entire Arrays as Function Arguments 385 The const Parameter Modifier 388 Pitfall: Inconsistent Use of const Parameters 391 Functions That Return an Array 391 Case Study: Production Graph 392 7.3 Programing with Arrays 405 Partially Filled Arrays 405 Programming Tip: Do Not Skimp on Formal Parameters 408 Programming Example: Searching an Array 408 Programming Example: Sorting an Array 411 7.4 Multidimensional Arrays 415 Multidimensional Array Basics 416 Multidimensional Array Parameters 416 Programming Example: Two-Dimensional Grading Program 418 Pitfall: Using Commas Between Array Indexes 422 Chapter Summary 423 Answers to Self-Test Exercises 424 Programming Projects 428 Chapter 8 Strings and Vectors 441 8.1 An Array Type for Strings 443 C-String Values and C-String Variables 443 Pitfall: Using = and == with C Strings 446 Other Functions in 448 C-String Input and Output 453 C-String-to-Number Conversions and Robust Input 455 8.2 The Standard string Clas 461 Introduction to the Standard Class string 461 I/O with the Class string 464 Programming Tip: More Versions of getline 467 Pitfall: Mixing cin >> variable; and getline 468 String Processing with the Class string 469 Programming Example: Palindrome Testing 473 Converting Between string Objects and C Strings 476 8.3 Vectors 477 Vector Basics 477 Pitfall: Using Square Brackets Beyond the Vector Size 480 Programming Tip: Vector Assignment Is Well Behaved 481 Efficiency Issues 481 Chapter Summary 483 Answers to Self-Test Exercises 484 Programming Projects 486 Chapter 9 Pointers and Dynamic Arrays 493 9.1 Pointers 494 Pointer Variables 495 Basic Memory Management 502 Pitfall: Dangling Pointers 503 Static Variables and Automatic Variables 504 Programming Tip: Define Pointer Types 504 9.2 Dynamic Arrays 507 Array Variables and Pointer Variables 507 Creating and Using Dynamic Arrays 508 Pointer Arithmetic (Optional) 514 Multidimensional Dynamic Arrays (Optional) 516 Chapter Summary 518 Answers to Self-Test Exercises 518 Programming Projects 519 Chapter 10 Defining Classes 525 10.1 Structures 526 Structures for Diverse Data 526 Pitfall: Forgetting a Semicolon in a Structure Definition 531 Structures as Function Arguments 532 Programming Tip: Use Hierarchical Structures 533 Initializing Structures 535 10.2 Classes 538 Defining Classes and Member Functions 538 Public and Private Members 543 Programming Tip: Make All Member Variables Private 551 Programming Tip: Define Accessor and Mutator Functions 551 Programming Tip: Use the Assignment Operator with Objects 553 Programming Example: BankAccount Class–Version 1 554 Summary of Some Properties of Classes 558 Constructors for Initialization 560 Programming Tip: Always Include a Default Constructor 568 Pitfall: Constructors with No Arguments 569 10.3 Abstract Data Types 571 Classes to Produce Abstract Data Types 572 Programming Example: Alternative Implementation of a Class 576 10.4 Introduction to Inheritance 581 Derived Classes 582 Defining Derived Classes 583 Chapter Summary 587 Answers to Self-Test Exercises 588 Programming Projects 594 Chapter 11 Friends, Overloaded Operators, and Arrays in Classes 601 11.1 Friend Functions 602 Programming Example: An Equality Function 602 Friend Functions 606 Programming Tip: Define Both Accessor Functions and Friend Functions 608 Programming Tip: Use Both Member and Nonmember Functions 610 Programming Example: Money Class (Version 1) 610 Implementation of digit_to_int (Optional) 617 Pitfall: Leading Zeros in Number Constants 618 The const Parameter Modifier 620 Pitfall: Inconsistent Use of const 621 11.2 Overloading Operators 625 Overloading Operators 626 Constructors for Automatic Type Conversion 629 Overloading Unary Operators 631 Overloading >> and << 632 11.3 Arrays and Classes 642 Arrays of Classes 642 Arrays as Class Members 646 Programming Example: A Class for a Partially Filled Array 647 11.4 Classes and Dynamic Arrays 649 Programming Example: A String Variable Class 650 Destructors 653 Pitfall: Pointers as Call-by-Value Parameters 656 Copy Constructors 657 Overloading the Assignment Operator 662 Chapter Summary 665 Answers to Self-Test Exercises 665 Programming Projects 675 Chapter 12 Separate Compilation and Namespaces 685 12.1 Separate Compilation 686 ADTs Reviewed 687 Case Study: DigitalTime —A Class Compiled Separately 688 Using #ifndef 697 Programming Tip: Defining Other Libraries 700 12.2 Namespaces 701 Namespaces and using Directives 701 Creating a Namespace 703 Qualifying Names 706 A Subtle Point About Namespaces (Optional) 707 Unnamed Namespaces 708 Programming Tip: Choosing a Name for a Namespace 713 Pitfall: Confusing the Global Namespace and the Unnamed Namespace 714 Chapter Summary 715 Answers to Self-Test Exercises 716 Programming Projects 718 Chapter 13 Pointers and Linked Lists 721 13.1 Nodes and Linked Lists 722 Nodes 722 Linked Lists 728 Inserting a Node at the Head of a List 729 Pitfall: Losing Nodes 732 Searching a Linked List 733 Pointers as Iterators 735 Inserting and Removing Nodes Inside a List 737 Pitfall: Using the Assignment Operator with Dynamic Data Structures 740 Variations on Linked Lists 741 Linked Lists of Classes 744 13.2 Stacks and Queues 747 Stacks 747 Programming Example: A Stack Class 748 Queues 753 Programming Example: A Queue Class 754 Chapter Summary 758 Answers to Self-Test Exercises 758 Programming Projects 761 Chapter 14 Recursion 769 14.1 Recursive Functions for Tasks 771 Case Study: Vertical Numbers 771 A Closer Look at Recursion 777 Pitfall: Infinite Recursion 779 Stacks for Recursion 780 Pitfall: Stack Overflow 782 Recursion Versus Iteration 782 14.2 Recursive Functions for Values 784 General Form for a Recursive Function That Returns a Value 784 Programming Example: Another Powers Function 784 14.3 Thinking Recursively 789 Recursive Design Techniques 789 Case Study: Binary Search—An Example of Recursive Thinking 790 Programming Example: A Recursive Member Function 798 Chapter Summary 802 Answers to Self-Test Exercises 802 Programming Projects 807 Chapter 15 Inheritance 811 15.1 Inheritance Basics 812 Derived Classes 813 Constructors in Derived Classes 821 Pitfall: Use of Private Member Variables from the Base Class 824 Pitfall: Private Member Functions Are Effectively Not Inherited 826 The protected Qualifier 826 Redefinition of Member Functions 829 Redefining Versus Overloading 832 Access to a Redefined Base Function 834 15.2 INHERITANCE DETAILS 835 Functions That Are Not Inherited 835 Assignment Operators and Copy Constructors in Derived Classes 836 Destructors in Derived Classes 837 15.3 Polymorphism 838 Late Binding 839 Virtual Functions in C++ 840 Virtual Functions and Extended Type Compatibility 845 Pitfall: The Slicing Problem 849 Pitfall: Not Using Virtual Member Functions 850 Pitfall: Attempting to Compile Class Definitions Without Definitions for Every Virtual Member Function 851 Programming Tip: Make Destructors Virtual 851 Chapter Summary 853 Answers to Self-Test Exercises 853 Programming Projects 857 Chapter 16 Exception Handling 867 16.1 Exception-Handling Basics 869 A Toy Example of Exception Handling 869 Defining Your Own Exception Classes 878 Multiple Throws and Catches 878 Pitfall: Catch the More Specific Exception First 882 Programming Tip: Exception Classes Can Be Trivial 883 Throwing an Exception in a Function 883 Exception Specification 885 Pitfall: Exception Specification in Derived Classes 887 16.2 Programing Techniques for Exception Handling 888 When to Throw an Exception 888 Pitfall: Uncaught Exceptions 890 Pitfall: Nested try-catch Blocks 890 Pitfall: Overuse of Exceptions 890 Exception Class Hierarchies 891 Testing for Available Memory 891 Rethrowing an Exception 892 Chapter Summary 892 Answers to Self-Test Exercises 892 Programming Projects 894 Chapter 17 Templates 899 17.1 Templates for Algorithm Abstraction 900 Templates for Functions 901 Pitfall: Compiler Complications 905 Programming Example: A Generic Sorting Function 907 Programming Tip: How to Define Templates 911 Pitfall: Using a Template with an Inappropriate Type 912 17.2 Templates for Data Abstraction 913 Syntax for Class Templates 913 Programming Example: An Array Class 916 Chapter Summary 922 Answers to Self-Test Exercises 922 Programming Projects 925 Chapter 18 Standard Template Library 931 18.1 Iterators 933 using Declarations 933 Iterator Basics 934 Pitfall: Compiler Problems 938 Kinds of Iterators 940 Constant and Mutable Iterators 944 Reverse Iterators 945 Other Kinds of Iterators 946 18.2 Containers 947 Sequential Containers 948 Pitfall: Iterators and Removing Elements 952 Programming Tip: Type Definitions in Containers 953 Container Adapters stack and queue 953 Associative Containers set and map 957 Efficiency 964 18.3 Generic Algorithms 965 Running Times and Big-O Notation 965 Container Access Running Times 970 Nonmodifying Sequence Algorithms 971 Container Modifying Algorithms 975 Set Algorithms 977 Sorting Algorithms 978 Chapter Summary 979 Answers to Self-Test Exercises 979 Programming Projects 981 Appendices 1 C++ Keywords 987 2 Precedence of Operators 988 3 The ASCII Character Set 990 4 Some Library Functions 991 5 Inline Functions 998 6 Overloading the Array Index Square Brackets 999 7 The this Pointer 1001 8 Overloading Operators as Member Operators 1004 Index 1006