|< 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 using Microsoft 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 in C++ 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?

  1. Algorithm, set_symmetric_difference() program example

  2. Algorithm, set_union() program example

  3. Algorithm, sort() program example

  4. Algorithm, sort_heap() program example

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

  1. template<class InputIterator1, class InputIterator2, class OutputIterator>OutputIterator set_symmetric_difference( InputIterator1 _First1, InputIterator1 _Last1, InputIterator2 _First2, InputIterator2 _Last2, OutputIterator _Result );

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

 

 

 

 

 

 

 

 

 

 

 

 

 

Parameter

Description

_First1

An input iterator addressing the position of the first element in the first of two sorted source ranges to be united and sorted into a single range representing the symmetric difference of the two source ranges.

_Last1

An input iterator addressing the position one past the last element in the first of two sorted source ranges to be united and sorted into a single range representing the symmetric difference of the two source ranges.

_First2

An input iterator addressing the position of the first element in second of two consecutive sorted source ranges to be united and sorted into a single range representing the symmetric difference of the two source ranges.

_Last2

An input iterator addressing the position one past the last element in second of two consecutive sorted source ranges to be united and sorted into a single range representing the symmetric difference of the two source ranges.

_Result

An output iterator addressing the position of the first element in the destination range where the two source ranges are to be united into a single sorted range representing the symmetric difference of the two source ranges.

_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 37.1

// 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:

 

C++ STL Algorithm, set_symmetric_difference() program example

 

set_union()

  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

 

Parameter

Description

_First1

An input iterator addressing the position of the first element in the first of two sorted source ranges to be united and sorted into a single range representing the union of the two source ranges.

_Last1

An input iterator addressing the position one past the last element in the first of two sorted source ranges to be united and sorted into a single range representing the union of the two source ranges.

_First2

An input iterator addressing the position of the first element in second of two consecutive sorted source ranges to be united and sorted into a single range representing the union of the two source ranges.

_Last2

An input iterator addressing the position one past the last element in second of two consecutive sorted source ranges to be united and sorted into a single range representing the union of the two source ranges.

_Result

An output iterator addressing the position of the first element in the destination range where the two source ranges are to be united into a single sorted range representing the union of the two source ranges.

_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 37.2

// 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:

C++ STL Algorithm, set_union() program example

 

 

sort()

  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

 

Parameter

Description

_First

A random-access iterator addressing the position of the first element in the range to be sorted.

_Last

A random-access iterator addressing the position one past the final element in the range to be 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 37.3

// 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:

 

C++ STL Algorithm, sort() program example

 

sort_heap()

  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

 

Parameter

Description

_First

A random-access iterator addressing the position of the first element in the target heap.

_Last

A random-access iterator addressing the position one past the final element in the target 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 37.4

  1. The first element is always the largest.

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

// 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:

 

 

C++ STL Algorithm, sort_heap() program example

 

stable_partition()

template<class BidirectionalIterator, class Predicate>
   BidirectionalIterator stable_partition( BidirectionalIterator _First, BidirectionalIterator _Last, Predicate _Pred );

 

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.

_Pred

User-defined predicate function object that defines the condition to be satisfied if an element is to be classified. A predicate takes single argument and returns true or false.

 

Table 37.5

// 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:

 

C++ STL Algorithm, stable_partition() program example

 

tenouk C++ STL tutorial

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Further C++ STL algorithm related reading:

 

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

  2. A complete C & C++ Standard Library documentation that includes STL.

  3. C++ Templates programming tutorials.

  4. Check the best 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