OBJECT- ORIENTED DESIGN AND PROGRAMMING WITH C++ RONALD LEACH Howard University Washington, D.C. AP PROFESSIONAL Boston San Diego New York London Sydney Tokyo Toronto This book is printed on acid-free paper («> Copyright © 1995 by Academic Press, Inc. Source code copyright © 1995 by Ronald J. Leach All rights reserved. No part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. All brand names and product names mentioned in this book are trademarks or registered trademarks of their respective companies. AP PROFESSIONAL 1300 Boylston Street, Chestnut Hill, MA 02167 An imprint of ACADEMIC PRESS, INC. A Division of HARCOURT BRACE & COMPANY United Kingdom Edition published by ACADEMIC PRESS LIMITED 24-28 Oval Road, London NW1 7DX Library of Congress Cataloging-in-Publication Data Leach, Ronald (Ronald J.) Object-oriented design and programming with C++ / Ronald J. Leach p. cm. Includes bibliographical references and index. ISBN 0-12-440215-1 (acid-free paper) 1. Object-oriented programming (Computer science) 2. C++ (Computer program language) I. Title. QA76.64.L43 1995 005.13'3~dc20 95-13535 CIP Printed in the United States of America 95 96 97 98 IP 9 8 7 6 5 4 3 2 1 Preface T his book is intended for persons who are reasonably familiar with the C pro­ gramming language and wish to understand the issues in object-oriented pro­ gramming using C++. The reader should have had enough experience with higher-level languages to understand pointers, arrays, and structured data types. The reader should also have written at least some simple programs in C using these language features. Although the book provides complete coverage of the C++ language, it covers the elementary syntax features quickly in order to be able to discuss the fundamental issues of software design in C++ (or any object-oriented language)—design, testing and reuse. These issues are repeated throughout the book. As with the authors book Using C in Software Design (AP PROFESSIONAL, 1993), this book is organized into two parts. Part I describes the fundamental features of C++: classes control structure, member functions, templates (parametrized classes), C++ data structures, and I/O. Special emphasis is given to testing of objects. This will provide the reader with a complete understanding of the fundamental issues of programming in C++ using object-oriented techniques. Part II describes more advanced, software-engineering-specific features of C++. Part II contains information on program structure, object-oriented design, and the proper use of techniques such as exceptions. The draft ANSI standard C++ class library is dis­ cussed in detail, as are several existing class libraries, such as those included with the IX X Preface standard distribution of the Borland and AT&T C++ systems. Part II includes two case studies with considerable amounts of C++ code so that the reader can see the applica­ tion of the object-oriented software engineering principles discussed in the book. A more detailed description of the books contents is given below. First, a list of software engineering principles is provided to guide the software devel­ opment process. Chapter 1 provides an overview of C++. It describes object-oriented programming and the history of C++ and briefly introduces classes, inheritance, polymorphism, and overloading. Chapter 2 contains a more detailed introduction to C++. It describes classes, funda­ mental data types, output with the « operator and cout, input with the » operator and cin, and control structures. This chapter contains a section on testing issues for overloaded operators and for user-defined I/O. Chapter 3 provides a description of functions, including friend, virtual, and inline functions. Base classes and derived classes are introduced here. We also describe the C++ preprocessor and organization of class libraries. The chapter closes with a discussion of testing issues. In Chapter 4, we describe arrays and pointers in C++. We use multidimensional arrays as the starting point for development of a class called Matrix, which is used with standard matrix operations. The power of the object-oriented approach is illustrated by development of a system of functions to treat sparse matrices. (A sparse matrix is one that has most of its entries 0.) Chapter 5 contains descriptions of the fundamental data structures and some typical implementations in C++. In this chapter we describe stacks, lists, queues, and trees and some typical implementations for them. Templates, or parameterized classes, are intro­ duced in this chapter. Each section that discusses an implementation of one of these data structures is followed by a section that discusses implementation of the same data structure using templates. Chapter 6 concludes the discussion of the fundamental principles of small-scale C++ programming in Part I. It provides a detailed discussion of file I/O in C++. It also completes the discussion of stream-based I/O. Part II of the book begins with Chapter 7, which initiates a discussion of larger soft­ ware systems and their implementation in C++. It includes a discussion of scope rules, separate compilation, class libraries and their organization, browsers, exceptions, and exception handling. Standard libraries are discussed in detail. Chapter 8 is devoted to object-oriented design. Several different object-oriented design methodologies are discussed. The major example is the development of a class of string operations. The related design techniques of information modeling and entity- relationships diagrams are also discussed in this chapter. Preface xi In Chapter 9, we discuss the design of a system to implement a graphical database. This will provide another example of the use of the design methodology presented in Chapter 8. C++ code for the implementation of this system is provided in the book. In Chapter 10 we discuss the design of a moderately complex system that provides a file system simulation. The system is developed using both a procedurally based description and an object-oriented one. This will be especially helpful to the program­ mer wishing to transform a procedurally described (or coded) system to an object-ori­ ented one. C++ code for both implementations of the system is also provided in the book. There are six appendices: the set of reserved words in C++, a formal description of the syntax of C++, a summary of the C language, the ANSI C standard library, the draft ANSI C++ standard library, and answers to selected exercises. The draft C++ library is likely to be the basis for an ANSI standard that is adopted by the time that this book appears. I would like to thank the following people for their assistance during the preparation of this book. Many thanks to my colleagues at Howard University (Don M. Coleman, Bernard Woolfolk, and Reza Hashemi) for many helpful discussions of object-oriented design and programming and C++ in particular and for reading portions of this manu­ script. Bernard also provided excellent insights into the object-oriented paradigm when he was a Visiting Professor at Howard on leave from AT&T. Anne Santos of After- Math provided helpful technical services. My editor at AP PROFESSIONAL, Charles Glaser, deserves special thanks for the continued encouragement to do this project and many helpful suggestions during the writing process. Many thanks to the AP PRO­ FESSIONAL "book team," Cindy Kogut and David Hannon. Software Engineering Principles T he term "software engineering" refers to a generally accepted set of goals for the analysis, design, implementation, testing, and maintenance of software. These software engineering goals include efficiency, reliability, usability, modi- fiability, portability, testability, reusability, maintainability, interoperability, and correct­ ness. These terms refer both to systems and to their components. Many of the terms are self-explanatory; however, their definitions are included for completeness. Efficiency: The software is produced in the expected time and within the limits of the available resources. The software produced runs within the time expected. Reliability: The software performs as expected. In multiuser systems, the system performs its functions even with other loads on the system. Usability: The software can be used properly without a huge investment in training. This generally refers to the ease of use of the user interface but also concerns the applicability of the software to the computer environment. Modifiability: The software can be easily changed if the requirements of the system change. Portability: The software system can be transferred to other computers or systems without major rewriting of the software. Software that needs only to be recompiled xiii xiv Software Engineering Principles in order to have a properly working system on the new machine is considered to be very portable. Testability: The software can be easily tested. This generally means that the software is written in a modular manner. Reusability: Some or all of the software can be used again in other projects. This means that the software is modular, that each individual module has a well-defined interface, and that each individual module has a clearly defined outcome from its execution. This often means that there is a substantial level of abstraction and gen­ erality in the modules that will be reused most often. Maintainability: The software can be easily understood and changed over time. This term is used to describe the lifetime of systems such as the air traffic control system that must operate for decades. Interoperability: The software system can interact properly with other systems. This can apply to software on a single, stand-alone computer or to software that is used on a network. Correctness: The program produces the correct output. These goals, while noble, do not help with the design of software that meets such goals. The choice of proper software design methodologies is currendy a matter of con­ siderable debate in academia, government, and industry. Some commonly used meth­ ods are data-structured systems design, Jackson structured design, data-flow design, rapid prototyping, spiral designs, etc. All these methods are useful in certain software projects. These methods were originally developed for programs written in procedural languages such as Ada, Pascal, or C. This book will emphasize the use of object-oriented methods in software engineer­ ing. We are not going to follow a particular object-oriented method of software engi­ neering and exclude consideration of all others. Instead we will show how systems can be designed in C++ using the software engineering principles described in this chapter. Software engineering will be a recurring theme in this book. The early chapters will emphasize correctness and reusability along with an introduction to the fundamentals of object-oriented design, object-oriented programming, and their implementation in the C++ programming language. The later chapters will include discussions of larger software systems and will describe some of the trade-offs involved in design decisions and methods used. The effect of a programming language such as C++ that supports object-oriented programming for the software engineering goals described in this chap­ ter will become evident when we study larger systems. (Technically, C++ is considered to be a hybrid language, because it contains support for both object-oriented and tradi­ tional procedurally oriented software engineering.) CHAPTER Overview of C++ 1.1 What Is Object-Oriented Programming? You have probably heard a lot of discussion about the C++ language and object-orient­ ed programming. Some people claim that using the technique of object-oriented pro­ gramming with languages such as C++ will automatically solve most of the major prob­ lems in software engineering. This was the intention of Bjarne Stroustrup, who is commonly considered to be the creator of the C++ language. Object-oriented languages are actually much older than C++; one of the earliest object-oriented languages was Simula, which was developed in 1967. Proponents of the object-oriented approach believe that the combination of object- oriented design and object-oriented programming provides a more natural framework for the software development process and for the reuse of previously developed software. Unfortunately, most experienced computer professionals have a healthy skepticism about the ability of any new programming paradigm to provide easier solutions to software engineering problems. It is difficult for the person new to this subject to distinguish between what is clearly true, what is clearly untrue, what is likely to be true but is cur- rendy unproven, and what requires special analysis of its utility in a given situation. 3 4 Part I • Fundamental Principles We will not indulge in hyperbole. Instead, we will present a relatively complete description of the C++ programming language and develop several relatively large sys­ tems in order to demonstrate the utility of the object-oriented paradigm. You may also have heard the statement that C++ is a superset of C. This is technically correct. C++ is a superset of ANSI C in the sense that a program in ANSI C can generally be compiled without major changes by a C++ compiler, except for differences in access to the standard libraries. However, anyone faced with the problem of using C++ for a soft­ ware system of any size has found that there are several subde differences in the semantics of C and C++, at least in the way that the semantics of the languages are implemented by various compiler writers. At the time that this book is being written, there is no official standard for C++ that is as universally accepted as the ANSI standard for C. The basic principle of object-oriented programming is that a software system can be viewed as a sequence of "transformations" on a set of "objects." The terms "transforma­ tions" and "object" are difficult to define in a precise sense for a variety of technical rea­ sons and therefore we will not attempt formal descriptions. To see the difficulty in making a precise definition, consider the following definition of an object by Yourdon and Coad: An object is an abstraction of something in the domain of the problem or its implementation, reflecting the capabilities of a system to keep information about it, interact with it, or both. An alternative definition was made by Booch: An object has state, behavior, and identity. Many other authors have different, but similar, definitions. Don't worry if you have trouble understanding the differences between the various definitions. We will illustrate the concepts by many examples so that you will be able to recognize them when they appear. Object-oriented programming differs from the more familiar "procedural program­ ming" in which the basic principle is that a software system is a sequence of operations on data. (The term imperative programming is often used instead of procedural pro­ gramming.) The level of abstraction of object-oriented programming is generally higher than that of procedural programming. (Both views of programming are different from logic programming. We will not discuss logic programming in this book.) Here is a simple example of the different viewpoints of object-oriented and procedu- rally oriented programming—a stack. In a procedural language such as C or Pascal, we can define a data type called stack (or similar) and define variables of this type. The standard operations on a stack might be implemented in functions called push( ), One • Overview of C++ 5 P°P ( ) > or enipty ( ). Depending on the language and the degree to which the details of implementation of the stack are hidden, the user of a stack within a program can be restricted to the previously defined functions. Recall that in C, use of the typedef construction can allow the same functions to be used for stacks of floats instead of stacks of integers. The change of the type of contents of the stack can be done by a sim­ ple change of a data type in a header file and a recompilation. Thus a stack of integer elements might look something like the following: /* Typical C definition of a stack of ints. */ #define MAXSTACK 20 struct stack { int item [MAXSTACK]; int top; }; typedef struct stack stack; while a stack of floating point numbers might look like /* Typical C definition of a stack of floats. */ Idefine MAXSTACK 20 struct stack { float item[MAXSTACK]; int top; }; typedef struct stack stack; However, the support for stack operations is not restricted to the functions designed by the programmer. It is easy to write other functions that manipulate the data within a stack while ignoring the fundamental stack feature of having only last-in, first-out access to the elements of the stack. For example, we could theoretically write a function change2 ( ) that would change the value of the second element from the top of the stack by direcdy manipulating the variable top. Code for this function might be: stack s; void change2(int value) { s.itern[top - 1] = value; }