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


 

 

 

 

 

 

MODULE 35_1

THE C++ STL ALGORITHM PART 7

 

 

 

 

 

 

 

 

 

My Training Period: xx hours

 

More <algorithm> member function program examples. Code examples compiled using Microsoft Visual C++ .Net, win32 empty console mode application. g++ compilation on Fedora Core 3 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:

 

  • Learn how to use the template classes and member functions.

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

  • Able to understand how the containers, iterators and algorithm work.

 

What do we have in this session?

  1. Algorithm, make_heap() program example

  2. Algorithm, max() program example

  3. Algorithm, max_element() program example

  4. Algorithm, merge() program example

  5. Algorithm, min() program example

 

make_heap()

  • Converts elements from a specified range into a heap in which the first element is the largest and for which a sorting criterion may be specified with a binary predicate.

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

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

Parameters

 

Parameter

Description

_First

A random-access iterator addressing the position of the first element in the range to be converted into a heap.

_Last

A random-access iterator addressing the position one past the final element in the range to be converted into a heap.

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

  • Heaps have two properties:

  1. The first element is always the largest.

  2. Elements may be added or removed in logarithmic time.

  • Heaps are an ideal way to implement priority queues and they are used in the implementation of the Standard Template Library container adaptor priority_queue Class.

  • The complexity is linear, requiring 3*(_Last – _First) comparisons.

 

 

 

 

 

 

 

 

 

 

 

 

 

// algorithm, make_heap()

#include <vector>

#include <algorithm>

#include <functional>

#include <iostream>

using namespace std;

 

int main()

{

    vector <int> vec1, vec2;

    vector <int>::iterator Iter1, Iter2;

    int i;

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

        vec1.push_back(i);

    cout<<"Operation: random_shuffle(vec1.begin(), vec1.end()).\n";

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

    cout<<"Vector vec1 is data:\n";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    // make vec1 a heap with default less than ordering

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

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

    cout<<"The heaped version of vector vec1 data:\n";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    // make vec1 a heap with greater than ordering

    cout<<"\nOperation: make_heap(vec1.begin(), vec1.end(), greater<int>()).\n";

    make_heap(vec1.begin(), vec1.end(), greater<int>());

    cout<<"The greater-than heaped version of vec1 data:\n";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    return 0;

}

 

Output

C++ STL algorithm make_heap() program example

 

max()

  1. template<class Type> const Type& max( const Type& _Left, const Type& _Right );

  2. template<class Type, class Pr> const Type& max( const Type& _Left, const Type& _Right, BinaryPredicate _Comp );

Parameters

 

Parameter

Description

_Left

The first of the two objects being compared.

_Right

The second of the two objects being compared.

_Comp

A binary predicate used to compare the two objects.

 

Table 35.6

// algorithm, max()

#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_greater(int elem1, int elem2)

{

   if(elem1 < 0)

      elem1 = - elem1;

   if(elem2 < 0)

      elem2 = - elem2;

   return (elem1 > elem2);

};

 

int main()

