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

Overview

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

See more details below
Available through our Marketplace sellers.
Other sellers (Hardcover)
  • All (26) from $1.99   
  • New (2) from $34.36   
  • Used (24) from $1.99   
Close
Sort by
Page 1 of 1
Showing All
Note: Marketplace items are not eligible for any BN.com coupons and promotions
$34.36
Seller since 2008

Feedback rating:

(174)

Condition:

New — never opened or used in original packaging.

Like New — packaging may have been opened. A "Like New" item is suitable to give as a gift.

Very Good — may have minor signs of wear on packaging but item works perfectly and has no damage.

Good — item is in good condition but packaging may have signs of shelf wear/aging or torn packaging. All specific defects should be noted in the Comments section associated with each item.

Acceptable — item is in working order but may show signs of wear such as scratches or torn packaging. All specific defects should be noted in the Comments section associated with each item.

Used — An item that has been opened and may show signs of wear. All specific defects should be noted in the Comments section associated with each item.

Refurbished — A used item that has been renewed or updated and verified to be in proper working condition. Not necessarily completed by the original manufacturer.

New
0201633981 BRAND NEW NEVER USED IN STOCK 125,000+ HAPPY CUSTOMERS SHIP EVERY DAY WITH FREE TRACKING NUMBER

Ships from: fallbrook, CA

Usually ships in 1-2 business days

  • Standard, 48 States
  • Standard (AK, HI)
$45.00
Seller since 2015

Feedback rating:

(215)

Condition: New
Brand new.

Ships from: acton, MA

Usually ships in 1-2 business days

  • Standard, 48 States
  • Standard (AK, HI)
Page 1 of 1
Showing All
Close
Sort by
Sending request ...

Overview

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

As part of the C++ standard, STL provides programmers with a catalog of reusable software components plus the rules that govern how to use them. This guide is the sole source for comprehensive tutorial and reference material on this new technology. Co-authored by one of the chief developers of the standard, this book teaches you everything you need to know about using STL effectively.

Read More Show Less

Editorial Reviews

Booknews
The Standard Template Library was created as the first library of genetic algorithms and data structures, with four ideas in mind: generic programming, abstractness without loss of efficiency, the Von Neumann computation model, and value semantics. This guide provides a tutorial, a description of each element of the library, and sample applications. The expanded second edition includes new code examples and demonstrations of the use of STL in real-world C++ software development; it reflects changes made to STL for the final ANSI/ISO C++ language standard. Annotation c. Book News, Inc., Portland, OR booknews.com
Read More Show Less

Product Details

  • ISBN-13: 9780201633986
  • Publisher: Addison Wesley Professional
  • Publication date: 12/15/1995
  • Series: Professional Computing Series
  • Edition description: Older Edition
  • Pages: 400
  • Product dimensions: 7.58 (w) x 9.51 (h) x 1.31 (d)

Meet the Author

David R. Musser, currently of Rensselaer Polytechnic Institute, has been involved with STL almost from its inception. Collaborating with its creator, Alexander Stepanov, he helped develop the first implementation and contributed to STL's inclusion in the ANSI/ISO C++ standard.
Read More Show Less

Read an Excerpt

Chapter 2: Overview of STL Components

STL contains six major kinds of components: containers, generic algorithms, iterators, function objects, adaptors, and allocators. In this chapter we will cover just the highlights of each kind of component, saving the details for later chapters.

2.1 Containers

In STL, containers are objects that store collections of other objects. There are two categories of STL container types: sequence containers and sorted associative containers.

2.1.1 Sequence Containers

Sequence containers organize a collection of objects, all of the same type T, into a strictly linear arrangement. The STL sequence container types are as follows:
  • vector<T> Provides random access to a sequence of varying length (random access means that the time to reach the ith element of the sequence is constant; that is, the time doesn’t depend on i), with amortized constant time insertions and deletions at the end.
  • deque<T> Also provides random access to a sequence of varying length, with amortized constant time insertions and deletions at both the beginning and the end.
  • list<T> Provides only linear time access to a sequence of varying length (O(N), where N is the current length), but with constant time insertions and deletions at any given position in the sequence.
