00 239-5 FM 2/19/99 12:54 PM Page i C++ Jesse Liberty with Vishwajit Aklecha Steve Haines Steven Mitchell Alexander Nickolov Charles Pace Meghraj Thakkar Michael J. Tobler Donald Xie Steve Zagieboylo 201 West 103rd Street Indianapolis,Indiana 46290 Unleashed P/V Unleashed generic ISBN# Name Date FM Lp#1 00 239-5 FM 2/19/99 12:54 PM Page ii C++ Unleashed EXECUTIVE EDITOR Tracy Dunkelberger Copyright © 1999 by Sams AQUISITIONS EDITOR All rights reserved. No part of this book shall be reproduced,stored in a Tracy Dunkelberger retrieval system,or transmitted by any means,electronic,mechanical,photo- copying,recording,or otherwise,without written permission from the publish- DEVELOPMENT EDITOR er. No patent liability is assumed with respect to the use of the information Sean Dixon contained herein. Although every precaution has been taken in the preparation MANAGINGEDITOR of this book,the publisher and author assume no responsibility for errors or Jodi Jensen omissions. Neither is any liability assumed for damages resulting from the use of the information contained herein. PROJECTEDITOR Maureen A. McDaniel International Standard Book Number:0-672-31239-5 Library of Congress Catalog Card Number:97-69859 COPYEDITOR Alice Martina-Smith First Printing:November 1998 INDEXER 00 99 98 4 3 2 1 Rebecca Salerno Printed in the United States of America PROOFREADER Trademarks Mona Brown All terms mentioned in this book that are known to be trademarks or service TECHNICALEDITOR marks have been appropriately capitalized. Sams Publishing cannot attest to Jay Armstrong the accuracy of this information. Use of a term in this book should not be Poney Carpenter regarded as affecting the validity of any trademark or service mark. Dan Clamage Tom Collins Windows is a registered trademark of Microsoft Corporation. Russ Jacobs Steven Mitchell Warning and Disclaimer David Thompson Every effort has been made to make this book as complete and as accurate as SOFTWAREDEVELOPMENT possible,but no warranty or fitness is implied. The information provided is on SPECIALIST an “as is”basis. The authors and the publisher shall have neither liability nor Dan Scherf responsibility to any person or entity with respect to any loss or damages aris- ing from the information contained in this book or from the use of the CD- TEAMCOORDINATOR ROM or programs accompanying it. Michelle Newcomb COVERDESIGNER Aren Howell INTERIORDESIGNER Gary Adair LAYOUTTECHNICIANS Ayanna Lacey Heather Hiatt Miller P/V Unleashed generic ISBN# Name Date FM Lp#1 00 239-5 FM 2/19/99 12:54 PM Page iii Contents at a Glance Introduction 1 PART I OBJECT-ORIENTED PROGRAMMING 5 1 Object-Oriented Analysis and Design 7 2 Implementing Class Design in C++ 45 3 Inheritance,Polymorphism,and Code Reuse 77 PART II IMPLEMENTATION ISSUES 123 4 Memory Management 125 5 How To Use Frameworks 169 6 Standard Template Library Container Classes 217 7 STL Iterators and Algorithms 285 8 Avoiding Name Clashes by Using Namespaces 361 9 Manipulating Object Types at Runtime 381 10 Tuning Application Performance 405 PART III MANIPULATING DATA 429 11 Recursion and Recursive Data Structures 431 12 Designing Efficient Sorting Methods 451 13 Search Algorithms in C++ 483 14 Hashing and Parsing Techniques 513 PART IV OBJECT PERSISTENCE AND ENCRYPTION 541 15 Object Persistence 543 16 Relational Databases and Persistence 621 17 Object Persistence Using Relational Databases 651 18 Object-Oriented Databases 677 19 Protecting Applications Using Encryption 737 P/V Unleashed generic ISBN# Name Date FM Lp#1 00 239-5 FM 2/19/99 12:54 PM Page iv PART V DISTRIBUTED COMPUTING TOPICS 777 20 CORBA 779 21 COM 809 22 Java and C++ 851 INDEX 877 P/V Unleashed generic ISBN# Name Date FM Lp#1 00 239-5 FM 2/19/99 12:54 PM Page v v CONTENTS Contents INTRODUCTION 1 What Is Covered......................................................................................1 Part I,“Object-Oriented Programming”............................................1 Part II,“Implementation Issues”........................................................1 Part III,“Manipulating Data” ............................................................2 Part IV,“Object Persistence and Encryption”....................................2 Part V,“Distributed Computing Topics”............................................2 What You Need To Know Already..........................................................2 What Software You Need........................................................................3 How To Read This Book ........................................................................3 PART I OBJECT-ORIENTED PROGRAMMING 5 1 OBJECT-ORIENTEDANALYSISANDDESIGN 7 Building Models......................................................................................8 Software Design:The Modeling Language............................................9 Software Design:The Process ..............................................................10 The Vision..............................................................................................13 Requirements Analysis..........................................................................13 Use Cases..........................................................................................14 Application Analysis........................................................................24 Systems Analysis..............................................................................25 Planning Documents........................................................................25 Visualizations....................................................................................26 Artifacts............................................................................................26 Design....................................................................................................27 What Are the Classes?......................................................................28 Transformations................................................................................30 Static Model......................................................................................31 Dynamic Model................................................................................40 Summary................................................................................................43 2 IMPLEMENTINGCLASSDESIGNINC++ 45 Translating Class Diagrams into C++ ..................................................46 Standard Classes ..............................................................................46 Template Classes..............................................................................48 Utility Classes..................................................................................49 Associations......................................................................................50 Aggregations....................................................................................56 Generalization..................................................................................58 Translating Interaction Diagrams into C++..........................................61 P/V Unleashed generic ISBN# Name Date FM Lp#1 00 239-5 FM 2/19/99 12:54 PM Page vi C++ vi UNLEASHED Implementing Collaboration Diagrams and Sequence Diagrams in C++ ..........................................................................62 Translating State Transition Diagrams into C++..................................68 Translating Activity Diagrams into C++ ..............................................72 Summary................................................................................................76 3 INHERITANCE, POLYMORPHISM, ANDCODEREUSE 77 Benefits of Inheritance..........................................................................78 Object-Oriented Linked Lists................................................................79 Designing the Linked List................................................................79 Implementing the Linked List..........................................................81 Abstract Classes ....................................................................................87 Overriding Pure Virtual Methods ....................................................93 Virtual Destructors ................................................................................94 Polymorphism Through Method Overloading......................................94 Memory Management............................................................................98 Issues in Overloading Other Operators ..............................................103 Assignment Operator......................................................................104 Overloading the Increment Operators............................................107 Virtual Copy Constructors..............................................................111 Multiple Inheritance............................................................................112 Problems in Multiple Inheritance ..................................................113 Multiple Inheritance Versus Containment......................................118 Summary..............................................................................................120 PART II IMPLEMENTATION ISSUES 123 4 MEMORYMANAGEMENT 125 Memory Management and Pointers....................................................127 Memory Leaks................................................................................131 Allocating Arrays............................................................................131 Stray,Dangling,and Wild Pointers................................................133 constPointers ..............................................................................134 constPointers and constMember Functions ............................134 Passing By Reference ....................................................................135 Passing a constPointer................................................................135 Don’t Return a Reference to an Object That Isn’t in Scope..........136 Pointer,Pointer,Who Has the Pointer?..........................................139 Pointers and Exceptions......................................................................140 Using Auto Pointers........................................................................146 Reference Counting........................................................................152 Summary..............................................................................................167 P/V Unleashed generic ISBN# Name Date FM Lp#1 00 239-5 FM 2/19/99 12:54 PM Page vii vii CONTENTS 5 HOWTOUSEFRAMEWORKS 169 The Microsoft Foundation Classes......................................................170 Getting Started................................................................................170 Other Wizards ................................................................................174 Gaining Perspective ............................................................................175 Application Architecture................................................................175 Multithreading................................................................................175 Cooperative Versus Preemptive Multithreading ............................176 Issues in Preemptive Multithreading ..................................................177 A Brief Case Study..............................................................................178 Creating Threads............................................................................179 Utility Classes......................................................................................199 String Manipulation Classes..........................................................199 Time Classes..................................................................................199 Documents and Views..........................................................................201 Views..............................................................................................201 Summary..............................................................................................215 6 STANDARDTEMPLATELIBRARYCONTAINERCLASSES 217 Defining and Instantiating Templates..................................................218 Defining and Instantiating Function Templates ............................218 Defining and Instantiating Class Templates ..................................219 Understanding Sequence Containers ..................................................221 The Vector Container......................................................................221 The List Container..........................................................................240 The Deque Container......................................................................253 Understanding Stacks..........................................................................255 Understanding Queues ........................................................................259 Priority Queues ..............................................................................262 Understanding Associative Containers................................................263 The Map Container........................................................................263 The Multimap Container................................................................277 The Set Container ..........................................................................279 The Multiset Container..................................................................280 Considering Performance Issues..........................................................280 Using the Standard C++ Library ........................................................282 Designing Element Types....................................................................283 Summary..............................................................................................284 7 STL ITERATORSANDALGORITHMS 285 Iterator Classes....................................................................................286 Position Within a Container ..........................................................286 Types of Iterators In and Out of Containers..................................286 Base Iterator Class..........................................................................287 Input Iterators ................................................................................289 P/V Unleashed generic ISBN# Name Date FM Lp#1 00 239-5 FM 2/19/99 12:54 PM Page viii C++ viii UNLEASHED Output Iterators..............................................................................290 Forward Iterators............................................................................291 Bidirectional Iterators ....................................................................291 Random Access Iterators................................................................291 Iterator Operations..........................................................................291 Standard Iterator Classes................................................................293 Function Objects..................................................................................296 Predicates........................................................................................297 Arithmetic Functions......................................................................298 Algorithm Classes................................................................................299 Non-Mutating Sequence Operations..............................................299 Mutating Sequence Algorithms......................................................311 Sorting and Related Sequence Operations ....................................327 Standard Function Compositions ..................................................352 Summary..............................................................................................360 8 AVOIDINGNAMECLASHESBYUSINGNAMESPACES 361 Functions and Classes Are Resolved by Name ..................................362 Creating a Namespace ........................................................................366 Declaring and Defining Types........................................................367 Defining Functions Outside a Namespace ....................................367 Adding New Members ..................................................................368 Nesting Namespaces......................................................................369 Using a Namespace..............................................................................369 The usingKeyword............................................................................373 The usingDirective......................................................................373 The usingDeclaration..................................................................375 The Namespace Alias..........................................................................376 The Unnamed Namespace ..................................................................377 The Standard Namespace std ............................................................378 Summary..............................................................................................379 9 MANIPULATINGOBJECTTYPESATRUNTIME 381 The typeid()Operator......................................................................382 The type_infoClass ........................................................................383 The Constructor for the type_infoClass....................................383 The Comparison Operators............................................................383 The name()Member Function......................................................385 The before()Member Function..................................................388 The typeid()Operator in Constructors and Destructors............389 Misuses of typeid()....................................................................390 Dynamic Typecasting of Objects........................................................392 The dynamic_cast()Operator..................................................392 The typeid()Versus the dynamic_castOperator..................398 P/V Unleashed generic ISBN# Name Date FM Lp#1 00 239-5 FM 2/19/99 12:54 PM Page ix ix CONTENTS Other Cast Operators ..........................................................................398 The static_cast()Operator......................................................398 The reinterpret_cast()Operator ..........................................400 When to Use the dynamic_cast(),static_cast(), or reinterpret_cast()Operator ..........................................401 The const_cast()Operator........................................................401 New Versus Old Typecasting ..............................................................402 Summary..............................................................................................404 10 TUNINGAPPLICATIONPERFORMANCE 405 Inline Functions Outside Class Definitions ........................................406 Avoid Revealing Implementation Code in Distributed Header Files ..................................................................................................412 Analyzing the Cost of Virtual Functions and Virtual Base Classes....413 Virtual Functions............................................................................414 Virtual Base Classes ......................................................................418 RTTI Trade-Offs..................................................................................422 Managing Memory for Temporary Objects........................................425 Summary..............................................................................................428 PART III MANIPULATING DATA 429 11 RECURSIONANDRECURSIVEDATASTRUCTURES 431 What Is Recursion?..............................................................................432 Fibonacci Numbers:A Recursive Definition ................................432 Stopping the Recursion..................................................................434 Recursive Structures............................................................................435 Traversing a Recursive Structure with a Recursive Function..............437 Recursion Versus Iteration and Tail Recursion....................................441 Tail Recursion................................................................................445 Indirect Recursion................................................................................446 Recursion and the Stack......................................................................447 Debugging Recursive Functions..........................................................449 Summary..............................................................................................449 12 DESIGNINGEFFICIENTSORTINGMETHODS 451 Analyzing the Performance of Algorithms..........................................452 Comparing the Average,Worst,and Best Cases............................453 The Stability of Sorts......................................................................454 Using Additional Storage During Sorting......................................454 The Bubble Sort ..................................................................................455 Analysis of the Bubble Sort ..........................................................457 P/V Unleashed generic ISBN# Name Date FM Lp#1