Book Reviews

Generic Programming and the STL

reviewed by Chuck Allison

When STL [1] came upon the C++ scene in late 1993 it didn't take the programming community long to see what a powerful tool it was. It was important enough to hold up completion of the C++ Standard for another two and a half years so it could play a major role in the Standard library. ObjectSpace, one of the first vendors to implement STL, ported it to Java lickety-split and named it JGL (which stands for ‘‘Generic Library for Java,'' believe it or not). C++ programmers started using vectors, maps, sets, and their iterators at every opportunity.

It is very likely that many people can just use STL ‘‘out of the box'' and will never need to be concerned about how it functions internally. But if the containers, iterators, and algorithms in the Standard C++ library don't quite do what you need, you may have to dig a little deeper into how they work. At the very least you may have to write your own function objects in such a way that they can interact with some of the standard function object adaptors. Or you may need to define your own type of container. And if you want it to operate with the rest of the STL framework, you'll need to define an iterator type to go with it and maybe even an allocator type. These are not tasks for the casual developer, but should you find yourself there, have I got a book for you!

Generic Programming and the STL is in this writer's opinion the most complete and most valuable STL book available. Matt Austern does a masterful job of presenting the concepts of STL and illustrating how to make the most of them in solving your programming challenges. Of course, few people are as qualified as he is to write such a book in the first place. I first met Matt at a meeting of the C++ standards committee, where he has represented Silicon Graphics for some time now. He was instrumental in completing the design of STL, is also an implementer of SGI's version of STL, and wrote their online documentation for the product. Through his association with Alex Stepanov, who also works at SGI, Matt is privy to the vision of STL that has brought it to its useful state. And Matt is above all a clear communicator. He treats the subject with rigor and completeness, yet without any superfluous clutter.

The very first sentence in the preface says a lot: ‘‘This is not a book about object-oriented programming.'' Indeed, but it is a landmark book on generic programming. In section 2.4 Matt explains very well how the refinement of concepts [2] so prevalent in STL is both similar to and different from inheritance, and why inheritance won't quite work in modeling such refinements.

It is well known that learning often proceeds in levels. After you master a subject to certain degree, you can then go on to a deeper level. It is important to gain some breadth at each level before you progress, however. Matt has structured this book with such a tiered approach; the three parts represent different levels of mastery. In Part I, Introduction to Generic Programming, he begins with a four-page teaser that motivates the utility of STL. He then gives introductory but rich illustrations of algorithms, ranges, iterators and their traits, function objects and adaptors, and containers, along with some advice for those who want to implement their own versions of the same. Gee, that's just about everything! But at this point you've really just had a taste of what STL is all about.

In Part II, STL Concepts, he explains the concepts behind STL. A concept here means a set of requirements, a behavior, if you will, that a library component must fulfill. For example, containers and their elements must be Assignable, Default Constructible, and Equality Comparable. The concepts of LessThan Comparable and Strict Weakly Comparable accommodate containers ordered by key values. This section is somewhat academic in flavor, but reflects the rigor that is essential to STL.

Part III, Algorithms and Classes, gives the specifications of the library elements that implement the concepts presented in Part II. Each class and generic algorithm appears with all the information you could possibly expect, including examples. Once you're comfortable with how STL works, you can use Part III as a handy reference manual while constructing applications.

If there is a down side to the book, it's that it is a little ‘‘too complete.'' It covers some features of SGI's STL that are not part of the official Standard C++ library (e.g., the hash-based containers). Unfortunately there is no easy way to tell when you encounter such a feature; you just have to know. (Of course, your compiler will help you.) Also, as I've already mentioned, the tone and exposition is academic to the point of being a little too dry for the novice; but if you want completeness, rigor, and accuracy, this book is a ‘‘must read.'' o

Notes

[1] STL stands for the Standard Template Library, of course, the brainchild of Alex Stepanov and Meng Lee, which they first presented to the C++ standards committee in November 1993. It has since been refined and added to the Standard C++ library. I think it is unfortunate that we still use the term ‘‘STL,'' since its features are now integrated into the full C++ library, but its initial popularity made the moniker stick. I find that some people mistakenly speak of the standard string classes as being ‘‘STL strings,'' or that other people wonder why other library classes, such as valarray and bitset, behave differently than the other generic containers. What was once called STL is only part of the larger C++ library; developers would do well to learn the entire library, and drop the term ‘‘STL,'' which has outlived its usefulness as an acronym.

[2] For example, a Random Access Iterator is a refinement of an Input Iterator, because it can do all of what the latter can and more. Likewise, a ForwardIterator is a refinement of both an Input Iterator and an Output Iterator. If inheritance were used to model these concepts, then you couldn't pass a pointer to an algorithm that uses iterators (because built-in types like pointers aren't instances of a suitable class).

Chuck Allison is a Senior Technical Advisor at Ingenix, a leading healthcare information company. He has been a contributing member of J16, the C++ standards committee, since 1991, and designed the Standard library's bitset class template. His book, C & C++ Code Capsules (Prentice-Hall, 1998), is filled with practical, ISO-compliant code. He is currently the Java columnist and consulting editor for the C/C++ Users Journal. Contact Chuck at cda@freshsources.com.