|< C++ STL algorithm 4 | Main | C++ STL Algorithm 6 >| Site Index | Download |


 

 

 

 

MODULE 34a_1

THE C++ STL ALGORITHM PART 5

 

 

 

 

 

My Training Period: xx hours

 

A continuation from previous Module, more examples, code samples compiled using Microsoft 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 in C++ 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?

  1. Algorithm, find_if() program example

  2. Algorithm, for_each() program example

  3. Algorithm, generate() program example

  4. Algorithm, generate_n() program example

  5. Algorithm, includes() program example

  6. Algorithm, copy() program example - g++

  7. Algorithm, find_first_of() program example - g++

 

find_if()

  • Locates the position of the first occurrence of an element in a range that satisfies a specified condition.

template<class InputIterator, class Predicate> InputIterator find_if( InputIterator _First, InputIterator _Last, Predicate _Pred );

Parameters

 

Parameter

Description

_First

An input iterator addressing the position of the first element in the range to be searched.

_Last

An input iterator addressing the position one past the final element in the range to be searched

_Pred

User-defined predicate function object that defines the condition to be satisfied by the element being searched for. A predicate takes single argument and returns true or false.

 

Table 34.15

  • The return value is an input iterator that addresses the first element in the range that satisfies the condition specified by the predicate.

  • This template function is a generalization of the algorithm find(), replacing the predicate "equals a specific value" with any predicate.

// 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:

 

C++ STL Algorithm find_if()

 

for_each()

template<class InputIterator, class Function> Function for_each( InputIterator _First, InputIterator _Last, Function _Func );

Parameters

 

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

// 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;

}

 

Output:

 

C++ STL Algorithm for_each()

 

generate()

template<class ForwardIterator, class Generator> void generate( ForwardIterator _First, ForwardIterator _Last, Generator _Gen );

 

Parameters

 

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

// 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;

}

 

Output:

 

C++ STL Algorithm generate()

 

generate_n()

template<class OutputIterator, class Size, class Generator> void generate_n( OutputIterator _First, Size _Count, Generator _Gen );

 

Parameters

 

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

 

  • 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 dereferenceable and, within the sequence, the last position must be reachable from the first by incrementation.

  • The complexity is linear, with exactly _Count calls to the generator being required.

// 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;

}

 

Output:

 

C++ STL Algorithm generate_n()

 

includes()

  1. template<class InputIterator1, class InputIterator2>bool includes( InputIterator1 _First1, InputIterator1 _Last1, InputIterator2 _First2, InputIterator2 _Last1 );

  2. template<class InputIterator1, class InputIterator2, class BinaryPredicate>bool includes( InputIterator1 _First1, InputIterator1 _Last1, InputIterator2 _First2, InputIterator2 _Last1, BinaryPredicate _Comp );

Parameters

 

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

// 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:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

C++ STL Algorithm includes()

// ******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

 

 

tenouk C++ STL tutorial

 

 

 

 

 

 

 

 

 

 

 

Further C++ STL algorithm reading:

 

  1. Source code in text is available in C++ Algorithm source code sample.

  2. C++ Templates programming tutorials.

  3. A complete C & C++ Standard Library documentation that includes STL.

  4. Check the best selling C / C++ and STL books at Amazon.com.

 

 

 

 

 

 

|< C++ STL algorithm 4 | Main | C++ STL Algorithm 6 >| Site Index | Download |


C++ STL Algorithm Classes:  Part 1 | Part 2 | Part 3 | Part 4 | Part 5 | Part 6 | Part 7 | Part 8 | Part 9 | Part 10 | Part 11 | Part 12 | Part 13 | Part 14 | Part 15