Home > Store

Generic Programming and the STL: Using and Extending the C++ Standard Template Library

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

Generic Programming and the STL: Using and Extending the C++ Standard Template Library


  • Your Price: $47.99
  • List Price: $59.99
  • Usually ships in 24 hours.


  • Copyright 1999
  • Dimensions: 7-1/2" x 9-1/2"
  • Pages: 576
  • Edition: 1st
  • Book
  • ISBN-10: 0-201-30956-4
  • ISBN-13: 978-0-201-30956-0

Many programmers are unaware that C++ is more than an object-oriented language. C++ is also a language for generic programming, a methodology that can greatly enhance your ability to write efficient and reusable software components.

Written by noted C++ authority Matthew H. Austern, Generic Programming and the STL introduces you to the generic programming paradigm and to the most important instance of that paradigm--the C++ Standard Template Library (STL). This book reveals that the STL is more than a set of convenient container classes: It is also an extensible framework for generic and interoperable components.

Generic Programming and the STL explains the central ideas underlying generic programming--concepts, modeling, and refinement--and shows how these ideas lead to the fundamental concepts of the STL: iterators, containers, and function objects. In this way you will conceive the STL as a library of concepts rather than a library of specific functions and classes. You will learn its formal structure and be able to take full advantage of its potential power. This book enables you to:

  • Extend the STL with your own library of portable and interoperable general-purpose components
  • Create algorithms that are decoupled from the types and data structures they operate on, thus eliminating the need to rewrite basic algorithms and data structures
  • Write more elegant, efficient, and effective code that can be used and reused across platforms

With the knowledge and understanding you will gain, you can achieve greater skill in creating the reusable and portable software that is now invaluable in our diverse and interconnected computing environment.



Web Resources

Click below for Web Resources related to this title:
Author's Web Site

Sample Content

Table of Contents



1. A Tour of the STL.

A Simple Example.


2. Algorithms and Ranges.

Linear Search.

Linear Search in C.


Linear Search in C++.

Concepts and Modeling.


Input Iterators.

Output Iterators.

Forward Iterators.

Bidirectional Iterators.

Random Access Iterators.



3. More about Iterators.

Iterator Traits and Associated Types.

Value Types.

Difference Type.

Reference and Pointer Types.

Dispatching Algorithms and Iterator Tags.

Putting It All Together.

Iterator Traits without iterator_traits.

Defining New Components.

Iterator Adaptors.

Advice for Defining an Iterator.

Advice for Defining an Algorithm.


4. Function Objects.

Generalizing Linear Search.

Function Object Concepts.

Unary and Binary Function Objects.

Predicates and Binary Predicates.

Associated Types.

Function Object Adaptors.

Predefined Function Objects.


5. Containers.

A Simple Container.

An Array Class.

How It Works.

Finishing Touches.

Container Concepts.

Containment of Elements.


The Hierarchy of Containers.

The Trivial Container.

Variable Size Container Concepts.


Associative Containers.



Which Container Should You Use?

Defining Your Own Container.


6. Basic Concepts.


Default Constructible.

Equality Comparable.


LessThan Comparable.

Strict Weakly Comparable.

7. Iterators.

Trivial Iterator.

Input Iterator.

Output Iterator.

Forward Iterator.

Bidirectional Iterator.

Random Access Iterator.

8. Function Objects.

Basic Function Objects.


Unary Function.

Binary Function.

Adaptable Function Objects.

Adaptable Generator.

Adaptable Unary Function.

Adaptable Binary Function.



Binary Predicate.

Adaptable Predicate.

Adaptable Binary Predicate.

Strict Weak Ordering.

Specialized Concepts.

Random Number Generator.

Hash Function.

9. Containers.

General Container Concepts.


Forward Container.

Reversible Container.

Random Access Container.



Front Insertion Sequence.

Back Insertion Sequence.

Associative Containers.

Associative Container.

Unique Associative Container.

Multiple Associative Container.

Simple Associative Container.

Pair Associative Container.

Sorted Associative Container.

Hashed Associative Container.



10. Basic Components.


Iterator Primitives.


Iterator Tag Classes.



Iterator Base Class.


Memory Management Primitives.






