# My Training Period: xx hours

More <algorithm> member function program examples. Code examples compiled using Microsoft VisualC++ .Net, win32 empty console mode application. g++ compilation on Fedora Core 3 example is given at the end of this Module. The source code for this tutorial is available inC++ STL Algorithm source codes.

# make_heap()

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

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

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

# Parameters

## Parameter

_First

_Last

_Comp

#### Table 35.5

• Heaps have two properties:

1. The first element is always the largest.

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

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

• The complexity is linear, requiring3*(_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 # max()

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

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

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

# Parameters

## Parameter

_Left

_Right

_Comp

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

• Themax() 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()

{

// comparing integers directly using the max algorithm

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

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

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

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

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

cout<<endl;

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

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

set<CInt> st1, st2, st3;

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

st1.insert(c1);

st1.insert(c2);

st2.insert(c2);

st2.insert(c3);

cout<<"st1 data: (";

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

cout<<*st1_Iter<<",";

st1_Iter = --st1.end();

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

cout<<"st2 data: (";

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

cout<<*st2_Iter<<",";

st2_Iter = --st2.end();

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

st3 = max(st1, st2);

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

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

cout<<*st3_Iter<<",";

st3_Iter = --st3.end();

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

// comparing vectors with integer elements using the max algorithm

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

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

int i;

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

vec1.push_back(i);

int j;

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

vec2.push_back(j);

int k;

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

vec3.push_back(2*k);

cout<<"\nVector vec1 data: ";

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

cout<<*Iter1<<" ";

cout<<endl;

cout<<"Vector vec2 data: ";

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

cout<<*Iter2<<" ";

cout<<endl;

cout<<"Vector vec3 data: ";

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

cout<<*Iter3<<" ";

cout<<endl;

vec4 = max(vec1, vec2);

vec5 = max(vec1, vec3);

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

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

cout<<*Iter4<<" ";

cout<<endl;

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

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

cout<<*Iter5<<" ";

cout<<endl;

return 0;

}

# Output # max_element()

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

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

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

# Parameters

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

{

public:

CInt(int n = 0) : m_nVal(n){}

CInt(const CInt& rhs) : m_nVal(rhs.m_nVal){}

CInt& operator=(const CInt& rhs)

{    m_nVal = rhs.m_nVal; return *this;    }

bool operator<(const CInt& rhs) const

{    return (m_nVal < rhs.m_nVal);    }

friend ostream& operator<<(ostream& osIn, const CInt& rhs);

private:

int m_nVal;

};

inline ostream& operator<<(ostream& osIn, const CInt& rhs)

{

osIn<<"CInt("<<rhs.m_nVal<<")";

return osIn;

}

// return whether modulus of elem1 is greater than modulus of elem2

bool mod_lesser(int elem1, int elem2)

{

if(elem1 < 0)

elem1 = - elem1;

if(elem2 < 0)

elem2 = - elem2;

return (elem1 < elem2);

};

int main()

{

// searching a set container with elements of type CInt for the maximum element

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

set<CInt> st1;

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

st1.insert(c1);

st1.insert(c2);

st1.insert(c3);

cout<<"st1 data: ";

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

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

st1_Iter = --st1.end();

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

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

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

cout<<endl;

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

// element under default less than & mod_lesser binary predicates

vector <int> vec;

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

int i;

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

vec.push_back(i);

int j;

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

vec.push_back(-j);

cout<<"Vector vec data: ";

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

cout<<*vec_Iter<<" ";

cout<<endl;

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

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

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

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

return 0;

}

# Output # 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.

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

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

# Parameters

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

_Result

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

_Comp

User-defined predicate function object that defines the sense in which one element is greater than another. The binary predicate takes two arguments and should return truewhen the first element is less than the second element andfalse 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().

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

<<"binary predicate mod_lesser is: ";

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

cout<<*Iter3a<<" ";

cout<<endl;

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

<<"binary predicate mod_lesser is: ";

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

cout<<*Iter3b<<" ";

cout<<endl;

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

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

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

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

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

cout<<*Iter1<<" ";

cout<<endl;

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

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

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

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

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

cout<<*Iter2<<" ";

cout<<endl;

// applying a user-defined binary predicate mod_lesser

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

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

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

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

cout<<*Iter3<<" ";

cout<<endl;

return 0;

}

# Output # min()

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

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

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

# Parameters

## Parameter

_Left

_Right

_Comp

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

• Themin() 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);

};

int main()

{

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

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

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

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

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

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

cout<<endl;

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

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

set<CInt> st1, st2, st3;

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

st1.insert(ci1);

st1.insert(ci2);

st2.insert(ci2);

st2.insert(ci3);

cout<<"st1 data: (";

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

cout<<*st1Iter<<",";

st1Iter = --st1.end();

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

cout<<"st2 data: (";

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

cout<<*st2Iter<<",";

st2Iter = --st2.end();

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

st3 = min(st1, st2);

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

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

cout<<*st3Iter<<",";

st3Iter = --st3.end();

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

// comparing vectors with integer elements using min algorithm

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

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

int i;

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

vec1.push_back(i);

int j;

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

vec2.push_back(j);

int k;

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

vec3.push_back(2*k);

cout<<"\nVector vec1 data: ";

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

cout<<*Iter1<<" ";

cout<<endl;

cout<<"Vector vec2 data: ";

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

cout<<*Iter2<<" ";

cout<<endl;

cout<<"Vector vec3 data: ";

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

cout<<*Iter3<<" ";

cout<<endl;

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

vec4 = min(vec1, vec2);

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

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

cout<<*Iter4<<" ";

cout<<endl;

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

vec5 = min(vec1, vec3);

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

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

cout<<*Iter5<<" ";

cout<<endl;

return 0;

}

# Output: tenouk C++ STL tutorial

# Further C++ STL algorithm related reading:

1. The source code for this tutorial is available inC++ STL Algorithm source codes.

2. Acomplete C Standard Library.

3. Acomplete C++ Standard Library documentation that includes STL.

4. C++ Templates programming tutorials.

5. Check thebest selling C / C++ and STL books at Amazon.com.