Chapter 7. Generic Programming Using the STL

• Sequential search (in an array) function template (p137): findarray.C
• Sequential search (in an linked list) function template (p138): findllist.C
• Adapting the linked list interface to fit the generic sequential search template find.h (p140): findllist2.C.
• A naive implementation sum1.h of a generic sum function which adds up the elements in a range [ it1, it2[ defined by two iterators (p 143). A call to this version of sum must be explicitly instantiated as shown in sum1.C
• The above problem can be fixed by adding the return type to sum's signature, as shown in sum2.h (p 144). The program sum2.C illustrates the use of this kludge.
• A better solution is to define a I::value_type as the return type of sum where I is the iterator type. The new version of sum can be found in sum3.h (p 145). The program in sum3.C illustrates the use of this approach.
• Unfortunately, for an iterator type I that is not a class type, we cannot define I::value_type. (e.g. T* is an iterator type for arrays of T but not a class type).
  The solution is to define a ``compile-time'' function iterator_traits that returns (among others) the value_type associated with an iterator type. The value for iterator_traits<T*> is defined using template specialization, see iteratortraits.h (p 147). The new definition of sum is in sum4.h The program in sum4.C illustrates the approach.
• Dispatching on an iterator's category to obtain an algorithm that adapts itself to the iterator's capabilities is illustrated in advance.h and advance.C (p 148).
• The use of input stream iterators is illustrated in findword.C which uses the class Word from word.h (p 151).
• Writearray.C illustrates the use of output stream iterators (p 152).
• The list container type is illustrated in the program wordlist.C (p 155) that produces a sorted list of words in a text.
• The vector container type is illustrated in the program dict.C (p 157) that uses the Dictionary class (implemented using hashing with separate chaining) defined in dict.h.
• The map associative container type is illustrated in the program sparse.C (p 159) that uses the sparse matrix class defined in sparse.h.
• The set container type is illustrated in the program wordset.C that produces a sorted list of words in a text (it is shorter and probably faster than wordlist.C).