Temporary Buffers.



11. Nonmutating Algorithms.

Linear Search.





Subsequence Matching.




Counting Elements.




Comparing Two Ranges.




Minimum and Maximum.





12. Basic Mutating Algorithms.

Copying Ranges.



Swapping Elements.





Replacing Elements.





Filling Ranges.





Removing Elements.







Permuting Algorithms.










Random Shuffling and Sampling.




Generalized Numeric Algorithms.





13. Sorting and Searching.

Sorting Ranges.







Operations on Sorted Ranges.

Binary Search.

Merging Two Sorted Ranges.

Set Operations on Sorted Ranges.

Heap Operations.






14. Iterator Classes.

Insert Iterators.




Stream Iterators.







15. Function Object Classes.

Function Object Base Classes.



Arithmetic Operations.














Logical Operations.




Identity and Projection.






Specialized Function Objects.



Member Function Adaptors.









Other Adaptors.









16. Container Classes.






Associative Containers.









Container Adaptors.




Appendix A. Portability and Standardization.

Language Changes.

The Template Compilation Model.

Default Template Parameters.

Member Templates.

Partial Specialization.

New Keywords.

Library Changes.


Container Adaptors.

Minor Library Changes.

Naming and Packaging.

Index. 0201309564T04062001


This is not a book about object-oriented programming.

You may think that's odd. You probably found this book in the C++ section of the bookstore, after all, and you've probably heard people use object oriented and C++ synonymously, but that isn't the only way to use the C++ language. C++ supports several fundamentally different paradigms, the newest and least familiar of which is generic programming.

Like most new ideas, generic programming actually has a long history. Some of the early research papers on generic programming are nearly 25 years old, and the first experimental generic libraries were written not in C++ but in Ada MS89a, MS89b and Scheme KMS88. Yet generic programming is new enough that no textbooks on the subject exist.

The first example of generic programming to become important outside of research groups was the STL, the C++ Standard Template Library. The Standard Template Library, designed by Alexander Stepanov (then of Hewlett-Packard Laboratories) and Meng Lee, was accepted in 1994 as part of the C++ standard library. The freely available "HP implementation" SL95, which served as a demonstration of the STL's capabilities, was released the same year.

When the Standard Template Library first became part of the C++ standard, the C++ community immediately recognized it as a library of high-quality and efficient container classes. It is always easiest to see what is familiar, and every C++ programmer is familiar with container classes. Every nontrivial program requires some way of managing a collection of objects, and every C++ programmer has written a class that implements strings or vectors or lists.

Container class libraries have been available since the earliest days of C++, and when "template" classes (parameterized types) were added to the language, one of their first uses--indeed, one of the main reasons that templates were introduced--was parameterized container classes. Many different vendors, including Borland, Microsoft, Rogue Wave, and IBM, wrote their own libraries that included Array <T> or its equivalent.

The fact that container classes are so familiar made the STL seem at first to be nothing more than yet another container class library. This familiarity diverted attention from the ways in which the STL was unique.

The STL is a large and extensible body of efficient, generic, and interoperable software components. It includes many of the basic algorithms and data structures of computer science, and it is written so that algorithms and data structures are decoupled from each other. Rather than a container class library, it is more accurate to think of the STL as a library of generic algorithms; containers exist so that the algorithms have something to operate on.

You can use the existing STL algorithms in your programs, just as you can use the existing STL containers. For example, you can use the generic STL sort as you would use the function qsort from the standard C library (although sort is simpler, more flexible, safer, and more efficient). Several books, including David Musser and Atul Saini's STL Tutorial and Reference Guide MS96 and Mark Nelson's C++ Programmer's Guide to the Standard Template Library Nel95, explain how to use the STL in such a way.

Even this much is useful. It is always better to reuse code than to rewrite it, and you can reuse the existing STL algorithms in your own programs. This is still, however, only one aspect of the STL. The STL was designed to be extensible; that is, it was designed so that, just as the different STL components are interoperable with each other, they are also interoperable with components you write yourself. Using the STL effectively means extending it.

Generic Programming

