[1] For a refresher on elementary algebra, we recommend Chrystal [1904].
[2] We recommend Patterson and Hennessy [2007].
[3] For a selective but incisive introduction to algorithms and data structures, we recommend Tarjan [1983].
[4] The standard reference is Stroustrup [2000].
[5] The code in the book compiles and runs under Microsoft Visual C++ 9 and g++ 4. This code, together with a few trivial macros that enable it to compile, as well as unit tests, can be downloaded from www.elementsofprogramming.com.
[6] See www.elementsofprogramming.com for the up-to-date errata.
[1] While regular types underlie the design of STL, they were first formally introduced in Dehnert and Stepanov [2000].
[2] Strictly speaking, as becomes clear in Chapter 4, it could be either total ordering or default total ordering.
[3] Underlying type is defined in Chapter 12.
[4] C++ functions are not objects and cannot be passed as arguments; C++ function pointers and function objects are objects and can be passed as arguments.
[5] Appendix B shows how to define type attributes and type functions in C++.
[6] Abstract procedures appeared, in substantially the form we use them, in 1930 in van der Waerden [1930], which was based on the lectures of Emmy Noether and Emil Artin. George Collins and David Musser used them in the context of computer algebra in the late 1960s and early 1970s. See, for example, Musser [1975].
[7] See Appendix B for the full syntax of the requires clause.
[1] Knuth [1997, page 7] attributes this algorithm to Robert W. Floyd.
[1] The original is in Robins and Shute [1987, pages 16–17]; the papyrus is from around 1650 BC but its scribe noted that it was a copy of another papyrus from around 1850 BC.
[2] For a comprehensive discussion of minimal-operation exponentiation, see Knuth [1997, pages 465–481].
[4] See the work on RSA by Rivest, et al. [1978].
[5] Compilers perform similar transformations only for built-in types when the semantics and complexity of the operations are known. The concept of regularity is an assertion by the creator of a type that programmers and compilers can safely perform such transformations.
[6] Another technique involves defining a function identity_element such that identity_element(op) returns the identity element for op.
[7] The first O(log n) algorithm for linear recurrences is due to Miller and Brown [1966].
[8] For a review of linear algebra, see Kwak and Hong [2004]. They discuss linear recurrences starting on page 214.
[9] Fiduccia [1985] shows how the constant factor can be reduced via modular polynomial multiplication.
[10] It could be any type that models semiring, which we define in Chapter 5.
[11] Leonardo Pisano, Liber Abaci, first edition, 1202. For an English translation, see Sigler [2002]. The sequence appears on page 404.
[1] In later chapters we extend the notion of stability to other categories of algorithms.
[2] We explain our naming convention later in this section.
[3] STL incorrectly requires that max(a, b) returns a when a and b are equivalent.
[4] This result was conjectured by Jozef Schreier and proved by Sergei Kislitsyn [Knuth, 1998, Theorem S, page 209].
[5] See Knuth [1998, Section 5.3: Optimum Sorting].
[1] “... the excess by which the greater of (two) unequal areas exceeds the less can, by being added to itself, be made to exceed any given finite area.” See Heath [1912, page 234].
[2] The Egyptians used this algorithm to do division with remainder, as they used the power algorithm to do multiplication. See Robins and Shute [1987, page 18].
[3] Dijkstra [1972, page 13] attributes this algorithm to N. G. de Bruijn.
[4] While this definition works for Archimedean monoids, it does not depend on ordering and can be extended to other structures with divisibility relations, such as rings.
[5] It is known as Euclid’s algorithm [Heath, 1925, pages 14–22].
[6] The incommensurability of the side and the diagonal of a square was one of the first mathematical proofs discovered by the Greeks. Aristotle refers to it in Prior Analytics I. 23 as the canonical example of proof by contradiction (reductio ad absurdum).
[7] See Chrystal [1904, Chapter 5].
[8] See van der Waerden [1930, Chapter 3, Section 18].
[9] See Knuth [1997, Exercise 4.6.1.6 (page 435) and Solution (page 673)].
[11] See Agarwal and Frandsen [2004].
[12] “If two numbers a and b have the same remainder r relative to the same modulus k they will be called congruent relative to the modulus k (following Gauss)” [Dirichlet, 1863].
[13] For an excellent discussion of quotient and remainder, see Boute [1992]. Boute identifies the two acceptable extensions as E and F; we follow Knuth in preferring what Boute calls F.
[14] We follow Peano [1908, page 27] and include 0 in the natural numbers.
[1] Our treatment of iterators is a further refinement of the one in Stepanov and Lee [1995] but differs from it in several aspects.
[2] A pseudotransformation has the signature of a transformation but is not regular.
[3] Notice the similarity to distance from Chapter 2.
[4] First introduced in Grassmann [1861]; Grassmann’s definition was popularized in Peano [1908].
[5] A function object can be used in this way.
[7] Some authors use nondecreasing and increasing instead of increasing and strictly increasing, respectively.
[8] The bisection technique dates back at least as far as the proof of the Intermediate Value Theorem in Bolzano [1817] and, independently, in Cauchy [1821]. While Bolzano and Cauchy used the technique for the most general case of continuous functions, Lagrange [1795] had previously used it to solve a particular problem of approximating a root of a polynomial. The first description of bisection for searching was John W. Mauchly’s lecture “Sorting and collating” [Mauchly, 1946].
[9] A similar STL function is called equal_range.
[10] In STL this is called a reverse iterator adapter.
[11] Two of the best-known algorithms for this problem are Boyer and Moore [1977] and Knuth, et al. [1977]. Musser and Nishanov [1997] serves as a good foundation for the abstract setting for these algorithms.
[1] Observe that find_adjacent_mismatch_forward in Chapter 6 used advance_tail implicitly.
[3] Link reversal was introduced in Schorr and Waite [1967] and was independently discovered by L. P. Deutsch. A version without tag bits was published in Robson [1973] and Morris [1979]. We show the particular technique of rotating the links due to Lindstrom [1973] and independently by Dwyer [1974].
[1] Jerry Schwarz suggests a potentially more elegant interface: replacing sink with a procedure store such that store(v, x) is equivalent to sink(x) ← v.
[2] The interface was suggested to us by T. K. Lakshman.
[1] A reverse algorithm could return the range of elements that were not moved: the middle element when the size of the range is odd or the empty range between the two “middle” elements when the size of the range is even. We do not know of an example when this return value is useful and, therefore, return void. Of course, for versions taking a counted range of forward iterators, it is useful to return the limit.
[2] Joseph Tighe suggests returning a pair, m and m′, in the order constituting a valid range; although it is an interesting suggestion and preserves all the information, we do not yet know of a compelling use of such an interface.
[3] The use of reverse_swap_ranges_bounded to determine m′ was suggested to us by Wilson Ho and Raymond Lo.
[1] Bentley [1984, pages 287–291] attributes the algorithm to Nico Lomuto.
[2] This lemma and the following exercise were suggested to us by Jon Brandt.
[3] See Hoare [1962] on the Quicksort algorithm. Because of the requirements of Quicksort, Hoare’s partition interchanges elements that are greater than or equal to a chosen element with elements that are less than or equal to the chosen element. A range of equal elements is divided in the middle. Observe that these two relations, ≤ and ≥, are not complements of each other.
[4] The technique is attributed to John McCarthy in Knuth [1998, Section 5.2.4 (Sorting by Merging), Exercise 17, page 167].
[5] The choice of 64 elements for the array handles any application on 64-bit architectures.
[6] Solving Exercise 9.5 explains the need for extracting the member m2.
[7] A similar algorithm was first described in John W. Mauchly’s lecture “Sorting and collating” [Mauchly, 1946].
[1] As with begin and end, overloading on constant is needed for a complete implementation.
[2] A complete implementation will also provide a constant iterator type, as a constant pointer to T, together with versions of begin and end overloaded on constant array_k that return the constant iterator type.
[4] The amortized complexity of an operation is the complexity averaged over a worst-case sequence of operations. The notion of amortized complexity was introduced in Tarjan [1985].
[5] Of course, it is possible to grow data from the back downward, but this does not appear to be practically useful.
[6] This is based on the original UNIX file system [see Thompson and Ritchie, 1974].
[7] This explains the warning against links from remote parts to the header in our discussion of doubly linked lists.
[1] The matching mechanism performs overload resolution by exact matching without any implicit conversions.
[2] To disambiguate between the use of < and > as relations or as template name delimiters, once a structure_name or procedure_name is parsed as part of a template, it becomes a terminal symbol.
[3] This implementation treats requirements as documentation only.
[4] Such a macro works only inside a template definition, because of the use of the keyword typename.