 |
 |
||||||||
| Home | College | Alumni | Career | Reference | About |
|
Thinking In C++ Volume 2: Practical Programming Bruce Eckel, President, MindView, Inc.
©2004
MindView, Inc.
All rights reserved. No part of this book may be reproduced in any form or by any electronic or mechanical means including information storage and retrieval systems without permission in writing from the publisher or authors, except by a reviewer who may quote brief passages in a review. Any of the names used in the examples and text of this book are fictional; any relationship to persons living or dead or to fictional characters in other works is purely coincidental. Dedication To all those who have
worked tirelessly Preface 19 Goals........................................ 19 Chapters................................... 20 Exercises................................... 23 Exercise solutions............. 23 Source code............................... 23 Language standards................... 25 Language support............. 25 Seminars, CD-ROMs & consulting. 25 Errors....................................... 26 About the cover......................... 26 Acknowledgements..................... 26 Building Stable Systems 29 1: Exception handling 31 Traditional error handling............. 32 Throwing an exception................ 34 Catching an exception................. 36 The try block.................... 36 Exception handlers........... 36 Exception matching..................... 39 Catching any exception..... 42 Re-throwing an exception.. 42 Uncaught exceptions......... 43 Cleaning up................................ 45 Resource management..... 47 Making everything an object 49 auto_ptr.......................... 52 Function-level try blocks.... 53 Standard exceptions................... 55 Exception specifications............... 59 Better exception specifications? 64 Exception specifications and inheritance 65 When not to use exception specifications 66 Exception safety......................... 67 Programming with exceptions....... 72 When to avoid exceptions.. 72 Typical uses of exceptions. 74 Overhead................................... 78 Summary................................... 80 Exercises................................... 81 2: Defensive programming 83 Assertions................................. 86 A simple unit test framework........ 90 Automated testing............ 92 The TestSuite Framework.. 97 Test suites..................... 101 The test framework code. 102 Debugging techniques............... 110 Trace macros................. 110 Trace file....................... 111 Finding memory leaks..... 112 Summary................................. 119 Exercises................................. 120 The Standard C++ Library 125 3: Strings in depth 127 What’s in a string?.................... 128 Creating and initializing C++ strings 130 Operating on strings................. 133 Appending, inserting, and concatenating strings 134 Replacing string characters 136 Concatenation using nonmember overloaded operators 141 Searching in strings.................. 142 Finding in reverse........... 147 Finding first/last of a set of characters 148 Removing characters from strings 150 Comparing strings.......... 153 Strings and character traits 157 A string application................... 164 Summary................................. 170 Exercises................................. 170 4: Iostreams 171 Why iostreams?........................ 172 Iostreams to the rescue............ 177 Inserters and extractors.. 177 Common usage.............. 182 Line-oriented input.......... 185 Handling stream errors.............. 186 File iostreams........................... 190 A File-Processing Example 192 Open modes................... 194 Iostream buffering.................... 195 Seeking in iostreams................. 198 String iostreams....................... 202 Input string streams........ 203 Output string streams...... 205 Output stream formatting.......... 209 Format flags................... 209 Format fields.................. 211 Width, fill, and precision.. 213 An exhaustive example... 214 Manipulators............................. 218 Manipulators with arguments 219 Creating manipulators..... 223 Effectors........................ 224 Iostream examples.................... 227 Maintaining class library source code 227 Detecting compiler errors 232 A simple datalogger........ 235 Internationalization................... 240 Wide Streams................. 240 Locales.......................... 243 Summary................................. 246 Exercises................................. 246 5: Templates in depth 249 Template parameters................. 249 Non-type template parameters 250 Default template arguments 252 Template template parameters 254 The typename keyword... 261 Using the template keyword as a hint 264 Member Templates......... 266 Function template issues........... 269 Type deduction of function template arguments 269 Function template overloading 274 Taking the address of a generated function template 275 Applying a function to an STL sequence 279 Partial ordering of function templates 282 Template specialization............... 284 Explicit specialization....... 284 Partial Specialization....... 286 A practical example........ 289 Preventing template code bloat 293 Name lookup issues.................. 298 Names in templates........ 298 Templates and friends..... 304 Template programming idioms.... 311 Traits............................. 311 Policies.......................... 317 The curiously-recurring template pattern 321 Template metaprogramming....... 324 Compile-time programming 325 Expression templates...... 336 Template compilation models...... 343 The inclusion model........ 343 The separation model...... 347 Summary................................. 349 Exercises................................. 350 6: Generic algorithms 351 A first look............................... 351 Predicates...................... 355 Stream iterators............. 357 Algorithm complexity...... 360 Function objects....................... 361 Classification of function objects 363 Automatic creation of function objects 364 Adaptable function objects 368 More function object examples 370 Function pointer adapters 379 Writing your own function object adapters 386 A catalog of STL algorithms....... 390 Support tools for example creation 393 Filling and generating...... 397 Counting........................ 399 Manipulating sequences... 400 Searching and replacing.. 406 Comparing ranges.......... 415 Removing elements........ 419 Sorting and operations on sorted ranges 423 Heap operations............. 434 Applying an operation to each element in a range 436 Numeric algorithms......... 445 General utilities.............. 449 Creating your own STL-style algorithms 451 Summary................................. 453 Exercises................................. 453 7: Generic containers 461 Containers and iterators............ 461 STL reference documentation 463 A first look............................... 464 Containers of strings....... 470 Inheriting from STL containers 472 A plethora of iterators............... 475 Iterators in reversible containers 477 Iterator categories.......... 478 Predefined iterators........ 481 The basic sequences: vector, list, deque 487 Basic sequence operations 487 vector............................ 491 deque............................ 498 Converting between sequences 501 Checked random-access. 504 list................................. 505 Swapping basic sequences 512 set.......................................... 513 A completely reusable tokenizer 516 stack....................................... 522 queue...................................... 526 Priority queues......................... 531 Holding bits.............................. 541 bitset<n>....................... 542 vector<bool>................. 547 Associative containers............... 548 Generators and fillers for associative containers 554 The magic of maps......... 557 Multimaps and duplicate keys 559 Multisets........................ 563 Combining STL containers.......... 567 Cleaning up containers of pointers 570 Creating your own containers..... 572 STL extensions......................... 575 Non-STL containers.................. 577 Summary................................. 582 Exercises................................. 583 Special Topics 587 8: Runtime type identification 589 Runtime casts.......................... 589 The typeid operator.................. 595 Casting to intermediate levels 598 void pointers.................. 599 Using RTTI with templates 600 Multiple inheritance.................... 601 Sensible uses for RTTI............... 602 A trash recycler.............. 603 Mechanism and overhead of RTTI 608 Summary................................. 609 Exercises................................. 610 9: Multiple inheritance 611 Perspective............................... 611 Interface inheritance.................. 613 Implementation inheritance........ 617 Duplicate subobjects................. 624 Virtual base classes................... 629 Name lookup issues.................. 639 Avoiding MI.............................. 643 Extending an interface............... 644 Summary................................. 649 Exercises................................. 649 10: Design patterns 651 The pattern concept.................. 651 The singleton........................... 653 Variations on singleton.... 654 Classifying patterns................... 659 Features, idioms, patterns 660 Building complex objects........... 661 Factories: encapsulating object creation 669 Polymorphic factories...... 672 Abstract factories............ 675 Virtual constructors......... 678 Observer.................................. 686 The “inner class” idiom.... 689 The observer example.... 693 Multiple dispatching................... 697 Multiple dispatching with Visitor 701 Exercises................................. 704 11: Concurrency 706 Motivation................................ 707 Concurrency in C++.................. 708 Installing Zthreads.......... 709 Defining Tasks.......................... 711 Using Threads.......................... 713 Creating responsive user interfaces 715 Managing Tasks.............. 717 Simplifying with Executors 718 Yielding.......................... 721 Sleeping........................ 723 Priority.......................... 725 Sharing limited resources........... 727 Ensuring the existence of objects 728 Improperly accessing resources 731 Controlling access........... 735 Simplified coding with Guards 737 Thread local storage....... 741 Terminating tasks...................... 743 Preventing iostream collision 743 The Ornamental Garden.. 744 Terminating when blocked 750 Interruption.................... 751 Cooperation between threads..... 757 Wait and signal............... 758 Broadcast...................... 763 Producer-Consumer relationships 766 Solving Threading problems with Queues 770 Deadlock.................................. 775 Summary................................. 783 Exercises................................. 784 A: Recommended reading 789 C............................................ 789 General C++............................ 789 Bruce’s books................. 790 Depth & dark corners................ 790 The STL................................... 791 Design Patterns........................ 791 B: Etc 793 Index 801
PrefaceIn Volume 1 of this book, you learn the fundamentals of C and C++. In this volume, we look at more advanced features, with an eye towards developing techniques and ideas that produce robust C++ programs. Thus, in this volume we are assuming that you are familiar with the material developed in Volume 1. Comment GoalsOur goals in this book are to:Comment 1. Present the material a simple step at a time, so the reader can easily digest each concept before moving on. 2. Teach “practical programming” techniques that you can use on a day-to-day basis. 3. Give you what we think is important for you to understand about the language, rather than everything we know. We believe there is an “information importance hierarchy,” and there are some facts that 95% of programmers will never need to know, but that would just confuse people and add to their perception of the complexity of the language. To take an example from C, if you memorize the operator precedence table (we never did) you can write clever code. But if you have to think about it, it will confuse the reader/maintainer of that code. So forget about precedence, and use parentheses when things aren’t clear. This same attitude will be taken with some information in the C++ language, which is more important for compiler writers than for programmers. 4. Keep each section focused enough so the lecture time – and the time between exercise periods – is small. Not only does this keep the audience’ minds more active and involved during a hands-on seminar, but it gives the reader a greater sense of accomplishment. 5. We have endeavored not to use any particular vendor’s version of C++. We have tested the code on all the implementations we could, and when one implementation absolutely refused to work because it doesn’t conform to the C++ Standard, we’ve flagged that fact in the example (you’ll see the flags in the source code) to exclude it from the build process. 6. Automate the compiling and testing of the code in the book. We have discovered that code that isn’t compiled and tested is probably broken, so in this volume we’ve instrumented the examples with test code. In addition, the code that you can download from http://www.MindView.net has been extracted directly from the text of the book using programs that also automatically create makefiles to compile and run the tests. This way we know that the code in the book is correct. ChaptersHere is a brief description of the chapters contained in this book: Part 1: Building Stable Systems 1. Exception handling. Error handling has always been a problem in programming. Even if you dutifully return error information or set a flag, the function caller may simply ignore it. Exception handling is a primary feature in C++ that solves this problem by allowing you to “throw” an object out of your function when a critical error happens. You throw different types of objects for different errors, and the function caller “catches” these objects in separate error handling routines. If you throw an exception, it cannot be ignored, so you can guarantee that something will happen in response to your error. The decision to use exceptions (a good one!) affects code design in fundamental ways. Comment 2. Defensive Programming. Many software problems can be prevented. To program defensively is to craft code in such a way that bugs can be found and fixed early before they have a chance to do damage in the field. The use of assertions is the single most important thing you can do to validate your code during development, while at the same time leaving an executable documentation trail in your code that reveals what you were thinking when you wrote the code in the first place. Before you let your code out of your hands it should be rigorously tested. A framework for automated unit testing is an indispensable tool for successful, everyday software development. Part 2: The Standard C++ Library 3. Strings in Depth. Text processing is the most common programming activity by far. The C++ string class relieves the programmer from memory management issues, while at the same time delivering a powerhouse of text processing capability. C++ also supports the use of wide characters and locales for internationalized applications. 4. Iostreams. One of the original C++ libraries – the one that provides the essential I/O facility – is called iostreams. Iostreams is intended to replace C’s stdio.h with an I/O library that is easier to use, more flexible, and extensible – you can adapt it to work with your new classes. This chapter teaches you the ins and outs of how to make the best use of the existing iostream library for standard I/O, file I/O, and in-memory formatting.Comment 5. Templates in Depth. The distinguishing feature of “modern C++” is the broad power of templates. Templates are for more than just generic containers; they support development of robust, generic, high-performance libraries. There is a lot to know about templates—they constitute, as it were, a sub-language within the C++ language, and give the programmer an impressive degree of control over the compilation process. It is not an understatement to say that templates have revolutionized C++ programming. 6. Generic Algorithms. Algorithms are at the core of computing, and C++, through its template facility, supports an impressive entourage of powerful, efficient, and easy-to-use generic algorithms. The standard algorithms are also customizable through function objects. This chapter looks at every algorithm in the library. (Chapters 6 and 7 cover that portion of the standard C++ library commonly-known as the Standard Template Library, or STL.) 7. Generic Containers & Iterators. C++ supports all the common data structures known to man in a type-safe manner. You never have to worry about what such a container holds; the homogeneity of its objects is guaranteed. Separating the traversing of a container from the container itself, another accomplishment of templates, is made possible through iterators. This ingenious arrangement allows a flexible application of algorithms to containers by means of the simplest of designs. Part 3: Special Topics 8. Run-time type identification. Run-time type identification (RTTI) lets you find the exact type of an object when you only have a pointer or reference to the base type. Normally, you’ll want to intentionally ignore the exact type of an object and let the virtual function mechanism implement the correct behavior for that type. But occasionally (like when writing software tools such as debuggers) it is very helpful to know the exact type of an object for which you only have a base pointer; often this information allows you to perform a special-case operation more efficiently. This chapter explains what RTTI is for and how to use it. Comment 9. Multiple inheritance. This sounds simple at first: A new class is inherited from more than one existing class. However, you can end up with ambiguities and multiple copies of base-class objects. That problem is solved with virtual base classes, but the bigger issue remains: When do you use it? Multiple inheritance is only essential when you need to manipulate an object through more than one common base class. This chapter explains the syntax for multiple inheritance, and shows alternative approaches – in particular, how templates solve one common problem. The use of multiple inheritance to repair a “damaged” class interface is demonstrated as a genuinely valuable use of this feature.Comment 10. Design Patterns. The most revolutionary advance in programming since objects is the introduction of design patterns. A design pattern is a language-independent codification of a solution to a common programming problem, expressed in such a way that it can apply to many contexts. Patterns such as Singleton, Factory Method, and Visitor now find their way into daily discussions around the keyboard. This chapter shows how to implement and use some of the more useful design patterns in C++. 11. Concurrent Programming. Users have long been used to responsive user interfaces that (seem to) process multiple tasks simultaneously. Modern operating systems allow processes to have multiple threads that share the process address space. Multi-threaded programming requires a different mindset, however, and comes with its own set of “gotchas.” This chapter uses a freely available library (Eric Crahen’s ZThread library) to show how to effectively manage multi-threaded applications in C++. ExercisesWe have discovered that simple exercises are exceptionally useful during a seminar to complete a student’s understanding, so you’ll find a set at the end of each chapter.Comment These are fairly simple, so they can be finished in a reasonable amount of time in a classroom situation while the instructor observes, making sure all the students are absorbing the material. Some exercises are a bit more challenging to keep advanced students entertained. They’re all designed to be solved in a short time and are only there to test and polish your knowledge rather than present major challenges (presumably, you’ll find those on your own – or more likely they’ll find you).Comment Exercise solutionsSolutions to exercises can be found in the electronic document The C++ Annotated Solution Guide, Volume 2, available for a nominal fee from www.MindView.net. Comment Source codeThe source code for this book is copyrighted freeware, distributed via the web site http://www.MindView.net. The copyright prevents you from republishing the code in print media without permission.Comment In the starting directory where you unpacked the code you will find the following copyright notice:Comment //:! :CopyRight.txt Copyright (c) MindView, Inc., 2003 Source code file from the book "Thinking in C++, 2nd Edition, Volume 2." All rights reserved EXCEPT as allowed by the following statements: You can freely use this file for your own work (personal or commercial), including modifications and distribution in executable form only. Permission is granted to use this file in classroom situations, including its use in presentation materials, as long as the book "Thinking in C++" is cited as the source. Except in classroom situations, you cannot copy and distribute this code; instead, the sole distribution point is http://www.MindView.net (and official mirror sites) where it is freely available. You cannot remove this copyright and notice. You cannot distribute modified versions of the source code in this package. You cannot use this file in printed media without the express permission of the author. The authors makes no representation about the suitability of this software for any purpose. It is provided "as is" without express or implied warranty of any kind, including any implied warranty of merchantability, fitness for a particular purpose or non-infringement. The entire risk as to the quality and performance of the software is with you. The authors and publisher shall not be liable for any damages suffered by you or any third party as a result of using or distributing software. In no event will the authors or the publisher be liable for any lost revenue, profit, or data, or for direct, indirect, special, consequential, incidental, or punitive damages, however caused and regardless of the theory of liability, arising out of the use of or inability to use software, even if Bruce Eckel and the publisher have been advised of the possibility of such damages. Should the software prove defective, you assume the cost of all necessary servicing, repair, or correction. If you think you've found an error, please submit the correction using the form you will find at www.MindView.net. (Please use the same form for non-code errors found in the book.) ///:~
You may use the code in your projects and in the classroom as long as the copyright notice is retained. Comment Language standardsThroughout this book, when referring to conformance to the ANSI/ISO C standard, we will be referring to the 1989 standard, and will generally just say ‘C.’ Only if it is necessary to distinguish between Standard 1989 C and older, pre-Standard versions of C will we make the distinction. We do not reference C99 in this book. Comment As this book goes to press the ANSI/ISO C++ committee has long ago finished working on the first C++ standard, commonly known as C++98. We will use the term Standard C++ to refer to this standardized language. If we simply refer to C++ you should assume we mean “Standard C++.” The C++ standards committee continues to address issues important to the C++ community that will find expression in C++0x, a future C++ standard not likely to be available for many years. Comment Language supportYour compiler may not support all the features discussed in this book, especially if you don’t have the newest version of your compiler. Implementing a language like C++ is a Herculean task, and you can expect that the features will appear in pieces rather than all at once. But if you attempt one of the examples in the book and get a lot of errors from the compiler, it’s not necessarily a bug in the code or the compiler – it may simply not be implemented in your particular compiler yet. On the Windows platform we have validated all examples with the C++ compiler found in Microsoft’s Visual Studio .NET 2003; Borland C++Builder version 6; the GNU projects g++ compiler, version 3.2, running under Cygwin; and the Edison Design Groups C++ front end using the Dinkumware full C++ library. We have also run all the examples on MAC OS X with Metrowerks C++ version 8. In those instances where a compiler does not support the feature required by a sample program, we have so indicated in comments in the source code. Comment Seminars, CD-ROMs & consultingBruce Eckel’s company, MindView, Inc., provides public hands-on training seminars based on the material in this book, and also for advanced topics. Selected material from each chapter represents a lesson, which is followed by a monitored exercise period so each student receives personal attention. We also provide on-site training, consulting, mentoring, and design & code walkthroughs. Information and sign-up forms for upcoming seminars and other contact information can be found at http://www.MindView.net. Comment ErrorsNo matter how many tricks a writer uses to detect errors, some always creep in and these often leap off the page for a fresh reader. If you discover anything you believe to be an error, please use the feedback system built into the electronic version of this book, which you will find at http://www.MindView.net. The feedback system uses unique identifiers on the paragraphs in the book, so you should click on the identifier next to the paragraph that you wish to comment on. Your help is appreciated. Comment About the coverThe cover artwork was painted by Larry O’Brien’s wife, Tina Jensen (yes, the Larry O’Brien who was the editor of Software Development Magazine for so many years). Not only are the pictures beautiful, but they are excellent suggestions of polymorphism. The idea for using these images came from Daniel Will-Harris, the cover designer (www.Will-Harris.com), working with Bruce Eckel. AcknowledgementsVolume 2 of this book languished in a half-completed state for a long time while Bruce got distracted with other things, notably Java, Design Patterns and especially Python (see www.Python.org). If Chuck hadn’t been willing (foolishly, he has sometimes thought) to finish the other half and bring things up-to-date, this book almost certainly wouldn’t have happened. There aren’t that many people whom Bruce would have felt comfortable entrusting this book to. Chuck’s penchant for precision, correctness and clear explanation is what has made this book as good as it is. Jamie King acted as an intern under Chuck’s direction during the completion of this book. He has been instrumental in making sure the book got finished, not only by providing feedback for Chuck, but especially because of his relentless questioning and picking of every single possible nit that he didn’t completely understand. If your questions are answered by this book, it’s probably because Jamie asked them first. Jamie also enhanced a number of the sample programs and created many of the exercises at the end of each chapter. Eric Crahen has been instrumental in the completion of Chapter 11 (Concuurent Programming). When we were looking for a threads package, we sought out one that was intuitive and easy to use, while being sufficiently robust to do the job. With Eric we got that and then some—he has been extremely cooperative and has used our feedback to enhance his library, while we have benefited from his insights as well. We are grateful to have had Pete Becker as a technical editor. Few people are as articulate and discriminating as Pete, not to mention as expert in C++ and software development in general. We also thank Bjorn Karlsson for his gracious and timely technical assistance as he reviewed the entire manuscript with little notice. The ideas and understanding in this book have come from many other sources, as well: friends like Andrea Provaglio, Dan Saks, Scott Meyers, Charles Petzold, and Michael Wilk; pioneers of the language like Bjarne Stroustrup, Andrew Koenig, and Rob Murray; members of the C++ Standards Committee like Nathan Myers (who was particularly helpful and generous with his insights), Herb Sutter, PJ Plauger, Pete Becker, Kevlin Henney, David Abrahams, Tom Plum, Reg Charney, Tom Penello, Sam Druker, and Uwe Steinmueller; people who have spoken in the C++ track at the Software Development Conference (which Bruce created and developed, and Chuck spoke in); and very often students in seminars, who ask the questions we need to hear in order to make the material clearer. Comment The book design, cover design, and cover photo were created by Bruce’s friend Daniel Will-Harris, noted author and designer, who used to play with rub-on letters in junior high school while he awaited the invention of computers and desktop publishing. However, we produced the camera-ready pages ourselves, so the typesetting errors are ours. Microsoft® Word XP was used to write the book and to create camera-ready pages. The body typeface is Georgia and the headlines are in Verdana. Comment We also wish to thank the generous professionals at the Edison Design Group and Dinkumware, Ltd., for giving us complimentary copies of their compiler and library (respectively). Without their assistance some of the examples in this book could not have been tested. We also wish to thank Howard Hinnant and the folks at Metrowerks for a copy of their compiler, and Sandy Smith and the folks at SlickEdit for keeping Chuck supplied with a world-class editing environment for so may years. Greg Comeau also provided a copy of his successful EDG-based compiler, Comeau C++. A special thanks to all our teachers, and all our students (who are our teachers as well). Evan Cofsky (Evan@TheUnixMan.com) provided all sorts of assistance on the server as well as development of programs in his now-favorite language, Python. Sharlynn Cobaugh and Paula Steuer were instrumental assistants, preventing Bruce from being washed away in a flood of projects. Dawn McGee provided much-appreciated inspiration and enthusiasm during this project. The supporting cast of friends includes, but is not limited to: Mark Western, Gen Kiyooka, Kraig Brockschmidt, Zack Urlocker, Andrew Binstock, Neil Rubenking, Steve Sinofsky, JD Hildebrandt, Brian McElhinney, Brinkley Barr, Larry O’Brien, Bill Gates at Midnight Engineering Magazine, Larry Constantine & Lucy Lockwood, Tom Keffer, Greg Perry, Dan Putterman, Christi Westphal, Gene Wang, Dave Mayer, David Intersimone, Claire Sawyers, The Italians (Andrea Provaglio, Laura Fallai, Marco Cantu, Michael Seaver, Huston Franklin, David Wagstaff, Corrado, Ilsa and Christina Giustozzi), Chris & Laura Strand, The Almquists, Brad Jerbic, John Kruth & Marilyn Cvitanic, Holly Payne (yes, the famous novelist!), Mark Mabry, The Robbins Families, The Moelter Families (& the McMillans), The Wilks, Dave Stoner, Laurie Adams, The Cranstons, Larry Fogg, Mike & Karen Sequeira, Gary Entsminger & Allison Brody, Chester Andersen, Joe Lordi, Dave & Brenda Bartlett, The Rentschlers, The Sudeks, Lynn & Todd, and their families. And of course, Mom & Dad, Sandy, James & Natalie, Kim& Jared, Isaac, Abbi, and even Sheba!
| ||||||||||||||||||||||||||