The STL is not just a collection of useful components. Its other aspect, which is less widely recognized and understood, is that it is a formal hierarchy of abstract requirements that describe software components. The reason that the STL's components are interoperable and extensible, and the reason that you can add new algorithms and new containers and can be confident that the new pieces and the old can be used together, is that all STL components are written to conform to precisely specified requirements.

Most of the important advances in computer science have been the discoveries of new kinds of abstractions. One crucial abstraction supported by all contemporary computer languages is the subroutine (a.k.a. the procedure or function--different languages use different terminology). Another abstraction supported by C++ is that of abstract data typing. In C++, it is possible to define a new data type together with that type's basic operations.

The combination of code and data forms an abstract data type, one that is always manipulated through a well-defined interface. Subroutines are an important abstraction because using a subroutine doesn't require that you depend on (or even necessarily know) its exact implementation; similarly, you can use an abstract data type--you can manipulate and even create values--without depending on the actual representation of the data. Only the interface is important.

C++ also supports object-oriented programming Boo94, Mey97, which involves hierarchies of polymorphic data types related by inheritance. Object-oriented programming has one more layer of indirection than abstract data typing, thus it achieves one more step in abstraction. In some circumstances you can refer to a value and manipulate it without needing to specify its exact type. You can write a single function that will operate on a number of types within an inheritance hierarchy.

Generic programming, too, means identifying a new kind of abstraction. The central abstraction of generic programming is less tangible than earlier abstractions like the subroutine or the class or the module. It is a set of requirements on data types. This is a difficult abstraction to grasp because it isn't tied to a specific C++ language feature. There is no keyword in C++ (or, for that matter, in any contemporary computer language) for declaring a set of abstract requirements.

What generic programming provides in return for understanding an abstraction that at first seems frustratingly nebulous is an unprecedented level of flexibility. Just as important, it achieves abstraction without loss of efficiency. Generic programming, unlike object-oriented programming, does not require you to call functions through extra levels of indirection; it allows you to write a fully general and reusable algorithm that is just as efficient as an algorithm handcrafted for a specific data type.

A generic algorithm is written by abstracting algorithms on specific types and specific data structures so that they apply to arguments whose types are as general as possible. This means that a generic algorithm actually has two parts: the actual instructions that describe the steps of the algorithm and the set of requirements that specify precisely which properties its argument types must satisfy.

The central innovation of the STL is the recognition that these type requirements can be specified and systematized. That is, it is possible to define a set of abstract concepts and to say that a type conforms to one of those concepts if it satisfies a certain set of requirements. These concepts are important because most of the assumptions that algorithms make about their types can be expressed both in terms of conformance to concepts and in terms of the relationships between different concepts. Additionally, these concepts form a well-defined hierarchy, one reminiscent of inheritance in traditional object-oriented programming but purely abstract.

This hierarchy of concepts is the conceptual structure of the STL. It is the most important part of the STL, and it is what makes reuse and interoperability possible. The conceptual structure would be important purely as a formal taxonomy of software components, even without its embodiment in code. The STL does include concrete data structures, such as pair and list, but to use those data structure effectively you must understand the conceptual structure they are built upon.

Defining abstract concepts and writing algorithms and data structures in terms of abstract concepts is the essence of generic programming.

How to Read This Book

This book describes the Standard Template Library as a library of abstract concepts. It defines the fundamental concepts and abstractions of the STL and shows what it means for a type to model one of those concepts or for an algorithm to be written in terms of a concept's interface. It discusses the classes and algorithms that are part of the basic STL, and it explains how you can write your own STL-compliant classes and algorithms and when you might want to do so. Finally, it includes a complete reference manual of all of the STL's concepts, classes, and algorithms.

Everyone should read Part I, which introduces the main ideas of the STL and of generic programming. It shows how to use and write a generic algorithm, and it explains what it means for an algorithm to be generic. Genericity has implications that go far beyond the ability to operate on multiple data types.

Exploring the idea of a generic algorithm leads naturally to the central ideas of concepts, modeling, and refinement, ideas that are as basic to generic programming as polymorphism and inheritance are to object-oriented programming. Generic algorithms on one-dimensional ranges, meanwhile, lead to the fundamental concepts of the STL: iterators, containers, and function objects.

