Home > Store > Programming > C/C++

larger cover

Add To My Wish List

Register your product to gain access to bonus material or receive a coupon.

STL Tutorial and Reference Guide: C++ Programming with the Standard Template Library, 2nd Edition

Book

  • This product currently is not for sale.
Not for Sale
  • About
  • Description
  • Downloads
  • Sample Content
  • Updates

Features

  • NEW!

  • Copyright 2001
  • Dimensions: 7-3/8x9-1/4
  • Pages: 560
  • Edition: 2nd
  • Book
  • ISBN-10: 0-201-37923-6
  • ISBN-13: 978-0-201-37923-5

"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 in-depth explanations of iterators, generic algorithms, containers, function objects, and much more. Several larger, non-trivial applications demonstrate how to put STL's power and flexibility to work. This book will also show you how to integrate STL with object-oriented 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 real-world 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/stl-book/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.

1. Introduction.

Who Should Read This Book.

What Generic Programming Is and Why It's Important.

How C++ Templates Enable Generic Programming.

The "Code Bloat" Problem with Templates.

Understanding STL's Performance Guarantees.

2. Overview of STL Components.

Containers.

Generic Algorithms.

Iterators.

Function Objects.

Adaptors.

Allocators.

3. How STL Differs from Other Libraries.

Extensibility.

Component Interchangeability.

Algorithm/Container Compatibility.

4. Iterators.

Input Iterators.

Output Iterators.

Forward Iterators.

Bidirectional Iterators.

Random Access Iterators.

The STL Iterator Hierarchy: Combining Algorithms and Containers Efficiently.

Insert Iterators.

Revisiting Input and Output: Stream Iterators.

Specification of Iterator Categories Required by STL Algorithms.

Designing Generic Algorithms.

Why Some Algorithms Require More Powerful Iterators.

Choosing the Right Algorithm.

Constant Versus Mutable Iterator Types.

Iterator Categories Provided by STL Containers.

5. Generic Algorithms.

Basic Algorithm Organization in STL.

Nonmutating Sequence Algorithms.

Mutating Sequence Algorithms.

Sorting-Related Algorithms.

Generalized Numeric Algorithms.

6. Sequence Containers.

Vectors.

Deques.

Lists.

7. Sorted Associative Containers.

Sets and Multisets.

Maps and Multimaps.

8. Function Objects.

Passing Functions via Function Pointers.

Advantages of Specifying Function Objects with Template Parameters.

STL-Provided Function Objects.

9. Container Adaptors.

Stack Container Adaptor.

Queue Container Adaptor.

Priority Queue Container Adaptor.

10. Iterator Adaptors.

11. Function Adaptors.

Binders.

Negators.

Adaptors for Pointers to Functions.

II. PUTTING IT TOGETHER: EXAMPLE PROGRAMS.

12. Program for Searching a Dictionary.

Finding Anagrams of a Given Word.

Interacting with the Standard String and I/O Streams Classes.

Generating Permutations and Searching the Dictionary.

Complete Program.

How Fast Is It?

13. Program for Finding All Anagram Groups.

Finding Anagram Groups.

Defining a Data Structure to Work with STL.

Creating Function Objects for Comparisons.

Complete Anagram Group Finding Program.

Reading the Dictionary into a Vector of PS Objects.

Using a Comparison Object to Sort Word Pairs.

Using an Equality Predicate Object to Search for Adjacent Equal Elements.

Using a Function Adaptor to Obtain a Predicate Object.

Copying the Anagram Group to the Output Stream.

Output of the Anagram Program.

14. Better Anagram Program: Using the List and Map Containers.

Data Structure Holding Iterator Pairs.

Storing Information in a Map of Lists.

Outputting the Anagram Groups in Order of Size.

Better Anagram Program.

Output of the Program.

Why Use a Map Container?

15. Faster Anagram Program: Using Multimaps.

Finding Anagram Groups, Version 3.

Declaration of the Multimap.

Reading the Dictionary into the Multimap.

Finding the Anagram Groups in the Multimap.

Outputting the Anagram Groups in Order of Size.

Output of the Program.

How Fast Is It?

16. Defining an Iterator Class.

New Kind of Iterator: Counting Iterator.

Counting Iterator Class.

17. Combining STL with Object-Oriented Programming.

Using Inheritance and Virtual Functions.

Avoiding "Code Bloat" from Container Instances.

18. Program for Displaying Theoretical Computer Science Genealogy.

Sorting Students by Date.

Associating Students with Advisors.

Finding the Roots of the Tree.

Reading the File.

Printing the Results.

Complete "Genealogy" Program.

19. Class for Timing Generic Algorithms.

Obstacles to Accurate Timing of Algorithms.

Overcoming the Obstacles.

Refining the Approach.

Automated Analysis with a Timer Class.

Timing the STL Sort Algorithms.

III. STL REFERENCE GUIDE.

20. Iterator Reference Guide.

Input Iterator Requirements.

Output Iterator Requirements.

Forward Iterator Requirements.

Bidirectional Iterator Requirements.

Random Access Iterator Requirements.

Iterator Traits.

Iterator Operations.

Istream Iterators.

Ostream Iterators.

Reverse Iterators.

Back Insert Iterators.

Front Insert Iterators.

Insert Iterators.

