|< C++ STL algorithm 3 | Main | C++ STL Algorithm 5 >| Site Index | Download |


 

 

 

 

 

 

MODULE 34a

THE C++ STL ALGORITHM PART 4

 

 

 

 

 

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.

 

 

 

 

 

The 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, equal_range() program example

  2. Algorithm, fill() program example

  3. Algorithm, fill_n() program example

  4. Algorithm, find() program example

  5. Algorithm, find_end() program example

  6. Algorithm, find_first_of() program example

 

 

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.

  1. template<class ForwardIterator, class Type>pair<ForwardIterator, ForwardIterator> equal_range( ForwardIterator _First, ForwardIterator _Last, const Type& _Val );

  2. template<class ForwardIterator, class Type, class Pr>pair<ForwardIterator, ForwardIterator> equal_range( ForwardIterator _First, ForwardIterator _Last, const Type& _Val, BinaryPredicate _Comp );

 

Parameters

 

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 in the ordered range that needs to be equivalent to the value of the element addressed by the first component of the pair returned and that needs to be less than the value of the element addressed by the second component of that pair returns.

_Comp

User-defined predicate function object that is true when the left-hand argument is less than the right-hand argument. The user-defined predicate function should return false when its arguments are equivalent.

 

Table 34.9

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

// algorithm, equal_range()

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

    vector <int>::iterator Iter1;

    pair < vector <int>::iterator, vector <int>::iterator > Result1, Result2, Result3;

    // constructing vectors vec1 with default less than ordering

    int i;

    for(i = -2; i <= 4; i++)

        vec1.push_back(i);

    int j;

    for(j =1; j <= 5; j++)

        vec1.push_back(j);

    sort(vec1.begin(), vec1.end());

    cout<<"vec1 data with range sorted by the binary predicate less than is:\n";

    for(Iter1 = vec1.begin(); Iter1 != vec1.end(); Iter1++)

        cout<<*Iter1<<" ";

    cout<<endl;

    // constructing vectors vec2 with range sorted by greater

    vector <int> vec2(vec1);

    vector <int>::iterator Iter2;

    sort(vec2.begin(), vec2.end(), greater<int>());

    cout<<"\nvec2 data with range sorted by the binary predicate greater than is:\n";

    for(Iter2 = vec2.begin(); Iter2 != vec2.end(); Iter2++)

        cout<<*Iter2<<" ";

    cout<<endl;

    // constructing vectors vec3 with range sorted by mod_lesser

    vector <int> vec3(vec1);

    vector <int>::iterator Iter3;

    sort(vec3.begin(), vec3.end(), mod_lesser);

    cout<<"\nvec3 data with range sorted by the binary predicate mod_lesser is:\n";

    for(Iter3 = vec3.begin(); Iter3 != vec3.end(); Iter3++)

        cout<<*Iter3<<" ";

    cout<<"\n\n";

    // equal_range of 4 in vec1 with default binary predicate less <int>()

    Result1 = equal_range(vec1.begin(), vec1.end(), 4);

    cout<<"lower_bound in vec1 for the element with a value of 4 is: "<<*Result1.first<<endl;

    cout<<"upper_bound in vec1 for the element with a value of 4 is: "<<*Result1.second<<endl;

    cout<<"The equivalence class for the element with a value of 4 in \nvec1 includes the elements: ";

    for(Iter1 = Result1.first; Iter1 != Result1.second; Iter1++)

        cout<<*Iter1<<" ";

    cout<<endl<<endl;

    // equal_range of 4 in vec2 with the binary predicate greater <int>()

    Result2 = equal_range(vec2.begin(), vec2.end(), 4, greater <int>());

    cout<<"lower_bound in vec2 for the element with a value of 4 is: "<<*Result2.first<<endl;

    cout<<"upper_bound in vec2 for the element with a value of 4 is: "<<*Result2.second<<endl;

    cout<<"The equivalence class for the element with a value of 4 in"\n vec2 includes the elements: ";

    for(Iter2 = Result2.first; Iter2 != Result2.second; Iter2++)

        cout<<*Iter2<<" ";

    cout<<endl<<endl;

    // equal_range of 4 in vec3 with the binary predicate mod_lesser

    Result3 = equal_range(vec3.begin(), vec3.end(), 4, mod_lesser);

    cout<<"lower_bound in vec3 for the element with a value of 4 is: "<<*Result3.first<<endl;

    cout<<"upper_bound in vec3 for the element with a value of 4 is: "<<*Result3.second<<endl;

    cout<<"equivalence class for the element with a value of 4 in \nvec3 includes the elements: ";

    for(Iter3 = Result3.first; Iter3 != Result3.second; Iter3++)

        cout<<*Iter3<<" ";

    cout<<endl<<endl;

    return 0;

}

 

