|< 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 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?

  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.  Thesort() algorithm is stable and guarantees that the relative ordering of equivalent elements will be preserved.

  • The run-time complexity ofstable_sort() depends on the amount of memory available, but the best case (given sufficient memory) is O(N log N) and the worst case isO(N(log N)2), whereN = _Last–First. Usually, thesort() 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 algorithmunique() 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 inC++ STL Algorithm source code.

  2. C++ Templates programming tutorials.

  3. Acomplete C Standard Library.

  4. Acomplete C++ Standard Library documentation that includes STL.

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