21. Container Reference Guide.

Requirements.

Organization of the Container Class Descriptions.

Vector.

Deque.

List.

Set.

Multiset.

Map.

Multimap.

Stack Container Adaptor.

Queue Container Adaptor.

Priority Queue Container Adaptor.

22. Generic Algorithm Reference Guide.

Organization of the Algorithm Descriptions.

Nonmutating Sequence Algorithm Overview.

For Each.

Find.

Find First.

Adjacent Find.

Count.

Mismatch.

Equal.

Search.

Search N.

Find End.

Mutating Sequence Algorithm Overview.

Copy.

Swap.

Transform.

Replace.

Fill.

Generate.

Remove.

Unique.

Reverse.

Rotate.

Random Shuffle.

Partition.

Sorting-Related Algorithms Overview.

Sort.

Nth Element.

Binary Search.

Merge.

Set Operations on Sorted Structures.

Heap Operations.

Min and Max.

Lexicographical Comparison.

Permutation Generators.

Generalized Numeric Algorithms Overview.

Accumulate.

Inner Product.

Partial Sum.

Adjacent Difference.

23. Function Object and Function Adaptor Reference Guide.

Requirements.

Base Classes.

Arithmetic Operations.

Comparison Operations.

Logical Operations.

Negator Adaptors.

Binder Adaptors.

Adaptors for Pointers to Functions.

Adaptors for Pointers to Member Functions.

24. Allocator Reference Guide.

Introduction.

Allocator Requirements.

Default Allocator.

Custom Allocators 448

25. Utilities Reference Guide.

Introduction.

Comparison Functions.

Pairs.

Appendix A: STL Header Files.

Appendix B: String Reference Guide.

String Classes.

Character Traits.

Appendix C: STL Include Files Used in Example Programs.

Files Used in Example 17.1.

Appendix D: STL Resources.

Internet Addresses for SGI Reference Implementation of ST.

World Wide Web Address for Source Code for Examples in this Book.

STL-Compatible Compilers.

Other Related STL and C++ Documents.

Generic Programming and STL Discussion List.

References.

Index. 0201379236T04062001

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 language-supported compile-time techniques) to many different uses.
  • The generality of STL components has been achieved without sacrificing efficiency.
  • The design of STL components as fine-grained, interchangeable building blocks makes them a suitable basis for further development of components for specialized areas such as databases, user interfaces, and so forth.
We have enjoyed seeing these statements borne out by the developments of the past five years.

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 STL-related 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 then-colleagues 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 Hewlett-Packard 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 Hewlett-Packard'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 user-level 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 Addison-Wesley 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 Addison-Wesley 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

A

Abstract data types, 127
Abstractions, family of, 127-128
Accessor(s)
container, 144-145
lists and, 160
maps/multimaps and, 181
sorted associative containers and, 170-173
deque and, 151
accumulate algorithm, 33-42, 122-123, 184-187, 427
Actual types, 8
Adaptability, 5
Adaptor(s)
basic description of, 40-43
pointer-to-function, 43
priority_queue, 43
queue, 43
reference guide, 431-440
stack, 43
adjacent_difference algorithm, 124-125, 430
adjacent_find algorithm, 77, 78-80, 231, 248, 389, 392-393
allocate function, 451
Allocator(s)
basic description of, 3, 43-44
class, 441-454
common member functions in all, 443-445
constructors, 446
custom, 448-454
destructors, 446
objects, 320
reference guide, 441-454
passing, to STL containers, 441-442
requirements, 442-445
Allocator template parameter, 14, 150, 154, 332, 340, 360, 374
Amortized
constant time, 17-18
time complexity, 17-18
Anagram groups. Anagrams
copying, to output streams, 232
finding, 225-233
outputting, in order of size, 237-238, 249
Anagrams. See also Anagram groups
multimaps and, 243-250
searching for, 215-217, 225-342
ANSI/ISO C++ Committee, 4
ANSI/ISO C++ Standard, 484
arithmetic operations, 433
Arrays
copying versions of algorithms and, 74-75
demonstrating the find algorithm with, 26-30
demonstrating the merge algorithm with, 31-32
find algorithm and, 66
input iterators and, 51-52
lists and, 153
maps and, 174-175
output iterators and, 53-54
rearranging elements of, 76
ASCII (American Standard Code for Information Interchange), 267, 273
assert macro, 21
assign function, 146-147, 152, 160, 174
Associative containers, 24-26, 320-321
Automatic expansion, 240-241

B

back function, 140-143, 193, 196
back_inserter template, 60-61, 63
back_inserter function, 314
back insert iterators, 60-61, 313-315
basic_string class, 462-472
begin function, 20-21, 24, 28, 34, 69-70, 165, 220
Bidirectional iterator(s), 36, 49, 55-57. See also Iterators
classification of, 58
requirements, 299-300
as more powerful, 67
random access iterators and, 56
reverse algorithm and, 96
sequence containers and, 137-138
Big-Oh notation, 15-18, 287, 292, 389
binary_function, 39, 187
binary predicate parameters, 75-76
binary_search algorithm, 68, 112-114
basic description of, 410, 415-417
random access iterators and, 56-57
searching dictionaries and, 218, 221, 228
Binders, 43, 205-206, 435-436. See also Function adaptors
Boolean values, 7, 21, 166
Borland C++, 484
Briggs's nuweb tool, 217

