MODULE 35

--THE STL--
ALGORITHM PART III

My Training Period: hours

Note: Compiled using Microsoft Visual C++ .Net, win32 empty console mode application. g++ compilation
example is given at the end of this Module.

Abilities

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

▪ Appreciate how the usage of the template classes and functions.
▪ Able to use containers, iterators and algorithm all together.

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.

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

Parameters

Parameter Description
A bidirectional iterator addressing the position of the first element in the first of
_First
two consecutive sorted ranges to be combined and sorted into a single range.
A bidirectional iterator addressing the position of the first element in the second
_Middle
of two consecutive sorted ranges to be combined and sorted into a single range.
A bidirectional iterator addressing the position one past the last element in the
_Last second of two consecutive sorted ranges to be combined and sorted into a single
range.
User-defined predicate function object that defines the sense in which one
element is greater than another. The binary predicate takes two arguments and
_Comp
should return true when the first element is less than the second element and false
otherwise.

Table 35.1

- The sorted consecutive ranges referenced must be valid; all pointers must be de-referenceable and,
within each sequence, the last position must be reachable from the first by incrementation.
- The sorted consecutive ranges must each be arranged as a precondition to the application of the
inplace_merge() algorithm in accordance with the same ordering as is to be used by the algorithm
to sort the combined ranges.
- The operation is stable as the relative order of elements within each range is preserved. When there are
equivalent elements in both source ranges, the element is the first range precedes the element from the
second in the combined range.
- The complexity depends on the available memory as the algorithm allocates memory to a temporary
buffer. If sufficient memory is available, the best case is linear with (_Last – _First)–1
comparisons; if no auxiliary memory is available, the worst case is N log(N), where N =
(_Last–_First).

www.tenouk.com Page 1 of 40
 //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++)

www.tenouk.com Page 2 of 40
 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:

iter_swap()

- Exchanges two values referred to by a pair of specified iterators.

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

- swap() should be used in preference to iter_swap(), which was included in the C++ Standard for
backward compatibility. If Fit1 and Fit2 are forward iterators, then iter_swap(Fit1, Fit2),
is equivalent to swap(*Fit1, *Fit2).
- The value types of the input forward iterators must have the same value.

//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){}

www.tenouk.com Page 3 of 40
 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: ";

www.tenouk.com Page 4 of 40
 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:

lexicographical_compare()

- Compares element by element between two sequences to determine which is lesser of the two.

template<class InputIterator1, class InputIterator2>

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

Parameters

Parameter Description
An input iterator addressing the position of the first element in the first range to be
_First1
compared.
An input iterator addressing the position one past the final element in the first range to
_Last1
be compared.
An input iterator addressing the position of the first element in the second range to be
_First2
compared.
An input iterator addressing the position one past the final element in the second range
_Last2
to be compared.
User-defined predicate function object that defines sense in which one element is less
_Comp than another. A binary predicate takes two arguments and returns true when satisfied
and false when not satisfied.

www.tenouk.com Page 5 of 40
 Table 35.3

- The return value is true if the first range is lexicographically less than the second range; otherwise
false.
- A lexicographical comparison between sequences compares them element by element until:

▪ It finds two corresponding elements unequal, and the result of their comparison is taken as the
result of the comparison between sequences.
▪ No inequalities are found, but one sequence has more elements than the other, and the shorter
sequence is considered less than the longer sequence.
▪ 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)

www.tenouk.com Page 6 of 40
 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:

lower_bound()

- Finds the position where the first element in an ordered range is or would be if it had a value that is less
than or equivalent to a specified value, where the sense of equivalence may be specified by a binary
predicate.

template<class ForwardIterator, class Type>

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

Parameters

Parameter Description
A forward iterator addressing the position of the first element in the range to be
_First
searched.
A forward iterator addressing the position one past the final element in the range to
_Last
be searched.
The value whose first position or possible first position is being searched for in the
_Val
ordered range.
User-defined predicate function object that defines sense in which one element is
_Comp less than another. A binary predicate takes two arguments and returns true when
satisfied and false when not satisfied.

www.tenouk.com Page 7 of 40
 Table 35.4

