This is a list of known mistakes in Matthew Austern's book Generic Programming and the STL: Using and Extending the C++ Standard Template Library (Addison Wesley Longman, 1998). If you find any additional mistakes, I would appreciate it if you would email me at matt@lafstern.org.

Some errors have already been corrected. This list is divided into errors found in the first printing only, errors found in both the first and second printings, errors found in the first through fourth printings (The third and fourth printings are identical), and errors found in the first through seventh printings (the fifth through seventh printings are identical).

On page 162, the first paragraph of the first bullet item says that no two keys ever hash to the same value. It should say that two different keys never hash to the same value.

Chapter 12

On page 244, in the definition of replace_if, the signature incorrectly uses the name replace.

On page 256, in the first paragraph after the heading remove_copy, the phrase "that are not equal to result" should instead read "that are not equal to value".

On page 77, in the fifth line from the bottom, C.last() should be replaced by C.end().

Chapter 7

On page 91, Default Constructible should be removed from the "Refinement Of" list. Trivial Iterators are not necessarily Default Constructible.

On page 92, the phrase "the expressions defined in Assignable, Equality Comparable, and Default Constructible" should be replaced by "the expressions defined in Assignable and Equality Comparable"

On page 92, the Default Constructor entry should be removed from the list of valid expressions.

On page 97, Default Constructible should be removed from the "Refinement Of" list. Output Iterators are not necessarily Default Constructible.

On page 98, the phrase "the expressions defined in Assignable and Default Constructible" should be replaced by "the expressions defined in Assignable".

On page 98, the Default Constructor entry should be removed from the list of valid expressions.

On page 100, Default Constructible should be added to the "Refinement Of" list.

On page 101, a Default Constructor entry should be added to the list of valid expressions.

At the bottom of page xix, in the acknowledgments, Jak Kirman is missing from the list of reviewers.

Chapter 1

On pages 4 and 5, in the definition of the line_iterator class, the name of the member variable at_end should be changed to is_valid all six times it appears. (The name is incorrect, since this member variable is true if and only we are not at the end of the input stream.)

Chapter 2

On page 10, in the paragraph following the bullets, the phrase "We specify the string by passing a pointer to its first argument" should be replaced by "We specify the string by passing a pointer to its first element".

At the bottom of page 13, the signature for find is incorrect. It should be changed from

  template <class Iterator, class T>
  Iter find(Iterator first, Iterator last, const T& value)

  template <class Iterator, class T>
  Iterator find(Iterator first, Iterator last, const T& value)

On page 18, in the second paragraph after the Basic Concepts heading, the phrase "and assign new value to objects of type X" should be replaced by "and assign new values to objects of type X"

Chapter 3

At the top of page 41, the phrase "and Input Iterator" should be replaced by "Input Iterator, and Output Iterator".

Chapter 4

On page 49, in the last paragraph of the introduction, the phrase "we are through a collection of records" should be replaced by "we are given a collection of records".

On page 55, in the third paragraph from the bottom of the page, the phrase "Just as Adaptable Unary Functions" should be replaced by "Just as Adaptable Unary Function".

Chapter 5

On page 59, on the third line from the top, "of of" is a mistake. It should instead read "of".

On page 64, on the second line from the bottom of the page, the phrase "these member functions" should be replaced by "these functions". (The functions in question are not member functions.)

On page 70, on the second line from the top of the page, the phrase "Bidirectional Iterator is a model of Forward Iterator" is incorrect, and should be replaced by "Bidirectional Iterator is a refinement of Forward Iterator".

On page 75, on the third line after the Associative Containers heading, the phrase "the elements are always ordering" should be replaced by "the elements are always ordered".

Chapter 6

On page 84, in the return type section of Copy constructor, the period following X is spurious. The line should simply be:
  Return type:    X

Chapter 7

On page 96, in the Semantics section for Postincrement and dereference, the first line of code is incorrect. It should be changed from
 T t = i;
to
 T t = *i;

On page 99, in the semantics section of Postincrement and assign, "++t" is incorrect. It should instead read "++x.

On page 104, in the semantics section of Iterator addition, the phrase "equivalent to executing --i n times" should be replaced by "equivalent to executing --i |n| times".

Chapter 8

On page 120, in the Notation section, the lines

	x	Object of type X.
	y, y, z	Objects of type Y.

are incorrect. They should be replaced by the single line

x, y, z

Objects of type X.

Chapter 9

