|< C++ STL Algorithm 8 | Main | C++ STL Algorithm 10 >|Site Index |Download |
MODULE 35a_1
THE C++ STL ALGORITHM PART 9
| 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 skills that supposed to be acquired:
What do we have in this session?
partial_sort_copy()
Parameters
| ||||||||||||||
// 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";
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 |
_First | A bidirectional iterator addressing the position of the first element in the range to be partitioned. |
_Last | A bidirectional iterator addressing the position one past the final element in the range to be partitioned. |
_Comp | User-defined predicate function object that defines the condition to be satisfied if 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.
Elementsa and b are equivalent, but not necessarily equal, if both Pr (a, b) is false and Pr (b, a) if false, wherePr is the parameter-specified predicate. Thepartition() 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.
// 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
Parameter | Description |
_First | A random-access iterator addressing the position of the first element in the heap. |
_Last | A random-access iterator addressing the position one past the final element in the heap. |
_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.17 | |
Thepop_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);
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 |
_First | A bidirectional iterator pointing to the position of the first element in the range to be permuted. |
_Last | A bidirectional iterator pointing to the position one past the final element in the range to be permuted. |
_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.18 | |
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 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:
The following are program examples compiled usingg++.
// *******algoiterswap.cpp*******
// algorithm, iter_swap() - g++
#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;
}
[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() - g++
#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;
r eturn 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
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.