Before discussing these sequence container types, we note that in many respects an ordinary C++ array type T a[N] can be used as a sequence container, because all STL generic algorithms are designed to work with arrays in the same way they work with other sequence types. And another important type, the library-provided string type (from header <string>), represents sequences of characters in a way that fits together well with STL algorithms and conventions. For example, STL provides a generic algorithm called reverse that can reverse many kinds of sequences, including string objects and arrays. Here is an example of its use on both a string and a character array.

Example 2.1: Using the STL generic reverse algorithm with a string and an array

"ex02-01.cpp" 20
‚ #include <iostream>
#include <string>
#include <cassert>
#include <algorithm> // For reverse algorithm
using namespace std;
int main()
{
cout << "Using reverse algorithm with a string" << endl;
string string1 = "mark twain";
reverse(string1.begin(), string1.end());
assert (string1 == "niawt kram");
cout << " --- Ok." << endl;
cout << "Using reverse algorithm with an array" << endl;
char array1[] = "mark twain";
int N1 = strlen(array1);
reverse(&array1[0], &array1[N1]);
assert (string(array1) == "niawt kram");
cout << " --- Ok." << endl;
return 0;
}

The arguments to the first call of reverse, namely string1.begin() and string1.end(), are calls to member functions begin and end defined by the string class. These member functions return iterators, which are pointer- like objects, referring to the beginning and end of string1. The reverse function reverses the order of the characters in the range specified by these iterators in place (i.e., the result replaces the original contents of string1). The assert macro call that follows is a simple check that the result in string1 is indeed the reverse of the original string. (The sidebar “The Assert Macro” contains more discussion of this and other uses of assert.)


The Assert Macro.

In Example 2.1, we check the results of calling reverse by using the assert macro from the cassert header (which corresponds to the C header assert.h). This macro takes a Boolean-valued expression as its single argument and does nothing if that expression evaluates to true, but it prints an informative message and terminates the program if the expression evaluates to false. In the first use of assert, the argument is string1 == "niawt kram", in which the == operator defined on string is used to compare two string objects character by character. One string involved in the comparison is string1 and the second is the result of a compiler-inserted call of the string constructor that takes "niawt kram" and constructs a string object.

In the second assert call the argument is string(array1) == "niawt kram", in which we use the aforementioned string constructor on the character array array1 so that the string == operator is used. Note that if we had written array1 == "niawt kram", the == operator would have had the wrong meaning. (It would check equality of pointers, not the string values to which they point.)

In many of the example programs in Part I we use the assert macro in a similar way to show the results we expect from algorithm or data structure operations.


In the second call of reverse we pass pointers to the beginning and end of the character array array1. Note that &array1[N1] is actually the address of the location one position past where the last character is stored. The convention with every STL algorithm is that whenever two iterators first and last are passed to the algorithm, they are expected to define the location at which to start traversing a sequence (first) and a location at which to stop traversing (last)—without attempting to process the element at which last points....
Read More Show Less

Table of Contents