On page 129, the postconditions for Size and Maximum size are incorrect. Both of them should be changed from

  0 <= a.size() <= a.max_size

  0 <= a.size() <= a.max_size()

On page 144, in the third line from the bottom, back should be replaced by end.

On page 158, in the semantics section of Upper bound, the phrase "whose key is greater k" should be replaced by "whose key is greater than k".

On page 164, in the return type section of Bucket count, X.size_type should instead be X::size_type.

On page 166, in the fourth bullet item at the top of the page, the phrase "size of of elements" should instead be "number of elements".

On page 166, in the first sentence after the Allocator heading, the phrase "a class that encapsulate" is incorrect. It should instead be "a class that encapsulates".

On page 166, in the parenthetical comment in the second paragraph from the bottom, "univerally" is a misspelling. It should instead read "universally".

On page 167, the phrase

And if you're you're using the default Allocator class

And if you're using the default Allocator class

On page 176, the signature for the constructor is incorrect. It should be changed from

  pair::pair(const T1&, const T2&)

  pair::pair(const T1& x, const T2& y)

On page 176, the signature for the generalized copy constructor is incorrect. It should be changed from

  template <class U1, class U2>
  pair::pair(const pair<U1, U2>&)

  template <class U1, class U2>
  pair::pair(const pair<U1, U2>& p)

On page 177, the signature for the helper function make_pair is incorrect. It should be changed from

  template <class T1, class T2>
  pair<T1, T2> make_pair(const T1&, const T2&)

  template <class T1, class T2>
  pair<T1, T2> make_pair(const T1& x, const T2& y)

On page 184, in the code example, the line
  list<int>::iterator i = L.begin();
is incorrect, and should be replaced by
  slist<int>::iterator i = L.begin();

On page 190, in the phrase "it is declared in the header <memory>", "<memory>" is incorrectly set in the ordinary text typeface. It should instead be set in the fixed-width typewriter typeface.

Chapter 11

On page 200, in the code example, the line
  list(int) L;
is incorrect, and should be replaced by
  list<int> L;

On page 211, in the second paragraph from the bottom, the sentence beginning with
  Version>1 uses operator ==
contains a typographical error. It should instead begin
  Version 1 uses operator ==

On page 224, in the second example, the line

  cout << The strings differ starting at character "

  cout << "The strings differ starting at character "

On page 242, in the paragraph immediately following the Example heading, the phrase "identiry function" is a misspelling. It should instead be "identity function"

On page 274, in the example, the constructors for equal_to<int> and modulus<int> are missing their parentheses.

On page 275, in the example, the constructors for equal_to<int> and modulus<int> are missing their parentheses.

Chapter 13

On page 294, in the top line, the space between the first quotation mark and the character 1 is spurious and should be removed.

On page 295, the phrase "stable_sort is implemented in terms of the the merge sort algorithm" is incorrect. It should be replaced by: "stable_sort is implemented in terms of the merge sort algorithm".

On page 296, in the first example, the comment line contains an extra quotation mark. It should read:
 // The printed result is "AaBbCcdDeEfF".

Chapter 14

On page 347, the declaration of the first constructor is incorrect. It should be changed from

  front_insert_iterator::front_insert_iterator(FrontInsertionSequence&)

  front_insert_iterator::front_insert_iterator(FrontInsertionSequence& S)

On page 349, in the example, the variable L is declared incorrectly. The declaration should be changed from

  list<int> L(100);

  list<int> L;

On page 350, the declaration of the first constructor is incorrect. It should be changed from

  back_insert_iterator::back_insert_iterator(BackInsertionSequence&)

  back_insert_iterator::back_insert_iterator(BackInsertionSequence& S)

On page 353, the declaration of the first constructor is incorrect. It should be changed from

  insert_iterator::insert_iterator(Container&, Container::iterator)

  insert_iterator::insert_iterator(Container& c, Container::iterator i)

On page 359, the declaration of the second constructor is incorrect. It should be changed from

  ostream_iterator::ostream_iterator(ostream_type&, const charT*)

  ostream_iterator::ostream_iterator(ostream_type& s, const charT* delim)

On page 363, in the descriptions of operator= and operator*, the expression *i = t should be replaced by *i = c.

On page 363, in the description of operator=, the type "const T&" should be replaced by "const CharT&".

Chapter 15

On page 383, the ellipses in the example code should be removed.

On page 389, the example is incorrect. First, the vector should be declared to have the name v, not c. Second, the assertion should be changed to read:

  assert(i == v.end() || *i >= 0);

