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

---

 

 

 

 

 

 

MODULE 36

THE C++ STL ALGORITHM PART 10

 

 

 

 

 

My Training Period: xx hours   More code samples compiled using MicrosoftVisual C++ .Net, win32 empty console mode application. g++ compilation examples given at the end of this Module. Source code for this tutorial is available 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. Able to understand how the containers, iterators and algorithm work.   What do we have in this page? Algorithm, push_heap(), make_heap() program example Algorithm, random_shuffle() program example Algorithm, remove() program example Algorithm, remove_copy() program example Algorithm, remove_copy_if() program example     push_heap() Adds an element that is at the end of a range to an existing heap consisting of the prior elements in the range. template<class RandomAccessIterator> void push_heap( RandomAccessIterator _First, RandomAccessIterator _Last ); template<class RandomAccessIterator, class BinaryPredicate> void push_heap( RandomAccessIterator _First, RandomAccessIterator _Last, BinaryPredicate _Comp );   Parameters   Parameter Description _First A random-access iterator addressing the position of the first element in the heap. _Last A random-access iterator addressing the position one past the final element in the range to be converted into a heap. _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 36.1

 

 

 

 

 

 

 

• The element must first be pushed back to the end of an existing heap and then the algorithm is used to add this element to the existing heap.  Repeat again, heaps have two properties:

1. The first element is always the largest.

2. Elements may be added or removed in logarithmic time.

• Heaps are an ideal way to implement priority queues and they are used in the implementation of the STL container adaptor priority_queue class.

• 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 range excluding the newly added element at the end must be a heap.

• The complexity is logarithmic, requiring at most log (_Last – _First) comparisons.

// algorithm, push_heap(), make_heap()

#include <vector>

#include <algorithm>

#include <functional>

#include <iostream>

using namespace std;

 

int main()

{

   vector <int> vec1;

   vector <int>::iterator Iter1;

   int i;

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

     vec1.push_back(i);

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

   cout<<"Given vector vec1 data: ";

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

      cout<<*Iter1<<" ";

   cout<<endl;

   // make vec1 a heap with default less than ordering

   cout<<"\nmake_heap()..."<<endl;

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

   cout<<"The default heaped version of vector vec1:\n";

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

      cout<<*Iter1<<" ";

   cout<<endl;

   // add elements to the heap

   cout<<"\npush_back() some data...\n";

   vec1.push_back(11);

   vec1.push_back(12);

   cout<<"The new heap vec1 with data pushed back:\n";

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

      cout<<*Iter1<<" ";

   cout<<endl;

   cout<<"\npush_heap()...."<<endl;

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

   cout<<"The default reheaped vec1 with data added is:\n";

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

      cout<<*Iter1<<" ";

   cout<<endl;

   // make vec1 a heap with greater than ordering

   cout<<"\nmake_heap()..."<<endl;

   make_heap(vec1.begin(), vec1.end(), greater<int>());

   cout<<"The greater than heaped version of vec1 data:\n ";

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

      cout<<*Iter1<<" ";

   cout<<endl;

   cout<<"\npush_back()..."<<endl;

   vec1.push_back(0);

   cout<<"The greater than heap vec1 with 13 pushed back is:\n";

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

      cout<<*Iter1<<" ";

   cout<<endl;

   cout<<"\npush_heap()...."<<endl;

   push_heap(vec1.begin(), vec1.end(), greater<int>());

   cout<<"The greater than reheaped vec1 with 13 added is:\n";

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

      cout<<*Iter1<<" ";

   cout<<endl;

}

 

Output:

 

 

random_shuffle()

• Rearranges a sequence of N elements in a range into one of N! possible arrangements selected at random.

1. template<class RandomAccessIterator> void random_shuffle( RandomAccessIterator _First, RandomAccessIterator _Last );

2. template<class RandomAccessIterator, class RandomNumberGenerator>void random_shuffle( RandomAccessIterator _First, RandomAccessIterator _Last, RandomNumberGenerator& _Rand );

 

Parameters

 

• The two versions (refer to the templates) of the function differ in how they generate random numbers.

• The first version uses an internal random number generator and the second a random number generator function object that is explicitly passed and can accept a seed value.

// algorithm, random_shuffle()

#include <vector>

#include <algorithm>

#include <functional>

#include <iostream>

using namespace std;

 

int main()

{

   vector <int> vec1;

   vector <int>::iterator Iter1;

   int i;

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

     vec1.push_back(i);

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

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

   cout<<*Iter1<<" ";

   cout<<endl;

   // random shuffle…

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

   cout<<"The original of vector vec1 random shuffle data:\n";

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

   cout<<*Iter1<<" ";

   cout<<endl;

   // shuffled once

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

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

   cout<<"Vector vec1 after reshuffle is:\n";

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

   cout<<*Iter1<<" ";

   cout<<endl;

   // re-shuffled...again

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

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

   cout<<"Vector vec1 after another reshuffle is:\n";

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

   cout<<*Iter1<<" ";

   cout<<endl;

}

 

Output:

 

 

remove()

• Eliminates a specified value from a given range without disturbing the order of the remaining elements and returning the end of a new range free of the specified value.

