STL Tutorial and Reference Guide: C++ Programming with the Standard Template Library

Description

• Copyright 1996
• Edition: 1st

• Book
• ISBN-10: 0-201-63398-1
• ISBN-13: 978-0-201-63398-6

The Standard Template Library (STL) represents a breakthrough in C++ programming methodology. Comprising a set of C++ generic data structures and algorithms, STL provides reusable, interchangeable components adaptable to many different uses without sacrificing efficiency. Adopted by the ANSI/ISO C++ Standards Committee, STL is an important addition to every C++ programmer's portfolio of skills.

This book introduces you to STL and provides the information and techniques you need to become a proficient STL programmer. The book 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, and function objects. Several larger, non-trivial applications, including a dictionary lookup program, demonstrate how to put STL's power and flexibility to work. The book will also show you how to integrate STL with object-oriented programming techniques, while the comprehensive and detailed STL reference guide will be a constant and convenient companion as you learn to work with the library.

0201633981B04062001



Downloads

Source Code

In this book all major and most minor points are illustrated with actual code examples, more than 80 small programs in all. The source code for all of these programs is available here, either for individual program viewing or all together in a compressed archive file for downloading. (This file and others mentioned below are available in three compression/archive formats; see the README file for details.)

Dictionary file

Several of the programs in Part II of the book use a file containing a dictionary of English words. You can use the programs with your own dictionary file if you have one, or download the 20,159-word dictionary file with which the programs were tested.

String class source file

Another useful source code file is bstring.h, the header file for the string class used in many of the example programs (donated by Modena Software Inc.). This class satisfies most of the requirements for the string class specified by the ANSI/ISO Draft Standard for C++, but is not completely up to date with more recent changes in the Standard.

STL source code

Finally, the October 31, 1995 final release of the Hewlett-Packard STL implementation is also available here. It has been modified slightly to compile well with several major compilers, as described in the next section.

STL-Compatible Compilers

The book's examples, bstring.h, and STL source code (the modified version available at the RPI site) have all been tested successfully with the following compilers:

• Apogee, version 3.0 (Unix)
• Borland C++, Version 4.5 (DOS/Windows)
• IBM xlC (AIX)
• IBM CSet++ (OS/2),
• Microsoft Visual C++, version 4.0 (DOS/Windows)

The examples and bstring.h have also been tested with the Free Software Foundation's compiler,

• GNU C++, version 2.7.2,

which is available on many platforms and comes with its own adaptation of HP STL. All of the example programs compile and execute properly with this version except Examples 5-9, 6-9, 13-1, 14-1, and 16-1.

Other compilers that have been reported to be able to compile STL include DEC C++ 5.0, EDG C++ front-end 2.29 (several compilers based on it), IBM VisualAge C++ 3.0, Kuck and Associates' Photon C++, Metrowerk's Codewarrior 7, Rational Apex C/C++ 2.0.6 , SGI C++ 4.0, Sun C++ 4.1, Symantec C++ 7.2, Watcom C++ 10.5. For further information on STL-compatibility of these and other compilers, see The STL-Compatible Compilers List and The STL Resource List, both maintained by Warren Young.



Sample Content

Table of Contents

Foreword.
Preface.

I. A 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.
Understanding STL's Performance Guarantees.
STL Header Files.
Conventions Used in Examples.
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.
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.
Example: Function Objects That Do Comparisons.
How Function Objects Differ from Function Pointers.
STL-Provided Function Objects.

9. Container Adaptors.
Stack Container Adaptor.
Queue Container Adaptor.
Priority Queue Container Adaptor.

10. Iterator Adaptors.
Reverse Iterators.
Insert Iterators.

11. Function Adaptors.
Negators.
Binders.
Adaptors for Pointers to Functions.

II. PUTTING IT TOGETHER: EXAMPLE PROGRAMS.

12. A Program for Searching a Dictionary.
Finding Anagrams of a Given Word.
Interacting with the Standard I/O Streams.
Searching the Dictionary.
Generating Permutations.
How Fast Is It?

13. A Program for Finding All Anagram Groups.
Finding Anagram Groups.
Defining a Data Structure to Work with STL.
Creating Function Objects for Comparisons.
The 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. A Better Anagram Program: Using the List and Map Containers.
A Data Structure Holding Pairs of Iterators.
Storing Information in a Map of Lists.
Outputting the Anagram Groups in Order of Size.
A Better Anagram Program.
Output of the Program.
Why Use a Map Container?

15. A 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?
Note on a Compiler Problem.

16. Defining an Iterator Class.
A New Kind of Iterator: Counting Iterator.
A Counting Iterator Class.

17. Combining STL with Object-Oriented Programming.
Using Inheritance and Virtual Functions.
Avoiding "Code Bloat" from Container Instances.

III. STL REFERENCE GUIDE.

18. Iterator Reference Guide.
Input Iterator Requirements.
Output Iterator Requirements.
Forward Iterator Requirements.
Bidirectional Iterator Requirements.
Random Access Iterator Requirements.
Istream Iterators.
Ostream Iterators.
Rev__1/2irectional Iterators.
Reverse Iterators.
Back Insert Iterators.
Front Insert Iterators.
Insert Iterators.

19. 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.

20. Generic Algorithm Reference Guide.
Organization of the Algorithm Descriptions.
Nonmutating Sequence Algorithm Overview.
For Each.
Find.
Adjacent Find.
Count.
Mismatch.
Equal.
Search.
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.

21. Function Object and Function Adaptor Reference Guide.
Requirements.
Arithmetic Operations.
Comparison Operations.
Logical Operations.
Negator Adaptors.
Binder Adaptors.
Adaptors for Pointers to Functions.