Foreword xxi
Foreword to the First Edition xxix
Preface xxxi
I Tutorial Introduction to STL 1
1 Introduction 3
1.1 Who Should Read This Book 4
1.2 What Generic Programming Is and Why It's Important 4
1.3 How C++ Templates Enable Generic Programming 7
1.4 The "Code Bloat" Problem with Templates 15
1.5 Understanding STL's Performance Guarantees 15
2 Overview of STL Components 19
2.1 Containers 19
2.2 Generic Algorithms 26
2.3 Iterators 33
2.4 Function Objects 36
2.5 Adaptors 40
2.6 Allocators 43
3 How STL Differs from Other Libraries 45
3.1 Extensibility 46
3.2 Component Interchangeability 46
3.3 Algorithm/Container Compatibility 48
4 Iterators 49
4.1 Input Iterators 50
4.2 Output Iterators 52
4.3 Forward Iterators 54
4.4 Bidirectional Iterators 55
4.5 Random Access Iterators 56
4.6 The STL Iterator Hierarchy: Combining Algorithms and Containers Efficiently 58
4.7 Insert Iterators 59
4.8 Revisiting Input and Output: Stream Iterators 62
4.9 Specification of Iterator Categories Required by STL Algorithms 64
4.10 Designing Generic Algorithms 65
4.11 Why Some Algorithms Require More Powerful Iterators 67
4.12 Choosing the Right Algorithm 68
4.13 Constant Versus Mutable Iterator Types 68
4.14 Iterator Categories Provided by STL Containers 71
5 Generic Algorithms 73
5.1 Basic Algorithm Organization in STL 73
5.2 Nonmutating Sequence Algorithms 77
5.3 Mutating Sequence Algorithms 87
5.4 Sorting-Related Algorithms 102
5.5 Generalized Numeric Algorithms 122
6 Sequence Containers 127
6.1 Vectors 129
6.2 Deques 148
6.3 Lists 152
7 Sorted Associative Containers 161
7.1 Sets and Multisets 162
7.2 Maps and Multimaps 174
8 Function Objects 183
8.1 Passing Functions via Function Pointers 184
8.2 Advantages of Specifying Function Objects with Template Parameters 186
8.3 STL-Provided Function Objects 191
9 Container Adaptors 193
9.1 Stack Container Adaptor 194
9.2 Queue Container Adaptor 196
9.3 Priority Queue Container Adaptor 198
10 Iterator Adaptors 201
11 Function Adaptors 205
11.1 Binders 205
11.2 Negators 206
11.3 Adaptors for Pointers to Functions 208
II Putting It Together: Example Programs 213
12 Program for Searching a Dictionary 215
12.1 Finding Anagrams of a Given Word 215
12.2 Interacting with the Standard String and I/O Streams Classes 218
12.3 Generating Permutations and Searching the Dictionary 220
12.4 Complete Program 221
12.5 How Fast Is It? 223
13 Program for Finding All Anagram Groups 225
13.1 Finding Anagram Groups 225
13.2 Defining a Data Structure to Work with STL 226
13.3 Creating Function Objects for Comparisons 227
13.4 Complete Anagram Group Finding Program 228
13.5 Reading the Dictionary into a Vector of PS Objects 229
13.6 Using a Comparison Object to Sort Word Pairs 230
13.7 Using an Equality Predicate Object to Search for Adjacent Equal Elements 230
13.8 Using a Function Adaptor to Obtain a Predicate Object 231
13.9 Copying the Anagram Group to the Output Stream 232
13.10 Output of the Anagram Program 232
14 Better Anagram Program: Using the List and Map Containers 235
14.1 Data Structure Holding Iterator Pairs 235
14.2 Storing Information in a Map of Lists 236
14.3 Outputting the Anagram Groups in Order of Size 237
14.4 Better Anagram Program 238
14.5 Output of the Program 239
14.6 Why Use a Map Container? 240
15 Faster Anagram Program: Using Multimaps 243
15.1 Finding Anagram Groups, Version 3 243
15.2 Declaration of the Multimap 246
15.3 Reading the Dictionary into the Multimap 247
15.4 Finding the Anagram Groups in the Multimap 247
15.5 Outputting the Anagram Groups in Order of Size 249
15.6 Output of the Program 249
15.7 How Fast Is It? 250
16 Defining an Iterator Class 251
16.1 New Kind of Iterator: Counting Iterator 251
16.2 Counting Iterator Class 253
17 Combining STL with Object-Oriented Programming 259
17.1 Using Inheritance and Virtual Functions 260
17.2 Avoiding "Code Bloat" from Container Instances 265
18 Program for Displaying Theoretical Computer Science Genealogy 267
18.1 Sorting Students by Date 267
18.2 Associating Students with Advisors 268
18.3 Finding the Roots of the Tree 270
18.4 Reading the File 273
18.5 Printing the Results 275
18.6 Complete "Genealogy" Program 276
19 Class for Timing Generic Algorithms 279
19.1 Obstacles to Accurate Timing of Algorithms 279
19.2 Overcoming the Obstacles 280
19.3 Refining the Approach 283
19.4 Automated Analysis with a Timer Class 284
19.5 Timing the STL Sort Algorithms 289
III STL Reference Guide 293
20 Iterator Reference Guide 295
20.1 Input Iterator Requirements 296
20.2 Output Iterator Requirements 298
20.3 Forward Iterator Requirements 299
20.4 Bidirectional Iterator Requirements 299
20.5 Random Access Iterator Requirements 300
20.6 Iterator Traits 301
20.7 Iterator Operations 304
20.8 Istream Iterators 304
20.9 Ostream Iterators 307
20.10 Reverse Iterators 309
20.11 Back Insert Iterators 313
20.12 Front Insert Iterators 315
20.13 Insert Iterators 316
21 Container Reference Guide 319
21.1 Requirements 319
21.2 Organization of the Container Class Descriptions 330
21.3 Vector 331
21.4 Deque 339
21.5 List 345
21.6 Set 354
21.7 Multiset 360
21.8 Map 365
21.9 Multimap 373
21.10 Stack Container Adaptor 378
21.11 Queue Container Adaptor 380
21.12 Priority Queue Container Adaptor 383
22 Generic Algorithm Reference Guide 387
22.1 Organization of the Algorithm Descriptions 387
22.2 Nonmutating Sequence Algorithm Overview 389
22.3 For Each 390
22.4 Find 391
22.5 Find First 391
22.6 Adjacent Find 392
22.7 Count 393
22.8 Mismatch 394
22.9 Equal 395
22.10 Search 396
22.11 Search N 397
22.12 Find End 397
22.13 Mutating Sequence Algorithm Overview 398
22.14 Copy 399
22.15 Swap 400
22.16 Transform 401
22.17 Replace 402
22.18 Fill 403
22.19 Generate 404
22.20 Remove 404
22.21 Unique 406
22.22 Reverse 407
22.23 Rotate 408
22.24 Random Shuffle 408
22.25 Partition 409
22.26 Sorting-Related Algorithms Overview 410
22.27 Sort 412
22.28 Nth Element 414
22.29 Binary Search 415
22.30 Merge 417
22.31 Set Operations on Sorted Structures 418
22.32 Heap Operations 421
22.33 Min and Max 423
22.34 Lexicographical Comparison 424
22.35 Permutation Generators 425
22.36 Generalized Numeric Algorithms Overview 426
22.37 Accumulate 427
22.38 Inner Product 428
22.39 Partial Sum 429
22.40 Adjacent Difference 430
23 Function Object and Function Adaptor Reference Guide 431
23.1 Requirements 431
23.2 Base Classes 432
23.3 Arithmetic Operations 433
23.4 Comparison Operations 433
23.5 Logical Operations 434
23.6 Negator Adaptors 435
23.7 Binder Adaptors 435
23.8 Adaptors for Pointers to Functions 436
23.9 Adaptors for Pointers to Member Functions 437
24 Allocator Reference Guide 441
24.1 Introduction 441
24.2 Allocator Requirements 442
24.3 Default Allocator 445
24.4 Custom Allocators 448
25 Utilities Reference Guide 455
25.1 Introduction 455
25.2 Comparison Functions 455
25.3 Pairs 456
Appendix A STL Header Files 459
Appendix B String Reference Guide 461
B.1 String Classes 461
B.2 Character Traits 472
Appendix C STL Include Files Used in Example Programs 477
C.1 Files Used in Example 17.1 477
Appendix D STL Resources 483
D.1 Internet Addresses for SGI Reference Implementation of STL 483
D.2 World Wide Web Address for Source Code for Examples in this Book 483
D.3 STL-Compatible Compilers 484
D.4 Other Related STL and C++ Documents 484
D.5 Generic Programming and STL Discussion List 484
References 485
Index 489
Read More Show Less

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
Read More Show Less