Output:

C++ STL Algorithm equal_range()

 

fill()

template<class ForwardIterator, class Type> void fill( ForwardIterator _First, ForwardIterator _Last, const Type& _Val );

Parameters

 

Parameter

Description

_First

A forward iterator addressing the position of the first element in the range to be traversed.

_Last

A forward iterator addressing the position one past the final element in the range to be traversed.

_Val

The value to be assigned to elements in the range [_First, _Last).

 

Table 34.10

// algorithm, fill()

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

 

int main()

{

    vector <int> vec;

    vector <int>::iterator Iter1;

    int i;

    for(i = 10; i <= 20; i++)

        vec.push_back(i);

    cout<<"Vector vec data: ";

    for(Iter1 = vec.begin(); Iter1 != vec.end(); Iter1++)

        cout<<*Iter1<<" ";

    cout<<endl;

    // fill the last 4 positions with a value of 9

    cout<<"\nOperation: fill(vec.begin() + 4, vec.end(), 9)\n";

    fill(vec.begin() + 4, vec.end(), 9);

    cout<<"Modified vec data: ";

    for(Iter1 = vec.begin(); Iter1 != vec.end(); Iter1++)

        cout<<*Iter1<<" ";

    cout<<endl;

    return 0;

}

 

Output:

 

C++ STL Algorithm fill()

 

fill_n()

template<class OutputIterator, class Size, class Type> void fill_n( OutputIterator _First, Size _Count, const Type& _Val );

Parameters

 

Parameter

Description

_First

An output iterator addressing the position of the first element in the range to be assigned the value _Val.

_Count

A signed or unsigned integer type specifying the number of elements to be assigned the value.

_Val

The value to be assigned to elements in the range [_First, _First + _Count).

 

Table 34.11

// algorithm, fill_n()

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

 

int main()

{

    vector <int> vec;

    vector <int>::iterator Iter1;

    int i;

    for(i = 10; i <= 20; i++)

        vec.push_back(i);

    cout<<"Vector vec data: ";

    for(Iter1 = vec.begin(); Iter1 != vec.end(); Iter1++)

        cout<<*Iter1<<" ";

    cout<<endl;

    // fill the last 3 positions for 6 position with a value of 9

    cout<<"\nOperation: fill_n(vec.begin() + 3, 6, 9)\n";

    fill_n(vec.begin() + 3, 6, 9);

    cout<<"Modified vec data: ";

    for(Iter1 = vec.begin(); Iter1 != vec.end(); Iter1++)

        cout<<*Iter1<<" ";

    cout<<endl;

    return 0;

}

 

Output:

 

C++ STL Algorithm fill_n()

 

find()

template<class InputIterator, class Type> InputIterator find( InputIterator _First, InputIterator _Last, const Type& _Val );

Parameters

 

Parameter

Description

_First

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

_Last

An input iterator addressing the position one past the final element in the range to be searched for the specified value.

_Val

The value to be searched for.

 

Table 34.12

// algorithm, find()

#include <list>

#include <algorithm>

#include <iostream>

using namespace std;

 

int main()

