|< C++ STL Algorithm 7 | Main | C++ STL Algorithm 9 >| Site Index | Download |


 

 

 

 

 

 

MODULE 35a

THE C++ STL ALGORITHM PART 8

 

 

 

 

 

 

 

 

My Training Period: xx hours

 

Continue from the previous Module, more member functions working examples, compiled using Microsoft Visual C++ .Net, win32 empty console mode application. g++ compilation example is given at the end of this Module. The source code for this tutorial is available in C++ STL Algorithm source codes.

 

The C++ STL algorithm abilities that supposed to be acquired:

 

  • Able to understand and use the member functions of the algorithm.

  • Appreciate the usage of the template classes and functions.

  • Able to use containers, iterators and algorithm all together.

 

What do we have in this session?

  1. Algorithm, min_element() program example

  2. Algorithm, mismatch() program example

  3. Algorithm, next_permutation() program example

  4. Algorithm, nth_element() program example

  5. Algorithm, partial_sort() program example

 

 

min_element()

  • Finds the first occurrence of smallest element in a specified range where the ordering criterion may be specified by a binary predicate.

  1. template<class ForwardIterator> ForwardIterator min_element( ForwardIterator _First, ForwardIterator _Last );

  2. template<class ForwardIterator, class BinaryPredicate>ForwardIterator min_element( ForwardIterator _First, ForwardIterator _Last, BinaryPredicate _Comp );

 

Parameters

 

Parameter

Description

_First

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

_Last

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

_Comp

User-defined predicate function object that defines the sense in which one element is greater than another. The binary predicate takes two arguments and should return true when the first element is less than the second element and false otherwise.

 

Table 35.10

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

// algorithm, min_element()

#include <vector>

#include <set>

#include <algorithm>

#include <iostream>

using namespace std;

 

class CInt;

ostream& operator<<(ostream& osIn, const CInt& rhs);

 

class CInt

{

    public:

       CInt(int n = 0) : m_nVal(n){}

       CInt(const CInt& rhs) : m_nVal( rhs.m_nVal ){}

       CInt& operator=(const CInt& rhs)

       {

           m_nVal = rhs.m_nVal;

           return *this;

       }

       bool operator<(const CInt& rhs) const

       {    return (m_nVal < rhs.m_nVal);    }

       friend ostream& operator<<(ostream& osIn, const CInt& rhs);

    private:

       int m_nVal;

};

 

inline ostream& operator<<(ostream& osIn, const CInt& rhs)

{

   osIn<<"CInt("<<rhs.m_nVal<<")";

   return osIn;

}

 

// return whether modulus of elem1 is greater 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()

{

    // searching a set container with elements of type CInt for the minimum element

    CInt ci1 = 4, ci2 = 12, ci3 = -4;

    set<CInt> st1;

    set<CInt>::iterator st1Iter, st2Iter, st3Iter;

    st1.insert(ci1);

    st1.insert(ci2);

    st1.insert(ci3);

    cout<<"st1 data: ";

    for(st1Iter = st1.begin(); st1Iter != --st1.end(); st1Iter++)

        cout<<*st1Iter<<",";

    st1Iter = --st1.end();

    cout<<*st1Iter<<endl;

    cout<<"\nOperation: min_element(st1.begin(), st1.end()).\n";

    st2Iter = min_element(st1.begin(), st1.end());

    cout<<"The smallest element in st1 is: "<<*st2Iter<<endl;

    // searching a vector with elements of type int for the maximum

    // element under default less than & mod_lesser binary predicates

    vector <int> vec1;

    vector <int>::iterator vec1Iter, vec2Iter, vec3Iter;

    int i;

    for(i = 1; i <= 4; i++)

        vec1.push_back(i);

    int j;

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

        vec1.push_back(-2*j);

    cout<<"\nVector vec1 data: ";

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

        cout<<*vec1Iter<<" ";

    cout<<endl;

    cout<<"\nOperation: min_element(vec1.begin(), vec1.end()).\n";

    vec2Iter = min_element(vec1.begin(), vec1.end());

    cout<<"The smallest element in vec1 is: "<<*vec2Iter<<endl;

    cout<<"\nOperation: min_element(vec1.begin(), vec1.end(), mod_lesser).\n";

    vec3Iter = min_element(vec1.begin(), vec1.end(), mod_lesser);

    cout<<"The smallest element in vec1 based on the mod_lesser\nbinary predicate is: "<<*vec3Iter<<endl;

    return 0;

}

 

