|< C++ STL Algorithm 2 | Main | C++ STL Algorithm 4 >| Site Index | Download |


 

 

 

 

 

MODULE 34_1

THE C++ STL ALGORITHM PART 3

 

 

 

 

 

My Training Period:        hours

 

Continue from the previous Module, more algorithm member functions program examples. Compiled using Microsoft Visual C++/.Net, win32 empty console mode application. g++ compilation on Fedora Core 3 examples given at the end of this Module. Source code in text is available in C++ Algorithm source code sample.

 

The C++ STL algorithm knowledge that supposed to be acquired:

 

 

What do we have in this session?

  1. Algorithm, copy_backward() program example

  2. Algorithm, count() program example

  3. Algorithm, count_if() program example

  4. Algorithm, the countif() program example

  5. Algorithm, equal() program example

  6. Algorithm, equal_range() program example

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

copy_backward()

  • Assigns the values of elements from a source range to a destination range, iterating through the source sequence of elements and assigning them new positions in a backward direction.

          template<class BidirectionalIterator1, class BidirectionalIterator2>

                      BidirectionalIterator2 copy_backward( BidirectionalIterator1 _First,

                               BidirectionalIterator1 _Last, BidirectionalIterator2 _DestEnd );

 

Parameters

 

Parameter

Description

_First

A bidirectional iterator addressing the position of the first element in the source range.

_Last

A bidirectional iterator addressing the position that is one past the final element in the source range.

_DestEnd

A bidirectional iterator addressing the position of the one past the final element in the destination range.

 

Table 34.5

  • The return value is an output iterator addressing the position that is one past the final element in the destination range, that is, the iterator addresses _DestEnd – (_Last – _First).

  • The source range must be valid and there must be sufficient space at the destination to hold all the elements being copied.

  • The copy_backward() algorithm imposes more stringent requirements than that the copy algorithm. Both its input and output iterators must be bidirectional.

  • The copy_backward() algorithm is the only STL algorithm designating the output range with an iterator pointing to the end of the destination range.

  • Because the algorithm copies the source elements in order beginning with the last element, the destination range can overlap with the source range provided the _Last position of the source range is not contained in the destination range.

  • copy() can be used to shift elements to the right but not the left, unless there is no overlap between the source and destination ranges. To shift to the left any number of positions, use the copy() algorithm.

  • The copy_backward() algorithm only modifies values pointed to by the iterators, assigning new values to elements in the destination range. It cannot be used to create new elements and cannot insert elements into an empty container directly.

// algorithm, copy_backward()

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

 

int main()

{

    vector <int> vec1, vec2;

    vector <int>::iterator Iter1, Iter2;

    int i;

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

        vec1.push_back(i);

    int j;

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

        vec2.push_back(j);

    cout<<"vec1 data: ";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    cout<<"vec2 data: ";

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

        cout<<*Iter2<<" ";

    cout<<endl;

    // to copy_backward the first 4 elements of vec1 into the middle of vec2

    copy_backward(vec1.begin(), vec1.begin() + 4, vec2.begin() + 8);

    cout<<"vec2 with vec1 insert data: ";

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

        cout<<*Iter2<<" ";

    cout<<endl;

    // to shift the elements inserted into vec2 two positions to the right

    copy_backward(vec2.begin()+4, vec2.begin()+7, vec2.begin()+9);

    cout<<"vec2 with shifted insert data: ";

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

        cout<<*Iter2<<" ";

    cout<<endl;

    return 0;

}

 

Output:

 

C++ STL Algorithm copy_backward()

 

count()

template<class InputIterator, class Type>
   typename iterator_traits<InputIterator>::difference_type count( InputIterator _First,
	InputIterator _Last, const Type& _Val );

 

Parameters

 

Parameter

Description

_First

An input iterator addressing the position of the first element in the range to be traversed.

_Last

An input iterator addressing the position one past the final element in the range to be traversed.

_Val

The value of the elements to be counted.

 

Table 34.6

// algorithm, count()

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

 

int main()

{

    vector <int> vec;

    vector <int>::iterator Iter;

    vec.push_back(12);

    vec.push_back(22);

    vec.push_back(12);

    vec.push_back(31);

    vec.push_back(12);

    vec.push_back(33);

    cout<<"vec data: ";

    for(Iter = vec.begin(); Iter != vec.end(); Iter++)

        cout<<*Iter<<" ";

    cout<<endl;

    int result;

    cout<<"\nOperation: count(vec.begin(), vec.end(), 12)\n";

    result = count(vec.begin(), vec.end(), 12);

    cout<<"The number of 12s in vec is: "<<result<<endl;

    return 0;

}

 

Output:

 

C++ STL Algorithm count()

 

count_if()

                template<class InputIterator, class Predicate>typename iterator_traits<InputIterator>::difference_typecount_if(

                                        InputIterator _First, InputIterator _Last, Predicate _Pred );

 

Parameters

 

Parameter

Description

_First

An input iterator addressing the position of the first element in the range to be searched.

_Last

An input iterator addressing the position one past the final element in the range to be searched.

_Pred

