|< C++ STL Algorithm 11 | Main | C++ STL Algorithm 13 >| Site Index | Download |

---

 

 

 

 

 

MODULE 36a

THE C++ STL ALGORITHM PART 12

 

 

 

 

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? Algorithm, reverse_copy() program example Algorithm, rotate() program example Algorithm, rotate_copy() program example Algorithm, search() program example Algorithm, search_n() program example   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 Description _First A bidirectional iterator pointing to the position of the first element in the source range within which the elements are being permuted. _Last A bidirectional iterator pointing to the position one past the final element in the source range within which the elements are being permuted. _Result An output iterator pointing to the position of the first element in the destination range to which elements are being copied.   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;

}

 

Output:

 

 

rotate()

 

• Exchanges the elements in two adjacent ranges.

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

 

Parameters

 

• 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++;

   }

}

 

Output:

 

 

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

 

• 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++;

   }

}

 

Output:

 

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

 

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

}

 

Output:

 

 

 

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

 

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

}

 

Output:

 

 

tenouk C++ STL tutorial

 

 

 

 

 

 

 

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.

 

 

 

 

 

 

 

|< C++ STL Algorithm 11 | Main | C++ STL Algorithm 13 >| 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