REVIEW - Data Structures, Algorithms, and Applications in C++


Data Structures, Algorithms, and Applications in C++


Sartaj Sahni



McGraw-Hill (1998)




Francis Glassborow


April 1999



The subject of this book is one of the most popular among those wanting to write about programming. Unlike the vast majority that have previously crossed my desk this author understands that templates have much to offer. He uses them extensively to address a wide range of algorithms and data structures. It is therefore particularly sad that he does not appear to know about the Standard Template Library. The result is that his entire presentation is out ofphase with the development of modern C++.

The result is that much of this book will have to be studied carefully and reworked by a programmer who wants to use the full power available in current and future releases of C++ compilers.

Another problem is that his implementations are under-developed and, despite the use of templates, are based on an understanding of C++ as it was half a dozen years ago. It comes as no surprise that the author is essentially an academic, nor considering the quality of too much academic presentation of C++, is it any surprise to note that he is the winner of the IEEE Computer Society's Taylor L. Booth Education Award.

Harsh words for what is an above average book so let me give you a few examples.

First his code suffers from the traditional tight coupling between algorithms and data structures. Decoupling these via the use of a wide range of iterator types was one of the great developments of the STL. The STL has been around long enough for people with the grasp of the subject that this author has to have learnt how it works and how it is designed for extension. The failure to understand this has lead to such backward design decisions as implementing a stack type that has not been templatised by the container. Instead, two of his versions use

inheritance (why not by aggregation) and the third uses a dynamically allocated array coupled with throwing an exception if you try to add an element to a full stack.

The STL version of a stack is much simpler. It recognises that the essential ingredient for a stack is that the elements are in a strict order (LIFO) and therefore requires a sequence container. Any one will do so a stack is basically an adaptation of a sequence container.

Another problem with the author's containers is that he does not seem to have done anything to suppress C++'s default pass by value semantics (you can blithely write code that passes a stack by value). While the elements of his containers require

default constructors as well as
copy semantics. The more I study what the author has done the more holes appear. His various
templates cannot co-exist, but had he done it the STL way he could have provided partial specialisations to support some of his variations.

Let me take another example. Early on he provides a template function to find the roots of a quadratic equation. The template type is the type of the coefficients and all his function does is to send the results to the

. The first problem is that he assumes that the coefficients will be all of the same built-in arithmetic type. That assumption is doubly flawed because the template will have problems with type deduction if the coefficients are of a mixed type and it will have a further problem if you use complex coefficients. Internally he uses a
to store the return value from a call to
with an argument of the template argument type.

The second problem (for me) is that he has hard wired his code to output to cout. For the simple addition of an

parameter defaulted to
he could have written something much more general. He was only writing an example of a template function but a quality product would not have been much more complicated.

My last example also comes from early on where he presents a currency class (it isn't, it is a US currency class). His class hits about every irritant I can think of. But I will stick with just one. If you are silly enough to call the constructor with a value for cents that is greater than 99 it calls

. Yes read that again, any time you try to create an object that is a number of dollars and cents, it checks the number of cents and aborts your program if you have too many of them.

So who can use this book? Well, despite the many good features I would hate to give it to a student, the very fact that the author does good things will add bogus authenticity to the bad ones. The best use I can think of is for an instructor to use it as a source of code for code reviews. As an example here is the author's example of recursion:

T Rsum(T a[], int n)
{// Return sum of numbers a[0:n-1].
if (n>0)
return Rsum(a, n-1) + a[n-1];
return 0;
Anyone feel like writing a code review of the above?

My advice to the author is to forget the ego-boosting awards, spend some time understanding the STL and generic programming in general, get a good panel of code reviewers to help and then write an entirely different book that will capitalise on his knowledge to produce a good student text on the subject.

Book cover image courtesy of Open Library.

Your Privacy

By clicking "Accept All Cookies" you agree ACCU can store cookies on your device and disclose information in accordance with our Privacy Policy and Cookie Policy.

By clicking "Share IP Address" you agree ACCU can forward your IP address to third-party sites to enhance the information presented on the site, and that these sites may store cookies on your device.