User-defined predicate function object that defines the condition to be satisfied if an element is to be counted. A predicate takes single argument and returns true or false.

 

Table 34.7

// algorithm, count_if()

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

 

bool isgreat(int value)

{    return value >8;    }

 

int main()

{

    vector <int> vec;

    vector <int>::iterator Iter;

    vec.push_back(13);

    vec.push_back(21);

    vec.push_back(9);

    vec.push_back(31);

    vec.push_back(8);

    vec.push_back(10);

    cout<<"vec data: ";

    for(Iter = vec.begin(); Iter != vec.end(); Iter++)

        cout<<*Iter<<" ";

    cout<<endl;

    int result1;

    cout<<"\nOperation: count_if(vec.begin(), vec.end(), isgreat)\n";

    result1 = count_if(vec.begin(), vec.end(), isgreat);

    cout<<"The number of elements in vec greater than 8 is: "<<result1<<endl;

    return 0;

}

 

Output:

 

C++ STL Algorithm count_if()

 

count_if()

 

  • The following example is to show how to use the count_if() STL function in Microsoft Visual C++ as an implementation dependent.

template<class InputIterator, class Predicate> inline size_t count_if(
			InputIterator First,
			InputIterator Last,
			Predicate P );
  • The class/parameter names in the prototype do not match the version in the header file. Some have been modified to improve readability.

  • The count_if() algorithm counts the number of elements in the range [First, Last) that cause the predicate to return true and returns the number of elements for which the predicate was true.

// algorithm, the countif()

// functions:

//   count_if()  - Count items in a range that satisfy a predicate.

//   begin()      - Returns an iterator that points to the first element in a sequence.

//   end()         - Returns an iterator that points one past the end of a sequence.

#include <iostream>

#include <algorithm>

#include <functional>

#include <string>

#include <vector>

using namespace std;

 

 

// return true if string str starts with letter 'C'

int MatchFirstChar(const string& str)

{

    string s("C");

    return s == str.substr(0, 1);

}

 

int main()

{

    const int VECTOR_SIZE = 110;

    // define a template class vector of strings

    typedef vector<string > StringVector;

    // define an iterator for template class vector of strings

    typedef StringVector::iterator StringVectorIt;

    // vector containing names

    StringVector NamesVect(VECTOR_SIZE);

    StringVectorIt start, end, it;

    // stores count of elements that match value.

    ptrdiff_t result = 0;

    // initialize vector NamesVect

    NamesVect[0] = "Learn";

    NamesVect[1] = "C";

    NamesVect[2] = "and";

    NamesVect[3] = "C++";

    NamesVect[4] = "also";

    NamesVect[5] = "Visual";

    NamesVect[6] = "C++";

    NamesVect[7] = "and";

    NamesVect[8] = "C++";

    NamesVect[9] = ".Net";

    // location of first element of NamesVect

    start = NamesVect.begin();

    // one past the location last element of NamesVect

    end = NamesVect.end();

    // print content of NamesVect

    cout<<"NamesVect: ";

    for(it = start; it != end; it++)

        cout<<*it<<" ";

    cout<<endl;

    // count the number of elements in the range [first, last +1) that start with letter 'C'

    result = count_if(start, end, MatchFirstChar);

    // print the count of elements that start with letter 'S'

    cout<<"Number of elements that start with letter \"C\" = "<<result<<endl;

}

 

Output:

 

C++ STL Algorithm count_if()

 

equal()

  1. template<class InputIterator1, class InputIterator2>bool equal( InputIterator1 _First1, InputIterator1 _Last1, InputIterator2 _First2 );

  1. template<class InputIterator1, class InputIterator2, class BinaryPredicate>bool equal( InputIterator1 _First1, InputIterator1 _Last1, InputIterator2 _First2, BinaryPredicate _Comp );

Parameters

 

Parameter

Description

_First1

An input iterator addressing the position of the first element in the first range to be tested.

_Last1

An input iterator addressing the position one past the final element in the first range to be tested.

_First2

An input iterator addressing the position of the first element in the second range to be tested.

_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 34.8

// algorithm, equal()

#include <vector>

#include <algorithm>

#include <iostream>

using namespace std;

 

// return whether second element is twice of the first

bool twice(int elem1, int elem2)

{    return elem1 * 2 == elem2;    }

 

int main()