template<class ForwardIterator, class Type> ForwardIterator remove( ForwardIterator _First, ForwardIterator _Last, const Type& _Val );

 

Parameters

 

 

The return value is a forward iterator addressing the new end position of the modified range, one past the final element of the remnant sequence free of the specified value. 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 order of the elements not removed remains stable. Theoperator== used to determine the equality between elements must impose an equivalence relation between its operands. The complexity is linear; there are (_Last – _First) comparisons for equality. The list Class class has a more efficient member function version ofremove(), which also re-links pointers.

// algorithm, remove()

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

 

int main()

{

   vector <int> vec1;

   vector <int>::iterator Iter1, new_end;

   int i;

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

   vec1.push_back(i);

   int j;

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

     vec1.push_back(8);

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

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

      cout<<*Iter1<<" ";

   cout<<endl;

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

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

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

       cout<<*Iter1<<" ";

   cout<<endl;

   // remove elements with a value of 8

   new_end = remove(vec1.begin(), vec1.end(), 8);

   cout<<"Vector vec1 data with value 8 removed is:\n";

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

       cout<<*Iter1<<" ";

   cout<<endl;

   // using erase, to change the sequence size

   vec1.erase(new_end, vec1.end());

   cout<<"Vector vec1 resized data with value 8 removed is:\n";

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

       cout<<*Iter1<<" ";

   cout<<endl;

}

 

Output:

 

 

remove_copy()

• Copies elements from a source range to a destination range, except that elements of a specified value are not copied, without disturbing the order of the remaining elements and returning the end of a new destination range.

template<class InputIterator, class OutputIterator, class Type>

   OutputIterator remove_copy( InputIterator _First, InputIterator _Last, OutputIterator _Result, const Type& _Val );

 

Parameters

 

• The return value is a forward iterator addressing the new end position of the destination range, one past the final element of the copy of the remnant sequence free of the specified value.

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

• There must be enough space in the destination range to contain the remnant elements that will be copied after elements of the specified value are removed.

• The order of the elements not removed remains stable.

• Theoperator== used to determine the equality between elements must impose an equivalence relation between its operands.

• The complexity is linear; there are (_Last – _First) comparisons for equality and at most (_Last – _First) assignments.

// algorithm, remove_copy()

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

 

int main()

{

   vector <int> vec1, vec2(10);

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

   int i;

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

     vec1.push_back(i);

   int j;

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

     vec1.push_back(5);

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

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

      cout<<*Iter1<<" ";

   cout<<endl;

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

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

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

      cout<<*Iter1<<" ";

   cout<<endl;

   // remove elements with a value of 5

   new_end = remove_copy(vec1.begin(), vec1.end(), vec2.begin(), 5);

   cout<<"Vector vec1 is left unchanged as:\n";

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

      cout<<*Iter1<<" ";

   cout<<endl;

   cout<<"Vector vec2 is a copy of vec1 with the value 5 removed:\n";

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

      cout<<*Iter2<<" ";

   cout<<endl;

}

 

Output:

 

 

remove_copy_if()

• Copies elements from a source range to a destination range, except that satisfying a predicate are not copied, without disturbing the order of the remaining elements and returning the end of a new destination range.

template<class InputIterator, class OutputIterator, class Predicate>

   OutputIterator remove_copy_if( InputIterator _First, InputIterator _Last, OutputIterator _Result, Predicate _Pred );

 

Parameters

 

• The return value is a forward iterator addressing the new end position of the destination range, one past the final element of the remnant sequence free of the elements satisfying the predicate.

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

• There must be enough space in the destination range to contain the remnant elements that will be copied after elements of the specified value are removed.

• The order of the elements not removed remains stable.

• Theoperator== used to determine the equality between elements must impose an equivalence relation between its operands.

• The complexity is linear: there are (_Last – _First) comparisons for equality and at most (_Last – _First) assignments.

// algorithm, remove_copy_if()

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

 

bool greathan(int value)

{ return value >7;}

 

int main()

{

   vector <int> vec1, vec2(14);

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

   int i;

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

    vec1.push_back(i);

   int j;

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

    vec1.push_back(5);

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

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

      cout<<*Iter1<<" ";

   cout<<endl;

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

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

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

      cout<<*Iter1<<" ";

   cout<<endl;

   // remove elements with a value greater than 7

   new_end = remove_copy_if(vec1.begin(), vec1.end(), vec2.begin(), greathan);

   cout<<"After the remove_copy_if() the vector,\nvec1 is left unchanged as ";

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

      cout<<*Iter1<<" ";

   cout<<endl;

   cout<<"Vector vec2 is a copy of vec1 with values greater than 7 removed:\n";

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

      cout<<*Iter2<<" ";

   cout<<endl;

}

 

Output:

 

 

tenouk C++ STL tutorial

 

 

 

 

 

 

 

Further C++ STL algorithm related reading:

 

1. Source code for this tutorial is available inC++ STL Algorithm source code.

2. Check thebest selling C / C++ and STL books at Amazon.com.

3. C++ Templates programming tutorials.

4. Acomplete C Standard Library.

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

 

 

 

 

 

 

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