|< C++ STL Algorithm 12 | Main | C++ STL Algorithm 14 >| Site Index | Download |


 

 

 

 

 

MODULE 36a_1

THE C++ STL ALGORITHM PART 13

 

 

 

 

 

My Training Period: xx hours

 

This is a continuation from previous Module, more code samples, compiled using Microsoft Visual C++ .Net, win32 empty console mode application. g++ compilation examples given at the end of this Module. Source code for this tutorial is available in C++ STL Algorithm source code.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

The C++ STL algorithm skill that supposed to be acquired:

 

  • Able to understand and use the member functions of the algorithm.

 

What do we have in this page?

  1. Algorithm, set_difference() program example

  2. Algorithm, set_intersection() program example

  3. Algorithm, random_shuffle() program example - g++

  4. Algorithm, search_n() program example - g++

 

set_difference()

  • Unites all of the elements that belong to one sorted source range, but not to a second sorted source range, 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_difference( InputIterator1 _First1, InputIterator1 _Last1, InputIterator2 _First2, InputIterator2 _Last2, OutputIterator _Result );

  2. template<class InputIterator1, class InputIterator2, class OutputIterator, class BinaryPredicate>OutputIterator set_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 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 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 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 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 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 36.17

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

// algorithm, set_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 = -2; i <= 3; i++)

      vec1a.push_back(i);

   int j;

   for(j =-2; j <= 1; 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 difference in ascending order with the default binary predicate less <int>()

   Result1 = set_difference(vec1a.begin(), vec1a.end(),

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

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

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

      cout<<*Iter1<<" ";

   cout<<endl;

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

   Result2 = set_difference(vec2a.begin(), vec2a.end(),

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

   cout<<"\nset_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 difference applying a user defined binary predicate mod_lesser()

   Result3 = set_difference(vec3a.begin(), vec3a.end(),

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

   cout<<"\nset_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_difference() program example

 

set_intersection()

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

  2. template<class InputIterator1, class InputIterator2, class OutputIterator, class BinaryPredicate>OutputIterator set_intersection( 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 intersection 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 intersection 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 intersection 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 intersection 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 intersection 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 36.18

 

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

  • The sorted source ranges referenced must be valid; all pointers must be dereferenceable 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.

  • 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 for nonempty source ranges.

 

// algorithm, set_intersection()

#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 = -2; i <= 2; i++)

     vec1a.push_back(i);

   int j;

   for(j = -4; j <= 0; 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 an intersection in ascending order with the default  binary predicate less <int>()

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

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

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

      cout<<*Iter1<<" ";

   cout<<endl;

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

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

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

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

      cout<<*Iter2<<" ";

   cout<<endl;

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

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

   cout<<"\nset_intersection() 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_intersection() program example

// ******algorandshuffle.cpp********

// algorithm, random_shuffle() - g++

#include <vector>

#include <algorithm>

#include <functional>

#include <iostream>

using namespace std;

 

int main()

{

   vector <int> vec1;

   vector <int>::iterator Iter1;

   int i;

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

     vec1.push_back(i);

   cout<<"The original of vector vec1 data:\n";

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

       cout<<*Iter1<<" ";

   cout<<endl;

   // random shuffle…

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

   cout<<"The original of vector vec1 random shuffle data:\n";

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

       cout<<*Iter1<<" ";

   cout<<endl;

   // shuffled once

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

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

   cout<<"Vector vec1 after reshuffle is:\n";

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

       cout<<*Iter1<<" ";

   cout<<endl;

   // shuffled again

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

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

   cout<<"Vector vec1 after another reshuffle is:\n";

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

       cout<<*Iter1<<" ";

   cout<<endl;

}

 

[bodo@bakawali ~]$ g++ algorandshuffle.cpp -o algorandshuffle

[bodo@bakawali ~]$ ./algorandshuffle

 

The original of vector vec1 data:

1 2 3 4 5 6 7 8 9 10

The original of vector vec1 random shuffle data:

5 4 8 9 1 6 3 2 7 10

Vector vec1 after reshuffle is:

7 1 8 9 6 4 10 3 2 5

Vector vec1 after another reshuffle is:

10 1 5 4 8 6 3 7 2 9

 

//*******algosearchn.cpp*********

// algorithm, search_n() - g++

// with some type conversion warning

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

   vector <int>::iterator Iter1;

   int i;

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

     vec1.push_back(5*i);

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

     vec1.push_back(5);

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

     vec1.push_back(5*i);

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

     vec1.push_back(5);

   cout<<"Vector vec1 data: ";

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

      cout<<*Iter1<<" ";

   cout<<endl;

   // searching vec1 for first match to (5 5 5) under identity

   vector <int>::iterator result1;

   result1 = search_n(vec1.begin(), vec1.end(), 3, 5);

   if(result1 == vec1.end())

      cout<<"\nThere is no match for a sequence (5 5 5) in vec1."<<endl;

   else

      cout<<"\nThere is at least one match of a sequence (5 5 5)\nin vec1 and the first one begins at "

          <<"position "<<result1 - vec1.begin()<<endl;

   // searching vec1 for first match to (5 5 5) under twice

   vector <int>::iterator result2;

   result2 = search_n(vec1.begin(), vec1.end(), 3, 5);

   if(result2 == vec1.end())

      cout<<"\nThere is no match for a sequence (5 5 5) in vec1 under the equivalence predicate twice."<<endl;

   else

      cout<<"\nThere is a match of a sequence (5 5 5) under the equivalence\npredicate twice"

          <<" in vec1 and the first one begins at position "<<result1 - vec1.begin()<<endl;

}

 

[bodo@bakawali ~]$ g++ algosearchn.cpp -o algosearchn

[bodo@bakawali ~]$ ./algosearchn

 

Vector vec1 data: 0 5 10 15 20 25 5 5 5 0 5 10 15 20 25 5 5 5

 

There is at least one match of a sequence (5 5 5)

in vec1 and the first one begins at position 6

 

There is a match of a sequence (5 5 5) under the equivalence

predicate twice in vec1 and the first one begins at position 6

 

 

tenouk C++ STL tutorial

 

 

 

 

 

 

 

 

 

 

 

Further C++ STL algorithm related reading:

 

  1. Source code for this tutorial is available in C++ STL Algorithm source code.

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

  3. Check the best selling C / C++ and STL books at Amazon.com.

  4. C++ Templates programming tutorials.

 

 

 

 

 

 

|< C++ STL Algorithm 12 | Main | C++ STL Algorithm 14 >| 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