This chapter is from the book
This chapter is from the book
This chapter is from the book
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.