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


 

 

 

 

 

MODULE 35a_1

THE C++ STL ALGORITHM PART 9

 

 

 

 

 

 

 

 

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

  2. Algorithm, partition() program example

  3. Algorithm, pop_heap() program example

  4. Algorithm, prev_permutation() program example

  5. Algorithm, iter_swap() program example - g++

  6. Algorithm, partition() program example - g++

 

partial_sort_copy()

  • Copies elements from a source range into a destination range where the source elements are ordered by either less than or another specified binary predicate.

  1. template<class InputIterator, class RandomAccessIterator>RandomAccessIterator partial_sort_copy( InputIterator _First1, InputIterator _Last1, RandomAccessIterator _First2, RandomAccessIterator _Last2 );

  2. template<class InputIterator, class RandomAccessIterator, class BinaryPredicate>RandomAccessIterator partial_sort_copy( InputIterator _First1, InputIterator _Last1, RandomAccessIterator _First2, RandomAccessIterator _Last2, BinaryPredicate _Comp );

 

Parameters

 

Parameter

Description

_First1

An input iterator addressing the position of the first element in the source range.

_Last1

An input iterator addressing the position one past the final element in the source range.

_First2

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

_Last2

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

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

  • The return value is a random-access iterator addressing the element in the destination range one position beyond the last element inserted from the source range.

  • The source and destination ranges must not overlap and must be valid; all pointers must be dereferenceable and within each sequence the last position must be reachable from the first by incrementation.

  • The binary predicate must provide a strict weak ordering so that elements that are not equivalent are ordered, but elements that are equivalent are not.  Two elements are equivalent under less than, but not necessarily equal, if neither is less than the other.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

// algorithm, partial_sort_copy()

#include <vector>

#include <list>

#include <algorithm>

#include <functional>

#include <iostream>

using namespace std;

 

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

        vec1.push_back(i);

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

    lst.push_back(6);

    lst.push_back(5);

    lst.push_back(2);

    lst.push_back(3);

    lst.push_back(4);

    lst.push_back(1);

    cout<<"Vector vec1 data: ";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    cout<<"\nList lst data: ";

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

        cout<<*lst_Iter<<" ";

    cout<<endl;

    // copying a partially sorted copy of lst into vec1

    cout<<"\nOperation: partial_sort_copy(lst.begin(),\nlst.end(),vec1.begin(),vec1.begin()+3).\n";

    vector <int>::iterator result1;

    result1 = partial_sort_copy(lst.begin(), lst.end(), vec1.begin(), vec1.begin()+3);

    cout<<"vector vec1 data: ";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    cout<<"The first vec1 element one position beyond\nthe last lst element inserted was "<<*result1<<endl;

    // copying a partially sorted copy of lst into vec2

    int j;

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

        vec2.push_back(j);

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

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

    vector <int>::iterator result2;

    cout<<"Operation: partial_sort_copy(lst.begin(),\nlst.end(), vec2.begin(), vec2.begin()+6, greater<int>()).\n";

    result2 = partial_sort_copy(lst.begin(), lst.end(), vec2.begin(), vec2.begin()+6, greater<int>());

    cout<<"List lst into vector vec2 data: ";

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

        cout<<*Iter2<<" ";

    cout<<endl;

    cout<<"The first vec2 element one position beyond"

            <<"\nthe last lst element inserted was "<<*result2<<endl;

    return 0;

}

 

Output:

C++ STL algorithm partial_sort_copy() program example

 

partition()

template<class BidirectionalIterator, class Predicate>
   BidirectionalIterator partition( BidirectionalIterator _First, BidirectionalIterator _Last, BinaryPredicate _Comp );

 

Parameters

 

Parameter

Description

_First

A bidirectional iterator addressing the position of the first element in the range to be partitioned.

_Last

A bidirectional iterator addressing the position one past the final element in the range to be partitioned.

_Comp

User-defined predicate function object that defines the condition to be satisfied if an element is to be classified. A predicate takes a single argument and returns true or false.

 

Table 35.16

// algorithm, partition()

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

 

// user defined...

bool great(int value)

{    return value >3;    }

 

int main()

{

    vector <int> vec1, vec2;

    vector <int>::iterator Iter1, Iter2;

    int i;

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

        vec1.push_back(i);

    cout<<"Vector vec1 data: ";

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

        cout<<*Iter1<<" ";

    cout<<endl;

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

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

    cout<<"Vector vec1 data: ";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    // partition the range with predicate great

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

    partition(vec1.begin(), vec1.end(), great);

    cout<<"The partitioned set of elements in vec1 is:\n";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    return 0;

}

 

Output:

 

C++ STL algorithm partition() program example

 

pop_heap()

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

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

 

Parameters

 

Parameter

Description

_First

A random-access iterator addressing the position of the first element in the heap.

_Last

A random-access iterator addressing the position one past the final element in the 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.17

  1. The first element is always the largest.

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

// algorithm, pop_heap()

#include <vector>

#include <algorithm>

#include <functional>

#include <iostream>

using namespace std;

 