Part I introduces the notation and the typographical conventions that are used throughout the remainder of the book: the terminology of modeling and refinement, the asymmetrical notation for ranges, and the special typeface for concept names.

The STL defines many concepts, some of which differ from each other only in technical details. Part I is an overview, and it discusses the broad outlines of STL concepts. Part II is a detailed reference manual that contains a precise definition of each STL concept. You may not wish to read Part II all the way through and, instead, may find it more useful to look up a particular concept only when you need to refer to its definition. (You should refer to Part II whenever you write a new type that conforms to an STL concept.)

Part III is also a reference manual. It documents the STL's predefined algorithms and classes. It relies heavily on the concept definitions of Part II. All STL algorithms and almost all concrete types are templates, and every template parameter can be characterized as the model of some concept. The definitions in Part III are cross-referenced to the appropriate sections of Part II.

In an ideal world, the book would end with Part III. Unfortunately, reality demands one more section, an appendix that discusses portability concerns. When the STL was first released, portability was not an issue because only one implementation existed. That is no longer the case, and whenever more than one implementation of any language or library exists, anyone who cares about portability must be aware of the differences between them.

The old HP implementation is still available by anonymous FTP from butler.hpl.hp.com, but it is no longer being maintained. A newer free implementation, from Silicon Graphics Computer Systems (SGI) is available at http://www.sgi.com/Technology/STL, and a port of the SGI STL to a variety of compilers, maintained by Boris Fomitchev, is available at http://www.metabyte.com/~fbp/stl. Finally, there are several different commercial STL implementations.

If you are writing real programs, it isn't enough to understand the theoretical design of the library; you also have to understand how the various STL implementations and the various C++ compilers differ. These unglamorous but necessary details are the subject of Appendix A.

Who Should Read This Book

While this book is largely about algorithms written in C++, it is neither an introductory textbook on algorithms nor a C++ tutorial. It does explain some of the unfamiliar aspects of both subjects. In particular, since the STL uses templates in ways that are uncommon in other sorts of C++ programs, it discusses some advanced techniques of programming with templates. This should not be your first C++ book, nor should it be your first exposure to an analysis of algorithms. You should know how to write basic C++ programs, and you should know the meaning of notation like O(N).

Two of the standard references on algorithms and data structures are Donald Knuth's The Art of Computer Programming Knu97, Knu98a, Knu98b, and Introduction to Algorithms, by Cormen, Leiserson, and Rivest CLR90. Two of the best introductory C++ books are The C++ Programming Language, by Bjarne Stroustrup Str97 and A C++ Primer, by Stanley Lippman and Josée Lajoie LL98.

How This Book Came About

I joined the compiler group at Silicon Graphics Computer Systems (SGI) in 1996. Alex Stepanov had left HP to join SGI several months before. At the time, SGI's C++ compiler did not include an implementation of the Standard Template Library. Using the original HP implementation as our source base, Alex, Hans Boehm, and I wrote the version of the STL that was shipped with release 7.1 (and subsequent releases) of SGI's MIPSpro compiler.

The SGI Standard Template Library Aus97 included many new and extended features, such as efficient and thread-safe memory allocation, hash tables, and algorithmic improvements. If these enhancements had remained proprietary, they would have been of no value to SGI's customers, so the SGI STL was made freely available to the public. It is distributed on the World Wide Web, along with its documentation, at http://www.sgi.com/Technology/STL.

The documentation, a set of Web pages, treats the STL's conceptual structure as central. It describes the abstract concepts that comprise the structure, and it documents the STL's algorithms and data structures in terms of the abstract concepts. We received many requests for an expanded form of the documentation, and this book is a response to those requests. The reference sections of this book, Parts II and III, are an outgrowth of the SGI STL Web pages.

The Web pages were written for and are copyrighted by SGI. I am using them with the kind permission of my management.


First and foremost, this book could not possibly have existed without the work of Alex Stepanov. Alex was involved with this book at every stage: he brought me to SGI, he taught me almost everything I know about generic programming, he participated in the development of the SGI STL and the SGI STL Web pages, and he encouraged me to turn the Web pages into a book. I am grateful to Alex for all of his help and encouragement.