C

C++ (high-level language)
compilers, STL-compatible, 484
literate programming and, 223
libraries, STL and difference between, 45-48
partial specialization and, 147
templates, generic programming and, relationship of, 7-14
Standard Library, 4
C++ Programming Language, The (Stroustrup), 260, 261
char* data type, 28
char_traits class, 472-476
char_type, 474-475
Character
manipulation functions, 473-476
traits, 472-476
Class(es). See also Classes (listed by name); Container adaptors
declarations, 330, 332
descriptions, organization of, 330-331
I/O stream, interacting with, 218-220
Classes (listed by name). See also Classes
allocator class, 441-454
basic_string class, 462-472
calc_square<int> class, 91
char_traits class, 472-476
earlier class, 275
greater class, 76
istream_iterator class, 72, 304-307
iterator_category class, 303-304
iterator_traits class, 254, 301-303
line class, 260
list<char> class, 13
list class, 56
map class, 162
multimap class, 162
multiply class, 39
multiset class, 162-174
ostream_iterator class, 54, 72, 289, 298, 304-309
PriorityQueueAsList class, 194
PriorityQueueAsVector class, 194
QueueAsDoubleList class, 194
QueueAsList class, 194
QueueAsVector class, 194
rectangle class, 260-261
reverse_iterator class, 203, 310-311
set class, 162-174
shape class, 260
StackAsList class, 194
string class, 21-22, 26, 103, 218-220, 461-472
timer class, 284-292
vector<char> class, 12-14
vector class, 12, 28, 30, 331-339
clock function, 279-280, 282-283
CLOCKS_PER_SEC constant, 280
clock_t, 280
"Code bloat" problem, 14, 208, 259, 265-266
Comments, 274
Compare(), 164
Comparison
functions, 455-457
objects, sorting word pairs with, 230
operations, 58, 433-434, 455-457
Compatibility
algorithm/container, 48, 68
plug, 6
Compilers, STL-compatible, 484
Components
categories of, 34
interchangeability of, 46-48
overview of, 18-44
const_iterator, 69-72, 130, 145
const_pointer, 130
const_reference, 130, 145
const_reverse_iterator, 201
Constant iterators
basic description of, 296
versus mutable iterators, 68-70
Constant reference parameters, 9
Constant time, 16, 56, 147, 167, 296
Constructor(s)
allocator, 446
basic description of, 319, 324-325
class descriptions and, 331
constructing sequences with, 130-135
deque, 340-341
function objects and, 190
iterators and, 306-309, 311, 314-316
lists and, 154, 347-348
map, 176, 368
multimap, 176, 374
priority_queue, 384
queue, 382
sequence containers and, 130-135, 150, 154
set, 154, 356
sorted associative containers and, 164, 176
stacks and, 379
string, 463-466
utilities and, 457
vector, 334-335
Container(s)
accesssors, 144-145
adaptors, 193-200, 319
allocators and, 43-44
associative, 24-26, 320-321
basic description of, 19-26
in C++ libraries other than STL, 45-48
class descriptions, 330-339
classes, generic, 9
combining, with algorithms, 58-59
common type definitions in all, 320-321
common member functions in all, 322-323
common members in all, 320-323
compatibility of, with algorithms, 48, 68
connecting, with iterators, 4, 5
converting strings to, 13
design and organization of, 319-320
equality, 145-146
important characteristics of, 319-320
instances, "code bloat" from, 265-266
iterator categories and, 58, 59, 71-72
less-than relations and, 145-146
passing allocators to, 441-442
reference guide, 319-386
reversible, 324
sequence, 19-24
sorted, 24-26
sorted associative, 127
Container template parameter, 13
Converse relation, 105
copy algorithm, 53-54, 87-89, 289
basic description of, 398, 399-400
iterators and, 204, 297
searching dictionaries and, 218, 249
copy_backward algorithm, 87-89
copy constructor, 134, 190
defining iterator classes and, 253, 254-255
insert iterators and, 60, 61
copying versions, of algorithms, 74-75
count algorithm, 77, 80-81, 172-173, 389, 393-394
count_if algorithm, 80-81
counting iterators, 251-258
ctime header, 280
Custom allocators, 448-454. See also Allocators
CWeb, 223

D

