Absolute C++

Walter Savitch is Professor Emeritus of Computer Science at the University of California at San Diego. He received his PhD in mathematics from the University of California at Berkeley in 1969. Since that time he has been on the faculty of the University of California in 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 and at the University of Colorado in Boulder, and has been a visiting scholar at the Centrum voor Wiskunde en Informatica in Amsterdam.

>Contents

Chapter 1 C++ Basics   1

1.1 Introduction to C++ 2

Origins of the C++ Language 2

C++ and Object-Oriented Programming 3

The Character of C++ 3

C++ Terminology   4

A Sample C++ Program   4

1.2 Variables, Expressions, and Assignment Statements   6

Identifiers   6

Variables   8

Assignment Statements   10

Pitfall: Uninitialized Variables   12

Tip: Use Meaningful Names   13

More Assignment Statements 13

Assignment Compatibility   14

Literals   15

Escape Sequences   17

Naming Constants   17

Arithmetic Operators and Expressions   19

Integer and Floating-Point Division   21

Pitfall: Division with Whole Numbers   22

Type Casting   22

Increment and Decrement Operators   25

Pitfall: Order of Evaluation   27

1.3 Console Input/Output   28

Output Using cout   28

New Lines in Output   29

Tip: End Each Program with /n or endl   30

Formatting for Numbers with a Decimal Point   31

Output with cerr   32

Input Using cin   32

Tip: Line Breaks in I/O 34

1.4 Program Style   34

Comments   35

1.5 Libraries and Namespaces   35

Libraries and include Directives   36

Namespaces   36

Pitfall: Problems with Library Names   37

Chapter Summary:   38

Answers to Self-Test Exercises   39

Programming Projects   40



Chapter 2 Flow of Control   43

2.1 Boolean Expressions   44

Building Boolean Expressions   44

Pitfall: Strings of Inequalities   45

Evaluating Boolean Expressions   46

Precedence Rules   48

Pitfall: Integer Values Can Be Used as Boolean Values   52

2.2 Branching Mechanisms   54

if-else Statements   54

Compound Statements   56

Pitfall: Using = in Place of ==   57

Omitting the else   59

Nested Statements   59

Multiway if-else Statement   59

The switch Statement   60

Pitfall: Forgetting a break in a switch Statement   63

Tip: Use switch Statements for Menus   63

Enumeration Types   64

The Conditional Operator   64

2.3 Loops   65

The while and do-while Statements   66

Increment and Decrement Operators Revisited   68

The Comma Operator   70

The for Statement   72

Tip: Repeat-N-Times Loops   74

Pitfall: Extra Semicolon in a for Statement   75

Pitfall: Infinite Loops   75

The break and continue Statements   78

Nested Loops   81

2.4 Introduction to File Input

Reading From a Text File Using ifstream

Chapter Summary   81

Answers to Self-Test Exercises   82

Programming Projects   87



Chapter 3 Function Basics   91

3.1 Predefined Functions   92

Predefined Functions That Return a Value   92

Predefined void Functions   97

A Random Number Generator   99

3.2 Programmer-Defined Functions   103

Defining Functions That Return a Value   103

Alternate Form for Function Declarations   106

Pitfall: Arguments in the Wrong Order   107

Pitfall: Use of the Terms Parameter and Argument   107

Functions Calling Functions   107

Example: A Rounding Function   107

Functions That Return a Boolean Value   110

Defining void Functions   111

return Statements in void Functions   113

Preconditions and Postconditions   113

main Is a Function   115

Recursive Functions   116

3.3 Scope Rules   117

Local Variables   117

Procedural Abstraction   120

Global Constants and Global Variables   121

Blocks   124

Nested Scopes   124

Tip: Use Function Calls in Branching and Loop Statements   125

Variables Declared in a for Loop   125

Chapter Summary   126

Answers to Self-Test Exercises   126

Programming Projects   130



Chapter 4 Parameters and Overloading   137

4.1 Parameters   138

Call-by-Value Parameters   138

A First Look at Call-by-Reference Parameters   141

Call-by-Reference Mechanism in Detail   143

Constant Reference Parameters   145

Example: The swapValues Function   146

Tip: Think of Actions, Not Code   147

Mixed Parameter Lists   148

Tip: What Kind of Parameter to Use   149

Pitfall: Inadvertent Local Variables   151

Tip: Choosing Formal Parameter Names   153

Example: Buying Pizza   153

4.2 Overloading and Default Arguments   156

Introduction to Overloading   156

Pitfall: Automatic Type Conversion and Overloading   159

Rules for Resolving Overloading   160

Example: Revised Pizza-Buying Program   162

Default Arguments   164

4.3 Testing and Debugging Functions   166

The assert Macro   166

Stubs and Drivers   167

