Introduction

Nothing beats reading a good book for learning a new technology, such as C++'s Standard Template Library (STL). I've read two good books on STL recently, and they both have their selling points. Hopefully, you can afford to get both; but if you can't, this comparative review may help you decide between the two.

Nelson's Book

This book covers the philosophy, use, and intimate details of Hewlett-Packard's (HP) STL implementation. This is a large book, and as with any other large book, one of the first questions I ask is, "Does it really need to be that big?" In this case, I say "Yes." The reason is that, in my view, Nelson's book is really three distinct, complete, and mutually complementary books in one. The first part is actually a long essay (80 pages) which gives an overview of STL. The second is a standard tutorial/reference combination. The third part reproduces the HP STL Specification. In light of STL's almost experimental nature, this last part is closer to being a necessity than just a nice touch. Below, I review each of the three "sub-books" separately.

The book devotes much space to exploring the inner workings of STL, so you really need a good foundation in C/C++ to make sense of it easily. Beginners may still want to read this book, though, for three reasons: 1. STL tutorials are still scarce; 2. Beginners can ignore these explorations and still learn the essentials of STL with this book; and 3. Any beginners reading this magazine and interested in STL have a good chance of advancing beyond the beginner stage, so the book will eventually become more useful to them.

Book 1: An STL Overview

The first "book" presents an overview of STL, including its history and philosophy.

Instead of providing the usual quick recap of well-known history, Nelson first thoroughly examines the history that led up to the creation of STL. He starts by discussing the limited genericity possible in C, works his way through C++'s evolving feature set, and ends up at C++'s recent features that make a truly generic and fast library like STL possible.

He then discusses templates. If you already understand C++ templates, you can safely skip this part. For those who can't skip it, rest assured that it's a top-notch discussion of templates as they apply to STL.

Finally, Nelson gives a nickel tour of STL itself, touching on all of STL's major features.

This first book can stand alone to serve as an "STL tasting booth" for those who still haven't decided that STL is something worth learning. If you already know you want to learn STL, this part makes a nice preview for the rest of the book.

Book 2: The STL Tutorial and Reference

The second section is what we might have expected the entire book to be: first a tutorial, then a well-written reference to STL. Indeed, some STL works dedicate the whole book to tutorial and reference. But this second "sub-book" is actually a cut above the rest of the pack. I discuss the tutorial and reference parts in turn.

The tutorial starts with the major sequential container classes: vector, deque, and list, as well as the container adaptors that can make a sequential container look like a stack, queue, or priority queue.

An average book would simply have shown how to use the containers by way of a few examples. What makes this a great book is that after it shows you how to use the container, it shows how HP's STL version really works. Nelson illustrates his explanations with snippets from the HP STL source code as well as clear diagrams.

One of the great things about STL is that it implements each major container in a different way, so that each has its unique performance properties. Accordingly, the next two chapters unveil the very different inner workings of the deque and list containers.

With this detailed treatment the reader can appreciate the underlying mechanisms, which is helpful in making design decisions. It's certainly nice to know that deques perform well when adding elements to both ends, while vectors are only quick for tail insertions. But knowing why these things are so gives you a sure feeling when making design decisions. Nelson puts the topping on this sundae of sequential container information by pitting all three containers against one another. This "showdown" of containers demonstrates the space and time tradeoffs clearly.

The next chapter briefly covers STL's container adaptors. Adaptors give a container an interface more appropriate to the task at hand. One common use is turning a vector into a stack, for example.

The next chapter covers STL's four associative containers. As in previous chapters, Nelson covers the implementation underlying the containers, which in this case is a red-black tree. While the explanation is useful, I wonder if the book wouldn't be improved by covering the interface and use of the red-black tree class itself. It seems to me that users may find themselves wanting to derive their own classes from STL's version instead of writing their own.

The next two chapters in the second section cover allocators and iterators, which provide uniform memory management and access to the containers. These chapters cover the subject well, but I can't say it's one that is all that exciting to me. These chapters aren't boring, but aside from being as complete as the rest of the book, they aren't otherwise noteworthy. Maybe those wanting to do things like database and special memory access through custom allocators and iterators will find this chapter more indispensable.

The next chapter gives a very brief overview of STL's algorithms. It basically just tells you what's available so you can find more information in the reference section. Last but not least, Nelson discusses function objects. These clever object-oriented replacements for function pointers are key to many portions of STL.

