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

# reverse_copy()

• Reverses the order of the elements within a source range while copying them into a destination range

template<class BidirectionalIterator, class OutputIterator>OutputIterator reverse_copy( BidirectionalIterator _First, BidirectionalIterator _Last, OutputIterator _Result );

# Parameters

## Parameter

_First

_Last

_Result

#### Table 36.12

• The return value is an output iterator pointing to the position one past the final element in the destination range to where the altered sequence of elements is being copied.

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

// algorithm, reverse_copy()

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

int main()

{

vector <int> vec1, vec2(11);

vector <int>::iterator Iter1, Iter2;

int i;

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

vec1.push_back(i);

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

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

cout<<*Iter1<<" ";

cout<<endl;

// reverse the elements in the vector

reverse_copy(vec1.begin(), vec1.end(), vec2.begin());

cout<<"The copy vec2 data of the reversed vector vec1 is:\n";

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

cout<<*Iter2<<" ";

cout<<endl;

cout<<"The original vector vec1 unmodified as:\n";

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

cout<<*Iter1<<" ";

cout<<endl;

}

# rotate()

• Exchanges the elements in two adjacent ranges.

`template<class ForwardIterator> void rotate( ForwardIterator _First, ForwardIterator _Middle, ForwardIterator _Last );`

# Parameters

## Parameter

_First

_Middle

_Last

#### Table 36.13

• The ranges 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 complexity is linear with at most (_Last – _First) swaps.

// algorithm, rotate()

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

int i;

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

vec1.push_back(i);

int j;

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

deq1.push_back(j);

cout<<"Vector vec1 data is: ";

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

cout<<*vec1Iter1 <<" ";

cout<<endl;

// let rotates...

rotate(vec1.begin(), vec1.begin() + 3, vec1.end());

cout<<"After rotating, vector vec1 data is: ";

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

cout<<*vec1Iter1<<" ";

cout<<endl;

cout<<"\nThe original deque deq1 is: ";

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

cout<<*deq1Iter1<<" ";

cout<<endl;

// let rotates…

int k = 1;

while(k <= deq1.end() - deq1.begin())

{

rotate(deq1.begin(), deq1.begin() + 1, deq1.end());

cout<<"Rotation of a single deque element to the back,\n deq1 is: ";

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

cout<<*deq1Iter1<<" ";

cout<<endl;

k++;

}

}

# rotate_copy()

• Exchanges the elements in two adjacent ranges within a source range and copies the result to a destination range.

template<class ForwardIterator, class OutputIterator>OutputIterator rotate_copy( ForwardIterator _First, ForwardIterator _Middle, ForwardIterator _Last, OutputIterator _Result );

# Parameters

#### Table 36.14

• The return value is an output iterator addressing the position one past the final element in the destination range.

• The ranges referenced must be valid; all pointers must be dereferenceable and within the sequence the last position is reachable from the first by incrementation.

• The complexity is linear with at most (_Last – _First) swaps.

// algorithm, rotate_copy()

#include <vector>

#include <deque>

#include <algorithm>

#include <iostream>

using namespace std;

int main()

{

vector <int> vec1, vec2(9);

deque <int> deq1, deq2(6);

vector <int>::iterator vec1Iter, vec2Iter;

deque<int>::iterator deq1Iter, deq2Iter;

int i;

for(i = -3; i <= 5; i++)

vec1.push_back(i);

int j;

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

deq1.push_back(j);

cout<<"Vector vec1 data is: ";

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

cout<<*vec1Iter<<" ";

cout<<endl;

rotate_copy(vec1.begin(), vec1.begin() + 3, vec1.end(), vec2.begin());

cout<<"\nAfter rotating, the vector vec1 data remains unchanged as:\n";

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

cout<<*vec1Iter<<" ";

cout<<endl;

cout<<"\nAfter rotating, the copy of vector vec1 in vec2 is,\n vec2:";

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

cout<<*vec2Iter<<" ";

cout<<endl;

cout<<"\nThe original deque deq1 is: ";

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

cout<<*deq1Iter<<" ";

cout<<endl;

int k = 1;

while(k <= deq1.end() - deq1.begin())

{

rotate_copy(deq1.begin(), deq1.begin() + 1, deq1.end(), deq2.begin());

cout<<"Rotation of a single deque element to the back,\n a deque copy, deq2 is: ";

for(deq2Iter = deq2.begin(); deq2Iter != deq2.end(); deq2Iter++)

cout<<*deq2Iter<<" ";

cout<<endl;

k++;

}

}

