[ ERCB Home |
New |
Feature |
Brief |
DDJ |
Letters |
Links
]
Algorithms for C and C++ Programmers
Review by Dean Gahlon
Copyright (C) Dr. Dobb's Journal, February, 1996
I find computer books that deal with algorithms more interesting than,
say, entry-level C or C++ books. Algorithm books provide tools I can use
directly to build programs, and generally are lasting reference works. Practical
Algorithms for Programmers, by Andrew Binstock and John Rex, and Practical
Algorithms in C++, by Bryan Flamig, both fit this description.
Although these two books cover much of the same ground, they approach the
topic from different angles. The focus of Binstock/Rex is on the algorithms
(expressed in C), while that of Flamig is more on expressing algorithms
in C++. In other words, Binstock/Rex is an algorithm book; Flamig is a C++
book covering algorithms.
In general, Binstock/Rex is more accessible than Flamig, both in writing
and coding. The authors go into detail about the trade- offs among the variants
of various algorithms. They do a good job of giving the information you
need to make an informed decision as to the best version for a particular
application. Flamig, on the other hand, is briefer and tends to say less
about the possible options. As to the coding, Binstock/Rex is clearer, with
comments explaining each section of the program. Comparatively, the code
in Flamig is somewhat terse. (I'll admit that part of my preference for
Binstock/Rex is that I like their indentation style more than Flamigs. Also,
Binstock and Rex use more white space, which makes the code more readable.)
Reading for Reference
For the most part, Practical Algorithms for C Programmers is better
organized than the Flamig book. For example, Binstock/ Rex thoroughly cover
string searching in one chapter (including some interesting approximate-string
algorithms), then move on to cover other topics. Flamig, however, discusses
string searching in part of one chapter, then returns to the topic again
in a later chapter on finite-state machines. Although it makes some sense
to put that particular algorithm (the Aho-Corasick string-matching algorithm)
in the chapter on FSMs, a potential reader is likelier to say "I want
an algorithm for string searching" than "I want an algorithm using
finite-state machines." For reasons such as this, Binstock/Rex is the
better of the two as a reference work. Although it's probably a small thing,
I also found the index in Binstock/Rex to be more helpful and complete than
the index in Flamig. I tested this by looking up string searching in the
index to each book; there was an entry for it in Binstock/Rex, but none
in Flamig.
I also prefer the references in the Binstock/Rex book. They use notes at
the end of each chapter, with informative, explanatory sentences. Flamig
has just a bibliography at the end of the book. While the latter is more
scholarly, I find going to the back of the book to find further references
breaks up the flow of text. I prefer all the information on one topic to
be together. I also like Binstock/Rex's references because they mention
the drawbacks of the article they're referring to. For instance, in listing
the ElfHash routine, they warn you that some published versions of the routine
leave out a crucial character. The erroneous version would cause the function
to return zero every time it was called, which isnt exactly desirable.
Beyond C and C++
If what you're looking for is a C++ book that goes beyond teaching the language,
Flamig is fine. Hidden within its code listings are some interesting practical
uses of some of the subtleties of C++. One example is combining the placement
new operator with a class copy constructor to construct an
instance of that class in place.
One interesting idea in Flamig (which forms the basis of a good portion
of the book) is that of generators. A generator is something like an iterator
(as widely represented in C++ literature and class libraries). However,
rather than stepping through an existing set of objects, as an iterator
does, each call to the generator generates the next object in the set. I
think the idea of generators could lead in several potentially useful directions.
However, the authors' introduction of them results in a lengthy discussion
of unwinding recursion into iteration. This ends with some semireadable
code involving GOTO statements. (I'm afraid I'm not as well-disposed toward
GOTO's as Flamig is.) Although I find the idea of generators intriguing,
I'm not quite sure that its worth the cost of the readability of the resulting
code.
In some sense, the main advantage to Flamig isn't so much the algorithms
as the practical examples of class construction and other routines using
C++. It is not, however, a guidebook for object-oriented design. Except
for the idea of generators, the entire question of object orientation is
relatively incidental to the book's presentation. But since there are many
other books on object- oriented design out there, I don't consider this
a flaw in the book.
Beyond the Ordinary
Quite often, Flamig's Practical Algorithms in C++ deals with some
slightly more advanced topics: permutations, graphs, finite-state machines,
and the like. Binstock/Rex's Practical Algorithms for C Programmers,
however, takes on some out-of-the-ordinary topics: date and time calculations,
arbitrary-precision arithmetic, and data validation and integrity. The material
on heaps is much more complete in Flamig than it is in Binstock/Rex. Binstock/Rex,
though, covers more basic data structures: linked lists, trees, and the
like. To be fair, Flamig apparently covered much of this in his companion
book Practical Data Structures in C++ (John Wiley & Sons, 1993, ISBN
0-471-55863-X).
Hashing is a good example of the two books' relative coverage of a specific
topic. (Hashing is a method of storing data so that it is retrievable via
what is essentially a table lookup. A hash function converts the key for
the item being stored into an index into the hash table.) Both books cover
the topic adequately; in fact, both present the same optimal hash function,
taken from the same source. However, Binstock/Rex goes into greater detail
in explaining the trade-offs involved in the various types of hashing (or,
more accurately, collision handling). Practical Algorithms for C Programmers
also details some ideas on how to get good performance out of hashing. Flamig
covers hashing more broadly, discussing, among other things, a class that
implements file-based hashing (included on disk) and rebuilding the hash
table when it grows too large.
Conclusion
Both Practical Algorithms for C Programmers and Practical Algorithms
in C++ present a wide range of algorithms in source-code form and go
into detail when describing specific algorithms. Neither book leaves algorithms
as exercises for the reader, as do many algorithm books that are designed
as textbooks.
I prefer Binstock/Rex's Practical Algorithms for C Programmers because
it covers more ground. However, it's a close race. Flamig's focus on C++
issues is a strong pull. Although Flamig's book is more theoretical than
that of Binstock/Rex, it still keeps close to the practical in its title.
(The practicality of the algorithms in Binstock/Rex speaks for itself.)
Binstock/Rex has a minor disadvantage in that getting the source code on
disk requires a separate payment to the publisher, because it's not included
with the book. To me, however, that's a small problem.
Practical Algorithms for C Programmers
Andrew Binstock and John Rex
Addison-Wesley, 1995
512 pp., $29.95
ISBN 0-201-63208-X
Practical Algorithms in C++
Bryan Flamig
John Wiley & Sons, 1995
450 pp., $43.95
ISBN 0-471-00955-5
Electronic Review of Computer Books
Created 5/1/96 / Last modified 6/7/96 / webmaster@ercb.com