{

    // comparing integers directly using the max algorithm

    int a = 11, b = -12, c = 20;

    const int& result1 = max(a, b, mod_greater);

    const int& result2 = max(b, c);

    cout<<"The mod_greater of the integers 11 and -12 is: "<<result1<<endl;

    cout<<"The larger of the integers -12 and 20 is: "<<result2<<endl;

    cout<<endl;

    // comparing set containers with elements of type CInt using the max algorithm

    CInt c1 = 1, c2 = 2, c3 = 3;

    set<CInt> st1, st2, st3;

    set<CInt>::iterator st1_Iter, st2_Iter, st3_Iter;

    st1.insert(c1);

    st1.insert(c2);

    st2.insert(c2);

    st2.insert(c3);

    cout<<"st1 data: (";

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

        cout<<*st1_Iter<<",";

    st1_Iter = --st1.end();

    cout<<*st1_Iter<<")."<<endl;

    cout<<"st2 data: (";

    for(st2_Iter = st2.begin(); st2_Iter != --st2.end(); st2_Iter++)

        cout<<*st2_Iter<<",";

    st2_Iter = --st2.end();

    cout<<*st2_Iter<<")."<<endl;

    st3 = max(st1, st2);

    cout<<"st3 = max(st1, st2) = (";

    for(st3_Iter = st3.begin(); st3_Iter != --st3.end(); st3_Iter++)

        cout<<*st3_Iter<<",";

    st3_Iter = --st3.end();

    cout<<*st3_Iter<<")."<<endl;

    // comparing vectors with integer elements using the max algorithm

    vector <int> vec1, vec2, vec3, vec4, vec5;

    vector <int>::iterator Iter1, Iter2, Iter3, Iter4, Iter5;

    int i;

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

        vec1.push_back(i);

    int j;

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

        vec2.push_back(j);

    int k;

    for(k = 0; k <= 2; k++)

        vec3.push_back(2*k);

    cout<<"\nVector vec1 data: ";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    cout<<"Vector vec2 data: ";

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

        cout<<*Iter2<<" ";

    cout<<endl;

    cout<<"Vector vec3 data: ";

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

        cout<<*Iter3<<" ";

    cout<<endl;

    vec4 = max(vec1, vec2);

    vec5 = max(vec1, vec3);

    cout<<"Vector vec4 = max(vec1,vec2) is: ";

    for(Iter4 = vec4.begin(); Iter4 != vec4.end(); Iter4++)

        cout<<*Iter4<<" ";

    cout<<endl;

    cout<<"Vector vec5 = max(vec1,vec3) is: ";

    for(Iter5 = vec5.begin(); Iter5 != vec5.end(); Iter5++)

        cout<<*Iter5<<" ";

    cout<<endl;

    return 0;

}

 

Output

C++ STL algorithm max() program example

 

max_element()

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

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

  2. template<class ForwardIterator, class BinaryPredicate>ForwardIterator max_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.7

// algorithm, max_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 maximum element

    CInt c1 = 1, c2 = 2, c3 = -3;

    set<CInt> st1;

    set<CInt>::iterator st1_Iter, st2_Iter, st3_Iter;

    st1.insert(c1);

    st1.insert(c2);

    st1.insert(c3);

    cout<<"st1 data: ";

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

        cout<<" "<<*st1_Iter<<",";

    st1_Iter = --st1.end();

    cout<<" "<<*st1_Iter<<endl;

    st2_Iter = max_element(st1.begin(), st1.end());

    cout<<"The largest element in st1 is: "<<*st2_Iter<<endl;

    cout<<endl;

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

    // element under default less than & mod_lesser binary predicates

    vector <int> vec;

    vector <int>::iterator vec_Iter, vec1_Iter, vec2_Iter;

    int i;

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

    vec.push_back(i);

    int j;

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

        vec.push_back(-j);

    cout<<"Vector vec data: ";

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

        cout<<*vec_Iter<<" ";

    cout<<endl;

    vec1_Iter = max_element(vec.begin(), vec.end());

    vec2_Iter = max_element(vec.begin(), vec.end(), mod_lesser);

    cout<<"The largest element in vec is: "<<*vec1_Iter<<endl;

    cout<<"The largest element in vec under the\nmod_lesser binary predicate is: "<<*vec2_Iter<<endl;

    return 0;

}

 

Output

 

C++ STL algorithm max_element() program example

 

