|< C++ STL Algorithm 13 | Main | C++ STL Algorithm 15 >|Site Index |Download |

---

 

 

 

 

 

MODULE 37

THE C++ STL ALGORITHM PART 14

 

 

 

 

 

 

My Training Period: xx hours   This is C++ STL algorithm programming tutorial final part. C++ codes compiled usingMicrosoft Visual C++ .Net, win32 empty console mode application. g++ compilation on Fedora Core 3 example is given at the end of this Module. Get the source code in text file inC++ STL Algorithm source code.   The C++ STL algorithm skills that supposed to be acquired:   Able to understand and use the member functions of the algorithm. Appreciate how the usage of the template classes and functions. Able to use containers, iterators and algorithm all together.   What do we have in this page? Algorithm, set_symmetric_difference() program example Algorithm, set_union() program example Algorithm, sort() program example Algorithm, sort_heap() program example Algorithm, stable_partition() program example     37.1  A Continuation from previous Module…   set_symmetric_difference() Unites all of the elements that belong to one, but not both, of the 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 set_symmetric_difference( InputIterator1 _First1, InputIterator1 _Last1, InputIterator2 _First2, InputIterator2 _Last2, OutputIterator _Result ); template<class InputIterator1, class InputIterator2, class OutputIterator, class BinaryPredicate>OutputIterator set_symmetric_difference( InputIterator1 _First1, InputIterator1 _Last1, InputIterator2 _First2, InputIterator2 _Last2, OutputIterator _Result, BinaryPredicate _Comp );

Parameters

 

 

 

 

 

 

 

 

• An output iterator addressing the position one past the last element in the sorted destination range representing the symmetric difference of the two source ranges.

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

• If the source ranges contain duplicates of an element, then the destination range will contain the absolute value of the number by which the occurrences of those elements in the one of the source ranges exceeds the occurrences of those elements in the second source range.

• The complexity of the algorithm is linear with at most 2*((_Last1 – _First1) – (_Last2 – _First2)) – 1 comparisons for nonempty source ranges.

// algorithm, set_symmetric_difference()

#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, Result1;

   // constructing vectors vec1a & vec1b with default less-than ordering

   int i;

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

     vec1a.push_back(i);

   int j;

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

     vec1b.push_back(j);

   cout<<"Original vector vec1a with range sorted by the\nbinary predicate less than is: ";

   for(Iter1a = vec1a.begin(); Iter1a != vec1a.end(); Iter1a++)

      cout<<*Iter1a<<" ";

   cout<<endl;

   cout<<"\nOriginal vector vec1b with range sorted by the\nbinary predicate less than is: ";

   for(Iter1b = vec1b.begin(); Iter1b != vec1b.end(); Iter1b++)

      cout<<*Iter1b<<" ";

   cout<<endl;

   // constructing vectors vec2a & vec2b with ranges sorted by greater

   vector <int>vec2a(vec1a), vec2b(vec1b), vec2(vec1);

   vector <int>::iterator Iter2a, Iter2b, Iter2, Result2;

   sort(vec2a.begin(), vec2a.end(), greater<int>());

   sort(vec2b.begin(), vec2b.end(), greater<int>());

   cout<<"\nOriginal vector vec2a with range sorted by the\nbinary predicate greater is: ";

   for(Iter2a = vec2a.begin(); Iter2a != vec2a.end(); Iter2a++)

      cout<<*Iter2a<<" ";

   cout<<endl;

   cout<<"\nOriginal vector vec2b with range sorted by the\nbinary predicate greater is: ";

   for(Iter2b = vec2b.begin(); Iter2b != vec2b.end(); Iter2b++)

      cout<<*Iter2b<<" ";

   cout<<endl;

   // constructing vectors vec3a & vec3b with ranges sorted by mod_lesser()

   vector<int>vec3a(vec1a), vec3b(vec1b), vec3(vec1);

   vector<int>::iterator Iter3a, Iter3b, Iter3, Result3;

   sort(vec3a.begin(), vec3a.end(), mod_lesser);

   sort(vec3b.begin(), vec3b.end(), mod_lesser);

   cout<<"\nOriginal vector vec3a with range sorted by the\nbinary predicate mod_lesser() is: ";

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

      cout<<*Iter3a<<" ";

   cout<<endl;

   cout<<"\nOriginal vector vec3b with range sorted by the\nbinary predicate mod_lesser() is: ";

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

      cout<<*Iter3b<<" ";

   cout<<endl;

   // to combine into a symmetric difference in ascending order with the default binary predicate less <int>()

   Result1 = set_symmetric_difference(vec1a.begin(), vec1a.end(), vec1b.begin(), vec1b.end(), vec1.begin());

   cout<<"\nset_symmetric_difference() of source ranges with default order,\nvector vec1mod: ";

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

      cout<<*Iter1<<" ";

   cout<<endl;

   // to combine into a symmetric difference in descending order, specify binary predicate greater<int>()

   Result2 = set_symmetric_difference(vec2a.begin(), vec2a.end(), vec2b.begin(), vec2b.end(), vec2.begin(), greater<int>());

   cout<<"\nset_symmetric_difference() of source ranges with binary predicate\ngreater specified, vector vec2mod: ";

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

      cout<<*Iter2<<" ";

   cout<<endl;

   // to combine into a symmetric difference applying a user defined binary predicate mod_lesser

   Result3 = set_symmetric_difference(vec3a.begin(), vec3a.end(), vec3b.begin(), vec3b.end(), vec3.begin(), mod_lesser);

   cout<<"\nset_symmetric_difference() of source ranges with binary predicate\nmod_lesser() specified, vector vec3mod: ";

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

      cout<<*Iter3<<" ";

   cout<<endl;

}

 

