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


 

 

 

 

 

MODULE 35

THE C++ STL ALGORITHM PART 6

 

 

 

 

 

 

 

 

 

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 skills 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, inplace_merge() program example

  2. Algorithm, iter_swap() program example

  3. Algorithm, lexicographical_compare() program example

  4. Algorithm, lower_bound() program example

 

 

35.1  Continuation from the previous Module…

 

inplace_merge()

  • Combines the elements from two consecutive sorted ranges into a single sorted range, where the ordering criterion may be specified by a binary predicate.

  1. template<class BidirectionalIterator>void inplace_merge( BidirectionalIterator _First, BidirectionalIterator _Middle, BidirectionalIterator _Last );

  2. template<class BidirectionalIterator, class Pr>void inplace_merge( BidirectionalIterator _First, BidirectionalIterator _Middle, BidirectionalIterator _Last, BinaryPredicate _Comp );

Parameters

 

Parameter

Description

_First

A bidirectional iterator addressing the position of the first element in the first of two consecutive sorted ranges to be combined and sorted into a single range.

_Middle

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

_Last

A bidirectional iterator addressing the position one past the last element in the second of two consecutive sorted ranges to be combined and sorted into a single 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.1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

// algorithm, inplace_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> vec1;

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

    // constructing vector vec1 with default less-than ordering

    int i;

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

        vec1.push_back(i);

    int j;

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

        vec1.push_back(j);

    cout<<"vector vec1 data with subranges sorted by the "<<"binary\npredicate less than is: ";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    // constructing vector vec2 with ranges sorted by greater

    vector <int> vec2(vec1);

    vector <int>::iterator break2;

    break2 = find(vec2.begin(), vec2.end(), -5);

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

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

    cout<<"\nvector vec2 data with subranges sorted by the "<<"binary\npredicate greater is: ";

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

        cout<<*Iter2<<" ";

    cout<<endl;

    // constructing vector vec3 with ranges sorted by mod_lesser

    vector <int> vec3(vec1);

    vector <int>::iterator break3;

    break3 = find(vec3.begin(), vec3.end(), -5);

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

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

    cout<<"\nvector vec3 data with subranges sorted by the "<<"binary\npredicate mod_lesser is: ";

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

        cout<<*Iter3<<" ";

    cout<<endl;

    vector <int>::iterator break1;

    break1 = find(vec1.begin(), vec1.end(), -5);

    inplace_merge(vec1.begin(), break1, vec1.end());

    cout<<"\nvector vec1merg data, merged inplace with\ndefault order: ";

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

        cout<<*Iter1<<" ";

    cout<<endl;

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

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

    cout<<"\nvector vec2merg data, merged inplace with binary\npredicate greater specified: ";

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

        cout<<*Iter2<<" ";

    cout<<endl;

    // applying a user defined binary predicate mod_lesser

    inplace_merge(vec3.begin(), break3, vec3.end(), mod_lesser);

    cout<<"\nvector vec3merg data, merged inplace with binary\npredicate mod_lesser specified: ";

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

        cout<<*Iter3<<" ";

    cout<<endl;

    return 0;

}

 

Output:

C++ STL algorithm inplace_merge() program example

 

iter_swap()

template<class ForwardIterator1, class ForwardIterator2> void iter_swap( ForwardIterator1 _Left, ForwardIterator2 _Right );

 

Parameters

 

Parameter

Description

_Left

One of the forward iterators whose value is to be exchanged.

_Right

The second of the forward iterators whose value is to be exchanged.

 

Table 35.2

// algorithm, iter_swap()

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

{

    CInt c1 = 9, c2 = 12, c3 = 17;

    deque<CInt> deq;

    deque<CInt>::iterator deqIter;

    deq.push_back(c1);

    deq.push_back(c2);

    deq.push_back(c3);

    cout<<"The deque of CInts data is:\n";

    for(deqIter = deq.begin(); deqIter != --deq.end(); deqIter++)

        cout<<" "<<*deqIter<<",";

    deqIter = --deq.end();

    cout<<" "<<*deqIter<<endl;

    // exchanging first and last elements with iter_swap

    iter_swap(deq.begin(), --deq.end());

    cout<<"\nThe deque of CInts data with first and last\nelements swapped is: ";

    for(deqIter = deq.begin(); deqIter != --deq.end(); deqIter++)

        cout<<" "<<*deqIter<<",";

    deqIter = --deq.end();

    cout<<" "<<*deqIter<<endl;

    // swapping back first and last elements with swap

    swap(*deq.begin(), *(deq.end() -1));

    cout<<"\nThe deque of CInts data with first and last\nelements re swapped is: ";

    for(deqIter = deq.begin(); deqIter != --deq.end(); deqIter++)

        cout<<" "<<*deqIter<<",";

    deqIter = --deq.end();

    cout<<" "<<*deqIter<<endl;

    // swapping a vector element with a deque element

    vector <int> vec;

    vector <int>::iterator Iter1;

    deque <int> deq1;

    deque <int>::iterator deq1Iter;

    int i;

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

        vec.push_back(i);

    int j;

    for(j = 16; j <= 20; j++)

        deq1.push_back(j);

    cout<<"\nVector vec data: ";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    cout<<"\nDeque deq1 data: ";

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

        cout<<*deq1Iter<<" ";

    cout<<endl;

    iter_swap(vec.begin(), deq1.begin());

    cout<<"\nAfter exchanging first elements,\nvector vec data is: ";

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

        cout<<*Iter1<<" ";

    cout<<endl<<"and deque deq1 data is: ";

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

        cout<<*deq1Iter<<" ";

    cout<<endl;

    return 0;

}

 