Output:

 

C++ STL algorithm min_element() program example

 

mismatch()

  1. template<class InputIterator1, class InputIterator2>pair<InputIterator1, InputIterator2> mismatch( InputIterator1 _First1, InputIterator1 _Last1, InputIterator2 _First2 );

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

Parameters

 

Parameter

Description

_First1

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

_Last1

An input iterator addressing the position one past the final element in the first range to be tested.

_First2

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

_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 35.11

// algorithm, mismatch()

#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 (elem1 * 2 == 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 = 0; j <= 7; j++)

        lst.push_back(5*j);

    int k;

    for(k = 0; k <= 5; 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;

    // testing vec1 and lst for mismatch under identity

    pair<vector <int>::iterator, list <int>::iterator> result1;

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

    cout<<"\nOperation: mismatch(vec1.begin(), vec1.end(), lst.begin()).\n";

    if(result1.first == vec1.end())

        cout<<"The two ranges do not differ."<<endl;

    else

        cout<<"The fist mismatch is between "<<*result1.first<<" and "<<*result1.second<<endl;

    // modifying the lst

    cout<<"\nDo some operation on the lst...\n";

    lst_inIter = lst.begin();

    lst_inIter++;

    lst_inIter++;

    lst.insert(lst_inIter, 70);

    cout<<"The modified lst data: ";

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

        cout<<*lst_Iter<<" ";

    cout<<endl;

    // testing vec1 with modified lst for mismatch under identity

    cout<<"\nOperationa: mismatch(vec1.begin(), vec1.end(), lst.begin())\n";

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

    if(result1.first == vec1.end())

        cout<<"The two ranges do not differ."<<endl;

    else

        cout<<"The first mismatch is between "<<*result1.first<<" and "<<*result1.second<< endl;

    // test vec1 and vec2 for mismatch under the binary predicate twice

    pair<vector <int>::iterator, vector <int>::iterator> result2;

    cout<<"\nOperation: mismatch(vec1.begin(), vec1.end(), vec2.begin(), twice).\n";

    result2 = mismatch(vec1.begin(), vec1.end(), vec2.begin(), twice);

    if(result2.first == vec1.end())

        cout<<"The two ranges do not differ based on the\nbinary predicate twice."<<endl;

    else

        cout<<"The first mismatch is between "<<*result2.first<<" and "<<*result2.second<<endl;

    return 0;

}

 

Output

C++ STL algorithm mismatch() program example

 

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.

  1. template<class BidirectionalIterator> bool next_permutation(BidirectionalIterator _First, BidirectionalIterator _Last );

  2. template<class BidirectionalIterator, class BinaryPredicate>bool next_permutation( BidirectionalIterator _First, BidirectionalIterator _Last, BinaryPredicate _Comp );

Parameters

 

Parameter

Description

_First

A bidirectional iterator pointing to the position of the first element in the range to be permuted.

_Last

A bidirectional iterator pointing to the position one past the final element in the range to be permuted.

_Comp

User-defined predicate function object that defines the comparison criterion to be satisfied by successive elements in the ordering. A binary predicate takes two arguments and returns true when satisfied and false when not satisfied.

 

Table 35.12

 

// algorithm, next_permutation()

#include <vector>

#include <deque>

#include <algorithm>

#include <iostream>

using namespace std;

 

class CInt;

ostream& operator<<(ostream& osIn, const CInt& rhs);

 

class CInt

{

    public:

       CInt(int n = 0) : m_nVal(n){}

       CInt(const CInt& rhs) : m_nVal(rhs.m_nVal){}

       CInt& operator=(const CInt& rhs)

       {    m_nVal = rhs.m_nVal; return *this;    }

