Appendix B. Generic Algorithms Handbook

Each generic algorithm, with the fistful of exceptions that make the rule, begins with a pair of iterators that marks the range of elements within the container over which to traverse. The range begins with the first iterator and ends with but does not include the second:

const int array_size = 7; 


int iarray[array_size] = { 1, 10, 8, 4, 3, 14, 8 }; 


vector<int> vec( iarray, iarray+ array_size ); 





vector<int>::iterator it = find( vec.begin(), vec.end(), value ); 


int *pi = find( iarray, iarray+array_size, value ); 

The algorithms are generally overloaded to support two versions: one that uses either the built-in equality or the less-than operator of the underlying element type, and a second one that accepts either a function object or a pointer to function providing an alternative implementation of that operator. For example, by default sort() orders the container elements using the less-than operator. To override that, we can pass in the predefined greater-than function object:

sort( vec.begin(), vec.end() ); 


sort( vec.begin(), vec.end(), greater<int>() ); 

Other algorithms, however, are separated into two uniquely named instances; the predicate instance in each case ends with the suffix _if, as in find_if(). For example, to find an element less than 10, we might write

find_if( vec.begin(), vec.end(), bind2nd( less<int>, 10 )) 

Many of the algorithms that modify the container they are applied to come in two flavors: an in-place version that changes the container, and a version that returns a copy of the container with the changes applied. For example, there is both a replace() and a replace_copy() algorithm. The copy version always contains _copy in its name. It accepts a third iterator that points to the first element of the container in which to copy the modified elements. By default, the copy is achieved by assignment. We can use one of three inserter adapters to override the assignment semantics and have the elements instead inserted. (See Section 3.9 for a discussion and examples.)

As programmers, we must quickly be able to look up which algorithms are available and how they are generally used. That is the purpose of this handbook. ^[1] The following built-in arrays, vectors, and lists are used as arguments to the algorithms:

^[1] This handbook is an abridged and recast version of the C++ Primer Appendix, which provides a program example and discussion of each generic algorithm. Here I've listed a subset of the algorithms that are, in my opinion, the most frequently used.

int ia[8]={ 1, 3, 6, 10, 15, 21, 28, 36 }; 


vector<int> ivec( ia, ia+8 ); 


list<int> ilist( ia, ia+8 ); 





string sa[10] = { "The", "light", "untonsured", "hair", 


     "grained", "and", "hued", "like", "pale", "oak" }; 


vector<string> svec( sa, sa+10 ); 


list<string> slist( sa, sa+10 ); 

Each listing provides a brief description of the algorithm, indicates the header file that must be included (either algorithm or numeric), and provides one or two usage examples.