The final chapters of the second section are a reference for STL, and as far as I've been able to tell, cover everything in HP STL. In addition to expanding upon the tutorial's topics, the reference covers sorting and searching, as well as set, heap, sequence, basic numeric, and miscellaneous operations.

Book 3: The STL Specification

This final "book" is a reprint of the original HP STL specification. This section is also quite valuable; it gives you an "STL bible" to refer to when your questions and problems outstrip the rest of the book's scope.

Criticisms and Kudos

Although I really like the book, I should point out a few of the book's faults and tradeoffs. The first tradeoff to keep in mind is that (probably due to timing issues) the book covers HP STL, which the pages of this magazine have shown to be very different from the emerging draft Standard STL. A serious fault is that the text rarely refers to the STL header files, so it's harder than it should be to find out which headers to include to get particular STL facilities.

The book more than makes up for these problems, however, with some really nice touches that make it truly great. For example, Nelson lists what each of the containers require of their contained objects. Documentation of this sort is dear to me, as I've frequently been forced to do without it.

As another nice touch, Nelson hints at many possibilities for extending STL through objects such as custom iterators and allocators that use something other than the heap for storage. If you wonder what this non-heap storage might be, Nelson provides some examples: database access and "special" memory access like MS-DOS's EMS memory.

Nelson minimizes the book's bulk through a form of reuse: he uses a single code example to illustrate a series of points in turn.

Finally, the chapter on associative containers attempts to shed some light on why STL's creators chose to implement associative containers as red-black trees instead of hash-based structures. His argument may not end the debate, but he does illuminate the issues well.

Other Considerations

As its back cover indicates, the book focuses on PC compilers, but readers should find it easy to identify and compensate for its few minor platform dependencies. For example, the code samples each have a commented #define at the top to make them compile with Borland C++ 4.x. These are easily removed. Another PCism: when the book displays pointers, they are clearly of the 16-bit, "short" variety. Beyond these sorts of things, I believe the code should be portable to any STL-compatible compiler (with the caveat that the diskette is MS-DOS-formatted.)

Musser and Saini's Book

As I hinted in the previous review, I expect a book of this kind to consist of two main parts, a tutorial in the basic-to-intermediate material first, and a complete reference second. Musser and Saini follow this well-established formula.

As you might expect from its (hard) cover, this book takes a more formal approach than Nelson's. It's certainly not from the ivory tower, but this book has the standard properties of a formal work: no light conversational humor in headings and text, lots of Big-O notation, and platform independent discussions. If it had a lighter writing style, it might be easier to read, but more formal writing has its advantages, too. For example, it's easier to skim the book by glancing at headings, because you don't have to mentally translate their meanings.

The book does not attempt to teach the use of templates, so readers will need to know how to use others' templates before tackling this book.

A note on accuracy: authors are only human, so they make mistakes. Addison-Wesley recognizes this and thus makes its errata sheets easily available. The errata sheet for this book is available on the Web at http://www.cs.rpi.edu/~musser/stl-book-errata.html.

The Tutorial

Musser and Saini get right to their subject. Unlike Nelson, they don't try to "sell" you on STL first; if you bought the book, they assume that you really do want to learn STL. They also don't bother recounting the converging histories of STL and C++. I give Musser and Saini points for a better overview of STL, though -- they provide less trivial examples and more of them.

The tutorial is one place where the book's theoretical outlook becomes obvious: the first tutorial chapter is on iterators, the glue that binds everything else together. Notwithstanding my lack of excitement about iterators (see previous review) I think this may be a better strategy than Nelson's. Without a good understanding of iterators, fitting STL algorithms and containers together can be quite frustrating.

The next chapter is on STL's algorithms. It might seem more prudent to cover containers next -- after all, how can you use algorithms without containers? But you can illustrate a lot of algorithms with simple vectors, which is what the authors do. Also, the basics of vectors were covered in the introductory material. The chapter actually covers all of STL's algorithms well, and with each algorithm (or group of closely related algorithms) it includes a well-chosen example program as illustration.

Next come STL's sequential containers, all in one chapter. This arrangement makes sense because the three sequential containers belong to a "family of abstractions," which lets the authors describe only once a feature common to all of the containers. The next chapter covers associative containers in much the same manner.

The next four chapters quickly cover function objects and the various adaptor types. It is interesting to note that this book considers the adaptors separately from the facilities they adapt, whereas Nelson deals with them side-by-side.

The Example Programs