Data abstraction, 127
Database(s)
associating students with advisors in, 268-270
sorting student data in, 267-268
trees, finding the roots of, 270-273
data_map, 268, 275
Data structures
defining, 226-227
holding iterator pairs, 234-235
deallocate function, 451, 454
default allocators, 445-448
Default template parameters, 14
Deferenceable value, use of the term, 295
Deletions, See also Erasure
container adaptors and, 193
lists and, 152-153
stacks and, 378
deque
basic description of, 29, 148-152, 339-345
common members of, 320-321
constructors, 151, 340-341
destructors, 340-341
container adaptors and, 193, 194-197
demonstrating the find algorithm with, 29-30
demonstrating the merge algorithm with, 31-32
destructors, 340-341
erasure and, 142, 344, 345-354
find algorithm and, 66
insert functions, 343-345, 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, 340-341
list, 347-348
map, 368
multimap, 374
set, 356
string, 463-466
vector, 334-335
Dictionaries
finding anagram groups in, 225-233
finding anagrams for a given word in, 215-217
permutations for membership in, testing, 220-221
programs for searching, 215-223
reading, into multimaps, 247-249
reading, into vectors of PS objects, 229-230
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, 193-194, 196, 198-200
Encapsulation, 43-44, 320
end function, 20-21, 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, 82-85, 389, 395-396
equal_range algorithm and, 112, 172, 410
iterators and, 313
less-than relations and, 145-46
lists and, 160
maps/multimaps and, 181-182
predicate objects, 230-231
sorted associative containers and, 173
erase function, 320, 325-326, 329, 331
deque and, 344, 345-354
iterators and, 70, 71-72
lists and, 155-156, 351, 354
maps and, 371-372
multimaps and, 378
multisets and, 364
sequence containers and, 142-143, 151, 155-156
set and, 359-360
sorted associative containers and, 168-170
strings and, 471
vectors and, 338-339
Erasure. See also Deletion
with the pop_back function, 140-143
lists and, 155-156
maps/multimaps and, 181
with the pop_back function, 140-143
sequence containers and, 140-143, 151, 155-156
sorted associative containers and, 168-170
Extensibility, 46

F

FIFO (first-in, first-out), 196
fill algorithm, 89-90, 398, 403
fill_n algorithm, 89-90
find algorithm, 26-30, 36, 40, 45, 77-78, 389, 391
advantages of, 112
compatibility of, with containers, 48, 68
component interchangeability and, 47-48
defining iterator classes and, 257
definition of, 65-66
iterators and, 50-52, 59, 64-65, 202-203
predicate version of, 77
sorted associative containers and, 168-171
find_end algorithm, 390, 397-398
find_first algorithm, 391-392
find_first_of algorithm, 389
find_if algorithm, 77, 205, 231, 232, 248
first iterator, 21-22, 28, 33, 49-50, 57
function objects and, 184
sequence containers and, 137-138
firstEqual function object, 227-228, 231, 248
firstLess function object, 227-228, 230
for_each algorithm, 77, 81-82, 389-391
Forward iterators, 36, 49, 54-55
classification of, 58
random access iterators and, 56
requirements, 299
sequence containers and, 137-138
forward_counting_iterator, 257
forward_iterator_tag, 254
ForwardIterator template parameter, 54-55, 253
front function, 196, 198
front_inserter function, 61
front insert iterators, 60-61, 315-316
Function(s). See also Function adaptors; Function objects; Functions (listed by name)
parameters, 75-77
pointers to, function adaptors for, 205, 208-211, 436-439
templates, 7, 10-11
virtual, 260-265
Function adaptors, 205-211, 432
binders, 43, 205-206, 435-436
categories of, 205
negators, 43, 205, 206-208, 435
for pointers to functions, 205, 208-211, 436-439
using, to obtain predicate objects, 231-232
Function object(s)
basic description of, 36-40, 183-191
creating, for comparisons, 227-228
reference guide, 431-440
operator overloading and, 38
specifying, with template parameters, 186-191
STL-provided, 191
Functions (listed by name). See also erase function; insert function
accumulate function, 33-42, 184-187
allocate function, 451
assign function, 146-147, 152, 160, 174
back function, 140-143, 193, 196
back_inserter function, 314
begin function, 20-21, 24, 28, 34, 69-70, 165, 220
capacity function, 138-140, 151, 160
clock function, 279-280, 282-283
deallocate function, 451, 454
distance function, 249
draw function, 261
empty function, 193-194, 196, 198-200
end function, 20-21, 24, 28, 34, 165, 220
front function, 196, 198
front_inserter function, 61
inserter function, 62, 314
key_compare function, 162-163, 173, 175, 182, 355
key_type function, 162, 175
lexicographical_compare function, 146
make function, 13-14, 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, 140-143, 193-194, 198
pop_front function, 61, 142, 151, 196-197
pop function, 194, 199
print_list function, 82
push_back function, 60, 61, 135-140, 148-149, 153-154, 193-198
push_front function, 60, 61, 127, 148-149, 151, 153-154
push function, 194
rbegin function, 201
remove function, 160
rend function, 42-43, 201
report function, 252
reserve function, 138-140, 149-151, 155
reverse function, 136-138
size function, 146, 193, 194, 196, 198-200
sort function, 48
splice function, 156
strchr function, 474
strcmp function, 473
strlen function, 474
swap function, 147, 152, 160, 182
time function, 283-284
top function, 194, 199
unique function, 158-159
vector function, 23, 261
Function templates
basic description of, 7, 10-11
member, 12
functional header, 76

G

