Home > Store > Programming > C/C++
STL Tutorial and Reference Guide: C++ Programming with the Standard Template Library, 2nd Edition
 By David R. Musser, Gillmer J. Derge, Atul Saini
 Published Mar 27, 2001 by AddisonWesley Professional. Part of the AddisonWesley Professional Computing Series series.
Book
 This product currently is not for sale.
Features

NEW!
 Copyright 2001
 Dimensions: 73/8x91/4
 Pages: 560
 Edition: 2nd
 Book
 ISBN10: 0201379236
 ISBN13: 9780201379235
"The second edition is clearer and adds more examples on how to use STL in a practical environment. Moreover, it is more concerned with performance and tools for its measurement. Both changes are very welcome."
Lawrence Rauchwerger, Texas A&M University
"So many algorithms, so little time! The generic algorithms chapter with so many more examples than in the previous edition is delightful! The examples work cumulatively to give a sense of comfortable competence with the algorithms, containers, and iterators used."
Max A. Lebow, Software Engineer, Unisys Corporation
The STL Tutorial and Reference Guide is highly acclaimed as the most accessible, comprehensive, and practical introduction to the Standard Template Library (STL). Encompassing a set of C++ generic data structures and algorithms, STL provides reusable, interchangeable components adaptable to many different uses without sacrificing efficiency. Written by authors who have been instrumental in the creation and practical application of STL, STL Tutorial and Reference Guide, Second Edition includes a tutorial, a thorough description of each element of the library, numerous sample applications, and a comprehensive reference.
You will find indepth explanations of iterators, generic algorithms, containers, function objects, and much more. Several larger, nontrivial applications demonstrate how to put STL's power and flexibility to work. This book will also show you how to integrate STL with objectoriented programming techniques. In addition, the comprehensive and detailed STL reference guide will be a constant and convenient companion as you learn to work with the library.
This second edition is fully updated to reflect all of the changes made to STL for the final ANSI/ISO C++ language standard. It has been expanded with new chapters and appendices. Many new code examples throughout the book illustrate individual concepts and techniques, while larger sample programs demonstrate the use of the STL in realworld C++ software development. An accompanying Web site, including source code and examples referenced in the text, can be found at http://www.cs.rpi.edu/~musser/stlbook/index.html.
0201379236B05212001
Source Code
Click below for Source Code related to this title:
Source Code
Source Code
Table of Contents
Foreword.
Foreword to the First Edition.
Preface.
I. TUTORIAL INTRODUCTION TO STL.
II. PUTTING IT TOGETHER: EXAMPLE PROGRAMS.
III. STL REFERENCE GUIDE.
Preface
In the five years since the first edition of STL Tutorial and Reference Guide appeared, the C++ language standard has been finalized and officially accepted, C++ compiler vendors have made great progress in bringing their compilers into compliance with the standard, and dozens of other books and magazine articles have appeared that describe and explain the standardized language and libraries. Many of these books and articles have highlighted the Standard Template Library (STL) as the most significant addition to the standard. Some hailed it, as we did in this book's first edition, as having the potential to revolutionize the way a large number of people program. The past five years have already seen much of that potential realized, with the first edition of this book playing a key role for tens of thousands of programmers. We wrote in the preface of the first edition that there are five reasons why the STL components could become some of the most widely used software in existence:
 C++ is becoming one of the most widely used programming languages (in large part due to the support it provides for building and using component libraries).
 Since STL has been incorporated into the ANSI/ISO standard for C++ and its libraries, compiler vendors are making it part of their standard distributions.
 All components in STL are generic, meaning that they are adaptable (by languagesupported compiletime techniques) to many different uses.
 The generality of STL components has been achieved without sacrificing efficiency.
 The design of STL components as finegrained, interchangeable building blocks makes them a suitable basis for further development of components for specialized areas such as databases, user interfaces, and so forth.