On page 397, in the example, the template arguments for project2nd are incorrect. They should be changed from project2nd<int, char*> to project2nd<char*, int>.

On page 405, in the example, the expression B::print is incorrect. It should be changed to &B::print. (According to the C++ standard, clause 5.3.1 paragraph 3, forming a pointer to member requires an explicit & operator. Some compilers permit writing a pointer to member without the explicit &, but this is an extension.)

On page 407, in the example, the expression B::print is incorrect. It should be changed to &B::print.

On page 409, in the example, the expression Operation::eval is incorrect. It should be changed to &Operation::eval.

On page 411, in the example, the expression vector<int>::operator[] is incorrect. It should be changed to &vector<int>::operator[].

On page 413, in the example, the expression vector<int>::size is incorrect. It should be changed to &vector<int>::size.

On page 415, in the example, the expression vector<int>::size is incorrect. It should be changed to &vector<int>::size.

On page 417, in the example, the constructor for struct D is incorrect. It should read

  D(int x) : val(x) {}

On page 417, in the example, the expression B::f is incorrect. It should be changed to &B::f.

On page 419, in the example, the constructor for struct D is incorrect. It should read

  D(int x) : val(x) {}

On page 419, in the example, the expression B::f is incorrect. It should be changed to &B::f.

On page 422, the line immediately following the heading for section 15.8.2 is incorrect. It should be changed from
  binder1st<BinaryFun>
to
  binder2nd<BinaryFun>

Chapter 16

On page 454, in the first boldfaced line on the page, the signature of splice is incorrect. The type of the second argument should be slist, not list.

Bibliography

On page 532, in the entry for KMS88, the URL is incorrect. It should be changed from http://www.cs.edu/~musser/genprog.html to http://www.cs.rpi.edu/~musser/genprog.html.

On page xix, "Sibylla Schupp" is a misspelling. The correct spelling is "Sibylle Schupp".

Chapter 1

On page 6, there is a mistake in the declaration of strtab_print. The body of operator() should be

    copy(s.first, s.second, ostream_iterator(out));

    copy(s.first, s.second, ostream_iterator(cout));

On page 41, the definition of advance is incorrect. The type iterator_traits<I> should be replaced by iterator_traits<InputIterator>, and the second argument in the call to advance should be n, not d.

On page 42, the definition of struct iterator is incorrect. In the template parameter list, T* and T& should be replaced by Value* and Value&.

On page 43, the template parameter lists for iter_swap and iter_swap_impl are incorrect. The template parameter list

    template <class ForwardIterator1, ForwardIterator2>

    template <class ForwardIterator1, class ForwardIterator2>

    template <class ForwardIterator1, ForwardIterator2, type T>

    template <class ForwardIterator1, class ForwardIterator2, class T>

On pages 45-46, there are several errors in the node_wrap_base, node_wrap, and const_node_wrap classes. Here is a corrected version.

    template <class Node, class Reference, class Pointer>
    struct node_wrap_base 
      : public iterator<forward_iterator_tag, Node, 
                        ptrdiff_t, Pointer, Reference> 
    {
      typedef node_wrap_base<Node, Node&, Node*>             iterator;
      typedef node_wrap_base<Node, const Node&, const Node*> const_iterator;
      Pointer ptr;

      node_wrap_base(Pointer p = 0) : ptr(p) {}
      node_wrap_base(const iterator& x) : ptr(x.ptr) {}

      Reference operator*() const { return *ptr; }
      Pointer operator->() const { return ptr; }

      void incr() { ptr = ptr->next; }

      bool operator==(const node_wrap_base& x) const { return ptr == x.ptr; }
      bool operator!=(const node_wrap_base& x) const { return ptr != x.ptr; }
    };

    template <class Node>
    struct node_wrap : public node_wrap_base<Node, Node&, Node*>
    {
      typedef node_wrap_base<Node, Node&, Node*> Base;
      node_wrap(Node* p = 0) : Base(p) {}
      node_wrap(const node_wrap<Node>& x) : Base(x) {}

      node_wrap& operator++() 
        { incr(); return *this; }
      node_wrap  operator++(int) 
        { node_wrap tmp = *this; incr(); return tmp; }
    };

    template <class Node>
    struct const_node_wrap 
      : public node_wrap_base<Node, const Node&, const Node*> 
    {
      typedef node_wrap_base<Node, const Node&, const Node*> Base;
      const_node_wrap(const Node* p = 0) : Base(p) {}
      const_node_wrap(const node_wrap<Node>& x) : Base(x) {}

      const_node_wrap& operator++() 
        { incr(); return *this; }
      const_node_wrap  operator++(int) 
        { const_node_wrap tmp = *this; incr(); return tmp; }
    };