int main()

{

    vector <int> vec;

    vector <int>::iterator Iter1, Iter2;

    int i;

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

        vec.push_back(i);

    // make vec a heap with default less than ordering

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

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

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

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

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

        cout<<*Iter1<<" ";

    cout<<endl;

    // add an element to the back of the heap

    vec.push_back(11);

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

    cout<<"The reheaped vec data with 11 added:\n";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    // remove the largest element from the heap

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

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

    cout<<"The heap vec data with 11 removed is:\n";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    // make vec a heap with greater-than ordering with a 0 element

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

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

    vec.push_back(0);

    push_heap(vec.begin(), vec.end(), greater<int>());

    cout<<"The greater than reheaped vec data puts the\nsmallest element first:";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    // application of pop_heap to remove the smallest element

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

    pop_heap(vec.begin(), vec.end(), greater<int>());

    cout<<"The greater than heaped vec data with the smallest element\nremoved from the heap is: ";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    return 0;

}

 

Output

C++ STL algorithm pop_heap() program example

 

 

prev_permutation()

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

  2. template<class BidirectionalIterator, class BinaryPredicate>bool prev_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.18

// algorithm, prev_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()

{

    // reordering the elements of type CInt in a deque using the prev_permutation algorithm

    CInt ci1 = 10, ci2 = 15, ci3 = 20;

    bool deq1Result;

    deque<CInt> deq1, deq2, deq3;

    deque<CInt>::iterator d1_Iter;

    deq1.push_back(ci1);

    deq1.push_back(ci2);

    deq1.push_back(ci3);

    cout<<"deque of CInts data: ";

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

    cout<<*d1_Iter<<",";

    d1_Iter = --deq1.end();

    cout<<*d1_Iter<<endl;

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

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

    if(deq1Result)

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

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

    else

        cout<<"The lexicographically previous permutation doesn't exist\nand the lexicographically "

                <<"smallest permutation\nhas replaced the original ordering of the sequence in deq1."<<endl;

    cout<<"\nAfter one application of prev_permutation(),\ndeq1 data: ";

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

        cout<<*d1_Iter<<",";

    d1_Iter = --deq1.end();

    cout<<*d1_Iter<<endl;

    // permutating vector elements with binary function mod_lesser

    vector <int> vec;

    vector <int>::iterator Iter1;

    int i;

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

        vec.push_back(i);

    cout<<"\nVector vec data: ";

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

        cout<<*Iter1<<" ";

    cout<<endl;

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

    prev_permutation(vec.begin(), vec.end(), mod_lesser);

    cout<<"After the first prev_permutation(), vector vec is:\n vec data: ";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    int j = 1;

    while (j <= 5)

    {

        prev_permutation(vec.begin(), vec.end(), mod_lesser);

        cout<<"After another prev_permutation() of vector vec,\nvec data: ";

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

            cout<<*Iter1<<" ";

        cout<<endl;

        j++;

    }

    return 0;

}

 

Output:

 

C++ STL algorithm prev_permutation() program example

// *******algoiterswap.cpp*******

// algorithm, iter_swap() - g++

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

}

 

[bodo@bakawali ~]$ g++ algoiterswap.cpp -o algoiterswap

[bodo@bakawali ~]$ ./algoiterswap

 

The deque of CInts data is:

 CInt(9), CInt(12), CInt(17)

 

The deque of CInts data with first and last

elements swapped is:  CInt(17), CInt(12), CInt(9)

 

The deque of CInts data with first and last

elements re swapped is:  CInt(9), CInt(12), CInt(17)

 

Vector vec data: 10 11 12 13 14

 

Deque deq1 data: 16 17 18 19 20

 

After exchanging first elements,

vector vec data is: 16 11 12 13 14

and deque deq1 data is: 10 17 18 19 20

 

// ******algopartition.cpp*******

// algorithm, partition() - g++

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

 

// user defined...

bool great(int value)

{    return value >3;    }

 

int main()

{

    vector <int> vec1, vec2;

    vector <int>::iterator Iter1, Iter2;

    int i;

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

        vec1.push_back(i);

    cout<<"Vector vec1 data: ";

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

        cout<<*Iter1<<" ";

    cout<<endl;

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

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

    cout<<"Vector vec1 data: ";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    // partition the range with predicate great

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

    partition(vec1.begin(), vec1.end(), great);

    cout<<"The partitioned set of elements in vec1 is:\n";

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

        cout<<*Iter1<<" ";

    cout<<endl;

r    eturn 0;

}

 

[bodo@bakawali ~]$ g++ algopartition.cpp -o algopartition

[bodo@bakawali ~]$ ./algopartition

 

Vector vec1 data: 0 1 2 3 4 5 6 7 8 9 10

 

Operation: random_shuffle(vec1.begin(), vec1.end()).

Vector vec1 data: 4 10 7 8 0 5 2 1 6 9 3

 

Operation: partition(vec1.begin(), vec1.end(), great).

The partitioned set of elements in vec1 is:

4 10 7 8 9 5 6 1 2 0 3

 

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