Changes in the Second Edition
In this new edition we have added substantially more tutorial material including expanded chapters in Part I on function objects and container, it erator, and function adaptors, and two entirely new chapters in Part II containing substantial new examples. We have also gone through all example code and surrounding discussion, including the reference material in Part III, to bring them up to date with the final standard. (Although some ambiguities in the standard have been discovered since it was finalized, we believe that in most cases the remaining uncertainties about the meaning of STL component specifications have no important consequences for the practicing programmer. In the few cases where they might, we point them out.) We also added a new chapter in Part III describing utility components such as the pair and comparison classes, and a new appendix describing the STLrelated features of the standard string class.
In this edition we have also adopted the "literate programming" style for presenting example programs and code fragments. For readers unfamiliar with this approach to simultaneous programming and documenting, a brief explanation is given in Chapter 2 and more details are presented in Chapter 12. One benefit of the literate programming approach is that coding details can be presented once and then referred to (by name and page number) many times, so readers do not have to read through the same details repeatedly. Another major benefit is that we have been able check even more thoroughly than before that all code is syntactically and logically correct, since literate programming tools make it easy to extract the code directly from the manuscript and compile and test it. A list of the compilers the code has been compiled and tested with is given in Appendix D.
Some History, from the Preface to the First Edition
Virtually all C++ programmers know that this language was originated by one person, Bjarne Stroustrup, who began thinking of how to extend the C language to support definition of classes and objects as early as 1979. So too, the architecture of STL is largely the creation of one person, Alexander Stepanov.
It is interesting that it was also in 1979, at about the same time as Stroustrup's initial research, that Alex began working out his initial ideas of generic programming and exploring their potential for revolutionizing software development. Although Dave Musser had developed and advocated some aspects of generic programming as early as 1971, it was limited to a rather specialized area of software development (computer algebra). Alex recognized the full potential for generic programming and persuaded his thencolleagues at General Electric Research and Development (including, primarily, Dave Musser and Deepak Kapur) that generic programming should be pursued as a comprehensive basis for software development. But at that time there was no real support in any programming language for generic programming. The first major language to provide such support was Ada, with its generic units feature, and by 1987 Dave and Alex had developed and published an Ada library for list processing that embodied the results of much of their research on generic programming. However, Ada had not achieved much acceptance outside the defense industry, and C++ seemed more likely to become widely used and provide good support for generic programming, even though the language was relatively immature (it did not even have templates, added only later). Another reason for turning to C++, which Alex recognized early on, was that the C/C++ model of computation, which allows very flexible access to storage (via pointers), is crucial to achieving generality without losing efficiency.
Still, much research and experimentation were needed, not just to develop individual components, but more important to develop an overall ar chitecture for a component library based on generic programming. First at AT&T Bell Laboratories and later at HewlettPackard Research Labs, Alex experimented with many architectural and algorithm formulations, first in C and later in C++. Dave Musser collaborated in this research, and in 1992 Meng Lee joined Alex's project at HP and became a major contributor.
This work undoubtedly would have continued for some time as just a research project or at best would have resulted in an HP proprietary library, if Andrew Koenig of Bell Labs had not become aware of the work and asked Alex to present the main ideas at a November 1993 meeting of the ANSI/ISO committee for C++ standardization. The committee's response was overwhelmingly favorable and led to a request from Andy for a formal proposal in time for the March 1994 meeting. Despite the tremendous time pressure, Alex and Meng were able to produce a draft proposal that received preliminary approval at that meeting.
The committee had several requests for changes and extensions (some of them major), and a small group of committee members met with Alex and Meng to help work out the details. The requirements for the most significant extension (associative containers) had to be shown to be consistent by fully implementing them, a task Alex delegated to Dave Musser. It would have been quite easy for the whole enterprise to spin out of control at this point, but again Alex and Meng met the challenge and produced a proposal that received final approval at the July 1994 ANSI/ISO committee meeting. (Additional details of this history can be found in an interview Alex gave in the March 1995 issue of Dr. Dobb's Journal.)
Spreading the Word
Subsequently, the Stepanov and Lee document 17 was incorporated into the ANSI/ISO C++ draft standard (1, parts of clauses 17 through 27). It also influenced other parts of the C++ Standard Library, such as the string facilities, and some of the previously adopted standards in those areas were revised accordingly.
In spite of STL's success with the committee, there remained the question of how STL would make its way into actual availability and use. With the STL requirements part of the publicly available draft standard, compiler vendors and independent software library vendors could of course develop their own implementations and market them as separate products or as selling points for their other wares. One of the first edition's authors, Atul Saini, was among the first to recognize the commercial potential and began exploring it as a line of business for his company, Modena Software Incorporated, even before STL had been fully accepted by the committee.
The prospects for early widespread dissemination of STL were considerably improved with HewlettPackard's decision to make its implementation freely available on the Internet in August 1994. This implementation, developed by Stepanov, Lee, and Musser during the standardization process, became the basis of all implementations offered by compiler and library vendors today.
Also in 1994, Dave Musser and Atul Saini developed the STL++ Manual, the first comprehensive userlevel documentation of STL, but they soon recognized that an even more comprehensive treatment of STL was needed, one that would have better and more complete coverage of all aspects of the library. In an attempt to meet this goal, and with much encouragement and assistance from their editor, Mike Hendrickson, they wrote the first edition of this book.
In the second edition, the two original authors are joined by Gillmer J. Derge, President and CEO of the consulting firm Toltec Software Services, Inc. He has been developing applications with C++ for more than a decade, including seven years with General Electric Corporate R&D, where he received a Whitney Award for technical achievement.
Acknowledgments for the First Edition
We gratefully acknowledge the encouragement and assistance of many people. First and foremost, Alex Stepanov and Meng Lee offered continuous encouragement and were always available to help straighten out any misconceptions we had about the design of the library. Invaluable assistance with code development and testing was provided by several Modena staff members, including Atul Gupta, Kolachala Kalyan, and Narasimhan Rampalli. Several reviewers of earlier drafts gave us much valuable feedback and helped us find ways to present the most crucial ideas more clearly. They include Mike Ballantyne, Tom Cargill, Edgar Chrisostomo, Brian Kernighan, Scott Meyers, Larry Podmolik, Kathy Stark, Steve Vinoski, and John Vlissides. Others who also made valuable suggestions include Dan Benanav, Bob Cook, Bob Ingalls, Nathan Schimke, Kedar Tupil, and Rick Wilhelm. Finally, we thank the team at AddisonWesley for their expert editorial and production assistance: Kim Dawley, Katie Duffy, Rosa Gonzalez, Mike Hendrickson, Simone Payment, Avanda Peters, John Wait, and Pamela Yee.
Acknowledgments for the Second Edition
For assistance with this edition, we wish first of all to thank the review ers for pointing out errors in the discussion and examples and suggesting many other improvements in the presentation. The extensive comments of Max A. Lebow, Lawrence Rauchwerger, and Jan Christiaan van Winkel were especially helpful. We also thank Deborah Lafferty, our editor, and Julie DeBaggis, who served as editor during the early planning of the second edition. Several other members of the production and marketing teams at AddisonWesley helped in many ways, including Jacquelyn Doucette, Chanda Leary Coutu, Curt Johnson, Jennifer Lawinski, and Marty Rabinowitz.
D.R.M.
Loudonville, NY
G.J.D.
Cohoes, NY
A.S.
Los Gatos, CA
October 2000
0201379236P04062001
Index
 Abstract data types, 127
 Abstractions, family of, 127128
 Accessor(s)
 container, 144145
 lists and, 160
 maps/multimaps and, 181
 sorted associative containers and, 170173
 deque and, 151
 accumulate algorithm, 3342, 122123, 184187, 427
 Actual types, 8
 Adaptability, 5
 Adaptor(s)
 basic description of, 4043
 pointertofunction, 43
 priority_queue, 43
 queue, 43
 reference guide, 431440
 stack, 43
 adjacent_difference algorithm, 124125, 430
 adjacent_find algorithm, 77, 7880, 231, 248, 389, 392393
 allocate function, 451
 Allocator(s)
 basic description of, 3, 4344
 class, 441454
 common member functions in all, 443445
 constructors, 446
 custom, 448454
 destructors, 446
 objects, 320
 reference guide, 441454
 passing, to STL containers, 441442
 requirements, 442445
 Allocator template parameter, 14, 150, 154, 332, 340, 360, 374
 Amortized
 constant time, 1718
 time complexity, 1718
 Anagram groups. Anagrams
 copying, to output streams, 232
 finding, 225233
 outputting, in order of size, 237238, 249
 Anagrams. See also Anagram groups
 multimaps and, 243250
 searching for, 215217, 225342
 ANSI/ISO C++ Committee, 4
 ANSI/ISO C++ Standard, 484
 arithmetic operations, 433
 Arrays
 copying versions of algorithms and, 7475
 demonstrating the find algorithm with, 2630
 demonstrating the merge algorithm with, 3132
 find algorithm and, 66
 input iterators and, 5152
 lists and, 153
 maps and, 174175
 output iterators and, 5354
 rearranging elements of, 76
 ASCII (American Standard Code for Information Interchange), 267, 273
 assert macro, 21
 assign function, 146147, 152, 160, 174
 Associative containers, 2426, 320321
 Automatic expansion, 240241

B
 back function, 140143, 193, 196
 back_inserter template, 6061, 63
 back_inserter function, 314
 back insert iterators, 6061, 313315
 basic_string class, 462472
 begin function, 2021, 24, 28, 34, 6970, 165, 220
 Bidirectional iterator(s), 36, 49, 5557. See also Iterators
 classification of, 58
 requirements, 299300
 as more powerful, 67
 random access iterators and, 56
 reverse algorithm and, 96
 sequence containers and, 137138
 BigOh notation, 1518, 287, 292, 389
 binary_function, 39, 187
 binary predicate parameters, 7576
 binary_search algorithm, 68, 112114
 basic description of, 410, 415417
 random access iterators and, 5657
 searching dictionaries and, 218, 221, 228
 Binders, 43, 205206, 435436. See also Function adaptors
 Boolean values, 7, 21, 166
 Borland C++, 484
 Briggs's nuweb tool, 217

C
 C++ (highlevel language)
 compilers, STLcompatible, 484
 literate programming and, 223
 libraries, STL and difference between, 4548
 partial specialization and, 147
 templates, generic programming and, relationship of, 714
 Standard Library, 4
 C++ Programming Language, The (Stroustrup), 260, 261
 char* data type, 28
 char_traits class, 472476
 char_type, 474475
 Character
 manipulation functions, 473476
 traits, 472476
 Class(es). See also Classes (listed by name); Container adaptors
 declarations, 330, 332
 descriptions, organization of, 330331
 I/O stream, interacting with, 218220
 Classes (listed by name). See also Classes
 allocator class, 441454
 basic_string class, 462472
 calc_square<int> class, 91
 char_traits class, 472476
 earlier class, 275
 greater class, 76
 istream_iterator class, 72, 304307
 iterator_category class, 303304
 iterator_traits class, 254, 301303
 line class, 260
 list<char> class, 13
 list class, 56
 map class, 162
 multimap class, 162
 multiply class, 39
 multiset class, 162174
 ostream_iterator class, 54, 72, 289, 298, 304309
 PriorityQueueAsList class, 194
 PriorityQueueAsVector class, 194
 QueueAsDoubleList class, 194
 QueueAsList class, 194
 QueueAsVector class, 194
 rectangle class, 260261
 reverse_iterator class, 203, 310311
 set class, 162174
 shape class, 260
 StackAsList class, 194
 string class, 2122, 26, 103, 218220, 461472
 timer class, 284292
 vector<char> class, 1214
 vector class, 12, 28, 30, 331339
 clock function, 279280, 282283
 CLOCKS_PER_SEC constant, 280
 clock_t, 280
 "Code bloat" problem, 14, 208, 259, 265266
 Comments, 274
 Compare(), 164
 Comparison
 functions, 455457
 objects, sorting word pairs with, 230
 operations, 58, 433434, 455457
 Compatibility
 algorithm/container, 48, 68
 plug, 6
 Compilers, STLcompatible, 484
 Components
 categories of, 34
 interchangeability of, 4648
 overview of, 1844
 const_iterator, 6972, 130, 145
 const_pointer, 130
 const_reference, 130, 145
 const_reverse_iterator, 201
 Constant iterators
 basic description of, 296
 versus mutable iterators, 6870
 Constant reference parameters, 9
 Constant time, 16, 56, 147, 167, 296
 Constructor(s)
 allocator, 446
 basic description of, 319, 324325
 class descriptions and, 331
 constructing sequences with, 130135
 deque, 340341
 function objects and, 190
 iterators and, 306309, 311, 314316
 lists and, 154, 347348
 map, 176, 368
 multimap, 176, 374
 priority_queue, 384
 queue, 382
 sequence containers and, 130135, 150, 154
 set, 154, 356
 sorted associative containers and, 164, 176
 stacks and, 379
 string, 463466
 utilities and, 457
 vector, 334335
 Container(s)
 accesssors, 144145
 adaptors, 193200, 319
 allocators and, 4344
 associative, 2426, 320321
 basic description of, 1926
 in C++ libraries other than STL, 4548
 class descriptions, 330339
 classes, generic, 9
 combining, with algorithms, 5859
 common type definitions in all, 320321
 common member functions in all, 322323
 common members in all, 320323
 compatibility of, with algorithms, 48, 68
 connecting, with iterators, 4, 5
 converting strings to, 13
 design and organization of, 319320
 equality, 145146
 important characteristics of, 319320
 instances, "code bloat" from, 265266
 iterator categories and, 58, 59, 7172
 lessthan relations and, 145146
 passing allocators to, 441442
 reference guide, 319386
 reversible, 324
 sequence, 1924
 sorted, 2426
 sorted associative, 127
 Container template parameter, 13
 Converse relation, 105
 copy algorithm, 5354, 8789, 289
 basic description of, 398, 399400
 iterators and, 204, 297
 searching dictionaries and, 218, 249
 copy_backward algorithm, 8789
 copy constructor, 134, 190
 defining iterator classes and, 253, 254255
 insert iterators and, 60, 61
 copying versions, of algorithms, 7475
 count algorithm, 77, 8081, 172173, 389, 393394
 count_if algorithm, 8081
 counting iterators, 251258
 ctime header, 280
 Custom allocators, 448454. See also Allocators
 CWeb, 223

D
 Data abstraction, 127
 Database(s)
 associating students with advisors in, 268270
 sorting student data in, 267268
 trees, finding the roots of, 270273
 data_map, 268, 275
 Data structures
 defining, 226227
 holding iterator pairs, 234235
 deallocate function, 451, 454
 default allocators, 445448
 Default template parameters, 14
 Deferenceable value, use of the term, 295
 Deletions, See also Erasure
 container adaptors and, 193
 lists and, 152153
 stacks and, 378
 deque
 basic description of, 29, 148152, 339345
 common members of, 320321
 constructors, 151, 340341
 destructors, 340341
 container adaptors and, 193, 194197
 demonstrating the find algorithm with, 2930
 demonstrating the merge algorithm with, 3132
 destructors, 340341
 erasure and, 142, 344, 345354
 find algorithm and, 66
 insert functions, 343345, 350
 iterators, 61, 62, 59, 150
 lists and, 153, 154
 deque container, 127, 359
 Destructor(s)
 allocator, 446
 basic description of, 319
 class descriptions and, 331
 deque, 340341
 list, 347348
 map, 368
 multimap, 374
 set, 356
 string, 463466
 vector, 334335
 Dictionaries
 finding anagram groups in, 225233
 finding anagrams for a given word in, 215217
 permutations for membership in, testing, 220221
 programs for searching, 215223
 reading, into multimaps, 247249
 reading, into vectors of PS objects, 229230
 Difference types, 130, 295
 Directory blocks, reallocation of, 150
 Discussion lists, 484
 distance function, 249
 draw function, 261

E
 earlier class, 275
 earlier relation, 269
 Efficiency, 5
 Emptiness, testing for, 379
 empty function, 193194, 196, 198200
 Encapsulation, 4344, 320
 end function, 2021, 24, 28
 accumulate function and, 34
 searching dictionaries and, 220
 sorted associative containers and, 165
 End markers, 72
 Equality
 deque and, 152
 equal algorithm and, 77, 8285, 389, 395396
 equal_range algorithm and, 112, 172, 410
 iterators and, 313
 lessthan relations and, 14546
 lists and, 160
 maps/multimaps and, 181182
 predicate objects, 230231
 sorted associative containers and, 173
 erase function, 320, 325326, 329, 331
 deque and, 344, 345354
 iterators and, 70, 7172
 lists and, 155156, 351, 354
 maps and, 371372
 multimaps and, 378
 multisets and, 364
 sequence containers and, 142143, 151, 155156
 set and, 359360
 sorted associative containers and, 168170
 strings and, 471
 vectors and, 338339
 Erasure. See also Deletion
 with the pop_back function, 140143
 lists and, 155156
 maps/multimaps and, 181
 with the pop_back function, 140143
 sequence containers and, 140143, 151, 155156
 sorted associative containers and, 168170
 Extensibility, 46

F
 FIFO (firstin, firstout), 196
 fill algorithm, 8990, 398, 403
 fill_n algorithm, 8990
 find algorithm, 2630, 36, 40, 45, 7778, 389, 391
 advantages of, 112
 compatibility of, with containers, 48, 68
 component interchangeability and, 4748
 defining iterator classes and, 257
 definition of, 6566
 iterators and, 5052, 59, 6465, 202203
 predicate version of, 77
 sorted associative containers and, 168171
 find_end algorithm, 390, 397398
 find_first algorithm, 391392
 find_first_of algorithm, 389
 find_if algorithm, 77, 205, 231, 232, 248
 first iterator, 2122, 28, 33, 4950, 57
 function objects and, 184
 sequence containers and, 137138
 firstEqual function object, 227228, 231, 248
 firstLess function object, 227228, 230
 for_each algorithm, 77, 8182, 389391
 Forward iterators, 36, 49, 5455
 classification of, 58
 random access iterators and, 56
 requirements, 299
 sequence containers and, 137138
 forward_counting_iterator, 257
 forward_iterator_tag, 254
 ForwardIterator template parameter, 5455, 253
 front function, 196, 198
 front_inserter function, 61
 front insert iterators, 6061, 315316
 Function(s). See also Function adaptors; Function objects; Functions (listed by name)
 parameters, 7577
 pointers to, function adaptors for, 205, 208211, 436439
 templates, 7, 1011
 virtual, 260265
 Function adaptors, 205211, 432
 binders, 43, 205206, 435436
 categories of, 205
 negators, 43, 205, 206208, 435
 for pointers to functions, 205, 208211, 436439
 using, to obtain predicate objects, 231232
 Function object(s)
 basic description of, 3640, 183191
 creating, for comparisons, 227228
 reference guide, 431440
 operator overloading and, 38
 specifying, with template parameters, 186191
 STLprovided, 191
 Functions (listed by name). See also erase function; insert function
 accumulate function, 3342, 184187
 allocate function, 451
 assign function, 146147, 152, 160, 174
 back function, 140143, 193, 196
 back_inserter function, 314
 begin function, 2021, 24, 28, 34, 6970, 165, 220
 capacity function, 138140, 151, 160
 clock function, 279280, 282283
 deallocate function, 451, 454
 distance function, 249
 draw function, 261
 empty function, 193194, 196, 198200
 end function, 2021, 24, 28, 34, 165, 220
 front function, 196, 198
 front_inserter function, 61
 inserter function, 62, 314
 key_compare function, 162163, 173, 175, 182, 355
 key_type function, 162, 175
 lexicographical_compare function, 146
 make function, 1314, 23
 memcpy function, 474
 memmove function, 474
 memset function, 474
 move function, 261
 mult function, 38
 my_algorithm function, 304
 my_algorithm_impl function, 304
 pop_back function, 140143, 193194, 198
 pop_front function, 61, 142, 151, 196197
 pop function, 194, 199
 print_list function, 82
 push_back function, 60, 61, 135140, 148149, 153154, 193198
 push_front function, 60, 61, 127, 148149, 151, 153154
 push function, 194
 rbegin function, 201
 remove function, 160
 rend function, 4243, 201
 report function, 252
 reserve function, 138140, 149151, 155
 reverse function, 136138
 size function, 146, 193, 194, 196, 198200
 sort function, 48
 splice function, 156
 strchr function, 474
 strcmp function, 473
 strlen function, 474
 swap function, 147, 152, 160, 182
 time function, 283284
 top function, 194, 199
 unique function, 158159
 vector function, 23, 261
 Function templates
 basic description of, 7, 1011
 member, 12
 functional header, 76

G
 Genealogy program, 267278
 Generalized numeric algorithms, 426427
 generate algorithm, 9091, 398, 404
 Generic. See also Generic algorithms
 container classes, 9
 programming, basic description of, 47
 Generic algorithms. See also Generic algorithms (listed by name)
 basic description of, 3, 56, 2632, 73126
 C++ templates and, relation of, 714
 choosing the right, 6870
 combining, with containers, 5859
 compatibility of, with containers, 48, 68
 component interchangeability and, 47
 copying versions of, 7475
 definition of, with function templates, 1011
 demonstrating, with arrays, 2627
 descriptions, organization of, 387389
 designing, 6566
 function parameters and, 7577
 inplace versions of, 7475
 iterator categories and, 5859, 6465
 organization of, in STL, 7377
 partial specialization and, 14
 reference guide, 387430
 which require more powerful iterators, 67
 sequence types and, 20
 singlepass, 66
 timing, class for, 279317
 Generic algorithms (listed by name). See also find algorithm; merge algorithm;
 sort algorithm
 accumulate algorithm, 122123, 427
 adjacent_difference algorithm, 124125, 430
 adjacent_find algorithm, 77, 7880, 231, 248, 389, 392393
 binary_search algorithm, 5657, 68, 112114, 218, 221, 228, 410, 415417
 copy algorithm, 5354, 8789, 204, 218, 249, 289, 297, 398, 399400
 copy_backward algorithm, 8789
 count algorithm, 77, 8081, 172173, 389, 393394
 fill algorithm, 8990, 398, 403
 fill_n algorithm, 8990
 find_end algorithm, 390, 397398
 find_first algorithm, 391392
 find_first_of algorithm, 389
 find_if algorithm, 77, 205, 231, 232, 248
 generate algorithm, 9091, 398, 404
 includes algorithm, 115, 410, 418421
 inner_product algorithm, 125126, 177178, 427
 inplace_merge algorithm, 114
 introselect algorithm, 112
 lexicographical_compare algorithm, 120121, 173
 lower_bound algorithm, 112114, 170172, 410
 make_heap algorithm, 117119, 410, 421423
 max algorithm, 11, 119120, 410, 423424
 max_element algorithm, 119120, 410, 423424
 min algorithm, 119120, 410, 423424
 min_element algorithm, 119120, 410, 423424
 mismatch algorithm, 77, 8285, 389, 394395
 next_permutation algorithm, 121122, 221, 425426
 nth_element algorithm, 110112, 410, 414415
 partial_sort algorithm, 106110, 292, 410, 412414
 partial_sum algorithm, 123125, 429
 partition algorithm, 9193, 399, 409410
 pop_heap algorithm, 117119, 410, 421423
 prev_permutation algorithm, 121122, 425426
 push_heap algorithm, 117119, 410, 421423
 random_shuffle algorithm, 76, 9394, 346, 399, 408409
 remove algorithm, 9495, 351353, 398, 404405
 remove_if algorithm, 351353
 replace algorithm, 5455, 9596, 398, 402403
 replace_copy algorithm, 75
 reserve algorithm, 469
 reverse_copy algorithm, 7475
 rotate algorithm, 9697, 399, 408
 search algorithm, 65, 77, 9697, 389, 396
 search_n algorithm, 390, 397
 set_difference algorithm, 115117, 410, 418421
 set_intersection algorithm, 115117, 410, 418421
 set_symmetric difference algorithm, 115117, 410, 418421
 set_union algorithm, 115117, 410, 418421
 sort_heap algorithm, 117119, 410, 421423
 splice algorithm, 351353
 stable_partition algorithm, 9193
 stable_sort algorithm, 106110, 291, 410, 412414
 swap algorithm, 9798, 147, 174, 398, 400401
 swap_ranges algorithm, 9899
 transform algorithm, 99100, 398, 401402
 unique algorithm, 87, 100102, 351353, 398, 406407
 Global operations, 313
 greater class, 76
 greater function object type, 103
 greater<string>() binary predicate, 80
 greater<T>(), 105
 GreaterThan50 object type, 78

H
 Hashed associative containers, 161162
 Header files, 260, 289, 359, 477, 479, 481
 Heap operations, 117119, 421423
 heapsort, 106
 Homogenous storage, 259

I
 ifstream constructor, 220
 Inplace versions, of algorithms, 7475
 Include files, 477482
 includes algorithm, 115, 410, 418421
 Inheritance, 260265
 inner_product algorithm, 125126, 177178, 427
 inplace_merge algorithm, 114
 Input iterator(s), 35, 49
 basic description of, 5052
 classification of, 58
 find algorithm and, 65
 random access iterators and, 56
 requirements, 296298
 InputIterator, 12, 50, 187
 inserter function, 62, 314
 inserter template, 62
 insert function, 12, 60, 62, 7072, 324331
 deque and, 343345, 350
 lists and, 354
 maps and, 371
 multimaps and, 376377
 multisets and, 363364
 sequence containers and, 128, 135140, 143, 151
 set and, 358359
 sorted associative containers and, 164167
 strings and, 470471
 vectors and, 338, 339
 Insert iterators, 5962, 316317
 Insertion, 193, 320. See also insert function; Insert iterator
 lists and, 152155, 354
 maps/multimaps and, 176181, 376377
 sorted associative containers and, 164167
 stacks and, 379
 insert mode, 59
 Instantiation, 8, 1315
 Interchangeability, of components, 4648
 International Standard for C++, 4
 introselect algorithm, 112
 introsort algorithm, 107
 I/O stream classes, interacting with, 218220
 iostreams, 5152, 218220
 istream_iterator class, 6, 6365, 72, 304307
 istream iterators, 6, 52, 6365, 72, 218, 304307
 Iterator(s). See also specific types
 accumulate algorithm with, 4142
 adaptors, 201204
 basic description of, 3, 5, 28, 3336, 4972
 categories, 35, 6465, 7172
 classes, 72, 251258, 302307
 containers and, 21
 deque, 150
 find algorithm and, 28
 hierarchy of, 5859
 input, 35
 operations, 304
 output, 35
 pairs, data structure holding, 235236
 range of, 4950
 random access, 36
 reference guide, 295318
 requirement of more powerful, for specific algorithms, 67
 sequence containers and, 129, 140, 143, 150
 subtraction of, 5758
 tags, standard, 303304
 terminology for, 295296
 traits, 301304
 iterator_category class, 303304
 iterator_traits class, 254, 301303
 iterator_type, 137138

K
 Kernighan, Brian, 268, 270
 key_compare function, 162163, 173, 175, 182, 355
 keys
 basic description of, 161
 equivalence, notion of, 163
 types of, 162163
 key_type type, 162, 175
 Knuth, D. E., 23, 223

L
 LastNameLess(), 104
 less function object type, 103
 less<int>(), 103
 Lessthan relations, 145146, 152, 181182
 lists and, 160
 sorted associative containers and, 173, 181182
 Levy, S., 223
 lexicographical order, 221
 lexicographical_compare algorithm, 120121, 146, 173
 LIFO (lastin, firstout), 196
 line class, 260
 Linear time, 16, 20, 142
 List(s)
 basic description of, 152160
 common members of, 320321
 constructors, 347348
 demonstrating the find algorithm with, 2829
 destructors, 347348
 erasure and, 142, 354
 input iterators and, 5152
 insert functions and, 354
 insert iterators and, 61
 iterator categories and, 59
 nonmutating sequence algorithms and, 84
 parameters for, 154
 random access iterators and, 57
 special operations for, 351352
 storing information in a map of, 236237
 stream iterators and, 63
 list<char> class, 13, 2324
 list class, 56
 list container, 127, 193, 194197
 demonstrating the merge algorithm with, 3132
 header files and, 359
 searching dictionaries and, 235242
 List iterators, 66, 67
 List sequence abstraction, 152160
 Literate programming style, 23, 217, 218, 220, 223
 Logarithmic time, 16, 112113
 Logical operations, 434435
 lower_bound algorithm, 112114, 170172, 410

M
 make function, 1314, 23
 make_heap algorithm, 117119, 410, 421423
 Map(s), 2526, 365373
 basic description of, 174182
 common members of, 320321
 constructors, 176, 368
 demonstrating, 2526
 destructors, 368
 insertion into, 176181
 iterators and, 7172
 special operations for, 372373
 map class, 162
 map container, 127128, 235242, 326330, 359
 map<Key, T> container, 25
 map<Key, T> object, 7172
 map<string, long> container, 25
 max algorithm, 11, 119120, 410, 423424
 max_element algorithm, 119120, 410, 423424
 Maximum time, 15
 Member function templates, 11
 memcpy function, 474
 memmove function, 474
 Memory, 283, 453. See also Allocators
 constraints, adaptation to, 107
 models, 320321
 memset function, 474
 merge algorithm, 6, 3032, 36, 114115, 410
 basic description of, 351353, 417418
 compatibility of, with containers, 48
 component interchangeability and, 47
 iterators and, 59, 6264
 lists and, 159
 microprocessors, 280, 283
 min algorithm, 119120, 410, 423424
 min_element algorithm, 119120, 410, 423424
 mismatch algorithm, 77, 8285, 389, 394395
 move function, 261
 mult function, 38
 multfunobj operator, 187
 multfun operator, 185186
 Multimap(s), 365, 374378
 basic description of, 174182
 common members of, 320321
 constructors for, 176, 374
 declarations, 246147
 finding anagram groups in, 247249
 insertion into, 176181
 iterators and, 7172
 searching dictionaries and, 243250
 special operations for, 377378
 multimap class, 162
 multimap container, 127128, 326330, 359
 multimap<Key, T> container, 25
 multiply class, 39
 Multiset(s), 170173, 360365
 common members of, 320321
 constructors, 361362
 destructors, 361362, 374
 erasing elements from, 168170
 special operations for, 365
 multiset class, 162174
 multiset container, 127128, 279, 326330
 multiset<Key> container, 25
 Mutable iterators, 6870, 296
 Mutating sequence algorithms, 87102, 398399. See also reverse algorithm
 copy_backward algorithm, 8789
 fill algorithm, 8990, 398, 403
 fill_n algorithm, 8990
 generate algorithm, 9091, 398, 404
 partition algorithm, 9193, 399, 409410
 random_shuffle algorithm, 76, 9394, 346, 399, 408409
 remove algorithm, 9495, 351353, 398, 404405
 replace algorithm, 5455, 9596, 398, 402403
 rotate algorithm, 9697, 399, 408
 swap algorithm, 9798, 147, 174, 398, 400401
 swap_ranges algorithm, 9899
 stable_partition algorithm, 9193
 transform algorithm, 99100, 398, 401402
 unique algorithm, 87, 100102, 351353, 398, 406407
 my_algorithm function, 304
 my_algorithm_impl function, 304

N
 negators, 43, 205, 206208, 435
 next_permutation algorithm, 121122, 221, 425426
 Nondecreasing (ascending) order, 105106
 nonincreasing (descending) order, 105106
 Nonmutating sequence algorithms, 7787, 389390. See also find algorithm
 adjacent_find algorithm, 77, 7880, 231, 248, 389, 392393
 count algorithm, 77, 8081, 172173, 389, 393394
 equal algorithm, 77, 8285, 389, 395396
 for_each algorithm, 77, 8182, 389391
 mismatch algorithm, 77, 8285, 389, 394395
 search algorithm, 65, 77, 9697, 389, 396
 not_equal_to, 81
 nth_element algorithm, 110112, 410, 414415
 Numeric algorithms, 122126
 nuweb, 217

O
 Objectoriented programming, combining STL with, 259266
 Open and orthogonal structure, 46
 Operation counting, 186191
 Operators
 = operator, 53, 65, 35, 13233, 255
 + operator, 29, 3637, 125
 ++ operator, 29, 33, 35, 49, 51, 53, 6566, 70, 255256, 296
 * operator, 33, 35, 125, 51, 6566, 173, 207, 298
 < operator, 30, 77, 102103
  operator, 146147, 152, 160, 182
 == operator, 53, 104, 132133, 145146, 163, 173174, 255
 => operator, 102103
 > operator, 102103, 105
 >= operator, 207
 [] operator, 177, 179, 181
 overloading, 38
 ordering predicates, 313
 ostream iterators, 5354, 72, 289, 298, 304309
 ostream_iterator class, 6, 54, 63, 72, 289, 298, 304309
 ostream_iterator constructor, 54
 output iterator(s), 35, 49, 5254
 classification of, 58
 random access iterators and, 56
 requirements, 298
 overwrite mode, 59

P
 pair, 89, 11, 227, 235, 456
 pair<const Key, T>, 7172
 Partial specialization, 14, 147
 partial_sort algorithm, 106110, 292, 410, 412414
 partial_sum algorithm, 123125, 429
 partition algorithm, 9193, 399, 409410
 Partitioning strategy, 107
 partitions, 9193, 107, 399, 409410
 Pascal, 223
 Pasttheendvalues, use of the term, 295
 Permutation(s)
 algorithms, 121122
 generating, 220221, 425426
 Pointer(s). See also Function adaptors
 forward iterators and, 5455
 random access iterators and, 57
 sequence containers and, 129
 using, as output iterators, 53
 pop_back function, 140143, 193194, 198
 pop_front function, 61, 142, 151, 196197
 pop function, 194, 199
 pop_heap algorithm, 117119, 410, 421423
 position iterator, 12
 PPS iterator pair, 235237
 Predicates, 75, 91, 231232
 prev_permutation algorithm, 121122, 425426
 print_list function, 82
 Printing, database information, 275276
 Priority queue, 43, 194, 198200, 384385
 PriorityQueueAsList class, 194
 PriorityQueueAsVector class, 194
 priority_queue container adaptor, 198200, 384385
 Processors, 280, 283
 ptr_fun, 209210
 Public member functions, 307, 309, 311312, 314317
 push_back function, 60, 61, 135140, 148149, 153154, 193198
 push_front function, 60, 61, 127, 148149, 151, 153154
 push function, 194
 push_heap algorithm, 117119, 410, 421423

Q
 Quadratic time, 16, 142
 queue
 adaptor, 43, 198199, 380383
 constructors, 382
 priority, 43, 194, 198200, 384385
 QueueAsDoubleList class, 194
 QueueAsList class, 194
 QueueAsVector class, 194
 quicksort, 107

R
 Random access
 iterators, 36, 49, 5658, 300301
 as more powerful, 67
 sequence containers and, 137
 random_shuffle algorithm, 76, 9394, 346, 399, 408409
 Ranges, use of the term, 296
 rbegin function, 201
 Reachability, use of the term, 296
 Reallocation, 140, 150
 rectangle class, 260261
 relation_map, 270275
 remove algorithm, 9495, 351353, 398, 404405
 remove function, 160
 remove_if algorithm, 351353
 rend function, 4243, 201
 replace algorithm, 5455, 9596, 398, 402403
 replace_copy algorithm, 75
 report function, 252
 report method, 287288
 reserve algorithm, 469
 reserve function, 138140, 149151, 155
 results method, 284, 287
 Reusable components, 4
 reverse algorithm, 2024, 96, 159, 351353
 basic description of, 399, 407
 bidirectional iterators and, 5556
 sequence containers and, 149, 152, 154
 reverse_copy algorithm, 7475
 reverse function, 136138
 Reverse iterators, 40, 4243, 130, 201, 203, 309313, 336, 342, 349
 reverse_iterator adaptor, 201
 reverse_iterator class, 203, 310311
 reverse_iterator component, 40, 4243, 130
 rotate algorithm, 9697, 399, 408

S
 search algorithm, 65, 77, 9697, 389, 396
 screen.cpp, 477478, 260
 screen.h, 260, 477, 479, 481
 screen manager, 260
 search_n algorithm, 390, 397
 Sequence algorithms, 87102, 398399. See also reverse algorithm
 copy_backward algorithm, 8789
 fill algorithm, 8990, 398, 403
 fill_n algorithm, 8990
 generate algorithm, 9091, 398, 404
 partition algorithm, 9193, 399, 409410
 random_shuffle algorithm, 76, 9394, 346, 399, 408409
 remove algorithm, 9495, 351353, 398, 404405
 replace algorithm, 5455, 9596, 398, 402403
 rotate algorithm, 9697, 399, 408
 swap algorithm, 9798, 147, 174, 398, 400401
 swap_ranges algorithm, 9899
 stable_partition algorithm, 9193
 transform algorithm, 99100, 398, 401402
 unique algorithm, 87, 100102, 351353, 398, 406407
 Sequence container(s), 1924, 146147
 basic description of, 127160, 319
 deque container, 127, 359
 common members of, 320321
 constructing sequences with, 130135
 list container, 3132, 127, 193, 194197, 235242, 359
 requirements, 324325
 vector container, 127148, 193, 194197, 218, 237238, 240241, 244, 359
 Set(s)
 accessors and, 170173
 basic description of, 354360
 common members of, 320321
 constructors, 356
 destructors, 356
 erasing elements from, 168170
 insert functions and, 358359
 operations, 115117
 set class, 162174
 set container, 127128, 326330
 set_difference algorithm, 115117, 410, 418421
 set_intersection algorithm, 115117, 410, 418421
 set<Key> container, 2425
 set_symmetric_difference algorithm, 115117, 410, 418421
 set_union algorithm, 115117, 410, 418421
 SGI Web site, 483
 shape class, 260
 shape.h, 479, 260
 shape libraries, 260
 shape.cpp, 260
 SIGACT Theoretical Computer Science Genealogy page, 267278
 singlepass algorithms, 297
 singular values, use of the term, 296
 size dependence, 241
 size function, 146, 193, 194, 196, 198200
 sort algorithm, 67, 106110, 158159, 281282, 346, 351353
 basic description of, 410, 412414
 compatibility of, with containers, 48
 component interchangeability and, 4748
 inplace version of, 74
 iterator categories and, 59
 objectoriented programming and, 265
 timing, 289292
 used with a binary predicate, 7677
 sorted associative containers, 161182, 319, 326330
 sorted structures, set operation on, 115117
 sort function, 48
 sort_heap algorithm, 117119, 410, 421423
 sorting
 searching dictionaries and, 230, 244
 students by date, 267268
 word pairs, with comparison objects, 230
 Sortingrelated algorithms
 basic description of, 102122, 410412
 comparison relations and, 102105
 stability property of, 104105, 106
 Sortingrelated member functions, 158159
 sort iterator, 36
 splice algorithm, 351353
 splice function, 156
 Splicing, 152, 156158, 351353
 stable_partition algorithm, 9193
 stable_sort algorithm, 106110, 291, 410, 412414
 Stack(s)
 adaptors, 43, 194196, 378380, 459
 basic description of, 193
 constructors, 380
 defining, as classes, 194
 empty, testing for, 193
 StackAsList class, 194
 StackAsVector, 194
 start_baseline method, 285
 start method, 286
 Static variables, 189
 STL (Standard Template Library)
 basic description of, 318
 combining, with objectoriented programming, 259266
 compatible compilers, 484
 defining a data structure to work with, 226227
 extensibility and, 46
 open and orthogonal structure of, 46
 organization of algorithms in, 7377
 other C++ libraries and, difference between, 4548
 performance guarantees, 1518
 userlevel descripton of, 4
 strchr function, 474
 strcmp function, 473
 stream iterators, 6263
 stream_input iterator, 218
 Strict weak ordering, 104
 String(s). See also string class
 constructors, 463466
 destructors, 463466
 objects, 2021
 reference guide, 461475
 string class, 2122, 26, 103, 218220, 461472
 strlen function, 474
 Stroustrup, Bjarne, 260
 Subtraction, 57
 swap algorithm, 9798, 147, 174, 398, 400401
 swap function, 147, 152, 160, 182
 swap_ranges algorithm, 9899

T
 Template(s), 610, 15, 266. See also Template parameters
 arguments, explict specification of, 1214
 function, basic description of, 7, 1011
 insert iterators and, 6061
 partial specialization and, 147
 template keyword, 9
 Template parameters, 14, 64
 maps/multimaps and, 175176
 sequence containers and, 150
 specifying function objects with, 186191
 Time. See also Time complexity
 bound, 16
 constant, 16, 56, 147, 167, 296
 linear, 16, 20, 142
 logarithmic, 16, 112113
 maximum, 15
 quadratic, 16, 142
 worstcase, 1518
 Time complexity, 78, 80, 8687, 389
 accumlate algorithm and, 427
 adjacent_difference algorithm and, 430
 adjacent_find algorithm and, 393
 binary_search algorithm and, 417
 copy algorithm and, 400
 equal algorithm and, 395
 fill algorithm and, 403
 find algorithm and, 391
 find_end algorithm and, 398
 find_first algorithm and, 392
 for_each algorithm and, 391
 generate algorithm and, 404
 heap operations and, 422
 inner_product algorithm and, 427
 max algorithm and, 424425
 merge algorithm and, 418
 min algorithm and, 424425
 mismatch algorithm and, 395
 mutating sequence algorithm and, 96, 97, 99, 100
 nth_element algorithm and, 415
 partial_sum algorithm and, 429
 partition algorithm and, 410
 random_shuffle algorithm and, 409
 reverse algorithm and, 407
 remove algorithm and, 405
 replace algorithm and, 403
 rotate algorithm and, 408
 search algorithm and, 396
 search_n algorithm and, 397
 set operations and, 421
 sort algorithm and, 414
 swap algorithm and, 401
 transform algorithm and, 402
 unique algorithm and, 407
 time function, 283284
 timer class, 284292
 timer.h, 289
 Timing
 accurate, obstacles to, 279280
 algorithms, 279317
 top function, 194, 199
 T parameter, 150, 154
 transform algorithm, 99100, 398, 401402
 trichotomy law, 102103
 tuples, 177180
 Type parameters, 8

U
 unique algorithm, 87, 100102, 351353, 398, 406407
 unique function, 158159
 Unix, 280
 upper_bound algorithm, 112114, 170172, 410
 Upper bounds, 1517, 112114, 170172, 410
 utilities
 comparison functions and, 455457
 reference guide for, 455457

V
 Value(s)
 retrieving, container adaptors and, 193
 types, use of the term, 295
 value_compare, 163, 175
 value_type, 129, 164, 176, 181
 Vector(s)
 basic description of, 22, 129148
 "code bloat" and, 265266
 common members of, 320321
 constructing sequences with, 130135
 constructors, 130135, 334335
 containers and, 22
 destructors, 334335
 demonstrating, with arrays, 2728
 deque and, 148
 erasure and, 140143
 insertion and, 141
 iterators and, 57, 61, 66
 lists and, 153
 mutating sequence algorithms and, 98
 of PS objects, reading dictionaries into, 229230
 reallocation and, 140
 types, 129140
 vector<char> class, 1214
 vector class, 12, 28, 30, 331339
 vector container, 127, 193, 194197, 218, 237238, 240241, 244, 359
 vector<T> container, 19
 Virtual functions, 260265
 void type, 448

W
 Weak ordering, 121
 Web (tool), 223
 word_pairs, 231, 238
 word_pairs vector, 229, 230
 word_pairs multimap, 248249
 Worstcase time, 1518
A
ONE MONTH ACCESS!
WITH PURCHASE
Get unlimited 30day access to thousands of Books & Training Videos about technology, professional development and digital media If you continue your subscription after your 30day trial, you can receive 30% off a monthly subscription to the Safari Library for up to 12 months.
Other Things You Might Like
 Tour of C++, A
 Book $23.99
 C++ Programming Language, The, 4th Edition
 eBook (Watermarked) $47.99