merge()

  1. template<class InputIterator1, class InputIterator2, class OutputIterator>OutputIterator merge( InputIterator1 _First1, InputIterator1 _Last1, InputIterator2 _First2, InputIterator2 _Last2, OutputIterator _Result );

  2. template<class InputIterator1, class InputIterator2, class OutputIterator, class BinaryPredicate>OutputIterator merge( InputIterator1 _First1, InputIterator1 _Last1, InputIterator2 _First2, InputIterator2 _Last2, OutputIterator _Result, 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 combined and sorted into a single range.

_Last1

An input iterator addressing the position one past the last element in the first of two sorted source ranges to be combined and sorted into a single range.

_First2

An input iterator addressing the position of the first element in second of two consecutive sorted source ranges to be combined and sorted into a single range.

_Last2

An input iterator addressing the position one past the last element in second of two consecutive sorted source ranges to be combined and sorted into a single range.

_Result

An output iterator addressing the position of the first element in the destination range where the two source ranges are to be combined into a single sorted range.

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

// algorithm, merge()

#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> vec1a, vec1b, vec1(12);

    vector <int>::iterator Iter1a, Iter1b, Iter1;

    // constructing vector vec1a and vec1b with default less than ordering

    int i;

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

        vec1a.push_back(i);

    int j;

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

        vec1b.push_back(j);

    cout<<"vector vec1a data with range sorted by the\n"

        <<"binary predicate less than is: ";

    for(Iter1a = vec1a.begin(); Iter1a != vec1a.end(); Iter1a++)

        cout<<*Iter1a<<" ";

    cout<<endl;

    cout<<"vector vec1b data with range sorted by the\n"

        <<"binary predicate less than is: ";

    for(Iter1b = vec1b.begin(); Iter1b != vec1b.end(); Iter1b++)

        cout<<*Iter1b<<" ";

    cout<<endl;

    // constructing vector vec2 with ranges sorted by greater

    vector <int> vec2a(vec1a), vec2b(vec1b), vec2(vec1);

    vector <int>::iterator Iter2a, Iter2b, Iter2;

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

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

    cout<<"vector vec2a data with range sorted by the\n"

            <<"binary predicate greater is: ";

    for(Iter2a = vec2a.begin(); Iter2a != vec2a.end(); Iter2a++)

        cout<<*Iter2a<<" ";

    cout<<endl;

    cout<<"vector vec2b data with range sorted by the\n"

        <<"binary predicate greater is: ";

    for(Iter2b = vec2b.begin(); Iter2b != vec2b.end(); Iter2b++)

        cout<<*Iter2b<<" ";

    cout<<endl;

    // constructing vector vec3 with ranges sorted by mod_lesser

    vector <int> vec3a(vec1a), vec3b(vec1b), vec3(vec1);

    vector <int>::iterator Iter3a, Iter3b, Iter3;

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

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

    cout<<"vector vec3a data with range sorted by the\n"

            <<"binary predicate mod_lesser is: ";

    for(Iter3a = vec3a.begin(); Iter3a != vec3a.end(); Iter3a++)

        cout<<*Iter3a<<" ";

    cout<<endl;

    cout<<"vector vec3b data with range sorted by the\n"

            <<"binary predicate mod_lesser is: ";

    for(Iter3b = vec3b.begin(); Iter3b != vec3b.end(); Iter3b++)

        cout<<*Iter3b<<" ";

    cout<<endl;

    // to merge in ascending order with default binary predicate less <int>()

    cout<<"\nOperation: merge(vec1a.begin(),vec1a.end(),\nvec1b.begin(),vec1b.end(),vec1.begin()).\n";

    merge(vec1a.begin(), vec1a.end(), vec1b.begin(), vec1b.end(), vec1.begin());

    cout<<"vector vec1merg data, merged with default order:\n";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    // to merge in descending order, specify binary predicate greater<int>()

    cout<<"\nOperation: merge(vec2a.begin(),vec2a.end(),\nvec2b.begin(),vec2b.end(),vec2.begin(),greater<int>()).\n";

    merge(vec2a.begin(), vec2a.end(), vec2b.begin(), vec2b.end(), vec2.begin(), greater<int>());

    cout<<"vector vec2merg data, merged with binary predicate\ngreater is: ";

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

        cout<<*Iter2<<" ";

    cout<<endl;

    // applying a user-defined binary predicate mod_lesser

    cout<<"\nOperation: merge(vec3a.begin(),vec3a.end(),\nvec3b.begin(),vec3b.end(),vec3.begin(),mod_lesser).\n";

    merge(vec3a.begin(), vec3a.end(), vec3b.begin(), vec3b.end(), vec3.begin(), mod_lesser);

    cout<<"vector vec3merg data, merged with binary predicate\nmod_lesser is: ";

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

        cout<<*Iter3<<" ";

    cout<<endl;

    return 0;

}

 

