|< C++ STL Algorithm 7 | Main | C++ STL Algorithm 9 >|Site Index |Download |
MODULE 35a
THE C++ STL ALGORITHM PART 8
| My Training Period: xx hours
Continue from the previous Module, more member functions working examples, compiled using MicrosoftVisual C++ .Net, win32 empty console mode application. g++ compilation example is given at the end of this Module. The source code for this tutorial is available inC++ STL Algorithm source codes.
The C++ STL algorithm abilities that supposed to be acquired:
What do we have in this session?
min_element()
Parameters
| ||||||||||
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.
// 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: ";
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 |
_First1 | An input iterator addressing the position of the first element in the first range to be tested. |
_Last1 | An input iterator addressing the position one past the final element in the first range to be tested. |
_First2 | An input iterator addressing the position of the first element in the second range to be tested. |
_Comp | User-defined predicate function object that defines the condition to be satisfied if two elements are to be taken as equivalent. A binary predicate takes two arguments and returns true when satisfied and false when not satisfied. |
Table 35.11 | |
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.
Theoperator== 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: ";
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()
Parameters
| |||||||||||
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()
{
// re-ordering 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)
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()
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 |
_First | A random-access iterator addressing the position of the first element in the range to be partitioned. |
_Nth | A random-access iterator addressing the position of element to be correctly ordered on the boundary of the partition. |
_Last | A random-access iterator addressing the position one past the final element in the range to be partitioned. |
_Comp | User-defined predicate function object that defines the comparison criterion to be satisfied by successive elements in the ordering. A binary predicate takes two arguments and returns true when satisfied and false when not satisfied. |
Table 35.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++)
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, RandomAccessIterator _SortEnd, RandomAccessIterator _Last );
template<class RandomAccessIterator, class BinaryPredicate>void partial_sort( RandomAccessIterator _First, RandomAccessIterator _SortEnd, RandomAccessIterator _Last, BinaryPredicate _Comp );
Parameters
Parameter | Description |
_First | A random-access iterator addressing the position of the first element in the range to be sorted. |
_SortEnd | A random-access iterator addressing the position one past the final element in the sub-range to be sorted. |
_Last | A random-access iterator addressing the position one past the final element in the range to be partially sorted. |
_Comp | User-defined predicate function object that defines the comparison criterion to be satisfied by successive elements in the ordering. A binary predicate takes two arguments and returns true when satisfied and false when not satisfied. |
Table 35.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
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:
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.