## Using the Generic Algorithms

To use the generic algorithms, we must include the associated
`algorithm` header file:

#include <algorithm>

Let's exercise the generic algorithms with our numeric sequence vector.
`is_elem()` must return `true` if a value is an element in the
sequence; otherwise, it returns `false`. Four possible generic search
algorithms are as follows:

`find()`searches an unordered collection marked by the iterator pair`first,last`for some value. If the value is found,`find()`returns an iterator addressing the value; otherwise, it returns an iterator addressing`last`.`binary_search()`searches a sorted collection. It returns`true`if the value is found; otherwise, it returns`false`.`binary_search()`is more efficient than`find()`.`count()`returns a count of the number of elements matching some value.`search()`matches a subsequence within a container. For example, given the sequence`{1,3,5,7,2,9}`, a search for the subsequence`{5,7,2}`returns an iterator to the beginning of the subsequence. If the subsequence is not present, an iterator to the end of the container is returned.

Because our vector is guaranteed to be in ascending order, our best choice is
the `binary_search()`:

#include <algorithm> bool is_elem( vector<int> &vec, int elem ) { // if the elem passed in is 34, the 9th element of // the Fibonacci sequence, but the stored sequence // only holds the first 6 elements: 1,1,2,3,5,8 // our search will not succeed. // Before we invoke binary_search(), // we must check here if we need to grow the sequence return binary_search( vec.begin(), vec.end(), elem ); }

As the comment before the invocation of `binary_search()` explains, we
must be sure that the numeric series contains element values sufficient to
include `elem`, were it a member of the series. One way to do that is to
test the largest element in the sequence against `elem`. If the largest
element is smaller than `elem`, we expand the sequence until its largest
element equals or exceeds `elem`.

One strategy for determining the largest element of the series is to use the
`max_element()` generic algorithm. `max_element()` is passed an
iterator pair marking the range of elements to traverse. It returns the largest
element within the vector. Here is our revised `is_elem()`:

#include <algorithm> // forward declaration extern bool grow_vec( vector<int>&, int ); bool is_elem( vector<int> &vec, int elem ) { int max_value = max_element( vec.begin(), vec.end() ); if ( max_value < elem ) return grow_vec( vec, elem ); if ( max_value == elem ) return true; return binary_search( vec.begin(), vec.end(), elem ); }

`grow_vec()` adds elements to the vector until an element in the
sequence is either equal to or greater than `elem`. If the sequence
element is equal to `elem`, it returns `true`; otherwise, it
returns `false`.

Of course, because our vector is in ascending order, we don't really
need to use `max_element()` to find the largest element; it is guaranteed
to be at position `vec.size()-1` for a nonempty vector:

int max_value = vec.empty() ? 0 : vec[vec.size()-1];

`binary_search()` requires that the container be sorted, but it is
left to the programmer to guarantee that. If we are unsure, we can
`copy()` our container into a second container:

vector<int> temp( vec.size() ); copy( vec.begin(), vec.end(), temp.begin() );

Now we `sort()` our temporary container before invoking
`binary_search()`:

sort( temp.begin(), temp.end() ); return binary_search( temp.begin(), temp.end(), elem );

`copy()` takes two iterators that mark the range of elements to copy.
A third iterator points to the first element of the target container. The
elements are then assigned in turn. It is our responsibility to make sure that
the target container is large enough to hold each element to be copied. If we
are not sure, we can use an inserter to override default assignment with
insertion.

Appendix B provides an example of using each generic algorithm.