泛型编程与STL（影印版） (2008 年度畅销榜NO.1102 )

许多程序员可能并不知道，C++不仅是一个面向对象程序语言，它还适用于泛型编程(generic programming)。这项技术可以大大增强你的能力，协助你写出高效率并可重复运用的软件组件(software components)。 \r\n 本书由知名的C++专家Matthew H.Austern执笔，引导你进入泛型编程思维模型，并将你带往此一模型的最重要成品：C++ Standard Template Library(STL)。本书揭示STL的奥秘，告诉你STL不仅仅是一组方便运用的容器类(container classes)。对于泛型组件和可交互作用的组件而言，STL是一个具备扩充能力的框架(framework)。 \r\n 本书阐述了泛型编程的中心思想：concepts、modeling、refinement，并为你展示这些思想如何导出STL的基础概念：iterators、containers、function Objects。循此路线，你可以把STL想像为一个由concepts(而非明确之functions或classes)组成的程序库。你将学习其正式结构并因此获得其潜在威力所带采的完整优势。 \r\n \r\n 作者简介 \r\n Matthew H.Austern：拥有博士学位，曾于MIT和UC Berkeley做研究。现任职于Silicon Graphics编译器团队，是SGI STL的主要作者。他是Dr.Dobb''s Journal和C++Report两本刊物的撰稿人，并主持newsgroup comp.std.c++，同时也是ISO/ANSI C++标准委员会的一位活跃成员。

Preface\r\nPart I Introduction to Generic Programming\r\nChapter 1 A Tour of the STL\r\n 1.1 A Simple Example\r\n 1.2 Summary\r\nChapter 2 Algorithms and Ranges\r\n 2.1 Linear Search\r\n 2.2 Concepts and Modeling\r\n 2.3 Iterators\r\n 2.4 Refinement\r\n 2.5 Summary\r\nChapter 3 More about Iterators\r\n 3.1 Iterator Traits and Associated Types\r\n 3.2 Defining New Components\r\n 3.3 Summary\r\nChapter 4 Function Objects\r\n 4.1 Generalizing Linear Search\r\n 4.2 Function Object Concepts\r\n 4.3 Function Object Adaptors\r\n 4.4 Predefined Function Objects\r\n 4.5 Summary\r\nChapter 5 Containers\r\n 5.1 A Simple Container\r\n 5.2 Container Concepts\r\n 5.3 Variable Size Container Concepts\r\n 5.4 Summary\r\nPart II Reference Manual: STL Concepts\r\nChapter 6 Basic Concepts\r\n 6.1 Assignable\r\n 6.2 Default Constructible\r\n 6.3 Equality Comparable\r\n 6.4 Ordering\r\nChapter 7 Iterators\r\n 7.1 Trivial Iterator\r\n 7.2 Input Iterator\r\n 7.3 Output Iterator\r\n 7.4 Forward Iterator\r\n 7.5 Bidirectional Iterator\r\n 7.6 Random Access Iterator\r\nChapter 8 Function Objects\r\n 8.1 Basic Function Objects\r\n 8.2 Adaptable Function Objects\r\n 8.3 Predicates\r\n 8.4. Specialized Concepts\r\nChapter 9 Containers\r\n 9.1 General Container Concepts\r\n 9.2 Sequences\r\n 9.3 Associative Containers\r\n 9.4 Allocator\r\nPart III Reference Manual: Algorithms and Classes\r\nChapter 10 Basic Components\r\n 10.1 pair\r\n 10.2 Iterator Primitives\r\n 10.3 allocator\r\n 10.4 Memory Management Primitives\r\n 10.5 Temporary Buffers\r\nChapter 11 Nonmutating Algorithms\r\n 11.1 Linear Search\r\n 11.2 Subsequence Matching\r\n 11.3 Counting Elements\r\n 11.4 for_each\r\n 11.5 Comparing Two Ranges\r\n 11.6 Minimum and Maximum\r\nChapter 12 Basic Mutating Algorithms\r\n 12.1 Copying Ranges\r\n 12.2 Swapping Elements\r\n 12.3 transform\r\n 12.4 Replacing Elements\r\n 12.5 Filling Ranges\r\n 12.6 Removing Elements\r\n 12.7 Permuting Algorithms\r\n 12.8 Partitions\r\n 12.9 Random Shuffling and Sampling\r\n 12.10 Generalized Numeric Algorithms\r\nChapter 13 Sorting and Searching\r\n 13.1 Sorting Ranges\r\n 13.2 Operations on Sorted Ranges\r\n 13.3 Heap Operations\r\nChapter 14 Iterator Classes\r\n 14.1 Insert Iterators\r\n 14.2 Stream Iterators\r\n 14.3 reverse_iterator\r\n 14.4 raw_storage_iterator\r\nChapter 15 Function Object Classes\r\n 15.1 Function Object Base Classes\r\n 15.2 Arithmetic Operations\r\n 15.3 Comparisons\r\n 15.4 Logical Operations\r\n 15.5 Identity and Projection\r\n 15.6 Specialized Function Objects\r\n 15.7 Member Function Adaptors\r\n 15.8 Other Adaptors\r\nChapter 16 Container Classes\r\n 16.1 Sequences\r\n 16.2 Associative Containers\r\n 16.3 Container Adaptors\r\nAppendix A Portability and Standardization\r\n A. 1 Language Changes\r\n A.2 Library Changes\r\n A.3 Naming and Packaging\r\nBibliography\r\nIndex\r\n