Chapter Summary   170

Answers to Self-Test Exercises   171

Programming Projects   172



Chapter 5 Arrays   177

5.1 Introduction to Arrays   178

Declaring and Referencing Arrays   178

Tip: Use for Loops with Arrays   181

Pitfall: Array Indexes Always Start with Zero   181

Tip: Use a Defined Constant for the Size of an Array   181

Arrays in Memory   182

Pitfall: Array Index Out of Range   184

Initializing Arrays   184

5.2 Arrays in Functions   187

Indexed Variables as Function Arguments   187

Entire Arrays as Function Arguments   188

The const Parameter Modifier   192

Pitfall: Inconsistent Use of const Parameters   193

Functions That Return an Array   194

Example: Production Graph   194

5.3 Programming with Arrays   200

Partially Filled Arrays   200

Tip: Do Not Skimp on Formal Parameters   200

Example: Searching an Array   203

Example: Sorting an Array   205

5.3 Multidimensional Arrays   210

Multidimensional Array Basics   210

Multidimensional Array Parameters   212

Example: Two-Dimensional Grading Program   213

Chapter Summary   218

Answers to Self-Test Exercises   219

Programming projects   223

Chapter 6 Structures and Classes 231

6.1 Structures   232

Structure Types 234

Pitfall: Forgetting a Semicolon in a Structure Definition   238

Structures as Function Arguments   238

Tip: Use Hierarchical Structures   239

Initializing Structures   242

6.2 Classes   244

Defining Classes and Member Functions   244

Encapsulation   250

Public and Private Members   251

Accessor and Mutator Functions   255

Tip: Separate Interface and Implementation   257

Tip: A Test for Encapsulation   258

Structures versus Classes   259

Tip: Thinking Objects   261

Chapter Summary   261

Answers to Self-Tesr Exercises   262

Programming Projects   264

Chapter 7 Constructors and Other Tools   267

7.1 Constructors   268

Constructor Definitions   268

Pitfall: Constructors with No Arguments   273

Explicit Constructor Calls   275

Tip: Always Include a Default Constructor   275

Example: BankAccount Class   278

Class Type Member Variables   285

7.2 More Tools   288

The const Parameter Modifier   288

Pitfall: Inconsistent Use of const   290

Inline Functions   295

Static Members   297

Nested and Local Class Definitions   300

7.3 Vectors—A Preview of the Standard Template
Library   301

Vector Basics   301

Pitfall: Using Square Brackets beyond the Vector Size   303

Tip: Vector Assignment Is Well Behaved   305

Efficiency Issues   305

Chapter Summary   307

Answers to Self-Test Exercises   307

Programming Projects   309

Chapter 8 Operator Overloading, Friends, and References   315

8.1 Basic Operator Overloading   316

Overloading Basics   317

Tip: A Constructor Can Return an Object   322

Returning by const Value   323

Tip: Returning Member Variables of a Class Type   326

Overloading Unary Operators   327

Overloading as Member Functions   328

Tip: A Class Has Access to All Its Objects   330

Overloading Function Application ( )   331

Pitfall: Overloading &&, ||, and the Comma Operator   331

8.2 Friend Functions and Automatic Type Conversion   332

Constructors for Automatic Type Conversion   332

Pitfall: Member Operators and Automatic Type Conversion   333

Friend Functions   334

Friend Classes   336

Pitfall: Compilers without Friends   338

8.3 References and More Overloaded Operators   339

References   339

Pitfall: Returning a Reference to Certain Member Variables 341

Overloading >> and <<   341

Tip: What Mode of Returned Value to Use   348

The Assignment Operator   350

Overloading the Increment and Decrement Operators   351

Overloading the Array Operator [ ]   354

Overloading Based on L-Value versus R-Value   356

Chapter Summary   356

Answers to Self-Test Exercises   356

Programming Projects   359



Chapter 9 Strings   363

9.1 An Array Type for Strings   364

C-String Values and C-String Variables   365

Pitfall: Using = and == with C-strings   369

Other Functions in    370

Example: Command-Line Arguments   373

C-String Input and Output   375

9.2 Character Manipulation Tools 378

Character I/O   378

The Member Functions get and put   379

Example: Checking Input Using a Newline Function   381

Pitfall: Unexpected '/n' in Input   383

The putback, peek, and ignore Member Functions   384

Character-Manipulating Functions   387

Pitfall: toupper and tolower Return int Values   389

9.3 The Standard Class string   390

Introduction to the Standard Class string   391

I/O with the Class string   394

Tip: More Versions of getline   397

Pitfall: Mixing cin >> variable; and getline   398

String Processing with the Class string   399

Example: Palindrome Testing   403

Converting between string Objects and C-Strings   407

Chapter Summary   407