Foreword

When Dave Musser asked me to write an extended foreword to the second edition of this book, I jumped on the opportunity. First, Dave is my closest professional friend; we have been collaborating for over 20 years, and without Dave there would be no STL. So honoring his request is by itself a privilege. It also gives me an opportunity to say a few words about what I had in mind while designing STL.

To use a tool, it is useful to understand not just the instructions for using it but also the principles that guided its designers. The main goal of this foreword is to present you with the principles behind STL. I'll conclude with some musings.

STL was designed with four fundamental ideas in mind:

• Generic programming
• Abstractness without loss of efficiency
• Von Neumann computational model
• Value semantics

Generic Programming.

Some of you might have heard that STL is an example of a programming technique called "generic programming." This is so. Some of you might have also heard that generic programming is a style of programming using C++ templates. This is not so. Generic programming has nothing to do with C++ or templates. Generic programming is a discipline that studies systematic organization of useful software components. Its objective is to develop a taxonomy of algorithms, data structures, memory allocation mechanisms, and other software artifacts in a way that allows the highest level of reuse, modularity, and usability.

To allow the greatest degree of reusability, one has to try to analyze all possible extensions. For example, when a famous computer scientist saw my version of Euclid's algorithm for finding the greatest common divisor of two quantities,

template <typename T> T gcd(T m, T n) {
while (n != 0) {
T t = m % n;
m = n;
n = t;
}
return m;
}

