Errata List for
Data Structures in C++ Using the STL

by Timothy A. Budd

Published by Addison-Wesley Longman

A number of error reports were given to me just hours before I left for teaching a summer course. I didn't have time to merge them into this list, but will simply for the moment give a link here. Eventually I'll check these out and combine them with this list.

A number of errors and typos in the first and second printing of the book were corrected in the third printing. The printing number of a book is the first number listed on the bottom of the copyright page.

15Octal constants can begin with 00 (tm)
111booleans can also be used as switch values (tm)
232comment, rand return => rand returns (es)
235last word, taking=>talking (jab)
238"seven of" -> "7 of" (twice) (mc)
240A data field (=>member function) ... is called a mutator (ap)
347in recipe, yokes should be yolks (tm)
352comment in wrong font (pl)
359comment in wrong font (es)
467Assert need only check > 0, and loop can begin at 1(mc)
4692nd for statement indented wrong (jv)
4706th par, (n-1)n is n2-n, not n2+n (em)
476m[i,j] should be m[i][j] (lz)
477Misspelling, Logarithmic (nk)
477discussion of drop, see footnote, (nk)
6113if true => if yes (es)
61182nd line, Figure 9.1 should refer to Figure 9.2 (tm)
7129body of loop isn't indented (mc)
7130initializing smallest wrong (see footnote) (db)
7136arguments to count function (footnote)(jtk)
7137become true => become false (js)
7138find(string&,int)=>find(string&, unsigned int) (lnz)
7143bug: resize doesn't always pad properly (footnote) (tm)
7147respectfully should be respectively (mo)
7148first loop in insert should use greater-equal
7150comps should nowdays return bool, not int
81552nd par, missing ``of'' in number fundamental (jtk and dk)
8160less than 20 => less than 21 (kz)
8160not be eliminate, be=>been (jtk)
8162indentation on last if statement wrong (jtk)
8162arguments to swap incorrect (jtk)
81662nd par, 2nd sentence, each is, not each are (jtk)
8170swap is O(1), not O(n) (pl)
8170Insert places element before iterator, not after.
8174Count returns value (footnote) (jtk)
81751st par, not only is count not a member function, args are wrong (footnote)(jtk)
8177tilde missing on destructor(mc)
81771st par, differences are, not differences is (jtk)
8178copy constructor, v.length() should be v.size() (kv)
8180bottom, should use ++current, not current++ (tm)
8181code won't compile (footnote) (kz)
91912nd par, 2nd sen, missing word "either of the" (mo)
9192inserter places elements prior to location specified by iterator
9193box at top should be id_number, to match text at bottom (tm,gf)
9196Code does not work as advertised, see footnote (jb)
9197constructor should set max, not size (ok)
9198missing colon in constructor, 15th line from bottom (gf)
9199some compilers object to variables having same name as classes (e.g., course) (sg)
9202add ::iterator to declarations for c_start, c_end, etc. (tm)
92028 lines from bottom, s_end should be s_stop (sg)
9203missing colon in constructor(kv)
92032nd arg in insert should be T& (kv)
9204missing colon in constructor(kv)
9206firstlink => firstLink (mo)
9207implementation of prefix and postfix operators reversed (tm)
9207return this should be dereferenced (kv)
9208use of terms preorder and postorder should be prefix, etc (nk)
9208new link needs template argument (kv)
9208itr->currentlink should use period (also in erase) (kv)
9210remove by-ref from argument to add
9212(bottom) private members can also be accessed by friends (tm)
10220template arguments for stack (see footnote) (jtk)
10225Line -12, has precedence less than or equal to the top, code doesn't handle same priorities well (see footnote) (jtk)
10226Some systems confuse plus with function of same name, rename enum values as plusOp, etc.
10229randomizer(6) should be randomizer(7) (tm)
10229method done, should be <= not < (mo)
10233destructer does not delete last node (tm)
11243previousRow should be declared with numColumns entries (mc)
11247mid page, The DFS is still looking, DFS=>BFS (pr)
11257Figure in middle of code, unfortunate page break (pr)
11259subscript operator, test should be less than, not lt-equal, (mo)
11260confusion with type signitures on prefix and postfix increments (see page 207) (nk)
12267data should be unsigned, not int (footnote 3) (jp)
12271variable max conflicts with function on some systems, rename as maxValue
12272The implementation is correct (see footnote 4) (jp)
12275swap and next line indented wrong (jp)
12276word should be passed by value, since it is modified (jp)
12278exceed should be equal or exceed (2nd to last line) (jp)
12281recall that a list ... held a pointer to first element. (however, the list described has pointer also to end) (jp)
12283lefthChild.size() should be leftChild->size() (same for right) (kv)
12284condtional test bottom of page 284 should be removed (mo)
12286node::insert, newElement should be newNode->value (kv)
12288in result, should test if (rest) result->parent = pa (kv)
13302symbol n used for two different purposes (see footnote)
13308doBinary, code needs to set parent pointers (kz)
13310(also page 311) isEmpty() => empty() (ms)
13311pop the LEFT paren, and from operatorStack, not operandStack (es)
13312node methods left() and right() should be leftChild and rightChild (kv)
13315postorder traversal initialization not right (see footnote) (kz)
13325Exercise 14, left nodes=>leaf nodes (mo)
14346Line -8, multiset::iterator tree = sorter.begin(); (kz)
14350Code, pivotPosition and pivotIndex should be same variable (jc)
14353quicksort, last argument should be numberElements, not number?Elements-1 (pr)
15368heapsize => heapSize (ta)
164042nd last sentence, missing word, generating THE concordance (nk)
17412hash function missing mod reduction (pr)
17420penultimate sentence, value sort should be count sort (from page 416) (mo)
18431Fig 18.1 inner loop should increment k (rl)
18434numberOfRows should not be initializer (see note) (rl)
18434Missing parens following numberOfRows (th), also cost should be costs
18435mid page, variable name should be quantity (see page 432), also cost should be costs (rl)
B504string comparison should be ==, not = (mo)
B5152nd prototype, stop2 => stop1 (jb)