22. Allocator Reference Guide.
Introduction.
The Default Allocator Interface.
Custom Allocators.

Appendix A. Non-STL Include Files Used in Example Programs.
File Used in "Anagram Finding" Examples in Chapters 13 and 14.
Files Used in "Shape Example" in Chapter 17.

Appendix B. How to Obtain STL Source Code and Related Files.
Internet Address for HP Reference Implementation of STL.
World Wide Web Address for Source Code for Examples in this Book.
Other World Wide Web Resources.
Other Related STL and C++ Documents.
STL Compliant Vendors.

References.
Index. 0201633981T04062001

Preface

In 1968 Doug McIlroy presented his famous paper, "Mass Produced Software Components" (Ref. 6). Now, more than a quarter of a century later, we still have not fully realized his vision of standard libraries of reusable components (which today are also known as "software building blocks" or "software ICs"). In some areas such as numerical and statistical computation, there is a long tradition of heavy use of standard libraries, rather than writing source code entirely from scratch, but in many other areas, standardization hasn't occurred. Even in the area of fundamental data structures and data-processing algorithms, where there is perhaps the greatest potential benefit from component standardization and widespread component use, no set of components has emerged and been embraced by large numbers of programmers or software development managers.

In the absence of a standard set of such data structure and algorithm components, programmers have been forced either to program everything from scratch or to adopt one of several commercial packages. While writing everything from scratch often gives programmers a sense of control, it is also a source of frustration, since there is rarely time to implement the best techniques, even assuming they are already known to the programmer. And the available commercial libraries have suffered from several drawbacks. In the C++ realm, for example, the problems include

• Incompatibility: The interfaces of classes supplied by various vendors are invariably different, making it difficult to write portable code.

• Inefficiency: The implementations of most commercially available components libraries typically involve complex class hierarchies with extensive use of inheritance and virtual functions. As a result, using these components results in significantly less-efficient programs than could be written in C.

• Unwieldy interfaces: In most component libraries, all operations to be performed on a data structure are part of the interface of the class defining it. Besides making it difficult for programmers to add new operations without recompiling the code, this makes the interfaces needlessly large.

These problems have been widely recognized for many years, but few solutions have been proposed and none has been widely embraced - not, that is, until now. The Standard Template Library is both a remarkable advance in programming methodology and a fully accepted part of the C++ Standard Library. It does not seem overly optimistic to expect that STL components will become some of the most widely used software in existence. The reasons are fivefold:

• C++ is becoming one of the most widely used programming languages (which is 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.

Virtually all C++ programmers know that the origin of this language is due to 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 it is the case that 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 one of this book's authors (D.R.M.) 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). It was Alex who recognized the full potential for generic programming and persuaded his then-colleagues at General Electric Research and Development (including, primarily, D.R.M. 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, and by 1987 Alex and D.R.M. 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 of the defense industry, and C++ seemed like a better bet for both becoming widely used and providing good support for generic programming, even though the language was relatively immature (it did not even have templates, which were 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 importantly to develop an overall architecture 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++. D.R.M. collaborated in this research, and in 1992 Meng Lee joined Alex's project at HP and became a major contributor.

This work likely would have continued for some time just as 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 Koenig 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 D.R.M. 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. Dobbs Journal.)

Subsequently, the Stepanov and Lee document (Ref. 10) has been incorporated almost intact into the ANSI/ISO C++ draft standard (Ref. 1, parts of clauses 17 through 27). It also has influenced other parts of the C++ Standard Library, such as the string facilities, and some of the previously adopted standards in those areas have been 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 this book's authors (A.S.) 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 D.R.M. during the standardization process, is the basis of Modena's STL++ product and several other vendors' offerings; it is referred to in this book as the "HP reference implementation."

The Stepanov and Lee document, while precise and complete, was aimed more at the committee than at the wide audience of C++ programmers. Along with modifying the HP reference implementation to work well with several compilers and providing several additional classes, Modena developed the STL++ Manual, the first comprehensive user-level documentation of STL. (D.R.M. served as an advisor to Modena and was the principal author of the Tutorial section of the STL++ Manual.) We recognized, though, 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. With much encouragement and assistance from our editor, Mike Hendrickson, we have attempted to meet this goal with the present book.

With the publication of this book, Modena and Addison-Wesley are also making available on the Internet all of the source code for examples used in this book, so that readers who want to try them do not have to type them. Instructions for finding and retrieving all of this material can be found in Appendix B.

We do not want to give the impression that we believe STL is the solution to all programming problems. There are potentially still some bumps in the road to its acceptance by the broad programming community, such as compiler weaknesses and the usual opportunities for misunderstanding of a radically new approach. We hope this book will make the road for STL itself as smooth as possible, but of course there are still many fundamental data structures and algorithms that are not covered. Beyond this realm, there are many more specialized areas of computation that also cry out for component standardization. References 3 and 7 discuss the larger view in some detail. We hope that among our readers will be some who have the vision and resources to continue in the direction that STL has opened up, carrying on its ideas to other component libraries, not only in C++ but also in other programming languages.

Although in the larger scheme of things it is just a small step toward realizing McIlroy's original vision (Ref. 6), STL is a remarkable achievement and has the potential for revolutionizing the way a large number of people program. We hope this book helps you become a full participant in that revolution.

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.

D.R.M.
Troy, NY

A.S.
Los Gatos, CA

October 1995

0201633981P04062001



Updates

Errata

Click below for Errata related to this title:
Errata

Submit Errata

