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

by Timothy A. Budd

Published by Addison-Wesley Longman

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.

Chapter	Page	Description
1	5	Octal constants can begin with 00 (tm)
1	11	booleans can also be used as switch values (tm)
2	32	comment, rand return => rand returns (es)
2	35	last word, taking=>talking (jab)
2	38	"seven of" -> "7 of" (twice) (mc)
2	40	A data field (=>member function) ... is called a mutator (ap)
3	47	in recipe, yokes should be yolks (tm)
3	52	comment in wrong font (pl)
3	59	comment in wrong font (es)
4	67	Assert need only check > 0, and loop can begin at 1(mc)
4	69	2nd for statement indented wrong (jv)
4	70	6th par, (n-1)n is n2-n, not n2+n (em)
4	76	m[i,j] should be m[i][j] (lz)
4	77	Misspelling, Logarithmic (nk)
4	77	discussion of drop, see footnote, (nk)
6	113	if true => if yes (es)
6	118	2nd line, Figure 9.1 should refer to Figure 9.2 (tm)
7	129	body of loop isn't indented (mc)
7	130	initializing smallest wrong (see footnote) (db)
7	136	arguments to count function (footnote)(jtk)
7	137	become true => become false (js)
7	138	find(string&,int)=>find(string&, unsigned int) (lnz)
7	143	bug: resize doesn't always pad properly (footnote) (tm)
7	147	respectfully should be respectively (mo)
7	148	first loop in insert should use greater-equal
7	150	comps should nowdays return bool, not int
8	155	2nd par, missing ``of'' in number fundamental (jtk and dk)
8	160	less than 20 => less than 21 (kz)
8	160	not be eliminate, be=>been (jtk)
8	162	indentation on last if statement wrong (jtk)
8	162	arguments to swap incorrect (jtk)
8	166	2nd par, 2nd sentence, each is, not each are (jtk)
8	170	swap is O(1), not O(n) (pl)
8	170	Insert places element before iterator, not after.
8	174	Count returns value (footnote) (jtk)
8	175	1st par, not only is count not a member function, args are wrong (footnote)(jtk)
8	177	tilde missing on destructor(mc)
8	177	1st par, differences are, not differences is (jtk)
8	178	copy constructor, v.length() should be v.size() (kv)
8	180	bottom, should use ++current, not current++ (tm)
8	181	code won't compile (footnote) (kz)
9	191	2nd par, 2nd sen, missing word "either of the" (mo)
9	192	inserter places elements prior to location specified by iterator
9	193	box at top should be id_number, to match text at bottom (tm,gf)
9	196	Code does not work as advertised, see footnote (jb)
9	197	constructor should set max, not size (ok)
9	198	missing colon in constructor, 15th line from bottom (gf)
9	199	some compilers object to variables having same name as classes (e.g., course) (sg)
9	202	add ::iterator to declarations for c_start, c_end, etc. (tm)
9	202	8 lines from bottom, s_end should be s_stop (sg)
9	203	missing colon in constructor(kv)
9	203	2nd arg in insert should be T& (kv)
9	204	missing colon in constructor(kv)
9	206	firstlink => firstLink (mo)
9	207	implementation of prefix and postfix operators reversed (tm)
9	207	return this should be dereferenced (kv)
9	208	use of terms preorder and postorder should be prefix, etc (nk)
9	208	new link needs template argument (kv)
9	208	itr->currentlink should use period (also in erase) (kv)
9	210	remove by-ref from argument to add
9	212	(bottom) private members can also be accessed by friends (tm)
10	220	template arguments for stack (see footnote) (jtk)
10	225	Line -12, has precedence less than or equal to the top, code doesn't handle same priorities well (see footnote) (jtk)
10	226	Some systems confuse plus with function of same name, rename enum values as plusOp, etc.
10	229	randomizer(6) should be randomizer(7) (tm)
10	229	method done, should be <= not < (mo)
10	233	destructer does not delete last node (tm)
11	243	previousRow should be declared with numColumns entries (mc)
11	247	mid page, The DFS is still looking, DFS=>BFS (pr)
11	257	Figure in middle of code, unfortunate page break (pr)
11	259	subscript operator, test should be less than, not lt-equal, (mo)
11	260	confusion with type signitures on prefix and postfix increments (see page 207) (nk)
12	267	data should be unsigned, not int (footnote 3) (jp)
12	271	variable max conflicts with function on some systems, rename as maxValue
12	272	The implementation is correct (see footnote 4) (jp)
12	275	swap and next line indented wrong (jp)
12	276	word should be passed by value, since it is modified (jp)
12	278	exceed should be equal or exceed (2nd to last line) (jp)
12	281	recall that a list ... held a pointer to first element. (however, the list described has pointer also to end) (jp)
12	283	lefthChild.size() should be leftChild->size() (same for right) (kv)
12	284	condtional test bottom of page 284 should be removed (mo)
12	286	node::insert, newElement should be newNode->value (kv)
12	288	in result, should test if (rest) result->parent = pa (kv)
13	302	symbol n used for two different purposes (see footnote)
13	308	doBinary, code needs to set parent pointers (kz)
13	310	(also page 311) isEmpty() => empty() (ms)
13	311	pop the LEFT paren, and from operatorStack, not operandStack (es)
13	312	node methods left() and right() should be leftChild and rightChild (kv)
13	315	postorder traversal initialization not right (see footnote) (kz)
13	325	Exercise 14, left nodes=>leaf nodes (mo)
14	346	Line -8, multiset::iterator tree = sorter.begin(); (kz)
14	350	Code, pivotPosition and pivotIndex should be same variable (jc)
14	353	quicksort, last argument should be numberElements, not number?Elements-1 (pr)
15	368	heapsize => heapSize (ta)
16	404	2nd last sentence, missing word, generating THE concordance (nk)
17	412	hash function missing mod reduction (pr)
17	420	penultimate sentence, value sort should be count sort (from page 416) (mo)
18	431	Fig 18.1 inner loop should increment k (rl)
18	434	numberOfRows should not be initializer (see note) (rl)
18	434	Missing parens following numberOfRows (th), also cost should be costs
18	435	mid page, variable name should be quantity (see page 432), also cost should be costs (rl)
B	504	string comparison should be ==, not = (mo)
B	515	2nd 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:

			a
		       /
		      b
		       \
		        c
                       /
		      d

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;
		else
			break;
		}

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:

  template 
   matrix::matrix (unsigned int nor, unsigned int noc)
 {
    rows.resize(nor);
    for (unsigned int i = 0; i < nor; i++)
		   rows[i].resize(noc);
 }

