Absolute C++ 6th Edition (Walter Savitch, Kenrick Mock) (z-library.sk, 1lib.sk, z-lib.sk)

Absolute C++6th edition

This page intentionally left blank

Walter Savitch University of California, San Diego Contributor Kenrick Mock University of Alaska Anchorage Absolute C++ Boston Columbus Indianapolis New York San Francisco Hoboken Amsterdam Cape Town Dubai London Madrid Milan Munich Paris Montréal Toronto Delhi Mexico City São Paulo Sydney Hong Kong Seoul Singapore Taipei Tokyo 6th Edition

ISBN-10: 0-13-397078-7 ISBN-13: 978-0-13-397078-4 Copyright © 2016, 2013, 2010 by Pearson Higher Education, Inc., Hoboken, NJ07030. All rights reserved. Manufactured in the United States of America. This publication is protected by Copyright and permissions should be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise. To obtain permission(s) to use materials from this work, please submit a written request to Pearson Higher Education, Permissions Department, 221 River Street, Hoboken, NJ 07030. Many of the designations by manufacturers and seller to distinguish their products are claimed as trademarks. Where those designations appear in this book, and the publisher was aware of a trademark claim, the designations have been printed in initial caps or all caps. The author and publisher of this book have used their best efforts in preparing this book. These efforts include the development, research, and testing of theories and programs to determine their effectiveness. The author and publisher make no warranty of any kind, expressed or implied, with regard to these programs or the documentation contained in this book. The author and publisher shall not be liable in any event for incidental or consequential damages with, or arising out of, the furnishing, performance, or use of these programs. Pearson Education Ltd., London Pearson Education Singapore, Pte. Ltd Pearson Education Canada, Inc. Pearson Education—Japan Pearson Education Australia PTY, Limited Pearson Education North Asia, Ltd., Hong Kong Pearson Educación de Mexico, S.A. de C.V. Pearson Education Malaysia, Pte. Ltd. Pearson Education, Inc., Hoboken, New Jersey Library of Congress Cataloging-in-Publication Data on File 10 9 8 7 6 5 4 3 2 1 Vice President and Editorial Director, ECS: Marcia J. Horton Acquisitions Editor: Matt Goldstein Editorial Assistant: Kelsey Loanes Product Marketing Manager: Bram Van Kempen Marketing Assistant: Jon Bryant Senior Managing Editor: Scott Disanno Production Project Manager: Rose Kernan Program Manager: Carole Snyder Global HE Director of Vendor Sourcing and Procurement: Diane Hynes Director of Operations: Nick Sklitsis Operations Specialist: Maura Zaldivar-Garcia Cover Designer: Black Horse Designs Manager, Rights and Permissions: Rachel Youdelman Associate Project Manager, Rights and Permissions: Timothy Nicholls Full-Service Project Management: Niraj Bhatt, Aptara®, Inc. Composition: Aptara®, Inc. Printer/Binder: Edwards Brothers Malloy Cover Printer: Phoenix Color/Hagerstown Cover Image: Bluelela/Fotolia Typeface: 10.5/12 Adobe Garamond

This book is designed to be a textbook and reference for programming in the C++ lan- guage. Although it does include programming techniques, it is organized around the features of the C++ language, rather than any particular curriculum of techniques. The main audience I had in mind is undergraduate students who had not had extensive programming experience with the C++ language. As such, this book is a suitable C++ text or reference for a wide range of users. The introductory chapters are written at a level that is accessible to beginners, while the boxed sections of those chapters serve to introduce more experienced programmers to basic C++ syntax. Later chapters are also understandable to beginners, but are written at a level suitable for students who have progressed to these more advanced topics. Absolute C++ is also suitable for anyone learning the C++ language on their own. (For those who want a textbook with more pedagogical material and more on very basic programming technique, try my text Problem Solving with C++, Eighth Edition, Pearson Education.) The C++ coverage in this book goes well beyond what a beginner needs to know. In particular, it has extensive coverage of inheritance, polymorphism, exception handling, and the Standard Template Library (STL), as well as basic coverage of patterns and the unified modeling language (UML). CHANGES IN THIS EDITION This sixth edition presents the same programming philosophy as the fifth edition. For instructors, you can teach the same course, presenting the same topics in the same order with no changes in the material covered or the chapters assigned. Changes include: ■ Introduction to C++11 in the context of C++98. Examples of C++11 content include new integer types, the auto type, raw string literals, strong enumerations, nullptr, ranged for loop, conversion between strings and integers, member initial- izers, and constructor delegation. ■ Additional material on sorting, the Standard Template Library, iterators, and excep- tion handling. ■ New appendix introducing the std::array class, regular expressions, threads, and smart pointers ■ Correction of errata. ■ Fifteen new Programming Projects. ■ Five new VideoNotes for a total of sixty-nine VideoNotes. These VideoNotes walk students through the process of both problem solving and coding to help reinforce key programming concepts. An icon appears in the margin of the book when a VideoNote is available regarding the topic covered in the text. ANSI/ISO C++ STANDARD This edition is fully compatible with compilers that meet the latest ANSI/ISO C++ standard. Preface v

