# 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. compilation example is given at the end of this Module. The source code for this tutorial is available in C++ STL Algorithm source codes.

# 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

_First1

_Last1

_First2

_Last2

_Comp

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

}

# partition()

• Classifies elements in a range into two disjoint sets, with those elements satisfying a unary predicate preceding those that fail to satisfy it.

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

# Parameters

## Parameter

_First

_Last

_Comp

#### Table 35.16

• The return value is a bidirectional iterator addressing the position of the first element in the range to not satisfy the predicate condition.

• The range referenced must be valid; all pointers must be dereferenceable and within the sequence the last position is reachable from the first by incrementation.

• Elements a and b are equivalent, but not necessarily equal, if both Pr (a, b) is false and Pr (b, a) if false, where Pr is the parameter-specified predicate. The partition() algorithm is not stable and does not guarantee that the relative ordering of equivalent elements will be preserved.  The algorithm stable_ partition() does preserve this original ordering.

• The complexity is linear: there are (_Last – _First) applications of _Comp and at most (_Last – _First)/2 swaps.

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

}

# pop_heap()

• Removes the largest element from the front of a heap to the next-to-last position in the range and then forms a new heap from the remaining elements.

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

_First

_Last

_Comp

#### Table 35.17

• The pop_heap() algorithm is the inverse of the operation performed by the push_heap() algorithm, in which an element at the next-to-last position of a range is added to a heap consisting of the prior elements in the range, in the case when the element being added to the heap is larger than any of the elements already in the heap.

• As mentioned before, 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 range referenced must be valid; all pointers must be de-referenceable and within the sequence the last position is reachable from the first by incrementation.

• The range excluding the newly added element at the end must be a heap.

• The complexity is logarithmic, requiring at most log (_Last – _First) comparisons.

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

}

# prev_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 prev_permutation( BidirectionalIterator _First, BidirectionalIterator _Last );

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

# Parameters

## Parameter

_First

_Last

_Comp

#### Table 35.18

• The return value is true if the lexicographically previous permutation exists and has replaced the original ordering of the range; otherwise false, in which case the ordering is transformed into the lexicographically largest permutation.

• The range referenced must be valid; all pointers must be dereferenceable and within the sequence the last position is reachable from the first by incrementation.

• The default binary predicate is less than and the elements in the range must be less-than comparable to ensure that the next permutation is well defined.

• The complexity is linear, with at most (_Last – _First)/2 swap.

// 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:

• The following are program examples compiled using g++.

// *******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

# 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 documentation that includes STL.

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