- The return value is a forward iterator addressing the position where the first element in an ordered
range is or would be if it had a value that is less than or equivalent to a specified value, where the sense
of equivalence may be specified by a binary predicate.
- The sorted source range referenced must be valid; all pointers must be de-referenceable and within the
sequence the last position must be reachable from the first by incrementation.
- The sorted range must each be arranged as a precondition to the application of the lower_bound()
algorithm in accordance with the same ordering as is to be used by the algorithm to sort the combined
ranges.
- The range is not modified by the algorithm merge().
- The value types of the forward iterators need be less-than comparable to be ordered, so that, given two
elements, it may be determined either that they are equivalent (in the sense that neither is less than the
other) or that one is less than the other. This results in an ordering between the nonequivalent elements
- The complexity of the algorithm is logarithmic for random-access iterators and linear otherwise, with
the number of steps proportional to (_Last1 – _First1).
//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 "

www.tenouk.com Page 8 of 40
 <<"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

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.

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

Parameters

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

www.tenouk.com Page 9 of 40
 A random-access iterator addressing the position one past the final element in the range to
_Last
be converted into a heap.
User-defined predicate function object that defines sense in which one element is less than
_Comp another. A binary predicate takes two arguments and returns true when satisfied and false
when not satisfied.

Table 35.5

- Heaps have two properties:

▪ The first element is always the largest.

▪ 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

www.tenouk.com Page 10 of 40
max()

- Compares two objects and returns the larger of the two, where the ordering criterion may be specified
by a binary predicate.

template<class Type>
const Type& max(
const Type& _Left,
const Type& _Right
);
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

- The return value is the greater of the two objects unless neither is greater, in which case it returns the
first of the two objects.
- The max() algorithm is unusual in having objects passed as parameters. Most STL algorithms operate
on a range of elements whose position is specified by iterator passes as parameters.
//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()
{

www.tenouk.com Page 11 of 40
 //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++)

www.tenouk.com Page 12 of 40
 cout<<*Iter5<<" ";
cout<<endl;
return 0;
}

Output

max_element()

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

template<class ForwardIterator>
ForwardIterator max_element(
ForwardIterator _First,
ForwardIterator _Last
);
template<class ForwardIterator, class BinaryPredicate>
ForwardIterator max_element(
ForwardIterator _First,
ForwardIterator _Last,
BinaryPredicate _Comp
);

Parameters

Parameter Description
A forward iterator addressing the position of the first element in the range to be
_First
searched for the largest element.
A forward iterator addressing the position one past the final element in the range to
_Last
be searched for the largest element.
User-defined predicate function object that defines the sense in which one element is
_Comp 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

- The return value is a forward iterator addressing the position of the first occurrence of the largest
element in the range searched.
- The range referenced must be valid; all pointers must be dereferenceable and within each sequence the
last position is reachable from the first by incrementation.
- The complexity is linear: (_Last – _First)–1 comparison is required for a nonempty range.

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

www.tenouk.com Page 13 of 40
 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;
}

www.tenouk.com Page 14 of 40
 Output

merge()

- Combines all of the elements from two sorted source ranges into a single, sorted destination range,
where the ordering criterion may be specified by a binary predicate.

template<class InputIterator1, class InputIterator2, class OutputIterator>

OutputIterator merge(
InputIterator1 _First1,
InputIterator1 _Last1,
InputIterator2 _First2,
InputIterator2 _Last2,
OutputIterator _Result
);
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
An input iterator addressing the position of the first element in the first of two sorted
_First1
source ranges to be combined and sorted into a single range.
An input iterator addressing the position one past the last element in the first of two sorted
_Last1
source ranges to be combined and sorted into a single range.
An input iterator addressing the position of the first element in second of two consecutive
_First2
sorted source ranges to be combined and sorted into a single range.
An input iterator addressing the position one past the last element in second of two
_Last2
consecutive sorted source ranges to be combined and sorted into a single range.
An output iterator addressing the position of the first element in the destination range
_Result
where the two source ranges are to be combined into a single sorted range.
User-defined predicate function object that defines the sense in which one element is
_Comp 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

- The return value is an output iterator addressing the position one past the last element in the sorted
destination range.
- The sorted source ranges referenced must be valid; all pointers must be de-referenceable and within
each sequence the last position must be reachable from the first by incrementation.
- The destination range should not overlap either of the source ranges and should be large enough to
contain the destination range.
- The sorted source ranges must each be arranged as a precondition to the application of the merge()
algorithm in accordance with the same ordering as is to be used by the algorithm to sort the combined
ranges.
- The operation is stable as the relative order of elements within each range is preserved in the
destination range. The source ranges are not modified by the algorithm merge().

