Scott Meyers
Modification History and Errata List for Effective STL
Last Updated 2 October 2018
by Scott Meyers
What follows are my notes on what I've changed in Effective STL since its original publication (i.e., since its first printing) and what I believe may need to be changed in future printings. Most of the changes (or prospective changes) are cosmetic and don't affect the technical content of the book. To distinguish those modifications that do represent important technical modifications, I precede those entries with an exclamation mark ("!") and display them in red.
Each entry includes the following information:
- Date Reported: The date the problem was brought to my attention.
- Who: The initials of the person reporting the problem. The initials "sdm" refer to me. The mapping from other initials to full names is at the bottom of this document.
- Pages: The pages of the book (or the Item number) affected.
- What: A description of the problem and the solution.
- Date Fixed: The date on which I fixed the problem. If no date is shown, it means I haven't gotten around to fixing the bug or I'm still mulling over whether I want to fix it. Sometimes I change my mind on bug reports, so prospective bugs often spend quite a while in the "not yet fixed" state. When Addison-Wesley notifies me that a new printing is about to take place, I go through the bugs and fix all those I've decided must be fixed. It's thus not uncommon for all the bugs fixed for a particular printing to have the same fix date.
The easiest way to use this list is to find out which of the book's printings you have (it's listed on the copyright page near the bottom), then go to the appropriate section of the list and read from that point forward. For example, if you have a copy of the second printing, the changes made to the first printing won't apply to you, because the changes will already be in place in your copy of the book.
I am always interested in bug reports and suggestions for improvements to Effective STL. To submit comments, send email to estl@aristeia.com.
To be assured of always having the most accurate version of Effective STL at your fingertips, I encourage you to buy a copy of each printing :-).
The following changes were made for the second printing of the book. You need to worry about these changes only if you have a copy of the first printing of Effective STL:
DATE DATE
REPORTED WHO PAGES WHAT FIXED
-------- --- ----- ------------------------------------------------ --------
6/27/01 js 95 In second comment on page, "mulitmap" ==> 6/27/01
"multimap"
6/21/01 jw 136 In the last comment in the code example, 6/27/01
"goalPosition now points" ==>
"begin + goalOffset now points"
6/26/01 mjh 164 "containing lot of data" ==> "containing lots 6/27/01
of data"
5/ 7/01 sdm 228 Add to [26] that the article and the software it 6/27/01
describes can be downloaded from
http://www.bdsoft.com/tools/stlfilt.html.
6/26/01 dp 228 URLs for both columns by Matt Austern ([24] and 6/27/01
the second bullet after [27]) end in .htm, not
.html. (I checked all the URLs shortly before
publication, so these must have changed right
after the book was initially printed.)
The following changes were made for the third printing of the book. These changes apply to your copy of Effective STL only if it's the first or second printing.
DATE DATE
REPORTED WHO PAGES WHAT FIXED
-------- --- ----- ------------------------------------------------ --------
7/21/01 sdm Inside Diagrams should indicate which Items they are 10/30/01
Cover from. Inside front cover is from Item 45.
Inside back cover is from Item 15.
8/31/01 ds iv "Dr. Suess" ==> "Dr. Seuss" (twice). (By AW)
9/ 4/01 bww iv Change "Meyer, Scott" to "Meyers, Scott" in the (By AW)
Library of Congress Cataloging-in-Publication
Data.
7/16/01 hh 11 In 2nd para on page, "pointers of auto_ptrs" ==> 10/29/01
"pointers or auto_ptrs"
8/ 4/01 dg 18-19 Once the typedef WidgetContainer is introduced, 10/29/01
the variable vw should be renamed cw to reflect
the new, more abstract, type name.
8/23/01 sdm 23-24 Clarify that only one of the three list::splice 10/29/01
functions requires linear complexity. The other
two can run in constant time and can allow size
to run in constant time.
10/29/01 sdm 23 Twice on this page, "list" is in the wrong font. 10/29/01
! 7/13/01 pc 27 In the second code example, insertLoc needs to 10/29/01
be incremented after the call to insert. This
error is especially embarrassing, because I got
it right on pp. 184-5 (where I also explain what
happens if you don't do the increment).
7/27/01 ras 34 In first bullet para, "It's type" ==> "Its type" 10/29/01
6/29/01 sdm 47 In the last line of paragraph 2, "list" should 10/29/01
be in code font.
8/17/01 sdm 47 Omit from para 2 the advice to treat list like 10/29/01
a sequence container. Based on a discussion
with jep, I'm now less certain that that
convention is as widespread as I'd thought.
10/ 4/01 ap 47 In 1st para, clarify that erase's return value 10/29/01
is void in associative containers only for the
forms taking iterators. (When passed a value,
erase returns the number of elements erased.)
7/13/01 gk 57 Near middle of page, "Then you use 10/29/01
SpecialHeapAllocator" ==> "then you use
SpecificHeapAllocator"
7/28/01 jep 59 In 1st para, "be convenient state" ==> 10/29/01
"be a convenient state".
10/24/01 wg 66 The first sentence of the third paragraph 10/29/01
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 10/29/01
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).
7/21/01 tm 75 In 2nd para, "stored in contiguous memory" ==> 10/29/01
"stored in a single chunk of contiguous memory"
7/23/01 jeh 76 In the last line of the comments above the 10/29/01
declarations for fillArray and fillString,
change "maxNumDoubles" or "maxNumChars" to
"arraySize".
! 8/23/01 ja 79 The last paragraph of Item 17 is incorrect. 10/29/01
5/23/02 en string is unique among the standard containers
in having swap invalidate all pointers,
references, and iterators into the strings.
(Such swaps do not invalidate anything when done
to vectors, deques, lists, or any of the
standard associative containers.) Omit
paragraph.
! 8/22/01 sdm 92 Eliminate the second-to-last sentence on this 10/29/01
250 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.) Page 250
was changed to eliminate the index entry for
"equality, implying inequivalence".
!10/11/01 gn 99 In the long middle para, casting away the 10/29/01
constness of a map key doesn't yield undefined
behavior, but attempting to modify the key
does.
7/ 8/01 dm 100 The order of steps 3 and 4 should be reversed, 10/29/01
both at the top of the page and in the code
example. This improves the exception safety of
the approach.
8/22/01 jep 100 Step 5 says that giving an accurate hint to 10/29/01
6 insert yields constant-time complexity, but it
246 actually yields amortized constant time
247 complexity. When I fixed this, I added a
248 definition of "amortized constant time" to
page 6, plus I added related index entries.
! 8/22/01 jep 104 In the lines after the calls to lower_bound, the 10/29/01
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/22/01 jep 104 In the comments following the calls to 10/29/01
106 lower_bound, the reference to Item 45 should be
to Item 19.
7/ 1/01 cm 105 In second-to-last para, "consistency between" 10/29/01
==> "consistency among"
8/22/01 jep 110 As in jep's bug report for page 100 above, 10/29/01
insertion with a hint yields amortized constant
time complexity, not simply constant time.
7/23/01 jeh 114 In 2nd para from bottom, "it's design" ==> 10/29/01
"its design".
10/11/01 gn 118 In first line of second bullet, "const iterator" 10/29/01
==> "const_iterator". The latter should be
in code font.
! 7/25/01 sb 119 One can't just replace "i-ci >= 3" with 10/30/01
"ci+3 <= i", because ci+3 might not be a valid
iterator, e.g., it might be beyond the end of the
container. I replaced the suggested workaround
with a new one based on casting i to a ConstIter.
! 8/22/01 jep 121 I added a footnote telling readers that the 10/29/01
approach described in this Item may fail for
reference-counted strings and pointing them to
jep's comment on this matter below.
7/ 4/01 ajf 121 In second paragraph from the bottom, "then move 10/29/01
it forward it until" ==> "then move it forward
until"
7/10/01 dm 126 Everywhere on page, "operator<<" ==> 10/29/01
"operator>>"
8/ 4/01 dg 136 In last para, "which reorders element" ==> 10/29/01
"which reorders elements".
8/23/01 sdm 144 In the lower diagram, non-code text in 10/29/01
"remove_if's return value" should be in text
font.
10/29/01 sdm 144 In the upper diagram, the words "uncertified" 10/29/01
should be in text font.
! 8/22/01 jep 159 In the second call to accumulate on this page, 10/29/01
1.0 should be 1.0f. The comment should also be
adjusted, as should the sentence after the
example.
7/23/01 jeh 159 In 2nd prose para, "a floating pointer numbers" 10/29/01
==> "a floating point number".
8/ 3/01 sdm 160 In the para following the code, there should be 10/29/01
no line break between "paragraph" and "2".
! 7/23/01 jeh 185 In last line of last code fragment, 10/29/01
"bind2nd(plus<int>" ==> "bind2nd(plus<double>".
The next sentence needs to be correspondingly
modified.
8/18/01 sp 187 Once in a code example on each page, 10/29/01
188 "vector<int> iterator" ==>
189 "vector<int>::iterator".
7/23/01 imt 199 At end of 2nd-to-last para, note that for set 10/29/01
and map, count must return 0 or 1, and that's
why find has no speed advantage for those
containers.
8/23/01 sdm 200 In the entry for equal_range in the next-to- 10/30/01
last row of the table, add "then distance".
Make the same change to this table on the
book's inside front cover.
7/ 8/01 ajf 209 In first line after the bulleted list, <set> 10/29/01
and <functional> should be in code font.
8/30/01 ab 211 At end of 2nd para, "Another STL platform I 10/29/01
uses..." ==> "Another STL platform I use..."
7/ 7/01 sdm 216 As noted below, it's becoming more common for 10/29/01
vector and string iterators not to be pointers.
The first bullet on this page needs to be
reworded.
8/ 4/01 dg 221 In 2nd para, "do fire up" ==> "do is fire up". 10/29/01
8/28/01 jtw 228 A more reliable URL for [27] is 10/29/01
http://www.research.att.com/~bs/stack_cat.pdf.
7/ 8/01 ajf 235 In first para under "Case-insensitive string 10/29/01
comparison," "The time, though" ==>
"This time, though"
7/ 1/01 hs 239- Many of the apostrophes in this Appendix are 10/29/01
244 "straight" instead of "curly."
7/16/01 jf 251 Column 1, "NiftyEmail" entry. The page number 10/29/01
212 has been split into 21 and 2.
7/16/01 jf 253 Column 2, "types in containers" (sub-sub entry 10/29/01
for "iterators"). The spacing of the "see also
iterator . . ." text is gappy.
7/16/01 jf 254 In several places, "Microsoft'" ==> 10/29/01
260 "Microsoft's".
7/16/01 jf 256 Column 2, "range" entry: The sub-sub entry "to 10/29/01
avoid . . ." is gappy.
10/28/01 sdm 256 Add entry "RB Tree, see red-black tree" 10/29/01
10/29/01 sdm Inside Diagram for Implementation D is missing the (By AW)
Back shading that's present in the corresponding
Cover diagram on page 71.
The following changes were made for the fourth printing of the book. These changes apply to your copy of Effective STL only if it's one of the first three printings.
DATE DATE
REPORTED WHO PAGES WHAT FIXED
-------- --- ----- ------------------------------------------------ --------
7/19/01 sdm 17 The case for erase isn't quite as bad as the case 7/25/04
for insert, because you can safely erase the last
element of a vector, deque, and list without
invalidating iterators/pointers/references to
elements preceding it in the container.
! 6/29/01 jk 20 The first para of Item 3 is incorrect: front 7/25/04
and back do NOT return copies of elements, they
return references to elements. I
removed all mention of front and back.
5/22/02 sxb 25 In para after the 1st code fragment, "more than 7/25/04
one function call" ==> "more than one
statement"
2/ 4/03 shh 39 In second-to-last code comment, "create a SPW" 7/25/04
==> "create an SPW".
!11/29/02 gm 44 Regarding the paragraph after the first code 7/25/04
example, the call to erase can't take
logarithmic time for multi containers, because
such containers might consist entirely of
elements with the value to be removed. I
reworded things.
9/ 4/02 ga 46 In the for loop in the first code example, 7/25/04
"AssocContainer" should be entirely in italics.
8/ 1/03 lfr 51 In 2nd-to-last para, "unsigned integral value" 7/25/04
==> "unsigned integral type"
11/ 6/02 wb 57 In the second code example, the 7/25/04
SpecificHeapAllocator template is missing the
word "class" at the beginning of the template
definition.
!11/ 5/01 sdm 61 In 2nd-to-last para, the claim that C++ 7/25/04
guarantees that local objects are destroyed if
an exception is thrown is not quite true. The
guarantee holds only if the exception is caught.
I added a footnote explaining this caveat.
7/ 3/02 kes 67 To third bullet, add a remark that calling 7/25/04
reserve never changes the number of objects in
the container. (Unfortunately, when I did this,
I wrote "resize" instead of "reserve," thus
introducing an error not fixed until the 6th
printing; see db's entry below for 2/3/05.)
9/27/01 lz 77 In the second section of example code, the call 7/25/04
to vd.resize(...) is missing the final closing
parenthesis.
2/ 1/03 lfr 90 Missing colon at end of page. (The missing colon 7/25/04
was actually deliberate, but I reworded the end of
the sentence to "try this:", which I think is
clearer.)
7/13/02 ckl 91 In first code example, ssp's type should be 7/25/04
declared to be set<string*, stringPtrLess>.
! 2/ 4/02 sdm 106 In the lookup code using lower_bound (near the 7/25/04
middle of the page), the test should be this
instead of what is in the book:
if (i != vd.end() && !DataCompare()(s, *i)) ...
The comment needs to be adjusted, too.
The code in the book lets lower_bound use the
default "<" as its comparison function, but the
call to sort used a DataCompare object. In this
particular example, the two tests do the same
thing, but in general, it is critical to ensure
that lookups in a sorted vector are done using
the same comparison function as was used to sort
the vector.
11/ 5/01 sdm 111 In 2nd-to-last line of Item 24, "map" should be 7/25/04
in code font.
7/22/01 dm 122- To create an iterator from a const_iterator, 7/25/04
8/22/01 jep 123 it's not actually necessary to have access to
the container. Rather, you need to have access
to some iterator i into the container that
is no closer to end() than the const_iterator
is. You can then use i as you would the
container's begin iterator. I reworded to avoid
the claim that access to the container is
necessary.
3/16/02 lfr 124 The last word of the second sentence of the last 7/25/04
unbulleted paragraph has "i" in the wrong font.
!11/ 5/01 ma 134 In last code example, "widgets.begin()+20" should 7/25/04
be "widgets.begin()+19".
9/ 4/02 ga 141 At end of second prose paragraph, "...you should 7/25/04
probably be calling partition..." ==> "...you
should probably be calling partition or
stable_partition..."
4/18/03 lz 157 In 1st line, "many elements" ==> "many elements 7/25/04
with a particular value"
! 8/16/01 kh 159 In the call to accumulate at the top of the page, 7/25/04
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.
11/18/01 sk 160-1 PointAverage's constructor should list its member 7/25/04
initializers in the order in which the data
members are defined in the class. (Shame on me
for making this mistake, as it is the topic of
Item 13 in my Effective C++.)
8/ 4/01 dg 162 The use of the term "components" in the 1st para 7/25/04
is confusing, because I never define that term.
Reword. (In general, I use "component" in this
book to mean "something in the STL.")
9/17/03 hs 163 In the middle of the page, 7/25/04
DoSomething::operator() should be declared
public.
8/21/01 sdm 165 BPFCImpl should inherit from unary_function. 7/25/04
2/26/03 shh 166 In the third bullet point on the page, "returns 7/25/04
true or false" ==> "returns true or false (or
something that can be implicitly converted to
true or false)."
1/ 8/02 sdm 169 In code comment, "widget" should be capitalized 7/25/04
in "pointer-to-widget". Also, two comments on
this page should be reworded. It's the Widgets
that are or are not interesting, not the pointers
to them.
9/25/02 pn 171-172 Some examples here fail to explicitly state that 7/25/04
inheritance from e.g., std::binary_function is
public. For consistency with what I do everywhere
else in the book, they should.
1/29/02 lfr 176 Last sentence of second-to-last para is missing 7/25/04
the word "to".
7/28/03 jp 206 Reword problem statement to: "get rid of all the 7/25/04
207 elements in the vector whose value is less than
x and that occur after the last value at least
as big as y".
!10/ 4/01 rd 207 The comment above the initialization of 7/25/04
rangeBegin is incorrect. It should read as
follows:
Initialize rangeBegin to point to the element
following the last occurrence of a value greater
than or equal to y. If there is no such value,
initialize rangeBegin to v.begin(). If the last
occurrence of the value is the last element in v,
initialize rangeBegin to v.end().
2/26/03 shh 211 In line 5 of 4th prose para, "do this is with" 7/25/04
==> "do this with"
7/20/04 gc 228 Regarding reference [24], the article appeared in 7/25/04
December 2000 (not November).
11/ 2/02 cb 253 In column 1, the entry for istream_iterators 7/25/04
mentioning operator<< should mention operator>>.
11/ 2/02 cb 255 In column 2, the entry for operator<< should 7/25/04
mention operator>>.
The following changes were made for the sixth printing of the book. These changes apply to your copy of Effective STL only if it's one of the first five printings.
DATE DATE
REPORTED WHO PAGES WHAT FIXED
-------- --- ----- ------------------------------------------------ --------
2/ 3/05 db 67 In final sentence of third bullet (added per 2/ 3/05
kes's 7/3/02 bug report above), "resize" ==>
"reserve".
The following changes were made for the seventh printing of the book. These changes apply to your copy of Effective STL only if it's one of the first six printings.
DATE DATE
REPORTED WHO PAGES WHAT FIXED
-------- --- ----- ------------------------------------------------ --------
5/24/02 en 12-14 Add a bullet with the question, "Do you care if 10/ 5/05
using swap on containers invalidates iterators,
pointers, or references?" If so, string is out,
as noted in the bug report by ja and en for
page 79 above.
2/ 5/02 sdm 18-19 The text suggests that the WCIterator typedef 10/ 4/05
(near the bottom of the page) adds abstraction,
but it doesn't. WidgetContainer::iterator is
just as abstract, because iterator is itself an
abstraction. typedefs for iterator types are
still attractive, however, because they can save
a lot of typing (e.g., WCIterator instead of
WidgetContainer::iterator).
7/28/01 jep 29 The statement near the end of para 2 that input 10/ 4/05
iterators require that elements be moved into
their final positions one place at a time is
incorrect. Implementations are permitted to do
that, but they are not required to, and more
efficient approaches are possible.
11/04/03 sdm 29-30 In contrast to when I wrote the book, current 10/ 4/05
7/28/04 sk 66 vector implementations often use a growth
67 factor other than 2. I revised the book to
eliminate comments suggesting that 2 is the most
common growth factor.
9/18/04 dxm 44 The comment next to the call to remove_copy_if 10/ 4/05
near the bottom of the page could suggest that
values are removed from c before copying them to
goodValues. In fact, c is not modified at all;
undesired values are simply skipped during the
copy. I reworded the comment to say that the
"desired" values are copied.
10/11/01 gn 67 In second bullet, it is worth noting that there 10/ 4/05
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.
12/21/04 nds 67 In the description for resize, it's not true 10/ 4/05
that if n is greater than the current size, new
default-constructed elements will be added.
Rather copies of a single default-constructed
element will be added.
8/22/01 jep 68 At end of 2nd-to-last para of Item 14, note that 10/ 4/05
any use of push_back would invalidate an
end iterator, e.g., one initialized from s.end().
! 8/23/01 ja 78 When string implementations use reference 10/ 4/05
counting, the swap trick using the copy
constructor 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);
This version of the swap trick is safer for
vectors, too, because it eliminates any chance
that the copy constructor will copy the other
vector's excess capacity (which implementations
are permitted to do). I changed both swap trick
examples on this page to use the range
constructor instead of the copy constructor.
1/31/03 lfr 91 Include an xref to Item 7 near the definition 10/ 4/05
for DereferenceLess for readers who are confused
about why DereferenceLess is a non-template
struct containing a templatized operator().
10/ 4/05 sdm 96 Added comment to the last code example to 10/ 4/05
indicate that it should not compile per the
changes to pg. 97 below. I also reworded some
surrounding text to avoid claiming that the
code is legal.
! 8/22/01 jep 97 The standardization committee has clarified 10/ 4/05
that modifying set or map keys without a cast
should not compile. I added a footnote to
this effect, also noting that nonconformant
STL implementations continue to be used.
9/17/03 hs 99 The claim in the 3rd prose para that map nodes 10/ 4/05
could be put in write-protected memory is dubious.
Among other things, the value part of the pair
is generally modifiable, and the node almost
certainly has pointers to its children, which
may change over time. I removed the statement.
9/ 8/01 dxc 101 The approach described in this Item makes sense 10/ 4/05
only if the performance of Phase 2 (Lookup)
is vastly more important than the performance of
the other phases.
9/18/05 fxs 103 Need to mention that emulating a set or map 10/ 5/05
106 using a vector requires making sure there are no
duplicates in the data by the end of Phase I.
I added comments to the code, as there was no
space to add a proper discussion of this matter.
(See also the comments below on this topic.)
! 8/20/01 ag 108 The 2nd-to-last para is incorrect. Both the 10/ 5/05
call to operator[] and to insert generate a
temporary pair that must be constructed and
destructed. The only real difference is that
calling insert saves a call to the assignment
operator.
5/ 1/05 af 134 In the first code example, the 2nd parameter to 10/ 5/05
partial_sort should be widgets.begin()+20. In
the second code example, the 2nd parameter to
nth_element should be widgets.begin()+19. (The
comments for both code fragments are correct.)
6/28/04 he 197 The statement in the 2nd prose paragraph that 10/ 4/05
"equal_range not only does the job of find for
sorted ranges, it also replaces count" is
incorrect, because this part of the Item is
discussing STL algorithms, and the equal_range
algorithm is based on equivalence, while the
find and count algorithms are based on equality.
I reworded to clarify that the statement is true
only for types where equality and equivalence
yield the same results.
6/20/00 das 201 The text is not clear enough that find on a 10/ 5/05
multi container need not find the first
occurrence of a value. I reworded the
paragraph very slightly, but this is just the
tip of a bigger iceberg. For details,
see my comment on the table in Item 45 below.
10/ 4/05 sdm 225 Added an unnumbered citation to the third 10/ 4/05
edition of Effective C++, and clarified that
the Effective C++ CD has a copy of the second
edition of that book.
8/31/05 lfr 234 In the 3rd paragraph, "c" and "char" should be 10/ 4/05
in code font.
2/28/04 mp 257 Add an index entry under "set" pointing to page 10/ 4/05
199 for "idiomatic test for membership."
The following changes were made for the eighth printing of the book. These changes apply to your copy of Effective STL only if it's one of the first seven printings.
DATE DATE
REPORTED WHO PAGES WHAT FIXED
-------- --- ----- ------------------------------------------------ --------
6/ 7/06 sdm 47 Footnote symbol should immediately follow 6/ 7/06
121 punctuation, not precede it.
12/28/05 vxs 61 In footnote, "ma y" ==> "may". (I have no 6/ 7/06
idea why the FrameMaker spell checker does not
catch this. I ran it, trust me.)
5/ 2/06 rxp 72-73 The bottom part of pg. 72 says that 6/ 7/06
Implementation C reserves no space for a trailing
null, but the bottom part of pg. 75 implies that
I know of no contemporary library implementation
where a trailing null is not stored (which is
true). Unfortunately, I am unable to reproduce
the results for Implementation C described on
pg. 72, so I removed mention of Implementation C
from the bottom of page 72 (which caused a change
in the break between pages 72 and 73).
4/17/06 txs 131 Unlike front_inserter and back_inserter (which 6/ 7/06
always call push_front and push_back,
respectively), inserter returns an iterator that
keeps track of where to perform its next
insertion. I added a footnote to this effect.
1/ 2/06 vxs 152 In line 7 of final para, "return false" ==> 6/ 7/06
"returns false".
3/28/06 cmm 190 Last word on page: "is" ==> "are". 6/ 7/06
1/ 7/06 mxd 205 Per the resolution of core language issue 115, 6/ 7/06
the line of code at the top of this page is now
valid. I added a footnote to this effect.
The following changes were made for the tenth printing of the book. These changes apply to your copy of Effective STL only if it's printing 7, 8, or 9.
DATE DATE
REPORTED WHO PAGES WHAT FIXED
-------- --- ----- ------------------------------------------------ --------
3/14/07 cxb 68 In the 9th printing only, in code at top of page, NA
the following line of red code is missing between
the two black lines:
v.reserve(1000);
(This was an error introduced during printing.
The book source itself is correct, hence the lack
of a fix date.)
9/27/06 gxu 100 Point 3 from the bottom of page 99 is repeated 10/ 4/05
at the top of page 100. (This error was
introduced in the 7th printing, when I modified
pages 99 and 100 but sent the printer only the
new page 99, sigh.)
The following changes were made for the 12th printing of the book. These changes apply to your copy of Effective STL only if it's one of the first 11 printings.
DATE DATE
REPORTED WHO PAGES WHAT FIXED
-------- --- ----- ------------------------------------------------ --------
5/21/08 jxn 77 In code comment near top of page, remove space
between "(" and "see". 5/??/08
9/15/07 dmr 145 In 3rd para, "containers of dynamically allocated 8/12/09
pointers" ==> "containers of pointers to
dynamically allocated objects".
4/15/08 nxh 152 In first line, "rect" ==> "correct". 8/12/09
4/22/08 ajs 205 In penultimate line, "programing" ==> 8/12/09
"programming".
8/12/09 sdm 205 In footnote, "anticipated to be in 2009" ==> 8/12/09
"anticipated to be around 2011".
1/24/08 sdm 225 In the second bullet entry, reformat "Second 1/25/08
Edition" to match how all other edition
references are formatted.
2/ 4/08 sdm 226 Revise [4] to refer to [21] instead of 8/12/09
giving URL.
1/24/08 sdm 226 Revise [5] to refer to the 2003 edition and 1/25/08
avoid mentioning the price. (It's now $30).
8/18/08 sdm 226 Revise [9] to reflect that the book has 8/12/09
now been published.
1/15/08 mxs 227-228 For [19], replace the URL with 1/25/08
http://erdani.org/publications/traits.html.
For the second bullet entry after [27], replace
the URL with http://www.ddj.com/cpp/184401382.
For [29], replace the URL with
http://www.aristeia.com/BookErrata/
auto_ptr-update.html.
3/11/08 sdm 228 Remove question mark from end of article title ??/??/08
in second bullet entry after [27].
3/11/08 sdm 228 URL for bullet entry above [28] should be ??/??/08
http://www.aristeia.com/BookErrata/
ec++3e-errata.html.
7/2/08 sdm 259 Remove index entry for "URLs, for Effective 8/12/09
C++ CD demo".
The following changes were made for the 14th printing of the book. These changes apply to your copy of Effective STL only if it's one of the first 13 printings.
DATE DATE
REPORTED WHO PAGES WHAT FIXED
-------- --- ----- ------------------------------------------------ --------
8/31/11 sdm xii Replaced estl@aristeia.com with 2/13/12
smeyers@aristeia.com for comments on book content.
8/24/09 mam 5 Italicize "complexity guarantees" in first 2/13/12
sentence of last paragraph.
! 5/23/11 axw 52 In declarations of set objects on these pages, 2/13/12
57 the allocator type is specified as the second
template argument, but it should be the third;
the examples are missing the type of the
comparison function.
6/ 9/10 rsb 154 Clarify that the version of ciStringCompare 2/13/12
shown on this page is the one with a strcmp-like
tri-value interface, not the one suitable for
use as an STL comparison function.
The following changes were made for the 15th printing of the book. These changes apply to your copy of Effective STL only if it's one of the first 14 printings.
DATE DATE
REPORTED WHO PAGES WHAT FIXED
-------- --- ----- ------------------------------------------------ --------
2/23/13 bvw 19 In highlighted declaration for SpecialAllocator, 4/29/13
"class" should precede "SpecialAllocator".
The following changes have been proposed but have not yet been published:
DATE DATE
REPORTED WHO PAGES WHAT FIXED
-------- --- ----- ------------------------------------------------ --------
9/20/18 lfr Inside The table on the inside front cover is missing
Front the "(see below)" remark in the last cell of
Cover, row 2 that's present in the table on page 200.
200 That remark could be more clearly worded, e.g.,
"(see discussion)".
What follows are interesting comments about the material in Effective STL, but I don't expect to be able to modify the book to take these comments into account until (if ever) I write a second edition.
DATE
REPORTED WHO PAGES WHAT
-------- --- ----- -----------------------------------------------------------
6/22/01 lz Many Thanks to Leor Zolman, all the code fragments in the book
are available in compilable form at
http://www.bdsoft.com/resources/estlcode.html.
5/ 8/01 sdm Many STLport debug mode is no longer the only STL
6/27/01 pe implementation where vector's and string's iterators
aren't real pointers. The latest Dinkumware library
(including the one shipped with VC .NET) also uses
classes for these iterator types, and I'm told that
the same is true of the library that ships with GCC
3.0.
5/ 9/01 sdm Many In most places where I mention arrays, I should mention
valarrays, too. Like vectors, valarrays are
constrained to have contiguous storage, and this means
that pointers can be used as iterators into valarrays.
8/31/08 lfr Many The C++ Standard offers no guarantees about the order in
which the elements of a range are visited within an
algorithm, but the book routinely assumes that elements
are visited in order from beginning to end. In practice,
this is probably a safe assumption, but it is an
assumption for which there is no backing in the Standard.
11/11/10 jxb Many The book fails to discuss the interaction of NaNs and the
STL. All comparisons against NaNs fail, which affects
functions that depend on equality (e.g., std::find,
which will never find a NaN), functions that depend
on equivalence (e.g., std::sort, which will view NaNs
as equivalent to every value), and functions that
depend on any other comparisons (e.g., "<").
Fundamentally, the STL is designed to work with
"normal" values, and NaNs, being distinctly abnormal
values, virtually always lead to undefined behavior
in the STL. (This could be an Item in its own right:
"Avoid using NaNs" or maybe "Be wary of NaNs," with
the understanding that the advice applies only to
mixing NaNs and the STL, not to the use of NaNs in
general.)
7/28/01 jep 5 In second bullet, the summary of input iterators is subtly
incorrect. Input iterators may be read more than once, but
they support only single-pass algorithms. Once you've
incremented past an element, you can't get back to that
element.
9/24/01 mm Item 1 Sometimes, the best data structure for a problem is not in
the STL at all. mm writes that "One of the biggest misuses
that I've seen of the STL is when maps are used instead of
sparse matrix data structures. ... In many applications, a
matrix is very sparse. It is often the case that there is
just 2 to 5 entries per column, even in matrices with tens
of thousands of rows. ... There are highly efficient data
structures for doing this, and they're not very
complicated. ... There are lots of efficient algorithms
available for doing all sorts of operations on a matrix,
and there are various places on the internet (especially
www.netlib.org) that have classes that encapsulate this."
7/15/01 sdm Item 1 For another discussion of the pros and cons of different
containers, check out Andrew Koenig's and Barbara Moo's
column, "Which Container Should I Use?," appearing in
the August 2001 C/C++ Users Journal.
4/28/02 sdm Item 1 In his May 2002 Dr. Dobb's Journal article, "Disk
Thrashing & the Pitfalls of Virtual Memory," Bartosz
Milewski describes another consideration to take into
account when choosing between vector and deque: the
impact of repeatedly copying objects in order to keep
vector's memory contiguous.
3/21/02 ss Items The rules governing the conditions under which iterators
1,26,28 are or are not invalidated fail to apply to
reverse_iterators. Some operations on node-based
containers (e.g., insertion) that invalide no iterators MAY
invalidate reverse_iterators. ss sent this example:
std::list<int> int_list;
int_list.push_back(1);
std::list<int>::reverse_iterator iter = int_list.rbegin();
std::cout << *iter; // prints "1"
int_list.push_back(2);
std::cout << *iter; // prints "2" (doh!)
If you're interested in more information on this, take a
look at a comp.std.c++ thread on this issue.
12/ 5/07 dd Item 1 Another consideration is container iteration speed,
which generally decreases in this order:
vector/string (fastest iteration), deque, list,
set/multiset/map/multimap (slowest iteration).
9/26/01 kh 13 Technically, it would be more accurate to define
contiguous-memory containers as those that are assumed
to store more than one element per dynamically allocated
chunk of memory; they are not required to do so.
In theory, both deque and string could be implemented as
arrays of pointers to objects, for example, though no sane
implementation would do things that way. (Very large
objects may be stored only one element per chunk of memory
in a deque, though one would have to wonder why such large
objects were being stored in an STL container in the first
place.)
7/16/01 sdm Item 4 If you're interested in the technical and standardization
issues surrounding list::size, check out the
July 2001 comp.std.c++ thread discussing the matter.
10/11/01 gn 33 gn writes:
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);
6/ 4/04 tb Item 7 tb argues that the Item title should make clear that this
Item applies only when the container owns the pointers,
i.e., is responsible for deleting them. That's true, of
course, but I hope the discussion in the Item makes that
clear. In a future edition, I may reword the Item title.
8/26/02 sdm Item 7 Several people have written to ask about why
DeleteObject::operator() takes a pointer to const, even
thought it's going to delete the pointer. The answer is
that if it did not, it wouldn't be possible to use
DeleteObject on containers such as vector<const char*>.
There has been much debate in the C++ community over
whether deleting pointers-to-const should be legal, but it
is and it can be useful, so it's important to me that
DeleteObject support it.
12/22/01 sdm Item 7 Windows programmers experimenting with my
DeleteObject class should beware that there is a
Windows function with the same name. (I didn't know
that when I wrote the book.)
7/11/07 axm Items Item 9 discusses how to erase while iterating, and Item 28
9, 28 discusses how to erase using reverse_iterators, but neither
Item discusses how to erase while iterating with
reverse_iterators. For information on this issue, see
the newsgroup discussion of the issue that axm initiated.
6/29/01 kl 44-46 "AssocContainer<int>" isn't really appropriate for map and
multimap. This is true, but I can't think of a better
term, and I don't think the current term is too misleading.
7/28/01 jep 46 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.
12/ 2/02 jr 46 The code at the bottom of this page has two shortcomings:
(1) though it works when iterating over an entire container,
it's incorrect if given an arbitrary end iterator, because
the call to erase will invalidate the end iterator; and (2)
because each call to erase shifts all succeeding elements
down by one, the linear-looking loop really runs in
quadratic time.
Here's code that addresses both problems, where endIt is the
arbitrary end iterator to be used and, for consistency,
beginIt is an arbitrary begin iterator to be used:
vector<int>::iterator i = beginIt;
while (i!=endIt && !badValue(*i)) ++i;
vector<int>::iterator j = i;
while (i!=endIt){
if (badValue(*i)) {
logFile << "Erasing " << *i << '\n';
} else {
*j=*i;
++j;
}
++i;
}
c.erase(j, endIt);
Note that the second while loop is essentially a variant of
remove_if (see Item 32).
jr reports that in simple tests he performed comparing the
performance of this code with that on the bottom of page 46,
he saw speed improvements of 2-3 orders of magnitude.
11/26/16 sxl 46 If it's acceptable to erase the "bad" elements in reverse
order, the following code can be used in place of what's
shown on the bottom of the page:
for (SeqContainer<int>::reverse_iterator i = c.rbegin(); i != c.rend(); ) {
if (badValue(*i)) {
logFile << "Erasing " << *i << '\n';
c.erase( std::next(i++).base() );
}
else ++i;
}
This should run as fast as the code in jr's comment of
12/2/02 (above), but, unlike jr's code, it calls the
destructor of each erased element at the time it's erased.
11/14/01 axg Item 10 One way to avoid creating allocators with per-object state
is to declare all member functions static.
10/11/01 gn 53 Though the book is correct that the type of the allocator
for ListNodes is
Allocator::rebind<ListNode>::other
you'd have to express that type like this in a program:
typename Allocator::template rebind<ListNode>::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.
11/28/01 sdm Items Matt Austern has a nice article on implementing a
10-11 debugging allocator and allocator adapters in his
December 2001 column, "A Debugging Allocator."
! 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."
11/ 5/01 sdm 60-61 An alternative to creating and using the Lock template is
to use Alexandrescu's and Marginean's ScopeGuard technique.
11/13/01 ib 60-62 Given that manual concurrency control is a necessity, you
might consider using the cross-platform threading library
available at Boost.
8/22/01 jep 66 jep notes that "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/18/02 apl 69 apl argues that credit for notion that "God is in the
details" should go to Mies van der Rohe, not Einstein. He
points to a column in The Atlantic online to bolster his
argument.
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 <string>, 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.
9/12/01 sdm 74 A number of people have expressed interest in the source
for my claim that the elements of a vector must be stored
in contiguous memory. This guarantee is not in the
Standard itself. Rather, it will be part of a forthcoming
Technical Corregendum to the Standard, something of which
all library implementers are certainly aware. For more
information on this matter, consult the official defect
report (Library Working Group Issue #69).
3/29/04 df 74 An alternative to "&v[0]" is "&v.front()". df argues
that this is "the most explict way to do it." To me,
"&v[0]" is equally explicit, but both work.
8/17/07 abt 74 abt remarks:
I don't think you should avoid calling doSomething
altogether just because the vector is empty. Perhaps
doSomething has Something useful to do, even if you give
it zero elements. So I think the example should be
changed to
doSomething(v.empty() ? 0 : &v[0], v.size());
or, perhaps even better (as Daniel Filip had suggested on
the errata site),
doSomething(v.empty() ? 0 : &v.front(), v.size());
3/10/09 axa 75 This blog entry at Van's House makes clear that the
current C++ standard is ambiguous about the statement
that strings need not be stored in contiguous memory,
and it makes even clearer that any ambiguity about
the situation is eliminated in C++0x.
7/ 8/01 dm 80 Technically, the statement at the bottom of page 79
may compile. The real problem is that even if it
does, the statement
*pb = true;
can't affect the value of v[0], because it's not possible
to have a pointer to a bit.
11/27/07 cpj 81 Another alternative to vector<bool> is
basic_string<bool>.
12/22/07 nxd 81 Other alternatives to vector<bool> include
vector<unsigned char> and Boost's dynamic_bitset.
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. An example of this issue is discussed on page
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 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<string*, StringPtrLess> 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.
6/16/13 cxp 91 Regarding my DereferenceLess struct, cxp writes:
The drawback with your method is that you have to
redefine all of the STL functors. That is a lot of
work, if instead you make a wrapper you can have it
wrap all binary_functions(for instance). Here is
what I would suggest for that item:
template <typename T>
struct Dereference {
typename T::result_type
operator()(const typename T::first_argument_type* arg1,
const typename T::second_argument_type* arg2) const
{
return T()(*arg1, *arg2);
}
};
std::set<string*, Dereference<std::less<string> > > myset;
8/22/01 jep Item 21 jep writes:
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.
6/20/01 cc 93 Writes cc:
The comparison type StringPtrGreater can be
implemented in terms of comparison type StringPtrLess:
struct StringPtrLess:
binary_function<const string*, const string*, bool>
{
bool operator()(const string* ps1,
const string* ps2) const
{ return *ps1 < *ps2; }
};
struct StringPtrGreater:
binary_function<const string*, const string*, bool>
{
bool operator()(const string* ps1,
const string* ps2) const
{ return StringPtrLess()(ps2, ps1); }
};
Not only does this ease the maintenance, but also,
more importantly, expresses the logic: To determine if
x > y, we just need to test if y < x. That is because
a < b and b > a are necessary and sufficient
conditions for each other.
3/29/17 rxh Item 22 If you want to portably change non-key fields in an object
stored in a map or multimap, but you don't want to follow
the five-step approach described on pages 99-100, you can
declare the fields you want to modify mutable. Such fields
can be portably changed even in const objects. This
approach can also be used with sets and multisets, in which
case there is no need to cast away an object's constness
prior to modifying its mutable non-key fields.
10/ 5/05 sdm Item 23 As noted above, vectors emulating sets and maps must
manually ensure that the data contain no duplicates. Three
ways to ensure this are (1) to know a priori that the input
contains no duplicates, (2) to invoke the "unique"
algorithm on the vector after sorting it, and (3) to put
the data into a normal set or map during Phase 1, then copy
it into a vector at the end of Phase 1; use of the set or
map will automatically sort the data and eliminate
duplicates.
12/ 5/07 dd Item 23 Sorted vectors can also outperform associative containers
when container iteration is an important operation. dd
reported that in one system he examined, iteration
over a vector was 35% faster than over a set.
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 Loki 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.
9/15/15 sdm Item 23 In view of the addition of the unordered (hash table-based)
containers to the Standard Library as of C++11, it
may be that situations where a sorted std::vector
made sense in C++98 are now better served by an
unordered container. For an overview of this idea,
check out my blog post on the topic.
1/ 4/04 or Item 24 Another advantage to a function like efficientAddOrUpdate
vis-a-vis operator[] is that use of operator[] requires
that the value type of the pair (i.e., the mapped_type)
support default construction for insertion, but
efficientAddOrUpdate does not.
8/20/01 ag 110-111 Writes 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_type: one in lower_bound, one in
key_comp and another one in insert.
11/12/01 sdm Item 25 Regarding the choice of basing hashed containers on
equality or equivalence, P. J. Plauger, founder of
Dinkumware, posted this to comp.lang.c++.moderated on
8/27/01:
Our latest version of the hash template classes aims for
the best of both worlds. Turns out it can hash properly
given either a strict weak ordering, as in operator
less<T>, or an inequality comparison, as in operator
not_equal<T>. So we add a partial specialization that
looks for SGI-style template parameters and invert the
sense of the supplied predicate. The upshot is that you
can use our hash tables as a drop-in replacement for
map/set, using a strict weak ordering, or as a drop-in
replacement for SGI-style hash_map/set, using an
(in)equality comparison.
If you're interested in the choice between equality and
equivalence for hashed containers, you might want to
view the thread from which this posting is taken.
2/20/02 sdm Item 25 For information on how hash-based containers may be added
to the next version of the Standard Library, consult Matt
Austern's April 2002 column,
"Hash Tables for the Standard Library."
3/26/06 txs 113 Traits are also explained in the
third edition of Effective C++ :-)
5/16/03 drm Item 26 "The advice of this Item seems kind of strong. Counting
in my last bit of code: 49 const_iterators, 3 iterators, 0
problems (so far). I think a better slant to the Item
might be: be careful, const_iterators have certain
restrictions. I don't see that those restrictions
necessarily lead to the recommendation to prefer iterator."
9/ 4/02 ga 117 Five lines from the bottom, "const" should be
capitalized, because it is the first word in a sentence.
! 8/16/09 sxv 117 It is possible to convert an iterator to a
reverse_iterator, but the conversion is not implicit.
8/22/01 jep 118-119 The Standard doesn't actually state that comparisons
between iterators and const_iterators must be supported.
Now, however, the Standardization Committee appears to be
on the verge of officially deciding that such comparisons
must be allowed. For details, consult Library Working Group
Issue #179. While you're there, note the link to 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 121 The advance/distance idiom shown here 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<ConstIter>(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(static_cast<const Container&>(c).begin(),
ci);
Iter i(c.begin()); // invalidates ci, but we
// don't need it any more
advance(i, d);
7/22/01 dm Item 27 dm notes that both advance and distance are linear-time
operations on some containers. The time to accomplish
what the advance(distance(...),...) idiom does can be cut
in half for containers that lack random access as follows:
C::iterator i(c.begin());
if (ci == c.end()) i = c(end();
else while (&*i != &*ci) ++i;
Writes dm:
This is twice as fast on average, because the while loop
shown above only traverses the elements once. (I timed
it using two different compilers. Sure enough -- about
twice as fast.) Neither solution is optimum for all
iterator categories. The best solution is one that is
parameterized by the category tag to invoke the
advance(distance()) idiom only on random access
iterators, and the while loop on all others.
Perhaps this Item should be renamed to "Use distance and
advance to convert a *random access* container's
const_iterators to iterators."
8/27/02 jcj Item 28 When using the range form of erase, there is no need to
adjust a reverse_iterator's base if it marks the end of the
erase range. Consider:
vector<int> v;
... // Put 1-5 in v
// Remove 2-4 from vector in example [1, 2, 3, 4, 5]
vector<int>::iterator ifirst = // ifirst points
find(v.begin(), v.end(), 2); // to the 2
vector<int>::reverse_iterator rilast = // rilast points
find(v.rbegin(), v.rend(), 4); // to the 4
v.erase(ifirst, rilast.base()); // erase 2-4,
// inclusive
9/ 4/02 ga 133 Writes ga, "Another variation: reserve, move away/copy the
elements that would be moved one by one in one chunk and
then transform on the gap that we are left with." I
believe that in some cases, this will be more efficient
than resize/copy.
6/18/01 sdm Item 31 Additional useful information on the STL's various
sorting options can be found in Matt Austern's
column in the August 2001 "Sorting in the
Standard Library."
9/21/01 fk 136 At the top of the page, begin and end should probably be
declared const. (There are other places where variables
could be declared const, but a quick glance showed that
methodically adding "const" would cause some formatting
problems (new line breaks) and would, in some cases,
probably call for additional explanatory text. Lest the
cure be worse than the disease, I decided to leave things
as they are. If there is a second edition of this book,
I'll address the matter then.)
4/ 4/06 txs 136 There's more than one way to define the median and the 75th
percentile. The way I show in the book limits values to
those possessed by Widgets in the container, but other
approaches are valid. For more information, see the
Wikipedia entries for median and percentile.
9/13/07 abt 136 The initialization of goalOffset uses a floating point
value, but goalOffset is integral. This elicits a warning
with some compilers. In this case, we could initialize
with widgets.size()/4, but in the general case, we could
make the deliberate nature of the conversion clear by
using a static_cast.
2/22/03 lfr Item 34 When using an algorithm expecting a sorted range (e.g.,
includes, set_union, etc.) on a standard associative
container (especially a map or multimap), it's important to
pass the correct comparison function. The easiest way to do
this is to pass the result of the value_comp member
function:
typedef multimap<int, string> map1, map2;
...
bool subMultiset = includes(map1.begin(), map1.end(),
map2.begin(), map2.end(),
map1.value_comp());
This works for sets and multisets, too, because for those
types, value_comp returns the same thing as key_comp.
However, as noted in Item 44, for operations like
lower_bound, etc., it's generally better to use member
functions instead of algorithms when both are applicable.
6/ 3/02 mkk Item 35 This Item proposes two versions of ciStringCompare, one
with a strcmp interface and one with an operator<
interface. They have the same signature and cannot
coexist. This is frustrating because one may well need
both, and it also makes the example in Item 19 ambiguous
(which one was meant?) The example code would be more
useful if the second function was called ciStringLess or
some other distinct name.
6/ 9/10 rsb 154 Under POSIX, the strcasecmp function offers functionality
akin to stricmp and strcmpi. (None of the three is
standard in C or C++.)
2/20/03 lfr 156 Because postincrement is less efficient than preincrement,
the if statement may be better implemented as follows:
if (p(*begin)) {
*destBegin = *begin;
++destBegin;
}
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.
9/21/01 fk Item 37 fk remarks that the accumulate approach to computing
11/29/02 gm 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.
gm disagrees. He writes: "the results of all but the
last of those divisions get thrown away. The actual
calculations that contribute to the final answer are
exactly the same for both versions; the only
difference is that the version with accumulate (1)
does far more divisions, (2) does a whole lot of
unnecessary contructions and destructions of Point
objects, and (3) isn't legal. It's possible that a
sufficiently smart compiler might be able to eliminate
all that wasted effort, I suppose."
I responded that floating point makes my head hurt,
and gm replied that "the point I'm making doesn't
really have anything to do with floating point. The
results of all those extra divisions you're worried
about get thrown away immediately, that's all.
They're used to make return values from
PointAverage::operator(), which get passed to the next
invocation of PointAverage::operator() and ignored
there."
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.
2/26/03 shh 159 In order to make sure that the initial summary value
passed to accumulate is of the appropriate type, shh
suggests using this form:
Y sum = accumulate (
begin, // acts like a T*
end, // acts like a T*
static_cast<Y>(initValue) // initValue need not be of type Y
);
8/30/08 lfr 160 Functors to be used with the standard adapters (not1,
161 not2, bind1st, bind2nd) must declare their operator()
163 functions const, so the standard adapters would not be
167 usable with the functors on these pages that have
non-const operator()s, even though they inherit from
unary- or binary_function. Their adaptability could be
useful to non-standard adapters, however, if those
adapters didn't require const operator() functions.
1/13/05 bxr 160 The following approach allows the average of a set of
points to be computed by accumulate without its functor
using any side effects:
class AveragePoint {
public:
AveragePoint() : SumX(0), SumY(0), mv_NbrOfPoints(0) {}
AveragePoint(const AveragePoint& av_AveragePoint,
const Point2D& Point)
: SumX(av_AveragePoint.SumX + Point.x),
SumY(av_AveragePoint.SumY + Point.y),
mv_NbrOfPoints(av_AveragePoint.mv_NbrOfPoints+1)
{}
operator Point2D()
{
return Point2D(SumX/mv_NbrOfPoints, SumY/mv_NbrOfPoints);
}
};
class PointAverage:
public std::binary_function<AveragePoint, Point2D, AveragePoint> {
public:
const AveragePoint operator()(const AveragePoint& avgSoFar,
const Point2D& Point) const
{
return AveragePoint(avgSoFar, Point);
}
};
std::list<Point2D> PointCont;
...
Point2D avg = std::accumulate(PointCont.begin(),
PointCont.end(),
AveragePoint(),
PointAverage());
9/ 4/02 ga 161 for_each is also faster.
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 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 ultimately resolved the
problem by adding wording to the standard explicitly noting
that function objects may be freely copied. For details,
consult the Committee's notes on the matter.
This resolution means that the advice of the Item should
really be more like "Make sure predicates behave well when
copied." It also means that that the part of the Item
on page 169 (regarding the function anotherBadPredicate)
is incorrect, because the fact that there is only one copy
of the predicate's state means that it will behave well
when copied.
5/19/03 drm 168 drm points out that my claim that "Declaring operator()
const in predicate classes is necessary for correct
behavior, but it's not sufficient" is too strong, because
it would be safe to modify data members that don't affect
the outcome of the predicate. Such predicates would be
rather odd, however, so to avoid confusing the issue, I
have chosen to retain the current wording in the book.
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.
9/30/03 mp 188 In the operator() implementation at the top of the page, it
might be preferable to write the test this way,
return lowVal < val && val < highVal;
so that val is both numerically and *physically* between
the bottom of the range on the left and the top of the
range on the right. mp finds this clearer and also nearer
to the mathematical notation "lowVal < val < highVal. (mp
attributes this idea to either Steve Maguire's "Writing
Solid Code" or "Debugging the Development Process.")
1/13/07 nxd Item 44 This Item also applies to the swap algorithm. (I think
it's unfortunate that swap is considered an algorithm, but
it is. More details are available in
the newsgroup discussion on this topic.)
10/28/01 jep 191 Regarding the widespread use of red-black trees to
implement the standard associative containers, jep writes:
A perfectly balanced tree is impossible to rebalance after
insert/delete in reasonable time. The reason that an RB
tree is usually used (I know of no exception other than my
AVL implementation) is because that was used in the
original. The AVL version outperformed the RB version
hands down for searches. With very high dynamics (every
search caused either an insert or erase), they were about
equal. RB does have a better erase than AVL. I have not
found time to try a deterministic skip list yet.
Splay-tree and treap in addition to not meeting the
required worst case times do not have very good average
times either.
10/ 5/05 sdm 200 There are now several entries in the table I would like to
change, but I'd have to change the corresponding text more
than is practical between printings. In general, table
entries correspond to the easiest way to code the tests
such that equivalence is used when appropriate. This is
explained at the bottom of page 200. However, the second
entry in the last column mentions lower_bound instead of
equal_range, and, as pointed out on page 201, this is
because lower_bound is more efficient than equal_range. As
a result, most entries in the table emphasize ease of
writing correct code, but at least one emphasizes
efficiency of the resulting code. This is inconsistent.
If efficiency is to be emphasized (which is likely what I'd
do if I were to do it again), the second row would contain
these entries in this order,
find lower_bound find lower_bound
and the third entry in the last row would be "find" instead
of equal_range. This is because equal_range requires two
logarithmic-time searches, while find and lower_bound
require only one. Also, I'd probably change the first
entry in the third column from "count" to "find," as I'm
no longer convinced that using "count" is a widespread
idiom for testing for membership in a set or map.
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.
4/13/08 axf 226 axf writes: "You have the link to the ANSI store, but
there are two more options today. One is the printed 2003
version from Wiley's, the other is the fact that the
current standard drafts are available at the C++ standards
web site, and the final wording may very well be posted there
as a freely accessible working document. I have a
shortcut (via a domain I own) as http://stdcpp.org/, which
redirects to the real site at
http://www.open-std.org/jtc1/sc22/wg21/. Perhaps you want
to mention these sources for information on the C++
standard. The Wiley's books (both C and C++ standard) if
someone prefers a fairly priced printed copy, and the
standardization committee's site for those who want to
follow what is going on."
11/14/01 yd 243-244 yd writes: "I took your advice and turned on the
__STL_MEMBER_TEMPLATES flag in the SGI STL
configuration. However I was not able to compile, due to a
Microsoft bug (Q241949 in the MS knowledge base). MSVC6
supports member templates, but only when they are defined
inside the class body. The SGI STL has many such members
defined out-of-body. Getting it to compile would require
extensive cut-and-paste throughout. I haven't checked
STLport, but chances are it has the same problem since
it's derived from SGI STL."
I know from personal experience that some constructs
requiring member templates work with MSVC6 and STLport, so
this suggests that STLport has modified the SGI
distribution on which it is based to better work with
MSVC6. That suggests that STLport's STL may be a better
choice than SGI's, at least as regards support for member
function templates under MSVC6.
Who's who:
al = Angelika Langer kg = Klaus Gütter mjh = Michael Hawkins wg = Wayne Goertel dp = Derek Price gn = Gabriel Netterdag jw = Jon Webb rd = Ruediger Dreier lz = Leor Zolman ma = Motti Abramsky cc = Charles Cao yd = Yigal Dayan pe = Phil Edwards ib = Ian Bruntlett js = Jim Scheller axg = Adam Gates kl = Laushway Kevin sk = Stefan Kuhlins jk = Jason Kenny mm = Marc Meketon cm = Carl Manaster jdl = Jonathan Low hs = Herb Sutter lfr = Fraser Ross ajf = Albert J. Franklin ss = Stan Sulsky gk = George King sxb = Scott Blachowicz dm = Dave Miller en = Eric Niebler hh = Harold Howe mkk = Mary Kuhner jf = John Fuller kes = Keith Stanley tm = Tim McCarthy ckl = Chan Ki Lok pc = Paolo Carlini apl = Alan Lehotsky jeh = John Hershberger jcj = Jeffrey C. Jacobs imt = Igor Mikolic-Torreira pn = Phillip Ngan sb = Stephan Bergmann wb = Wolfram Burkhardt ras = Robert Allan Schwartz as = Adrian Spermezan jep = John Potter gm = Gareth McCaughan gl = Guillaume Laurent ga = Giulio Agostini yjz = Yingjun Zhang cb = Charles Brockman dg = David Grigsby shh = Seyed H. Haeri kh = Kevlin Henney jr = Johan Rade sp = Sanjay Pattni drm = Doug Morgan hxh = Howard Hinnant mp = Matt Page ja = Jesper Andersen mc = Moshe Cohen jtw = Jing Tao Wang jp = Jim Phillips ag = Andrea Griffini or = Olaf Raeke ab = André Blavier df = Daniel Filip ds = Dan Schmidt tb = Tim Buchowski bww = Bradley White he = Hans Eckardt dxc = David X Callaway gc = Guru Chandar fk = Feliks Kluzniak sk = Sharad Kala ap = Adam Petersen dxm = Declan Moran db = Day Barr nds = Nick de Smith fxs = Shlomi Frank bxr = Bert Rodiers af = Andy Fyfe vxs = Vincent Stojanov mxd = Mark Davis txs = Thomas Schell cmm = Cameron Mac Minn rxp = Randy Parker gxu = Giora Unger cxb = Christos Bellos nxd = Niels Dekker axm = Adam McLaurin abt = Allen B. Taylor cpj = Chris Just dmr = Martin Rottinger dd = Dibyendu Das mxs = Molly Sharp nxh = Neil Henderson ajs = Andrew Savige jxn = Julie Nahil axf = Attila Fehér axa = Amnon Aaronsohn sxv = Subramanian Venkatasubramanian mam = Mark A. McLaughlin rsb = Robert S. Barnes jxb = Jan Bielawski axw = Alexander Weaver bvw = Bart Vandewoestyne cxp = Charlie Page sxl = Sergey Lyskov rxh = Rafael Hamdan
From here you may wish to visit the Amazon Page for Effective STL.