|< C++ STL Algorithm 14 | Main | C++ STL Function Objects & Misc. >| Site Index | Download |


 

 

 

 

MODULE 37_1

THE C++ STL ALGORITHM PART 15

 

 

 

 

 

 

 

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, stable_sort() program example

  2. Algorithm, swap() program example

  3. Algorithm, swap_ranges() program example

  4. Algorithm, transform() program example

  5. Algorithm, unique() program example

  6. Algorithm, unique_copy() program example

  7. Algorithm, upper_bound() program example

  8. Algorithm, sort() program example - g++

 

stable_sort()

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

  1. template<class BidirectionalIterator> void stable_sort( BidirectionalIterator _First, BidirectionalIterator _Last );

  2. template<class BidirectionalIterator, class BinaryPredicate>void stable_sort( 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 sorted.

_Last

A bidirectional 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.6

  • 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 stable and guarantees that the relative ordering of equivalent elements will be preserved.

  • The run-time complexity of stable_sort() depends on the amount of memory available, but the best case (given sufficient memory) is O(N log N) and the worst case is O(N(log N)2), where N = _Last–First. Usually, the sort() algorithm is significantly faster than stable_sort().

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

// algorithm, stable_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;

   vector <int>::iterator Iter1;

   for (int i=10; i<=20; 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(vec1.begin(), vec1.end());

   cout<<"\nDefault sorted 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, stable_sort() program example

 

swap()

template<class Type>  void swap( Type& _Left, Type& _Right );

 

Parameters

 

Parameter

Description

_Left

The first object to have its elements exchanged.

_Right

The second object to have its elements exchanged.

 

Table 37.7

// algorithm, swap()

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

     vec1.push_back(i);

   int j;

   for(j = 10; j <= 15; j++)

     vec2.push_back(j);

   cout<<"Vector vec1 data is:\n";

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

      cout<<*Iter1<<" ";

   cout<<endl;

   cout<<"\nVector vec2 data is:\n";

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

      cout<<*Iter2<<" ";

   cout<<endl;

   swap(vec1, vec2);

   cout<<"\nNow, vector vec1 data is:\n";

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

      cout<<*Iter1<<" ";

   cout<<endl;

   cout<<"\nThen, vector vec2 data is:\n";

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

      cout<<*Iter2<<" ";

   cout<<endl;

}

 

Output:

 

C++ STL Algorithm, swap() program example

 

swap_ranges()

template<class ForwardIterator1, class ForwardIterator2>
   ForwardIterator2 swap_ranges( ForwardIterator1 _First1, ForwardIterator1 _Last1, ForwardIterator2 _First2 );

 

Parameters

 

Parameter

Description

_First1

A forward iterator pointing to the first position of the first range whose elements are to be exchanged.

_Last1

A forward iterator pointing to one past the final position of the first range whose elements are to be exchanged.

_First2

A forward iterator pointing to the first position of the second range whose elements are to be exchanged.

 

Table 37.8

// algorithm, swap_ranges()

#include <vector>

#include <deque>

#include <algorithm>

#include <iostream>

using namespace std;

 

int main()

{

   vector <int> vec1;

   deque <int> deq1;

   vector <int>::iterator vec1Iter1;

   deque<int>::iterator deq1Iter;

   int i;

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

     vec1.push_back(i);

   int j;

   for(j =24; j <= 29; j++)

     deq1.push_back(j);

   cout<<"Vector vec1 data:\n";

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

      cout<<*vec1Iter1<<" ";

   cout<<endl;

   cout<<"\nDeque deq1 data:\n";

   for(deq1Iter = deq1.begin(); deq1Iter != deq1.end(); deq1Iter++)

      cout<<*deq1Iter<<" ";

   cout<<endl;

   swap_ranges(vec1.begin(), vec1.end(), deq1.begin());

   cout<<"\nAfter the swap_range(), vector vec1 data:\n";

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

      cout<<*vec1Iter1<<" ";

   cout<<endl;

   cout<<"\nAfter the swap_range() deque deq1 data:\n";

   for(deq1Iter = deq1.begin(); deq1Iter != deq1.end(); deq1Iter++)

      cout<<*deq1Iter<<" ";

   cout<<endl;

}

 

Output:

 

C++ STL Algorithm, swap_ranges() program example

 

transform()

  1. template<class InputIterator, class OutputIterator, class UnaryFunction>OutputIterator transform( InputIterator _First1, InputIterator _Last1, OutputIterator _Result, UnaryFunction _Func );

  2. template<class InputIterator1, class InputIterator2, class OutputIterator, class BinaryFunction>OutputIterator transform( InputIterator1 _First1, InputIterator1 _Last1, InputIterator2 _First2, OutputIterator _Result, BinaryFunction _Func );

Parameters

 

Parameter

Description

_First1

An input iterator addressing the position of the first element in the first source range to be operated on.

_Last1

An input iterator addressing the position one past the final element in the first source range operated on.

_First2

An input iterator addressing the position of the first element in the second source range to be operated on.

_Result

An output iterator addressing the position of the first element in the destination range.

_Func

User-defined unary function object used in the first version of the algorithm that is applied to each element in the first source range or A user-defined binary function object used in the second version of the algorithm that is applied pairwise, in a forward order, to the two source ranges.

 

Table 37.9

// algorithm, transform()

#include <vector>

#include <algorithm>

#include <functional>

#include <iostream>

using namespace std;

 

// the function object multiplies an element by a Factor

template <class Type>

class MultValue

{

   private:

      // the value to multiply by

      Type Factor;

   public:

      // constructor initializes the value to multiply by

      MultValue(const Type& _Val) : Factor(_Val) {    }

      // the function call for the element to be multiplied

      int operator()(Type& elem) const

      {return (elem * Factor);}

};

 

int main()

{

   vector <int> vec1, vec2(7), vec3(7);

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

   // constructing vector vec1

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

     vec1.push_back(i);

   cout<<"Original vector vec1 data: ";

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

      cout<<*Iter1<<" ";

   cout<<endl;

   // modifying the vector vec1 in place

   transform(vec1.begin(), vec1.end(), vec1.begin(), MultValue<int>(2));

   cout<<"\nThe elements of the vector vec1 multiplied by 2 in place gives:\nvec1mod data: ";

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

      cout<<*Iter1<<" ";

   cout<<endl;

   // using transform() to multiply each element by a factor of 5

   transform(vec1.begin(), vec1.end(), vec2.begin(), MultValue<int>(5));

   cout<<"\nMultiplying the elements of the vector vec1mod\nby the factor 5 & copying to vec2 gives:\nvec2 data: ";

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

      cout<<*Iter2<<" ";

   cout<<endl;

   // the second version of transform used to multiply the elements of the vectors vec1mod & vec2 pairwise

   transform(vec1.begin(), vec1.end(), vec2.begin(), vec3.begin(), multiplies<int>());

   cout<<"\nMultiplying elements of the vectors vec1mod and vec2 pairwise gives:\nvec3 data: ";

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

      cout<<*Iter3<<" ";

   cout<<endl;

}

 

Output:

 

C++ STL Algorithm, transform() program example

 

unique()

  1. template<class ForwardIterator> ForwardIterator unique( ForwardIterator _First, ForwardIterator _Last );
  2. template<class ForwardIterator, class Pr> ForwardIterator unique( ForwardIterator _First, 
			ForwardIterator _Last, BinaryPredicate _Comp );

Parameters

 

Parameter

Description

_First

A forward iterator addressing the position of the first element in the range to be scanned for duplicate removal.

_Last

A forward iterator addressing the position one past the final element in the range to be scanned for duplicate removal.

_Comp

User-defined predicate function object that defines the condition to be satisfied if two elements are to be taken as equivalent. A binary predicate takes two arguments and returns true when satisfied and false when not satisfied.

 

Table 37.10

 

  • The return value is a forward iterator to the new end of the modified sequence that contains no consecutive duplicates, addressing the position one past the last element not removed.

  • Both forms of the algorithm remove the second duplicate of a consecutive pair of equal elements.

  • The operation of the algorithm is stable so that the relative order of the undeleted elements is not changed.

  • 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 number of elements in the sequence is not changed by the algorithm unique() and the elements beyond the end of the modified sequence are de-referenceable but not specified.

  • The complexity is linear, requiring (_Last – _First) – 1 comparisons.

  • List provides a more efficient member function unique(), which may perform better.

  • These algorithms cannot be used on an associative container.

 

// algorithm, unique()

#include <vector>

#include <algorithm>

#include <functional>

#include <iostream>

using namespace std;

 

// return whether modulus of elem1 is equal to modulus of elem2

bool mod_equal(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 vec1_Iter1, vec1_Iter2, vec1_Iter3, vec1_NewEnd1, vec1_NewEnd2, vec1_NewEnd3;

   int i;

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

   {

      vec1.push_back(4);

      vec1.push_back(-4);

   }

 

   int j;

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

     vec1.push_back(8);

   vec1.push_back(9);

   vec1.push_back(9);

   cout<<"Vector vec1 data:\n";

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

      cout<<*vec1_Iter1<<" ";

   cout<<endl;

   // remove consecutive duplicates

   vec1_NewEnd1 = unique(vec1.begin(), vec1.end());

   cout<<"\nRemoving adjacent duplicates from vector vec1 gives:\n";

   for(vec1_Iter1 = vec1.begin(); vec1_Iter1 != vec1_NewEnd1; vec1_Iter1++)

      cout<<*vec1_Iter1<<" ";

   cout<<endl;

   // remove consecutive duplicates under the binary predicate mod_equal()

   vec1_NewEnd2 = unique(vec1.begin(), vec1_NewEnd1, mod_equal);

   cout<<"\nRemoving adjacent duplicates from vector vec1 under\nthe binary predicate mod_equal() gives:\n";

   for(vec1_Iter2 = vec1.begin(); vec1_Iter2 != vec1_NewEnd2; vec1_Iter2++)

      cout<<*vec1_Iter2<<" ";

   cout<<endl;

   // remove elements if preceded by an element that was greater

   vec1_NewEnd3 = unique(vec1.begin(), vec1_NewEnd2, greater<int>());

   cout<<"\nRemoving adjacent elements satisfying the binary\npredicate mod_equal() from vector vec1 gives:\n";

   for(vec1_Iter3 = vec1.begin(); vec1_Iter3 != vec1_NewEnd3; vec1_Iter3++)

      cout<<*vec1_Iter3<<" ";

   cout<<endl;

}

 

Output:

 

C++ STL Algorithm, unique() program example

 

unique_copy()

  1. template<class InputIterator, class OutputIterator> OutputIterator unique_copy( InputIterator _First, InputIterator _Last, OutputIterator _Result );

  2. template<class InputIterator, class OutputIterator, class BinaryPredicate>OutputIterator unique_copy( InputIterator _First, InputIterator _Last, OutputIterator _Result, BinaryPredicate _Comp);

Parameters

 

Parameter

Description

_First

A forward iterator addressing the position of the first element in the source range to be copied.

_Last

A forward iterator addressing the position one past the final element in the source range to be copied.

_Result

An output iterator addressing the position of the first element in the destination range that is receiving the copy with consecutive duplicates removed.

_Comp

User-defined predicate function object that defines the condition to be satisfied if two elements are to be taken as equivalent. A binary predicate takes two arguments and returns true when satisfied and false when not satisfied.

 

Table 37.11

// algorithm, unique_copy()

#include <vector>

#include <algorithm>

#include <functional>

#include <iostream>

using namespace std;

 

// return whether modulus of elem1 is equal to modulus of elem2

bool mod_equal(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 vec1_Iter1, vec1_Iter2, vec1_NewEnd1, vec1_NewEnd2;

   int i;

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

   {

      vec1.push_back(8);

      vec1.push_back(-8);

   }

   int j;

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

     vec1.push_back(5);

   vec1.push_back(9);

   vec1.push_back(9);

   int k;

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

     vec1.push_back(12);

   cout<<"Vector vec1 data is:\n";

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

      cout<<*vec1_Iter1<<" ";

   cout<<endl;

   // copy first half to second, removing consecutive duplicates

   vec1_NewEnd1 = unique_copy(vec1.begin(), vec1.begin() + 8, vec1.begin() + 8);

   cout<<"\nCopying the first half of the vector to the second half\nwhile removing adjacent duplicates gives:\n";

   for(vec1_Iter1 = vec1.begin(); vec1_Iter1 != vec1_NewEnd1; vec1_Iter1++)

      cout<<*vec1_Iter1<<" ";

   cout<<endl;

   for(int l = 0; l <= 7; l++)

     vec1.push_back(10);

   // remove consecutive duplicates under the binary predicate mod_equals

   vec1_NewEnd2 = unique_copy(vec1.begin(), vec1.begin() + 14, vec1.begin() + 14, mod_equal);

   cout<<"\nCopying the first half of the vector to the second half\nremoving adjacent duplicates under mod_equal() gives\n";

   for(vec1_Iter2 = vec1.begin(); vec1_Iter2 != vec1_NewEnd2; vec1_Iter2++)

      cout<<*vec1_Iter2<<" ";

   cout<<endl;

}

 

Output:

 

C++ STL Algorithm, unique_copy() program example

 

upper_bound()

  1. template<class ForwardIterator, class Type>ForwardIterator upper_bound( ForwardIterator _First, ForwardIterator _Last, const Type& _Val );

  2. template<class ForwardIterator, class Type, class Pr>ForwardIterator upper_bound( ForwardIterator _First, ForwardIterator _Last, const Type& _Val, BinaryPredicate _Comp );

Parameters

 

Parameter

Description

_Firs

The position of the first element in the range to be searched.

_Last

The position one past the final element in the range to be searched.

_Val

The value in the ordered range that needs to be exceeded by the value of the element addressed by the iterator returned.

_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.12

// algorithm, upper_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

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

     vec1.push_back(i);

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

     vec1.push_back(j);

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

   cout<<"Original vector vec1 data with range\nsorted by the binary predicate less than is:\n";

   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;

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

   cout<<"\nOriginal vector vec2 data with range\nsorted by the binary predicate greater is:\n";

   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;

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

   cout<<"\nOriginal vector vec3 data with range\nsorted by the binary predicate mod_lesser is:\n";

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

      cout<<*Iter3<<" ";

   cout<<endl;

   // upper_bound of -3 in vec1 with default binary predicate less <int>()

   Result1 = upper_bound(vec1.begin(), vec1.end(), -3);

   cout<<"\nThe upper_bound in vec1 for the element with a value of -3 is: "<<*Result1<<endl;

   // upper_bound of 2 in vec2 with the binary predicate greater <int>()

   Result2 = upper_bound(vec2.begin(), vec2.end(), 2, greater<int>());

   cout<<"\nThe upper_bound in vec2 for the element with a value of 2 is: "<<*Result2<<endl;

   // upper_bound of 3 in vec3 with the binary predicate mod_lesser

   Result3 = upper_bound(vec3.begin(), vec3.end(), 3, mod_lesser);

   cout<<"\nThe upper_bound in vec3 for the element with a value of 3 is: "<<*Result3<<endl;

}

 

Output:

 

C++ STL Algorithm, upper_bound() program example

// ******algosort.cpp*********

// algorithm, sort() - g++

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

}

 

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

[bodo@bakawali ~]$ ./algosort

 

Original random shuffle vector vec1 data:

4 10 11 15 14 5 13 1 6 9 3 7 8 2 0 12

 

Sorted vector vec1 data:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

 

Re sorted (greater) vector vec1 data:

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

 

User defined re sorted vector vec1 data:

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

 

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. C++ Templates programming tutorials.

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

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

 

 

 

 

 

 

 

|< C++ STL Algorithm 14 | Main | C++ STL Function Objects & Misc. >| 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