{

    vector <int> vec1, vec2, vec3;

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

    int i;

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

        vec1.push_back(i);

    int j;

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

        vec2.push_back(j);

    int k;

    for(k = 10; k <= 15; k++)

        vec3.push_back(k);

    cout<<"vec1 data: ";

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

        cout<<*Iter1<<" ";

    cout<<endl;

    cout<<"vec2 data: ";

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

        cout<<*Iter2<<" ";

    cout<<endl;

    cout<<"vec3 data: ";

    for(Iter3 = vec3.begin(); Iter3 != vec3.end(); Iter3++)

        cout<<*Iter3<<" ";

    cout<<endl;

    // testing vec1 and vec2 for equality based on equality

    bool b;

    b = equal(vec1.begin(), vec1.end(), vec2.begin());

    if(b)

        cout<<"The vectors vec1 and vec2 are equal based on equality."<<endl;

    else

        cout<<"The vectors vec1 and vec2 are not equal based on equality."<<endl;

    // testing vec1 and vec3 for equality based on equality

    bool c;

    c = equal(vec1.begin(), vec1.end(), vec3.begin());

    if(c)

        cout<<"The vectors vec1 and vec3 are equal based on equality."<<endl;

    else

        cout<<"The vectors vec1 and vec3 are not equal based on equality."<<endl;

    // testing vec1 and vec3 for equality based on twice

    bool d;

    d = equal(vec1.begin(), vec1.end(), vec3.begin(), twice);

    if(d)

        cout<<"The vectors vec1 and vec3 are equal based on twice."<<endl;

    else

        cout<<"The vectors vec1 and vec3 are not equal based on twice."<<endl;

   return 0;

}

 

Output:

 

C++ STL Algorithm equal()

 

equal_range()

  1. template<class ForwardIterator, class Type>pair<ForwardIterator, ForwardIterator> equal_range( ForwardIterator _First, ForwardIterator _Last, const Type& _Val );

  2. template<class ForwardIterator, class Type, class Pr>pair<ForwardIterator, ForwardIterator> equal_range( ForwardIterator _First, ForwardIterator _Last, const Type& _Val, BinaryPredicate _Comp );

 

Parameters

 

Parameter

Description

_First

A forward iterator addressing the position of the first element in the range to be searched.

_Last

A forward iterator addressing the position one past the final element in the range to be searched.

_Val

The value in the ordered range that needs to be equivalent to the value of the element addressed by the first component of the pair returned and that needs to be less than the value of the element addressed by the second component of that pair returns.

_Comp

User-defined predicate function object that is true when the left-hand argument is less than the right-hand argument. The user-defined predicate function should return false when its arguments are equivalent.

 

Table 34.9

// algorithm, equal_range()

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

    pair < vector <int>::iterator, vector <int>::iterator > Result1, Result2, Result3;

    // constructing vectors vec1 with default less than ordering

    int i;

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

        vec1.push_back(i);

    int j;

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

        vec1.push_back(j);

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

    cout<<"vec1 data with range sorted 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;

    sort(vec2.begin(), vec2.end(), greater<int>());

    cout<<"\nvec2 data with range sorted by the binary predicate greater than 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;

    sort(vec3.begin(), vec3.end(), mod_lesser);

    cout<<"\nvec3 data with range sorted by the binary predicate mod_lesser is:\n";

    for(Iter3 = vec3.begin(); Iter3 != vec3.end(); Iter3++)

        cout<<*Iter3<<" ";

    cout<<"\n\n";

    // equal_range of 4 in vec1 with default binary predicate less <int>()

    Result1 = equal_range(vec1.begin(), vec1.end(), 4);

    cout<<"lower_bound in vec1 for the element with a value of 4 is: "<<*Result1.first<<endl;

    cout<<"upper_bound in vec1 for the element with a value of 4 is: "<<*Result1.second<<endl;

    cout<<"The equivalence class for the element with a value of 4 in \nvec1 includes the elements: ";

    for(Iter1 = Result1.first; Iter1 != Result1.second; Iter1++)

        cout<<*Iter1<<" ";

    cout<<endl<<endl;

    // equal_range of 4 in vec2 with the binary predicate greater <int>()

    Result2 = equal_range(vec2.begin(), vec2.end(), 4, greater <int>());

    cout<<"lower_bound in vec2 for the element with a value of 4 is: "<<*Result2.first<<endl;

    cout<<"upper_bound in vec2 for the element with a value of 4 is: "<<*Result2.second<<endl;

    cout<<"The equivalence class for the element with a value of 4 in\n vec2 includes the elements: ";

    for(Iter2 = Result2.first; Iter2 != Result2.second; Iter2++)

        cout<<*Iter2<<" ";

    cout<<endl<<endl;

    // equal_range of 4 in vec3 with the binary predicate mod_lesser

    Result3 = equal_range(vec3.begin(), vec3.end(), 4, mod_lesser);

    cout<<"lower_bound in vec3 for the element with a value of 4 is: "<<*Result3.first<<endl;

    cout<<"upper_bound in vec3 for the element with a value of 4 is: "<<*Result3.second<<endl;

    cout<<"equivalence class for the element with a value of 4 in \nvec3 includes the elements: ";

    for(Iter3 = Result3.first; Iter3 != Result3.second; Iter3++)

        cout<<*Iter3<<" ";

    cout<<endl<<endl;

    return 0;

}

 

Output:

C++ STL Algorithm equal_range()

 

tenouk C++ STL tutorial

 

 

 

 

 

 

 

 

 

 

 

 

Further C++ STL algorithm related reading:

 

  1. A complete C & C++ Standard Library documentation that includes STL.

  2. Source code in text is available in C++ Algorithm source code sample.

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

  4. C++ Templates programming tutorials.

 

 

 

 

 

 

 

|< C++ STL Algorithm 2 | Main | C++ STL Algorithm 4 >| 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