Genealogy program, 267-278
Generalized numeric algorithms, 426-427
generate algorithm, 90-91, 398, 404
Generic. See also Generic algorithms
container classes, 9
programming, basic description of, 4-7
Generic algorithms. See also Generic algorithms (listed by name)
basic description of, 3, 5-6, 26-32, 73-126
C++ templates and, relation of, 7-14
choosing the right, 68-70
combining, with containers, 58-59
compatibility of, with containers, 48, 68
component interchangeability and, 47
copying versions of, 74-75
definition of, with function templates, 10-11
demonstrating, with arrays, 26-27
descriptions, organization of, 387-389
designing, 65-66
function parameters and, 75-77
in-place versions of, 74-75
iterator categories and, 58-59, 64-65
organization of, in STL, 73-77
partial specialization and, 14
reference guide, 387-430
which require more powerful iterators, 67
sequence types and, 20
single-pass, 66
timing, class for, 279-317
Generic algorithms (listed by name). See also find algorithm; merge algorithm;
sort algorithm
accumulate algorithm, 122-123, 427
adjacent_difference algorithm, 124-125, 430
adjacent_find algorithm, 77, 78-80, 231, 248, 389, 392-393
binary_search algorithm, 56-57, 68, 112-114, 218, 221, 228, 410, 415-417
copy algorithm, 53-54, 87-89, 204, 218, 249, 289, 297, 398, 399-400
copy_backward algorithm, 87-89
count algorithm, 77, 80-81, 172-173, 389, 393-394
fill algorithm, 89-90, 398, 403
fill_n algorithm, 89-90
find_end algorithm, 390, 397-398
find_first algorithm, 391-392
find_first_of algorithm, 389
find_if algorithm, 77, 205, 231, 232, 248
generate algorithm, 90-91, 398, 404
includes algorithm, 115, 410, 418-421
inner_product algorithm, 125-126, 177-178, 427
inplace_merge algorithm, 114
introselect algorithm, 112
lexicographical_compare algorithm, 120-121, 173
lower_bound algorithm, 112-114, 170-172, 410
make_heap algorithm, 117-119, 410, 421-423
max algorithm, 11, 119-120, 410, 423-424
max_element algorithm, 119-120, 410, 423-424
min algorithm, 119-120, 410, 423-424
min_element algorithm, 119-120, 410, 423-424
mismatch algorithm, 77, 82-85, 389, 394-395
next_permutation algorithm, 121-122, 221, 425-426
nth_element algorithm, 110-112, 410, 414-415
partial_sort algorithm, 106-110, 292, 410, 412-414
partial_sum algorithm, 123-125, 429
partition algorithm, 91-93, 399, 409-410
pop_heap algorithm, 117-119, 410, 421-423
prev_permutation algorithm, 121-122, 425-426
push_heap algorithm, 117-119, 410, 421-423
random_shuffle algorithm, 76, 93-94, 346, 399, 408-409
remove algorithm, 94-95, 351-353, 398, 404-405
remove_if algorithm, 351-353
replace algorithm, 54-55, 95-96, 398, 402-403
replace_copy algorithm, 75
reserve algorithm, 469
reverse_copy algorithm, 74-75
rotate algorithm, 96-97, 399, 408
search algorithm, 65, 77, 96-97, 389, 396
search_n algorithm, 390, 397
set_difference algorithm, 115-117, 410, 418-421
set_intersection algorithm, 115-117, 410, 418-421
set_symmetric difference algorithm, 115-117, 410, 418-421
set_union algorithm, 115-117, 410, 418-421
sort_heap algorithm, 117-119, 410, 421-423
splice algorithm, 351-353
stable_partition algorithm, 91-93
stable_sort algorithm, 106-110, 291, 410, 412-414
swap algorithm, 97-98, 147, 174, 398, 400-401
swap_ranges algorithm, 98-99
transform algorithm, 99-100, 398, 401-402
unique algorithm, 87, 100-102, 351-353, 398, 406-407
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, 161-162
Header files, 260, 289, 359, 477, 479, 481
Heap operations, 117-119, 421-423
heapsort, 106
Homogenous storage, 259

I

ifstream constructor, 220
In-place versions, of algorithms, 74-75
Include files, 477-482
includes algorithm, 115, 410, 418-421
Inheritance, 260-265
inner_product algorithm, 125-126, 177-178, 427
inplace_merge algorithm, 114
Input iterator(s), 35, 49
basic description of, 50-52
classification of, 58
find algorithm and, 65
random access iterators and, 56
requirements, 296-298
InputIterator, 12, 50, 187
inserter function, 62, 314
inserter template, 62
insert function, 12, 60, 62, 70-72, 324-331
deque and, 343-345, 350
lists and, 354
maps and, 371
multimaps and, 376-377
multisets and, 363-364
sequence containers and, 128, 135-140, 143, 151
set and, 358-359
sorted associative containers and, 164-167
strings and, 470-471
vectors and, 338, 339
Insert iterators, 59-62, 316-317
Insertion, 193, 320. See also insert function; Insert iterator
lists and, 152-155, 354
maps/multimaps and, 176-181, 376-377
sorted associative containers and, 164-167
stacks and, 379
insert mode, 59
Instantiation, 8, 13-15
Interchangeability, of components, 46-48
International Standard for C++, 4
introselect algorithm, 112
introsort algorithm, 107
I/O stream classes, interacting with, 218-220
iostreams, 51-52, 218-220
istream_iterator class, 6, 63-65, 72, 304-307
istream iterators, 6, 52, 63-65, 72, 218, 304-307
Iterator(s). See also specific types
accumulate algorithm with, 41-42
adaptors, 201-204
basic description of, 3, 5, 28, 33-36, 49-72
categories, 35, 64-65, 71-72
classes, 72, 251-258, 302-307
containers and, 21
deque, 150
find algorithm and, 28
hierarchy of, 58-59
input, 35
operations, 304
output, 35
pairs, data structure holding, 235-236
range of, 49-50
random access, 36
reference guide, 295-318
requirement of more powerful, for specific algorithms, 67
sequence containers and, 129, 140, 143, 150
subtraction of, 57-58
tags, standard, 303-304
terminology for, 295-296
traits, 301-304
iterator_category class, 303-304
iterator_traits class, 254, 301-303
iterator_type, 137-138