Footnote 1 Chapter 7, Page 143
The pad character may be important even if the new length is less than the buffer length. Consider a string that starts out with ten spaces, is resized to 3, then resized again to six. The last resize will not trigger a reallocation, but should use the pad character.

Footnote 2 Chapter 4, rain-drop discussion
Although largely correct as intuition, there are several minor mistakes in the discussion of gravity and the water drop. First off, the forces pulling down are EQUAL to the forces pulling up, otherwise the drop would rise up. (The book says the upward forces are greater than that of gravity). Second, the force holding the drop in place is adhesion, not surface tension. Surface tension is the force that is making the drop more or less half-hemispherical. (nk)

Chapter 7, page 130
The initial values for smallest and middle are wrong if the entire text consisted of words that were either all smaller than ``middle'' or all larger. It would be better, albeit more complex, to wait until after the split, until after the iterators have been defined, after you have tested to make sure they are not equal, then initialize both smallest and largest to the first word.
(Noted by Dick Botting).

Arguments to Count
In chapters 7 and 8 I describe the {\sf count} generic algorithm. Here I got caught in a late change that occurred between the April 95 draft of the STL (the document I used as my major source) and the final version. In the earlier form the result was returned through a pass-by-reference argument, as I described. In the final version it was returned as the procedure result.

Chapter 8, page 181, inplace merge
The code for inplace merge won't actually compile, since T cannot be bound to a type by the argument values. In the STL this is actually fixed using something called iterator traits, but discussing iterator traits at this point seemed like it would only confuse the student. So it seemed like a choice between a simple, but slightly incorrect, explanation of the concept, or a complex explanation of the code, that would serve only to confuse the concept. I elected clarity over precision, some may argue with this choice.

course registration system
John Boyland, Univ of Wisconsin, has pointed out that the course registration system does not work exactly as advertised. Students are matched with courses in the order that students are encountered, which, if a student registers for more than one course, can cause a student to be left out of a course that they should otherwise have been allowed access to. For example, assume that courses have a limit of 1, and we have the following records:
	Smith,Amy A
	Jones,Randy B
	Smith,Amy B
Since Amy will be processed entirely before randy, she will get both courses A and B, and poor Randy will get nothing. The fix, unfortunately, eliminates some of features that make this a good illustration of generic algorithms in the STL.

Template Arguments for Stack
Here again I was caught by a change between the time of the austin specification of the STL and the final document. In the draft the template arguments for stacks and queues were the underlying container. In the final document the first argument is the element type, and the second optional argument is the underlying container. This actually makes more sense, but is a change I didn't catch.

