Two quick things:
- I've updated the ESTL errata list. New entries are below.
- Reminder: I'm speaking at Powells in Portland this Thursday.
Updated ESTL Errata List:
I've received a number of interesting bug reports and other comments on
ESTL since I last updated the errata list, so I've added the new stuff to
the list. You'll find the updated list in its usual spot at
http://www.aristeia.com/BookErrata/estl1e-errata_frames.html. The new
entries are listed below in the half-baked form I use internally for
keeping track of new errata.
Talk at Powell's this Thursday:
This Thursday night I'll be doing a C++/STL Q&A at Powell's Technical
bookstore at 7:00 PM. For details, consult my earlier mailing on this
topic (http://groups.yahoo.com/group/scott_meyers/message/27). I hope to
see you there!
Scott
DATE DATE
REPORTED WHO PAGES WHAT FIXED
-------- --- ----- ------------------------------------------------ --------
8/31/01 ds iv "Dr. Suess" ==> "Dr. Seuss" (twice).
8/ 4/01 dg 18-19 Once the typedef WidgetContainer is introduced,
the variable vw should be renamed cw to reflect
the new, more abstract, type name.
8/23/01 sdm Item 4 Clarify that of the three list::splice functions,
only one requires linear complexity. The other
two can run in constant time and can allow size to
run in constant time.
8/17/01 sdm 47 Omit from para 2 the advice to treat list like
a sequence container. Based on a discussion with
jep, I'm now less certain that that convention is
as widespread as I'd thought.
! 8/16/01 kh 55-56 My discussion of putting containers in shared
memory is incomplete and, to some degree,
misleading. As Item 15 demonstrates, some string
implementations use the small string optimization,
so elements of such strings won't be in shared
memory unless the string objects themselves are.
Furthermore, even use of placement new to put
containers in shared memory won't put static
components of those containers in shared memory,
and the Standard allows containers to have such
components (e.g., a shared empty string
representation); some implementations take
advantage of this allowance. kh summarizes things
this way: "No matter how well-written your
allocator implementation [for shared memory], if
it works, it is either a matter of luck or
hardwiring to a specific container implementation."
! 8/23/01 ja 78-79 When string implementations use reference
counting, the swap trick doesn't decrease the
capacity, because the copy constructor isn't
allocating any memory; it's just adjusting a
reference count. A more reliable way to perform
shrink-to-fit is to create the temporary string
via the range constructor, e.g., like this for the
last line of code on page 78:
string(s.begin(), s.end()).swap(s);
8/23/01 ja 79 The last paragraph of Item 17 is true, but it
doesn't matter in this context, because the swap
is with a temporary object that is destroyed at
the end of the statement. As a result, all
iterators, pointers, and references into the
"shrunk-to-fit" string have been invalidated.
I'll omit this paragraph from future printings
(and I'll try to remember to check the index to
see if it gets anything from this paragaph).
7/31/01 gl Item 20 When your comparison function for an associative
container isn't less<T>, it's important to specify
the comparison function for all algorithms that
will perform comparisons. Include a warning in
this Item and xref the example on pg. 149 in
Item 34. Note that following the advice of Item 44
minimizes the chances of running into this kind of
problem.
! 8/22/01 sdm 92 Eliminate the second-to-last sentence on this
page. In fact, equal values *are* equivalent,
because neither of two equal values precedes the
other in any reasonable sort order. (The
definition of "reasonable" is "strict weak
ordering," as I mention on page 94.)
! 8/22/01 jep Item 22 Shortly after the book was published, the Committee
decided that elements of sets/multisets should not be
modifiable without a cast, so the second code example
on page 96 is now invalid. To change a set/multiset
element in place, use the const_cast technique shown
on page 98. If you don't need in-place modification,
the five-step process described on pp. 99-100
continues to be safe and portable.
! 8/22/01 jep 104 In the lines after the calls to lower_bound, the
106 second test should be "!(w < *i)" and
"!(s < i->first)", respectively. This needs to be
fixed in both the code and the comments.
! 8/20/01 ag 108 The analysis for the cost of the call to insert is
incorrect, because it overlooks that the pair
created in the insert call is a temporary that
will ultimately be used to copy construct the pair
stored in the map. Because the temporary pair
contains a Widget, a temporary Widget is
constructed and destroyed. In practice, ag
observed that "the difference between the two
methods is only that in the operator[] form,
there's the extra call to the assignment operator
specialized for a double."
ag has demonstrated that operator[] could be
implemented much more efficiently than insert, but
the Standard is unfortunately worded in a way that
makes such implementations illegal. In the
future, this wording may be changed, or
implementers may choose to ignore it.
All things considered, the conclusion that insert
is more efficient than operator[] when adding new
elements to a map is not as reliable as I thought
when I wrote the book. In the immortal words of
Nathan Myers, "if it matters, measure."
8/ 4/01 dg 136 In last para, "which reorders element" ==>
"which reorders elements".
8/23/01 sdm 144 In the lower diagram, non-code text in
"remove_if's return value" should be in text font.
! 8/16/01 kh 159 In the call to accumulate at the top of the page,
the literal 0 is incorrect. Because its type is
int, accumulate will use int as its internal type
for storing the partially accumulated sums. The
correct type for this is string::size_type. It
makes a difference, because int is signed and
string::size_type is unsigned.
8/ 3/01 sdm 160 In the para following the code, there should be
no line break between "paragraph" and "2".
8/ 4/01 dg 162 The use of the term "components" in the 1st para
is confusing, because I never define that term.
Reword. (In general, I use "component" in this
book to mean "something in the STL.")
8/21/01 sdm 165 BPFCImpl should inherit from unary_function.
8/24/01 sdm 169 Practically speaking, anotherBadPredicate isn't as
bad as the function objects generated by
BadPredicate, because there is only one copy of
its state. As a result, anotherBadPredicate is
likely to behave as expected when passed to
remove_if or any other algorithm. (But see below
for "Interesting Comments" on Item 39.)
8/18/01 sp 187 Once in a code example on each page,
188 "vector<int> iterator" ==>
189 "vector<int>::iterator".
8/23/01 sdm 200 In the entry for equal_range in the next-to-last
row of the table, add "(followed by distance)".
Make the same change to this table on the book's
inside front cover.
8/30/01 ab 211 At end of 2nd para, "Another STL platform I uses..."
==>
"Another STL platform I use..."
8/ 4/01 dg 221 In 2nd para, "do fire up" ==> "do is fire up".
8/28/01 jtw 228 A more reliable URL for [27] is
http://www.research.att.com\
/~bs/stack_cat.pdf.
Interesting Comments:
DATE
REPORTED WHO PAGES WHAT
-------- --- ----- -----------------------------------------------------------
7/28/01 jep Item 9 The approach I show for erasing elements in a contiguous-
memory container while iterating through it does a good
job of maintaining iterator validity, but the time
complexity of the approach is quadratic. This can
typically be improved to linear by using a two pass
strategy:
1. Walk the container, writing the log for each element
you plan to erase (but don't erase anything yet).
2. Perform a range erase, e.g., by using the erase-
remove idiom or by using partition (or
stable_partition) and then erasing.
8/19/01 hxh 72-73 Regarding Implementation B's capacity being 7 when the
size of the string is 5, hxh (the author of
Implementation B) writes:
At the time I wrote, I could not imagine an
allocator that could deliver a non multiple of
sizeof(void*) bytes on the platforms I was targeting. I
could imagine specialty allocators that could very
efficiently deliver 4 bytes, but not 1, 2 or 3 bytes.
Or 8 bytes, but probably not 5, 6 or 7. So string takes
advantage of this. If the client asks for 5 bytes, he
gets 7 (8 minus 1 for the terminating null). So this
string really does have a minimum capacity. It's 3. I
tend to go for very small minimum capacities in order to
make containers of containers more efficient.
8/ 4/01 sdm Item 23 As part of the Loki library described in his book,
Modern
C++ Design (Addison-Wesley, 2001), and downloadable
from the book's web site, Andrei Alexandrescu developed the
AssocVector template, a map-like container built on top of
sorted vectors. If you're interested in the performance
improvements you might get from using a sorted vector
instead of a map, consider downloading AssocVector and
giving it a try.
8/20/01 ag 110-111 Write ag:
The discussion about using a generic ValueArgType to use
the specialized assign if present is interesting, but
using KeyArgType instead of key_type may trigger
multiple conversions for the key. Imagine having a map
indexed by strings and calling
efficientAddOrUpdate(m,"Andrea",10.5);
With the version in the book there are three conversions
from KeyArgType to key_value: one in lower_bound, one in
key_comp and another one in insert.
8/ 3/01 yjz Item 37 Writes yjz:
I agree that accumulate most clearly expresses what's
going on. Personally, that's more intuitive to me. I
would definitely choose accumulate when I do simple
value accumulations. But for the final example in this
item, I would definitely use for_each because the
solution using accumulate provided by this item
introduces a lot of overhead by calculating the average
point every time the operator() is called. So,
supposedly, we have n elements in the container, for the
example using accumulate, you will calculate the average
of points n times. But in for_each example, you only do
that calculation once. For this specific example, there
are 2*(n-1) times of division and (n-1) times of
construction of temporary Point objects which are not
necessary.
8/24/01 sdm Item 39 My decision to advise readers to make predicates pure
functions was based on pragmatic considerations, not on
the Standard. In fact, Kreft and Langer argue in their
April
2001 CUJ column that the Standard allows
predicates to have state, though they concede that the
problem I describe in this Item does exist in some STL
implementations. The Committee is aware of the problem,
but from what I can tell, they are leaning towards
modifying the Standard to require that predicates be pure
functions. If they do, my advice will conform to the
Standard at that point. To follow the Committee's
deliberations on this matter, monitor the status of
Library
Working Group Issue #92.
6/16/01 al Item 39 The idea of using remove_if to eliminate the third element
from a range is misguided. Implicit in my discussion is
the idea that remove_if will examine the elements in the
range FROM THE BEGINNING TO THE END, but this is not
required by the Standard and conceptually doesn't make
sense. Even if the predicate passed to remove_if could
safely have state, the only thing we could reasonably
expect from remove_if is that the third element visited
would be removed; we wouldn't be able to make any
assumptions about WHICH element that would be. For more
on this idea, consult the April 2001 column by
Klaus Kreft and Angelika Langer, "Unary
Predicates
in the STL." At the same time, it's worth noting that
every implementation of remove_if I know behaves like the
one in the book, and there are technical reasons why
alternative implementations are unlikely.
8/16/01 kh 203 Strictly speaking, the code at the bottom of this page
is not standard-conformant, because library implementers
are permitted to add extra parameters to library
functions, as long as the parameters have default
values. (You can read about this matter in Herb
Sutter's GOTW
#64.) A workaround for such a perverse
library implementation would be precisely what Item 46
suggests: use a function object to wrap the call to the
library function.
- I've updated the ESTL errata list. New entries are below.
- Reminder: I'm speaking at Powells in Portland this Thursday.
Updated ESTL Errata List:
I've received a number of interesting bug reports and other comments on
ESTL since I last updated the errata list, so I've added the new stuff to
the list. You'll find the updated list in its usual spot at
http://www.aristeia.com/BookErrata/estl1e-errata_frames.html. The new
entries are listed below in the half-baked form I use internally for
keeping track of new errata.
Talk at Powell's this Thursday:
This Thursday night I'll be doing a C++/STL Q&A at Powell's Technical
bookstore at 7:00 PM. For details, consult my earlier mailing on this
topic (http://groups.yahoo.com/group/scott_meyers/message/27). I hope to
see you there!
Scott
DATE DATE
REPORTED WHO PAGES WHAT FIXED
-------- --- ----- ------------------------------------------------ --------
8/31/01 ds iv "Dr. Suess" ==> "Dr. Seuss" (twice).
8/ 4/01 dg 18-19 Once the typedef WidgetContainer is introduced,
the variable vw should be renamed cw to reflect
the new, more abstract, type name.
8/23/01 sdm Item 4 Clarify that of the three list::splice functions,
only one requires linear complexity. The other
two can run in constant time and can allow size to
run in constant time.
8/17/01 sdm 47 Omit from para 2 the advice to treat list like
a sequence container. Based on a discussion with
jep, I'm now less certain that that convention is
as widespread as I'd thought.
! 8/16/01 kh 55-56 My discussion of putting containers in shared
memory is incomplete and, to some degree,
misleading. As Item 15 demonstrates, some string
implementations use the small string optimization,
so elements of such strings won't be in shared
memory unless the string objects themselves are.
Furthermore, even use of placement new to put
containers in shared memory won't put static
components of those containers in shared memory,
and the Standard allows containers to have such
components (e.g., a shared empty string
representation); some implementations take
advantage of this allowance. kh summarizes things
this way: "No matter how well-written your
allocator implementation [for shared memory], if
it works, it is either a matter of luck or
hardwiring to a specific container implementation."
! 8/23/01 ja 78-79 When string implementations use reference
counting, the swap trick doesn't decrease the
capacity, because the copy constructor isn't
allocating any memory; it's just adjusting a
reference count. A more reliable way to perform
shrink-to-fit is to create the temporary string
via the range constructor, e.g., like this for the
last line of code on page 78:
string(s.begin(), s.end()).swap(s);
8/23/01 ja 79 The last paragraph of Item 17 is true, but it
doesn't matter in this context, because the swap
is with a temporary object that is destroyed at
the end of the statement. As a result, all
iterators, pointers, and references into the
"shrunk-to-fit" string have been invalidated.
I'll omit this paragraph from future printings
(and I'll try to remember to check the index to
see if it gets anything from this paragaph).
7/31/01 gl Item 20 When your comparison function for an associative
container isn't less<T>, it's important to specify
the comparison function for all algorithms that
will perform comparisons. Include a warning in
this Item and xref the example on pg. 149 in
Item 34. Note that following the advice of Item 44
minimizes the chances of running into this kind of
problem.
! 8/22/01 sdm 92 Eliminate the second-to-last sentence on this
page. In fact, equal values *are* equivalent,
because neither of two equal values precedes the
other in any reasonable sort order. (The
definition of "reasonable" is "strict weak
ordering," as I mention on page 94.)
! 8/22/01 jep Item 22 Shortly after the book was published, the Committee
decided that elements of sets/multisets should not be
modifiable without a cast, so the second code example
on page 96 is now invalid. To change a set/multiset
element in place, use the const_cast technique shown
on page 98. If you don't need in-place modification,
the five-step process described on pp. 99-100
continues to be safe and portable.
! 8/22/01 jep 104 In the lines after the calls to lower_bound, the
106 second test should be "!(w < *i)" and
"!(s < i->first)", respectively. This needs to be
fixed in both the code and the comments.
! 8/20/01 ag 108 The analysis for the cost of the call to insert is
incorrect, because it overlooks that the pair
created in the insert call is a temporary that
will ultimately be used to copy construct the pair
stored in the map. Because the temporary pair
contains a Widget, a temporary Widget is
constructed and destroyed. In practice, ag
observed that "the difference between the two
methods is only that in the operator[] form,
there's the extra call to the assignment operator
specialized for a double."
ag has demonstrated that operator[] could be
implemented much more efficiently than insert, but
the Standard is unfortunately worded in a way that
makes such implementations illegal. In the
future, this wording may be changed, or
implementers may choose to ignore it.
All things considered, the conclusion that insert
is more efficient than operator[] when adding new
elements to a map is not as reliable as I thought
when I wrote the book. In the immortal words of
Nathan Myers, "if it matters, measure."
8/ 4/01 dg 136 In last para, "which reorders element" ==>
"which reorders elements".
8/23/01 sdm 144 In the lower diagram, non-code text in
"remove_if's return value" should be in text font.
! 8/16/01 kh 159 In the call to accumulate at the top of the page,
the literal 0 is incorrect. Because its type is
int, accumulate will use int as its internal type
for storing the partially accumulated sums. The
correct type for this is string::size_type. It
makes a difference, because int is signed and
string::size_type is unsigned.
8/ 3/01 sdm 160 In the para following the code, there should be
no line break between "paragraph" and "2".
8/ 4/01 dg 162 The use of the term "components" in the 1st para
is confusing, because I never define that term.
Reword. (In general, I use "component" in this
book to mean "something in the STL.")
8/21/01 sdm 165 BPFCImpl should inherit from unary_function.
8/24/01 sdm 169 Practically speaking, anotherBadPredicate isn't as
bad as the function objects generated by
BadPredicate, because there is only one copy of
its state. As a result, anotherBadPredicate is
likely to behave as expected when passed to
remove_if or any other algorithm. (But see below
for "Interesting Comments" on Item 39.)
8/18/01 sp 187 Once in a code example on each page,
188 "vector<int> iterator" ==>
189 "vector<int>::iterator".
8/23/01 sdm 200 In the entry for equal_range in the next-to-last
row of the table, add "(followed by distance)".
Make the same change to this table on the book's
inside front cover.
8/30/01 ab 211 At end of 2nd para, "Another STL platform I uses..."
==>
"Another STL platform I use..."
8/ 4/01 dg 221 In 2nd para, "do fire up" ==> "do is fire up".
8/28/01 jtw 228 A more reliable URL for [27] is
http://www.research.att.com\
/~bs/stack_cat.pdf.
Interesting Comments:
DATE
REPORTED WHO PAGES WHAT
-------- --- ----- -----------------------------------------------------------
7/28/01 jep Item 9 The approach I show for erasing elements in a contiguous-
memory container while iterating through it does a good
job of maintaining iterator validity, but the time
complexity of the approach is quadratic. This can
typically be improved to linear by using a two pass
strategy:
1. Walk the container, writing the log for each element
you plan to erase (but don't erase anything yet).
2. Perform a range erase, e.g., by using the erase-
remove idiom or by using partition (or
stable_partition) and then erasing.
8/19/01 hxh 72-73 Regarding Implementation B's capacity being 7 when the
size of the string is 5, hxh (the author of
Implementation B) writes:
At the time I wrote
allocator that could deliver a non multiple of
sizeof(void*) bytes on the platforms I was targeting. I
could imagine specialty allocators that could very
efficiently deliver 4 bytes, but not 1, 2 or 3 bytes.
Or 8 bytes, but probably not 5, 6 or 7. So string takes
advantage of this. If the client asks for 5 bytes, he
gets 7 (8 minus 1 for the terminating null). So this
string really does have a minimum capacity. It's 3. I
tend to go for very small minimum capacities in order to
make containers of containers more efficient.
8/ 4/01 sdm Item 23 As part of the Loki library described in his book,
Modern
C++ Design (Addison-Wesley, 2001), and downloadable
from the book's web site, Andrei Alexandrescu developed the
AssocVector template, a map-like container built on top of
sorted vectors. If you're interested in the performance
improvements you might get from using a sorted vector
instead of a map, consider downloading AssocVector and
giving it a try.
8/20/01 ag 110-111 Write ag:
The discussion about using a generic ValueArgType to use
the specialized assign if present is interesting, but
using KeyArgType instead of key_type may trigger
multiple conversions for the key. Imagine having a map
indexed by strings and calling
efficientAddOrUpdate(m,"Andrea",10.5);
With the version in the book there are three conversions
from KeyArgType to key_value: one in lower_bound, one in
key_comp and another one in insert.
8/ 3/01 yjz Item 37 Writes yjz:
I agree that accumulate most clearly expresses what's
going on. Personally, that's more intuitive to me. I
would definitely choose accumulate when I do simple
value accumulations. But for the final example in this
item, I would definitely use for_each because the
solution using accumulate provided by this item
introduces a lot of overhead by calculating the average
point every time the operator() is called. So,
supposedly, we have n elements in the container, for the
example using accumulate, you will calculate the average
of points n times. But in for_each example, you only do
that calculation once. For this specific example, there
are 2*(n-1) times of division and (n-1) times of
construction of temporary Point objects which are not
necessary.
8/24/01 sdm Item 39 My decision to advise readers to make predicates pure
functions was based on pragmatic considerations, not on
the Standard. In fact, Kreft and Langer argue in their
April
2001 CUJ column that the Standard allows
predicates to have state, though they concede that the
problem I describe in this Item does exist in some STL
implementations. The Committee is aware of the problem,
but from what I can tell, they are leaning towards
modifying the Standard to require that predicates be pure
functions. If they do, my advice will conform to the
Standard at that point. To follow the Committee's
deliberations on this matter, monitor the status of
Library
Working Group Issue #92.
6/16/01 al Item 39 The idea of using remove_if to eliminate the third element
from a range is misguided. Implicit in my discussion is
the idea that remove_if will examine the elements in the
range FROM THE BEGINNING TO THE END, but this is not
required by the Standard and conceptually doesn't make
sense. Even if the predicate passed to remove_if could
safely have state, the only thing we could reasonably
expect from remove_if is that the third element visited
would be removed; we wouldn't be able to make any
assumptions about WHICH element that would be. For more
on this idea, consult the April 2001 column by
Klaus Kreft and Angelika Langer, "Unary
Predicates
in the STL." At the same time, it's worth noting that
every implementation of remove_if I know behaves like the
one in the book, and there are technical reasons why
alternative implementations are unlikely.
8/16/01 kh 203 Strictly speaking, the code at the bottom of this page
is not standard-conformant, because library implementers
are permitted to add extra parameters to library
functions, as long as the parameters have default
values. (You can read about this matter in Herb
Sutter's GOTW
#64.) A workaround for such a perverse
library implementation would be precisely what Item 46
suggests: use a function object to wrap the call to the
library function.
No comments:
Post a Comment