he objected that the algorithm is not correct since it returns -1 when called with 1 and -1 as its arguments, and therefore the common divisor returned is not the greatest. He suggested that I fix the problem by changing the last line to

return m < 0 ? -m : m;

Unfortunately, if you do this the algorithm will not work for many important extensions: polynomials, Gaussian integers, and so on. It would require the set of elements on which we operate to be totally ordered. The problem disappears if we use a more abstract (and algorithmically more meaningful) definition of greatest common divisor: a divisor that is divisible by any other divisor. That definition allows for nonunique solutions: in the case of integers both 6 and -6 are greatest common divisors of 24 and 30. This actually corresponds to what mathematicians have been doing for the last several hundred years.

The classification of software components should deal only with useful components. It would be ridiculous to introduce a concept of semisequence--a sequence that has multiple beginnings but only one end--since we do not know any data structures that look like that nor any algorithms that could operate on them.

After we organize things systematically, we can ensure the consistency of their interfaces. That is, interfaces to two components should be the same to the same degree that the behavior of the components is the same. That allows us to implement algorithms that work on multiple components--generic algorithms. It also makes it possible to use the library. If a programmer masters STL's vector, it is not going to be too hard to learn to use STL's list and even easier to learn to use deque. It is my belief that the interfaces that allow the greatest possible degree of abstract programming are also the interfaces that are easiest to learn. (This presupposes that a person is learning things from scratch. It is hard to convince a hardened Lisp programmer that comparing with the past-the-end iterator is a better way than testing for nil.)

In many respects the ideas of generic programming are very similar to the ideas of abstract algebra. Those of you who took a course dealing with groups, rings, and fields should be able to see where classification of iterators is coming from.1

As mathematics organizes theorems around different abstract theories, generic programming organizes algorithms around different abstract concepts. So the task of the library designer is to find all interesting algorithms, find the minimal requirements that allow these algorithms to work, and organize them around these requirements. In general requirements are described through a set of acceptable expressions and their semantics. For example, STL does not state that ++ on an iterator must be defined as a member function of a class. It just states that if i is an iterator and if it can be dereferenced, then ++i is a valid expression.

Abstractness Without Loss of Efficiency.

While mathematics often deals with objects that cannot be constructed at all or could be constructed only if given an arbitrarily long time, computer science makes efficiency an explicit concern. It is not enough to know that an operation can be done. It is important to know that it will be done reasonably fast. To assure that, STL does several things.

First, it makes complexity requirements a part of each interface. When concepts such as iterators are specified, certain complexity requirements are given. A programmer can be certain that doing ++ on an iterator does not depend dramatically on where in the sequence it is. Dereferencing should be equally fast--it is not legal to implement list iterators with a structure containing the pointer to the list's head and the integer index. (It should be noted that while the operational semantics of the operations can be specified rigorously by specifying the set of valid expressions and their semantics, the complexity is specified informally; a totally new insight is needed to find a way for specifying complexity requirements in a rigorous but practically useful way.)

Second, STL takes great care not to hide any part of a data structure that allows efficient access. Instead of providing get and put methods for operating on a container--the favorite method of textbook writers--the pointer to the value is exposed so that fields could be modified in place. One can write

i->second = 5;

instead of

pair<int, int> tmp = my_vector.get(i);
tmp.second = 5;
my_vector.put(i, tmp);

The fact that iterators to elements of a vector do not survive the periodic reallocations is noted, and it is assumed that STL users can learn to deal with it by either preallocating enough storage or storing indices and not iterators.

