Scott Meyers

Modification History and Errata List for Effective STL

Last Updated February 23, 2013
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:

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), and the URL for that
                      article is now http://www.cuj.com/documents/s=8000/
                      cujcexp1812austern/.

  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 have been proposed but have not yet been published:

    DATE                                                                  DATE
  REPORTED WHO PAGES  WHAT                                                FIXED
  -------- --- -----  ------------------------------------------------  --------
   2/23/13 bvw    19  In highlighted declaration for SpecialAllocator,
                      "class" should precede "SpecialAllocator".

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?," 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/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 CUJ 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.
                     
   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.  

  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.

   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 CUJ 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 CUJ, "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 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 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 

From here you may wish to visit the Amazon Page for Effective STL.