K

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

L

LastNameLess(), 104
less function object type, 103
less<int>(), 103
Less-than relations, 145-146, 152, 181-182
lists and, 160
sorted associative containers and, 173, 181-182
Levy, S., 223
lexicographical order, 221
lexicographical_compare algorithm, 120-121, 146, 173
LIFO (last-in, first-out), 196
line class, 260
Linear time, 16, 20, 142
List(s)
basic description of, 152-160
common members of, 320-321
constructors, 347-348
demonstrating the find algorithm with, 28-29
destructors, 347-348
erasure and, 142, 354
input iterators and, 51-52
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, 351-352
storing information in a map of, 236-237
stream iterators and, 63
list<char> class, 13, 23-24
list class, 56
list container, 127, 193, 194-197
demonstrating the merge algorithm with, 31-32
header files and, 359
searching dictionaries and, 235-242
List iterators, 66, 67
List sequence abstraction, 152-160
Literate programming style, 23, 217, 218, 220, 223
Logarithmic time, 16, 112-113
Logical operations, 434-435
lower_bound algorithm, 112-114, 170-172, 410

M

make function, 13-14, 23
make_heap algorithm, 117-119, 410, 421-423
Map(s), 25-26, 365-373
basic description of, 174-182
common members of, 320-321
constructors, 176, 368
demonstrating, 25-26
destructors, 368
insertion into, 176-181
iterators and, 71-72
special operations for, 372-373
map class, 162
map container, 127-128, 235-242, 326-330, 359
map<Key, T> container, 25
map<Key, T> object, 71-72
map<string, long> container, 25
max algorithm, 11, 119-120, 410, 423-424
max_element algorithm, 119-120, 410, 423-424
Maximum time, 15
Member function templates, 11
memcpy function, 474
memmove function, 474
Memory, 283, 453. See also Allocators
constraints, adaptation to, 107
models, 320-321
memset function, 474
merge algorithm, 6, 30-32, 36, 114-115, 410
basic description of, 351-353, 417-418
compatibility of, with containers, 48
component interchangeability and, 47
iterators and, 59, 62-64
lists and, 159
microprocessors, 280, 283
min algorithm, 119-120, 410, 423-424
min_element algorithm, 119-120, 410, 423-424
mismatch algorithm, 77, 82-85, 389, 394-395
move function, 261
mult function, 38
multfunobj operator, 187
multfun operator, 185-186
Multimap(s), 365, 374-378
basic description of, 174-182
common members of, 320-321
constructors for, 176, 374
declarations, 246-147
finding anagram groups in, 247-249
insertion into, 176-181
iterators and, 71-72
searching dictionaries and, 243-250
special operations for, 377-378
multimap class, 162
multimap container, 127-128, 326-330, 359
multimap<Key, T> container, 25
multiply class, 39
Multiset(s), 170-173, 360-365
common members of, 320-321
constructors, 361-362
destructors, 361-362, 374
erasing elements from, 168-170
special operations for, 365
multiset class, 162-174
multiset container, 127-128, 279, 326-330
multiset<Key> container, 25
Mutable iterators, 68-70, 296
Mutating sequence algorithms, 87-102, 398-399. See also reverse algorithm
copy_backward algorithm, 87-89
fill algorithm, 89-90, 398, 403
fill_n algorithm, 89-90
generate algorithm, 90-91, 398, 404
partition algorithm, 91-93, 399, 409-410
random_shuffle algorithm, 76, 93-94, 346, 399, 408-409
remove algorithm, 94-95, 351-353, 398, 404-405
replace algorithm, 54-55, 95-96, 398, 402-403
rotate algorithm, 96-97, 399, 408
swap algorithm, 97-98, 147, 174, 398, 400-401
swap_ranges algorithm, 98-99
stable_partition algorithm, 91-93
transform algorithm, 99-100, 398, 401-402
unique algorithm, 87, 100-102, 351-353, 398, 406-407
my_algorithm function, 304
my_algorithm_impl function, 304

N

negators, 43, 205, 206-208, 435
next_permutation algorithm, 121-122, 221, 425-426
Nondecreasing (ascending) order, 105-106
nonincreasing (descending) order, 105-106
Nonmutating sequence algorithms, 77-87, 389-390. See also find algorithm
adjacent_find algorithm, 77, 78-80, 231, 248, 389, 392-393
count algorithm, 77, 80-81, 172-173, 389, 393-394
equal algorithm, 77, 82-85, 389, 395-396
for_each algorithm, 77, 81-82, 389-391
mismatch algorithm, 77, 82-85, 389, 394-395
search algorithm, 65, 77, 96-97, 389, 396
not_equal_to, 81
nth_element algorithm, 110-112, 410, 414-415
Numeric algorithms, 122-126
nuweb, 217

O

