Problem Solving with C++
International Edition
7th Edition
Published on 27. March 2008
Book
Mixed media product
1072 pages
978-0-321-54940-2 (ISBN)
Description
Now featuring new Video Notes the Seventh Edition ofProblem Solving with C++ continues to be the most widely used textbook by students and instructors in the introduction to programming and C++ language course. Through each edition, hundreds and thousands of students have valued Walt Savitch's approach to programming, which emphasizes active reading through the use of well-placed examples and self-test examples. Created for the beginner, this book focuses on cultivating strong problem-solving and programming techniques while introducing students to the C++ programming language.
More details
Edition
7th edition
Language
English
Place of publication
United States
Publishing group
Pearson Education (US)
Target group
Professional and scholarly
Dimensions
Height: 189 mm
Width: 231 mm
Thickness: 35 mm
Weight
1612 gr
ISBN-13
978-0-321-54940-2 (9780321549402)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Other editions
New editions
Book
05/2011
8th Edition
Pearson Education Limited
€69.17
Article exhausted; check for reprint
Previous edition
Book
04/2006
6th Edition
Pearson
€59.55
Article exhausted; check for reprint
Person
Walter Savitch is Professor Emeritus of Computer Science at the University of California-San Diego. He received his PhD in mathematics from the University of California-Berkeley in 1969. Since that time he has been on the faculty of the University of California-San Diego (UCSD). He served as director of the UCSD Interdisciplinary PhD program in cognitive science for over ten years. He has served as a visiting researcher at the computer science departments of the University of Washington in Seattle and at the University of Colorado in Boulder, and has been a visiting scholar at the Centrum voor Wiskunde en Informatica in Amsterdam.
Kenrick Mock is an Associate Professor at the University of Alaska-Anchorage. He has also taught at Washington Stat University, Portland State University, and the University of California-Davis. He teaches undergraduate computer science courses across the curriculum including introductory C++, Java (TM), Visual Basic (R) for non-programmers, algorithms, computer security, and artificial intelligence. With the Coastal Marine Institute at UAA, he helped develop a computer system to aid in research about Alaska sea ice and the atmosphere. Before becoming a teacher, Mock was a research scientist and software engineer at Intel (TM). He received a PhD in computer science from UC Davis.
Kenrick Mock is an Associate Professor at the University of Alaska-Anchorage. He has also taught at Washington Stat University, Portland State University, and the University of California-Davis. He teaches undergraduate computer science courses across the curriculum including introductory C++, Java (TM), Visual Basic (R) for non-programmers, algorithms, computer security, and artificial intelligence. With the Coastal Marine Institute at UAA, he helped develop a computer system to aid in research about Alaska sea ice and the atmosphere. Before becoming a teacher, Mock was a research scientist and software engineer at Intel (TM). He received a PhD in computer science from UC Davis.
Content
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 17
The Software Life Cycle 17
1.3 INTRODUCTION TO C++ 19
Origins of the C++ Language 19
A Sample C++ Program 20
Pitfall: Using the Wrong Slash in \n 24
Programming Tip: Input and Output Syntax 24
Layout of a Simple C++ Program 24
Pitfall: Putting a Space before the include File Name 26
Compiling and Running a C++ Program 27
Programming Tip: Getting Your Program to Run 27
1.4 TESTING AND DEBUGGING 30
Kinds of Program Errors 30
Pitfall: Assuming Your Program Is Correct 31
Chapter Summary 32
Answers to Self-Test Exercises 33
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
The Type char 63
The Type bool 64
Introduction to the Class string 65
Type Compatibilities 66
Arithmetic Operators and Expressions 69
Pitfall: Whole Numbers in Division 71
More Assignment Statements 73
2.4 SIMPLE FLOW OF CONTROL 74
A Simple Branching Mechanism 74
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 94
Naming Constants 96
Chapter Summary 98
Answers to Self-Test Exercises 99
Programming Projects 104
Chapter 3 More Flow of Control 111
3.1 USING 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 129
Pitfall: Forgetting a break in a switch Statement 133
Using switch Statements for Menus 134
Blocks 134
Pitfall: Inadvertent Local Variables 139
3.3 MORE ABOUT C++ LOOP STATEMENTS 140
The while Statements Reviewed 141
Increment and Decrement Operators Revisited 142
The for Statement 145
Pitfall: Extra Semicolon in a for Statement 150
What Kind of Loop to Use 151
Pitfall: Uninitialized Variables and Infinite Loops 153
The break Statement 153
Pitfall: The break Statement in Nested Loops 155
3.4 DESIGNING LOOPS 156
Loops for Sums and Products 156
Ending a Loop 157
Nested Loops 161
Debugging Loops 163
Chapter Summary 166
Answers to Self-Test Exercises 167
Programming Projects 173
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
Type Casting 188
Older Form of Type Casting 190
Pitfall: Integer Division Drops the Fractional Part 191
4.3 PROGRAMMER-DEFINED FUNCTIONS 192
Function Definitions 192
Functions That Return a Boolean Value 196
Alternate Form for Function Declarations 199
Pitfall: Arguments in the Wrong Order 199
Function Definition-Syntax Summary 201
More About Placement of Function Definitions 202
Programming Tip: Use Function Calls in Branching Statements 202
4.4 PROCEDURAL ABSTRACTION 204
The Black Box Analogy 204
Programming Tip: Choosing Formal Parameter Names 206
Programming Tip: Nested Loops 208
Case Study: Buying Pizza 211
Programming Tip: Use Pseudocode 217
4.5 LOCAL VARIABLES 218
The Small Program Analogy 218
Programming Example: Experimental Pea Patch 220
Global Constants and Global Variables 221
Call-by-Value Formal Parameters Are Local Variables 224
Namespaces Revisited 226
Programming Example: The Factorial Function 229
4.6 OVERLOADING FUNCTION NAMES 230
Introduction to Overloading 231
Programming Example: Revised Pizza-Buying Program 233
Automatic Type Conversion 236
Chapter Summary 239
Answers to Self-Test Exercises 239
Programming Projects 244
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 266
Mixed Parameter Lists 268
Programming Tip: What Kind of Parameter to Use 268
Pitfall: Inadvertent Local Variables 270
5.3 USING PROCEDURAL ABSTRACTION 272
Functions Calling Functions 273
Preconditions and Postconditions 273
Case Study: Supermarket Pricing 274
5.4 TESTING AND DEBUGGING FUNCTIONS 282
Stubs and Drivers 282
5.5 GENERAL DEBUGGING TECHNIQUES 287
Keep an Open Mind 287
Check Common Errors 288
Localize the Error 288
The assert macro 291
Chapter Summary 292
Answers to Self-Test Exercises 293
Programming Projects 297
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 313
Techniques for File I/O 316
Appending to a File (Optional) 320
File Names as Input (Optional) 320
6.2 TOOLS FOR STREAM I/O 323
Formatting Output with Stream Functions 323
Manipulators 328
Streams as Arguments to Functions 332
Programming Tip: Checking for the End of a File 332
A Note on Namespaces 336
Programming Example: Cleaning Up a File Format 337
6.3 CHARACTER I/O 338
The Member Functions get and put 339
The putback Member Function (Optional) 342
Programming Example: Checking Input 343
Pitfall: Unexpected '\n' in Input 346
The eof Member Function 349
Programming Example: Editing a Text File 352
Predefined Character Functions 352
Pitfall: toupper and tolower Return Values 355
Chapter Summary 357
Answers to Self-Test Exercises 359
Programming Projects 364
Chapter 7 Arrays 375
7.1 INTRODUCTION TO ARRAYS 376
Declaring and Referencing Arrays 376
Programming Tip: Use for Loops with Arrays 378
Pitfall: Array Indexes Always Start with Zero 378
Programming Tip: Use a Defined Constant for the Size of an Array 378
Arrays in Memory 380
Pitfall: Array Index Out of Range 381
Initializing Arrays 383
7.2 ARRAYS IN FUNCTIONS 385
Indexed Variables as Function Arguments 385
Entire Arrays as Function Arguments 388
The const Parameter Modifier 391
Pitfall: Inconsistent Use of const Parameters 393
Functions That Return an Array 394
Case Study: Production Graph 394
7.3 PROGRAMMING WITH ARRAYS 408
Partially Filled Arrays 408
Programming Tip: Do Not Skimp on Formal Parameters 411
Programming Example: Searching an Array 412
Programming Example: Sorting an Array 414
7.4 MULTIDIMENSIONAL ARRAYS 419
Multidimensional Array Basics 420
Multidimensional Array Parameters 420
Programming Example: Two-Dimensional Grading Program 422
Pitfall: Using Commas Between Array Indexes 427
Chapter Summary 427
Answers to Self-Test Exercises 428
Programming Projects 433
Chapter 8 Strings and Vectors 445
8.1 AN ARRAY TYPE FOR STRINGS 447
C-String Values and C-String Variables 447
Pitfall: Using = and == with C Strings 451
Other Functions in 453
C-String Input and Output 457
C-String-to-Number Conversions and Robust Input 460
8.2 THE STANDARD string CLASS 465
Introduction to the Standard Class string 465
I/O with the Class string 468
Programming Tip: More Versions of getline 472
Pitfall: Mixing cin >> variable; and getline 472
String Processing with the Class string 474
Programming Example: Palindrome Testing 476
Converting between string Objects and C Strings 481
8.3 VECTORS 482
Vector Basics 482
Pitfall: Using Square Brackets Beyond the Vector Size 484
Programming Tip: Vector Assignment Is Well Behaved 486
Efficiency Issues 487
Chapter Summary 488
Answers to Self-Test Exercises 489
Programming Projects 491
Chapter 9 Pointers and Dynamic Arrays 499
9.1 POINTERS 500
Pointer Variables 501
Basic Memory Management 508
Pitfall: Dangling Pointers 509
Static Variables and Automatic Variables 510
Programming Tip: Define Pointer Types 510
9.2 DYNAMIC ARRAYS 513
Array Variables and Pointer Variables 513
Creating and Using Dynamic Arrays 513
Pointer Arithmetic (Optional) 519
Multidimensional Dynamic Arrays (Optional) 521
Chapter Summary 523
Answers to Self-Test Exercises 523
Programming Projects 524
Chapter 10 Defining Classes 529
10.1 STRUCTURES 530
Structures for Diverse Data 530
Pitfall: Forgetting a Semicolon in a Structure Definition 535
Structures as Function Arguments 536
Programming Tip: Use Hierarchical Structures 537
Initializing Structures 539
10.2 CLASSES 542
Defining Classes and Member Functions 542
Public and Private Members 547
Programming Tip: Make All Member Variables Private 555
Programming Tip: Define Accessor and Mutator Functions 555
Programming Tip: Use the Assignment Operator with Objects 557
Programming Example: BankAccount Class-Version 1 557
Summary of Some Properties of Classes 562
Constructors for Initialization 564
Programming Tip: Always Include a Default Constructor 572
Pitfall: Constructors with No Arguments 573
10.3 ABSTRACT DATA TYPES 575
Classes to Produce Abstract Data Types 576
Programming Example: Alternative Implementation of a Class 580
10.4 INTRODUCTION TO INHERITANCE 584
Inheritance Among Stream Classes 585
Programming Example: Another new_line Function 588
Default Arguments for Functions (Optional) 589
Defining Derived Classes 591
Chapter Summary 594
Answers to Self-Test Exercises 595
Programming Projects 603
Chapter 11 Friends, Overloaded Operators, and
Arrays in Classes 609
11.1 FRIEND FUNCTIONS 610
Programming Example: An Equality Function 610
Friend Functions 614
Programming Tip: Define Both Accessor Functions and Friend
Functions 616
Programming Tip: Use Both Member and Nonmember Functions 618
Programming Example: Money Class (Version 1) 618
Implementation of digit_to_int (Optional) 625
Pitfall: Leading Zeros in Number Constants 626
The const Parameter Modifier 628
Pitfall: Inconsistent Use of const 630
11.2 OVERLOADING OPERATORS 633
Overloading Operators 634
Constructors for Automatic Type Conversion 638
Overloading Unary Operators 640
Overloading >> and << 640
11.3 ARRAYS AND CLASSES 651
Arrays of Classes 651
Arrays as Class Members 655
Programming Example: A Class for a Partially Filled Array 656
11.4 CLASSES AND DYNAMIC ARRAYS 659
Programming Example: A String Variable Class 659
Destructors 663
Pitfall: Pointers as Call-by-Value Parameters 665
Copy Constructors 667
Overloading the Assignment Operator 672
Chapter Summary 675
Answers to Self-Test Exercises 676
Programming Projects 686
Chapter 12 Separate Compilation and Namespaces 695
12.1 SEPARATE COMPILATION 696
ADTs Reviewed 697
Case Study: DigitalTime-A Class Compiled Separately 698
Using #ifndef 707
Programming Tip: Defining Other Libraries 710
12.2 NAMESPACES 712
Namespaces and using Directives 712
Creating a Namespace 714
Qualifying Names 717
A Subtle Point About Namespaces (Optional) 718
Unnamed Namespaces 719
Programming Tip: Choosing a Name for a Namespace 722
Pitfall: Confusing the Global Namespace and the Unnamed
Namespace 724
Chapter Summary 727
Answers to Self-Test Exercises 727
Programming Projects 729
Chapter 13 Pointers and Linked Lists 733
13.1 NODES AND LINKED LISTS 734
Nodes 734
Linked Lists 740
Inserting a Node at the Head of a List 741
Pitfall: Losing Nodes 744
Searching a Linked List 745
Pointers as Iterators 749
Inserting and Removing Nodes Inside a List 749
Pitfall: Using the Assignment Operator with Dynamic
Data Structures 752
Variations on Linked Lists 754
Linked Lists of Classes 756
13.2 STACKS AND QUEUES 760
Stacks 760
Programming Example: A Stack Class 761
Queues 766
Programming Example: A Queue Class 767
Chapter Summary 771
Answers to Self-Test Exercises 772
Programming Projects 775
Chapter 14 Recursion 781
14.1 RECURSIVE FUNCTIONS FOR TASKS 783
Case Study: Vertical Numbers 783
A Closer Look at Recursion 790
Pitfall: Infinite Recursion 791
Stacks for Recursion 793
Pitfall: Stack Overflow 794
Recursion Versus Iteration 795
14.2 RECURSIVE FUNCTIONS FOR VALUES 796
General Form for a Recursive Function That Returns a Value 796
Programming Example: Another Powers Function 797
14.3 THINKING RECURSIVELY 801
Recursive Design Techniques 801
Case Study: Binary Search-An Example of Recursive Thinking 803
Programming Example: A Recursive Member Function 810
Chapter Summary 815
Answers to Self-Test Exercises 815
Programming Projects 820
Chapter 15 Inheritance 825
15.1 INHERITANCE BASICS 826
Derived Classes 827
Constructors in Derived Classes 835
Pitfall: Use of Private Member Variables from the Base Class 838
Pitfall: Private Member Functions Are Effectively Not Inherited 840
The protected Qualifier 840
Redefinition of Member Functions 843
Redefining Versus Overloading 847
Access to a Redefined Base Function 848
15.2 INHERITANCE DETAILS 849
Functions That Are Not Inherited 850
Assignment Operators and Copy Constructors in Derived Classes 850
Destructors in Derived Classes 851
15.3 POLYMORPHISM 853
Late Binding 853
Virtual Functions in C++ 854
Virtual Functions and Extended Type Compatibility 860
Pitfall: The Slicing Problem 864
Pitfall: Not Using Virtual Member Functions 864
Pitfall: Attempting to Compile Class Definitions Without Definitions for
Every Virtual Member Function 865
Programming Tip: Make Destructors Virtual 866
Chapter Summary 867
Answers to Self-Test Exercises 868
Programming Projects 872
Chapter 16 Exception Handling 881
16.1 EXCEPTION-HANDLING BASICS 883
A Toy Example of Exception Handling 883
Defining Your Own Exception Classes 892
Multiple Throws and Catches 892
Pitfall: Catch the More Specific Exception First 896
Programming Tip: Exception Classes Can Be Trivial 897
Throwing an Exception in a Function 898
Exception Specification 898
Pitfall: Exception Specification in Derived Classes 902
16.2 PROGRAMMING TECHNIQUES FOR
EXCEPTION HANDLING 903
When to Throw an Exception 903
Pitfall: Uncaught Exceptions 905
Pitfall: Nested try-catch Blocks 905
Pitfall: Overuse of Exceptions 905
Exception Class Hierarchies 906
Testing for Available Memory 906
Rethrowing an Exception 907
Chapter Summary 907
Answers to Self-Test Exercises 907
Programming Projects 909
Chapter 17 Templates 913
17.1 TEMPLATES FOR ALGORITHM ABSTRACTION 914
Templates for Functions 915
Pitfall: Compiler Complications 919
Programming Example: A Generic Sorting Function 921
Programming Tip: How to Define Templates 925
Pitfall: Using a Template with an Inappropriate Type 926
17.2 TEMPLATES FOR DATA ABSTRACTION 927
Syntax for Class Templates 927
Programming Example: An Array Class 930
Chapter Summary 936
Answers to Self-Test Exercises 936
Programming Projects 939
Chapter 18 Standard Template Library 943
18.1 ITERATORS 945
Using Declarations 945
Iterator Basics 946
Pitfall: Compiler Problems 951
Kinds of Iterators 952
Constant and Mutable Iterators 956
Reverse Iterators 957
Other Kinds of Iterators 959
18.2 CONTAINERS 960
Sequential Containers 960
Pitfall: Iterators and Removing Elements 965
Programming Tip: Type Definitions in Containers 965
Container Adapters stack and queue 966
Associative Containers set and map 970
Efficiency 976
18.3 GENERIC ALGORITHMS 977
Running Times and Big-O Notation 978
Container Access Running Times 982
Nonmodifying Sequence Algorithms 983
Container Modifying Algorithms 989
Set Algorithms 989
Sorting Algorithms 991
Chapter Summary 991
Answers to Self-Test Exercises 992
Programming Projects 994
APPENDICES
1 C++ Keywords 999
2 Precedence of Operators 1000
3 The ASCII Character Set 1002
4 Some Library Functions 1003
5 Inline Functions 1011
6 Overloading the Array Index Square Brackets 1012
7 The this Pointer 1014
8 Overloading Operators as Member Operators 1017
INDEX 1019
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 17
The Software Life Cycle 17
1.3 INTRODUCTION TO C++ 19
Origins of the C++ Language 19
A Sample C++ Program 20
Pitfall: Using the Wrong Slash in \n 24
Programming Tip: Input and Output Syntax 24
Layout of a Simple C++ Program 24
Pitfall: Putting a Space before the include File Name 26
Compiling and Running a C++ Program 27
Programming Tip: Getting Your Program to Run 27
1.4 TESTING AND DEBUGGING 30
Kinds of Program Errors 30
Pitfall: Assuming Your Program Is Correct 31
Chapter Summary 32
Answers to Self-Test Exercises 33
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
The Type char 63
The Type bool 64
Introduction to the Class string 65
Type Compatibilities 66
Arithmetic Operators and Expressions 69
Pitfall: Whole Numbers in Division 71
More Assignment Statements 73
2.4 SIMPLE FLOW OF CONTROL 74
A Simple Branching Mechanism 74
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 94
Naming Constants 96
Chapter Summary 98
Answers to Self-Test Exercises 99
Programming Projects 104
Chapter 3 More Flow of Control 111
3.1 USING 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 129
Pitfall: Forgetting a break in a switch Statement 133
Using switch Statements for Menus 134
Blocks 134
Pitfall: Inadvertent Local Variables 139
3.3 MORE ABOUT C++ LOOP STATEMENTS 140
The while Statements Reviewed 141
Increment and Decrement Operators Revisited 142
The for Statement 145
Pitfall: Extra Semicolon in a for Statement 150
What Kind of Loop to Use 151
Pitfall: Uninitialized Variables and Infinite Loops 153
The break Statement 153
Pitfall: The break Statement in Nested Loops 155
3.4 DESIGNING LOOPS 156
Loops for Sums and Products 156
Ending a Loop 157
Nested Loops 161
Debugging Loops 163
Chapter Summary 166
Answers to Self-Test Exercises 167
Programming Projects 173
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
Type Casting 188
Older Form of Type Casting 190
Pitfall: Integer Division Drops the Fractional Part 191
4.3 PROGRAMMER-DEFINED FUNCTIONS 192
Function Definitions 192
Functions That Return a Boolean Value 196
Alternate Form for Function Declarations 199
Pitfall: Arguments in the Wrong Order 199
Function Definition-Syntax Summary 201
More About Placement of Function Definitions 202
Programming Tip: Use Function Calls in Branching Statements 202
4.4 PROCEDURAL ABSTRACTION 204
The Black Box Analogy 204
Programming Tip: Choosing Formal Parameter Names 206
Programming Tip: Nested Loops 208
Case Study: Buying Pizza 211
Programming Tip: Use Pseudocode 217
4.5 LOCAL VARIABLES 218
The Small Program Analogy 218
Programming Example: Experimental Pea Patch 220
Global Constants and Global Variables 221
Call-by-Value Formal Parameters Are Local Variables 224
Namespaces Revisited 226
Programming Example: The Factorial Function 229
4.6 OVERLOADING FUNCTION NAMES 230
Introduction to Overloading 231
Programming Example: Revised Pizza-Buying Program 233
Automatic Type Conversion 236
Chapter Summary 239
Answers to Self-Test Exercises 239
Programming Projects 244
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 266
Mixed Parameter Lists 268
Programming Tip: What Kind of Parameter to Use 268
Pitfall: Inadvertent Local Variables 270
5.3 USING PROCEDURAL ABSTRACTION 272
Functions Calling Functions 273
Preconditions and Postconditions 273
Case Study: Supermarket Pricing 274
5.4 TESTING AND DEBUGGING FUNCTIONS 282
Stubs and Drivers 282
5.5 GENERAL DEBUGGING TECHNIQUES 287
Keep an Open Mind 287
Check Common Errors 288
Localize the Error 288
The assert macro 291
Chapter Summary 292
Answers to Self-Test Exercises 293
Programming Projects 297
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 313
Techniques for File I/O 316
Appending to a File (Optional) 320
File Names as Input (Optional) 320
6.2 TOOLS FOR STREAM I/O 323
Formatting Output with Stream Functions 323
Manipulators 328
Streams as Arguments to Functions 332
Programming Tip: Checking for the End of a File 332
A Note on Namespaces 336
Programming Example: Cleaning Up a File Format 337
6.3 CHARACTER I/O 338
The Member Functions get and put 339
The putback Member Function (Optional) 342
Programming Example: Checking Input 343
Pitfall: Unexpected '\n' in Input 346
The eof Member Function 349
Programming Example: Editing a Text File 352
Predefined Character Functions 352
Pitfall: toupper and tolower Return Values 355
Chapter Summary 357
Answers to Self-Test Exercises 359
Programming Projects 364
Chapter 7 Arrays 375
7.1 INTRODUCTION TO ARRAYS 376
Declaring and Referencing Arrays 376
Programming Tip: Use for Loops with Arrays 378
Pitfall: Array Indexes Always Start with Zero 378
Programming Tip: Use a Defined Constant for the Size of an Array 378
Arrays in Memory 380
Pitfall: Array Index Out of Range 381
Initializing Arrays 383
7.2 ARRAYS IN FUNCTIONS 385
Indexed Variables as Function Arguments 385
Entire Arrays as Function Arguments 388
The const Parameter Modifier 391
Pitfall: Inconsistent Use of const Parameters 393
Functions That Return an Array 394
Case Study: Production Graph 394
7.3 PROGRAMMING WITH ARRAYS 408
Partially Filled Arrays 408
Programming Tip: Do Not Skimp on Formal Parameters 411
Programming Example: Searching an Array 412
Programming Example: Sorting an Array 414
7.4 MULTIDIMENSIONAL ARRAYS 419
Multidimensional Array Basics 420
Multidimensional Array Parameters 420
Programming Example: Two-Dimensional Grading Program 422
Pitfall: Using Commas Between Array Indexes 427
Chapter Summary 427
Answers to Self-Test Exercises 428
Programming Projects 433
Chapter 8 Strings and Vectors 445
8.1 AN ARRAY TYPE FOR STRINGS 447
C-String Values and C-String Variables 447
Pitfall: Using = and == with C Strings 451
Other Functions in 453
C-String Input and Output 457
C-String-to-Number Conversions and Robust Input 460
8.2 THE STANDARD string CLASS 465
Introduction to the Standard Class string 465
I/O with the Class string 468
Programming Tip: More Versions of getline 472
Pitfall: Mixing cin >> variable; and getline 472
String Processing with the Class string 474
Programming Example: Palindrome Testing 476
Converting between string Objects and C Strings 481
8.3 VECTORS 482
Vector Basics 482
Pitfall: Using Square Brackets Beyond the Vector Size 484
Programming Tip: Vector Assignment Is Well Behaved 486
Efficiency Issues 487
Chapter Summary 488
Answers to Self-Test Exercises 489
Programming Projects 491
Chapter 9 Pointers and Dynamic Arrays 499
9.1 POINTERS 500
Pointer Variables 501
Basic Memory Management 508
Pitfall: Dangling Pointers 509
Static Variables and Automatic Variables 510
Programming Tip: Define Pointer Types 510
9.2 DYNAMIC ARRAYS 513
Array Variables and Pointer Variables 513
Creating and Using Dynamic Arrays 513
Pointer Arithmetic (Optional) 519
Multidimensional Dynamic Arrays (Optional) 521
Chapter Summary 523
Answers to Self-Test Exercises 523
Programming Projects 524
Chapter 10 Defining Classes 529
10.1 STRUCTURES 530
Structures for Diverse Data 530
Pitfall: Forgetting a Semicolon in a Structure Definition 535
Structures as Function Arguments 536
Programming Tip: Use Hierarchical Structures 537
Initializing Structures 539
10.2 CLASSES 542
Defining Classes and Member Functions 542
Public and Private Members 547
Programming Tip: Make All Member Variables Private 555
Programming Tip: Define Accessor and Mutator Functions 555
Programming Tip: Use the Assignment Operator with Objects 557
Programming Example: BankAccount Class-Version 1 557
Summary of Some Properties of Classes 562
Constructors for Initialization 564
Programming Tip: Always Include a Default Constructor 572
Pitfall: Constructors with No Arguments 573
10.3 ABSTRACT DATA TYPES 575
Classes to Produce Abstract Data Types 576
Programming Example: Alternative Implementation of a Class 580
10.4 INTRODUCTION TO INHERITANCE 584
Inheritance Among Stream Classes 585
Programming Example: Another new_line Function 588
Default Arguments for Functions (Optional) 589
Defining Derived Classes 591
Chapter Summary 594
Answers to Self-Test Exercises 595
Programming Projects 603
Chapter 11 Friends, Overloaded Operators, and
Arrays in Classes 609
11.1 FRIEND FUNCTIONS 610
Programming Example: An Equality Function 610
Friend Functions 614
Programming Tip: Define Both Accessor Functions and Friend
Functions 616
Programming Tip: Use Both Member and Nonmember Functions 618
Programming Example: Money Class (Version 1) 618
Implementation of digit_to_int (Optional) 625
Pitfall: Leading Zeros in Number Constants 626
The const Parameter Modifier 628
Pitfall: Inconsistent Use of const 630
11.2 OVERLOADING OPERATORS 633
Overloading Operators 634
Constructors for Automatic Type Conversion 638
Overloading Unary Operators 640
Overloading >> and << 640
11.3 ARRAYS AND CLASSES 651
Arrays of Classes 651
Arrays as Class Members 655
Programming Example: A Class for a Partially Filled Array 656
11.4 CLASSES AND DYNAMIC ARRAYS 659
Programming Example: A String Variable Class 659
Destructors 663
Pitfall: Pointers as Call-by-Value Parameters 665
Copy Constructors 667
Overloading the Assignment Operator 672
Chapter Summary 675
Answers to Self-Test Exercises 676
Programming Projects 686
Chapter 12 Separate Compilation and Namespaces 695
12.1 SEPARATE COMPILATION 696
ADTs Reviewed 697
Case Study: DigitalTime-A Class Compiled Separately 698
Using #ifndef 707
Programming Tip: Defining Other Libraries 710
12.2 NAMESPACES 712
Namespaces and using Directives 712
Creating a Namespace 714
Qualifying Names 717
A Subtle Point About Namespaces (Optional) 718
Unnamed Namespaces 719
Programming Tip: Choosing a Name for a Namespace 722
Pitfall: Confusing the Global Namespace and the Unnamed
Namespace 724
Chapter Summary 727
Answers to Self-Test Exercises 727
Programming Projects 729
Chapter 13 Pointers and Linked Lists 733
13.1 NODES AND LINKED LISTS 734
Nodes 734
Linked Lists 740
Inserting a Node at the Head of a List 741
Pitfall: Losing Nodes 744
Searching a Linked List 745
Pointers as Iterators 749
Inserting and Removing Nodes Inside a List 749
Pitfall: Using the Assignment Operator with Dynamic
Data Structures 752
Variations on Linked Lists 754
Linked Lists of Classes 756
13.2 STACKS AND QUEUES 760
Stacks 760
Programming Example: A Stack Class 761
Queues 766
Programming Example: A Queue Class 767
Chapter Summary 771
Answers to Self-Test Exercises 772
Programming Projects 775
Chapter 14 Recursion 781
14.1 RECURSIVE FUNCTIONS FOR TASKS 783
Case Study: Vertical Numbers 783
A Closer Look at Recursion 790
Pitfall: Infinite Recursion 791
Stacks for Recursion 793
Pitfall: Stack Overflow 794
Recursion Versus Iteration 795
14.2 RECURSIVE FUNCTIONS FOR VALUES 796
General Form for a Recursive Function That Returns a Value 796
Programming Example: Another Powers Function 797
14.3 THINKING RECURSIVELY 801
Recursive Design Techniques 801
Case Study: Binary Search-An Example of Recursive Thinking 803
Programming Example: A Recursive Member Function 810
Chapter Summary 815
Answers to Self-Test Exercises 815
Programming Projects 820
Chapter 15 Inheritance 825
15.1 INHERITANCE BASICS 826
Derived Classes 827
Constructors in Derived Classes 835
Pitfall: Use of Private Member Variables from the Base Class 838
Pitfall: Private Member Functions Are Effectively Not Inherited 840
The protected Qualifier 840
Redefinition of Member Functions 843
Redefining Versus Overloading 847
Access to a Redefined Base Function 848
15.2 INHERITANCE DETAILS 849
Functions That Are Not Inherited 850
Assignment Operators and Copy Constructors in Derived Classes 850
Destructors in Derived Classes 851
15.3 POLYMORPHISM 853
Late Binding 853
Virtual Functions in C++ 854
Virtual Functions and Extended Type Compatibility 860
Pitfall: The Slicing Problem 864
Pitfall: Not Using Virtual Member Functions 864
Pitfall: Attempting to Compile Class Definitions Without Definitions for
Every Virtual Member Function 865
Programming Tip: Make Destructors Virtual 866
Chapter Summary 867
Answers to Self-Test Exercises 868
Programming Projects 872
Chapter 16 Exception Handling 881
16.1 EXCEPTION-HANDLING BASICS 883
A Toy Example of Exception Handling 883
Defining Your Own Exception Classes 892
Multiple Throws and Catches 892
Pitfall: Catch the More Specific Exception First 896
Programming Tip: Exception Classes Can Be Trivial 897
Throwing an Exception in a Function 898
Exception Specification 898
Pitfall: Exception Specification in Derived Classes 902
16.2 PROGRAMMING TECHNIQUES FOR
EXCEPTION HANDLING 903
When to Throw an Exception 903
Pitfall: Uncaught Exceptions 905
Pitfall: Nested try-catch Blocks 905
Pitfall: Overuse of Exceptions 905
Exception Class Hierarchies 906
Testing for Available Memory 906
Rethrowing an Exception 907
Chapter Summary 907
Answers to Self-Test Exercises 907
Programming Projects 909
Chapter 17 Templates 913
17.1 TEMPLATES FOR ALGORITHM ABSTRACTION 914
Templates for Functions 915
Pitfall: Compiler Complications 919
Programming Example: A Generic Sorting Function 921
Programming Tip: How to Define Templates 925
Pitfall: Using a Template with an Inappropriate Type 926
17.2 TEMPLATES FOR DATA ABSTRACTION 927
Syntax for Class Templates 927
Programming Example: An Array Class 930
Chapter Summary 936
Answers to Self-Test Exercises 936
Programming Projects 939
Chapter 18 Standard Template Library 943
18.1 ITERATORS 945
Using Declarations 945
Iterator Basics 946
Pitfall: Compiler Problems 951
Kinds of Iterators 952
Constant and Mutable Iterators 956
Reverse Iterators 957
Other Kinds of Iterators 959
18.2 CONTAINERS 960
Sequential Containers 960
Pitfall: Iterators and Removing Elements 965
Programming Tip: Type Definitions in Containers 965
Container Adapters stack and queue 966
Associative Containers set and map 970
Efficiency 976
18.3 GENERIC ALGORITHMS 977
Running Times and Big-O Notation 978
Container Access Running Times 982
Nonmodifying Sequence Algorithms 983
Container Modifying Algorithms 989
Set Algorithms 989
Sorting Algorithms 991
Chapter Summary 991
Answers to Self-Test Exercises 992
Programming Projects 994
APPENDICES
1 C++ Keywords 999
2 Precedence of Operators 1000
3 The ASCII Character Set 1002
4 Some Library Functions 1003
5 Inline Functions 1011
6 Overloading the Array Index Square Brackets 1012
7 The this Pointer 1014
8 Overloading Operators as Member Operators 1017
INDEX 1019