www.tenouk.com Page 15 of 40
 - The value types of the input iterators need be less than comparable to be ordered, so that, given two
elements, it may be determined either that they are equivalent, in the sense that neither is less than the
other or that one is less than the other. This results in an ordering between the nonequivalent elements.
- When there are equivalent elements in both source ranges, the elements in the first range precede the
elements from the second source range in the destination range.
- The complexity of the algorithm is linear with at most (_Last1 – _First1)–(_Last2 –
_First2)–1 comparisons.
- The list class provides a member function merge() to merge the elements of two lists.
//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"

www.tenouk.com Page 16 of 40
 <<"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<i
nt>()).\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_lesse
r).\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

www.tenouk.com Page 17 of 40
min()

- Compares two objects and returns the lesser of the two, where the ordering criterion may be specified
by a binary predicate.

template<class Type>
const Type& min(
const Type& _Left,
const Type& _Right
);
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

- The return value is the lesser of the two objects unless neither is lesser, in which case it returns the first
of the two objects.
- The min() algorithm is unusual in having objects passed as parameters. Most STL algorithms operate
on a range of elements whose position is specified by iterators passed as parameters.

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

www.tenouk.com Page 18 of 40
 };

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

www.tenouk.com Page 19 of 40
 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:

min_element()

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

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

Parameters

Parameter Description
A forward iterator addressing the position of the first element in the range to
_First
be searched for the largest element.
A forward iterator addressing the position one past the final element in the
_Last
range to be searched for the largest element.
User-defined predicate function object that defines the sense in which one
element is greater than another. The binary predicate takes two arguments and
_Comp
should return true when the first element is less than the second element and
false otherwise.

Table 35.10

- The return value is a forward iterator addressing the position of the first occurrence of the smallest
element in the range searched.
- The range referenced must be valid; all pointers must be de-referenceable and within each sequence the
last position is reachable from the first by incrementation.
- The complexity is linear: (_Last – _First)–1 comparison is required for a non-empty range.

www.tenouk.com Page 20 of 40
 //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: ";

www.tenouk.com Page 21 of 40
 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:

mismatch()

- Compares two ranges element by element either for equality or equivalent in a sense specified by a
binary predicate and locates the first position where a difference occurs.

template<class InputIterator1, class InputIterator2>

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

Parameters

Parameter Description
An input iterator addressing the position of the first element in the first range to be
_First1
tested.
An input iterator addressing the position one past the final element in the first
_Last1
range to be tested.
An input iterator addressing the position of the first element in the second range to
_First2
be tested.
User-defined predicate function object that defines the condition to be satisfied if
_Comp 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

www.tenouk.com Page 22 of 40
 - The return value is a pair of iterators addressing the positions of the mismatch in the two ranges, the
first component iterator to the position in the first range and the second component iterator to the
position in the second range.
- If there is no difference between the elements in the ranges compared or if the binary predicate in the
second version is satisfied by all element pairs from the two ranges, then the first component iterator
points to the position one past the final element in the first range and the second component iterator to
position one past the final element tested in the second range.
- The range to be searched must be valid; all pointers must be de-referenceable and the last position is
reachable from the first by incrementation.
- The time complexity of the algorithm is linear in the number of elements contained in the range.
- The operator== used to determine the equality between elements must impose an equivalence
relation between its operands.

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

www.tenouk.com Page 23 of 40
 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

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.

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

Parameters

Parameter Description
A bidirectional iterator pointing to the position of the first element in the range to be
_First
permuted.
A bidirectional iterator pointing to the position one past the final element in the range to
_Last
be permuted.
User-defined predicate function object that defines the comparison criterion to be
_Comp
satisfied by successive elements in the ordering. A binary predicate takes two

www.tenouk.com Page 24 of 40
 arguments and returns true when satisfied and false when not satisfied.

Table 35.12

- The return value is true if the lexicographically next permutation exists and has replaced the original
ordering of the range; otherwise false, in which case the ordering is transformed into the
lexicographically smallest 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
insure that the next permutation is well defined.
- The complexity is linear with at most (_Last–_First)/2 swaps.

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

www.tenouk.com Page 25 of 40
 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:

nth_element()

www.tenouk.com Page 26 of 40
 - Partitions a range of elements, correctly locating the nth element of the sequence in the range so that all
the elements in front of it are less than or equal to it and all the elements that follow it in the sequence
are greater than or equal to it.

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

Parameters