Object-oriented programming, combining STL with, 259-266
Open and orthogonal structure, 46
Operation counting, 186-191
Operators
= operator, 53, 65, 35, 132-33, 255
+ operator, 29, 36-37, 125
++ operator, 29, 33, 35, 49, 51, 53, 65-66, 70, 255-256, 296
* operator, 33, 35, 125, 51, 65-66, 173, 207, 298
< operator, 30, 77, 102-103
- operator, 146-147, 152, 160, 182
== operator, 53, 104, 132-133, 145-146, 163, 173-174, 255
=> operator, 102-103
> operator, 102-103, 105
>= operator, 207
[] operator, 177, 179, 181
overloading, 38
ordering predicates, 313
ostream iterators, 53-54, 72, 289, 298, 304-309
ostream_iterator class, 6, 54, 63, 72, 289, 298, 304-309
ostream_iterator constructor, 54
output iterator(s), 35, 49, 52-54
classification of, 58
random access iterators and, 56
requirements, 298
overwrite mode, 59

P

pair, 8-9, 11, 227, 235, 456
pair<const Key, T>, 71-72
Partial specialization, 14, 147
partial_sort algorithm, 106-110, 292, 410, 412-414
partial_sum algorithm, 123-125, 429
partition algorithm, 91-93, 399, 409-410
Partitioning strategy, 107
partitions, 91-93, 107, 399, 409-410
Pascal, 223
Past-the-end-values, use of the term, 295
Permutation(s)
algorithms, 121-122
generating, 220-221, 425-426
Pointer(s). See also Function adaptors
forward iterators and, 54-55
random access iterators and, 57
sequence containers and, 129
using, as output iterators, 53
pop_back function, 140-143, 193-194, 198
pop_front function, 61, 142, 151, 196-197
pop function, 194, 199
pop_heap algorithm, 117-119, 410, 421-423
position iterator, 12
PPS iterator pair, 235-237
Predicates, 75, 91, 231-232
prev_permutation algorithm, 121-122, 425-426
print_list function, 82
Printing, database information, 275-276
Priority queue, 43, 194, 198-200, 384-385
PriorityQueueAsList class, 194
PriorityQueueAsVector class, 194
priority_queue container adaptor, 198-200, 384-385
Processors, 280, 283
ptr_fun, 209-210
Public member functions, 307, 309, 311-312, 314-317
push_back function, 60, 61, 135-140, 148-149, 153-154, 193-198
push_front function, 60, 61, 127, 148-149, 151, 153-154
push function, 194
push_heap algorithm, 117-119, 410, 421-423

Q

Quadratic time, 16, 142
queue
adaptor, 43, 198-199, 380-383
constructors, 382
priority, 43, 194, 198-200, 384-385
QueueAsDoubleList class, 194
QueueAsList class, 194
QueueAsVector class, 194
quicksort, 107

R

Random access
iterators, 36, 49, 56-58, 300-301
as more powerful, 67
sequence containers and, 137
random_shuffle algorithm, 76, 93-94, 346, 399, 408-409
Ranges, use of the term, 296
rbegin function, 201
Reachability, use of the term, 296
Reallocation, 140, 150
rectangle class, 260-261
relation_map, 270-275
remove algorithm, 94-95, 351-353, 398, 404-405
remove function, 160
remove_if algorithm, 351-353
rend function, 42-43, 201
replace algorithm, 54-55, 95-96, 398, 402-403
replace_copy algorithm, 75
report function, 252
report method, 287-288
reserve algorithm, 469
reserve function, 138-140, 149-151, 155
results method, 284, 287
Reusable components, 4
reverse algorithm, 20-24, 96, 159, 351-353
basic description of, 399, 407
bidirectional iterators and, 55-56
sequence containers and, 149, 152, 154
reverse_copy algorithm, 74-75
reverse function, 136-138
Reverse iterators, 40, 42-43, 130, 201, 203, 309-313, 336, 342, 349
reverse_iterator adaptor, 201
reverse_iterator class, 203, 310-311
reverse_iterator component, 40, 42-43, 130
rotate algorithm, 96-97, 399, 408

S