On page 57, the body of the helper function not1 is incorrect. The expression unary_negate<Predicate>(pred) should be replaced by unary_negate<AdaptablePredicate>(pred).

On page 57, on the fourth line from the bottom, the sentence "There is a similar adapter, pointer_to_unary_function, for binary functions" should be replaced by "There is a similar adapter, pointer_to_binary_function, for binary functions".

Chapter 5

On page 63, the footnote incorrectly identifies class block as a POD type. The footnote should instead read:

The C++ standard refers to a type that satisfies these restrictions as an aggregate type.

On page 128, the expression in the Destructor section is missing a tilde. The expression incorrectly reads a. X(). It should instead read a.~X().

On page 141, the third line incorrectly reads:

    fill_insert(p, first, last);

    range_insert(p, f, l);

Also on page 141, just above Complexity Guarantees, the insert member function is defined incorrectly; the arguments are declared as f and l, but the function body uses them as first and last. They should be f and l in both places.

Chapter 10

On page 185, the phrase

and a new Forward Iterator by inheriting from

  forward_iterator<forward_iterator_tag, T>

and a new Forward Iterator by inheriting from

  iterator<forward_iterator_tag, T>

On page 188, the second boldface line from the bottom of the page is incorrect. It reads:

  allocator::allocator()

  allocator::~allocator()

On page 201, under the Where Defined heading, the first sentence reads: "In the HP implementation, for_each was declared in the header <algo.h>." It should instead read: "In the HP implementation, find_if was declared in the header <algo.h>."

On page 205, a note has been omitted from the Requirements on Types section. The note should read:

According to the C++ standard both iterator types are required to be models of Forward Iterator, but this is unnecessarily strict. It is possible to implement find_first_of such that the second iterator type is a model of Forward Iterator and the first is any kind of Input Iterator.

On page 275, a note has been omitted from the Requirements on Types section. The note should read:

According to the C++ standard the iterator type is required to be a model of Bidirectional Iterator, but this is unnecessarily strict. It is possible to implement stable_partition for any Forward Iterator.

On page 282, the phrase "it is declared in the header <algorithm>" is incorrect. It should be replaced by "it is declared in the header <numeric>".

On page 284, the phrase "it is declared in the header <algorithm>" is incorrect. It should be replaced by "it is declared in the header <numeric>".

On page 285, the third template parameter is named (both in the template parameter list and in the function parameter list) BinaryOperation. This is inconsistent, because elsewhere (in the Requirements on Types section) it is referred to as BinaryFunction. It should be named BinaryFunction consistently.

On page 286, the phrase "it is declared in the header <algorithm>" is incorrect. It should be replaced by "it is declared in the header <numeric>".

On page 287, the phrase "it is declared in the header <algorithm>" is incorrect. It should be replaced by "it is declared in the header <numeric>".

Chapter 13

On page 300, the declaration of version 2 of partial_sort_copy is incorrect. The third template parameter appears as StrictWeakOrdering in the template parameter list but as Compare in the argument list. It should be StrictWeakOrdering in both places.

Chapter 15

On page 386, the phrase "if and only it" should be replaced by "if and only if".

On page 409, in the example, the last argument to transform is incorrect. It should be mem_fun(Operation::eval), not mem_fun1(Operation::eval). (This helper function was called mem_fun1 in earlier drafts of the C++ standard, but it is now called mem_fun.)

On page 411, in the example, the last argument to transform is incorrect. It should be mem_fun_ref(extract), not mem_fun1_ref(extract).

On page 426, in the example, the third line is incorrect. It should say bind2nd, not binder2nd.

Chapter 16

On page 507, in the description of stack::empty(), the phrase "Returns true and only if" should be replaced by "Returns true if and only if".

Appendix

On page 545, there should be an entry for ptr_fun. That entry is missing.

Thanks to Sam Bradsher, Bruce Eckel, Guy Gascoigne, Todd Kushner, Ed James-Beckham, Jon Jagger, Nate Lewis, CH Lin, Shawn D. Pautz, John Potter, George Reilly, Manos Renieris, Peter Roth, Dieter Rothmeier, Andreas Scherer, and Jürgen Zeller, for bringing these errors to my attention.