I also wish to thank Bjarne Stroustrup and Andy Koenig for helping me to understand C++ and Dave Musser for his numerous contributions (some of which can be found in the bibliography) to generic programming, to the STL, and to this book. Dave used an early version of the SGI STL Web pages as part of his course material, and the Web pages were greatly improved through his and his students' comments.

Similarly, this book was greatly improved through the comments of reviewers, including Tom Becker, Steve Clamage, Jay Gischer, Brian Kernighan, Andy Koenig, Angelika Langer, Dave Musser, Sibylla Schupp, and Alex Stepanov, who read early versions. This book is more focused than it would have been without them, and it contains far fewer errors. Any mistakes that remain are my own.

I am also indebted to the staff at Addison-Wesley, including John Fuller, Mike Hendrickson, Marina Lang, and Genevieve Rajewski, for guiding me through the writing process, and to Karen Tongish for her careful copyediting.

Finally, I am grateful to my fiancée, Janet Lafler, for her love and support and for her patience during the many evenings and weekends that I spent writing.

Our cats, Randy and Oliver, tried to help by walking over my keyboard, but in the end I deleted most of their contributions.




Click below for Errata related to this title:

Submit Errata

More Information

InformIT Promotional Mailings & Special Offers

I would like to receive exclusive offers and hear about products from InformIT and its family of brands. I can unsubscribe at any time.


Pearson Education, Inc., 221 River Street, Hoboken, New Jersey 07030, (Pearson) presents this site to provide information about products and services that can be purchased through this site.

This privacy notice provides an overview of our commitment to privacy and describes how we collect, protect, use and share personal information collected through this site. Please note that other Pearson websites and online products and services have their own separate privacy policies.

Collection and Use of Information

To conduct business and deliver products and services, Pearson collects and uses personal information in several ways in connection with this site, including:

Questions and Inquiries

For inquiries and questions, we collect the inquiry or question, together with name, contact details (email address, phone number and mailing address) and any other additional information voluntarily submitted to us through a Contact Us form or an email. We use this information to address the inquiry and respond to the question.

Online Store

For orders and purchases placed through our online store on this site, we collect order details, name, institution name and address (if applicable), email address, phone number, shipping and billing addresses, credit/debit card information, shipping options and any instructions. We use this information to complete transactions, fulfill orders, communicate with individuals placing orders or visiting the online store, and for related purposes.


Pearson may offer opportunities to provide feedback or participate in surveys, including surveys evaluating Pearson products, services or sites. Participation is voluntary. Pearson collects information requested in the survey questions and uses the information to evaluate, support, maintain and improve products, services or sites, develop new products and services, conduct educational research and for other purposes specified in the survey.

Contests and Drawings

Occasionally, we may sponsor a contest or drawing. Participation is optional. Pearson collects name, contact information and other information specified on the entry form for the contest or drawing to conduct the contest or drawing. Pearson may collect additional personal information from the winners of a contest or drawing in order to award the prize and for tax reporting purposes, as required by law.


If you have elected to receive email newsletters or promotional mailings and special offers but want to unsubscribe, simply email information@informit.com.

Service Announcements

On rare occasions it is necessary to send out a strictly service related announcement. For instance, if our service is temporarily suspended for maintenance we might send users an email. Generally, users may not opt-out of these communications, though they can deactivate their account information. However, these communications are not promotional in nature.

Customer Service

We communicate with users on a regular basis to provide requested services and in regard to issues relating to their account we reply via email or phone in accordance with the users' wishes when a user submits their information through our Contact Us form.

Other Collection and Use of Information

Application and System Logs

Pearson automatically collects log data to help ensure the delivery, availability and security of this site. Log data may include technical information about how a user or visitor connected to this site, such as browser type, type of computer/device, operating system, internet service provider and IP address. We use this information for support purposes and to monitor the health of the site, identify problems, improve service, detect unauthorized access and fraudulent activity, prevent and respond to security incidents and appropriately scale computing resources.

Web Analytics

Pearson may use third party web trend analytical services, including Google Analytics, to collect visitor information, such as IP addresses, browser types, referring pages, pages visited and time spent on a particular site. While these analytical services collect and report information on an anonymous basis, they may use cookies to gather web trend information. The information gathered may enable Pearson (but not the third party web trend services) to link information with application and system log data. Pearson uses this information for system administration and to identify problems, improve service, detect unauthorized access and fraudulent activity, prevent and respond to security incidents, appropriately scale computing resources and otherwise support and deliver this site and its services.