Output

 

C++ STL algorithm merge() program example

 

min()

  1. template<class Type> const Type& min( const Type& _Left, const Type& _Right );

  2. template<class Type, class Pr> const Type& min( const Type& _Left, const Type& _Right, BinaryPredicate _Comp );

Parameters

 

Parameter

Description

_Left

The first of the two objects being compared.

_Right

The second of the two objects being compared.

_Comp

A binary predicate used to compare the two objects.

 

Table 35.9

// algorithm, min()

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

{

    // comparing integers directly using the min algorithm with binary predicate mod_lesser & with default less than

    int a = 9, b = -12, c = 12;

    const int& result1 = min(a, b, mod_lesser);

    const int& result2 = min(b, c);

    cout<<"The mod_lesser of the integers 9 and -12 is: "<<result1<<endl;

    cout<<"The lesser of the integers -12 and 12 is: "<<result2<<endl;

    cout<<endl;

    // comparing set containers with elements of type CInt using the min algorithm

    CInt ci1 = 2, ci2 = 3, ci3 = 4;

    set<CInt> st1, st2, st3;

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

    st1.insert(ci1);

    st1.insert(ci2);

    st2.insert(ci2);

    st2.insert(ci3);

    cout<<"st1 data: (";

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

        cout<<*st1Iter<<",";

    st1Iter = --st1.end();

    cout<<*st1Iter<<")"<<endl;

    cout<<"st2 data: (";

    for(st2Iter = st2.begin(); st2Iter != --st2.end(); st2Iter++)

        cout<<*st2Iter<<",";

    st2Iter = --st2.end();

    cout<<*st2Iter<<")"<<endl;

    st3 = min(st1, st2);

    cout<<"st3 = min(st1, st2) data: (";

    for(st3Iter = st3.begin(); st3Iter != --st3.end(); st3Iter++)

        cout<<*st3Iter<<",";

    st3Iter = --st3.end();

    cout<<*st3Iter<<")"<<endl;

    // comparing vectors with integer elements using min algorithm

    vector <int> vec1, vec2, vec3, vec4, vec5;

    vector <int>::iterator Iter1, Iter2, Iter3, Iter4, Iter5;

    int i;

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

        vec1.push_back(i);

    int j;

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

        vec2.push_back(j);

    int k;

    for(k = 1; k <= 3; k++)

        vec3.push_back(2*k);

    cout<<"\nVector vec1 data: ";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    cout<<"Vector vec2 data: ";

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

        cout<<*Iter2<<" ";

    cout<<endl;

    cout<<"Vector vec3 data: ";

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

        cout<<*Iter3<<" ";

    cout<<endl;

    cout<<"\nOperation: vec4 = min(vec1, vec2).\n";

    vec4 = min(vec1, vec2);

    cout<<"Vector vec4 = min(vec1,vec2) data: ";

    for(Iter4 = vec4.begin(); Iter4 != vec4.end(); Iter4++)

        cout<<*Iter4<<" ";

    cout<<endl;

    cout<<"\nOperation: vec5 = min(vec1, vec3).\n";

    vec5 = min(vec1, vec3);

    cout<<"Vector vec5 = min(vec1,vec3) data: ";

    for(Iter5 = vec5.begin(); Iter5 != vec5.end(); Iter5++)

    cout<<*Iter5<<" ";

    cout<<endl;

    return 0;

}

 

Output:

 

C++ STL algorithm min() 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. 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 6 | Main | C++ Algorithm 8 >| 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