Answers to Self-Test Exercises 408

Programming Projects 412

Chapter 10 Pointers and Dynamic Arrays   419

10.1 Pointers   420

Pointer Variables   421

Basic Memory Management   429

Pitfall: Dangling Pointers   432

Dynamic Variables and Automatic Variables   432

Tip: Define Pointer Types   433

Pitfall: Pointers as Call-by-Value Parameters   435

Uses for Pointers   437

10.2 Dynamic Arrays   438

Array Variables and Pointer Variables   438

Creating and Using Dynamic Arrays   439

Example: A Function That Returns an Array   443

Pointer Arithmetic   445

Multidimensional Dynamic Arrays   446

10.3 Classes, Pointers, and Dynamic Arrays   449

The -> Operator   449

The this Pointer   450

Overloading the Assignment Operator   451

Example: A Class for Partially Filled Arrays   453

Destructors   462

Copy Constructors   463

Chapter Summary   467

Answers to Self-Test Exercises   468

Programming Projects   470

Chapter 11 Separate Compilation and Namespaces   473

11.1 Separate Compilation   474

Encapsulation Reviewed   475

Header Files and Implementation Files   476

Example: DigitalTime Class   484

Tip: Reusable Components   485

Using #ifndef   485

Tip: Defining Other Libraries   488

11.2 Namespaces   489

Namespaces and using Directives   489

Creating a Namespace   491

Using Declarations   494

Qualifying Names   496

Tip: Choosing a Name for a Namespace   498

Example: A Class Definition in a Namespace   498

Unnamed Namespaces   499

Pitfall: Confusing the Global Namespace and the Unnamed Namespace   506

Tip: Unnamed Namespaces Replace the static Qualifier   507

Tip: Hiding Helping Functions   507

Nested Namespaces   508

Tip: What Namespace Specification Should You Use?   508

Chapter Summary   511

Answers to Self-Test Exercises   512

Programming Projects   513

Chapter 12 Streams and File I/O 519

12.1 I/O Streams   521

File I/O   521

Pitfall: Restrictions on Stream Variables   526

Appending to a File 526

Tip: Another Syntax for Opening a File   528

Tip: Check That a File Was Opened Successfully   530

Character I/O   532

Checking for the End of a File   533

12.2 Tools for Stream I/O   537

File Names as Input   537

Formatting Output with Stream Functions   538

Manipulators   542

Saving Flag Settings   543

More Output Stream Member Functions   544

Example: Cleaning Up a File Format   546

Example: Editing a Text File   548

12.3 Stream Hierarchies: A Preview of Inheritance   551

Inheritance among Stream Classes   551

Example: Another newLine Function   553

Parsing Strings with the stringstream Class

12.4 Random Access to Files   557

Chapter Summary   559

Answers to Self-Test Exercises   559

Programming Projects   562

Chapter 13 Recursion 571

13.1 Recursive void Functions   573

Example: Vertical Numbers   573

Tracing a Recursive Call   576

A Closer Look at Recursion   579

Pitfall: Infinite Recursion   580

Stacks for Recursion   582

Pitfall: Stack Overflow   583

Recursion versus Iteration   584

13.2 Recursive Functions That Return a Value   585

General Form for a Recursive Function That Returns a Value   585

Example: Another Powers Function   586

Mutual Recursion

13.3 Thinking Recursively   591

Recursive Design Techniques   591

Binary Search   592

Coding   594

Checking The Recursion   598

Efficiency   598

Chapter Summary   600

Answers to Self-Test Exercises   601

Programming Projects   605

Chapter 14 Inheritance 609

14.1 Inheritance Basics   610

Derived Classes   610

Constructors in Derived Classes   620

Pitfall: Use of Private Member Variables from the Base Class   622

Pitfall: Private Member Functions Are Effectively Not Inherited   624

The protected Qualifier   624

Redefinition of Member Functions   627

Redefining versus Overloading   628

Access to a Redefined Base Function   630

Functions That Are Not Inherited   631

14.2 Programming with Inheritance   632

Assignment Operators and Copy Constructors in Derived Classes   632

Destructors in Derived Classes   633

Example: Partially Filled Array with Backup   634

Pitfall: Same Object on Both Sides of the Assignment Operator   643

Example: Alternate Implementation of PFArrayDBak   643

Tip: A Class Has Access to Private Members of All Objects of the Class   646

Tip: “Is a” versus “Has a”   646

Protected and Private Inheritance   647

Multiple Inheritance   648

Chapter Summary   649

Answers to Self-Test Exercises 649

Programming Projects 651

Chapter 15 Polymorphism and Virtual Functions   657

15.1 Virtual Function Basics   658

Late Binding   658

Virtual Functions in C++   659

Tip: The Virtual Property Is Inherited   666