Output:

 

 

set_union()

• Unites all of the elements that belong to at least one of 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 set_union( InputIterator1 _First1, InputIterator1 _Last1, InputIterator2 _First2, InputIterator2 _Last2, OutputIterator _Result );

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

Parameters

 

• The return value is an output iterator addressing the position one past the last element in the sorted destination range representing the union of the two source ranges.

• 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. If the source ranges contain duplicates of an element, then the destination range will contain the maximum number of those elements that occur in both source ranges.

• The complexity of the algorithm is linear with at most 2*((_Last1 – _First1) – (_Last2 – _First2)) – 1 comparisons.

// algorithm, set_union()

#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, Result1;

   // constructing vectors vec1a & vec1b with default less than ordering

   int i;

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

     vec1a.push_back(i);

   int j;

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

     vec1b.push_back(j);

   cout<<"Original vector vec1a with range sorted by the\nbinary predicate less than is: ";

   for(Iter1a = vec1a.begin(); Iter1a != vec1a.end(); Iter1a++)

      cout<<*Iter1a<<" ";

   cout<<endl;

   cout<<"\nOriginal vector vec1b with range sorted by the\nbinary predicate less than is: ";

   for(Iter1b = vec1b.begin(); Iter1b != vec1b.end(); Iter1b++)

      cout<<*Iter1b<<" ";

   cout<<endl;

   // constructing vectors vec2a & vec2b with ranges sorted by greater

   vector <int>vec2a(vec1a), vec2b(vec1b), vec2(vec1);

   vector <int>::iterator Iter2a, Iter2b, Iter2, Result2;

   sort(vec2a.begin(), vec2a.end(), greater<int>());

   sort(vec2b.begin(), vec2b.end(), greater<int>());

   cout<<"\nOriginal vector vec2a with range sorted by the\nbinary predicate greater is: ";

   for(Iter2a = vec2a.begin(); Iter2a != vec2a.end(); Iter2a++)

      cout<<*Iter2a<<" ";

   cout<<endl;

   cout<<"\nOriginal vector vec2b with range sorted by the\nbinary predicate greater is: ";

   for(Iter2b = vec2b.begin(); Iter2b != vec2b.end(); Iter2b++)

      cout<<*Iter2b<<" ";

   cout<<endl;

   // constructing vectors vec3a & vec3b with ranges sorted by mod_lesser()

   vector <int>vec3a(vec1a), vec3b(vec1b), vec3(vec1);

   vector <int>::iterator Iter3a, Iter3b, Iter3, Result3;

   sort(vec3a.begin(), vec3a.end(), mod_lesser);

   sort(vec3b.begin(), vec3b.end(), mod_lesser);

   cout<<"\nOriginal vector vec3a with range sorted by the\nbinary predicate mod_lesser() is: ";

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

      cout<<*Iter3a<<" ";

   cout<<endl;

   cout<<"\nOriginal vector vec3b with range sorted by the\nbinary predicate mod_lesser() is: ";

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

      cout<<*Iter3b<<" ";

   cout<<endl;

   // to combine into a union in ascending order with the default binary predicate less <int>()

   Result1 = set_union(vec1a.begin(), vec1a.end(), vec1b.begin(), vec1b.end(), vec1.begin());

   cout<<"\nset_union() of source ranges with default order,\nvector vec1mod: ";

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

      cout<<*Iter1<<" ";

   cout<<endl;

   // to combine into a union in descending order, specify binary predicate greater<int>()

   Result2 = set_union(vec2a.begin(), vec2a.end(), vec2b.begin(), vec2b.end(), vec2.begin(), greater<int>());

   cout<<"\nset_union() of source ranges with binary predicate greater\nspecified, vector vec2mod: ";

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

      cout<<*Iter2<<" ";

   cout<<endl;

   // to combine into a union applying a user-defined binary predicate mod_lesser

   Result3 = set_union(vec3a.begin(), vec3a.end(), vec3b.begin(), vec3b.end(), vec3.begin(), mod_lesser);

   cout<<"\nset_union() of source ranges with binary predicate\nmod_lesser() specified, vector vec3mod: ";

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

      cout<<*Iter3<<" ";

   cout<<endl;

}

 