{

    list <int> lst;

    list <int>::iterator Iter;

    list <int>::iterator result;

    lst.push_back(9);

    lst.push_back(21);

    lst.push_back(14);

    lst.push_back(10);

    lst.push_back(16);

    lst.push_back(31);

    cout<<"List lst data: ";

    for(Iter = lst.begin(); Iter != lst.end(); Iter++)

        cout<<*Iter<<" ";

    cout<<endl;

    cout<<"\nOperation: find(lst.begin(), lst.end(), 14)\n";

    result = find(lst.begin(), lst.end(), 14);

    if(result == lst.end())

        cout<<"There is no 14 in list lst."<<endl;

    else

        result++;

    cout<<"There is a 14 in list lst and it is"<<" followed by a "<<*(result)<<endl;

    return 0;

}

 

Output:

 

C++ STL Algorithm find()

 

find_end()

  1. template<class ForwardIterator1, class ForwardIterator2>ForwardIterator1 find_end( ForwardIterator1 _First1, ForwardIterator1 _Last1, ForwardIterator2 _First2, ForwardIterator2 _Last2 );

  2. template<class ForwardIterator1, class ForwardIterator2, class Pr>ForwardIterator1 find_end( ForwardIterator1 _First1, ForwardIterator1 _Last1, ForwardIterator2 _First2, ForwardIterator2 _Last2, BinaryPredicate _Comp );

Parameters

 

Parameter

Description

_First1

A forward iterator addressing the position of the first element in the range to be searched.

_Last1

A forward iterator addressing the position one past the final element in the range to be searched.

_First2

A forward iterator addressing the position of the first element in the range to be searched.

_Last2

A forward iterator addressing the position one past the final element in the range to be searched.

_Comp

User-defined predicate function object that defines the condition to be satisfied if two elements are to be taken as equivalent. A binary predicate takes two arguments and returns true when satisfied and false when not satisfied.

 

Table 34.13

// algorithm, find_end()

//some type conversion warning

#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 = 10; i <= 15; i++)

        vec1.push_back(i);

    int j;

    for(j = 11; j <= 14; j++)

        lst.push_back(j);

    int k;

    for(k = 12; k <= 14; k++)

        vec2.push_back(2*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<<endl;

    // searching vec1 for a match to lst under identity

    vector <int>::iterator result1;

    result1 = find_end(vec1.begin(), vec1.end(), lst.begin(), lst.end());

    if(result1 == vec1.end())

        cout<<"There is no match of lst in vec1."<<endl;

    else

        cout<<"There is a match of lst in vec1 that 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_end(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 "

                <<"predicate\ntwice and that begins at position "<<result2 - vec1.begin()<<endl;

    return 0;

}

 

Output:

 

C++ STL Algorithm find_end()

 

find_first_of()

  1. template<class ForwardIterator1, class ForwardIterator2>ForwardIterator1 find_first_of( ForwardIterator1 _First1, ForwardIterator1 _Last1, ForwardIterator2 _First2, ForwardIterator2 _Last2 );

  2. template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>ForwardIterator1 find_first_of( ForwardIterator1 _First1, ForwardIterator1 _Last1, ForwardIterator2 _First2, ForwardIterator2 _Last2, BinaryPredicate _Comp );

Parameters

 

Parameter

Description

_First1

A forward iterator addressing the position of the first element in the range to be searched.

_Last1

A forward iterator addressing the position one past the final element in the range to be searched.

_First2

A forward iterator addressing the position of the first element in the range to be matched.

_Last2

A forward iterator addressing the position one past the final element in the range to be matched.

_Comp

User-defined predicate function object that defines the condition to be satisfied if two elements are to be taken as equivalent. A binary predicate takes two arguments and returns true when satisfied and false when not satisfied.

 

Table 34.14

// algorithm, find_first_of()

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

}

 

Output:

 

C++ STL Algorithm find_first_of()

 

 

tenouk C++ STL tutorial

 

 

 

 

 

 

 

 

 

 

 

Further C++ STL algorithm reading:

 

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

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

  3. C++ Templates programming tutorials.

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

 

 

 

 

 

 

|< C++ STL algorithm 3 | Main | C++ STL Algorithm 5 >| 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