Chapter 10, infixToPostfix
Several people have noted that the simple algorithm used to comparing the precedence of operators in the infixToPostfix algorithm does not treat additions and subtractions at the same precedence level (or multiplications and divisions). John Cummings, a student of Nancy E. Miller at Mississippi State University, suggested the following fix:

	int Precedence (const operators &myOp) {
		if (myOp==leftparent)
			return 1
		else if (myOp==plusOp || muOp==minusOp)
			return 2
		else if (myOp==multiplyOp || muyOp==divideOp)
			return 3
then inside the function processOp, instead of simply comparing the two ops, add two calls on Precedence and compare their results.

Footnote 3 Chapter 12, bit-set implementation
On some machines, left shift of a signed quantity retains the sign bit. This can be avoided by using unsigned, rather than signed int. (jp) also notes that the unused high order bits of the bitset may cause the equality test to give incorrect results.

Footnote 4 Chapter 12, set implementation
The sense of "correct" is not clear here. It should not be taken to mean "standard conformant", since, as is explicitly noted, it is not as efficient as the standard sets must be, nor does it provide all the standard operations.

Chapter 13, Postorder traversal
The initialization of the postorder tree traversal is not correct. Consider the following tree:

The solution involves adding another loop around the left slide:
	while (true) {
		while (current && current->leftchild)
			current = current->leftchild;
		if (current->rightchild)
			current = current->rightchild;

Page 302, symbol n
Throughout most of page 302, n is used to represent the height of a tree. Then, 8 lines from the botton, n is suddently changed to represent the number of nodes in a tree. Clearly a different symbol should have been used for the latter.
Page 434, code at top
The call in numberOfRows should not be an initializer, instead there should be a call on resize in the body of the function:

   matrix::matrix (unsigned int nor, unsigned int noc)
    for (unsigned int i = 0; i < nor; i++)

Send all reports of errors or typos to Professor Budd at
One or more of the errors reported above were found by the following individuals:
Tolu Abiona, Northwestern Univeresity, Evenston, IL
Dick Botting, Professor, computer science, Cal State University, San Bernidino.
Jo Anna Bradfield, student, California State University San Bernadino
John Tang Boyland, University of Wisconsin-Milwaukee
Dr. Mats Cedvall, Computing Science Department, Uppsala Universitet
Jens Claußen, Lehrstuhl für Dialogorientierte Systeme, Universität Passau, Germany
Gary Flynn, James Madison University
Stan Goodman, Computer Science Student, Angelo State University, Texas.
Todd D. Haverkos, Northwestern University.
Omca Korugan, Alphatech, Inc
Nainan Kovoor, Shawn Systems, Inc.
Dave Kush, Junior CS, Cal State San Bernardino
Changwu Li, Temple University, USA.
Ricky Liu.
Paul Lu, Department of Computer Science, University of Toronto
Tom Mathies, Visiting Assistant Professor of Computer Science, Bucknell University
Nancy Miller, Associate Professor, Computer Science, Mississippi State University.
Eric Montague, Student, UC Berkeley Extension.
Mike Otten, Computer Science Department, Oregon Institute of Technology
Ajay S. Patil, Visiting Faculty to the Department of Information Technology, North Maharashtra University, India.
John E. Potter, Lock Haven, University of Pennsylvania
Peter Norman Reynolds, Swinburne University of Technology, Austrialia
Jonas Sundström, CS student, Uppsala University, Sweden,
Michael Sogioka, Student, Computer Science Department, California State University, San Bernardino.
Edward Szumski, Student, Computer Science Department, California State University, San Bernardino.
John A. Trono, Associate Professor of Computer Science, St. Michael's College
Jane Turk, Assistant Professor, Mathematics and Computer Science, La Salle University
Josh Valencia, Student, Computer Science Department, California State University, San Bernardino
Kerstin Voigt, Assistant Professor of Computer Science, California State University, San Bernardino
Han-gang Yu, Dept of Physiology & Biophysics, State University of New York at Stony Brook.
Kay Zemoudeh, Associate Professor Computer Science, Cal State San Bernardino
Leon Z.
Liping Zhang, MS Student,Department of Computer Science, University of Wisconsin.