Parameter Description
A random-access iterator addressing the position of the first element in the range to be
_First
partitioned.
A random-access iterator addressing the position of element to be correctly ordered on
_Nth
the boundary of the partition.
A random-access iterator addressing the position one past the final element in the range
_Last
to be partitioned.
User-defined predicate function object that defines the comparison criterion to be
_Comp 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

- 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 nth_element() algorithm does not guarantee that elements in the sub-ranges either side of the
nth element are sorted. It thus makes fewer guarantees than partial_sort(), which orders the
elements in the range below some chosen element, and may be used as a faster alternative to
partial_sort() when the ordering of the lower range is not required.
- Elements are equivalent, but not necessarily equal, if neither is less than the other.
- The average of a sort complexity is linear with respect to _Last – _First.

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

www.tenouk.com Page 27 of 40
 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:

partial_sort()

- Arranges a specified number of the smaller elements in a range into a non-descending order or
according to an ordering criterion specified by a binary predicate.

template<class RandomAccessIterator>
void partial_sort(
RandomAccessIterator _First,

www.tenouk.com Page 28 of 40
 RandomAccessIterator _SortEnd,
RandomAccessIterator _Last
);
template<class RandomAccessIterator, class BinaryPredicate>
void partial_sort(
RandomAccessIterator _First,
RandomAccessIterator _SortEnd,
RandomAccessIterator _Last
BinaryPredicate _Comp
);

Parameters

Parameter Description
A random-access iterator addressing the position of the first element in the range
_First
to be sorted.
A random-access iterator addressing the position one past the final element in the
_SortEnd
sub-range to be sorted.
A random-access iterator addressing the position one past the final element in the
_Last
range to be partially sorted.
User-defined predicate function object that defines the comparison criterion to be
_Comp 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

- 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.
- Elements are equivalent, but not necessarily equal, if neither is less than the other. The sort()
algorithm is not stable and does not guarantee that the relative ordering of equivalent elements will be
preserved. The algorithm stable_sort() does preserve this original ordering.
- The average of a sort complexity is O(N log N), where N = _Last – _First.

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

www.tenouk.com Page 29 of 40
 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:

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.

template<class InputIterator, class RandomAccessIterator>

RandomAccessIterator partial_sort_copy(
InputIterator _First1,
InputIterator _Last1,
RandomAccessIterator _First2,
RandomAccessIterator _Last2
);
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.
An input iterator addressing the position one past the final element in the source
_Last1
range.
A random-access iterator addressing the position of the first element in the sorted
_First2
destination range.
A random-access iterator addressing the position one past the final element in the
_Last2
sorted destination range.

www.tenouk.com Page 30 of 40
 User-defined predicate function object that defines the condition to be satisfied if
_Comp 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";

www.tenouk.com Page 31 of 40
 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:

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 Description
A bidirectional iterator addressing the position of the first element in the range to
_First
be partitioned.
A bidirectional iterator addressing the position one past the final element in the
_Last
range to be partitioned.
User-defined predicate function object that defines the condition to be satisfied if
_Comp an element is to be classified. A predicate takes a single argument and returns true
or false.

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.

www.tenouk.com Page 32 of 40
 //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:

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.

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

Parameters

www.tenouk.com Page 33 of 40
 Parameter Description
A random-access iterator addressing the position of the first element in the
_First
heap.
A random-access iterator addressing the position one past the final element in
_Last
the heap.
User-defined predicate function object that defines sense in which one element
_Comp is less than another. A binary predicate takes two arguments and returns true
when satisfied and false when not satisfied.

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:

▪ The first element is always the largest.

▪ 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);

www.tenouk.com Page 34 of 40
 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

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.

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

Parameters

Parameter Description
A bidirectional iterator pointing to the position of the first element in the range to
_First
be permuted.
A bidirectional iterator pointing to the position one past the final element in the
_Last
range to be permuted.
User-defined predicate function object that defines the comparison criterion to be
_Comp 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

www.tenouk.com Page 35 of 40
 - 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 "

www.tenouk.com Page 36 of 40
 <<"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:

- Program examples compiled using g++.

www.tenouk.com Page 37 of 40
 //*******algoiterswap.cpp*******
//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;

www.tenouk.com Page 38 of 40
 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()
#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++)

www.tenouk.com Page 39 of 40
 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;
}

[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

---------------------------------------------End of Algorithm part III--------------------------------------

---www.tenouk.com---

Further reading and digging:

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

www.tenouk.com Page 40 of 40