|< C++ STL Algorithm 5 | Main | C++ Algorithm 7 >|Site Index |Download |
MODULE 35
THE C++ STL ALGORITHM PART 6
| 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 skills that supposed to be acquired:
What do we have in this session?
35.1 Continuation from the previous Module…
inplace_merge()
Parameters
| ||||||||||||
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 isN log(N), where N = (_Last–_First).
// 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++)
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 toiter_swap(), which was included in the C++ Standard for backward compatibility. If Fit1 and Fit2 are forward iterators, theniter_swap(Fit1, Fit2), is equivalent toswap(*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){}
CInt(const CInt& rhs) : m_nVal(rhs.m_nVal){}
CInt& operator=(const CInt& rhs)
{ m_nVal = rhs.m_nVal; return *this;}
bool operator<(const CInt& rhs) const
{ return (m_nVal < rhs.m_nVal);}
friend ostream& operator<<(ostream& osIn, const CInt& rhs);
private:
int m_nVal;
};
inline ostream& operator<<(ostream& osIn, const CInt& rhs)
{
osIn<<"CInt(" <<rhs.m_nVal<< ")";
return osIn;
}
// return whether modulus of elem1 is less than modulus of elem2
bool mod_lesser(int elem1, int elem2)
{
if(elem1 < 0)
elem1 = - elem1;
if(elem2 < 0)
elem2 = - elem2;
return (elem1 < elem2);
};
int main()
{
CInt c1 = 9, c2 = 12, c3 = 17;
deque<CInt> deq;
deque<CInt>::iterator deqIter;
deq.push_back(c1);
deq.push_back(c2);
deq.push_back(c3);
cout<<"The deque of CInts data is:\n";
for(deqIter = deq.begin(); deqIter != --deq.end(); deqIter++)
cout<<" "<<*deqIter<<",";
deqIter = --deq.end();
cout<<" "<<*deqIter<<endl;
// exchanging first and last elements with iter_swap
iter_swap(deq.begin(), --deq.end());
cout<<"\nThe deque of CInts data with first and last\nelements swapped is: ";
for(deqIter = deq.begin(); deqIter != --deq.end(); deqIter++)
cout<<" "<<*deqIter<<",";
deqIter = --deq.end();
cout<<" "<<*deqIter<<endl;
// swapping back first and last elements with swap
swap(*deq.begin(), *(deq.end() -1));
cout<<"\nThe deque of CInts data with first and last\nelements re swapped is: ";
for(deqIter = deq.begin(); deqIter != --deq.end(); deqIter++)
cout<<" "<<*deqIter<<",";
deqIter = --deq.end();
cout<<" "<<*deqIter<<endl;
// swapping a vector element with a deque element
vector <int> vec;
vector <int>::iterator Iter1;
deque <int> deq1;
deque <int>::iterator deq1Iter;
int i;
for(i = 10; i <= 14; i++)
vec.push_back(i);
int j;
for(j = 16; j <= 20; j++)
deq1.push_back(j);
cout<<"\nVector vec data: ";
for(Iter1 = vec.begin(); Iter1 != vec.end(); Iter1++)
cout<<*Iter1<<" ";
cout<<endl;
cout<<"\nDeque deq1 data: ";
for(deq1Iter = deq1.begin(); deq1Iter != deq1.end(); deq1Iter++)
cout<<*deq1Iter<<" ";
cout<<endl;
iter_swap(vec.begin(), deq1.begin());
cout<<"\nAfter exchanging first elements,\nvector vec data is: ";
for(Iter1 = vec.begin(); Iter1 != vec.end(); Iter1++)
cout<<*Iter1<<" ";
cout<<endl<<"and deque deq1 data is: ";
for(deq1Iter = deq1.begin(); deq1Iter != deq1.end(); deq1Iter++)
cout<<*deq1Iter<<" ";
cout<<endl;
return 0;
}
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 |
_First1 | An input iterator addressing the position of the first element in the first range to be compared. |
_Last1 | An input iterator addressing the position one past the final element in the first range to be compared. |
_First2 | An input iterator addressing the position of the first element in the second range to be compared. |
_Last2 | An input iterator addressing the position one past the final element in the second range to be compared. |
_Comp | User-defined predicate function object that defines sense in which one element is less than another. A binary predicate takes two arguments and returns true when satisfied and false when not satisfied. |
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)
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 |
_First | A forward iterator addressing the position of the first element in the range to be searched. |
_Last | A forward iterator addressing the position one past the final element in the range to be searched. |
_Val | The value whose first position or possible first position is being searched for in the ordered range. |
_Comp | User-defined predicate function object that defines sense in which one element is less than another. A binary predicate takes two arguments and returns true when satisfied and false when not satisfied. |
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 "
<<"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
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.