Output:

 

sort()

• Arranges the elements in a specified range into a non-descending order or according to an ordering criterion specified by a binary predicate.

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

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

Parameters

 

• 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 so 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, sort()

#include <vector>

#include <algorithm>

// for greater<int>()

#include <functional>     

#include <iostream>

using namespace std;

 

// return whether first element is greater than the second

bool userdefgreater(int elem1, int elem2)

{    return elem1 > elem2;    }

 

int main()

{

   vector <int> vec1;  // container

   vector <int>::iterator Iter1;  // iterator

   int k;

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

      vec1.push_back(k);

   random_shuffle(vec1.begin(), vec1.end());

   cout<<"Original random shuffle vector vec1 data:\n";

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

      cout<<*Iter1<<" ";

   cout<<endl;

   sort(vec1.begin(), vec1.end());

   cout<<"\nSorted vector vec1 data:\n";

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

      cout<<*Iter1<<" ";

   cout<<endl;

   // to sort in descending order, specify binary predicate

   sort(vec1.begin(), vec1.end(), greater<int>());

   cout<<"\nRe sorted (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

   sort(vec1.begin(), vec1.end(), userdefgreater);

   cout<<"\nUser defined re sorted vector vec1 data:\n";

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

      cout<<*Iter1<<" ";

   cout<<endl;

}

 

Output:

 

 

sort_heap()

• Converts a heap into a sorted range.

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

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

Parameters

 

• Heaps have two properties:

1. The first element is always the largest.

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

• After the application if this algorithm, the range it was applied to is no longer a heap.

• This is not a stable sort because the relative order of equivalent elements is not necessarily preserved.

• 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 complexity is at most N log N, whereN = (_Last – _First).

// algorithm, sort_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 = 1; i <= 10; i++)

    vec1.push_back(i);

   random_shuffle(vec1.begin(), vec1.end());

   cout<<"Random shuffle vector vec1 data:\n";

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

      cout<<*Iter1<<" ";

   cout<<endl;

   // sort heap vec1 with default less-than ordering

   sort_heap(vec1.begin(), vec1.end());

   cout<<"\nThe sorted heap vec1 data:\n";

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

      cout<<*Iter1<<" ";

   cout<<endl;

   // make vec1 a heap with greater than ordering

   make_heap(vec1.begin(), vec1.end(), greater<int>());

   cout<<"\nThe greater than heaped version of vec1 data:\n";

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

      cout<<*Iter1<<" ";

   cout<<endl;

   sort_heap(vec1.begin(), vec1.end(), greater<int>());

   cout<<"\nThe greater than sorted heap vec1 data:\n";

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

      cout<<*Iter1<<" ";

   cout<<endl;

}

 

Output:

 

 

 

stable_partition()

• Classifies elements in a range into two disjoint sets, with those elements satisfying a unary predicate preceding those that fail to satisfy it, preserving the relative order of equivalent elements.

template<class BidirectionalIterator, class Predicate>

   BidirectionalIterator stable_partition( BidirectionalIterator _First, BidirectionalIterator _Last, Predicate _Pred );

 

Parameters

 

• 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 de-referenceable 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.  The stable_ partition() algorithm is stable and guarantees that the relative ordering of equivalent elements will be preserved.

• The algorithm partition() does not necessarily preserve this original ordering.

// algorithm, stable_partition()

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

 

bool greaterthan(int value )

{    return value > 5;    }

 

int main()

{

   vector <int> vec1, vec2;

   vector <int>::iterator Iter1, Iter2, result;

   int i;

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

     vec1.push_back(i);

   int j;

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

     vec1.push_back(3);

   random_shuffle(vec1.begin(), vec1.end());

   cout<<"Random shuffle vector vec1 data:\n";

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

      cout<<*Iter1<<" ";

   cout<<endl;

   // partition the range with predicate greater than 5...

   result = stable_partition (vec1.begin(), vec1.end(), greaterthan);

   cout<<"\nThe partitioned set of elements in vec1 is:\n";

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

      cout<<*Iter1<<" ";

   cout<<endl;

   cout<<"\nThe first element in vec1 fail to satisfy the\npredicate greaterthan is:\n "<<*result<<endl;

}

 

Output:

 

 

tenouk C++ STL tutorial

 

 

 

 

 

 

 

Further C++ STL algorithm related reading:

 

1. Get the source code in text file inC++ STL Algorithm source code.

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.

 

 

 

 

 

|< C++ STL Algorithm 13 | Main | C++ STL Algorithm 15 >|Site Index |Download |

---

C++ STL Algorithm Classes:  Part 1 | Part 2 |Part 3 | Part 4 | Part 5 | Part 6 | Part 7 | Part 8 |Part 9 | Part 10 |Part 11 | Part 12 | Part 13 | Part 14 | Part 15