Dr. Dobb's Journal October 1999
In the continuing effort to reinvent myself every five years, I wanted to learn something that would yield the most bang for my mental buck. Since my capital is diminishing, I decided to pursue another level of abstraction. Rather than learning the class hierarchy of yet another RAD tool, I wanted a new way to think. And rather than another 10 tips and tricks, I wanted another viewpoint, something that would make programming easier.
Although I had used C++ on a few projects, I hadn't had much chance to study or use the Standard Template Library (STL) since the language was standardized. Now that many C++ compilers are starting to meet the standard, I decided to follow Bjarne Stroustrup's advice in the third edition of his book The C++ Programming Language (Addison-Wesley, 1997), and investigate the STL as a tool that might give me more leverage.
To explain the advantages of the STL, I paraphrase David Musser, coauthor of the STL Tutorial And Reference Guide:
That's the executive summary of these pointssmall and easy, robust, and fast. This was exactly what I was looking for. Now, on to the books, which I present in chronological publishing order.
C++ Programmer's Guide to the Standard Template Library, by Mark Nelson, is one of the first books about the STL. As such, it was all we had at the time. Because the STL was so new, the opening chapters sell the use of STL as an improvement over hand-coded C. If you need convincing, these chapters are worth a quick read.
However, the rest of the book looks like it was rushed into print by the publisher, and is irritating to read. Several tables and figures are not referenced in the text, and some tables are printed in a font that makes them illegible.
Although it offers substantially more graphics than either of the other texts reviewed here, most of these are of the fundamental type, and document such things as set operations using Venn diagrams. I expect that most readers would find these superfluous. As a trade paperback, IDG's chapter and page layout makes the book larger than it needs to be, but this may come from trying to appeal to a wide audience and grab additional shelf space. I find the layout a little too cute: The chapter lead quotations are irrelevant, and subheads often provide no clue as to the contents of the following paragraphs.
It may be difficult to obtain a copy of the book, as the book is out of print. The legible and copious sample code, provided on the accompanying 3.5-inch diskette, is written to cope with the vagaries of Borland's C++ 4.x, a tool that has evolved by at least four versions. Using the code with today's compilers would therefore require some effort.
The authors of the original version of the STL are Alexander Stepanov and Meng Lee. David Musser, coauthor of STL Tutorial And Reference Guide: C++ Programming With The Standard Template Library is now working with Stepanov at Silicon Graphics, and has been working with generic programming about as long as Stepanov himselfabout 20 years. Seeing the promise in STL, Atul Saini released an early commercial version of the library as Modena's STL++ product.
The opening section of STL Tutorial And Reference Guide demonstrates the use of the STL with some simple example programs that are highly legible and understandable, even for C++ newbies. This is clean, nice looking code.
And speaking of examplesthere are lots of them and, no typos. This is the best quality editing I've seen in several years. All the examples use assertions for error checking, which is okay for academic presentations. If you plan to use the code in your own programs, though, be prepared to redesign it to use exceptions.
The text includes several cautions that compilers may be missing certain capabilities. These cautions are becoming less necessary, but are worth seeing, because they tell you how up-to-date your tools are.
The text presents several more lengthy applications worth coming back to for further study:
The incredible part is that all of these lengthy programs can be built in two pages of code! All of the code is available on the Web, and URLs are plentiful in the appendix, so an accompanying CD-ROM is not required.
C++ was standardized after the book was published. Musser and Saini, like Nelson, were aiming at a moving target. The header and function names of today's STL differ from the ones shown in their text. Therefore, it would require some effort to make use of the example code.
Alex Stepanov encouraged Matthew Austern, who also works at Silicon Graphics, to transform the SGI web pages documenting the STL into a book. I'm glad the persuasion succeeded: Generic Programming and the STL: Using and Extending the C++ Standard Template Library is the text from which I learned the STL. Austern has made explicit that which is implicit in other texts.
But since the HTML is available, and freely downloadable, why not just use it instead of buying a book? First, I don't learn well from hypertext; I prefer linear explication. Second, I like to read in places far away from my machines, and a book is still the most portable device. With the balmy Virginia weather we've been having lately, I'd rather retreat to the shade of a tree and pencil in marginalia. Finally, the most important part of the text (Part 1) is not included in the HTML documentation.
The book doesn't come with an accompanying CD-ROM or disk. If you decide to use the SGI version of the STL, you'll want to download both the STL and its documentation from the SGI web site (http://www.sgi.com/Technology/STL/) anyway, and use the HTML as help files (expect to spend about 15 minutes at 56K).
The text is divided into three parts, with an appendix.
Part 1 is the most useful part for learning the STL, as Austern presents "Concepts, Requirements, and Models." Models are what show up in programs. Concepts and requirements don't appear in C++; they are the invisible part of the library. But with Austern's text explaining them, it's like having the authors of the library leaning over your shoulder and saying, "When we wrote this part of the code, this is what we were thinking." Given Austern's 80-page explanation of concepts and requirements, the models are much easier to understand.
The simple graphics also help. Collect them, and you have a snapshot of STL on a single sheet of paper. And if you're new to C++, you need to read the explanation of asymmetric ranges in Chapter 2.
Part 2 is a formal documentation of the concepts presented in Part 1, and Part 3 documents the STL interface. The appendix addresses portability and standardization, which is still a necessary concern, because compilers are not equivalent.
Austern recommends that everyone read Part 1, and dip into Parts 2 and 3 when a particular item needs to be researched. I recommend browsing the entire book. For example, one chapter I was tempted to skip was "Sorting And Searching." But it mentions Musser's new Introspective sort, an unstable algorithm that is worst case O(N Log N) as opposed to Quicksort, which is worst case O(N2). This once again points to the obvious advantages of using a library like the STL. Although there's not much chance that I will add a faster sort to the library, some genius will. My programs can be improved by merely recompiling against the latest version of the library.
Austern's book, as is the case with the others reviewed here, is not readable in the "Great American Novel" sense. There's a lot of repetition, but this is desirable in a text that will act as a reference. On the other hand, there are a lot of typos. Austern's web site lists those found in the first and second printings, and it'll take about 30-40 minutes to fix them. Even so, after making the listed corrections, I found a few more typos and forwarded them to the e-mail address on Austern's web site. An autoresponder replied: "I am on my honeymoon, and I will be out of the country..." Congratulations Matt!
DDJ