search algorithm, 65, 77, 96-97, 389, 396
screen.cpp, 477-478, 260
screen.h, 260, 477, 479, 481
screen manager, 260
search_n algorithm, 390, 397
Sequence algorithms, 87-102, 398-399. See also reverse algorithm
copy_backward algorithm, 87-89
fill algorithm, 89-90, 398, 403
fill_n algorithm, 89-90
generate algorithm, 90-91, 398, 404
partition algorithm, 91-93, 399, 409-410
random_shuffle algorithm, 76, 93-94, 346, 399, 408-409
remove algorithm, 94-95, 351-353, 398, 404-405
replace algorithm, 54-55, 95-96, 398, 402-403
rotate algorithm, 96-97, 399, 408
swap algorithm, 97-98, 147, 174, 398, 400-401
swap_ranges algorithm, 98-99
stable_partition algorithm, 91-93
transform algorithm, 99-100, 398, 401-402
unique algorithm, 87, 100-102, 351-353, 398, 406-407
Sequence container(s), 19-24, 146-147
basic description of, 127-160, 319
deque container, 127, 359
common members of, 320-321
constructing sequences with, 130-135
list container, 31-32, 127, 193, 194-197, 235-242, 359
requirements, 324-325
vector container, 127-148, 193, 194-197, 218, 237-238, 240-241, 244, 359
Set(s)
accessors and, 170-173
basic description of, 354-360
common members of, 320-321
constructors, 356
destructors, 356
erasing elements from, 168-170
insert functions and, 358-359
operations, 115-117
set class, 162-174
set container, 127-128, 326-330
set_difference algorithm, 115-117, 410, 418-421
set_intersection algorithm, 115-117, 410, 418-421
set<Key> container, 24-25
set_symmetric_difference algorithm, 115-117, 410, 418-421
set_union algorithm, 115-117, 410, 418-421
SGI Web site, 483
shape class, 260
shape.h, 479, 260
shape libraries, 260
shape.cpp, 260
SIGACT Theoretical Computer Science Genealogy page, 267-278
single-pass algorithms, 297
singular values, use of the term, 296
size dependence, 241
size function, 146, 193, 194, 196, 198-200
sort algorithm, 67, 106-110, 158-159, 281-282, 346, 351-353
basic description of, 410, 412-414
compatibility of, with containers, 48
component interchangeability and, 47-48
in-place version of, 74
iterator categories and, 59
object-oriented programming and, 265
timing, 289-292
used with a binary predicate, 76-77
sorted associative containers, 161-182, 319, 326-330
sorted structures, set operation on, 115-117
sort function, 48
sort_heap algorithm, 117-119, 410, 421-423
sorting
searching dictionaries and, 230, 244
students by date, 267-268
word pairs, with comparison objects, 230
Sorting-related algorithms
basic description of, 102-122, 410-412
comparison relations and, 102-105
stability property of, 104-105, 106
Sorting-related member functions, 158-159
sort iterator, 36
splice algorithm, 351-353
splice function, 156
Splicing, 152, 156-158, 351-353
stable_partition algorithm, 91-93
stable_sort algorithm, 106-110, 291, 410, 412-414
Stack(s)
adaptors, 43, 194-196, 378-380, 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, 3-18
combining, with object-oriented programming, 259-266
-compatible compilers, 484
defining a data structure to work with, 226-227
extensibility and, 46
open and orthogonal structure of, 46
organization of algorithms in, 73-77
other C++ libraries and, difference between, 45-48
performance guarantees, 15-18
user-level descripton of, 4
strchr function, 474
strcmp function, 473
stream iterators, 62-63
stream_input iterator, 218
Strict weak ordering, 104
String(s). See also string class
constructors, 463-466
destructors, 463-466
objects, 20-21
reference guide, 461-475
string class, 21-22, 26, 103, 218-220, 461-472
strlen function, 474
Stroustrup, Bjarne, 260
Subtraction, 57
swap algorithm, 97-98, 147, 174, 398, 400-401
swap function, 147, 152, 160, 182
swap_ranges algorithm, 98-99

T

Template(s), 6-10, 15, 266. See also Template parameters
arguments, explict specification of, 12-14
function, basic description of, 7, 10-11
insert iterators and, 60-61
partial specialization and, 147
template keyword, 9
Template parameters, 14, 64
maps/multimaps and, 175-176
sequence containers and, 150
specifying function objects with, 186-191
Time. See also Time complexity
bound, 16
constant, 16, 56, 147, 167, 296
linear, 16, 20, 142
logarithmic, 16, 112-113
maximum, 15
quadratic, 16, 142
worst-case, 15-18
Time complexity, 78, 80, 86-87, 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, 424-425
merge algorithm and, 418
min algorithm and, 424-425
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, 283-284
timer class, 284-292
timer.h, 289
Timing
accurate, obstacles to, 279-280
algorithms, 279-317
top function, 194, 199
T parameter, 150, 154
transform algorithm, 99-100, 398, 401-402
trichotomy law, 102-103
tuples, 177-180
Type parameters, 8

U

unique algorithm, 87, 100-102, 351-353, 398, 406-407
unique function, 158-159
Unix, 280
upper_bound algorithm, 112-114, 170-172, 410
Upper bounds, 15-17, 112-114, 170-172, 410
utilities
comparison functions and, 455-457
reference guide for, 455-457

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, 129-148
"code bloat" and, 265-266
common members of, 320-321
constructing sequences with, 130-135
constructors, 130-135, 334-335
containers and, 22
destructors, 334-335
demonstrating, with arrays, 27-28
deque and, 148
erasure and, 140-143
insertion and, 141
iterators and, 57, 61, 66
lists and, 153
mutating sequence algorithms and, 98
of PS objects, reading dictionaries into, 229-230
reallocation and, 140
types, 129-140
vector<char> class, 12-14
vector class, 12, 28, 30, 331-339
vector container, 127, 193, 194-197, 218, 237-238, 240-241, 244, 359
vector<T> container, 19
Virtual functions, 260-265
void type, 448

W

Weak ordering, 121
Web (tool), 223
word_pairs, 231, 238
word_pairs vector, 229, 230
word_pairs multimap, 248-249
Worst-case time, 15-18

Errata

Click below for Errata related to this title:
Errata

Submit Errata

FREE

ONE MONTH ACCESS!

WITH PURCHASE


Get unlimited 30-day access to thousands of Books & Training Videos about technology, professional development and digital media If you continue your subscription after your 30-day trial, you can receive 30% off a monthly subscription to the Safari Library for up to 12 months.