A continuation from previous Module, more examples, code samples compiled usingMicrosoft Visual 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.
| C++ STL algorithm skills that supposed to be acquired:
▪ Able to understand and use the member functions of the algorithm.▪ Learn how to use the template classes and functions.▪ Able to use containers, iterators and algorithm all together.
What do we have in this page?
find_if()
Parameters
// algorithm, find_if() #include <list> #include <algorithm> #include <iostream> using namespace std;
bool great(int value) {return value>13;}
int main() { list <int> lst; list <int>::iterator Iter; list <int>::iterator result; lst.push_back(13); lst.push_back(9); lst.push_back(10); lst.push_back(22); lst.push_back(31); lst.push_back(17); cout<<"List lst data: "; for(Iter = lst.begin(); Iter != lst.end(); Iter++) cout<<*Iter<<" "; cout<<endl; cout<<"\nOperation: find_if(lst.begin(), lst.end(), great)\n"; result = find_if(lst.begin(), lst.end(), great); if(result == lst.end()) cout<<"There is no element greater than 13 in list lst."<<endl; else result++; cout<<"There is an element greater than 13\nin list lst, and it is followed by a "<<*(result)<<endl; return 0; }
Output:
|
Applies a specified function object to each element in a forward order within a range and returns the function object.
template<class InputIterator, class Function> Function for_each( InputIterator _First, InputIterator _Last, Function _Func );
Parameter | Description |
_First | An input iterator addressing the position of the first element in the range to be operated on. |
_Last | An input iterator addressing the position one past the final element in the range operated on. |
_Func | User-defined function object that is applied to each element in the range. |
Table 34.16 |
The return value is a copy of the function object after it has been applied to all of the elements in the range.
The algorithm for_each() is very flexible, allowing the modification of each element within a range in different, user-specified ways. You will also find for_each in PHP library.
Templatized functions may be reused in a modified form by passing different parameters. User-defined functions may accumulate information within an internal state that the algorithm may return after processing all of the elements in the range.
The range referenced must be valid; all pointers must be de-referenceable and, within the sequence, the last position must be reachable from the first by incrementation.
The complexity is linear with at most (_Last – _First) comparisons.
// algorithm, for_each()
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
// the function object multiplies an element by a Factor
template <class Type>
class MultValue
{
private:
// the value to multiply by
Type Factor;
public:
// constructor initializes the value to multiply by
MultValue(const Type& _Val) : Factor(_Val) { }
// the function call for the element to be multiplied
void operator()(Type& elem) const
{ elem *= Factor; }
};
// the function object to determine the average
class Average
{
private:
// the number of elements
long num;
// the sum of the elements
long sum;
public:
// constructor initializes the value to multiply by
Average() : num(0), sum(0){ }
// the function call to process the next element
void operator()( int elem ) \
{
// increment the element count
num++;
// add the value to the partial sum
sum += elem;
}
// return Average
operator double()
{ return (static_cast <double> (sum))/(static_cast <double> (num)); }
};
int main()
{
vector <int> vec;
vector <int>::iterator Iter1;
// constructing vector vec
int i;
for(i = -3; i <= 4; i++)
vec.push_back(i);
cout<<"vector vec data: ";
for(Iter1 = vec.begin(); Iter1 != vec.end(); Iter1++)
cout<<*Iter1<<" ";
cout<<endl;
// using for_each to multiply each element by a Factor
for_each(vec.begin(), vec.end(), MultValue<int>(-2));
cout<<"\nMultiplying the elements of the vector vec\n"
<<"by the factor -2 gives:\nvecmult1 data: ";
for(Iter1 = vec.begin(); Iter1 != vec.end(); Iter1++)
cout<<*Iter1<<" ";
cout<<endl;
// the function object is templatized and so can be used again on the elements with a different Factor
for_each(vec.begin(), vec.end(), MultValue<int>(5));
cout<<"\nMultiplying the elements of the vector vecmult1\n"
<<"by the factor 5 gives:\nvecmult2 data: ";
for(Iter1 = vec.begin(); Iter1 != vec.end(); Iter1++)
cout<<*Iter1<<" ";
cout<<endl;
// the local state of a function object can accumulate information about a sequence of actions that the
// return value can make available, here the Average
double avemod2 = for_each(vec.begin(), vec.end(), Average());
cout<<"\nThe average of the elements of vec is:\nAverage(vecmult2) = "<<avemod2<<endl;
return 0;
}
Assigns the values generated by a function object to each element in a range.
template<class ForwardIterator, class Generator> void generate( ForwardIterator _First, ForwardIterator _Last, Generator _Gen );
Parameter | Description |
_First | A forward iterator addressing the position of the first element in the range to which values are to be assigned. |
_Last | A forward iterator addressing the position one past the final element in the range to which values are to be assigned. |
_Gen | A function object that is called with no arguments that is used to generate the values to be assigned to each of the elements in the range. |
Table 34.17 |
The function object is invoked for each element in the range and does not need to return the same value each time it is called. It may, for example, read from a file or refer to and modify a local state.
The generator's result type must be convertible to the value type of the forward iterators for the range.
The range referenced must be valid; all pointers must be de-referenceable and, within the sequence, the last position must be reachable from the first by incrementation.
The complexity is linear, with exactly (_Last – _First) calls to the generator being required.
// algorithm, generate()
#include <vector>
#include <deque>
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
// assigning random values to vector integer elements
vector <int> vec(5);
vector <int>::iterator Iter1;
deque <int> deq(5);
deque <int>::iterator deqIter;
cout<<"\nOperation: generate(vec.begin(), vec.end(), rand)\n";
generate(vec.begin(), vec.end(), rand);
cout<<"Vector vec data: ";
for(Iter1 = vec.begin(); Iter1 != vec.end(); Iter1++)
cout<<*Iter1<<" ";
cout<<endl;
// assigning random values to deque integer elements
cout<<"\nOperation: generate(deq.begin(), deq.end(), rand)\n";
generate(deq.begin(), deq.end(), rand);
cout<<"Deque deq data: ";
for(deqIter = deq.begin(); deqIter != deq.end(); deqIter++)
cout<<*deqIter<<" ";
cout<<endl;
return 0;
}
Assigns the values generated by a function object to a specified number of element in a range and returns to the position one past the last assigned value.
template<class OutputIterator, class Size, class Generator> void generate_n( OutputIterator _First, Size _Count, Generator _Gen );
Parameter | Description |
_First | An output iterator addressing the position of first element in the range to which values are to be assigned. |
_Count | A signed or unsigned integer type specifying the number of elements to be assigned a value by the generator function. |
_Gen | A function object that is called with no arguments that is used to generate the values to be assigned to each of the elements in the range. |
Table 34.18 |
// algorithm, generate_n() #include <vector> #include <deque> #include <algorithm> #include <iostream> using namespace std; |
int main()
{
// assigning random values to vector integer elements
vector <int> vec(7);
vector <int>::iterator Iter1;
deque <int> deq(7);
deque <int>::iterator deqIter;
cout<<"\nOperation: generate_n(vec.begin(), 7, rand)\n";
generate_n(vec.begin(), 7, rand);
cout<<"Vector vec data: ";
for(Iter1 = vec.begin(); Iter1 != vec.end(); Iter1++)
cout<<*Iter1<<" ";
cout<<endl;
// assigning random values to deque integer elements
cout<<"\nOperation: generate_n(deq.begin(), 4, rand)\n";
generate_n(deq.begin(), 4, rand);
cout<<"Deque deq data: ";
for(deqIter = deq.begin(); deqIter != deq.end(); deqIter++)
cout<<*deqIter<<" ";
cout<<endl;
return 0;
}
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.
template<class InputIterator1, class InputIterator2>bool includes( InputIterator1 _First1, InputIterator1 _Last1, InputIterator2 _First2, InputIterator2 _Last1 );
template<class InputIterator1, class InputIterator2, class BinaryPredicate>bool includes( InputIterator1 _First1, InputIterator1 _Last1, InputIterator2 _First2, InputIterator2 _Last1, BinaryPredicate _Comp );
Parameter | Description |
_First1 | An input iterator addressing the position of the first element in the first of two sorted source ranges to be tested for whether all the elements of the second are contained in the first. |
_Last1 | An input iterator addressing the position one past the last element in the first of two sorted source ranges to be tested for whether all the elements of the second are contained in the first. |
_First2 | An input iterator addressing the position of the first element in second of two consecutive sorted source ranges to be tested for whether all the elements of the second are contained in the first. |
_Last2 | An input iterator addressing the position one past the last element in second of two consecutive sorted source ranges to be tested for whether all the elements of the second are contained in the first. |
_Comp | User-defined 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.19 |
The return value is a true if the first sorted range contains all the elements in the second sorted range; otherwise, false.
Another way to think of this test is that it determined whether the second source range is a subset of the first source range.
The sorted source ranges referenced must be valid; all pointers must be de-referenceable and, within each sequence, the last position must be reachable from the first by incrementation.
The sorted source ranges must each be arranged as a precondition to the application of the algorithm includes 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 the algorithm merge().
The value types of the input iterators need be less than 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 non equivalent elements.
More precisely, the algorithm tests whether all the elements in the first sorted range under a specified binary predicate have equivalent ordering to those in the second sorted range.
The complexity of the algorithm is linear with at most 2*((_Last1 – _First1)–(_Last2 – _First2))–1 comparisons for nonempty source ranges.
// algorithm, includes()
#include <vector>
#include <algorithm>
// for greater<int>()
#include <functional>
#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()
{
vector <int> vec1, vec2;
vector <int>::iterator Iter1, Iter2;
// constructing vectors vec1 & vec2 with default less-than ordering
int i;
for(i = -2; i <= 4; i++)
vec1.push_back(i);
int j;
for(j =-2; j <= 3; j++)
vec2.push_back(j);
cout<<"vector vec1 data with range sorted by the binary predicate\nless than is: ";
for(Iter1 = vec1.begin(); Iter1 != vec1.end(); Iter1++)
cout<<*Iter1<<" ";
cout<<endl;
cout<<"\nvector vec2 data with range sorted by the "
<<"binary predicate\nless than is: ";
for(Iter2 = vec2.begin(); Iter2 != vec2.end(); Iter2++)
cout<<*Iter2<<" ";
cout<<endl;
// constructing vectors vec3 & vec4 with ranges sorted by greater
vector <int> vec3(vec1), vec4(vec2);
vector <int>::iterator Iter3, Iter4;
sort(vec3.begin(), vec3.end(), greater<int>());
sort(vec4.begin(), vec4.end(), greater<int>());
vec3.pop_back();
cout<<"\nvector vec3 data with range sorted by the binary predicate\ngreater is: ";
for(Iter3 = vec3.begin(); Iter3 != vec3.end(); Iter3++)
cout<<*Iter3<<" ";
cout<<endl;
cout<<"\nvector vec4 data with range sorted by the binary predicate\ngreater is: ";
for(Iter4 = vec4.begin(); Iter4 != vec4.end(); Iter4++)
cout<<*Iter4<<" ";
cout<<endl;
// constructing vectors vec5 & vec6 with ranges sorted by mod_lesser
vector <int> vec5(vec1), vec6(vec2);
vector <int>::iterator Iter5, Iter6;
reverse(vec5.begin(), vec5.end());
vec5.pop_back();
vec5.pop_back();
sort(vec5.begin(), vec5.end(), mod_lesser);
sort(vec6.begin(), vec6.end(), mod_lesser);
cout<<"\nvector vec5 data with range sorted by the binary predicate\nmod_lesser is: ";
for(Iter5 = vec5.begin(); Iter5 != vec5.end(); Iter5++)
cout<<*Iter5<<" ";
cout<<endl;
cout<<"\nvector vec6 data with range sorted by the binary predicate\nmod_lesser is: ";
for(Iter6 = vec6.begin(); Iter6 != vec6.end(); Iter6++)
cout<<*Iter6<<" ";
cout<<endl;
// to test for inclusion under an ascending order with the default binary predicate less <int>()
bool Result1;
Result1 = includes(vec1.begin(), vec1.end(), vec2.begin(), vec2.end());
if(Result1)
cout<<"\nAll the elements in vector vec2 are contained in vector vec1."<<endl;
else
cout<<"\nAt least one of the elements in vector vec2 is not contained in vector vec1."<<endl;
// to test for inclusion under descending order specifies binary predicate greater<int>()
bool Result2;
Result2 = includes(vec3.begin(), vec3.end(), vec4.begin(), vec4.end(), greater<int>());
if(Result2)
cout<<"\nAll the elements in vector vec4 are contained\nin vector vec3."<<endl;
else
cout<<"\nAt least one of the elements in vector vec4\nis not contained in vector vec3."<<endl;
// to test for inclusion under a user defined binary predicate mod_lesser
bool Result3;
Result3 = includes(vec5.begin(), vec5.end(), vec6.begin(), vec6.end(), mod_lesser);
if(Result3)
cout<<"\nAll the elements in vector vec6 are contained under\nmod_lesser in vector vec5."<<endl;
else
cout<<"\nAt least one of the elements in vector vec6 is not\ncontained under mod_lesser in vector vec5."<<endl;
return 0;
}
Output:
The following are program examples compiled usingg++.
// ******algocopy.cpp********
// algorithm, copy() - g++
#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;
}
[bodo@bakawali ~]$ g++ algocopy.cpp -o algocopy
[bodo@bakawali ~]$ ./algocopy
vec1 data: 0 1 2 3 4 5
vec2 data: 10 11 12 13 14 15 16 17 18 19 20
vec2 with vec1 insert data: 10 11 12 13 14 0 1 2 3 19 20
vec2 with shifted insert data: 10 11 14 0 1 0 1 2 3 19 20
// ******algofindfirstof.cpp********
// algorithm, find_first_of() - g++
#include <vector>
#include <list>
#include <algorithm>
#include <iostream>
using namespace std;
// return whether second element is twice the first
bool twice(int elem1, int elem2)
{return (2 * elem1 == elem2);}
int main()
{
vector <int> vec1, vec2;
list <int> lst;
vector <int>::iterator Iter1, Iter2;
list <int>::iterator lst_Iter, lst_inIter;
int i;
for(i = 0; i <= 5; i++)
vec1.push_back(5*i);
int j;
for(j = 3; j <= 4; j++)
lst.push_back(5*j);
int k;
for(k = 2; k <= 4; k++)
vec2.push_back(10*k);
cout<<"Vector vec1 data: ";
for(Iter1 = vec1.begin(); Iter1 != vec1.end(); Iter1++)
cout<<*Iter1<<" ";
cout<<endl;
cout<<"List lst data: ";
for(lst_Iter = lst.begin(); lst_Iter!= lst.end(); lst_Iter++)
cout<<*lst_Iter<<" ";
cout<<endl;
cout<<"Vector vec2 data: ";
for(Iter2 = vec2.begin(); Iter2 != vec2.end(); Iter2++)
cout<<*Iter2<<" ";
cout<<endl;
// searching vec1 for first match to lst under identity
vector <int>::iterator result1;
result1 = find_first_of(vec1.begin(), vec1.end(), lst.begin(), lst.end());
if(result1 == vec1.end())
cout<<"\nThere is no match of lst in vec1."<<endl;
else
cout<<"\nThere is at least one match of lst in vec1\nand the first one begins at position "<<result1 - vec1.begin()<<endl;
// searching vec1 for a match to lst under the binary predicate twice
vector <int>::iterator result2;
result2 = find_first_of(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), twice);
if(result2 == vec1.end())
cout<<"\nThere is no match of lst in vec1."<<endl;
else
cout<<"\nThere is a sequence of elements in vec1 that are\nequivalent to those in vec2 under the binary\n"
<<"predicate twice and the first one begins at position "<<result2 - vec1.begin()<<endl;
return 0;
}
[bodo@bakawali ~]$ g++ algofindfirstof.cpp -o algofindfirstof
[bodo@bakawali ~]$ ./algofindfirstof
Vector vec1 data: 0 5 10 15 20 25
List lst data: 15 20
Vector vec2 data: 20 30 40
There is at least one match of lst in vec1
and the first one begins at position 3
There is a sequence of elements in vec1 that are
equivalent to those in vec2 under the binary
predicate twice and the first one begins at position 2
Source code in text is available inC++ Algorithm source code sample.
Acomplete C++ Standard Library documentation that includes STL.