       bool operator<(const CInt& rhs) const

       {    return (m_nVal < rhs.m_nVal);    }

       friend ostream& operator<<(ostream& osIn, const CInt& rhs);

    private:

       int m_nVal;

};

 

inline ostream& operator<<(ostream& osIn, const CInt& rhs)

{

   osIn<<"CInt("<<rhs.m_nVal<<")";

   return osIn;

}

 

// 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()

{

    // re-ordering the elements of type CInt in a deque using the prev_permutation algorithm

    CInt ci1 = 7, ci2 = 5, ci3 = 17;

    bool deq1Result;

    deque<CInt> deq1, deq2, deq3;

    deque<CInt>::iterator deq1Iter;

    deq1.push_back(ci1);

    deq1.push_back(ci2);

    deq1.push_back(ci3);

    cout<<"deque deq1 of CInts data is: ";

    for(deq1Iter = deq1.begin(); deq1Iter != --deq1.end(); deq1Iter++)

        cout<<" "<<*deq1Iter<<",";

    deq1Iter = --deq1.end();

    cout<<" "<<*deq1Iter<<endl;

    cout<<"\nOperation: next_permutation(deq1.begin(), deq1.end()).\n";

    deq1Result = next_permutation(deq1.begin(), deq1.end());

    if(deq1Result)

        cout<<"The lexicographically next permutation exists and has\nreplaced the original "

                <<"ordering of the sequence in deq1."<<endl;

    else

        cout<<"The lexicographically next permutation doesn't exist\n and the lexicographically "

                <<"smallest permutation\n has replaced the ordering of the sequence in deq1."<<endl;

    cout<<"\nAfter the next_permutation,\ndeq1 data: ";

    for(deq1Iter = deq1.begin(); deq1Iter != --deq1.end(); deq1Iter++)

        cout<<" "<<*deq1Iter<<",";

    deq1Iter = --deq1.end();

    cout<<" "<<*deq1Iter<<endl;

    // permuting vector elements with binary function mod_lesser

    vector <int> vec1;

    vector <int>::iterator Iter1;

    int i;

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

        vec1.push_back(i);

    cout<<"\nVector vec1 data: ";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    next_permutation(vec1.begin(), vec1.end(), mod_lesser);

    cout<<"After the first next_permutation(), vector vec1 is:\nvec1 data: ";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    int k = 1;

    while (k <= 5)

    {

        next_permutation(vec1.begin(), vec1.end(), mod_lesser);

        cout<<"After another next_permutation() of vector vec1,\nvec1 data: ";

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

            cout<<*Iter1<<" ";

        cout<<endl;

        k++;

    }

    return 0;

}

 

Output:

 

C++ STL algorithm next_permutation() program example

 

nth_element()

  1. template<class RandomAccessIterator>void nth_element( RandomAccessIterator _First, RandomAccessIterator _Nth, RandomAccessIterator _Last );

  2. template<class RandomAccessIterator, class BinaryPredicate>void nth_element( RandomAccessIterator _First, RandomAccessIterator _Nth, RandomAccessIterator _Last, BinaryPredicate _Comp );

Parameters

 

Parameter

Description

_First

A random-access iterator addressing the position of the first element in the range to be partitioned.

_Nth

A random-access iterator addressing the position of element to be correctly ordered on the boundary of the partition.

_Last

A random-access iterator addressing the position one past the final element in the range to be partitioned.

_Comp

User-defined predicate function object that defines the comparison criterion to be satisfied by successive elements in the ordering. A binary predicate takes two arguments and returns true when satisfied and false when not satisfied.

 

Table 35.13

// algorithm, nth_element()

#include <vector>

#include <algorithm>

// for greater<int>()

#include <functional>

#include <iostream>

using namespace std;

 

// user defined function, return whether first element is greater than the second

bool great(int elem1, int elem2)

{return (elem1 > elem2);}

 

int main()

