In preparation for the upcoming third printing of Effective STL, I've
fully updated the ESTL Errata list, including the addition of a number of
new bug reports and "interesting comments." My raw notes for the latest
delta are below, but things got massaged a fair amount as I integrated the
new material into the old list, so don't be surprised when you find
differences between what's below and what's in the list at
http://www.aristeia.com/BookErrata/estl1e-errata_frames.html.
My favorite bug in the book so far, though not one of the new ones below,
is the one reported for page 126, where I and every one of my pre-pub
reviewers overlooked the fact that in several places on the page, I'd
written "operator<<" where I clearly meant "operator>>". When reading the
manuscript, each of us saw what we wanted to see -- what we *expected* to
see -- instead of what was actually on the page. I marveled when that was
reported. But not right away. First I had to read the report over several
times. It look that long for my eyes to see that what was in ink was not
what was in my brain.
Scott
[Raw notes for latest ESTL errata update]
DATE DATE
REPORTED WHO PAGES WHAT FIXED
-------- --- ----- ------------------------------------------------ --------
9/ 4/01 bww iv Change "Meyer, Scott" to "Meyers, Scott" in the
Library of Congress Cataloging-in-Publication
Data.
10/ 4/01 ap 47 In 1st para, clarify that erase's return value
is void in associative containers only for the
forms taking iterators. (When passed a value,
erase returns the number of elements erased.)
10/24/01 wg 66 The first sentence of the third paragraph begins,
"Given all that ..., It should not". The word
"it" is errantly capitalized.
10/11/01 gn 67 In second and third bullets, the parameters
taken by resize and reserve are of type
Container::size_type, not size_t (though for all
the standard containers, Container::size_type
must be size_t).
10/11/01 gn 67 In second bullet, it is worth noting that there
is also a two-argument version of resize, the
second argument specifying the value to copy
into new elements if the container needs to be
increased in size.
8/22/01 jep 68 At end of 2nd-to-last para of Item 14, note that
any use of push_back would invalidate an
end iterator, e.g., one initialized from s.end().
! 10/11/01 gn 99 In the long middle para, casting away the
constness of a map key doesn't yield undefined
behavior, but attempting to MODIFY the key
does.
8/22/01 jep 100 Step 5 says that giving an accurate hint to the
"hint" form of insert yields constant-time
complexity, but it actually yields amortized
constant time complexity. Fixing this requires
that I also modify page 6 to define "amortized
constant time," and I'll have to add the term to
the index, too.
8/22/01 jep 104 In the 4th comment from the top of the page, the
reference to Item 45 should really be to Item 19.
8/22/01 jep 110 As in jep's bug report for page 100 above,
insertion with a hint yields amortized constant
time complexity, not simply constant time.
10/11/01 gn 118 In first line of second bullet, "const iterator"
==> "const_iterator". The latter should be
in code font.
8/22/01 jep 118-9 The Standardization Committee appears to be on
the verge of officially deciding that
comparisons between iterators and
const_iterators should always compile. For
details, consult href="http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html#179">Library
Working Group Issue
#179. While you're there, note the link to
href="http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html#280">Issue
#280, where you'll see that whether to
require comparisons of reverse_iterators and
const_reverse_iterators is not yet resolved.
! 8/22/01 jep Item 27 The code shown in this Item is sanctioned by
the Standard for every standard container except
string, and it should also work for any string
implementation that avoids reference counting.
For strings using reference counting, calling
begin() may invalidate existing iterators, and
that leads to this problem:
typedef string::iterator Iter;
typedef string::const_iterator ConstIter;
string s;
ConstIter ci;
... // make ci point into s
Iter i(s.begin()); // calling begin
// invalidates ci!
advance(i, distance(i, ci));
// pass invalidated ci
// to distance
A use of advance and distance that should work
with any standard container c (including strings
employing reference counting) is this:
Container::difference_type d =
distance(c.begin(), ci);
Iter i(c.begin()); // invalidates ci, but we
// don't need it any more
advance(i, d);
9/21/01 fk 136 At the top of the page, begin and end should
probably be declared const. (In fact, I should
probably look at all the code examples in the
book to see if other local vars could be
declared const, too.)
! 8/22/01 jep 159 In the second call to accumulate on this page,
1.0 should be 1.0f. The comment should also be
adjusted, as should the sentence after the example.
9/ 8/01 dxc Item 23 This Item focuses on lookup time, but overall
performance is determined by both setup time
(including the time to sort the vector) and lookup
time. Clarify that the assumption underlying this
Item is that the number of lookups vastly dominates
the number of insertions and erasures.
Interesting Comments:
DATE
REPORTED WHO PAGES WHAT
-------- --- ----- -----------------------------------------------------------
10/11/01 gn 33 Regarding the declaration of the function int f(double(d))
at the bottom of the page, the text suggest that the
parentheses are ignored. Well, it depends on what d is. If
it is a type-name then the function is
int f(double (*)(d)), and that is not the same as
int f(double d). The d must be looked up in this case to
determine if it is a type-name or not. See 8.2/7.
typedef int d;
int f(double(d)); // d is a type-name =>
// int f(double (*)(int));
int d;
int f(double(d)); // d isn't a type-name =>
// int f(double);
10/11/01 gn 53 Though the book is correct that the type of the allocator
for ListNodes is
Allocator::rebind::other
you'd have to express that type like this in a program:
typename Allocator::template rebind::other
Pages 7-8 explain why the "typename" is necessary, and the
use of "template" here is similarly required to help the
parser process things correctly.
8/22/01 jep 66 The "aptly named max_size member function" does nothing
more than return a number based on the number of bits in
size_type. It has nothing to do with how many items may
really be placed in any of the containers without
exceeding memory.
8/22/01 jep 90-91 You don't have to create a functor class, because
you could use stringPtrLess's type, then pass
stringPtrLess as a constructor argument:
bool stringPtrLess (string const*, string const*);
typedef bool (*StringPtrLess) (string const*,
string const*);
set ssp(stringPtrLess);
This is legal code, but I consider it highly ill-advised,
because it allows for the possibility that you have
multiple containers of the same type but with
different
sort orders. To me, that's a recipe for disaster, and
that's why I went out of my way to avoid mentioning it in
the book.
8/22/01 jep Item 21 Using less_equal is even worse than you say. The average
quicksort used in sort will crash with some data sets.
Neither 10A nor 10B will be in the range of equal_range.
For { 9 10B 10A 11 } I got find(10) is end,
lower_bound(10) is 11, upper_bound(10) is 10B, and
equal_range(10) is [11, 10B), an invalid range.
9/21/01 fk Item 37 fk points out that the accumulate approach to computing
the average of a set of points involves multiple
divisions, while the for_each approach does only a single
division at the end. As a result, he suggests that the
for_each approach may be more accurate. This seems likely
to me. At any rate, it's all but certain that for some
sets of points, the accumulate and for_each approaches
will yield slightly different averages due to the
complexities of floating point math.
10/14/01 kg Item 37 There is a notable difference between the accumulate and
the for_each approaches to this problem. When the range
is empty, accumulate returns Point(0,0), but calling
result on the functor returned from for_each yields
undefined behavior due to division by zero.
fully updated the ESTL Errata list, including the addition of a number of
new bug reports and "interesting comments." My raw notes for the latest
delta are below, but things got massaged a fair amount as I integrated the
new material into the old list, so don't be surprised when you find
differences between what's below and what's in the list at
http://www.aristeia.com/BookErrata/estl1e-errata_frames.html.
My favorite bug in the book so far, though not one of the new ones below,
is the one reported for page 126, where I and every one of my pre-pub
reviewers overlooked the fact that in several places on the page, I'd
written "operator<<" where I clearly meant "operator>>". When reading the
manuscript, each of us saw what we wanted to see -- what we *expected* to
see -- instead of what was actually on the page. I marveled when that was
reported. But not right away. First I had to read the report over several
times. It look that long for my eyes to see that what was in ink was not
what was in my brain.
Scott
[Raw notes for latest ESTL errata update]
DATE DATE
REPORTED WHO PAGES WHAT FIXED
-------- --- ----- ------------------------------------------------ --------
9/ 4/01 bww iv Change "Meyer, Scott" to "Meyers, Scott" in the
Library of Congress Cataloging-in-Publication
Data.
10/ 4/01 ap 47 In 1st para, clarify that erase's return value
is void in associative containers only for the
forms taking iterators. (When passed a value,
erase returns the number of elements erased.)
10/24/01 wg 66 The first sentence of the third paragraph begins,
"Given all that ..., It should not". The word
"it" is errantly capitalized.
10/11/01 gn 67 In second and third bullets, the parameters
taken by resize and reserve are of type
Container::size_type, not size_t (though for all
the standard containers, Container::size_type
must be size_t).
10/11/01 gn 67 In second bullet, it is worth noting that there
is also a two-argument version of resize, the
second argument specifying the value to copy
into new elements if the container needs to be
increased in size.
8/22/01 jep 68 At end of 2nd-to-last para of Item 14, note that
any use of push_back would invalidate an
end iterator, e.g., one initialized from s.end().
! 10/11/01 gn 99 In the long middle para, casting away the
constness of a map key doesn't yield undefined
behavior, but attempting to MODIFY the key
does.
8/22/01 jep 100 Step 5 says that giving an accurate hint to the
"hint" form of insert yields constant-time
complexity, but it actually yields amortized
constant time complexity. Fixing this requires
that I also modify page 6 to define "amortized
constant time," and I'll have to add the term to
the index, too.
8/22/01 jep 104 In the 4th comment from the top of the page, the
reference to Item 45 should really be to Item 19.
8/22/01 jep 110 As in jep's bug report for page 100 above,
insertion with a hint yields amortized constant
time complexity, not simply constant time.
10/11/01 gn 118 In first line of second bullet, "const iterator"
==> "const_iterator". The latter should be
in code font.
8/22/01 jep 118-9 The Standardization Committee appears to be on
the verge of officially deciding that
comparisons between iterators and
const_iterators should always compile. For
details, consult href="http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html#179">Library
Working Group Issue
#179. While you're there, note the link to
href="http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html#280">Issue
#280, where you'll see that whether to
require comparisons of reverse_iterators and
const_reverse_iterators is not yet resolved.
! 8/22/01 jep Item 27 The code shown in this Item is sanctioned by
the Standard for every standard container except
string, and it should also work for any string
implementation that avoids reference counting.
For strings using reference counting, calling
begin() may invalidate existing iterators, and
that leads to this problem:
typedef string::iterator Iter;
typedef string::const_iterator ConstIter;
string s;
ConstIter ci;
... // make ci point into s
Iter i(s.begin()); // calling begin
// invalidates ci!
advance(i, distance
// pass invalidated ci
// to distance
A use of advance and distance that should work
with any standard container c (including strings
employing reference counting) is this:
Container::difference_type d =
distance
Iter i(c.begin()); // invalidates ci, but we
// don't need it any more
advance(i, d);
9/21/01 fk 136 At the top of the page, begin and end should
probably be declared const. (In fact, I should
probably look at all the code examples in the
book to see if other local vars could be
declared const, too.)
! 8/22/01 jep 159 In the second call to accumulate on this page,
1.0 should be 1.0f. The comment should also be
adjusted, as should the sentence after the example.
9/ 8/01 dxc Item 23 This Item focuses on lookup time, but overall
performance is determined by both setup time
(including the time to sort the vector) and lookup
time. Clarify that the assumption underlying this
Item is that the number of lookups vastly dominates
the number of insertions and erasures.
Interesting Comments:
DATE
REPORTED WHO PAGES WHAT
-------- --- ----- -----------------------------------------------------------
10/11/01 gn 33 Regarding the declaration of the function int f(double(d))
at the bottom of the page, the text suggest that the
parentheses are ignored. Well, it depends on what d is. If
it is a type-name then the function is
int f(double (*)(d)), and that is not the same as
int f(double d). The d must be looked up in this case to
determine if it is a type-name or not. See 8.2/7.
typedef int d;
int f(double(d)); // d is a type-name =>
// int f(double (*)(int));
int d;
int f(double(d)); // d isn't a type-name =>
// int f(double);
10/11/01 gn 53 Though the book is correct that the type of the allocator
for ListNodes is
Allocator::rebind
you'd have to express that type like this in a program:
typename Allocator::template rebind
Pages 7-8 explain why the "typename" is necessary, and the
use of "template" here is similarly required to help the
parser process things correctly.
8/22/01 jep 66 The "aptly named max_size member function" does nothing
more than return a number based on the number of bits in
size_type. It has nothing to do with how many items may
really be placed in any of the containers without
exceeding memory.
8/22/01 jep 90-91 You don't have to create a functor class, because
you could use stringPtrLess's type, then pass
stringPtrLess as a constructor argument:
bool stringPtrLess (string const*, string const*);
typedef bool (*StringPtrLess) (string const*,
string const*);
set
This is legal code, but I consider it highly ill-advised,
because it allows for the possibility that you have
multiple containers of the same type but with
different
sort orders. To me, that's a recipe for disaster, and
that's why I went out of my way to avoid mentioning it in
the book.
8/22/01 jep Item 21 Using less_equal is even worse than you say. The average
quicksort used in sort will crash with some data sets.
Neither 10A nor 10B will be in the range of equal_range.
For { 9 10B 10A 11 } I got find(10) is end,
lower_bound(10) is 11, upper_bound(10) is 10B, and
equal_range(10) is [11, 10B), an invalid range.
9/21/01 fk Item 37 fk points out that the accumulate approach to computing
the average of a set of points involves multiple
divisions, while the for_each approach does only a single
division at the end. As a result, he suggests that the
for_each approach may be more accurate. This seems likely
to me. At any rate, it's all but certain that for some
sets of points, the accumulate and for_each approaches
will yield slightly different averages due to the
complexities of floating point math.
10/14/01 kg Item 37 There is a notable difference between the accumulate and
the for_each approaches to this problem. When the range
is empty, accumulate returns Point(0,0), but calling
result on the functor returned from for_each yields
undefined behavior due to division by zero.
No comments:
Post a Comment