Output:

C++ STL algorithm iter_swap() program example

 

 

lexicographical_compare()

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

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

Parameters

 

Parameter

Description

_First1

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

_Last1

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

_First2

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

_Last2

An input iterator addressing the position one past the final element in the second range to be compared.

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

  1. It finds two corresponding elements unequal, and the result of their comparison is taken as the result of the comparison between sequences.

  2. No inequalities are found, but one sequence has more elements than the other, and the shorter sequence is considered less than the longer sequence.

  3. No inequalities are found and the sequences have the same number of elements, and so the sequences are equal and the result of the comparison is false.

// algorithm, lexicographical_compare()

#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 = 0; j <= 6; 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;

    // self lexicographical_comparison of vec1 under identity

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

    bool result1;

    result1 = lexicographical_compare(vec1.begin(), vec1.end(), vec2.begin(), vec2.end());

    if(result1)

        cout<<"Vector vec1 is lexicographically_less than vec2."<<endl;

    else

        cout<<"Vector vec1 is not lexicographically_less than vec2."<<endl;

    // lexicographical_comparison of vec1 and lst under identity

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

    bool result2;

    result2 = lexicographical_compare(vec1.begin(), vec1.end(), lst.begin(), lst.end());

    if(result2)

        cout<<"Vector vec1 is lexicographically_less than lst."<<endl;

    else

        cout<<"Vector vec1 is lexicographically_less than lst."<<endl;

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

    bool result3;

    result3 = lexicographical_compare(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), twice);

    if(result3)

        cout<<"Vector vec1 is lexicographically_less than\nvec2 based on twice."<<endl;

    else

        cout<<"Vector vec1 is not lexicographically_less than\nvec2 based on twice."<<endl;

    return 0;

}

 

Output:

 

C++ STL algorithm lexicographical_compare() program example

 

lower_bound()

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

  2. template<class ForwardIterator, class Type, class BinaryPredicate>ForwardIterator lower_bound( 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 whose first position or possible first position is being searched for in the ordered range.

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

// algorithm, lower_bound()

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

    // constructing vectors vec1a & vec1b with default less than ordering

    int i;

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

        vec1.push_back(i);

    int j;

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

        vec1.push_back(j);

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

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

    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;

    // constructing vectors vec2 with range sorted by greater

    vector <int> vec2(vec1);

    vector <int>::iterator Iter2, Result2;

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

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

    cout<<"vector vec2 data with range sorted by the binary predicate\ngreater is: ";

    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, Result3;

    cout<<"\nOperation: sort(vec3.begin(), vec3.end(), mod_lesser).\n";

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

    cout<<"vector vec3 data with range sorted by the "

            <<"binary predicate\nmod_lesser is: ";

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

        cout<<*Iter3<<" ";

    cout<<endl;

    // lower_bound of 5 in vec1 with default binary predicate less <int>()

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

    Result1 = lower_bound(vec1.begin(), vec1.end(), 5);

    cout<<"The lower_bound in vec2 for the\nelement with a value of 5 is: "<<*Result1<<endl;

    // lower_bound of 5 in vec2 with the binary predicate greater<int>()

    Result2 = lower_bound(vec2.begin(), vec2.end(), 5, greater<int>());

    cout<<"The lower_bound in vec2 for the\nelement with a value of 5 is: "<<*Result2<<endl;

    // lower_bound of 5 in vec3 with the binary predicate mod_lesser

    cout<<"\nOperation: lower_bound(vec3.begin(), vec3.end(), 5, mod_lesser).\n";

    Result3 = lower_bound(vec3.begin(), vec3.end(), 5, mod_lesser);

    cout<<"The lower_bound in vec3 for the\nelement with a value of 5 is: "<<*Result3<<endl;

    return 0;

}

 

Output

C++ STL algorithm lower_bound() program example

 

 

tenouk C++ STL tutorial

 

 

 

 

 

 

 

 

 

 

 

Further C++ STL algorithm related reading:

 

  1. C++ Templates programming tutorials.

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

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