(ta)

Tolu Abiona, Northwestern Univeresity, Evenston, IL

(db)

Dick Botting, Professor, computer science, Cal State University, San Bernidino.

(jab)

Jo Anna Bradfield, student, California State University San Bernadino

(jb)

John Tang Boyland, University of Wisconsin-Milwaukee

(mc)

Dr. Mats Cedvall, Computing Science Department, Uppsala Universitet

(jc)

Jens Claußen, Lehrstuhl für Dialogorientierte Systeme, Universität Passau, Germany

(gf)

Gary Flynn, James Madison University

(sg)

Stan Goodman, Computer Science Student, Angelo State University, Texas.

(th)

Todd D. Haverkos, Northwestern University.

(ok)

Omca Korugan, Alphatech, Inc

(nk)

Nainan Kovoor, Shawn Systems, Inc.

(dk)

Dave Kush, Junior CS, Cal State San Bernardino

(cl)

Changwu Li, Temple University, USA.

(rl)

Ricky Liu.

(pl)

Paul Lu, Department of Computer Science, University of Toronto

(tm)

Tom Mathies, Visiting Assistant Professor of Computer Science, Bucknell University

(nm)

Nancy Miller, Associate Professor, Computer Science, Mississippi State University.

(em)

Eric Montague, Student, UC Berkeley Extension.

(mo)

Mike Otten, Computer Science Department, Oregon Institute of Technology

(ap)

Ajay S. Patil, Visiting Faculty to the Department of Information Technology, North Maharashtra University, India.

(jp)

John E. Potter, Lock Haven, University of Pennsylvania

(pr)

Peter Norman Reynolds, Swinburne University of Technology, Austrialia

(js)

Jonas Sundström, CS student, Uppsala University, Sweden,

(ms)

Michael Sogioka, Student, Computer Science Department, California State University, San Bernardino.

(es)

Edward Szumski, Student, Computer Science Department, California State University, San Bernardino.

(jt)

John A. Trono, Associate Professor of Computer Science, St. Michael's College

(jtk)

Jane Turk, Assistant Professor, Mathematics and Computer Science, La Salle University

(jv)

Josh Valencia, Student, Computer Science Department, California State University, San Bernardino

(kv)

Kerstin Voigt, Assistant Professor of Computer Science, California State University, San Bernardino

(hy)

Han-gang Yu, Dept of Physiology & Biophysics, State University of New York at Stony Brook.

(kz)

Kay Zemoudeh, Associate Professor Computer Science, Cal State San Bernardino

(lnz)

Leon Z.

(lz)

Liping Zhang, MS Student,Department of Computer Science, University of Wisconsin.