# My Training Period:        hours

Continue from the previous Module, more algorithm member functions program examples. Compiled using MicrosoftVisual 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 inC++ Algorithm source code sample.

# 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

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

}

# count()

• Returns the number of elements in a range whose values match a specified value.

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

# Parameters

#### Table 34.6

• The return value is the difference type of the InputIterator that counts the number of elements in the range [_First, _Last) that have value _Val.

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

• This algorithm is generalized to count elements that satisfy any predicate with the template function count_if().

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

}

# count_if()

• Returns the number of elements in a range whose values satisfy a specified condition.

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

InputIterator _First, InputIterator _Last, Predicate _Pred );

# Parameters

#### Table 34.7

• The return value is the number of elements that satisfy the condition specified by the predicate.

• This template function is a generalization of the algorithmcount(), replacing the predicate "equals a specific value" with any predicate.

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

}

# 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 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.Thecount_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 #include #include #include #include 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);

}

# equal()

• Compares two ranges element by element either for equality or equivalence in a sense specified by a binary predicate.

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

#### Table 34.8

• The return value is true if and only if the ranges are identical or equivalent under the binary predicate when compared element by element; otherwise, false.

• The range to be searched must be valid; all pointers must be de-referenceable and the last position is reachable from the first by incrementation.

• The time complexity of the algorithm is linear in the number of elements contained in the range.

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

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

}

# equal_range()

• Finds a pair of positions in an ordered range, the first less than or equivalent to the position of a specified element and the second greater than the element's position, where the sense of equivalence or ordering used to establish the positions in the sequence may be specified by a binary predicate.

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

• The return value is a pair of forward iterators addressing two positions in an ordered range in which the first component of the pair refers to the position where an element is or would be if it had a value that is less than or equivalent to a specified value and the second component of the pair refers to the first position where an element has a value that is greater than the value specified, where the sense of equivalence or ordering may be specified by a binary predicate.

• Alternatively, the pair of forward iterators may be described as specify a sub range, contained within the range searched, in which all of the elements are equivalent to the specified value in the sense defined by the binary predicate used.

• The first component of the pair of the algorithm returnslower_bound(), and the second component returnsupper_bound().

• The sub range defined by the pair of iterators returned by theequal_range() algorithm contains the equivalence class, in the standard set-theoretic sense, of the element whose value is specified as a parameter.

• 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 equal_range() 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, 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:

tenouk C++ STL tutorial

# Further C++ STL algorithm related reading:

1. Acomplete C Standard Library.

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

3. Source code in text is available inC++ Algorithm source code sample.

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

5. C++ Templates programming tutorials.