{

    vector <int> vec;

    vector <int>::iterator Iter1;

    int i;

    for(i = 0; i <= 5; i++)

        vec.push_back(i);

    int j;

    for(j = 10; j <= 15; j++)

        vec.push_back(j);

    int k;

    for(k = 20; k <= 25; k++)

        vec.push_back(k);

    cout<<"vector vec data:\n";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    cout<<"\nOperation: nth_element(vec.begin(),\nvec.begin()+3, vec.end()).\n";

    nth_element(vec.begin(), vec.begin()+3, vec.end());

    cout<<"Position 3 partitioned vector vec data:\n";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    // to sort in descending order, specify binary predicate

    cout<<"\nOperation: nth_element(vec.begin(),\nvec.begin()+4, vec.end(),greater<int>()).\n";

    nth_element(vec.begin(), vec.begin()+4, vec.end(), greater<int>());

    cout<<"Position 4 partitioned (greater) vector vec data:\n";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    cout<<"\nOperation: random_shuffle(vec.begin(), vec.end()).\n";

    random_shuffle(vec.begin(), vec.end());

    cout<<"Shuffled vector vec data:\n";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    // a user-defined binary predicate...

    cout<<"\nOperation: nth_element(vec.begin(),\nvec.begin() + 5, vec.end(), great).\n";

    nth_element(vec.begin(), vec.begin() + 5, vec.end(), great);

    cout<<"Position 5 partitioned (great) vector data:\n";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    return 0;

}

 

Output:

C++ STL algorithm nth_element() program example

 

partial_sort()

  1. template<class RandomAccessIterator>void partial_sort( RandomAccessIterator _First, RandomAccessIterator _SortEnd, RandomAccessIterator _Last );

  2. template<class RandomAccessIterator, class BinaryPredicate>void partial_sort( RandomAccessIterator _First, RandomAccessIterator _SortEnd, RandomAccessIterator _Last, BinaryPredicate _Comp );

Parameters

 

Parameter

Description

_First

A random-access iterator addressing the position of the first element in the range to be sorted.

_SortEnd

A random-access iterator addressing the position one past the final element in the sub-range to be sorted.

_Last

A random-access iterator addressing the position one past the final element in the range to be partially sorted.

_Comp

User-defined predicate function object that defines the comparison criterion to be satisfied by successive elements in the ordering. A binary predicate takes two arguments and returns true when satisfied and false when not satisfied.

 

Table 35.14

// algorithm, partial_sort()

#include <vector>

#include <algorithm>

// for greater<int>()

#include <functional>     

#include <iostream>

using namespace std;

 

// user defined, return whether first element is greater than the second

bool great(int elem1, int elem2)

{    return elem1 > elem2;    }

 

int main()

{

    vector <int> vec1;

    vector <int>::iterator Iter1;

    // fill up the vector with data...

    int i;

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

        vec1.push_back(i);

    int j;

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

        vec1.push_back(j);

    cout<<"vector vec1 data:\n";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    cout<<"\nOperation: partial_sort(vec1.begin(),\nvec1.begin()+ 5, vec1.end()).\n";

    partial_sort(vec1.begin(), vec1.begin() + 5, vec1.end());

    cout<<"Partially sorted vector vec1 data:\n";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    // to partially sort in descending order, specify binary predicate

    cout<<"\nOperation: partial_sort(vec1.begin(),\nvec1.begin()+4, vec1.end(), greater<int>()).\n";

    partial_sort(vec1.begin(), vec1.begin()+4, vec1.end(), greater<int>());

    cout<<"Partially resorted (greater) vector vec1 data:\n";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    // a user-defined binary predicate can also be used

    cout<<"\nOperation: partial_sort(vec1.begin(),\nvec1.begin()+8, vec1.end(), great).\n";

    partial_sort(vec1.begin(), vec1.begin()+8, vec1.end(), great);

    cout<<"Partially resorted (great) vector vec1 data:\n";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    return 0;

}

 

Output:

 

C++ STL algorithm partial_sort() program example

 

tenouk C++ STL tutorial

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Further C++ STL algorithm related reading:

 

  1. The source code for this tutorial is available in C++ STL Algorithm source codes.

  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 7 | Main | C++ STL Algorithm 9 >| 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