vi Preface STANDARD TEMPLATE LIBRARY The Standard Template Library (STL) is an extensive collection of preprogrammed data structure classes and algorithms. The STL is perhaps as big a topic as the core C++ language, so I have included a substantial introduction to STL. There is a full chapter on the general topic of templates and a full chapter on the particulars of STL, as well as other material on, or related to, STL at other points in the text. OBJECT-ORIENTED PROGRAMMING This book is organized around the structure of C++. As such, the early chapters cover aspects of C++ that are common to most high-level programming languages but are not particularly oriented toward object-oriented programming (OOP). For a reference book—and for a book for learning a second language—this makes sense. However, I consider C++ to be an OOP language. If you are programming in C++ and not C, you must be using the OOP features of C++. This text offers extensive coverage of encapsu- lation, inheritance, and polymorphism as realized in the C++ language. Chapter 20, on patterns and UML, gives additional coverage of OOP-related material. FLEXIBILITY IN TOPIC ORDERING This book allows instructors wide latitude in reordering the material. This is important if a book is to serve as a reference. This is also in keeping with my philosophy of accom- modating the instructor’s style, rather than tying the instructor to my own personal preference of topic ordering. Each chapter introduction explains what material must already have been covered before each section of the chapter can be covered. ACCESSIBLE TO STUDENTS It is not enough for a book to present the right topics in the right order. It is not even enough for it be correct and clear to an instructor. The material also needs to be pre- sented in a way that is accessible to the novice. Like my other textbooks, which proved to be very popular with students, this book was written to be friendly and accessible to the student. SUMMARY BOXES Each major point is summarized in a boxed section. These boxed sections are spread throughout each chapter. They serve as summaries of the material, as a quick reference source, and as a quick way to learn the C++ syntax for a feature you know about in general but for which you do not know the C++ particulars. SELF-TEST EXERCISES Each chapter contains numerous self-test exercises. Complete answers for all the self- test exercises are given at the end of each chapter.

VIDEO NOTES VideoNotes are step-by-step videos that guide readers through the solution to an end of chapter problem or further illuminate a concept presented in the text. Icons in the text indicate where a VideoNote enhances a topic. Fully navigable problems allow for self- paced instruction. VideoNotes are located at www.pearsonhighered.com/cs-resources/. OTHER FEATURES Pitfall sections, programming technique sections, and examples of complete programs with sample input and output are given throughout each chapter. Each chapter ends with a summary and a collection of programming projects. SUPPORT MATERIAL The following support materials are available to all users of this book at www. pearsonhighered.com/cs-resources: ■ Source code from the book The following resources are available to qualified instructors only at www.pearsonhighered. com/irc. Please contact your local sales representative for access information. ■ Instructor’s Manual with Solutions ■ PowerPoint® slides HOW TO ACCESS INSTRUCTOR AND STUDENT RESOURCE MATERIALS Online Practice and Assessment with . MyProgrammingLab helps students fully grasp the logic, semantics, and syntax of programming. Through practice exercises and immediate, personalized feedback, MyProgrammingLab improves the programming competence of beginning students who often struggle with the basic concepts and paradigms of popular high-level pro- gramming languages. A self-study and homework tool, a MyProgrammingLab course consists of hun- dreds of small practice problems organized around the structure of this textbook. For students, the system automatically detects errors in the logic and syntax of their code submissions and offers targeted hints that enable students to figure out what went wrong—and why. For instructors, a comprehensive gradebook tracks correct and incor- rect answers and stores the code inputted by students for review. For a full demonstration, to see feedback from instructors and students, or to get started using MyProgrammingLab in your course, visit www.myprogramminglab.com. ACKNOWLEDGMENTS Numerous individuals have contributed invaluable help and support to making this book happen. Frank Ruggirello and Susan Hartman at Addison-Wesley first conceived the idea and supported the first edition, for which I owe them a debt of gratitude. A VideoNote Preface vii