Cookies and Related Technologies

This site uses cookies and similar technologies to personalize content, measure traffic patterns, control security, track use and access of information on this site, and provide interest-based messages and advertising. Users can manage and block the use of cookies through their browser. Disabling or blocking certain cookies may limit the functionality of this site.

Do Not Track

This site currently does not respond to Do Not Track signals.


Pearson uses appropriate physical, administrative and technical security measures to protect personal information from unauthorized access, use and disclosure.


This site is not directed to children under the age of 13.


Pearson may send or direct marketing communications to users, provided that

  • Pearson will not use personal information collected or processed as a K-12 school service provider for the purpose of directed or targeted advertising.
  • Such marketing is consistent with applicable law and Pearson's legal obligations.
  • Pearson will not knowingly direct or send marketing communications to an individual who has expressed a preference not to receive marketing.
  • Where required by applicable law, express or implied consent to marketing exists and has not been withdrawn.

Pearson may provide personal information to a third party service provider on a restricted basis to provide marketing solely on behalf of Pearson or an affiliate or customer for whom Pearson is a service provider. Marketing preferences may be changed at any time.

Correcting/Updating Personal Information

If a user's personally identifiable information changes (such as your postal address or email address), we provide a way to correct or update that user's personal data provided to us. This can be done on the Account page. If a user no longer desires our service and desires to delete his or her account, please contact us at customer-service@informit.com and we will process the deletion of a user's account.


Users can always make an informed choice as to whether they should proceed with certain services offered by InformIT. If you choose to remove yourself from our mailing list(s) simply visit the following page and uncheck any communication you no longer want to receive: www.informit.com/u.aspx.

Sale of Personal Information

Pearson does not rent or sell personal information in exchange for any payment of money.

While Pearson does not sell personal information, as defined in Nevada law, Nevada residents may email a request for no sale of their personal information to NevadaDesignatedRequest@pearson.com.

Supplemental Privacy Statement for California Residents

California residents should read our Supplemental privacy statement for California residents in conjunction with this Privacy Notice. The Supplemental privacy statement for California residents explains Pearson's commitment to comply with California law and applies to personal information of California residents collected in connection with this site and the Services.

Sharing and Disclosure

Pearson may disclose personal information, as follows:

  • As required by law.
  • With the consent of the individual (or their parent, if the individual is a minor)
  • In response to a subpoena, court order or legal process, to the extent permitted or required by law
  • To protect the security and safety of individuals, data, assets and systems, consistent with applicable law
  • In connection the sale, joint venture or other transfer of some or all of its company or assets, subject to the provisions of this Privacy Notice
  • To investigate or address actual or suspected fraud or other illegal activities
  • To exercise its legal rights, including enforcement of the Terms of Use for this site or another contract
  • To affiliated Pearson companies and other companies and organizations who perform work for Pearson and are obligated to protect the privacy of personal information consistent with this Privacy Notice
  • To a school, organization, company or government agency, where Pearson collects or processes the personal information in a school setting or on behalf of such organization, company or government agency.


This web site contains links to other sites. Please be aware that we are not responsible for the privacy practices of such other sites. We encourage our users to be aware when they leave our site and to read the privacy statements of each and every web site that collects Personal Information. This privacy statement applies solely to information collected by this web site.

Requests and Contact

Please contact us about this Privacy Notice or if you have any requests or questions relating to the privacy of your personal information.

Changes to this Privacy Notice

We may revise this Privacy Notice through an updated posting. We will identify the effective date of the revision in the posting. Often, updates are made to provide greater clarity or to comply with changes in regulatory requirements. If the updates involve material changes to the collection, protection, use or disclosure of Personal Information, Pearson will provide notice of the change through a conspicuous notice on this site or other appropriate way. Continued use of the site after the effective date of a posted revision evidences acceptance. Please contact us if you have questions or concerns about the Privacy Notice or any objection to any revisions.

Last Update: November 17, 2020