Problem solving with C++

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 Programming 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 Pitfall: Compiling a C++11 program 27 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 32 Answers to Self-Test Exercises 33 Practice Programs 35 Programming Projects 36 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 55 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 Expressions 60 The Types int and double 60 Other Number Types 62 C++11 Types 63 The Type char 64 The Type bool 66 Introduction to the Class string 66 Type Compatibilities 68 Arithmetic Operators and Expressions 69 Pitfall: Whole Numbers in Division 72 More Assignment Statements 74 2.4 Simple Flow of Control 74 A Simple Branching Mechanism 75 Pitfall: Strings of Inequalities 80 Pitfall: Using = in place of == 81 Compound Statements 82 Simple Loop Mechanisms 84 Increment and Decrement Operators 87 Programming Example: Charge Card Balance 89 Pitfall: Infinite Loops 90 2.5 Program Style 93 Indenting 93 Comments 93 Naming Constants 95 Chapter Summary 98 Answers to Self-Test Exercises 98 Practice Programs 103 Programming Projects 105 Chapter 3 More Flow of Control 111 3.1 Usin g Boolean Expressions 112 Evaluating Boolean Expressions 112 Pitfall: Boolean Expressions Convert to int Values 116 Enumeration Types (Optional) 119 3.2 Multiway Branches 120 Nested Statements 120 Programming Tip: Use Braces in Nested Statements 121 Multiway if-else Statements 123 Programming Example: State Income Tax 125 The switch Statement 128 Pitfall: Forgetting a break in a switch Statement 132 Using switch Statements for Menus 133 Blocks 135 Pitfall: Inadvertent Local Variables 138 3.3 More About C++ Loop Statements 139 The while Statements Reviewed 139 Increment and Decrement Operators Revisited 141 The for Statement 144 Pitfall: Extra Semicolon in a for Statement 149 What Kind of Loop to Use 150 Pitfall: Uninitialized Variables and Infinite Loops 152 The break Statement 153 Pitfall: The break Statement in Nested Loops 154 3.4 Designing Loops 155 Loops for Sums and Products 155 Ending a Loop 157 Nested Loops 160 Debugging Loops 162 Chapter Summary 165 Answers to Self-Test Exercises 166 Practice Programs 172 Programming Projects 174 Chapter 4 Procedural Abstraction and Functions That Return a Value 181 4.1 Top-Down Design 182 4.2 Predefined Functions 183 Using Predefined Functions 183 Random Number Generation 188 Type Casting 190 Older Form of Type Casting 192 Pitfall: Integer Division Drops the Fractional Part 192 4.3 Programmer-Defined Functions 193 Function Definitions 193 Functions That Return a Boolean Value 199 Alternate Form for Function Declarations 199 Pitfall: Arguments in the Wrong Order 200 Function Definition-Syntax Summary 201 More About Placement of Function Definitions 202 Programming Tip: Use Function Calls in Branching Statements 203 4.4 Procedural Abstraction 204 The Black-Box Analogy 204 Programming Tip: Choosing Formal Parameter Names 207 Programming Tip: Nested Loops 208 Case Study: Buying Pizza 211 Programming Tip: Use Pseudocode 217 4.5 Scope and Local Variables 218 The Small Program Analogy 218 Programming Example: Experimental Pea Patch 221 Global Constants and Global Variables 221 Call-by-Value Formal Parameters Are Local Variables 224 Block Scope 226 Namespaces Revisited 227 Programming Example: The Factorial Function 230 4.6 Overloading Function Names 232 Introduction to Overloading 232 Programming Example: Revised Pizza-Buying Program 235 Automatic Type Conversion 238 Chapter Summary 240 Answers to Self-Test Exercises 240 Practice Programs 245 Programming Projects 247 Chapter 5 Functions for All Subtasks 251 5.1 void Functions 252 Definitions of void Functions 252 Programming Example: Converting Temperatures 255 return Statements in void Functions 255 5.2 Call-By-Reference Parameters 259 A First View of Call-by-Reference 259 Call-by-Reference in Detail 262 Programming Example: The swap_values Function 267 Mixed Parameter Lists 268 Programming Tip: What Kind of Parameter to Use 269 Pitfall: Inadvertent Local Variables 270 5.3 Using Procedural Abstraction 273 Functions Calling Functions 273 Preconditions and Postconditions 275 Case Study: Supermarket Pricing 276 5.4 Testing and Debugging Functions 281 Stubs and Drivers 282 5.5 General Debugging Techniques 287 Keep an Open Mind 287 Check Common Errors 287 Localize the Error 288 The assert Macro 290 Chapter Summary 292 Answers to Self-Test Exercises 293 Practice Programs 296 Programming Projects 299 Chapter 6 I/O Streams as an Introduction to Objects and Classes 305 6.1 Streams and Basic File I/O 306 Why Use Files for I/O? 307 File I/O 308 Introduction to Classes and Objects 312 Programming Tip: Check Whether a File Was Opened Successfully 314 Techniques for File I/O 316 Appending to a File (Optional) 320 File Names as Input (Optional) 321 6.2 Tools for Stream I/O 323 Formatting Output with Stream Functions 323 Manipulators 329 Streams as Arguments to Functions 332 Programming Tip: Checking for the End of a File 332 A Note on Namespaces 335 Programming Example: Cleaning Up a File Format 336 6.3 Character I/O 338 The Member Functions get and put 338 The putback Member Function (Optional) 342 Programming Example: Checking Input 343 Pitfall: Unexpected '\n' in Input 345 Programming Example: Another new_line Function 347 Default Arguments for Functions (Optional) 348 The eof Member Function 353 Programming Example: Editing a Text File 355 Predefined Character Functions 356 Pitfall: toupper and tolower Return Values 358 Chapter Summary 360 Answers to Self-Test Exercises 361 Practice Programs 368 Programming Projects 370 Chapter 7 Arrays 377 7.1 Introduction to Arrays 378 Declaring and Referencing Arrays 378 Programming Tip: Use for Loops with Arrays 380 Pitfall: Array Indexes Always Start with Zero 380 Programming Tip: Use a Defined Constant for the Size of an Array 380 Arrays in Memory 382 Pitfall: Array Index Out of Range 383 Initializing Arrays 386 Programming Tip: C++11 Range-Based for Statement 386 7.2 Arrays in Functions 389 Indexed Variables as Function Arguments 389 Entire Arrays as Function Arguments 391 The const Parameter Modifier 394 Pitfall: Inconsistent Use of const Parameters 397 Functions That Return an Array 397 Case Study: Production Graph 398 7.3 Programming with Arrays 411 Partially Filled Arrays 411 Programming Tip: Do Not Skimp on Formal Parameters 414 Programming Example: Searching an Array 414 Programming Example: Sorting an Array 417 Programming Example: Bubble Sort 421 7.4 Multidimensional Arrays 424 Multidimensional Array Basics 425 Multidimensional Array Parameters 425 Programming Example: Two-Dimensional Grading Program 427 Pitfall: Using Commas Between Array Indexes 431 Chapter Summary 432 Answers to Self-Test Exercises 433 Practice Programs 437 Programming Projects 439 Chapter 8 Strings and Vectors 451 8.1 An Array Type for Strings 453 C-String Values and C-String Variables 453 Pitfall: Using = and == with C Strings 456 Other Functions in 458 Pitfall: Copying past the end of a C-string using strcpy 461 C-String Input and Output 464 C-String-to-Number Conversions and Robust Input 466 8.2 The Standard string Class 472 Introduction to the Standard Class string 472 I/O with the Class string 475 Programming Tip: More Versions of getline 478 Pitfall: Mixing cin " variable; and getline 479 String Processing with the Class string 480 Programming Example: Palindrome Testing 484 Converting Between string Objects and C Strings 487 Converting Between Strings and Numbers 488 8.3 Vectors 489 Vector Basics 489 Pitfall: Using Square Brackets Beyond the Vector Size 492 Programming Tip: Vector Assignment Is Well Behaved 493 Efficiency Issues 493 Chapter Summary 495 Answers to Self-Test Exercises 495 Practice Programs 497 Programming Projects 498 Chapter 9 Pointers and Dynamic Arrays 507 9.1 Pointers 508 Pointer Variables 509 Basic Memory Management 516 Pitfall: Dangling Pointers 517 Static Variables and Automatic Variables 518 Programming Tip: Define Pointer Types 518 9.2 Dynamic Arrays 521 Array Variables and Pointer Variables 521 Creating and Using Dynamic Arrays 522 Pointer Arithmetic (Optional) 528 Multidimensional Dynamic Arrays (Optional) 530 Chapter Summary 532 Answers to Self-Test Exercises 532 Practice Programs 533 Programming Projects 534 Chapter 10 Defining Classes 541 10.1 Structures 542 Structures for Diverse Data 542 Pitfall: Forgetting a Semicolon in a Structure Definition 547 Structures as Function Arguments 548 Programming Tip: Use Hierarchical Structures 549 Initializing Structures 551 10.2 Classes 554 Defining Classes and Member Functions 554 Public and Private Members 559 Programming Tip: Make All Member Variables Private 567 Programming Tip: Define Accessor and Mutator Functions 567 Programming Tip: Use the Assignment Operator with Objects 569 Programming Example: BankAccount Class-Version 1 570 Summary of Some Properties of Classes 574 Constructors for Initialization 576 Programming Tip: Always Include a Default Constructor 584 Pitfall: Constructors with No Arguments 585 Member Initializers and Constructor Delegation in C++11 587 10.3 Abstract Data Types 588 Classes to Produce Abstract Data Types 589 Programming Example: Alternative Implementation of a Class 593 10.4 Introduction to Inheritance 598 Derived Classes 599 Defining Derived Classes 600 Chapter Summary 604 Answers to Self-Test Exercises 605 Practice Programs 611 Programming Projects 612 Chapter 11 Friends, Overloaded Operators, and Arrays in Classes 619 11.1 Friend Functions 620 Programming Example: An Equality Function 620 Friend Functions 624 Programming Tip: Define Both Accessor Functions and Friend Functions 626 Programming Tip: Use Both Member and Nonmember Functions 628 Programming Example: Money Class (Version 1) 628 Implementation of digit_to_int (Optional) 635 Pitfall: Leading Zeros in Number Constants 636 The const Parameter Modifier 638 Pitfall: Inconsistent Use of const 639 11.2 Overloading Operators 643 Overloading Operators 644 Constructors for Automatic Type Conversion 647 Overloading Unary Operators 649 Overloading " and " 650 11.3 Arrays and Classes 660 Arrays of Classes 660 Arrays as Class Members 664 Programming Example: A Class for a Partially Filled Array 665 11.4 Classes and Dynamic Arrays 667 Programming Example: A String Variable Class 668 Destructors 671 Pitfall: Pointers as Call-by-Value Parameters 674 Copy Constructors 675 Overloading the Assignment Operator 680 Chapter Summary 683 Answers to Self-Test Exercises 683 Practice Programs 693 Programming Projects 694 Chapter 12 Separate Compilation and Namespaces 703 12.1 Separate Compilation 704 ADTs Reviewed 705 Case Study: DigitalTime -A Class Compiled Separately 706 Using #ifndef 715 Programming Tip: Defining Other Libraries 718 12.2 Namespaces 719 Namespaces and using Directives 719 Creating a Namespace 721 Qualifying Names 724 A Subtle Point About Namespaces (Optional) 725 Unnamed Namespaces 726 Programming Tip: Choosing a Name for a Namespace 731 Pitfall: Confusing the Global Namespace and the Unnamed Namespace 732 Chapter Summary 733 Answers to Self-Test Exercises 734 Practice Programs 736 Programming Projects 738 Chapter 13 Pointers and Linked Lists 739 13.1 Nodes and Linked Lists 740 Nodes 740 nullptr 745 Linked Lists 746 Inserting a Node at the Head of a List 747 Pitfall: Losing Nodes 750 Searching a Linked List 751 Pointers as Iterators 755 Inserting and Removing Nodes Inside a List 755 Pitfall: Using the Assignment Operator with Dynamic Data Structures 757 Variations on Linked Lists 760 Linked Lists of Classes 762 13.2 Stacks and Queues 765 Stacks 765 Programming Example: A Stack Class 766 Queues 771 Programming Example: A Queue Class 772 Chapter Summary 776 Answers to Self-Test Exercises 776 Practice Programs 779 Programming Projects 780 Chapter 14 Recursion 789 14.1 Recursive Functions for Tasks 791 Case Study: Vertical Numbers 791 A Closer Look at Recursion 797 Pitfall: Infinite Recursion 799 Stacks for Recursion 800 Pitfall: Stack Overflow 802 Recursion Versus Iteration 802 14.2 Recursive Functions for Values 804 General Form for a Recursive Function That Returns a Value 804 Programming Example: Another Powers Function 804 14.3 Thinking Recursively 809 Recursive Design Techniques 809 Case Study: Binary Search-An Example of Recursive Thinking 810 Programming Example: A Recursive Member Function 818 Chapter Summary 822 Answers to Self-Test Exercises 822 Practice Programs 827 Programming Projects 827 Chapter 15 Inheritance 833 15.1 Inheritance Basics 834 Derived Classes 837 Constructors in Derived Classes 845 Pitfall: Use of Private Member Variables from the Base Class 848 Pitfall: Private Member Functions Are Effectively Not Inherited 850 The protected Qualifier 850 Redefinition of Member Functions 853 Redefining Versus Overloading 856 Access to a Redefined Base Function 858 15.2 INHERITANCE DETAILS 859 Functions That Are Not Inherited 859 Assignment Operators and Copy Constructors in Derived Classes 860 Destructors in Derived Classes 861 15.3 Polymorphism 862 Late Binding 863 Virtual Functions in C++ 864 Virtual Functions and Extended Type Compatibility 869 Pitfall: The Slicing Problem 873 Pitfall: Not Using Virtual Member Functions 874 Pitfall: Attempting to Compile Class Definitions Without Definitions for Every Virtual Member Function 875 Programming Tip: Make Destructors Virtual 875 Chapter Summary 877 Answers to Self-Test Exercises 877 Practice Programs 881 Programming Projects 884 Chapter 16 Exception Handling 893 16.1 Exception-Handling Basics 895 A Toy Example of Exception Handling 895 Defining Your Own Exception Classes 904 Multiple Throws and Catches 904 Pitfall: Catch the More Specific Exception First 908 Programming Tip: Exception Classes Can Be Trivial 909 Throwing an Exception in a Function 909 Exception Specification 911 Pitfall: Exception Specification in Derived Classes 913 16.2 Programming Techniques for Exception Handling 914 When to Throw an Exception 914 Pitfall: Uncaught Exceptions 916 Pitfall: Nested try-catch Blocks 916 Pitfall: Overuse of Exceptions 916 Exception Class Hierarchies 917 Testing for Available Memory 917 Rethrowing an Exception 918 Chapter Summary 918 Answers to Self-Test Exercises 918 Practice Programs 920 Programming Projects 921 Chapter 17 Templates 925 17.1 Templates for Algorithm Abstraction 926 Templates for Functions 927 Pitfall: Compiler Complications 931 Programming Example: A Generic Sorting Function 933 Programming Tip: How to Define Templates 937 Pitfall: Using a Template with an Inappropriate Type 938 17.2 Templates for Data Abstraction 939 Syntax for Class Templates 939 Programming Example: An Array Class 942 Chapter Summary 949 Answers to Self-Test Exercises 949 Practice Programs 953 Programming Projects 953 Chapter 18 Standard Template Library 957 18.1 Iterators 959 using Declarations 959 Iterator Basics 960 Programming Tip: Use auto to Simplify Variable Declarations 964 Pitfall: Compiler Problems 964 Kinds of Iterators 966 Constant and Mutable Iterators 970 Reverse Iterators 971 Other Kinds of Iterators 972 18.2 Containers 973 Sequential Containers 974 Pitfall: Iterators and Removing Elements 978 Programming Tip: Type Definitions in Containers 979 Container Adapters stack and queue 979 Associative Containers set and map 983 Programming Tip: Use Initialization, Ranged For, and auto with Containers 990 Efficiency 990 18.3 Generic Algorithms 991 Running Times and Big-O Notation 992 Container Access Running Times 995 Nonmodifying Sequence Algorithms 997 Container Modifying Algorithms 1001 Set Algorithms 1003 Sorting Algorithms 1004 Chapter Summary 1005 Answers to Self-Test Exercises 1005 Practice Programs 1007 Programming Projects 1008 Appendices 1 C++ Keywords 1015 2 Precedence of Operators 1016 3 The ASCII Character Set 1018 4 Some Library Functions 1019 5 Inline Functions 1026 6 Overloading the Array Index Square Brackets 1027 7 The this Pointer 1029 8 Overloading Operators as Member Operators 1032 Index 1034