special thanks to Matt Goldstein who was the editor for the second, third, and fourth editions. His help and support were critical to making this project succeed. Chelsea Kharakozova, Marilyn Lloyd, Yez Alayan, and the other fine people at Pearson Education also provided valuable support and encouragement. The following reviewers provided suggestions for the book. I thank them all for their hard work and helpful comments. Duncan Buell University of South Carolina Daniel Cliburn University of the Pacific Natacha Gueroguieva College of Staten Island, CUNY Archana Sharma Gupta Delaware Technical and Community College Kenneth Moore Community College of Allegheny County Robert Meyers Florida State University Clayton Price Missouri University of Science and Technology Terry Rooker Oregon State University William Smith Tulsa Community College Hugh Lauer Worcester Polytechnic Institute Richard Albright University of Delaware J. Boyd Trolinger Butte College Jerry K. Bilbrey, Jr Francis Marion University Albert M. K. Cheng University of Houston David Cherba Michigan State University Fredrick H. Colclough Colorado Technical University Drue Coles Boston University Stephen Corbesero Moravian College Christopher E. Cramer Ron DiNapoli Cornell University Qin Ding Pennsylvania State University, Harrisburg Martin Dulberg North Carolina State University H. E. Dunsmore Purdue University Evan Golub University of Maryland Terry Harvey University of Delaware Joanna Klukowska Hunter College, CUNY Lawrence S. Kroll San Francisco State University Stephen P. Leach Florida State University Alvin S. Lim Auburn University Tim H. Lin Cal Poly Pomona R. M. Lowe Clemson University Jeffrey L. Popyack Drexel University viii Preface

Amar Raheja Cal Poly Pomona Victoria Rayskin University of Central Los Angeles Loren Rhodes Juniata College Jeff Ringenberg University of Michigan Victor Shtern Boston University Aaron Striegel University of Notre Dame J. Boyd Trolinger Butte College Chrysafis Vogiatzis University of Florida Joel Weinstein Northeastern University Dick Whalen College of Southern Maryland A special thanks goes to Kenrick Mock (University of Alaska Anchorage) who exe- cuted the updating of this edition. He once again had the difficult job of satisfying me, the editor, and himself. I thank him for a truly excellent job. Walter Savitch Preface ix

LOCATION OF VIDEONOTES IN THE TEXT www.pearsonhighered.com/savitch Chapter 1 Compiling and Running a C++ Program, page 4 C++11 Fixed Width Integer Types, page 10 Solution to Programming Project 1.11, page 45 Chapter 2 Nested Loop Example, page 85 Solution to Programming Project 2.5, page 97 Solution to Programming Project 2.9, page 98 Solution to Programming Project 2.10, page 98 Chapter 3 Generating Random Numbers, page 109 Scope Walkthrough, page 127 Solution to Programming Project 3.9, page 142 Chapter 4 Using an Integrated Debugger, page 175 Solution to Programming Project 4.4, page 182 Solution to Programming Project 4.11, page 183 Chapter 5 Array Walkthrough, page 189 Range-Based for Loop, page 194 Bubble Sort Walkthrough, page 219 Solution to Programming Project 5.7, page 238 Solution to Programming Project 5.15, page 242 Chapter 6 Solution to Programming Project 6.5, page 278 Solution to Programming Project 6.9, page 279 Chapter 7 Constructor Walkthrough, page 282 Default Initialization of Member Variables, page 301 Solution to Programming Project 7.4, page 323 Solution to Programming Project 7.7, page 324 Chapter 8 Solution to Programming Project 8.7, page 372 Chapter 9 Using cin and getline with the string class, page 405 Solution to Programming Project 9.11, page 423 Solution to Programming Project 9.13, page 424 Chapter 10 Example of Shallow Copy vs. Deep Copy, page 465 Solution to Programming Project 10.5, page 475 Chapter 11 Avoiding Multiple Definitions with #ifndef, page 490 Solution to Programming Project 11.5, page 518 Chapter 12 Walkthrough of the stringstream demo, page 560 Solution to Programming Project 12.17, page 572 Solution to Programming Project 12.25, page 576 Chapter 13 Recursion and the Stack, page 588 Walkthrough of Mutual Recursion, page 597 Solution to Programming Project 13.9, page 615 Solution to Programming Project 13.11, page 616 Chapter 14 Solution to Programming Project 14.7, page 663 VideoNote

