Continue from the previous Module, more algorithm member functions program examples. Compiled using MicrosoftVisual C++/.Net, win32 empty console mode application. g++ compilation on Fedora Core 3 examples given at the end of this Module. Source code in text is available inC++ Algorithm source code sample.
 34.1 The <algorithm> Header File
#include <algorithm>

The following table is a list of the member functions available in<algorithm>. So many huh!
Member function  Description 
adjacent_find()  Searches for two adjacent elements that are either equal or satisfy a specified condition. 
binary_search()  Tests whether there is an element in a sorted range that is equal to a specified value or that is equivalent to it in a sense specified by a binary predicate. 
copy()  Assigns the values of elements from a source range to a destination range, iterating through the source sequence of elements and assigning them new positions in a forward direction. 
copy_backward()  Assigns the values of elements from a source range to a destination range, iterating through the source sequence of elements and assigning them new positions in a backward direction. 
count()  Returns the number of elements in a range whose values match a specified value. 
count_if()  Returns the number of elements in a range whose values match a specified condition. 
equal()  Compares two ranges element by element either for equality or equivalence in a sense specified by a binary predicate. 
equal_range()  Finds a pair of positions in an ordered range, the first less than or equivalent to the position of a specified element and the second greater than the element's position, where the sense of equivalence or ordering used to establish the positions in the sequence may be specified by a binary predicate. 
fill()  Assigns the same new value to every element in a specified range. 
fill_n()  Assigns a new value to a specified number of elements in a range beginning with a particular element. 
find()  Locates the position of the first occurrence of an element in a range that has a specified value. 
find_end()  Looks in a range for the last subsequence that is identical to a specified sequence or that is equivalent in a sense specified by a binary predicate. 
find_first_of()  Searches for the first occurrence of any of several values within a target range or for the first occurrence of any of several elements that are equivalent in a sense specified by a binary predicate to a specified set of the elements. 
find_if()  Locates the position of the first occurrence of an element in a range that satisfies a specified condition. 
for_each()  Applies a specified function object to each element in a forward order within a range and returns the function object. 
generate()  Assigns the values generated by a function object to each element in a range. 
generate_n()  Assigns the values generated by a function object to a specified number of element is a range and returns to the position one past the last assigned value. 
includes()  Tests whether one sorted range contains all the elements contained in a second sorted range, where the ordering or equivalence criterion between elements may be specified by a binary predicate. 
inplace_merge()  Combines the elements from two consecutive sorted ranges into a single sorted range, where the ordering criterion may be specified by a binary predicate. 
iter_swap()  Exchanges two values referred to by a pair of specified iterators. 
lexicographical_compare()  Compares element by element between two sequences to determine which is lesser of the two. 
lower_bound()  Finds the position where the first element in an ordered range is or would be if it had a value that is less than or equivalent to a specified value, where the sense of equivalence may be specified by a binary predicate. 
make_heap()  Converts elements from a specified range into a heap in which the first element is the largest and for which a sorting criterion may be specified with a binary predicate. 
max()  Compares two objects and returns the larger of the two, where the ordering criterion may be specified by a binary predicate. 
max_element()  Finds the first occurrence of largest element in a specified range where the ordering criterion may be specified by a binary predicate. 
merge()  Combines all the elements from two sorted source ranges into a single, sorted destination range, where the ordering criterion may be specified by a binary predicate. 
min()  Compares two objects and returns the lesser of the two, where the ordering criterion may be specified by a binary predicate. 
min_element()  Finds the first occurrence of smallest element in a specified range where the ordering criterion may be specified by a binary predicate. 
mismatch()  Compares two ranges element by element either for equality or equivalent in a sense specified by a binary predicate and locates the first position where a difference occurs. 
next_permutation()  Reorders the elements in a range so that the original ordering is replaced by the lexicographically next greater permutation if it exists, where the sense of next may be specified with a binary predicate. 
nth_element()  Partitions a range of elements, correctly locating the nth element of the sequence in the range so that all the elements in front of it are less than or equal to it and all the elements that follow it in the sequence are greater than or equal to it. 
partial_sort()  Arranges a specified number of the smaller elements in a range into a nondescending order or according to an ordering criterion specified by a binary predicate. 
partial_sort_copy()  Copies elements from a source range into a destination range where the source elements are ordered by either less than or another specified binary predicate. 
partition()  Classifies elements in a range into two disjoint sets, with those elements satisfying a unary predicate preceding those that fail to satisfy it. 
pop_heap()  Removes the largest element from the front of a heap to the nexttolast position in the range and then forms a new heap from the remaining elements. 
prev_permutation()  Reorders the elements in a range so that the original ordering is replaced by the lexicographically next greater permutation if it exists, where the sense of next may be specified with a binary predicate. 
push_heap()  Adds an element that is at the end of a range to an existing heap consisting of the prior elements in the range. 
random_shuffle()  Rearranges a sequence of N elements in a range into one of N! possible arrangements selected at random. 
remove()  Eliminates a specified value from a given range without disturbing the order of the remaining elements and returning the end of a new range free of the specified value. 
remove_copy()  Copies elements from a source range to a destination range, except that elements of a specified value are not copied, without disturbing the order of the remaining elements and returning the end of a new destination range. 
remove_copy_if()  Copies elements from a source range to a destination range, except that satisfying a predicate are not copied, without disturbing the order of the remaining elements and returning the end of a new destination range. 
remove_if()  Eliminates elements that satisfy a predicate from a given range without disturbing the order of the remaining elements and returning the end of a new range free of the specified value. 
replace()  Examines each element in a range and replaces it if it matches a specified value. 
replace_copy()  Examines each element in a source range and replaces it if it matches a specified value while copying the result into a new destination range. 
replace_copy_if()  Examines each element in a source range and replaces it if it satisfies a specified predicate while copying the result into a new destination range. 
replace_if()  Examines each element in a range and replaces it if it satisfies a specified predicate. 
reverse()  Reverses the order of the elements within a range. 
reverse_copy()  Reverses the order of the elements within a source range while copying them into a destination range 
rotate()  Exchanges the elements in two adjacent ranges. 
rotate_copy()  Exchanges the elements in two adjacent ranges within a source range and copy the result to a destination range. 
search()  Searches for the first occurrence of a sequence within a target range whose elements are equal to those in a given sequence of elements or whose elements are equivalent in a sense specified by a binary predicate to the elements in the given sequence. 
search_n()  Searches for the first subsequence in a range that of a specified number of elements having a particular value or a relation to that value as specified by a binary predicate. 
set_difference()  Unites all of the elements that belong to one sorted source range, but not to a second sorted source range, into a single, sorted destination range, where the ordering criterion may be specified by a binary predicate. 
set_intersection()  Unites all of the elements that belong to both sorted source ranges into a single, sorted destination range, where the ordering criterion may be specified by a binary predicate. 
set_symmetric_difference()  Unites all of the elements that belong to one, but not both, of the sorted source ranges into a single, sorted destination range, where the ordering criterion may be specified by a binary predicate. 
set_union()  Unites all of the elements that belong to at least one of two sorted source ranges into a single, sorted destination range, where the ordering criterion may be specified by a binary predicate. 
sort()  Arranges the elements in a specified range into a nondescending order or according to an ordering criterion specified by a binary predicate. 
sort_heap()  Converts a heap into a sorted range. 
stable_partition()  Classifies elements in a range into two disjoint sets, with those elements satisfying a unary predicate preceding those that fail to satisfy it, preserving the relative order of equivalent elements. 
stable_sort()  Arranges the elements in a specified range into a nondescending order or according to an ordering criterion specified by a binary predicate and preserves the relative ordering of equivalent elements. 
swap()  Exchanges the values of the elements between two types of objects, assigning the contents of the first object to the second object and the contents of the second to the first. 
swap_ranges()  Exchanges the elements of one range with the elements of another, equal sized range. 
transform()  Applies a specified function object to each element in a source range or to a pair of elements from two source ranges and copies the return values of the function object into a destination range. 
unique()  Removes duplicate elements that are adjacent to each other in a specified range. 
unique_copy()  Copies elements from a source range into a destination range except for the duplicate elements that are adjacent to each other. 
upper_bound()  Finds the position of the first element in an ordered range that has a value that is greater than a specified value, where the ordering criterion may be specified by a binary predicate. 
Table 34.1 
The following section presents some of the program examples using the member functions. Notice the using of the containers and iterators in the program examples and in the function and class templates.
Searches for two adjacent elements that are either equal or satisfy a specified condition.
template<class ForwardIterator> ForwardIterator adjacent_find(ForwardIterator _First, ForwardIterator _Last);
template<class ForwardIterator , class BinaryPredicate>ForwardIterator adjacent_find( ForwardIterator _First, ForwardIterator _Last, BinaryPredicate _Comp );
Parameter  Description 
_First  A forward iterator addressing the position of the first element in the range to be searched. 
_Last  A forward iterator addressing the position one past the final element in the range to be searched. 
_Comp  The binary predicate giving the condition to be satisfied by the values of the adjacent elements in the range being searched. 
Table 34.2 
The return value is a forward iterator to the first element of the adjacent pair that are either equal to each other (in the first version) or that satisfy the condition given by the binary predicate (in the second version), provided that such a pair of elements is found. Otherwise, an iterator pointing to _Last is returned.
Theadjacent_find() algorithm is a nonmutating sequence algorithm. The range to be searched must be valid; all pointers must be dereferenceable and the last position is reachable from the first by incrementation. The time complexity of the algorithm is linear in the number of elements contained in the range.
Theoperator== used to determine the match between elements must impose an equivalence relation between its operands.
// algorithm, adjacent_find() #include <list> #include <algorithm> #include <iostream> using namespace std;
// returns whether second element is twice the first bool twice(int elem1, int elem2) { return (elem1 * 2 == elem2); }
int main() { list<int> lst; list<int>::iterator Iter; list<int>::iterator result1, result2; // construct a list container lst.push_back(14); lst.push_back(17); lst.push_back(31); lst.push_back(31); lst.push_back(10); lst.push_back(20); cout << "List lst data: "; for(Iter = lst.begin(); Iter != lst.end(); Iter++) cout<<*Iter<< " "; cout<<endl<<endl; result1 = adjacent_find(lst.begin(), lst.end()); if(result1 == lst.end()) cout<<"There are not two adjacent elements that are equal."<<endl; else cout<<"There are two adjacent elements that are equal.\nThey have a value of "<<*(result1)<<endl; result2 = adjacent_find(lst.begin(), lst.end(), twice); if(result2 == lst.end()) cout<<"\nThere are no two adjacent elements where the second is twice the first."<<endl; else { cout<<"\nThere are two adjacent elements\nwhere the second is twice the first.\nThey have values of "<<*(result2++); cout<<" & "<<*result2<<endl; } return 0; } 
Tests whether there is an element in a sorted range that is equal to a specified value or that is equivalent to it in a sense specified by a binary predicate.
template<class ForwardIterator, class Type> bool binary_search( ForwardIterator _First, ForwardIterator _Last, const Type& _Val );
template<class ForwardIterator, class Type, class BinaryPredicate>bool binary_search( ForwardIterator _First, ForwardIterator _Last, const Type& _Val, BinaryPredicate _Comp );
Parameter  Description 
_First  A forward iterator addressing the position of the first element in the range to be searched. 
_Last  A forward iterator addressing the position one past the final element in the range to be searched. 
_Val  The value required to be matched by the value of the element or that must satisfy the condition with the element value specified by the binary predicate. 
_Comp  Userdefined predicate function object that defines sense in which one element is less than another. A binary predicate takes two arguments and returns true when satisfied and false when not satisfied. 
Table 34.3 
The return value is true if an element is found in the range that is equal or equivalent to the specified value; otherwise, false.
The sorted source range referenced must be valid; all pointers must be dereferenceable and, within the sequence, the last position must be reachable from the first by incrementation.
The sorted range must each be arranged as a precondition to the application of the binary_search() algorithm in accordance with the same ordering as is to be used by the algorithm to sort the combined ranges.
The source ranges are not modified by binary_search().
The value types of the forward iterators need to be lessthan comparable to be ordered, so that, given two elements, it may be determined either that they are equivalent (in the sense that neither is less than the other) or that one is less than the other. This results in an ordering between the nonequivalent elements
The complexity of the algorithm is logarithmic for randomaccess iterators and linear otherwise, with the number of steps proportional to (_Last1–_First1).
// algorithm, binary_search()
#include <list>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
// return whether modulus of elem1 is less than modulus of elem2
bool mod_lesser(int elem1, int elem2)
{
if(elem1 < 0)
elem1 =  elem1;
if(elem2 < 0)
elem2 =  elem2;
return (elem1 < elem2);
}
int main()
{
list<int> lst;
list<int>::iterator Iter;
bool b1, b2;
lst.push_back(13);
lst.push_back(23);
lst.push_back(10);
lst.push_back(33);
lst.push_back(35);
lst.push_back(9);
lst.sort();
cout<<"List lst data: ";
for(Iter = lst.begin(); Iter != lst.end(); Iter++)
cout<<*Iter<<" ";
cout<<endl;
b1 = binary_search(lst.begin(), lst.end(), 10);
if(b1)
cout<<"\nThere is an element in list lst with\na value equal to 10."<<endl;
else
cout<<"\nThere is no element in list lst with\na value equal to 10."<<endl;
b2 = binary_search(lst.begin(), lst.end(), 13, greater<int>());
if(b2)
cout<<"\nThere is an element in list lst with a\nvalue equivalent to 13 under greater than."<<endl;
else
cout<<"\nNo element in list lst with a\nvalue equivalent to 13 under greater than."<<endl;
// a binary_search under the userdefined binary predicate mod_lesser
vector <int> vec;
vector <int>::iterator Iter1;
int i;
for(i = 3; i <= 5; i++)
vec.push_back(i);
sort(vec.begin(), vec.end(), mod_lesser);
cout<<"\nOrdered under mod_lesser, vector vec data:\n";
for(Iter1 = vec.begin(); Iter1 != vec.end(); Iter1++)
cout<<*Iter1<<" ";
cout<<endl;
bool b3 = binary_search(vec.begin(), vec.end(), 2, mod_lesser);
if(b3)
cout<<"\nThere is an element with a value\nequivalent to 2 under mod_lesser()."<<endl;
else
cout<<"\nThere is no element with a value\nequivalent to 2 under mod_lesser()."<<endl;
return 0;
}
Assigns the values of elements from a source range to a destination range, iterating through the source sequence of elements and assigning them new positions in a forward direction.
template<class InputIterator, class OutputIterator> OutputIterator copy( InputIterator _First, InputIterator _Last, OutputIterator _DestBeg );
Parameter  Description 
_First  An input iterator addressing the position of the first element in the source range. 
_Last  An input iterator addressing the position that is one past the final element in the source range. 
_DestBeg  An output iterator addressing the position of the first element in the destination range. 
Table 34.4 
The return value is an output iterator addressing the position that is one past the final element in the destination range, that is, the iteratoraddresses _Result + (_Last – _First).
The source range must be valid and there must be sufficient space at the destination to hold all the elements being copied.
Because the algorithm copies the source elements in order beginning with the first element, the destination range can overlap with the source range provided the _First position of the source range is not contained in the destination range.
copy() can be used to shift elements to the left but not the right, unless there is no overlap between the source and destination ranges. To shift to the right any number of positions, use thecopy_backward() algorithm.
Thecopy() algorithm only modifies values pointed to by the iterators, assigning new values to elements in the destination range. It cannot be used to create new elements and cannot insert elements into an empty container directly.
// algorithm, copy()
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
vector <int> vec1, vec2;
vector <int>::iterator Iter1, Iter2;
int i;
for(i = 0; i <= 5; i++)
vec1.push_back(i);
int j;
for(j = 10; j <= 20; j++)
vec2.push_back(j);
cout<<"vec1 data: ";
for(Iter1 = vec1.begin(); Iter1 != vec1.end(); Iter1++)
cout<<*Iter1<<" ";
cout<<endl;
cout<<"vec2 data: ";
for(Iter2 = vec2.begin(); Iter2 != vec2.end(); Iter2++)
cout<<*Iter2<<" ";
cout<<endl;
// to copy the first 4 elements of vec1 into the middle of vec2
copy(vec1.begin(), vec1.begin() + 4, vec2.begin() + 5);
cout<<"vec2 with vec1 insert data: ";
for(Iter2 = vec2.begin(); Iter2 != vec2.end(); Iter2++)
cout<<*Iter2<<" ";
cout<<endl;
// to shift the elements inserted into vec2 two positions to the left
copy(vec2.begin()+4, vec2.begin() + 7, vec2.begin() + 2);
cout<<"vec2 with shifted insert data: ";
for(Iter2 = vec2.begin(); Iter2 != vec2.end(); Iter2++)
cout<<*Iter2<<" ";
cout<<endl;
return 0;
}
Acomplete C++ Standard Library documentation that includes STL.
Source code in text is available inC++ Algorithm source code sample.