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.