Chapter 15 Solution to Programming Project 15.5, page 698 Solution to Programming Project 15.7, page 699 Chapter 16 Solution to Programming Project 16.3, page 736 Solution to Programming Project 16.7, page 737 Chapter 17 Solution to Programming Project 17.5, page 828 Solution to Programming Project 17.11, page 830 Chapter 18 Solution to Programming Project 18.5, page 865 Chapter 19 C++11 and Containers, page 899 Solution to Programming Project 19.9, page 920 Solution to Programming Project 19.12, page 921

This page intentionally left blank

Brief Contents Chapter 1 C++ BASICS 1 Chapter 2 FLOW OF CONTROL 47 Chapter 3 FUNCTION BASICS 101 Chapter 4 PARAMETERS AND OVERLOADING 147 Chapter 5 ARRAYS 187 Chapter 6 STRUCTURES AND CLASSES 245 Chapter 7 CONSTRUCTORS AND OTHER TOOLS 281 Chapter 8 OPERATOR OVERLOADING, FRIENDS, AND REFERENCES 327 Chapter 9 STRINGS 373 Chapter 10 POINTERS AND DYNAMIC ARRAYS 425 Chapter 11 SEPARATE COMPILATION AND NAMESPACES 477 Chapter 12 STREAMS AND FILE I/O 521 Chapter 13 RECURSION 577 Chapter 14 INHERITANCE 619 Chapter 15 POLYMORPHISM AND VIRTUAL FUNCTIONS 669 Chapter 16 TEMPLATES 701 Chapter 17 LINKED DATA STRUCTURES 739 Chapter 18 EXCEPTION HANDLING 833 Chapter 19 STANDARD TEMPLATE LIBRARY 867 Chapter 20 PATTERNS AND UML (online at www.pearsonhighered.com/ savitch) Appendix 1 C++ KEYWORDS 923 Appendix 2 PRECEDENCE OF OPERATORS 925 Appendix 3 THE ASCII CHARACTER SET 927 Appendix 4 SOME LIBRARY FUNCTIONS 929 Appendix 5 OLD AND NEW HEADER FILES 937 Appendix 6 ADDITIONAL C++11 LANGUAGE FEATURES 939 INDEX 955 xiii

This page intentionally left blank

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 TIP: Compiling C++ Programs 5 1.2 VARIABLES, EXPRESSIONS, AND ASSIGNMENT STATEMENTS 6 Identifiers 7 Variables 8 Assignment Statements 11 Introduction to the string class 12 PITFALL: Uninitialized Variables 13 TIP: Use Meaningful Names 14 More Assignment Statements 14 Assignment Compatibility 15 Literals 16 Escape Sequences 18 Raw String Literals 19 Naming Constants 19 Arithmetic Operators and Expressions 20 Integer and Floating-Point Division 22 PITFALL: Division with Whole Numbers 23 Type Casting 24 Increment and Decrement Operators 26 PITFALL: Order of Evaluation 28 1.3 CONSOLE INPUT/OUTPUT 29 Output Using cout 29 New Lines in Output 30 TIP: End Each Program with \n or endl 31 Formatting for Numbers with a Decimal Point 31 Output with cerr 33 Input Using cin 33 TIP: Line Breaks in I/O 36 1.4 PROGRAM STYLE 37 Comments 37 xv

xvi Contents 1.5 LIBRARIES AND NAMESPACES 38 Libraries and include Directives 38 Namespaces 38 PITFALL: Problems with Library Names 39 Chapter Summary 40 Answers to Self-Test Exercises 41 Programming Projects 43 Chapter 2 Flow of Control 47 2.1 BOOLEAN EXPRESSIONS 48 Building Boolean Expressions 48 PITFALL: Strings of Inequalities 49 Evaluating Boolean Expressions 50 Precedence Rules 52 PITFALL: Integer Values Can Be Used as Boolean Values 56 2.2 BRANCHING MECHANISMS 58 if-else Statements 58 Compound Statements 60 PITFALL: Using = in Place of = = 61 Omitting the else 63 Nested Statements 63 Multiway if-else Statement 63 The switch Statement 64 PITFALL: Forgetting a break in a switch Statement 67 TIP: Use switch Statements for Menus 67 Enumeration Types 67 The Conditional Operator 69 2.3 LOOPS 69 The while and do-while Statements 70 Increment and Decrement Operators Revisited 73 The Comma Operator 74 The for Statement 76 TIP: Repeat-N-Times Loops 78 PITFALL: Extra Semicolon in a for Statement 79 PITFALL: Infinite Loops 79 The break and continue Statements 82 Nested Loops 85

