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

# 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

_First

_Last

_Comp

#### 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: # swap()

• Exchanges the values of the elements between two types of objects, assigning the contents of the first object to the second object and the contents of the second to the first.

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

# Parameters

## Parameter

_Left

_Right

#### Table 37.7

• This algorithm is exceptional in the STL in being designed to operate on individual elements rather than on a range of elements.

// 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: # swap_ranges()

• Exchanges the elements of one range with the elements of another, equal sized range.

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

# Parameters

## Parameter

_First1

_Last1

_First2

#### Table 37.8

• The return value is a forward iterator pointing to one past the final position of the second range whose elements are to be exchanged.

• The ranges referenced must be valid; all pointers must be de-referenceable and within each sequence the last position is reachable from the first by incrementation.  The second range has to be as large as the first range.

• The complexity is linear with _Last1 – _First1 swaps performed.  If elements from containers of the same type are being swapped, them the swap() member function from that container should be used, because the member function typically has constant complexity.

// 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: # transform()

• Applies a specified function object to each element in a source range or to a pair of elements from two source ranges and copies the return values of the function object into a destination range.

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

_First1

_Last1

_First2

_Result

_Func

#### Table 37.9

• The return value is an output iterator addressing the position one past the final element in the destination range that is receiving the output elements transformed by the function object.

• The 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 must be large enough to contain the transformed source range.

• If_Result is set equal to_First1 in the first version of the algorithm, then the source and destination ranges will be the same and the sequence will be modified in place.  But the _Result may not address a position within the range [_First1 +1, _Last1).

• The complexity is linear with at most (_Last1 – _First1) comparisons.

// 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: # unique()

• Removes duplicate elements that are adjacent to each other in a specified range.

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

_First

_Last

_Comp

#### 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: # unique_copy()

• Copies elements from a source range into a destination range except for the duplicate elements that are adjacent to each other.

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

_First

_Last

_Result

_Comp

#### Table 37.11

• The return value is an output iterator addressing the position one past the final element in the destination range that is receiving the copy with consecutive duplicates 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 ranges referenced must be valid; all pointers must be de-referenceable and within a sequence the last position is reachable from the first by incrementation.

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

// 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: # upper_bound()

• Finds the position of the first element in an ordered range that has a value that is greater than a specified value, where the ordering criterion may be specified by a binary predicate.

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

_Firs

_Last

_Val

_Comp

#### Table 37.12

• The return value is a forward iterator addressing the position of the first element in an ordered range that has a value that is greater than a specified value, where the ordering criterion may be specified by a binary predicate.

• The sorted source range referenced must be valid; all pointers must be de-referenceable and within the sequence the last position must be reachable from the first by incrementation.

• The sorted range must each be arranged as a precondition to the application of the upper_bound() algorithm in accordance with the same ordering as is to be used by the algorithm to sort the combined ranges.

• The range is not modified by the algorithm merge().

• The value types of the forward 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

• The complexity of the algorithm is logarithmic for random-access iterators and linear otherwise, with the number of steps proportional to(_Last1 – _First1).

// 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: • The following is a program example compiled usingg++.

// ******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.