Again, Musser and Saini outdo Nelson in the examples category: each of the next four chapters is built around a largish example (as compared to the rest of the text's examples) that solves a problem by using STL. We usually like to read an example that does a lot for its size, and the authors succeed handily in creating such an example here. All of the programs are also based on a common theme, working with anagrams; as a result, they all hang together well, and between programs improvements follow a natural progression.

The next chapter focuses on defining an iterator class. This is a nice, mildly evangelistic touch on the authors' part -- evangelistic because they're (naturally) trying to prove the extensibility of STL.

They then take a quick step out of the classroom and into the "real world." Here the authors discuss some of the how-to issues that come up when trying to get STL to do some nonobvious things. One of the examples show how to reduce the template code bloat problem with a novel application of polymorphism.

The Reference

The book's reference section is, like the rest of the book, quite "standard." It is divided into chapters roughly parallel to the tutorial's, and each subsection discusses the details of a particular facility. I didn't find it lacking in any way. One thing covered in this section that isn't covered in the tutorial are allocators. The reference provides enough information to let you write your own allocators if the necessity presents itself.

Criticisms and Kudos, Part 2

I do have a criticism of the book. I'm really unimpressed with the illustrations in this book. They're not inaccurate, but they just don't communicate their information as well as Nelson's do. Fortunately, I think this book doesn't need illustrations as much as Nelson's book does, so it doesn't suffer all that much. I still think that they could have been clearer, though.

Now here are some nice touches: though the rest of the book uses the HP reference implementation of STL in its examples, the introduction to the book does explain the header changes that the ISO C++ committee made. These particular changes will probably cause some headaches, and this feature should help alleviate the suffering.

The tutorial chapter on iterators offers a table of containers paired with the iterators they return. This makes matching up containers with compatible algorithms easier.

The chapter on associative containers doesn't spend much time arguing for red-black trees over hash tables, but the book does mention that there are STL-based hash containers available from the main STL site (ftp://butler.hpl.hp.com/stl), which was a nice revelation. The other sites mentioned in the same appendix are also worth a visit, and their inclusion is yet another nice touch.

Comparing the Two Books

These two books differ in philosophy, in a couple of fundamental ways. For one thing, Nelson's book tries to do more than Musser and Saini's does. Besides the reprint of the STL spec, the main extra Nelson offers is a running exploration into the workings and design of an implementation of STL. However, in doing so, he constrains the book somewhat to one implementation and one platform.

On the other hand, Nelson's coverage gives us an insight into STL that, once obtained, is hard to imagine doing without. This added insight gives the designer in all of us information to help us choose between similar STL facilities, as well as some good lessons in design. Plus, it's really easy to step past the dependencies if they get in your way. In all likelihood, future implementations of STL will look much like the HP reference implementation, and the PC dependencies are easy to spot and fix.

It all adds up to this: I think Nelson's book is a great introduction to the library, and that it provides an insight into some of the "Zen" of STL, which Musser and Saini's book does not. Also, Nelson's inclusion of the STL spec and a decent reference makes his book useful beyond the initial learning period.

Does that mean the other book is useless? No, not by any means. It's just different. For one thing, I think that Musser and Saini have done a better job of organizing their book. The organization of Nelson's book is okay, but I get the impression it wouldn't be as easy to use as a reference. By better organization I mean that it is easier to predict where to find coverage of a certain feature in Musser and Saini. In particular, Musser and Saini make a clear separation between the straight reference material and the tutorial material. Of course, Nelson's organization has its points as well: his reference section contains examples as well as the tutorial, which is nice when you're still learning how to use something and need both reference and example material at the same time.

I mentioned that Nelson's book covers a working implementation of STL. I personally consider this a plus, but perhaps not everyone will. If you don't have the time or inclination to understand the details of an STL implementation, you may be better off with Musser and Saini.

The Verdict

I think Nelson's book makes a better tutorial, and that Musser and Saini have the better reference.

If you're a non-PC user who can't stand PCisms, stay away from the Nelson book. If you're more interested in the theory of STL, start with Musser and Saini's book.

I'd really hate to choose between the two books. But if you must, I'd recommend doing what I did, if you can: learn with Nelson, and if you decide you need better reference or how-to material, get the Musser and Saini book.

Warren Young is a software engineer for Educational Technology Resources, Inc. He has been programming and playing with computers since the mid-80's. He has some web pages about programming (including STL) at http://www.cyberport.com/~tangent/programming. You can send him email at tangent@cyberport.com.