Contents xvii 2.4 INTRODUCTION TO FILE INPUT 85 Reading From a Text File Using ifstream 86 Chapter Summary 89 Answers to Self-Test Exercises 89 Programming Projects 95 Chapter 3 Function Basics 101 3.1 PREDEFINED FUNCTIONS 102 Predefined Functions That Return a Value 102 Predefined void Functions 107 A Random Number Generator 109 3.2 PROGRAMMER-DEFINED FUNCTIONS 113 Defining Functions That Return a Value 114 Alternate Form for Function Declarations 116 PITFALL: Arguments in the Wrong Order 117 PITFALL: Use of the Terms Parameter and Argument 117 Functions Calling Functions 117 EXAMPLE: A Rounding Function 117 Functions That Return a Boolean Value 120 Defining void Functions 121 return Statements in void Functions 123 Preconditions and Postconditions 123 main Is a Function 125 Recursive Functions 125 3.3 SCOPE RULES 127 Local Variables 127 Procedural Abstraction 129 Global Constants and Global Variables 130 Blocks 133 Nested Scopes 134 TIP: Use Function Calls in Branching and Loop Statements 134 Variables Declared in a for Loop 135 Chapter Summary 136 Answers to Self-Test Exercises 136 Programming Projects 140

xviii Contents Chapter 4 Parameters and Overloading 147 4.1 PARAMETERS 148 Call-by-Value Parameters 148 A First Look at Call-by-Reference Parameters 150 Call-by-Reference Mechanism in Detail 153 Constant Reference Parameters 155 EXAMPLE: The swapValues Function 155 TIP: Think of Actions, Not Code 156 Mixed Parameter Lists 157 TIP: What Kind of Parameter to Use 158 PITFALL: Inadvertent Local Variables 160 TIP: Choosing Formal Parameter Names 161 EXAMPLE: Buying Pizza 162 4.2 OVERLOADING AND DEFAULT ARGUMENTS 165 Introduction to Overloading 165 PITFALL: Automatic Type Conversion and Overloading 168 Rules for Resolving Overloading 169 EXAMPLE: Revised Pizza-Buying Program 171 Default Arguments 173 4.3 TESTING AND DEBUGGING FUNCTIONS 175 The assert Macro 175 Stubs and Drivers 176 Chapter Summary 179 Answers to Self-Test Exercises 179 Programming Projects 181 Chapter 5 Arrays 187 5.1 INTRODUCTION TO ARRAYS 188 Declaring and Referencing Arrays 188 TIP: Use for Loops with Arrays 191 PITFALL: Array Indexes Always Start with Zero 191 TIP: Use a Defined Constant for the Size of an Array 191 Arrays in Memory 192 PITFALL: Array Index out of Range 194 The Range-Based for Loop 194 Initializing Arrays 195

Contents xix 5.2 ARRAYS IN FUNCTIONS 197 Indexed Variables as Function Arguments 197 Entire Arrays as Function Arguments 198 The const Parameter Modifier 202 PITFALL: Inconsistent Use of const Parameters 203 Functions That Return an Array 204 EXAMPLE: Production Graph 204 5.3 PROGRAMMING WITH ARRAYS 209 Partially Filled Arrays 209 TIP: Do Not Skimp on Formal Parameters 210 EXAMPLE: Searching an Array 213 EXAMPLE: Sorting an Array 215 EXAMPLE: Bubble Sort 219 5.4 MULTIDIMENSIONAL ARRAYS 223 Multidimensional Array Basics 223 Multidimensional Array Parameters 224 EXAMPLE: Two-Dimensional Grading Program 225 Chapter Summary 230 Answers to Self-Test Exercises 231 Programming Projects 235 Chapter 6 Structures and Classes 245 6.1 STRUCTURES 246 Structure Types 248 PITFALL: Forgetting a Semicolon in a Structure Definition 252 Structures as Function Arguments 252 TIP: Use Hierarchical Structures 253 Initializing Structures 255 6.2 CLASSES 258 Defining Classes and Member Functions 258 Encapsulation 264 Public and Private Members 265 Accessor and Mutator Functions 268 TIP: Separate Interface and Implementation 270 TIP: A Test for Encapsulation 271 Structures versus Classes 272 TIP: Thinking Objects 274 Chapter Summary 274 Answers to Self-Test Exercises 275 Programming Projects 277