This is not a book about object-oriented programming. You may think that's odd. You probably found this book in the C++ section of the bookstore, after all, and you've probably heard people use object oriented and C++ synonymously, but that isn't the only way to use the C++ language. C++ supports several fundamentally different paradigms, the newest and least familiar of which is generic programming. Like most new ideas, generic programming actually has a long history. Some of the early research papers on generic programming are nearly 25 years old, and the first experimental generic libraries were written not in C++ but in Ada [MS89a, MS89b] and Scheme [KMS88]. Yet generic programming is new enough that no textbooks on the subject exist. The first example of generic programming to become important outside of research groups was the STL, the C++ Standard Template Library. The Standard Template Library, designed by Alexander Stepanov (then of Hewlett-Packard Laboratories) and Meng Lee, was accepted in 1994 as part of the C++ standard library. The freely available "HP implementation" [SL95], which served as a demonstration of the STL's capabilities, was released the same year. When the Standard Template Library first became part of the C++ standard, the C++ community immediately recognized it as a library of high-quality and efficient container classes. It is always easiest to see what is familiar, and every C++ programmer is familiar with container classes. Every nontrivial program requires some way of managing a collection of objects, and every C++ programmer has written a class that implements strings or vectors or lists. Container class libraries have been available since the earliest days of C++, and when "template" classes (parameterized types) were added to the language, one of their first uses--indeed, one of the main reasons that templates were introduced-was parameterized container classes. Many different vendors, including Borland, Microsoft, Rogue Wave, and IBM, wrote their own libraries that included Array or its equivalent. The fact that container classes are so familiar made the STL seem at first to be nothing more than yet another container class library. This familiarity diverted attention from the ways in which the STL was unique. The STL is a large and extensible body of efficient, generic, and interoperable software components. It includes many of the basic algorithms and data structures of computer science, and it is written so that algorithms and data structures are decoupled from each other. Rather than a container class library, it is more accurate to think of the STL as a library of generic algorithms; containers exist so that the algorithms have something to operate on. You can use the existing STL algorithms in your programs, just as you can use the existing STL containers. For example, you can use the generic STL sort as you would use the function qsort from the standard C library (although sort is simpler, more flexible, safer, and more efficient). Several books, including David Musser and Atul Saini's STL Tutorial and Reference Guide [MS96] and Mark Nelson's C++ Programmer's Guide to the Standard Template Library [Ne195], explain how to use the STL in such a way. Even this much is useful. It is always better to reuse code than to rewrite it, and you can reuse the existing STL algorithms in your own programs. This is still, however, only one aspect of the STL. The STL was designed to be extensible; that is, it was designed so that, just as the different STL components are interoperable with each other, they are also interoperable with components you write yourself. Using the STL effectively means extending it. Generic Programming The STL is not just a collection of useful components. Its other aspect, which is less widely recognized and understood, is that it is a formal hierarchy of abstract requirements that describe software components. The reason that the STL's components are interoperable and extensible, and the reason that you can add new algorithms and new containers and can be confident that the new pieces and the old can be used together, is that all STL components are written to conform to precisely specified requirements. Most of the important advances in computer science have been the discoveries of new kinds of abstractions. One crucial abstraction supported by all contemporary computer languages is the subroutine (a.k.a. the procedure or function—different languages use different terminology). Another abstraction supported by C++ is that of abstract data typing. In C++, it is possible to define a new data type together with that type's basic operations. The combination of code and data forms an abstract data type, one that is always manipulated through a well-defined interface. Subroutines are an important abstraction because using a subroutine doesn't require that you depend on (or even necessarily know) its exact implementation; similarly, you can use an abstract data type--you can manipulate and even create values--without depending on the actual representation of the data. Only the interface is important. C++ also supports object-oriented programming [Boo94, Mey97], which involves hierarchies of polymorphic data types related by inheritance. Object-oriented programming has one more layer of indirection than abstract data typing, thus it achieves one more step in abstraction. In some circumstances you can refer to a value and manipulate it without needing to specify its exact type. You can write a single function that will operate on a number of types within an inheritance hierarchy. Generic programming, too, means identifying a new kind of abstraction. The central abstraction of generic programming is less tangible than earlier abstractions like the subroutine or the class or the module. It is a set of requirements on data types. This is a difficult abstraction to grasp because it isn't tied to a specific C++ language feature. There is no keyword in C++ (or, for that matter, in any contemporary computer language) for declaring a set of abstract requirements. What generic programming provides in return for understanding an abstraction that at first seems frustratingly nebulous is an unprecedented level of fiexibility. Just as important, it achieves abstraction without loss of efficiency. Generic programming, unlike object-oriented programming, does not require you to call functions through extra levels of indirection; it allows you to write a fully general and reusable algorithm that is just as efficient as an algorithm handcrafted for a specific data type. A generic algorithm is written by abstracting algorithms on specific types and specific data structures so that they apply to arguments whose types are as general as possible. This means that a generic algorithm actually has two parts: the actual instructions that describe the steps of the algorithm and the set of requirements that specify precisely which properties its argument types must satisfy. The central innovation of the STL is the recognition that these type requirements can be specified and systematized. That is, it is possible to define a set of abstract concepts and to say that a type conforms to one of those concepts if it satisfies a certain set of requirements. These concepts are important because most of the assumptions that algorithms make about their types can be expressed both in terms of conformance to concepts and in terms of the relationships between different concepts. Additionally, these concepts form a well-defined hierarchy, one reminiscent of inheritance in traditional object-oriented programming but purely abstract. This hierarchy of concepts is the conceptual structure of the STL. It is the most important part of the STL, and it is what makes reuse and interoperability possible. The conceptual structure would be important purely as a formal taxonomy of software components, even without its embodiment in code. The STL does include concrete data structures, such as pair and list, but to use those data structure effectively you must understand the conceptual structure they are built upon. Defining abstract concepts and writing algorithms and data structures in of abstract concepts is the essence of generic programming. How to Read This Book This book describes the Standard Template Library as a library of abstract concepts. It defines the fundamental concepts and abstractions of the STL and shows what it means for a type to model one of those concepts or for an algorithm to be written in terms of a concept's interface. It discusses the classes and algorithms that are part of the basic STL, and it explains how you can write your own STL-compliant classes and algorithms and when you might want to do so. Finally, it includes a complete reference manual of all of the STL's concepts, classes, and algorithms. Everyone should read Part I, which introduces the main ideas of the STL and of generic programming. It shows how to use and write a generic algorithm, and it explains what it means for an algorithm to be generic. Genericity has implications that go far beyond the ability to operate on multiple data types. Exploring the idea of a generic algorithm leads naturally to the central ideas of concepts, modeling, and refinement, ideas that are as basic to generic programming as polymorphism and inheritance are to object-oriented programming. Generic algorithms on one-dimensional ranges, meanwhile, lead to the fundamental concepts of the STL: iterators, containers, and function objects. Part I introduces the notation and the typographical conventions that are used throughout the remainder of the book: the terminology of modeling and refinement, the asymmetrical notation for ranges, and the special typeface for concept names. The STL defines many concepts, some of which differ from each other only in technical details. Part I is an overview, and it discusses the broad outlines of STL concepts. Part II is a detailed reference manual that contains a precise definition of each STL concept. You may not wish to read Part II all the way through and, instead, may find it more useful to look up a particular concept only when you need to refer to its definition. (You should refer to Part Il whenever you write a new type that conforms to an STL concept.) Part III is also a reference manual. It documents the STL's predefined algorithms and classes. It relies heavily on the concept definitions of Part II. All STL algorithms and almost all concrete types are templates, and every template parameter can be characterized as the model of some concept. The definitions in Part III are cross-referenced to the appropriate sections of Part II. In an ideal world, the book would end with Part III Unfortunately, reality demands one more section, an appendix that discusses portability concerns. When the STL was first released, portability was not an issue because only one implementation existed. That is no longer the case, and whenever more than one implementation of any language or library exists, anyone who cares about portability must be aware of the differences between them. The old HP implementation is still available by anonymous FTP from butler. hpl.hp.com, but it is no longer being maintained. A newer free implementation, from Silicon Graphics Computer Systems (SGI) is available at http://www.sgi.com/ Technology/STL, and a port of the SGI STL to a variety of compilers, maintained by Boris Fomitchev, is available at http://www.metabyte.com/~fbp/stl. Finally, there are several different commercial STL implementations. If you are writing real programs, it isn't enough to understand the theoretical design of the library; you also have to understand how the various STL implementations and the various C++ compilers differ. These unglamorous but necessary details are the subject of Appendix A. Who Should Read This Book While this book is largely about algorithms written in C++, it is neither an introductory textbook on algorithms nor a C++ tutorial. It does explain some of the unfamiliar aspects of both subjects. In particular, since the STL uses templates in ways that are uncommon in other sorts of C++ programs, it discusses some advanced techniques of programming with templates. This should not be your first C++ book, nor should it be your first exposure to an analysis of algorithms. You should know how to write basic C++ programs, and you should know the meaning of notation like O(N). Two of the standard references on algorithms and data structures are Donald Knuth's The Art of Computer Programming [Knu97, Knu98a, Knu98b], and Introduction to Algorithms, by Cormen, Leiserson, and Rivest [CLR90]. Two of the best introductory C++ books are The C++ Programming Language, by Bjarne Stroustrup [Str97], and A C++ Primer, by Stanley Lippman and Josee Lajoie [LL98]. I joined the compiler group at Silicon Graphics Computer Systems (SGI) in 1996. Alex Stepanov had left HP to join SGI several months before. At the time, SGI's C++ compiler did not include an implementation of the Standard Template Library. Using the original HP implementation as our source base, Alex, Hans Boehm, and Iwrote the version of the STL that was shipped with release 7.1 (and subsequent releases) of SGI's MIPSpro compiler. The SGI Standard Template Library [Aus97] included many new and extended features, such as efficient and thread-safe memory allocation, hash tables, and algorithmic improvements. If these enhancements had remained proprietary, they would have been of no value to SGI's customers, so the SGI STL was made freely available to the public. It is distributed on the World Wide Web, along with its documentation, at http://www, sgi.com/Technology/STL. The documentation, a set of Web pages, treats the STL's conceptual structure as central. It describes the abstract concepts that comprise the structure, and it documents the STL's algorithms and data structures in terms of the abstract concepts. We received many requests for an expanded form of the documentation, and this book is a response to those requests. The reference sections of this book, Parts II and III, are an outgrowth of the SGI STL Web pages. The Web pages were written for and are copyrighted by SGI the kind permission of my management. Acknowledgments First and foremost, this book could not possibly have existed without the work of Alex Stepanov. Alex was involved with this book at every stage: he brought me to SGI, he taught me almost everything I know about generic programming, he participated in the development of the SGI STL and the SGI STL Web pages, and he encouraged me to turn the Web pages into a book. I am grateful to Alex for all of his help and encouragement. I also wish to thank Bjarne Stroustrup and Andy Koenig for helping me to understand C++ and Dave Musser for his numerous contributions (some of which can be found in the bibliography) to generic programming, to the STL, and to this book. Dave used an early version of the SGI STL Web pages as part Of his course material, and the Web pages were greatly improved through his and his students' comments. Similarly, this book was greatly improved through the comments of reviewers, including Tom Becker, Steve Clamage, Jay Gischer, Brian Kernighan, Jak Kirman, Andy Koenig, Angehka Langer, Dave Musser, SibyUe Schupp, and Alex Stepanov, who read early versions. This book is more focused than it would have been without them, and it contains far fewer errors. Any mistakes that remain are my own. Several mistakes in the first, second, and third printings of this book have now been corrected, and I wish to thank Sam Bradsher, Bruce Eckel, Guy Gascoigne, Ed James-Beckham, Jon Jagger, Nate Lewis, CH Lin, Shawn D. Pautz, John Potter, George Reilly, Manos Renieris, Peter Roth, Dieter Rothmeier, Andreas Scherer, and Jurgen Zeller, for bringing these errors to my attention. I am also indebted to the staff at Addison-Wesley, including John Fuller, Mike Hen-drickson, Marina Lang, and Genevieve Rajewski, for guiding me through the writing process, and to Karen Tongish for her careful copyediting. Finally, I am grateful to my fiancee, Janet Lafler, for her love and support and for her patience during the many evenings and weekends that I spent writing. Our cats, Randy and Oliver, tried to help by walking over my keyboard, but in the end I deleted most of their contributions.