|< 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 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.

for_each()

• 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 );

Parameters

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

}

Output:

generate()

• 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 );

Parameters

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

}

Output:

generate_n()

• 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 );

Parameters

 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:

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.

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

• 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

tenouk C++ STL tutorial

Further C++ STL algorithm reading:

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

2. C++ Templates programming tutorials.

3. Acomplete C Standard Library.

4. Acomplete C++ Standard Library documentation that includes STL.

5. Check thebest 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