# search()

• Searches for the first occurrence of a sequence within a target range whose elements are equal to those in a given sequence of elements or whose elements are equivalent in a sense specified by a binary predicate to the elements in the given sequence.

1. template<class ForwardIterator1, class ForwardIterator2>ForwardIterator1 search( ForwardIterator1 _First1, ForwardIterator1 _Last1, ForwardIterator2 _First2, ForwardIterator2 _Last2 );

2. template<class ForwardIterator1, class ForwardIterator2, class Pr>ForwardIterator1 search( ForwardIterator1 _First1, ForwardIterator1 _Last1, ForwardIterator2 _First2, ForwardIterator2 _Last2, BinaryPredicate _Comp );

# Parameters

## Parameter

_First1

_Last1

_First2

_Last2

_Comp

#### Table 36.15

• The return value is a forward iterator addressing the position of the first element of the first subsequence that matches the specified sequence or that is equivalent in a sense specified by a binary predicate.

• The operator== used to determine the match between an element and the specified value must impose an equivalence relation between its operands.

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

• Average complexity is linear with respect to the size of the searched range, and worst case complexity is also linear with respect to the size of the sequence being searched for.

// algorithm, search() compiled 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;

list <int> lst1;

vector <int>::iterator Iter1, Iter2;

list <int>::iterator lst1_Iter, lst1_inIter;

int i;

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

vec1.push_back(5*i);

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

vec1.push_back(5*i);

int j;

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

lst1.push_back(5*j);

int k;

for(k = 2; k <= 4; k++)

vec2.push_back(10*k);

cout<<"Vector vec1 data: ";

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

cout<<*Iter1<<" ";

cout<<endl;

cout<<"List lst1 data: ";

for(lst1_Iter = lst1.begin(); lst1_Iter!= lst1.end(); lst1_Iter++)

cout<<*lst1_Iter<<" ";

cout<<endl;

cout<<"Vector vec2 data: ";

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

cout<<*Iter2<<" ";

cout<<endl<<endl;

// searching vec1 for first match to lst1 under identity

vector <int>::iterator result1;

result1 = search (vec1.begin(), vec1.end(), lst1.begin(), lst1.end());

if(result1 == vec1.end())

cout<<"There is no match of lst1 in vec1."<<endl;

else

cout<<"There is at least one match of lst1 in vec1\nand the first one begins at "

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

// searching vec1 for a match to lst1 under the binary predicate twice

vector <int>::iterator result2;

result2 = search(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), twice);

if(result2 == vec1.end())

cout<<"\nThere is no match of lst1 in vec1."<<endl;

else

cout<<"\nThere is a sequence of elements in vec1 that are equivalent\nto those in vec2 under the binary "

<<"predicate twice\nand the first one begins at position "<<result2 - vec1.begin()<<endl;

}

# search_n()

• Searches for the first subsequence in a range that of a specified number of elements having a particular value or a relation to that value as specified by a binary predicate.

1. template<class ForwardIterator1, class Diff2, class Type>ForwardIterator1 search_n( ForwardIterator1 _First1, ForwardIterator1 _Last1, Size2 _Count, const Type& _Val );

2. template<class ForwardIterator1, class Size2, class Type, class BinaryPredicate>ForwardIterator1 search_n( ForwardIterator1 _First1, ForwardIterator1 _Last1, Size2 _Count, const Type& _Val, BinaryPredicate _Comp );

# Parameters

#### Table 36.16

• The return value is a forward iterator addressing the position of the first element of the first subsequence that matches the specified sequence or that is equivalent in a sense specified by a binary predicate.

• The operator== used to determine the match between an element and the specified value must impose an equivalence relation between its operands.

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

• Complexity is linear with respect to the size of the searched.

// algorithm, search_n(), 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;

}

# Further C++ STL algorithm related reading:

1. C++ Templates programming tutorials.

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

3. Acomplete C Standard Library.

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

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