C++ by Dissection Ira Pohl University of California Santa Cruz Boston San Francisco New York London Toronto Sydney Tokyo Singapore Madrid Mexico City Munich Paris Cape Town Hong Kong Montreal Senior Acquistions Editor Maite Suarez-Rivas Project Editor Katherine Harutunian Executive Marketing Manager Michael Hirsch Production Supervisor Marilyn Lloyd Project Management Argosy Publishing Copyeditor Jeannie Smith Proofreader Janet Renard Composition and Art Debra Dolsberry and Argosy Publishing Text and Cover Design Leslie Haimes Design Manager Gina Hagen Prepress and Manufacturing Hugh Crawford Access the latest information about Addison-Wesley titles from our World Wide Web site: http://www.aw.com/cs Many of the designations used by manufacturers and sellers to distinguish their products are claimed as tradmarks. Where those designations appear in this book, and Addison-Wesley was aware of a trademark claim, the designations have been printed in initial caps or all caps. Borland C/C++ is a registered trademark of Borland International, Inc. GNU C/C++ is a registered trademark of Free Software Foundation, Inc. Microsoft C/C++ is a registered trademark of Microsoft, Inc. Turbo C/C++ is a registered trademark of Borland International, Inc. MS-DOS is a registered trademark of Microsoft, Inc. OS/2 is a registered trademark of International Business Machines, Inc. UNIX is a registered trademark licensed through X/Open Company, Ltd. Windows is a registered trademark of Microsoft, Inc. FrameMaker is a registered trademark of Frame Technology, Inc. PostScript is a registered trademark of Adobe Systems, Inc. The programs and applications presented in this book have been included for their instructional value. They have been tested with care, but are not guaranteed for any particular purpose. The publisher does not offer any warranties or representations, nor does it accept any liabilities with respect to the pro- grams or applications. Library of Congress Cataloging-in-Publication Data Pohl, Ira C++ by Dissection / Ira Pohl. p. cm. ISBN 0-201-74396-5 (pbk.) 1. C++ (Computer program language) I. Title. QA76.73.C153 P58 2002 005.13’3--dc21 2001045829 CIP Copyright © 2002 by Addison-Wesley All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or trans- mitted, in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior written permission of the publisher. Printed in the United States of America. ISBN 0-201-74396-5 About Ira Pohl Ira Pohl, Ph.D., is a professor of Computer Science at the University of Cali- fornia, Santa Cruz. He has over 30 years of experience as a software meth- odologist. His teaching and research interests are in the areas of artificial intelligence, programming languages, practical complexity problems, heu- ristic search methods, deductive algorithms, and educational and social issues. He originated error analysis in heuristic search methods and deduc- tive algorithms. He is an ACM Fellow and has lectured at Berkeley, Stanford, the Vrije Uni- versity in Amsterdam, the Courant Institute, Edinburgh University in Scot- land, and Auckland University in New Zealand. When not programming, he enjoys riding bicycles in Aptos, California, with his wife Debra and daughter Laura. Other Publications by Ira Pohl Ira is the sole author of the following Addison-Wesley or Benjamin Cum- mings publications: C++ for C Programmers C++ for Pascal Programmers C++ for Fortran Programmers Turbo C++ Object Oriented Programming Using C++ C++ Distilled Ira is coauthor with Al Kelley for a series of books published by Addison- Wesley and Benjamin Cummings on the C programming language: A Book on C: An Introduction to Programming in C C by Dissection Turbo C: The Essentials of C Programming Ira is also coauthor with Charlie McDowell of the following Addison-Wesley publication: Java by Dissection: The Essentials of Java Programming Ira’s first book, coauthored with Alan Shaw, was a pioneering text on com- puter science (Computer Science Press, 1981): The Nature of Computation: An Introduction to Computer Science Dedicated to Philip Pohl (1932–2001) who gave me my first computer (a slide rule). Preface T oday, the ANSI C++ programming language is widely used throughout the world in both academia and industry. In many educational institutions it is the language of choice for a first programming course and for a language to be used for computer sci- ence instruction. A key reason for this is that C++ has drifted down the curriculum from more advanced courses to more introductory courses. Further, C++ comes with many useful libraries, and is supported by sophisticated integrated environments. It is a language that efficiently supports object-oriented programming (OOP) the dominant contemporary programming methodology. C++ by Dissection presents a thorough introduction to the programming process by carefully developing working programs to illuminate key features of the C++ program- ming language. Program code is explained in an easy-to-follow, careful manner through- out. The code has been tested on several platforms and is found on the bundled CD- rom accompanying this text. The code in C++ By Dissection can be used with most C++ systems, including those found in operating systems such as MacOS, MS-DOS, OS/2, UNIX, and Windows. C++, invented at Bell Labs by Bjarne Stroustrup in the mid-1980s, is a powerful, mod- ern, successor language to C. C++ adds to C the concept of class, a mechanism for pro- viding user-defined types, also called abstract data types. C++ supports object-oriented programming by these means and by providing inheritance and runtime type binding. Ira Pohl’s C++ by Dissection Dissections vii Dissections This book presents readers with a clear and thorough introduction to the programming process by carefully developing working C++ programs, using the method of dissection. Dissection is a unique pedagogical tool first developed by the author in 1984 to illumi- nate key features of working code. A dissection is similar to a structured walk-through of the code. Its intention is to explain to the reader newly encountered programming elements and idioms as found in working code. Programs and functions are explained in an easy-to-follow step-by-step manner. Key ideas are reinforced throughout by use in different contexts. No Background Assumed This book assumes no programming background and can be used by students and first time computer users. Experienced programmers not familiar with C++ will also benefit from the carefully structured presentation of the C++ language. For student use, the book is intended as a first course in computer science or programming. It is suitable for a CS1 course or beginning programming course for other disciplines. Each chapter presents a number of carefully explained programs, which lead the stu- dent in a holistic manner to ever-improving programming skills. From the start, the stu- dent is introduced to complete programs, and at an early point in the text is introduced to writing functions as a major feature of structured programming. The function is to the program as the paragraph is to the essay. Competence in writing functions is the hallmark of the skilled programmer and hence is emphasized. Examples and exercises are plentiful in content and level of difficulty. They allow instructors to pick assign- ments appropriate to their audiences. Ira Pohl’s C++ by Dissection Special Features viii Special Features C++ by Dissection: The Essentials of C++ Programming incorporates a number of special features: (cid:1) A CD-Rom with a working compiler. (cid:1) A website with and the full electronically searchable text of this book. Also included are active links to useful web-sites and complete working code for this text (cid:1) Software engineering practice is described throughout (cid:1) Dr. P’s prescriptions are concise programming tips provided for the beginner for each chapter (cid:1) Early explanation of simple recursion to reflect its earlier introduction in beginning computer science courses (cid:1) Coverage of program correctness and type-safety (cid:1) In-depth explanation of functions and pointers because these concepts are typically stumbling blocks for the beginner (cid:1) Object-oriented programming concepts are emphasized (cid:1) Generic programming and STL are carefully described (cid:1) UML diagrams are introduced as an aid to understanding object-oriented program- ming (cid:1) Comparison to Java, optional Java exercises and coordinating references to Java by Dissection (with Charlie McDowell) (cid:1) Active links to online code by clicking on the infile line above each major program section. (cid:1) Active links to online sites via clicking on blue underlined text. Chapter Features Each chapter contains the following pedagogical elements: Dissections. Major elements of the important example programs are explained by the method of dissection. This step-by-step discussion of new programming ideas helps the reader encountering these ideas for the first time to understand them. Object-oriented programming. The reader is led gradually to the object-oriented style. Chapter 4, Classes and Abstract Data Types, introduces classes, which are the basic mechanism for producing modular programs and implementing abstract data types. Class variables are the objects being manipulated. Chapter 8, Inheritance and OOP, develops inheritance and virtual functions, two key elements in this paradigm. Chapter 11, OOP Using C++, discusses OOP programming philosophy. This book develops in the programmer an appreciation of this point of view. Ira Pohl’s C++ by Dissection Classroom Usage ix Programming Style and Software Engineering. Programming style and software method- ology is stressed throughout. Important concepts such as structured branching state- ments, nested flow of control, top-down design, and object-oriented programming are presented early in the book. A consistent and proper coding style is adopted from the beginning with careful explanation as to its importance and rationale. The coding style used in the book is one commonly used by working programming professionals in the C++ community. Working Code. Right from the start the student is introduced to full working programs. With the executable code, the student can better understand and appreciate the pro- gramming ideas under discussion. Many programs and functions are explained through dissections. Variations on programming ideas are often presented in the exercises. Common Programming Errors. Many typical programming bugs, along with techniques for avoiding them, are described. Much of the frustration of learning a programming language is caused by encountering obscure errors. Many books discuss correct code but leave the reader to a trial-and-error process for finding out about bugs. This book explains how typical errors in C++ are made and what must be done to correct them. Dr. P’s Prescriptions. A series of programming tips is based on wide experience. A con- cise rationale is given for each tip. Comparison to Java. An optional section describes the programming elements of Java that are comparable to the C++ examples. Exercises supporting these sections are included as well. For the most part, C++ and Java have equivalent elements. The text aids the student already conversant in Java to migrate to C++. Also the C++ student who later takes up Java will benefit from this section. Furthermore, as the book is a compan- ion volume to Java by Dissection (with Charlie McDowell) the reader has access to com- plete explanations of the Java concepts fully utilizing this book’s pedagogy. Summary. A succinct list of points covered in the chapter serves as a review for the reader, reinforcing the new ideas that were presented in the chapter. Exercises. The exercises test the student’s knowledge of the language. Many exercises are intended to be done interactively while reading the text. This encourages self-paced instruction by the reader. In addition to exercising features of the language, some exer- cises look at a topic in more detail, and others extend the reader’s knowledge to an advanced area of use. Classroom Usage This book can be used as a text in a one-semester course that teaches students how to program. Chapters 1 through 5 cover the C++ programming language through the use of arrays, pointers, and basic object programming. A second-semester course can be devoted to more advanced data types, OOP, generic programming and STL, file process- ing, and software engineering as covered in Chapters 6 through 11. In a course designed for students who already have some knowledge of programming, not necessarily in C++, the instructor can cover all the topics in the text. This book can also be used as a text in other computer science courses that require the student to use C++. In a compar- ative language course, it can be used with companion volumes for C, Java, and C# that Ira Pohl’s C++ by Dissection Interactive Environment x follow the same dissection approach and share many of the same examples done uniquely in each language. Interactive Environment This book is written explicitly for an interactive environment. Experimentation via key- board and screen is encouraged throughout. For PCs, there are many vendors that sup- ply interactive C++ systems, including Borland, IBM, Metroworks, Microsoft, and Symantec. Professional Use While intended for the beginning programmer, C++ by Dissection: The Essentials of C++ Programming is a friendly introduction to the entire language for the experienced pro- grammer as well. In conjunction with A Book on C, Fourth Edition by Al Kelley and Ira Pohl (Addison Wesley Longman, Inc., Reading, MA, 1998, ISBN 0-201183994), the com- puter professional will gain a comprehensive understanding of both languages. As a package, the two books offer an integrated treatment of the C/C++ programming lan- guage and its use that is unavailable elsewhere. Furthermore, in conjunction with Java by Dissection by Ira Pohl and Charlie McDowell (Addison Wesley Longman, Inc., Reading, MA, 1999, ISBN 0-201-61248-8), the student or professional is also given an integrated treatment of the object-oriented language Java. This book is the basis of many on-site professional training courses given by the author, who has used its contents to train professionals and students in various forums since 1986. The text is the basis for Web-based training in C++ available from www.digi- talthink.com. Supplements Support materials are available to instructors adopting this textbook for classroom use and include the following: (cid:1) Solutions to exercises (cid:1) Code for example programs (cid:1) Powerpoint slides of all the figures Please check on-line information for this book at www.aw.com/cssupport for more information on obtaining these supplements.