|< C++ STL Algorithm 6 | Main | C++ Algorithm 8 >|Site Index |Download |
MODULE 35_1
THE C++ STL ALGORITHM PART 7
| 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.
The C++ STL algorithm abilities that supposed to be acquired:
What do we have in this session?
make_heap()
Parameters
| ||||||||||
// 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.
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.
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()
|
Parameters
Parameter | Description |
_First | A forward iterator addressing the position of the first element in the range to be searched for the largest element. |
_Last | A forward iterator addressing the position one past the final element in the range to be searched for the largest element. |
_Comp | User-defined predicate function object that defines the sense in which one element is greater than another. The binary predicate takes two arguments and should return true when the first element is less than the second element and false otherwise. |
Table 35.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.
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 |
_First1 | An input iterator addressing the position of the first element in the first of two sorted source ranges to be combined and sorted into a single range. |
_Last1 | An input iterator addressing the position one past the last element in the first of two sorted source ranges to be combined and sorted into a single range. |
_First2 | An input iterator addressing the position of the first element in second of two consecutive sorted source ranges to be combined and sorted into a single range. |
_Last2 | 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.
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.
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:
Further C++ STL algorithm related reading:
The source code for this tutorial is available inC++ STL Algorithm source codes.
Acomplete C++ Standard Library documentation that includes STL.