Tip: When to Use a Virtual Function   666

Pitfall: Omitting the Definition of a Virtual Member Function   667

Abstract Classes and Pure Virtual Functions   667

Example: An Abstract Class   669

15.2 Pointers and Virtual Functions   671

Virtual Functions and Extended Type Compatibility   671

Pitfall: The Slicing Problem   675

Tip: Make Destructors Virtual   676

Downcasting and Upcasting   677

How C++ Implements Virtual Functions   678

Chapter Summary   680

Answers to Self-Test Exercises   681

Programming Projects   682



Chapter 16 Templates   687

16.1 Function Templates   688

Syntax for Function Templates   690

Pitfall: Compiler Complications   693

Tip: How to Define Templates   694

Example: A Generic Sorting Function   695

Pitfall: Using a Template with an Inappropriate Type   700

16.1 Class Templates   702

Syntax for Class Templates   703

Example: An Array Template Class   707

The vector and basic_string Templates   713

16.3 Templates and Inheritance   713

Example: Template Class for a Partially Filled Array with Backup   714

Chapter Summary   720

Answers to Self-Test Exercises   720

Programming Projects   723

Chapter 17 Linked Data Structures   725

17.1 Nodes and Linked Lists   727

Nodes   727

Linked Lists   732

Inserting a Node at the Head of a List   734

Pitfall: Losing Nodes   737

Inserting and Removing Nodes Inside a List   737

Pitfall: Using the Assignment Operator with Dynamic Data Structures   741

Searching a Linked List   742

Doubly Linked Lists   744

Adding a Node to a Doubly Linked List   746

Deleting a Node from a Doubly Linked List   748

Example: A Generic Sorting Template Version of Linked List Tools 753

17.2 Linked List Applications   757

Example: A Stack Template Class   757

Example: A Queue Template Class   764

Tip: A Comment on Namespaces   767

Friend Classes and Similar Alternatives   768

Example: Hash Tables with Chaining   771

Efficiency of Hash Tables   777

Example: A Set Template Class   778

Efficiency of Sets Using Linked Lists   784

17.3 Iterators   785

Pointers as Iterators   786

Iterator Classes   786

Example: An Iterator Class   788

17.4 Trees   974

Tree Properties   795

Example: A Tree Template Class   797

Chapter Summary   802

Answers to Self-Test Exercises   803

Programming Projects   812

Chapter 18 Exception Handling   819

18.1 Exception Handling Basics   821

A Toy Example of Exception Handling   821

Defining Your Own Exception Classes   830

Multiple Throws and Catches   830

Pitfall: Catch the More Specific Exception First   834

Tip: Exception Classes Can Be Trivial   835

Throwing an Exception in a Function   835

Exception Specification   837

Pitfall: Exception Specification in Derived Classes   839

18.2 Programming Techniques for Exception Handling   840

When to Throw an Exception   841

Pitfall: Uncaught Exceptions   842

Pitfall: Nested try-catch Blocks    843

Pitfall: Overuse of Exceptions   843

Exception Class Hierarchies   844

Testing for Available Memory   844

Rethrowing an Exception   845

Chapter Summary   845

Answers to Self-Test Exercises   845

Programming Projects   847

Chapter 19 Standard Template Library   851

19.1 Iterators   853

Iterator Basics   853

Pitfall: Compiler Problems   858

Kinds of Iterators   859

Constant and Mutable Iterators   862

Reverse Iterators   864

Other Kinds of Iterators   865

19.2 Containers   866

Sequential Containers   866

Pitfall: Iterators and Removing Elements   872

Tip: Type Definitions in Containers   872

The Container Adapters stack and queue   872

Pitfall: Underlying Containers   873

The Associative Containers set and map   876

Efficiency   881

19.3 Generic Algorithms   883

Running Times and Big-O Notation   884

Container Access Running Times   888

Nonmodifying Sequence Algorithms   889

Modifying Sequence Algorithms   894

Set Algorithms   895

Sorting Algorithms   897

Chapter Summary   897

Answers to Self-Test Exercises   898

Programming Projects   900

Chapter 20 Patterns and UML   907

20.1 Patterns   908

Adapter Pattern   909

The Model-View-Controller Pattern   909

Example: A Sorting Pattern   911

Efficiency of the Sorting Pattern   917

Tip: Pragmatics and Patterns   918

Pattern Formalism   919

UML   919

History of UML   920

UML Class Diagrams   920

Class Interactions   921

Chapter Summary   921

Answers to Self-Test Exercises   922

Programming Projects   923

Appendix 1 C++ Keywords   927

Appendix 2 Precedence of Operators   929

Appendix 3 The ASCII Character Set   931

Appendix 4 Some Library Functions   933

Appendix 5 Old and New Header Files   941

Index   945