Great care was taken to see that all the generic algorithms in STL are state of the art and as efficient as hand-coded ones (being quite precise, that they are as efficient as hand-coded ones when a good optimizing compiler--such as Kuck and Associates' C++ compiler--is used).

Von Neumann Computational Model.

Although abstract mathematics uses simple numeric facts as its basis of abstraction--one should not forget that mathematics is an experimental science--what should we use as our basis of abstraction to come up with a generic abstract framework? It is my firm belief that the only solid basis is the architectures of< real computers. It is important to remember that modern computer architectures are a result of many years of evolution guided by the need to solve more and more diverse problems. Byte-addressable memory and pointers are not the artifacts we inherited from some archaic hardware designs--archaic hardware designs did not have bytes and there were no pointers; one wrote loops with the help of self-modifying code--but the results of architecture catching up with< the needs of applications.2 If we are interested in designing a generic framework for numerical types, it is important to understand the working of built-in numeric types, not just the mathematical theory of integers and real numbers.

The most important new concept in computer science that was not already present in mathematics is the concept of address. Making addresses, not just values, a part of our computational model was the revolutionary step that enabled all the progress from 72 addresses in the Mark I to millions of Internet addresses. In many respects, the most controversial part of STL is the fact that it makes addresses and their conceptual classification the cornerstone of the whole edifice. (This statement might appear strange to a practical programmer, but the academic community has spent decades trying to eliminate addresses altogether in doing what is called "functional programming.") In mathematical terms, the idea underlying STL is that different data structures correspond to different address algebras, different ways of connecting addresses together. A set of operations that move from one address in the data structure to the next corresponds to iterators. A set of operations that add and delete addresses to and from the data structure corresponds to containers.

While the STL classification of iterators (input, output, forward, bidirectional, random access) is sufficient for all the fundamental sequence algorithms, further categories of iterators need to be defined for STL to be properly extended to deal with multidimensional structures. (As a matter of fact, even for many fundamental sequence algorithms, two-dimensional iterators are needed to speed them up in cases of (1) nonuniform accesses as, for example, is the case with deque iterators or cache lines and (2) multiprocessor implementations.)

Value Semantics.

STL views containers as a generalization of structures. As the structure owns its components, so does a container own its components. When you copy structures, all their components are copied. When a structure is destroyed, all its components are destroyed. The same happens with containers. These properties are essential features that allow structures and containers to model the key attribute of real-life things--the relationship between whole and part. Of course, the whole-part relationship is not the only kind of relationship in the real world, and the rest of the relationships need to be modeled with iterators.3 It is my belief that the confusion between a part and a relation, which is so common in object-oriented languages and libraries, is a major source of conceptual confusion in the modeling of the real world as well as the main reason that they absolutely require garbage collection. STL is not object-oriented--not only in the way it uses global generic algorithms, but more significantly, in the fact that it separates the notions of having an object as a part and pointing to an object.
It assumes that

T a = b;

creates a copy of an object, with all parts being distinct, not just another pointer to the same object. Specifications of those algorithms in STL that use assignment (sort, partition, remove, and so on) require this value semantics. In the STL universe objects never share parts (unless, of course, one object is a part of the other).

In general, STL assumes that for any type on which it operates the semantics of copy constructors, destructors, assignment, and equality and their relations are the same as for built-in types. In addition, STL assumes that for those objects for which operators <, >, <=, and >= are defined, their semantics is the same as for built-in types, or, mathematically speaking, they define a total ordering. (One of the gripes I have against C++ is that C++ does not require the semantics of fundamental operations to be consistent with the semantics of built-in types; one can define an operator = to do multiplication. Operator overloading is good only if used in a highly disciplined way; otherwise, it can cause great harm.)

Musings.

STL was not designed to be a part of the C++ Standard Library. It was designed to be the first library of generic algorithms and data structures. It so happened that C++ was the only language in which I could implement such a library to my personal satisfaction. In the five years since STL has been widely available, many people have made claims that they can do STL-like things in their favorite language: Ada-95, ML, Dylan, Eiffel, Java, and so on. Maybe they can. As far as I can see, they have not. I wish they could. I wish someone would construct a language more suitable to generic programming than C++. After all, one gets by in C++ by the skin of one's teeth. Fundamental concepts of STL, things like iterators and containers, are not describable in C++ since STL depends on rigorous sets of requirements that do not have any linguistic representation in C++. (They are, of course, defined in the standard, but they are defined in English.)

The whole point of STL is that it is an extensible framework. While STL is widely used, my hopes for the creation of many libraries of generic components have not been fulfilled. As far as I can determine the reason that such libraries are not created is that there are no financial mechanisms for supporting the work. One cannot make money out of fundamental algorithms. They have to be designed for the entire industry by small teams of component craftsmen. While I have been lucky, on a couple of occasions, to receive funding from large computer companies to do STL work, it cannot be done in a serious way until some reliable way of funding the work is found. It is my hope that the U.S. government or alternatively the EU will fund a small but effective organization dedicated to producing generic software components. And I mean not research but actual production of well-organized, documented, generic, and efficient components. Please write to your elected representatives.

STL presupposes a very different way of teaching computer science. What 99 percent of programmers need to know is not how to build components but how to use them. STL presupposes a different way of running software organizations. People who write their own code, instead of using standard components, should be dealt with like people who propose designing nonstandard, proprietary CPUs. Can we ever move software into the industrial age? I wonder ...

Alexander Stepanov
January 2001


Footnotes


(1)
In general, I believe that mathematical culture is essential for a good software engineer. Sadly enough, nowadays one goes through college--and
through graduate school--without any exposure to real mathematics. I would urge all of you to keep reading mathematics throughout your career.
There are some remarkable books out there--I highly recommend the following three books by John Stillwell: Numbers and Geometry,
Mathematics and Its History, and Elements of Algebra; after you are done with them, consider Geometry: Euclid and Beyond by Robin
Hartshorne and Visual Complex Analysis by Tristan Needham.
(2)
It is very important for a good programmer to understand what really goes under the hood of a high-level programming language. It is important to know at least a couple of different architectures well. Since I recommended a bunch of mathematical books, let me also suggest a couple of computer books: John Hennessy and David Patterson's Computer Architecture: A Quantitative Approach is, in my opinion, the most important computer science book; one gets, however, a wonderful additional perspective if it is supplemented with Computer Architecture: Concepts and Evolution, by Gerrit Blaauw and Fred Brooks, especially the second part of the book, "The Computer Zoo," which covers some remarkable historical designs.
(3)
For example, while my leg is my part, my lawyer is not. If I am destroyed, my leg is destroyed; if I am copied, my leg is copied. My lawyer is another human being, and while my death might affect him in various ways--like a lot of pointers to a dead client, known as dangling pointers--he is not going to be automatically destroyed.

Read More Show Less

Customer Reviews

Be the first to write a review
( 0 )
Rating Distribution

5 Star

(0)

4 Star

(0)

3 Star

(0)

2 Star

(0)

1 Star

(0)

Your Rating:

Your Name: Create a Pen Name or

Barnes & Noble.com Review Rules

Our reader reviews allow you to share your comments on titles you liked, or didn't, with others. By submitting an online review, you are representing to Barnes & Noble.com that all information contained in your review is original and accurate in all respects, and that the submission of such content by you and the posting of such content by Barnes & Noble.com does not and will not violate the rights of any third party. Please follow the rules below to help ensure that your review can be posted.

Reviews by Our Customers Under the Age of 13

We highly value and respect everyone's opinion concerning the titles we offer. However, we cannot allow persons under the age of 13 to have accounts at BN.com or to post customer reviews. Please see our Terms of Use for more details.

What to exclude from your review:

Please do not write about reviews, commentary, or information posted on the product page. If you see any errors in the information on the product page, please send us an email.

Reviews should not contain any of the following:

  • - HTML tags, profanity, obscenities, vulgarities, or comments that defame anyone
  • - Time-sensitive information such as tour dates, signings, lectures, etc.
  • - Single-word reviews. Other people will read your review to discover why you liked or didn't like the title. Be descriptive.
  • - Comments focusing on the author or that may ruin the ending for others
  • - Phone numbers, addresses, URLs
  • - Pricing and availability information or alternative ordering information
  • - Advertisements or commercial solicitation

Reminder:

  • - By submitting a review, you grant to Barnes & Noble.com and its sublicensees the royalty-free, perpetual, irrevocable right and license to use the review in accordance with the Barnes & Noble.com Terms of Use.
  • - Barnes & Noble.com reserves the right not to post any review -- particularly those that do not follow the terms and conditions of these Rules. Barnes & Noble.com also reserves the right to remove any review at any time without notice.
  • - See Terms of Use for other conditions and disclaimers.
Search for Products You'd Like to Recommend

Recommend other products that relate to your review. Just search for them below and share!

Create a Pen Name

Your Pen Name is your unique identity on BN.com. It will appear on the reviews you write and other website activities. Your Pen Name cannot be edited, changed or deleted once submitted.

 
Your Pen Name can be any combination of alphanumeric characters (plus - and _), and must be at least two characters long.

Continue Anonymously

    If you find inappropriate content, please report it to Barnes & Noble
    Why is this product inappropriate?
    Comments (optional)